Magic-State Distillation in All Prime Dimensions Using Quantum Reed-Muller Codes

We propose families of protocols for magic-state distillation—important components of fault-tolerance schemes—for systems of odd prime dimension. Our protocols utilize quantum Reed-Muller codes with transversal non-Clifford gates. We find that, in higher dimensions, small and effective codes can be used that have no direct analogue in qubit (two-dimensional) systems. We present several concrete protocols, including schemes for three-dimensional (qutrit) and five-dimensional (ququint) systems. The five-dimensional protocol is, by many measures, the best magic-state-distillation scheme yet discovered. It excels both in terms of error threshold with respect to depolarizing noise ($36.3\%$) and the efficiency measure known as yield, where, for a large region of parameters, it outperforms its qubit counterpart by many orders of magnitude.

Popular Summary

A quantum computer exploits the nonclassical aspects of quantum mechanics, but its extreme sensitivity to noise makes fault-tolerant techniques a must for it to operate reliably. A key component in high-threshold fault-tolerance schemes is the preparation of magic states, quantum states in a superposition of classical states, that are required to exploit quantum effects. However, the slightest of experimental imperfections results in the preparation of flawed magic states, unsuitable for immediate use in quantum computers. Fortunately, many copies of flawed magic states can be distilled down to a smaller number of suitable magic states. This process of magic-state distillation, however, forms a bottleneck in implementations of the already proposed fault-tolerant techniques in terms of the impractically high overheads in resources such as memory and running time. Unless overcome, such overhead costs could consign quantum computers to history books as a theoretically possible, but practically infeasible, technology. We propose in this paper that a shift of magic-state distillation from the current qubit paradigm (involving two-level systems) to a qudit one (involving $d$-level systems) may provide a way to overcome the overhead bottleneck.

Our starting point was curiosity: Can we achieve magic-state distillation in more complex systems? Quantum computing is usually conceived in terms of qubits, but this need not be the case. In fact, qudits can be the basis for a quantum computer, and we designed methods of magic-state distillation for all prime numbers $d$. To our surprise, by exploiting new insights into number-theoretic properties of qudit computers, some of our protocols offer substantial improvements over their better-known qubit cousins. In particular, five levels appear as the optimal case where our protocol outperforms all previously discovered protocols in all figures of merit. Notably, the potential resource savings in device memory could easily be on the order of a millionfold.

This work opens the door for the development of qudit-based fault-tolerance schemes based on magic-state distillation. These schemes may offer significant advantages over their qubit counterparts and hence bring the development of a scalable quantum computer closer to our grasp.

Figure 1

An outline of a single round of magic-state-distillation protocol. Within many architectures of fault-tolerant quantum computing, a large proportion of the device is committed to these magic-state factories. Each attempt uses $n$ copies of a state $\rho$ and when successful outputs a state ${\rho }^{\prime }\propto \mathcal{E}({\rho }^{\otimes n})$. For $n$ given successful attempts, the output states are used as inputs into the next iteration. Within the magic-state model, the completely positive map, $\mathcal{E}$, is composed of a sequence of Clifford unitaries and Pauli measurements. This figure illustrates a protocol where $n=4$, for example, the ququint, $d=5$, protocol that we discuss throughout the article.

Figure 2

The canonical $C_M$ plane for a qutrit, $d=3$, onto which any state can be projected by $C_M$ twirling. Every quantum state is a point in the complex plane for the complex number $z_{\rho }=\mathrm{tr}(C_M\rho )$. The three pure magic states, $|M_k⟩$, take values $z=1,\omega ,{\omega }^2$, which have $|z{|}^2=1$ and so lie on a circle in the plane. All physical states have $z=(1-f_1-f_2)+\omega f_1+{\omega }^2{f}_2$, and so lie in the convex hull of the pure magic states, forming a triangle of physical states. The distillable region of states can, by use of the ${\mathcal{Q}\mathcal{R}\mathcal{M}}_3(2)$ protocol, be brought arbitrarily close to the nearest pure magic state. The stabilizer states are the convex hull over the set of points, $z$, taken for each of the pure stabilizer states. It is impossible to distill not only the stabilizer states but also the bound states, as demonstrated in Ref. 42. Note that the rotational symmetry is to be expected, as the Pauli $Z$ rotation performs a rotation in the $C_M$ plane.

Figure 3

The output error ${ϵ}^{\prime }$ against input error $ϵ$ for (a) ${\mathcal{Q}\mathcal{R}\mathcal{M}}_3(2)$ and (b) ${\mathcal{Q}\mathcal{R}\mathcal{M}}_5(1)$. For a fixed $ϵ$, there are many different compatible states, and so there are many different possible output ${ϵ}^{\prime }$. These output ${ϵ}^{\prime }$ are shown as a region rather than as a single curve. For the worst-case noise, we mark the threshold ${ϵ}^{*}$. The dashed line shows the specific instance of depolarizing noise, and the associated depolarizing threshold ${ϵ}_{\mathrm{dep}}^{*}$ is also shown. The straight line is simply the “breakeven” line.

Figure 4

The yield on a log scale of our protocols, ${\mathcal{Q}\mathcal{R}\mathcal{M}}_3(2)$ and ${\mathcal{Q}\mathcal{R}\mathcal{M}}_5(1)$ (blue), compared with the Bravyi-Kitaev ${\mathcal{Q}\mathcal{R}\mathcal{M}}_2(4)$ (red) protocol. (a) and (c) are a function of initial error probabilities ${ϵ}_{\mathrm{in}}$ and target error probabilities ${ϵ}_{\mathrm{target}}$. For the qutrit and ququint states, the noise is depolarizing. (a) and (c) come with cross sections (b) and (d), respectively, with the target error probability held constant. The sudden changes in yield occur because of discrete changes in the number of iterations required.