Efficient magic state factories with a catalyzed $|CCZ\rangle$ to $2|T\rangle$ transformation

Craig Gidney and Austin G. Fowler

Google Inc., Santa Barbara, California 93117, USA

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


We present magic state factory constructions for producing $|CCZ\rangle$ states and $|T\rangle$ states. For the $|CCZ\rangle$ factory we apply the surface code lattice surgery construction techniques described in [15] to the fault-tolerant Toffoli [21,12]. The resulting factory has a footprint of $12d \times 6d$ (where $d$ is the code distance) and produces one $|CCZ\rangle$ every $5.5d$ surface code cycles. Our $|T\rangle$ state factory uses the $|CCZ\rangle$ factory's output and a catalyst $|T\rangle$ state to exactly transform one $|CCZ\rangle$ state into two $|T\rangle$ states. It has a footprint $25\%$ smaller than the factory in [15] but outputs $|T\rangle$ states twice as quickly. We show how to generalize the catalyzed transformation to arbitrary phase angles, and note that the case $\theta=22.5^\circ$ produces a particularly efficient circuit for producing $|\sqrt{T}\rangle$ states. Compared to using the $12d \times 8d \times 6.5d$ $|T\rangle$ factory of [15], our $|CCZ\rangle$ factory can quintuple the speed of algorithms that are dominated by the cost of applying Toffoli gates, including Shor's algorithm [31] and the chemistry algorithm of Babbush et al. [1]. Assuming a physical gate error rate of $10^{-3}$, our CCZ factory can produce $\sim 10^{10}$ states on average before an error occurs. This is sufficient for classically intractable instantiations of the chemistry algorithm, but for more demanding algorithms such as Shor's algorithm the mean number of states until failure can be increased to $\sim 10^{12}$ by increasing the factory footprint $\sim 20\%$.

► BibTeX data

► References

[1] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear t complexity. arXiv preprint arXiv:1805.03662, 2018. 10.1103/​PhysRevX.8.041015.

[2] Alex Bocharov, Martin Roetteler, and Krysta M Svore. Efficient synthesis of universal repeat-until-success quantum circuits. Physical review letters, 114 (8): 080502, 2015. 10.1103/​PhysRevLett.114.080502.

[3] S. B. Bravyi and A. Yu. Kitaev. Quantum codes on a lattice with boundary. quant-ph/​9811052, 1998. URL https:/​/​arxiv.org/​abs/​quant-ph/​9811052.

[4] Sergey Bravyi and Jeongwan Haah. Magic-state distillation with low overhead. Physical Review A, 86 (5): 052329, 2012. 10.1103/​PhysRevA.86.052329.

[5] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103/​PhysRevA.71.022316.

[6] Benjamin J Brown, Katharina Laubscher, Markus S Kesselring, and James R Wootton. Poking holes and cutting corners to achieve clifford gates with the surface code. Physical Review X, 7 (2): 021029, 2017. 10.1103/​PhysRevX.7.021029.

[7] Earl T Campbell. Catalysis and activation of magic states in fault-tolerant architectures. Physical Review A, 83 (3): 032317, 2011. 10.1103/​PhysRevA.83.032317.

[8] Earl T Campbell and Mark Howard. Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost. Physical Review A, 95 (2): 022316, 2017. 10.1103/​PhysRevA.95.022316.

[9] Earl T Campbell and Mark Howard. Magic state parity-checker with pre-distilled components. Quantum, 2: 56, 2018. 10.22331/​q-2018-03-14-56.

[10] Niel de Beaudrap and Dominic Horsman. The zx calculus is a language for surface code lattice surgery. arXiv preprint arXiv:1704.08670, 2017. URL https:/​/​arxiv.org/​abs/​1704.08670.

[11] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill. Topological quantum memory. J. Math. Phys., 43: 4452–4505, 2002. 10.1063/​1.1499754. quant-ph/​0110143.

[12] Bryan Eastin. Distilling one-qubit magic states into toffoli states. Physical Review A, 87 (3): 032321, 2013. 10.1103/​PhysRevA.87.032321.

[13] 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. 10.1103/​physreva.86.032324. arXiv:1208.0928.

