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] Hector Miller-Bakewell, "Finite Verification of Infinite Families of Diagram Equations", Electronic Proceedings in Theoretical Computer Science 318, 27 (2020).

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

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

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

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

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

[8] 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, Electronic Proceedings in Theoretical Computer Science 318, 85 (2020).

[9] 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 1, 104 (2019).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[24] Niel de Beaudrap, "Well-tempered ZX and ZH calculi", arXiv:2006.02557.

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-21 13:36:06) and SAO/NASA ADS (last updated successfully 2021-04-21 13:36:07). The list may be incomplete as not all publishers provide suitable and complete citation data.