Magic State Distillation: Not as Costly as You Think

Daniel Litinski

Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Arnimallee 14, 14195 Berlin, Germany

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

► BibTeX data

► References

[1] J. Preskill, Reliable quantum computers, Proc. Roy. Soc. Lond. A 454, 385 (1998).

[2] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015).

[3] E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault-tolerant universal quantum computation, Nature 549, 172 (2017).

[4] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2 (2003).

[5] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012).

[6] C. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14, 123011 (2012).

[7] D. Litinski and F. v. Oppen, Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes, Quantum 2, 62 (2018).

[8] A. G. Fowler and C. Gidney, Low overhead quantum computation using lattice surgery, arXiv:1808.06709 (2018).

[9] S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas, Phys. Rev. A 71, 022316 (2005).

[10] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Phys. Rev. X 8, 041015 (2018).

[11] S. Bravyi and J. Haah, Magic-state distillation with low overhead, Phys. Rev. A 86, 052329 (2012).

[12] A. G. Fowler, S. J. Devitt, and C. Jones, Surface code implementation of block code state distillation, Scientific Rep. 3, 1939 (2013).

[13] A. M. Meier, B. Eastin, and E. Knill, Magic-state distillation with the four-qubit code, Quant. Inf. Comp. 13, 195 (2013).

[14] C. Jones, Multilevel distillation of magic states for quantum computing, Phys. Rev. A 87, 042305 (2013a).

[15] G. Duclos-Cianci and K. M. Svore, Distillation of nonstabilizer states for universal quantum computation, Phys. Rev. A 88, 042325 (2013).

[16] G. Duclos-Cianci and D. Poulin, Reducing the quantum-computing overhead with complex gate distillation, Phys. Rev. A 91, 042315 (2015).

[17] E. T. Campbell and M. Howard, Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost, Phys. Rev. A 95, 022316 (2017a).

[18] J. O'Gorman and E. T. Campbell, Quantum computation with realistic magic-state factories, Phys. Rev. A 95, 032338 (2017).

[19] J. Haah and M. B. Hastings, Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates, Quantum 2, 71 (2018).

[20] E. T. Campbell and M. Howard, Magic state parity-checker with pre-distilled components, Quantum 2, 56 (2018).

[21] C. Gidney and A. G. Fowler, Efficient magic state factories with a catalyzed $|CCZ\rangle$ to $2|T\rangle$ transformation, Quantum 3, 135 (2019).

[22] C. Jones, P. Brooks, and J. Harrington, Gauge color codes in two dimensions, Phys. Rev. A 93, 052332 (2016).

[23] S. Bravyi and A. Cross, Doubled color codes, arXiv:1509.03239 (2015).

[24] T. Jochym-O'Connor and S. D. Bartlett, Stacked codes: Universal fault-tolerant quantum computation in a two-dimensional layout, Phys. Rev. A 93, 022323 (2016).

[25] H. Bombin, 2D quantum computation with 3D topological codes, arXiv:1810.09571 (2018).

[26] C. Chamberland and A. W. Cross, Fault-tolerant magic state preparation with flag qubits, Quantum 3, 143 (2019).

[27] B. J. Brown, A fault-tolerant non-Clifford gate for the surface code in two dimensions, arXiv:1903.11634 (2019).

[28] D. Litinski, A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery, Quantum 3, 128 (2019).

[29] M. Amy and M. Mosca, T-count optimization and Reed-Muller codes, IEEE Transactions on Information Theory , 1 (2019).

[30] 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).

[31] A. J. Landahl and C. Ryan-Anderson, Quantum computing by color-code lattice surgery, arXiv:1407.5103 (2014).

[32] Y. Li, A magic state’s fidelity can be superior to the operations that created it, New J. Phys. 17, 023037 (2015).

[33] J. Lodyga, P. Mazurek, A. Grudka, and M. Horodecki, Simple scheme for encoding and decoding a qubit in unknown state for various topological codes, Scientific Rep. 5, 8975 (2015).

[34] L. Lao et al., Preparing high-fidelity magic states with low costs, in preparation.

[35] Cramming more power into a quantum device, https:/​/​​blogs/​research/​2019/​03/​ power-quantum-device/​, accessed: 2019-05-09.

[36] 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).

[37] The Python script and Mathematica notebook can be found on GitHub, see https:/​/​​litinski/​magicstates.

[38] E. T. Campbell and M. Howard, Unifying gate synthesis and magic state distillation, Phys. Rev. Lett. 118, 060501 (2017b).

[39] P. Selinger, Quantum circuits of $T$-depth one, Phys. Rev. A 87, 042302 (2013).

[40] C. Jones, Low-overhead constructions for the fault-tolerant Toffoli gate, Phys. Rev. A 87, 022328 (2013b).

[41] C. Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018).

[42] B. J. Brown and S. Roberts, Universal fault-tolerant measurement-based quantum computation, arXiv:1811.11780 (2018).

Cited by

[1] Michael Hanks, Marta P. Estarellas, William J. Munro, and Kae Nemoto, "Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus", Physical Review X 10 4, 041030 (2020).

