Fault-tolerant magic state preparation with flag qubits

Christopher Chamberland1,2 and Andrew W. Cross1

1IBM T. J. Watson Research Center, Yorktown Heights, NY, 10598, United States
2Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

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


Magic state distillation is one of the leading candidates for implementing universal fault-tolerant logical gates. However, the distillation circuits themselves are not fault-tolerant, so there is additional cost to first implement encoded Clifford gates with negligible error. In this paper we present a scheme to fault-tolerantly and directly prepare magic states using flag qubits. One of these schemes requires only three ancilla qubits, even with noisy Clifford gates. We compare the physical qubit and gate cost of our scheme to the magic state distillation protocol of Meier, Eastin, and Knill (MEK), which is efficient and uses a small stabilizer circuit. For low enough noise rates, we show that in some regimes the overhead can be improved by several orders of magnitude compared to the MEK scheme which uses Clifford operations encoded in the codes considered in this work.

► BibTeX data

► References

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

[2] Quantum Algorithm Zoo. https:/​/​math.nist.gov/​quantum/​zoo/​. Last Accessed: 2018-10-31.

[3] Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets. Phys. Rev. Lett., 102: 110502, Mar 2009. 10.1103/​PhysRevLett.102.110502. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.102.110502.

[4] E. Knill, R. Laflamme, and W. Zurek. Threshold Accuracy for Quantum Computation. arXiv e-prints, art. quant-ph/​9610011, Oct 1996. URL https:/​/​ui.adsabs.harvard.edu/​abs/​1996quant.ph.10011K.

[5] Tomas Jochym-O'Connor and Raymond Laflamme. Using concatenated quantum codes for universal fault-tolerant quantum gates. Phys. Rev. Lett., 112: 010505, 2014. 10.1103/​PhysRevLett.112.010505. URL http:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.112.010505.

[6] Adam Paetznick and Ben W. Reichardt. Universal fault-tolerant quantum computation with only transversal gates and error correction. Phys. Rev. Lett., 111: 090505, Aug 2013. 10.1103/​PhysRevLett.111.090505. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.111.090505.

[7] Jonas T. Anderson, Guillaume Duclos-Cianci, and David Poulin. Phys. Rev. Lett., 113: 080501, Aug 2014. 10.1103/​PhysRevLett.113.080501.

[8] Héctor Bombín. Dimensional jump in quantum error correction. New Journal of Physics, 18 (4): 043038, apr 2016. 10.1088/​1367-2630/​18/​4/​043038. URL https:/​/​doi.org/​10.1088.

[9] Theodore J. Yoder, Ryuji Takagi, and Isaac L. Chuang. Universal fault-tolerant gates on concatenated stabilizer codes. Phys. Rev. X, 6: 031039, Sep 2016. 10.1103/​PhysRevX.6.031039. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevX.6.031039.

[10] E. Knill. Fault-Tolerant Postselected Quantum Computation: Schemes. arXiv e-prints, art. quant-ph/​0402171, Feb 2004. URL https:/​/​ui.adsabs.harvard.edu/​abs/​2004quant.ph..2171K.

[11] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Phys. Rev. A, 71: 022316, Feb 2005. 10.1103/​PhysRevA.71.022316. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.71.022316.

[12] Jeongwan Haah, Matthew B. Hastings, D. Poulin, and D. Wecker. Magic state distillation with low space overhead and optimal asymptotic input count. Quantum, 1: 31, October 2017. ISSN 2521-327X. 10.22331/​q-2017-10-03-31. URL https:/​/​doi.org/​10.22331/​q-2017-10-03-31.

[13] Jeongwan Haah and Matthew B. Hastings. Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates. Quantum, 2: 71, June 2018. ISSN 2521-327X. 10.22331/​q-2018-06-07-71. URL https:/​/​doi.org/​10.22331/​q-2018-06-07-71.

[14] Matthew B. Hastings and Jeongwan Haah. Distillation with sublogarithmic overhead. Phys. Rev. Lett., 120: 050504, Jan 2018. 10.1103/​PhysRevLett.120.050504. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.120.050504.

[15] Jeongwan Haah, Matthew B. Hastings, David Poulin, and Dave Wecker. Magic state distillation at intermediate size. Quantum Info. Comput., 18 (1& 2): 97–165, February 2018. ISSN 0114-0140.

[16] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86: 032324, Sep 2012. 10.1103/​PhysRevA.86.032324.

[17] Hayato Goto. Step-by-step magic state encoding for efficient fault-tolerant quantum computation. Scientific Reports, (4): 7501, 2014. 10.1038/​srep07501.

[18] Joe O'Gorman and Earl T. Campbell. Quantum computation with realistic magic-state factories. Phys. Rev. A, 95: 032338, Mar 2017. 10.1103/​PhysRevA.95.032338. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.95.032338.

[19] Daniel Litinski. A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum, 3: 128, March 2019. ISSN 2521-327X. 10.22331/​q-2019-03-05-128. URL https:/​/​doi.org/​10.22331/​q-2019-03-05-128.

