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", arXiv:1905.09749, 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] Lingling Lao and Ben Criger, Proceedings of the 19th ACM International Conference on Computing Frontiers 113 (2022) ISBN:9781450393386.

[6] 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.

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

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

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

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

[11] 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[37] 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", arXiv:1902.02134.

[38] Sepehr Nezami and Jeongwan Haah, "Classification of Small Triorthogonal Codes", arXiv:2107.09684.

[39] 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.

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