[14] Austin G Fowler and Simon J Devitt. A bridge to lower overhead quantum computation. arXiv preprint arXiv:1209.0510, 2012. URL https:/​/​arxiv.org/​abs/​1209.0510.

[15] Austin G Fowler and Craig Gidney. Low overhead quantum computation using lattice surgery. arXiv preprint arXiv:1808.06709, 2018. URL https:/​/​arxiv.org/​abs/​1808.06709.

[16] Austin G Fowler, Simon J Devitt, and Cody Jones. Surface code implementation of block code state distillation. Scientific reports, 3: 1939, 2013. 10.1038/​srep01939.

[17] Craig Gidney. Halving the cost of quantum addition. Quantum, 2: 74, 2018. 10.22331/​q-2018-06-18-74.

[18] Daniel Gottesman and Isaac L Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390, 1999. 10.1038/​46503.

[19] Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, 2012. 10.1088/​1367-2630/​14/​12/​123011.

[20] Daniel Jonathan and Martin B Plenio. Entanglement-assisted local manipulation of pure quantum states. Physical Review Letters, 83 (17): 3566, 1999. 10.1103/​PhysRevLett.83.3566.

[21] Cody Jones. Low-overhead constructions for the fault-tolerant toffoli gate. Physical Review A, 87 (2): 022328, 2013. 10.1103/​PhysRevA.87.022328.

[22] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and quantum computation. American Mathematical Soc., 2002.

[23] Andrew J Landahl and Chris Cesare. Complex instruction set computing architecture for performing accurate quantum $ z $ rotations with less magic. arXiv preprint arXiv:1302.3240, 2013. URL https:/​/​arxiv.org/​abs/​1302.3240.

[24] Ying Li. A magic state’s fidelity can be superior to the operations that created it. New Journal of Physics, 17 (2): 023037, 2015. 10.1088/​1367-2630/​17/​2/​023037.

[25] Daniel Litinski. A game of surface codes: Large-scale quantum computing with lattice surgery. Quantum, 3: 128, 2019. 10.22331/​q-2019-03-05-128.

[26] Prashant Mishra and Austin Fowler. Resource comparison of two surface code implementations of small angle z rotations. arXiv preprint arXiv:1406.4948, 2014. URL https:/​/​arxiv.org/​abs/​1406.4948.

[27] Yunseong Nam, Yuan Su, and Dmitri Maslov. Approximate quantum fourier transform with o(n log(n)) t gates. arXiv preprint arXiv:1803.04933, 2018. URL https:/​/​arxiv.org/​abs/​1803.04933.

[28] Maura B Paterson and Douglas R Stinson. Yet another hat game. the electronic journal of combinatorics, 17 (1): R86, 2010. URL https:/​/​www.combinatorics.org/​ojs/​index.php/​eljc/​article/​view/​v17i1r86.

[29] R. Raussendorf and J. Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Phys. Rev. Lett., 98: 190504, 2007. 10.1103/​PhysRevLett.98.190504. URL https:/​/​doi.org/​10.1103/​PhysRevLett.98.190504. quant-ph/​0610082.

[30] R. Raussendorf, J. Harrington, and K. Goyal. Topological fault-tolerance in cluster state quantum computation. New J. Phys., 9: 199, 2007. 10.1088/​1367-2630/​9/​6/​199. URL https:/​/​doi.org/​10.1088/​1367-2630/​9/​6/​199. quant-ph/​0703143.

[31] Peter W Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on, pages 124–134. Ieee, 1994. 10.1109/​SFCS.1994.365700.

[32] Christof Zalka. Fast versions of shor's quantum factoring algorithm. arXiv preprint quant-ph/​9806084, 1998. URL https:/​/​arxiv.org/​abs/​quant-ph/​9806084.

Cited by

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

[2] Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush, "Fault-Tolerant Quantum Simulations of Chemistry in First Quantization", PRX Quantum 2 4, 040332 (2021).

[3] Jinyoung Ha, Jonghyun Lee, and Jun Heo, "Resource analysis of quantum computing with noisy qubits for Shor’s factoring algorithms", Quantum Information Processing 21 2, 60 (2022).