[2] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 5, 433 (2021).

[3] M. Lostaglio and A. Ciani, "Error Mitigation and Quantum-Assisted Simulation in the Error Corrected Regime", Physical Review Letters 127 20, 200506 (2021).

[4] T. R. Scruby, D. E. Browne, P. Webster, and M. Vasmer, "Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code", Quantum 6, 721 (2022).

[5] Sergey Bravyi, Oliver Dial, Jay M. Gambetta, Darío Gil, and Zaira Nazario, "The future of quantum computing with superconducting qubits", Journal of Applied Physics 132 16, 160902 (2022).

[6] Lingling Lao and Ben Criger, Proceedings of the 19th ACM International Conference on Computing Frontiers 113 (2022) ISBN:9781450393386.

[7] Casey Duckering, Jonathan M. Baker, David I. Schuster, and Frederic T. Chong, 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) 173 (2020) ISBN:978-1-7281-7383-2.

[8] Jeongwan Haah and Matthew B. Hastings, "Measurement sequences for magic state distillation", Quantum 5, 383 (2021).

[9] Mikkel V. Larsen, Christopher Chamberland, Kyungjoo Noh, Jonas S. Neergaard-Nielsen, and Ulrik L. Andersen, "Fault-Tolerant Continuous-Variable Measurement-based Quantum Computation Architecture", PRX Quantum 2 3, 030325 (2021).

[10] Noah Shutty and Christopher Chamberland, "Decoding Merged Color-Surface Codes and Finding Fault-Tolerant Clifford Circuits Using Solvers for Satisfiability Modulo Theories", Physical Review Applied 18 1, 014072 (2022).

[11] Pedro Parrado-Rodríguez, Manuel Rispler, and Markus Müller, "Rescaling decoder for two-dimensional topological quantum color codes on 4.8.8 lattices", Physical Review A 106 3, 032431 (2022).

[12] Principles of Superconducting Quantum Computers 327 (2022) ISBN:9781119750727.

[13] Simon Martiel and Timothée Goubault de Brugière, "Architecture aware compilation of quantum circuits via lazy synthesis", Quantum 6, 729 (2022).

[14] Paul Webster and Stephen D. Bartlett, "Fault-tolerant quantum gates with defects in topological stabilizer codes", Physical Review A 102 2, 022403 (2020).

[15] Thomas Häner, Damian S. Steiger, Torsten Hoefler, and Matthias Troyer, Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis 1 (2021) ISBN:9781450384421.

[16] Gökhan Torun, Hüseyin Talha Şenyaşa, and Ali Yildiz, "Resource theory of superposition: State transformations", Physical Review A 103 3, 032416 (2021).

[17] Isaac H. Kim, Ye-Hua Liu, Sam Pallister, William Pol, Sam Roberts, and Eunseok Lee, "Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules", Physical Review Research 4 2, 023019 (2022).

[18] Sepehr Nezami and Jeongwan Haah, "Classification of small triorthogonal codes", Physical Review A 106 1, 012437 (2022).

[19] Lan Luo, Zhi Ma, Dongdai Lin, and Hong Wang, "Fault-tolerance thresholds for code conversion schemes with quantum Reed–Muller codes", Quantum Science and Technology 5 4, 045022 (2020).

[20] Diego Ristè, Luke C. G. Govia, Brian Donovan, Spencer D. Fallek, William D. Kalfus, Markus Brink, Nicholas T. Bronn, and Thomas A. Ohki, "Real-time processing of stabilizer measurements in a bit-flip code", npj Quantum Information 6 1, 71 (2020).

[21] Mark Webber, Vincent Elfving, Sebastian Weidt, and Winfried K. Hensinger, "The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime", AVS Quantum Science 4 1, 013801 (2022).

[22] Christopher Chamberland and Earl T. Campbell, "Universal Quantum Computing with Twist-Free and Temporally Encoded Lattice Surgery", PRX Quantum 3 1, 010331 (2022).

[23] Nick S. Blunt, Joan Camps, Ophelia Crawford, Róbert Izsák, Sebastian Leontica, Arjun Mirani, Alexandra E. Moylett, Sam A. Scivier, Christoph Sünderhauf, Patrick Schopf, Jacob M. Taylor, and Nicole Holzmann, "Perspective on the Current State-of-the-Art of Quantum Computing for Drug Discovery Applications", Journal of Chemical Theory and Computation 18 12, 7001 (2022).

[24] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, "Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction", PRX Quantum 2 3, 030305 (2021).

[25] Nikolaos Koukoulekidis and David Jennings, "Constraints on magic state protocols from the statistical mechanics of Wigner negativity", npj Quantum Information 8 1, 42 (2022).

[26] Christopher Chamberland and Kyungjoo Noh, "Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits", npj Quantum Information 6 1, 91 (2020).

[27] Hao Dai, Shuangshuang Fu, and Shunlong Luo, "Detecting Magic States via Characteristic Functions", International Journal of Theoretical Physics 61 2, 35 (2022).

