Magic-state distillation with low overhead

We propose a family of error-detecting stabilizer codes with an encoding rate of $1/3$ that permit a transversal implementation of the gate $T=\exp (-i\pi Z/8)$ on all logical qubits. These codes are used to construct protocols for distilling high-quality “magic” states $T\left|+\right.〉$ by Clifford group gates and Pauli measurements. The distillation overhead scales as $O({\log }^{\gamma }(1/\epsilon ))$, where $\epsilon$ is the output accuracy and $\gamma ={\log }_2\left(3\right)\approx 1.6$. To construct the desired family of codes, we introduce the notion of a triorthogonal matrix, a binary matrix in which any pair and any triple of rows have even overlap. Any triorthogonal matrix gives rise to a stabilizer code with a transversal $T$ gate on all logical qubits, possibly augmented by Clifford gates. A powerful numerical method for generating triorthogonal matrices is proposed. Our techniques lead to a twofold overhead reduction for distilling magic states with accuracy $\epsilon \sim {10}^{-12}$ compared with previously known protocols.

Figure 1

Implementation of the $T$ gate using CO and one copy of the ancillary state $\left|A\right.〉$. If the ancilla is a mixture of $\left|A\right.〉$ and $Z\left|A\right.〉$ with probabilities $1-p$ and $p$, respectively, the circuit enacts a noisy version of the $T$ gate, namely, ${\rho }_{\mathrm{out}}=(1-p)T{\rho }_{\mathrm{in}}{T}^{†}+pZT{\rho }_{\mathrm{in}}{T}^{†}Z=\mathcal{E}\circ \mathcal{T}\left({\rho }_{\mathrm{in}}\right)$. The above circuit is used $n$ times in the subroutine of Fig. 2.

Figure 2

The distillation subroutine for the magic state $\left|A\right.〉$ based on a triorthogonal matrix $G$. The encoder prepares $k$ copies of the state $\left|+\right.〉$ encoded by the stabilizer code $\mathrm{CSS}\left(X,{\mathcal{G}}_0;Z,{\mathcal{G}}^{\perp }\right)$. Implementation of each $T$ gate consumes one ancillary $\left|A\right.〉$ state, as shown in Fig. 1. If the ancillae $\left|A\right.〉$ have error rate $p$, each ideal $T$ gate is followed by a $Z$ error with probability $p$. The Clifford operator $U$ is constructed in Lemma 2. Note that $U$ is diagonal in the $Z$ basis and thus commutes with any $Z$ error. The syndrome $s$ is measured only for $X$-type stabilizers $X\left(f^a\right)$, where $f^a$ are the rows of $G_0$. In the case when all stabilizers $X\left(f^a\right)$ have eigenvalue $+1$ (trivial syndrome) the decoder is applied. It returns $k$ copies of state $\left|A\right.〉$ with the overall error probability $O\left(p^d\right)$. The trivial syndrome is observed with probability $1-O\left(p\right)$.

Figure 3

Distillation cost $C$ as a function of the target error rate $\epsilon ={10}^{-\delta }$ for a fixed input error rate $p=0.01$. The top curve is obtained from [18], and the bottom curve is obtained from the optimization using the triorthogonal matrices $G\left(k\right)$. The lines are a guide to the eye.