[20] Theodore J. Yoder and Isaac H. Kim. The surface code with a twist. Quantum, 1: 2, April 2017. ISSN 2521-327X. 10.22331/​q-2017-04-25-2. URL https:/​/​doi.org/​10.22331/​q-2017-04-25-2.

[21] Rui Chao and Ben W. Reichardt. Quantum error correction with only two extra qubits. Phys. Rev. Lett., 121: 050502, Aug 2018. 10.1103/​PhysRevLett.121.050502. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.121.050502.

[22] Rui Chao and Ben W. Reichardt. Fault-tolerant quantum computation with few qubits. arXiv:quant-ph/​1705.05365, 2017. URL https:/​/​arxiv.org/​abs/​1705.05365. URL https:/​/​doi.org/​10.1038/​s41534-018-0085-z.

[23] Christopher Chamberland and Michael E. Beverland. Flag fault-tolerant error correction with arbitrary distance codes. Quantum, 2: 53, February 2018. ISSN 2521-327X. 10.22331/​q-2018-02-08-53. URL https:/​/​doi.org/​10.22331/​q-2018-02-08-53.

[24] Theerapat Tansuwannont, Christopher Chamberland, and Debbie Leung. Flag fault-tolerant error correction, measurement, and quantum computation for cyclic CSS codes. arXiv e-prints, art. arXiv:1803.09758, Mar 2018. URL https:/​/​ui.adsabs.harvard.edu/​abs/​2018arXiv180309758T.

[25] Ben W. Reichardt. Fault-tolerant quantum error correction for steane's seven-qubit color code with few or no extra qubits. arXiv:quant-ph/​1804.06995, 2018. URL https:/​/​arxiv.org/​abs/​1804.06995.

[26] Adam M. Meier, Bryan Eastin, and Emanuel Knill. Magic-state distillation with the four-qubit code. Quantum Info. Comput., 13 (3-4): 0195–0209, 2013.

[27] Austin G. Fowler and Craig Gidney. Low overhead quantum computation using lattice surgery. arXiv e-prints, art. arXiv:1808.06709, Aug 2018. URL https:/​/​ui.adsabs.harvard.edu/​abs/​2018arXiv180806709F.

[28] Craig Gidney and Austin G. Fowler. Efficient magic state factories with a catalyzed $|CCZ\rangle$ to $2|T\rangle$ transformation. Quantum, 3: 135, April 2019. ISSN 2521-327X. 10.22331/​q-2019-04-30-135. URL https:/​/​doi.org/​10.22331/​q-2019-04-30-135.

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

[30] Panos Aliferis, Daniel Gottesman, and John Preskill. Quantum accuracy threshold for concatenated distance-3 codes. Quantum Info. Comput., 6 (2): 97–165, March 2006. ISSN 1533-7146. URL http:/​/​dl.acm.org/​citation.cfm?id=2011665.2011666.

[31] Colin J Trout, Muyuan Li, Mauricio Gutiérrez, Yukai Wu, Sheng-Tao Wang, Luming Duan, and Kenneth R Brown. Simulating the performance of a distance-3 surface code in a linear ion trap. New Journal of Physics, 20 (4): 043038, apr 2018. 10.1088/​1367-2630/​aab341. URL https:/​/​doi.org/​10.1088.

[32] A. Bermudez, X. Xu, M. Gutiérrez, S. C. Benjamin, and M. Müller. Fault-tolerant protection of near-term trapped-ion topological qubits under realistic noise sources. arXiv e-prints, art. arXiv:1810.09199, Oct 2018. URL https:/​/​ui.adsabs.harvard.edu/​abs/​2018arXiv181009199B.

[33] Maika Takita, Andrew W. Cross, A. D. Córcoles, Jerry M. Chow, and Jay M. Gambetta. Experimental demonstration of fault-tolerant state preparation with superconducting qubits. Phys. Rev. Lett., 119: 180501, Oct 2017. 10.1103/​PhysRevLett.119.180501. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.119.180501.

[34] Adam Paetznick and Ben W. Reichardt. Fault-tolerant ancilla preparation and noise threshold lower bounds for the 23-qubit golay code. Quantum Info. Comput., 12 (11-12): 1034–1080, November 2012. ISSN 1533-7146. URL http:/​/​dl.acm.org/​citation.cfm?id=2481569.2481579.

[35] Christopher Chamberland, Tomas Jochym-O'Connor, and Raymond Laflamme. Thresholds for universal concatenated quantum codes. Phys. Rev. Lett., 117: 010501, Jun 2016. 10.1103/​PhysRevLett.117.010501. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.117.010501.

[36] Christopher Chamberland, Tomas Jochym-O'Connor, and Raymond Laflamme. Overhead analysis of universal concatenated quantum codes. Phys. Rev. A, 95: 022313, Feb 2017. 10.1103/​PhysRevA.95.022313.

