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.
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.
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.
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.
Magic state distillation plays an important role in universal fault-tolerant quantum computing, and its overhead is one of the major obstacles to realizing fault-tolerant quantum computers. Hence, many studies have been conducted to reduce this overhead. Among these, Litinski has provided a concrete assessment of resource-efficient distillation protocol implementations on the rotated surface code. On the other hand, recently, Itogawa et al. have proposed zero-level distillation, a distillation protocol offering very small spatial and temporal overhead to generate relatively low-fidelity magic states. While zero-level distillation offers preferable spatial and temporal overhead, it cannot directly generate high-fidelity magic states since it only reduces the logical error rate of the magic state quadratically. In this study, we evaluate the spatial and temporal overhead of two-level distillation implementations generating relatively high-fidelity magic states, including ones incorporating zero-level dis-tillation. To this end, we introduce (0+ 1)-level distillation, a two-level distillation protocol which combines zero-level distillation and the 15-to-1 distillation protocol. We refine the second-level 15-to-l implementation in it to capitalize on the small footprint of zero-level distillation. Under conditions of a physical error probability of Pphys = 10-4(10-3) and targeting an error rate for the magic state within [5 × 10-17,10-11] ([5 × 10-11,10-8]), (0+1)-level distillation reduces the spatiotemporal overhead by more than 63% (61%) compared to the (15-to-l)x(15-to-l) protocol and more than 43% (44%) compared to the (15-to-l)x(20-to-4) protocol, offering a substantial efficiency gain over the traditional protocols.
Magic-state distillation is a resource intensive subroutine for quantum computation. The ratio of noisy input states to output states with an error rate at most ε scales as O(log^{γ}(1/ε)) [S. Bravyi and J. Haah, Magic-state distillation with low overhead, Phys. Rev. A 86, 052329 (2012)10.1103/PhysRevA.86.052329]. In a breakthrough paper, Hastings and Haah [Distillation with Sublogarithmic Overhead, Phys. Rev. Lett. 120, 050504 (2018)10.1103/PhysRevLett.120.050504] showed that it is possible to construct distillation routines with a sublogarithmic overhead, achieving γ≈0.6779 and falsifying a conjecture that γ is lower bounded by 1. They then ask whether γ can be made arbitrarily close to 0. We answer this question in the affirmative for magic-state distillation routines using qudits of prime dimension (d dimensional quantum systems for prime d).
Magic plays a dual role in quantum computation: it promotes stabilizer dynamics from efficient classical simulability to computational universality, but also challenges fault-tolerant architectures, since non-stabilizer operations are harder to protect against noise. Magic state distillation addresses this issue, yet existing protocols remain largely tailored to specific assumptions about the input or noise model and, more fundamentally, no general information-theoretic theory of optimal magic-state conversion currently exists. Here we develop such a characterization for pure qubit states through universal magic state concentration: a fixed stabilizer protocol that converts a few copies of an unknown pure non-stabilizer qubit state into an exact target magic state. Motivated by the impossibility of exact T-state concentration, we build six- and eight-copy protocols producing an exact CCZ state, with six copies being minimal. Their success probabilities are governed by the linearized order-three stabilizer Rényi entropy M3lin. We show that this connection is structural: for up to nine input copies, M3lin fully determines the success probability of every universal Clifford-invariant stabilizer protocol. Remarkably, this characterization persists asymptotically: our constructions achieve optimal rates among universal single-output protocols and remain optimal up to logarithmic factors among arbitrary stabilizer protocols. As a corollary, we show that any unknown pure non-stabilizer state suffices for universal quantum computation via probabilistic CCZ-state injection. Together, these results identify the stabilizer Rényi entropy as a fundamental operational quantity in magic state distillation.
Developing space- and time-efficient logical magic state preparation protocols will likely be an essential step towards building a large-scale fault-tolerant quantum computer. Motivated by this need, we introduce a scalable method for simulating logical magic state preparation protocols under the standard circuit-level noise model. When applied to protocols based on code switching, magic state cultivation, and magic state distillation, our method yields a complexity polynomial in (i) the number of qubits and (ii) the non-stabilizerness, e.g., stabilizer rank or Pauli rank, of the target encoded magic state. The efficiency of our simulation method is rooted in a curious fact: every circuit-level Pauli error in these protocols propagates to a Clifford error at the end. This property is satisfied by a large family of protocols, including those that repeatedly measure a transversal Clifford that squares to a Pauli. We provide a proof-of-principle numerical simulation that prepares a magic state using such logical Clifford measurements. Our work enables practical simulation of logical magic state preparation protocols without resorting to approximations or resource-intensive state-vector simulations.