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

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.
https://doi.org/10.1103/PhysRevX.8.041015
arXiv:1805.03662

[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.
https://doi.org/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.
arXiv: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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv: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.
https://doi.org/10.1063/1.1499754
arXiv: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.
https://doi.org/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.
https://doi.org/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.
arXiv: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.
arXiv: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.
https://doi.org/10.1038/srep01939

[17] Craig Gidney. Halving the cost of quantum addition. Quantum, 2: 74, 2018. 10.22331/​q-2018-06-18-74.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv: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.
https://doi.org/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.
https://doi.org/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.
arXiv: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.
arXiv: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.
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.
https://doi.org/10.1103/PhysRevLett.98.190504
arXiv: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.
https://doi.org/10.1088/1367-2630/9/6/199
arXiv: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.
https://doi.org/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.
arXiv:quant-ph/9806084

Cited by

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

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

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

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

[5] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov, "Lower bounds on the non-Clifford resources for quantum computations", arXiv:1904.01124 (2019).

[6] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, "Qubitization of Arbitrary Basis Quantum Chemistry by Low Rank Factorization", arXiv:1902.02134 (2019).

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

[8] Narayanan Rengaswamy, Robert Calderbank, and Henry D. Pfister, "Unifying the Clifford Hierarchy via Symmetric Matrices over Rings", arXiv:1902.04022 (2019).

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

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

The above citations are from SAO/NASA ADS (last updated 2019-05-21 05:03:09). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-05-21 05:03:07).