[4] Hector Miller-Bakewell, "Finite Verification of Infinite Families of Diagram Equations", Electronic Proceedings in Theoretical Computer Science 318, 27 (2020).

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

[6] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush, "Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization", PRX Quantum 1 2, 020312 (2020).

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

[8] Kento Oonishi, Tomoki Tanaka, Shumpei Uno, Takahiko Satoh, Rodney Van Meter, and Noboru Kunihiro, "Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-Phase Toffoli Gates", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[9] Yasunari Suzuki, Suguru Endo, Keisuke Fujii, and Yuuki Tokunaga, "Quantum Error Mitigation as a Universal Error Reduction Technique: Applications from the NISQ to the Fault-Tolerant Quantum Computing Eras", PRX Quantum 3 1, 010345 (2022).

[10] John S. Van Dyke, George S. Barron, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, "Preparing Bethe Ansatz Eigenstates on a Quantum Computer", PRX Quantum 2 4, 040329 (2021).

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

[12] Bob Coecke, Dominic Horsman, Aleks Kissinger, and Quanlong Wang, "Kindergarden quantum mechanics graduates ...or how I learned to stop gluing LEGO together and love the ZX-calculus", Theoretical Computer Science 897, 1 (2022).

[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] Niel de Beaudrap, "Well-tempered ZX and ZH Calculi", Electronic Proceedings in Theoretical Computer Science 340, 13 (2021).

[15] Torsten Hoefler, Thomas Häner, and Matthias Troyer, "Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage", Communications of the ACM 66 5, 82 (2023).

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

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

[18] Shilin Huang, Michael Newman, and Kenneth R. Brown, "Fault-tolerant weighted union-find decoding on the toric code", Physical Review A 102 1, 012419 (2020).

[19] Joshua J. Goings, Alec White, Joonho Lee, Christofer S. Tautermann, Matthias Degroote, Craig Gidney, Toru Shiozaki, Ryan Babbush, and Nicholas C. Rubin, "Reliably assessing the electronic structure of cytochrome P450 on today’s classical computers and tomorrow’s quantum computers", Proceedings of the National Academy of Sciences 119 38, e2203533119 (2022).

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

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

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

[23] Titouan Carette, Yohann D'Anello, and Simon Perdrix, "Quantum Algorithms and Oracles with the Scalable ZX-calculus", Electronic Proceedings in Theoretical Computer Science 343, 193 (2021).

[24] Julian Schuhmacher, Guglielmo Mazzola, Francesco Tacchino, Olga Dmitriyeva, Tai Bui, Shanshan Huang, and Ivano Tavernelli, "Extending the reach of quantum computing for materials science with machine learning potentials", AIP Advances 12 11, 115321 (2022).

[25] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister, "Logical Clifford Synthesis for Stabilizer Codes", IEEE Transactions on Quantum Engineering 1, 1 (2020).

[26] Gary J. Mooney, Charles D. Hill, and Lloyd C. L. Hollenberg, "Cost-optimal single-qubit gate synthesis in the Clifford hierarchy", Quantum 5, 396 (2021).

[27] Christopher Chamberland and Andrew W. Cross, "Fault-tolerant magic state preparation with flag qubits", Quantum 3, 143 (2019).

[28] Niel de Beaudrap, Ross Duncan, Dominic Horsman, and Simon Perdrix, "Pauli Fusion: a Computational Model to Realise Quantum Transformations from ZX Terms", Electronic Proceedings in Theoretical Computer Science 318, 85 (2020).

[29] Craig Gidney, "Stim: a fast stabilizer circuit simulator", Quantum 5, 497 (2021).

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

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

[32] Niel de Beaudrap and Dominic Horsman, "The ZX calculus is a language for surface code lattice surgery", Quantum 4, 218 (2020).

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

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

[35] Richard D.P. East, John van de Wetering, Nicholas Chancellor, and Adolfo G. Grushin, "AKLT-States as ZX-Diagrams: Diagrammatic Reasoning for Quantum States", PRX Quantum 3 1, 010302 (2022).

[36] Earl T Campbell, "Early fault-tolerant simulations of the Hubbard model", Quantum Science and Technology 7 1, 015007 (2022).

