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

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.
https://doi.org/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.
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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/10.1103/PhysRevA.71.042322

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

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/10.1103/PhysRevA.54.1098

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

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

[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.
https://doi.org/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.
arXiv:quant-ph/1705.02329

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

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1070/1063-7869/44/10S/S29
https:/​/​arxiv.org/​abs/​0904.2557

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
arXiv:1108.5738

[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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
http:/​/​www.jstor.org/​stable/​52827

► Cited by (beta)

[1] J. Conrad, C. Chamberland, N. P. Breuckmann, 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).

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

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

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

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

(The above data is from Crossref's cited-by service. Unfortunately not all publishers provide suitable and complete citation data so that some citing works or bibliographic details may be missing.)