\documentclass{article}
\usepackage{amsthm,amsmath,amsfonts,fullpage}

\newcounter{probpart}
\newenvironment{probparts}{\begin{list}{\alph{probpart})}%
{\usecounter{probpart}}}{\end{list}}

\newcommand{\problem}[2]{\noindent {\bf Problem \#{#1}.  {#2}}}

\newcommand{\ket}[1]{|{#1}\rangle}
\newcommand{\bra}[1]{\langle{#1}|}

\newcommand{\enczero}{\ket{\overline{0}}}
\newcommand{\encone}{\ket{\overline{1}}}

\newcommand{\Hilbert}{\mathcal{H}}                       % a generic Hilbert space
\newcommand{\Hilbertk}[1]{\mathcal{H}_{{#1}}}       % a Hilbert space of dimension k
\newcommand{\channel}[1]{\mathcal{#1}}              % font choice for a quantum channel

\begin{document}

\title{Problem Set \#2}
\author{Quantum Error Correction\\Instructor: Daniel Gottesman}
\date{Due Tuesday, Mar.~10, 2026, 11:59 PM}

\maketitle

General instructions: No use of LLMs.  If you collaborate or use any outside resources, remember to cite them in your solutions.

This problem set has problems on 2 pages.

\problem{1}{Low-density parity check CSS codes (15 points)}

A classical LDPC (``low density parity check'') code is an $[n,k,d]$ linear code where each row of the parity check matrix has at most $r$ $1$'s and each column of the parity check matrix has at most $c$ $1$'s, with $r$ and $c$ of constant size (as $n$ gets large).  (Sometimes LDPC codes with $r$ and $c$ increasing sublinearly with $n$ are also considered, but assume $r$ and $c$ are constant for the purposes of this problem.)  Classical LDPC codes are interesting because they can achieve good values of $k/n$, $d/n$, and also generally have good decoding algorithms.

A quantum LDPC code is a stabilizer code for which each generator has low weight and each qubit appears in only a small number of generators.  One might try to make good quantum LDPC codes using the CSS construction, based on pairs of classical LDPC codes $C_1(n)$ and $C_2(n)$.  Suppose that one finds a family of such codes which produce $[[n,k,d]]$ quantum codes with $k/n$ and $d/n$ both constant as $n$ gets large.  Show that this family of quantum codes must be degenerate for large $n$.

[It took a long time to find such codes in the quantum case.  The point of the problem is that, because degeneracy is important to find such codes, the quantum case is not a straightforward application of the CSS construction.]

\medskip

\problem{2}{Analyzing Clifford group circuits (25 points)}

In the following diagrams, $R = R_{\pi/4}$ is the matrix $\mathrm{diag}(1,i)$ and $H$ is the Hadamard transform.

\begin{probparts}
\item (10 points) For the following Clifford group circuit, compute the overall action on Paulis and use that to write down the $4 \times 4$ unitary matrix performed by the circuit:

\begin{center}
\begin{picture}(140,60)

\put(20,20){\line(1,0){14}}
\put(20,40){\line(1,0){54}}

\put(34,14){\framebox(12,12){$H$}}
\put(46,20){\line(1,0){28}}

\put(60,40){\circle*{4}}
\put(60,40){\line(0,-1){24}}
\put(60,20){\circle{8}}

\put(74,34){\framebox(12,12){$H$}}
\put(74,14){\framebox(12,12){$R$}}
\put(86,40){\line(1,0){34}}
\put(86,20){\line(1,0){34}}

\put(100,20){\circle*{4}}
\put(100,20){\line(0,1){24}}
\put(100,40){\circle{8}}

\end{picture}
\end{center}

\item (15 points) For the following Clifford group circuit, use Clifford simulation techniques to compute the full probability distribution of the $8$ possible classical outputs after measuring all qubits in the computational basis:

\begin{center}
\begin{picture}(200,80)

\put(20,20){\line(1,0){14}}
\put(20,40){\line(1,0){54}}
\put(20,60){\line(1,0){14}}

\put(0,20){\makebox(20,0){$\ket{0}$}}
\put(0,40){\makebox(20,0){$\ket{0}$}}
\put(0,60){\makebox(20,0){$\ket{0}$}}

\put(34,54){\framebox(12,12){$H$}}
\put(34,14){\framebox(12,12){$H$}}
\put(46,60){\line(1,0){68}}
\put(46,20){\line(1,0){114}}

\put(60,60){\circle*{4}}
\put(60,60){\line(0,-1){24}}
\put(60,40){\circle{8}}

\put(74,34){\framebox(12,12){$R$}}
\put(86,40){\line(1,0){28}}

\put(100,20){\circle*{4}}
\put(100,20){\line(0,1){24}}
\put(100,40){\circle{8}}

\put(114,54){\framebox(12,12){$H$}}
\put(114,34){\framebox(12,12){$R$}}
\put(126,60){\line(1,0){34}}
\put(126,40){\line(1,0){8}}

\put(134,34){\framebox(12,12){$H$}}
\put(146,40){\line(1,0){14}}

\put(160,20){\line(2,1){10}}
\put(160,20){\line(2,-1){10}}
\put(170,15){\line(0,1){10}}

\put(160,40){\line(2,1){10}}
\put(160,40){\line(2,-1){10}}
\put(170,35){\line(0,1){10}}

\put(160,60){\line(2,1){10}}
\put(160,60){\line(2,-1){10}}
\put(170,55){\line(0,1){10}}

\end{picture}
\end{center}

\end{probparts}

\medskip

\problem{3}{Twirling (20 points)}

Let $S(\rho)$ be a quantum operation (a completely positive trace-preserving map) taking $n$ qubits to $n$ qubits.
{\bf Hint:} (For both parts) Any $2^n \times 2^n$ matrix can be expanded in the basis of Pauli operators.

\begin{probparts}
\item (10 points) Consider the following quantum operation: Choose a uniformly random $P \in \mathcal{P}_n/\{\pm I, \pm i I\}$ (i.e., a Pauli ignoring global phase).  Apply $P^\dagger$, then $S$, then $P$ (for the same $P$).  Show that, averaging over $P$, the resulting quantum operation is a Pauli channel.  A Pauli channel is any channel $\mathcal{S}$ such that $\mathcal{S}(\rho) = (1- \sum_P p_P) \rho + \sum_{P} p_P P \rho P^\dagger$.  (Where the sums are over non-trivial Paulis without phases, $\mathcal{P}_n/\{\pm 1, \pm i\} \setminus \{I\}$.)

\item (10 points) Now instead of choosing a random Pauli, choose a random Clifford and do the same thing, i.e., uniformly random $C \in \mathcal{C}_n/\{e^{i\phi} I \}$, apply $C^\dagger$, then $S$, then $C$.  Show that, averaging over $C$, the resulting quantum channel is a depolarizing channel.  A depolarizing channel is a channel $\mathcal{S}$ such that $\mathcal{S}(\rho) = [1-  (4^{n}-1)p] \rho + \sum_{P} p P \rho P^\dagger$.  (Where the sums are over non-trivial Paulis without phases, $\mathcal{P}_n/\{\pm 1, \pm i\} \setminus \{I\}$.) That is, an $n$-qubit depolarizing channel is a Pauli channel where all probabilities $p_P$ are the same.
% 4^n corrected from 2^n
\end{probparts}

\end{document}
