Flag fault-tolerant error correction with arbitrary distance codes

Christopher Chamberland1 and Michael E. Beverland2

1Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada
2Station Q Quantum Architectures and Computation Group, Microsoft ResearchRedmond, WA 98052, USA

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


In this paper we introduce a general fault-tolerant quantum error correction protocol using flag circuits for measuring stabilizers of arbitrary distance codes. In addition to extending flag error correction beyond distance-three codes for the first time, our protocol also applies to a broader class of distance-three codes than was previously known. Flag circuits use extra ancilla qubits to signal when errors resulting from $v$ faults in the circuit have weight greater than $v$. The flag error correction protocol is applicable to stabilizer codes of arbitrary distance which satisfy a set of conditions and uses fewer qubits than other schemes such as Shor, Steane and Knill error correction. We give examples of infinite code families which satisfy these conditions and analyze the behaviour of distance-three and -five examples numerically. Requiring fewer resources than Shor error correction, flag error correction could potentially be used in low-overhead fault-tolerant error correction protocols using low density parity check quantum codes of large code length.

► BibTeX data

► References

[1] Benjamin J. Brown, Daniel Loss, Jiannis K. Pachos, Chris N. Self, and James R. Wootton. Quantum memories at finite temperature. Rev. Mod. Phys., 88: 045005, Nov 2016. 10.1103/​RevModPhys.88.045005.

[2] A Yu Kitaev. Unpaired majorana fermions in quantum wires. Physics-Uspekhi, 44 (10S): 131, 2001. URL http:/​/​stacks.iop.org/​1063-7869/​44/​i=10S/​a=S29.

[3] Torsten Karzig, Christina Knapp, Roman M. Lutchyn, Parsa Bonderson, Matthew B. Hastings, Chetan Nayak, Jason Alicea, Karsten Flensberg, Stephan Plugge, Yuval Oreg, Charles M. Marcus, and Michael H. Freedman. Scalable designs for quasiparticle-poisoning-protected topological quantum computation with majorana zero modes. Phys. Rev. B, 95: 235305, Jun 2017. 10.1103/​PhysRevB.95.235305.

[4] Peter W. Shor. Fault-tolerant quantum computation. Proceedings., 37th Annual Symposium on Foundations of Computer Science, pages 56–65, 1996. URL http:/​/​dl.acm.org/​citation.cfm?id=874062.875509.

[5] A. M. Steane. Active stabilization, quantum computation, and quantum state synthesis. Phys. Rev. Lett., 78: 2252–2255, Mar 1997. 10.1103/​PhysRevLett.78.2252.

[6] E. Knill. Scalable quantum computing in the presence of large detected-error rates. Phys. Rev. A, 71: 042322, Apr 2005a. 10.1103/​PhysRevA.71.042322.

[7] Sergey Bravyi and Alexei Kitaev. Quantum codes on a lattice with boundary. arXiv:quant-ph/​9811052, 1998.

[8] Eric Dennis, Alexei Kitaev, Andrew Landhal, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43: 4452–4505, 2002. 10.1063/​1.1499754.

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

[10] Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 176–188. ACM, 1997. 10.1137/​S0097539799359385.

[11] John Preskill. Reliable quantum computers. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969): 385–410, 1998. 10.1098/​rspa.1998.0167.

[12] Emanuel Knill, Raymond Laflamme, and Wojciech H. Zurek. Resilient quantum computation. Science, 279: 342–345, 1998. 10.1126/​science.279.5349.342.

[13] David Poulin. Optimal and efficient decoding of concatenated quantum block codes. Phys. Rev. A, 74: 052333, Nov 2006. 10.1103/​PhysRevA.74.052333.

[14] David S. Wang, Austin G. Fowler, and Lloyd C. L. Hollenberg. Surface code quantum computing with error rates over 1 Phys. Rev. A, 83: 020302, Feb 2011. 10.1103/​PhysRevA.83.020302.

[15] R. Gallager. Low-density parity-check codes. IRE Transactions on Information Theory, 8 (1): 21–28, 1962. 10.1109/​TIT.1962.1057683.

[16] Alexey A. Kovalev and Leonid P. Pryadko. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Phys. Rev. A, 87: 020304, Feb 2013. 10.1103/​PhysRevA.87.020304.

[17] J. P. Tillich and G. Z�mor. Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60 (2): 1193–1202, Feb 2014. ISSN 0018-9448. 10.1109/​TIT.2013.2292061.

