We present an infinite family of protocols to distill magic states for T -gates that has a low space overhead and uses an asymptotic number of input magic states to achieve a given target error that is conjectured to be optimal. The space overhead, defined as the ratio between the physical qubits to the number of output magic states, is asymptotically constant, while both the number of input magic states used per output state and the T -gate depth of the circuit scale linearly in the logarithm of the target error δ (up to log log 1 / δ ). Unlike other distillation protocols, this protocol achieves this performance without concatenation and the input magic states are injected at various steps in the circuit rather than all at the start of the circuit. The protocol can be modified to distill magic states for other gates at the third level of the Clifford hierarchy, with the same asymptotic performance. The protocol relies on the construction of weakly self-dual CSS codes with many logical qubits and large distance, allowing us to implement control-SWAPs on multiple qubits. We call this code the "inner code". The control-SWAPs are then used to measure properties of the magic state and detect errors, using another code that we call the "outer code". Alternatively, we use weakly-self dual CSS codes which implement controlled Hadamards for the inner code, reducing circuit depth. We present several specific small examples of this protocol.
Magic state distillation is a crucial yet resource-intensive process in fault-tolerant quantum computation. The protocol's overhead, defined as the number of input magic states required per output magic state with an error rate below
ε, typically grows as
O(logγ(1/ε)). Achieving smaller overheads, i.e., smaller exponents
γ, is highly desirable; however, all existing protocols require polylogarithmically growing overheads with some
γ>0, and identifying the smallest achievable exponent
γ for distilling magic states of qubits has remained challenging. To address this issue, we develop magic state distillation protocols for qubits with efficient, polynomial-time decoding that achieve an
O(1) overhead, meaning the optimal exponent
γ=0; this improves over the previous best of
γ≈0.678 due to Hastings and Haah. In our construction, we employ algebraic geometry codes to explicitly present asymptotically good quantum codes for
210-dimensional qudits that support transversally implementable logical gates in the third level of the Clifford hierarchy. The use of asymptotically good codes with non-vanishing rate and relative distance leads to the constant overhead. These codes can be realised by representing each
210-dimensional qudit as a set of
10 qubits, using stabiliser operations on qubits. The
10-qubit magic states distilled with these codes can be converted to and from conventional magic states for the controlled-controlled-
Z (
CCZ) and
T gates on qubits with only a constant overhead loss, making it possible to achieve constant-overhead distillation of such standard magic states for qubits. These results resolve the fundamental open problem in quantum information theory concerning the construction of magic state distillation protocols with the optimal exponent.
In order to circumvent that no universal set of gates can be achieved on a given quantum error-correcting codes, additional gates can be performed through magic state injection. This however requires to have access to high fidelity magic state, which can be obtained by the distillation of low quality states to fewer higher quality ones. In this paper, we provide a family of distillation protocols able to produce diagonal states at every level of the Clifford hierarchy. This family is obtained recursively using code doubling techniques and leveraging qubit recycling, the fact that some idle qubits of the protocols can be measured and re-used. At a given level of the Clifford hierarchy, we show that the protocols we derive can be performed at arbitrary high distance on a fix number of logical qubits. This family recovers many known efficient protocols, and uncovers new ones, such as a
111→1 protocol for
∣T⟩ state distillation at distance
7, which are the most compact in term of volume. Finally, we discuss possible extension of this framework for distillation protocols producing more than one output state.
Recently [1] we proposed a family of magic state distillation protocols that obtains asymptotic performance that is conjectured to be optimal. This family depends upon several codes, called “inner codes” and “outer codes.” In Ref. [1], some small examples of these codes were given as well as an analysis of codes in the asymptotic limit. Here, we analyze such protocols in an intermediate size regime, using hundreds to thousands of qubits. We use BCH inner codes [2], combined with various outer codes. We extend the protocols of Ref. [1] by adding error correction in some cases. We present a variety of protocols in various input error regimes; in many cases these protocols require significantly fewer input magic states to obtain a given output error than previous protocols.
Qudits offer the potential for low-overhead magic state distillation, although previous results for asymptotically good codes have required qudit dimension
q≫100 or code length
N≫100. These parameters far exceed experimental demonstrations of qudit platforms, and thus motivate the search for better codes. Using a novel lifting procedure, we construct the first family of good triorthogonal codes on the
F22m alphabet with
m≥3 that lies above the Tsfasman-Vladut-Zink bound. These codes yield a family of asymptotically good quantum codes with transversal CCZ gates, enabling constant space overhead magic state distillation with qudit dimension as small as
q=64. Further, we identify a promising code with parameters
[[42,14,6]]64. Finally, we show that a distilled
∣CCZ⟩22m can be reduced to a
∣CCZ⟩2n state for arbitrary
n with a constant-depth Clifford circuit of at most 9 computational basis measurements, 12 single-qudit and 9 two-qudit Clifford gates.
The overhead exponent -- characterizing the scaling of the number of noisy magic states with respect to the target distillation error -- has been a central quantity to benchmark magic state distillation protocols. On the other hand, a related but less investigated quantity motivated by an information-theoretic viewpoint is the asymptotic distillation rate, the largest ratio of output to input magic states such that error vanishes asymptotically. These two quantities are tightly related in the specific case -- the overhead exponent is zero if and only if the asymptotic distillation rate is linear. However, their relationship in other regimes has been unclear. Here, we show that their quantitative relation is generally not robust, by presenting a family of magic state distillation protocols with an overhead exponent not close to zero -- in fact, larger than one -- that still achieves the asymptotic rate arbitrarily close to the linear rate. This implies that the distillation rate is not constrained by the overhead exponent within the sublinear rate regime. Notably, our protocol is based on error checking by measurements of logical Clifford operators, which underlies the recent magic state cultivation protocol, suggesting the potential of this mechanism for asymptotic magic state distillation.
It has been conjectured that, for any distillation protocol for magic states for the
T gate, the number of noisy input magic states required per output magic state at output error rate $\ensuremath{\epsilon}$ is $\mathrm{\ensuremath{\Omega}}[\mathrm{log}(1/\ensuremath{\epsilon})]$. We show that this conjecture is false. We find a family of quantum error correcting codes of parameters $⟦\ensuremath{\sum}_{i=w+1}^{m}(\genfrac{}{}{0}{}{m}{i}),\ensuremath{\sum}_{i=0}^{w}(\genfrac{}{}{0}{}{m}{i}),\ensuremath{\sum}_{i=w+1}^{r+1}(\genfrac{}{}{0}{}{r+1}{i})⟧$ for any integers
m>2r, $r>w\ensuremath{\ge}0$, by puncturing quantum Reed-Muller codes. When $m>\ensuremath{\nu}r$, our code admits a transversal logical gate at the $\ensuremath{\nu}$th level of Clifford hierarchy. In a distillation protocol for magic states at the level $\ensuremath{\nu}=3$ (
T gate), the ratio of input to output magic states is $O\mathbf{(}{\mathrm{log}}^{\ensuremath{\gamma}}(1/\ensuremath{\epsilon})\mathbf{)}$, where $\ensuremath{\gamma}=\mathrm{log}(n/k)/\mathrm{log}(d)<0.678$ for some
m,
r,
w. The smallest code in our family for which $\ensuremath{\gamma}<1$ is on $\ensuremath{\approx}{2}^{58}$ qubits.