\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

\newcommand{\solution}{\paragraph{Solution:}}

\begin{document}

\title{Problem Set \#3}
\author{Quantum Error Correction\\Instructors:  Daniel Gottesman}
\date{Due Tuesday, Mar.~31, 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}{Quantum Hamming bound for qudit codes (15 points)}

The quantum Hamming bound for qudits of dimension $p$ becomes
\begin{equation}
\sum_{s=0}^t \binom{n}{s} (p^2-1)^s \leq p^{n-k},
\end{equation}
which must hold for non-degenerate $((n, p^k, 2t+1))_p$ codes.
\begin{probparts}
\item (5 points) For what values of $p$ does a $[[5,1,3]]_p$ code saturate the quantum Hamming bound?
\item (5 points) For what values of $p$ would a $[[9,1,5]]_p$ code saturate the quantum Hamming bound?  For which values of $p$ would the code violate the quantum Hamming bound?  (Note that such a code is only known to exist for prime power $p$ with $p \geq 9$.)
\item (5 points) For $p=3$, find the smallest integer values of $n$ and $k$ such that an $[[n,k,3]]_3$ code saturates the quantum Hamming bound or show that no integer $n$ and $k$ work.
\end{probparts}

\medskip

\problem{2}{Transversal gates for qutrit code (25 points)}

For this problem, consider the following $[[4,2,2]]_3$ stabilizer code on qutrits:

\begin{tabular}{ccccc}
  & $X$ & $X$ & $X^{-1}$ & $X^{-1}$ \\
  & $Z$ & $Z$ & $Z$ & $Z$ \\
\hline 
$\overline{X}_1$ & $X$ & $X^{-1}$ & $I$ & $I$ \\
$\overline{Z}_1$ & $Z$ & $I$ & $Z$ & $I$ \\
$\overline{X}_2$ & $I$ & $X$ & $I$ & $X^{-1}$ \\
$\overline{Z}_2$ & $I$ & $I$ & $Z$ & $Z^{-1}$
\end{tabular}

For each of the physical gates below, determine if it is valid gadget (meaning it preserves the codespace) and, if so, what logical gate it performs.  (You can specify the logical gate via a circuit or as a transformation on the logical Paulis.)

\begin{probparts}
\item (5 points) $\mathcal{F}^{\otimes 4}$, where $\mathcal{F}$ is the qutrit Fourier transform, $\mathcal{F} \ket{a} = \sum_b \omega^{ab} \ket{b}$.
\item (5 points) $S_2^{\otimes 4}$, where $S_2$ is multiplication by $2$, $S_2 \ket{a} = \ket{2a}$, with arithmetic mod $3$.
\item (5 points) $R^{\otimes 4}$, where $R$ is the quadratic phase gate, $R \ket{a} = \omega^{a(a-1)/2} \ket{a}$.
\item (5 points) $SUM^{\otimes 4}$, where $SUM$ is the two-qutrit sum gate, $SUM \ket{a} \ket{b} = \ket{a} \ket{a + b}$, with arithmetic mod $3$.
\item (5 points) Find a valid gadget of the form $\mathcal{F}^{a_1} \otimes \mathcal{F}^{a_2} \otimes \mathcal{F}^{a_3} \otimes \mathcal{F}^{a_4}$, with $\mathcal{F}$ the Fourier transform as in part a and not all of the $a_i$'s are the same.  Give the logical gate performed by this transversal gate. 
\end{probparts}

\medskip

\problem{3}{Definitions of fault tolerance for multiple-qubit gadgets (20 points)}

\begin{probparts}

\item (5 points) Write down the Gate Propagation Property (GPP) and the Gate Correctness Property (GCP) for a gate gadget acting on 3 blocks of the QECC.

\item (5 points) Write down the Preparation Correctness Property (PCP) for a Bell state preparation gadget, which prepares the logical $\ket{\overline{00}} + \ket{\overline{11}}$ state for two blocks of the QECC.  

\item (5 points) Write down two versions of the Preparation Propagation Property (PPP) for a Bell state preparation gadget when there are $s$ faults in the gadget: a weak version allowing $s$ errors per block and a strong version allowing $s$ errors total between the blocks.

\item (5 points) Suppose you perform a Bell state preparation gadget that satisfies the PCP and either the weak or strong PPP, and then do a two-block transversal gate between the two blocks produced by the Bell state preparation gadget (with no EC step between).  If there are $r$ faults in the Bell state gadget and $s$ faults in the transversal gate, what is the smallest $t$ such that the final state is guaranteed to pass a $t$-filter?  Give answers for both cases: When the Bell state preparation gadget satisfies the weak PPP and when it satisfies the strong PPP.

\end{probparts}




\end{document}
