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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[21] Y. Herasymenko and T. E. O'Brien, "A diagrammatic approach to variational quantum ansatz construction", arXiv:1907.08157.

[22] 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", arXiv:2012.08536.

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-19 20:36:54) and SAO/NASA ADS (last updated successfully 2021-10-19 20:36:55). The list may be incomplete as not all publishers provide suitable and complete citation data.