[18] Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Info. Comput., 14 (15-16): 1338–1372, November 2014. ISSN 1533-7146. URL http:/​/​dl.acm.org/​citation.cfm?id=2685179.2685184.

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

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

[21] Jesse Fern. An upper bound on quantum fault tolerant thresholds. arXiv:quant-ph/​0801.2608, 2008.

[22] David P. DiVincenzo and Panos Aliferis. Effective fault-tolerant quantum computation with slow measurements. Phys. Rev. Lett., 98: 020501, Jan 2007. 10.1103/​PhysRevLett.98.020501.

[23] Rui Chao and Ben W. Reichardt. Quantum error correction with only two extra qubits. arXiv:quant-ph/​1705.02329, 2017a.

[24] Rui Chao and Ben W. Reichardt. Fault-tolerant quantum computation with few qubits. arXiv:quant-ph/​1705.05365, 2017b.

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

[26] Barbara M. Terhal. Quantum error correction for quantum memories. Rev. Mod. Phys., 87: 307–346, Apr 2015. 10.1103/​RevModPhys.87.307.

[27] Christopher Chamberland, Pavithran Iyer, and David Poulin. Fault-Tolerant Quantum Computing in the Pauli or Clifford Frame with Slow Error Diagnostics. Quantum, 2: 43, January 2018. ISSN 2521-327X. 10.22331/​q-2018-01-04-43.

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

[29] Andrew W. Cross, David P. Divincenzo, and Barbara M. Terhal. A comparative code study for quantum fault tolerance. Quantum Info. Comput., 9 (7): 541–572, July 2009. ISSN 1533-7146. URL http:/​/​dl.acm.org/​citation.cfm?id=2011814.2011815.

[30] Panos Aliferis and Andrew W. Cross. Subsystem fault tolerance with the bacon-shor code. Phys. Rev. Lett., 98: 220502, May 2007. 10.1103/​PhysRevLett.98.220502.

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

[32] 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. 10.1070/​1063-7869/​44/​10S/​S29.

[33] A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2 – 30, 2003. ISSN 0003-4916. 10.1016/​S0003-4916(02)00018-0.

[34] Yu Tomita and Krysta M. Svore. Low-distance surface codes under realistic quantum noise. Phys. Rev. A, 90: 062320, Dec 2014. 10.1103/​PhysRevA.90.062320.

[35] Xiao-Gang Wen. Quantum orders in an exact soluble model. Phys. Rev. Lett., 90: 016803, Jan 2003. 10.1103/​PhysRevLett.90.016803.

[36] H. Bombin and M. A. Martin-Delgado. Topological quantum distillation. Phys. Rev. Lett., 97: 180501, Oct 2006. 10.1103/​PhysRevLett.97.180501.

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

[38] Andrew J. Landahl, Jonas T. Anderson, and Patrick R. Rice. Fault-tolerant quantum computing with color codes. arXiv:1108.5738, 2011.

[39] Hayato Goto. Minimizing resource overheads for fault-tolerant preparation of encoded states of the steane code. Scientific Reports, (6): 19578, 2016. 10.1038/​srep19578.

[40] Adam Paetznick and Ben W. Reichardt. Fault-tolerant ancilla preparation and noise threshold lower boudds 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.

[41] Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17 (3): 449–467, 1965. 10.4153/​CJM-1965-045-4.

[42] Vladimir Kolmogorov. Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1 (1): 43–67, 2009. 10.1007/​s12532-009-0002-8.

[43] Raymond Laflamme, Cesar Miquel, Juan Pablo Paz, and Wojciech Hubert Zurek. Perfect quantum error correcting code. Phys. Rev. Lett., 77: 198–201, Jul 1996. 10.1103/​PhysRevLett.77.198.

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

Cited by

[1] Vickram N. Premakumar, Hele Sha, Daniel Crow, Eric Bach, and Robert Joynt, "2-designs and redundant syndrome extraction for quantum error correction", Quantum Information Processing 20 3, 84 (2021).

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

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

[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] Lingling Lao and Carmen G. Almudever, "Fault-tolerant quantum error correction on near-term quantum processors using flag and bridge qubits", Physical Review A 101 3, 032333 (2020).

[6] 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", Physical Review A 100 6, 062307 (2019).

[7] Joschka Roffe, "Quantum error correction: an introductory guide", Contemporary Physics 60 3, 226 (2019).

[8] Ben W Reichardt, "Fault-tolerant quantum error correction for Steane’s seven-qubit color code with few or no extra qubits", arXiv:1804.06995, Quantum Science and Technology 6 1, 015007 (2020).

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