[37] Jonathan Allcock, Anna Vangone, Agnes Meyder, Stanislaw Adaszewski, Martin Strahm, Chang-Yu Hsieh, and Shengyu Zhang, "The Prospects of Monte Carlo Antibody Loop Modelling on a Fault-Tolerant Quantum Computer", Frontiers in Drug Discovery 2, 908870 (2022).

[38] Daniel Litinski, "Magic State Distillation: Not as Costly as You Think", Quantum 3, 205 (2019).

[39] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, "Quantum computing enhanced computational catalysis", Physical Review Research 3 3, 033055 (2021).

[40] Guglielmo Mazzola, "Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers", Physical Review A 104 2, 022431 (2021).

[41] Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven, "Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage", PRX Quantum 2 1, 010103 (2021).

[42] Narayanan Rengaswamy, Robert Calderbank, and Henry D. Pfister, "Unifying the Clifford hierarchy via symmetric matrices over rings", Physical Review A 100 2, 022304 (2019).

[43] Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush, "Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization", Quantum 4, 296 (2020).

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

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

[46] Alain Delgado, Pablo A. M. Casares, Roberto dos Reis, Modjtaba Shokrian Zini, Roberto Campos, Norge Cruz-Hernández, Arne-Christian Voigt, Angus Lowe, Soran Jahangiri, M. A. Martin-Delgado, Jonathan E. Mueller, and Juan Miguel Arrazola, "Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer", Physical Review A 106 3, 032428 (2022).

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

[48] Niel de Beaudrap and Dominic Horsman, "The ZX calculus is a language for surface code lattice surgery", arXiv:1704.08670, (2017).

[49] Craig Gidney and Austin G. Fowler, "Flexible layout of surface code computations using AutoCCZ states", arXiv:1905.08916, (2019).

[50] Hyeongrak Choi, Mihir Pant, Saikat Guha, and Dirk Englund, "Percolation-based architecture for cluster state creation using photon-mediated entanglement between atomic memories", npj Quantum Information 5, 104 (2019).

[51] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister, "Logical Clifford Synthesis for Stabilizer Codes", arXiv:1907.00310, (2019).

[52] Hyeongrak Choi, Mihir Pant, Saikat Guha, and Dirk Englund, "Percolation based architecture for cluster state creation using photon-mediated entanglement between atomic memories", arXiv:1704.07292, (2017).

[53] Niel de Beaudrap, "Well-tempered ZX and ZH Calculi", arXiv:2006.02557, (2020).

[54] Richard D. P. East, Pierre Martin-Dussaud, and John Van de Wetering, "Spin-networks in the ZX-calculus", arXiv:2111.03114, (2021).

[55] Niel de Beaudrap, Ross Duncan, Dominic Horsman, and Simon Perdrix, "Pauli Fusion: a Computational Model to Realise Quantum Transformations from ZX Terms", arXiv:1904.12817, (2019).

[56] Titouan Carette, Yohann D'Anello, and Simon Perdrix, "Quantum Algorithms and Oracles with the Scalable ZX-calculus", arXiv:2104.01043, (2021).

[57] Titouan Carette, Dominic Horsman, and Simon Perdrix, "SZX-calculus: Scalable Graphical Quantum Reasoning", arXiv:1905.00041, (2019).

[58] Alexandru Paler, "SurfBraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code", arXiv:1902.02417, (2019).

[59] Daniel Herr, Alexandru Paler, Simon J. Devitt, and Franco Nori, "Time versus Hardware: Reducing Qubit Counts with a (Surface Code) Data Bus", arXiv:1902.08117, (2019).

[60] Alexandru Paler and Robert Basmadjian, "Clifford Gate Optimisation and T Gate Scheduling: Using Queueing Models for Topological Assemblies", arXiv:1906.06400, (2019).

[61] Tuomas Laakkonen, Konstantinos Meichanetzidis, and John van de Wetering, "Picturing counting reductions with the ZH-calculus", arXiv:2304.02524, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-07 01:52:23) and SAO/NASA ADS (last updated successfully 2023-06-07 01:52:24). The list may be incomplete as not all publishers provide suitable and complete citation data.