Quantum computation with realistic magic-state factories

Leading approaches to fault-tolerant quantum computation dedicate a significant portion of the hardware to computational factories that churn out high-fidelity ancillas called magic states. Consequently, efficient and realistic factory design is of paramount importance. Here we present the most detailed resource assessment to date of magic-state factories within a surface code quantum computer, along the way introducing a number of techniques. We show that the block codes of Bravyi and Haah [Phys. Rev. A 86, 052329 (2012)] have been systematically undervalued; we track correlated errors both numerically and analytically, providing fidelity estimates without appeal to the union bound. We also introduce a subsystem code realization of these protocols with constant time and low ancilla cost. Additionally, we confirm that magic-state factories have space-time costs that scale as a constant factor of surface code costs. We find that the magic-state factory required for postclassical factoring can be as small as 6.3 million data qubits, ignoring ancilla qubits, assuming ${10}^{-4}$ error gates and the availability of long-range interactions.

Figure 1

Explicit circuit for realizing Bravyi-Haah $(3k+8)\to k$ block protocols for $k=2,6,10,14,....$ Squares indicate the $(3k+8)$ noisy $|T\rangle$ magic states to be distilled, and circles represent ancilla qubits used to effect measurements on the magic states. Increasing $k$ does not increase the number of time steps in the protocol but increases the number of qubits involved in a block. As we increase $k$, we add qubits to the tail end, with the protocol translationally invariant along the tail. We report that we have independently confirmed the validity of the protocol for $k=2$ by full wave-function simulation, which further confirmed that all single errors are detected and all two errors processes lead to outputs with correlated errors.

Figure 2

The tree structure of many rounds of distillation, with branches (directed black lines) that merge at branching points that we call modules. The thickness of the branch increases with each round. The main plot shows a fictitious scheme where $n_l=3$ and $k_l=2$ for all rounds. Inset: The structure within a module. Incoming branches contain many qubits; here this is shown to be four. These qubits undergo a permutation $\sigma$ and are fed into an instance of a block of a distillation protocol shown as a square. Here the three incoming branches carry four qubits, and so we need four instances of a $3\to 2$ protocol. We use a fictitious protocol to keep the numbers low enough to illustrate clearly. Each of the four blocks output two qubits, and these are merged into a branch of eight qubits fed into a later module. A pernicious error pattern is shown in red (lighter gray), which is detected in two of distillation blocks, marked with crosses, but goes undetected in a third block.

Figure 3

(a) and (b) The cost $\mathcal{C}$ of the Bravyi-Haah protocols utilizing both block checking and module checking. It can be seen that only around the transitions to an additional level of distillation is block checking very slightly preferable.

Figure 4

The concept of balanced investment. During the initial rounds of distillation smaller surface codes can be used to encode the logical information. The factory requires only logical surfaces of the distance corresponding to the target error rate of the round in which that qubit is involved. This target in each round will depend on the final error target, the protocol being used to achieve it, and the error rate of the raw state.

Figure 5

Space-time overheads of producing both (a) and (b) $|T\rangle$ states and (c) and (d) $|\mathrm{Toff}\rangle$ states. Note that module checking is more beneficial when one of the rounds of distillation is Toffoli.

Figure 6

To produce $T$ magic states at a “time-optimal” rate the factory must, on average, produce states at a rate equal to the fastest rate at which they can be used in sequence by an algorithm. In this paper, where we have assumed that $t_{\mathrm{sc}}=10t_{\mathrm{meas}/\mathrm{ff}}$, this means ten magic states must be produced on average every $t_{\mathrm{sc}}$ to keep up with the time-optimal implementation of the algorithm. As this figure makes clear, it is indeed possible to produce a given number of magic states faster (slower) than this using more (fewer) qubits. Each data point represents one possible magic-state factory given the input error and target number of ${10}^{16}T$ magic states; only the factories near the boundary between possible and impossible factories are shown. Not shown in the lower right of each graph are myriad other possible factories of lower rate and higher overhead. As seen clearly in (a), doubling the size of the factory can allow one to more than double the rate of magic-state production when the larger factory allows the use of the higher-$k$ (and therefore higher-rate) block codes. This point is less evident in (b), where only two rounds of distillation can be sufficient and the higher-$k$ block codes are not necessarily optimal.

Figure 7

The scaling of resource cost in qubit rounds per magic state is not worse than that of the surface code. This corroborates the predictions of Raussendorf et al. [28] and suggests that the asymptotic overhead scaling $\sim O(log{\left(N\right)}^3)$ of the surface code is applicable to universal fault-tolerant computing with gate counts in the regime of practical interest. Lines are fitted functions of the form $\mathcal{V}(p_{\mathrm{g}},N)=alog{\left(N\right)}^b+c$.

Figure 8

Squares represent magic states to be distilled, and circles are ancillas used to implement measurements in Reed-Muller. Edges show required hardware connections and associated required control-phase gates. Edges show time ordering of control-phase gates, e.g., red, purple, green, blue, and gold (dark to light gray), demonstrating the required entanglement can be established in five time steps. Sometimes we call this the graph representing $G_z^{\text{RM}}$.

Figure 9

Squares represent magic states to be distilled, and circles are ancillas used to implement the stabilizer measurements which project the $T$ states into the Toffoli state. As before, edges show required hardware connections and associated control-phase gates. Edges show time ordering of control phase gates, e.g., red, purple, green, blue, and gold (dark to light gray), demonstrating the required entanglement can be established in four time steps for the $Z$ stabilizers and five time steps for the single $X$ stabilizer, which utilizes just two ancillas. We call this the graph representing $G_z^{\mathrm{Toff}}$.

Figure 10

Numeric vs analytic. (a) Bravyi-Haah block protocols with two and three rounds of distillation. (b) Toffoli protocol followed by one or two rounds of Bravyi-Haah. (c) One or two rounds of Bravyi-Haah followed by the Toffoli protocol. The close correspondence of our analytic treatment of the factory and numerical simulations is demonstrated for two and three rounds of the magic-state distillation with module checking. Points represent simulation data, while the lines are the corresponding analytic estimates as determined by Theorem 1. The protocols are labeled by the $k$ value of each round, which is set to be equal for each round of distillation. The global error, the probability of a logical error anywhere in the output of the factory, is shown. For a “2-2-2” factory this is the probability of an error anywhere in the 8 output magic states; for a “26-26-26” this corresponds to an error anywhere in the 17,576 magic states that this factory produces.

Figure 11

Rare-event method. When simulating the fictional factory of Fig. 2 with our rare-event method, only the red (darker gray) highlighted parts of the factory are actively simulated, i.e., require computation of the stabilizer outcomes and the logical state of the outputs.