[10] J. Conrad, C. Chamberland, N. P. Breuckmann, and B. M. Terhal, "The small stellated dodecahedron code and friends", Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 376 2123, 20170323 (2018).

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

[12] Rui Chao and Ben W. Reichardt, "Quantum Error Correction with Only Two Extra Qubits", Physical Review Letters 121 5, 050502 (2018).

[13] P Baireuther, M D Caio, B Criger, C W J Beenakker, and T E O’Brien, "Neural network decoder for topological color codes with circuit level noise", New Journal of Physics 21 1, 013003 (2019).

[14] Andrea Rodriguez-Blanco, Alejandro Bermudez, Markus Müller, and Farid Shahandeh, "Efficient and Robust Certification of Genuine Multipartite Entanglement in Noisy Quantum Error Correction Circuits", PRX Quantum 2 2, 020304 (2021).

[15] Joschka Roffe, David Headley, Nicholas Chancellor, Dominic Horsman, and Viv Kendon, "Protecting quantum memories using coherent parity check codes", Quantum Science and Technology 3 3, 035010 (2018).

[16] Natalie C Brown, Michael Newman, and Kenneth R Brown, "Handling leakage with subsystem codes", New Journal of Physics 21 7, 073055 (2019).

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

[18] Shilin Huang and Kenneth R. Brown, "Constructions for measuring error syndromes in Calderbank-Shor-Steane codes between Shor and Steane methods", Physical Review A 104 2, 022429 (2021).

[19] Chen Lin, YiChen Wang, JinZhao Wu, and GuoWu Yang, "Efficient Decoding Scheme of Non-Uniform Concatenation Quantum Code with Deep Neural Network", International Journal of Theoretical Physics 60 3, 848 (2021).

[20] Shilin Huang and Kenneth R. Brown, "Between Shor and Steane: A Unifying Construction for Measuring Error Syndromes", Physical Review Letters 127 9, 090505 (2021).

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

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

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

[24] Christopher Chamberland and Pooya Ronagh, "Deep neural decoders for near term fault-tolerant experiments", Quantum Science and Technology 3 4, 044002 (2018).

[25] Christina Knapp, Michael Beverland, Dmitry I. Pikulin, and Torsten Karzig, "Modeling noise and error correction for Majorana-based quantum computing", Quantum 2, 88 (2018).

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

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

[28] Y. Ma, Y. Xu, X. Mu, W. Cai, L. Hu, W. Wang, X. Pan, H. Wang, Y. P. Song, C.-L. Zou, and L. Sun, "Error-transparent operations on a logical qubit protected by quantum error correction", Nature Physics 16 8, 827 (2020).

[29] Atharv Joshi, Kyungjoo Noh, and Yvonne Y Gao, "Quantum information processing with bosonic qubits in circuit QED", Quantum Science and Technology 6 3, 033001 (2021).

[30] Pedro Parrado-Rodríguez, Ciarán Ryan-Anderson, Alejandro Bermudez, and Markus Müller, "Crosstalk Suppression for Fault-tolerant Quantum Error Correction with Trapped Ions", Quantum 5, 487 (2021).

[31] Shilin Huang and Kenneth R. Brown, "Fault-tolerant compass codes", Physical Review A 101 4, 042312 (2020).

[32] Michael E Beverland, Benjamin J Brown, Michael J Kastoryano, and Quentin Marolleau, "The role of entropy in topological quantum error correction", Journal of Statistical Mechanics: Theory and Experiment 2019 7, 073404 (2019).

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

[34] M. Gutiérrez, M. Müller, and A. Bermúdez, "Transversality and lattice surgery: Exploring realistic routes toward coupled logical qubits with trapped-ion quantum processors", Physical Review A 99 2, 022330 (2019).

[35] Dripto M Debroy, Muyuan Li, Shilin Huang, and Kenneth R Brown, "Logical performance of 9 qubit compass codes in ion traps with crosstalk errors", Quantum Science and Technology 5 3, 034002 (2020).

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

[37] Christophe Vuillot, "Is error detection helpful on IBM 5Q chips ?", arXiv:1705.08957.

[38] Prithviraj Prabhu and Ben W. Reichardt, "Fault-tolerant syndrome extraction and cat state preparation with fewer qubits", arXiv:2108.02184.

[39] Weilei Zeng, Alexei Ashikhmin, Michael Woolls, and Leonid P. Pryadko, "Quantum convolutional data-syndrome codes", arXiv:1902.07395.

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