[37] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54: 1098–1105, Aug 1996. 10.1103/​PhysRevA.54.1098.

[38] Andrew W. Steane. Multiple-Particle Interference and Quantum Error Correction. Proc. Roy. Soc. Lond., 452: 2551–2577, 1996. URL http:/​/​www.jstor.org/​stable/​52827.

[39] Earl Campbell and Dan Browne. On the structure of protocols for magic state distillation. Lecture Notes in Computer Science, 5906.

[40] Andrew J. Landahl and Ciaran Ryan-Anderson. Quantum computing by color-code lattice surgery. arXiv e-prints, art. arXiv:1407.5103, Jul 2014. URL https:/​/​ui.adsabs.harvard.edu/​abs/​2014arXiv1407.5103L.

[41] Christophe Vuillot, Lingling Lao, Ben Criger, Carmen García Almudéver, Koen Bertels, and Barbara M Terhal. Code deformation and lattice surgery are gauge fixing. New Journal of Physics, 21 (3): 033028, mar 2019. 10.1088/​1367-2630/​ab0199. URL https:/​/​doi.org/​10.1088.

[42] Daniel Gottesman. An introduction to quantum error correction and fault-tolerant quantum computation. Proceedings of Symposia in Applied Mathematics, 68: 13–58, 2010. URL https:/​/​arxiv.org/​abs/​0904.2557.

[43] Emanuel Knill. Quantum computing with realistically noisy devices. Nature, 434 (7029): 39–44, 2005. 10.1038/​nature03350.

[44] Panagiotis Panos Aliferis. Level reduction and the quantum threshold theorem. PhD thesis, California Institute of Technology, 2007.

[45] Qiskit: an open source quantum computing framework. https:/​/​github.com/​Qiskit. Last Accessed: 2018-10-31.

Cited by

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

[2] Wen-Long Ma, Mengzhen Zhang, Yat Wong, Kyungjoo Noh, Serge Rosenblum, Philip Reinhold, Robert J. Schoelkopf, and Liang Jiang, "Path-Independent Quantum Gates with Noisy Ancilla", Physical Review Letters 125 11, 110503 (2020).

[3] Theerapat Tansuwannont and Debbie Leung, "Fault-tolerant quantum error correction using error weight parities", Physical Review A 104 4, 042410 (2021).

[4] Christopher Chamberland, Aleksander Kubica, Theodore J Yoder, and Guanyu Zhu, "Triangular color codes on trivalent graphs with flag qubits", New Journal of Physics 22 2, 023019 (2020).

[5] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", Physical Review Research 2 3, 033444 (2020).

[6] Yunong Shi, Christopher Chamberland, and Andrew Cross, "Fault-tolerant preparation of approximate GKP states", arXiv:1905.00903, New Journal of Physics 21 9, 093007 (2019).

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

[8] Ilkwon Sohn, Jeongho Bang, and Jun Heo, "Dynamic Concatenation of Quantum Error Correction in Integrated Quantum Computing Architecture", Scientific Reports 9 1, 3302 (2019).

[9] Christopher Chamberland, Guanyu Zhu, Theodore J. Yoder, Jared B. Hertzberg, and Andrew W. Cross, "Topological and Subsystem Codes on Low-Degree Graphs with Flag Qubits", Physical Review X 10 1, 011022 (2020).

[10] Dripto M. Debroy and Kenneth R. Brown, "Extended flag gadgets for low-overhead circuit verification", Physical Review A 102 5, 052409 (2020).

[11] Xin Wang, Mark M. Wilde, and Yuan Su, "Efficiently Computable Bounds for Magic State Distillation", arXiv:1812.10145, Physical Review Letters 124 9, 090505 (2020).

[12] Xiaosi Xu, Simon C. Benjamin, and Xiao Yuan, "Variational Circuit Compiler for Quantum Error Correction", Physical Review Applied 15 3, 034068 (2021).

[13] Rui Chao and Ben W. Reichardt, "Flag Fault-Tolerant Error Correction for any Stabilizer Code", arXiv:1912.09549, PRX Quantum 1 1, 010302 (2020).

[14] Leonid P. Pryadko, "On maximum-likelihood decoding with circuit-level errors", arXiv:1909.06732, Quantum 4, 304 (2020).

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

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

[17] Theerapat Tansuwannont, Christopher Chamberland, and Debbie Leung, "Flag fault-tolerant error correction, measurement, and quantum computation for cyclic Calderbank-Shor-Steane codes", Physical Review A 101 1, 012342 (2020).

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

[19] Xin Wang, Mark M Wilde, and Yuan Su, "Quantifying the magic of quantum channels", arXiv:1903.04483, New Journal of Physics 21 10, 103002 (2019).

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

[21] Yuxiang Yang, Yin Mo, Joseph M. Renes, Giulio Chiribella, and Mischa P. Woods, "Covariant Quantum Error Correcting Codes via Reference Frames", arXiv:2007.09154.

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