Fibonacci scheme for fault-tolerant quantum computation

We rigorously analyze Knill’s Fibonacci scheme for fault-tolerant quantum computation, which is based on the recursive preparation of Bell states protected by a concatenated error-detecting code. We prove lower bounds on the threshold fault rate of $0.67\times {10}^{-3}$ for adversarial local stochastic noise, and $1.25\times {10}^{-3}$ for independent depolarizing noise. In contrast to other schemes with comparable proved accuracy thresholds, the Fibonacci scheme has a significantly reduced overhead cost because it uses postselection far more sparingly.

Figure 1

(Color online) The gadget for a CNOT gate protected by $C_4$. A transversal CNOT gate, which implements the logical CNOT gate acting on two blocks, is preceded and followed by logical teleportations, which extract the code’s error syndrome. Arrows denote CNOT gates, with the arrow tip pointing to the target qubit. Green and blue triangles pointing to the left denote ${\mathcal{M}}_{{\sigma }_x}$ and ${\mathcal{M}}_{{\sigma }_z}$, respectively, and Bell pairs encoded in $C_4$ (1-BPs) are prepared as in Fig. 2.

Figure 2

(Color online) (a) Preparation of an unencoded Bell pair (0-BP) where green and blue triangles pointing to the right denote ${\mathcal{P}}_{\mid +⟩}$ and ${\mathcal{P}}_{\mid 0⟩}$, respectively. (b) A Bell pair encoded in $C_4$ (1-BP) is constructed by preparing one block in the logical ∣+⟩ state, a second block in the logical ∣0⟩ state, and applying transversal CNOT gates. (c) The two blocks of a 1-BP are teleported, using two other 1-BPs, in order to limit correlations between errors in different output blocks. Depending on the measurement outcomes, logical Pauli operators (not shown) acting on the two output blocks may be needed to complete the teleportations.

Figure 3

(Color online) (a) The complete preparation circuit for a $j$-BP where $j>1$. It is identical to the circuit shown in Fig. 2c, except that a final teleportation of each level-$(j-1)$ subblock has been added. (b) The teleportation circuit.

Figure 4

(Color online) The noisy preparation of a 0-BP is equivalent to an ideal 0-BP followed by noisy storage locations acting on the two qubits (denoted by black dots). Noise is quasi-independent and the strength for errors of type $m$ is ${\epsilon }_{{\sigma }_m}(0,0)$.

Figure 5

(Color online) (a) The effective circuit ${\mathfrak{P}}_{1\text{−}\mathrm{BP}}$ that produces the same output as the 1-BP preparation circuit in Fig. 2c; here, ${\mathcal{D}}^{-1}$ denotes an ideal encoder and the black dots are noisy storage locations. (b) The circuit in (a) can be represented as a directed depth-2 tree, with noisy locations at the vertices. The noise is quasi-independent for any legitimate set of vertices (a set is “legitimate” if it contains no descendant of a member of the set).

Figure 6

(Color online) The effective circuit ${\mathfrak{P}}_{j\text{−}\mathrm{BP}}$ that produces the same output as the $j$-BP preparation circuit in Fig. 3. The circuit is a depth-$(j+1)$ directed tree, with noisy locations at the vertices, and the noise is quasi-independent for any legitimate set of vertices. Conditioned on accepting the $j$-BP, the noise strength for errors of type $m$ is ${\epsilon }_{{\sigma }_m}(i,j\mid j)$ at depth-$(j+1-i)$ in the tree.

Figure 7

(Color online) (a) The $j$-BP preparation circuit, where each input state is a $(j-1)$-BP, each CNOT gate denotes a transversal CNOT acting on two ${\left(C_4\right)}^{▷(j-1)}$ blocks, and each measurement denotes a transversal measurement of a ${\left(C_4\right)}^{▷(j-1)}$ block. The magnified drawing shows the effective circuit ${\mathfrak{P}}_{(j-1)\text{−}\mathrm{BP}}$, a depth-$j$ directed tree, that produces the same output as the $(j-1)$-BP preparation circuit; this $(j-1)$-BP is used to teleport a ${\left(C_4\right)}^{▷j-1}$ subblock. (b) Construction of the effective circuit ${\mathfrak{P}}_{j\text{−}\mathrm{BP}}$ that produces the same output as the $j$-BP preparation circuit. Noisy locations at vertices of depth 3 or more are inherited from the $(j-1)$-BPs used in the subblock teleportations. The noise at depth 2 comes from two contributions, which are combined together: the noise in the input $(j-1)$-BP (shown inside the dashed curve) and the noise due to logical errors in the subblock teleportation (shown inside the solid curve). The noise at depth 1 comes from logical errors in the block teleportation (also shown inside the solid curve).

Figure 8

(Color online) An alternative preparation circuit for $j$-BPs. Compared to the circuit in Fig. 3, the direction of the CNOT gates is reversed so that type-$x$ and type-$z$ errors propagate differently than in Fig. 3.

Figure 9

(Color online) On the top, the effective noise strength ${\epsilon }_{\mathrm{css}}\left(j\right)$ for ${\mathcal{G}}_{\mathrm{CSS}}$ operations protected by ${\left(C_4\right)}^{▷j}$, as a function of the fundamental noise strength $\epsilon$, for $j=1,2,3,4,5$. The straight lines serve as guides to the eye for points with the same value of $j$. For $\epsilon$ satisfying Eq. (38), ${\epsilon }_{\mathrm{css}}\left(j\right)$ decreases as $j$ increases. On the bottom, the probability $p(j\mid j-1)$ of accepting a $j$-BP conditioned on having accepted all $(j-1)$-BPs, as a function of the fundamental noise strength $\epsilon$, for $j=1,2,3,4,5$. For $\epsilon$ satisfying Eq. (38), $p(j\mid j-1)$ approaches unity as $j$ increases. The different behavior of the probability of acceptance for $j=1,2$ compared to $j⩾3$ is due to omitting the subblock teleportations for $j=2$ but including them for $j⩾3$.

Figure 10

(Color online) A purification circuit for the preparation of the state ∣0⟩: Two copies of ∣0⟩ are prepared, a CNOT gate is applied, and ${\sigma }_z$ is measured on the second output qubit; the preparation is accepted if the measurement outcome is ${\sigma }_z=+1$. For independent depolarizing noise, the probability of a type-$x$ error conditioned on accepting the ∣0⟩ state is $\frac{8}{15}\epsilon +O\left({\epsilon }^2\right)$.