Magic State Distillation: Not as Costly as You Think
Open accessAbstract
Despite significant overhead reductions since its first proposal, magic state distillation is often considered to be a very costly procedure that dominates the resource cost of fault-tolerant quantum computers. The goal of this work is to demonstrate that this is not true. By writing distillation circuits in a form that separates qubits that are capable of error detection from those that are not, most logical qubits used for distillation can be encoded at a very low code distance. This significantly reduces the space-time cost of distillation, as well as the number of qubits. In extreme cases, it can cost less to distill a magic state than to perform a logical Clifford gate on full-distance logical qubits.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the week before we first released this paper, Daniel Litinsky made [56] available. He independently arrived at the idea of using distillation to herald errors within the factory, and provided rough numerics indicating this may reduce the volume of distillation by as much as a factor of 10.
“In fact, in the week before we first released this paper, Daniel Litinsky made [56] available. He independently arrived at the idea of using distillation to herald errors within the factory, and provided rough numerics indicating this may reduce the volume of distillation by as much as a factor of 10.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [56]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · cited 3× · see citing works
“r correction is expected to be an essential part of a large-scale quantum computer [1{3]. The most promising quantum error-correcting codes are two-dimensional topological codes such as surface codes [4,5]. With these codes, the preparation of logical Pauli eigenstates and the measurement of logical Pauli product oper…”
BackgroundInfluentialUniversal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525 · cited 4× · see citing works
“The 15-to-1 protocol [6] is sometimes characterized as having an output error probability of 35p3.”
BackgroundInfluentialQuantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354 · see citing works
Surface code quantum computing by lattice surgery
Horsman, D., Fowler, A. G., Devitt, S., & Meter, R. V. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/12/123011 · Cited by 598 · cited 4× · see citing works
“The simplest protocol [27] starts with a physical state |ψ〉, i.”
BackgroundInfluentialEncoding Electronic Spectra in Quantum Circuits with Linear T Complexity
Babbush, R., Gidney, C., Berry, D. W., Wiebe, N., McClean, J., Paler, A., Fowler, A., & Neven, H. (2018) · Physical Review X · doi:10.1103/physrevx.8.041015 · Cited by 383 · see citing works
Halving the cost of quantum addition
Gidney, C. (2018) · Quantum · doi:10.22331/q-2018-06-18-74 · Cited by 279 · see citing works
Haah, J., & Hastings, M. B. (2018) · Quantum · doi:10.22331/q-2018-06-07-71 · Cited by 79 · see citing works
A fault-tolerant non-Clifford gate for the surface code in two dimensions
Brown, B. J. (2020) · Science Advances · doi:10.1126/sciadv.aay4929 · Cited by 77 · see citing works
Low overhead quantum computation using lattice surgery
Fowler, A. G., & Gidney, C. (2018) · arXiv · doi:10.48550/arxiv.1808.06709 · Cited by 69 · see citing works
Flagged first, then by citations
Research works printed but not linked: 30
- J. Preskill, Reliable quantum computers, Proc. Roy. Soc. Lond. A 454, 385 (1998). · DOI · Paper page
- E. T. Campbell, B. M. Terhal, and C. Vuil- lot, Roads towards fault-tolerant universal quantum computation, Nature 549, 172 (2017). · DOI · Paper page
- A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2 (2003). · DOI · Paper page
- D. Litinski and F. v. Oppen, Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes, Quantum 2, 62 (2018). · DOI
- S. Bravyi and J. Haah, Magic-state distillation with low overhead, Phys. Rev. A 86, 052329 (2012). · DOI
- A. G. Fowler, S. J. Devitt, and C. Jones, Surface code implementation of block code state distillation, Scientific Rep. 3, 1939 (2013). · DOI · Paper page
- A. M. Meier, B. Eastin, and E. Knill, Magic- state distillation with the four-qubit code, Quant. Inf. Comp. 13, 195 (2013).
- C. Jones, Multilevel distillation of magic states for quantum computing, Phys. Rev. A 87, 042305 (2013). · DOI
- G. Duclos-Cianci and K. M. Svore, Distillation of nonstabilizer states for universal quantum compu- tation, Phys. Rev. A 88, 042325 (2013). · DOI
- G. Duclos-Cianci and D. Poulin, Reducing the quantum-computing overhead with complex gate distillation, Phys. Rev. A 91, 042315 (2015). · DOI
- E. T. Campbell and M. Howard, Unified framework for magic state distillation and multiqubit gate syn- thesis with reduced resource cost, Phys. Rev. A 95, 022316 (2017). · DOI
- J. O'Gorman and E. T. Campbell, Quantum com- putation with realistic magic-state factories, Phys. Rev. A 95, 032338 (2017). · DOI · Paper page
- E. T. Campbell and M. Howard, Magic state parity-checker with pre-distilled components, Quantum 2, 56 (2018). · DOI
- C. Gidney and A. G. Fowler, Efficient magic state factories with a catalyzed |CCZ to 2|T transfor- mation, Quantum 3, 135 (2019). · DOI · Paper page
- C. Jones, P. Brooks, and J. Harrington, Gauge color codes in two dimensions, Phys. Rev. A 93, 052332 (2016). · DOI
- S. Bravyi and A. Cross, Doubled color codes, arXiv:1509.03239 (2015). · arXiv
- T. Jochym-O'Connor and S. D. Bartlett, Stacked codes: Universal fault-tolerant quantum computa- tion in a two-dimensional layout, Phys. Rev. A 93, 022323 (2016). · DOI
- H. Bombin, 2D quantum computation with 3D topological codes, arXiv:1810.09571 (2018). · arXiv
- C. Chamberland and A. W. Cross, Fault-tolerant magic state preparation with flag qubits, Quantum 3, 143 (2019). · DOI
- D. Litinski, A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery, Quan- tum 3, 128 (2019). · DOI · Paper page
- M. Amy and M. Mosca, T-count optimization and Reed-Muller codes, IEEE Transactions on Informa- tion Theory , 1 (2019). · DOI · Paper page
- J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, Magic state distillation with low space overhead and optimal asymptotic input count, Quantum 1, 31 (2017). · DOI
- A. J. Landahl and C. Ryan-Anderson, Quan- tum computing by color-code lattice surgery, arXiv:1407.5103 (2014). · arXiv
- Y. Li, A magic states fidelity can be superior to the operations that created it, New J. Phys. 17, 023037 (2015). · DOI
- J. Lodyga, P. Mazurek, A. Grudka, and M. Horodecki, Simple scheme for encoding and de- coding a qubit in unknown state for various topo- logical codes, Scientific Rep. 5, 8975 (2015). · DOI
- K. Wright, K. Beck, S. Debnath, J. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. Pisenti, M. Chmielewski, C. Collins, et al., Benchmarking an 11-qubit quantum computer, arXiv:1903.08181 (2019). · arXiv
- E. T. Campbell and M. Howard, Unifying gate syn- thesis and magic state distillation, Phys. Rev. Lett. 118, 060501 (2017). · DOI
- P. Selinger, Quantum circuits of T -depth one, Phys. Rev. A 87, 042302 (2013). · DOI
- C. Jones, Low-overhead constructions for the fault- tolerant Toffoli gate, Phys. Rev. A 87, 022328 (2013). · DOI
- B. J. Brown and S. Roberts, Universal fault- tolerant measurement-based quantum computation, arXiv:1811.11780 (2018). · arXiv
Cited by
Sorted by citations
Quantum computational chemistry
McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C., & Yuan, X. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.015003 · Cited by 1,621 · see citing works
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830 · see citing works
Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction
Lee, J., Berry, D. W., Gidney, C., Huggins, W. J., McClean, J. R., Wiebe, N., & Babbush, R. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030305 · Cited by 304 · see citing works
Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes
Chamberland, C., Noh, K., Arrangoiz-Arriola, P., Campbell, E. T., Hann, C. T., Iverson, J., Putterman, H., Bohdanowicz, T. C., Flammia, S. T., Keller, A., et al. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010329 · Cited by 281 · see citing works
Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
Berry, D. W., Gidney, C., Motta, M., McClean, J. R., & Babbush, R. (2019) · Quantum · doi:10.22331/q-2019-12-02-208 · Cited by 222 · see citing works
Perspective on the Current State-of-the-Art of Quantum Computing for Drug Discovery Applications
Blunt, N. S., Camps, J., Crawford, O., Izsák, R., Leontica, S., Mirani, A., Moylett, A. E., Scivier, S. A., Sünderhauf, C., Schopf, P., et al. (2022) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.2c00574 · Cited by 192 · see citing works
Encoding a magic state with beyond break-even fidelity
Gupta, R. S., Sundaresan, N., Alexander, T., Wood, C. J., Merkel, S. T., Healy, M. B., Hillenbrand, M., Jochym-O’Connor, T., Wootton, J. R., Yoder, T. J., et al. (2024) · Nature · doi:10.1038/s41586-023-06846-3 · Cited by 115 · see citing works
Early Fault-Tolerant Quantum Computing
Katabarwa, A., Gratsea, K., Caesura, A., & Johnson, P. D. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020101 · Cited by 103 · see citing works
“The most efficient distillation widgets known in the surface code are given in [88].”
BackgroundError Mitigation for Universal Gates on Encoded Qubits
Piveteau, C., Sutter, D., Bravyi, S., Gambetta, J. M., & Temme, K. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.200505 · Cited by 81 · see citing works
Beverland, M. E., Kubica, A., & Svore, K. M. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.020341 · Cited by 82 · see citing works
Error rates and resource overheads of repetition cat qubits
Guillaud, J., & Mirrahimi, M. (2021) · Physical Review A · doi:10.1103/physreva.103.042413 · Cited by 55 · see citing works
Low-overhead quantum computing with the color code
Thomsen, F., Kesselring, M. S., Bartlett, S. D., & Brown, B. J. (2024) · Physical Review Research · doi:10.1103/physrevresearch.6.043125 · Cited by 15 · see citing works
Magic state cultivation: growing T states as cheap as CNOT gates
Gidney, C., Shutty, N., & Jones, C. (2024) · arXiv · doi:10.48550/arxiv.2409.17595 · Cited by 9
“The main inefficiency of magic state distillation is the fact that it’s performed with logical operations [Fow+12; GF19a; Lit19].”
BackgroundMethodInfluentialThreshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
Omanakuttan, S., He, Z., Zhang, Z., Hao, T., Babakhani, A., Boulebnane, S., Chakrabarti, S., Herman, D., Sullivan, J., Perlin, M. A., et al. (2025) · arXiv · doi:10.48550/arxiv.2504.01897 · Cited by 3 · see citing works
“To evaluate the runtime of these components, we consider their fault-tolerant implementation in a surface code architecture with a Clifford+ T +CCZ gate set that is realized with lattice surgery [59] and resource-state factories [39].”
Influential
- Authors
- Litinski, D.
- Affiliations
- Freie Universität Berlin (DE)
- Corresponding author
- Litinski, Daniel
- Venue
- Quantum
- Published
- 2019-12-02
- Volume
- 3
- Pages
- 205
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W2945632438
- Cited by
- 220
- References
- 9
- Citations by year
- 2026: 49 · 2025: 59 · 2024: 33 · 2023: 26 · 2022: 25 · 2021: 17 · 2020: 10 · 2019: 1
- FWCI
- 6.04
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Funders
- Deutsche Forschungsgemeinschaft (TR 183, CRC/TR183)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- magic state distillation, fault-tolerant quantum computing, resource costs, logical qubits, code distance, error detection, overhead reduction
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