[28] S Flannigan, N Pearson, G H Low, A Buyskikh, I Bloch, P Zoller, M Troyer, and A J Daley, "Propagation of errors and quantitative quantum simulation with quantum advantage", Quantum Science and Technology 7 4, 045025 (2022).

[29] Campbell K. McLauchlan and Benjamin Béri, "Fermion-Parity-Based Computation and Its Majorana-Zero-Mode Implementation", Physical Review Letters 128 18, 180504 (2022).

[30] Jérémie Guillaud and Mazyar Mirrahimi, "Error rates and resource overheads of repetition cat qubits", Physical Review A 103 4, 042413 (2021).

[31] Manoj G. Gowda and Pradeep Kiran Sarvepalli, "Color codes with twists: Construction and universal-gate-set implementation", Physical Review A 104 1, 012603 (2021).

[32] Michael E. Beverland, Aleksander Kubica, and Krysta M. Svore, "Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes", PRX Quantum 2 2, 020341 (2021).

[33] S. Pathak, A. E. Russo, S. K. Seritan, and A. D. Baczewski, "Quantifying T -gate-count improvements for ground-state-energy estimation with near-optimal state preparation", Physical Review A 107 4, L040601 (2023).

[34] Y. Herasymenko and T.E. O'Brien, "A diagrammatic approach to variational quantum ansatz construction", Quantum 5, 596 (2021).

[35] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, "Quantum computational chemistry", Reviews of Modern Physics 92 1, 015003 (2020).

[36] Michael Vasmer and Aleksander Kubica, "Morphing Quantum Codes", PRX Quantum 3 3, 030319 (2022).

[37] Julio Carlos Magdalena de la Fuente, Nicolas Tarantino, and Jens Eisert, "Non-Pauli topological stabilizer codes from twisted quantum doubles", Quantum 5, 398 (2021).

[38] Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G.S.L. Brandão, "Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes", PRX Quantum 3 1, 010329 (2022).

[39] Christophe Piveteau, David Sutter, Sergey Bravyi, Jay M. Gambetta, and Kristan Temme, "Error Mitigation for Universal Gates on Encoded Qubits", Physical Review Letters 127 20, 200505 (2021).

[40] Shraddha Singh, Andrew S. Darmawan, Benjamin J. Brown, and Shruti Puri, "High-fidelity magic-state preparation with a biased-noise architecture", Physical Review A 105 5, 052410 (2022).

[41] Gaurav Saxena and Gilad Gour, "Quantifying multiqubit magic channels with completely stabilizer-preserving operations", Physical Review A 106 4, 042422 (2022).

[42] Ilkwon Byun, Junpyo Kim, Dongmoon Min, Ikki Nagaoka, Kosuke Fukumitsu, Iori Ishikawa, Teruo Tanimoto, Masamitsu Tanaka, Koji Inoue, and Jangwoo Kim, Proceedings of the 49th Annual International Symposium on Computer Architecture 366 (2022) ISBN:9781450386104.

[43] Paul Webster, Michael Vasmer, Thomas R. Scruby, and Stephen D. Bartlett, "Universal fault-tolerant quantum computing with stabilizer codes", Physical Review Research 4 1, 013092 (2022).

[44] Seok-Hyung Lee and Hyunseok Jeong, "Universal hardware-efficient topological measurement-based quantum computation via color-code-based cluster states", Physical Review Research 4 1, 013010 (2022).

[45] Ryuji Takagi and Hiroyasu Tajima, "Universal limitations on implementing resourceful unitary evolutions", Physical Review A 101 2, 022315 (2020).

[46] Kyungjoo Noh, Liang Jiang, and Bill Fefferman, "Efficient classical simulation of noisy random quantum circuits in one dimension", Quantum 4, 318 (2020).

[47] Héctor Bombín, Chris Dawson, Ryan V. Mishmash, Naomi Nickerson, Fernando Pastawski, and Sam Roberts, "Logical Blocks for Fault-Tolerant Topological Quantum Computation", PRX Quantum 4 2, 020303 (2023).

[48] F. Orts, E. Filatovas, G. Ortega, J. F. SanJuan-Estrada, and E. M. Garzón, "Improving the number of T gates and their spread in integer multipliers on quantum computing", Physical Review A 107 4, 042621 (2023).

[49] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", arXiv:1905.09749, (2019).

[50] Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon Benjamin, and Xiao Yuan, "Quantum computational chemistry", arXiv:1808.10402, (2018).

[51] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, "Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization", Quantum 3, 208 (2019).

[52] Benjamin J. Brown, "A fault-tolerant non-Clifford gate for the surface code in two dimensions", Science Advances 6 21, eaay4929 (2020).

[53] Casey Duckering, Jonathan M. Baker, David I. Schuster, and Frederic T. Chong, "Virtualized Logical Qubits: A 2.5D Architecture for Error-Corrected Quantum Computing", arXiv:2009.01982, (2020).

[54] Craig Gidney, "Cleaner magic states with hook injection", arXiv:2302.12292, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-05-29 19:28:50) and SAO/NASA ADS (last updated successfully 2023-05-29 19:28:51). The list may be incomplete as not all publishers provide suitable and complete citation data.