Concatenation Schemes for Topological Fault-tolerant Quantum Error Correction

Zhaoyi Li1, Isaac Kim2, and Patrick Hayden1

1Department of Physics, Stanford University, Stanford, CA 94305, USA
2Department of Computer Science, University of California, Davis, CA 95616, USA

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


We investigate a family of fault-tolerant quantum error correction schemes based on the concatenation of small error detection or error correction codes with the three-dimensional cluster state. We propose fault-tolerant state preparation and decoding schemes that effectively convert every circuit-level error into an erasure error, leveraging the cluster state's high threshold against such errors. We find a set of codes for which such a conversion is possible, and study their performance against the standard circuit-level depolarizing model. Our best performing scheme, which is based on a concatenation with a classical code, improves the threshold by $16.5\%$ and decreases the spacetime overhead by $32\%$ compared to the scheme without concatenation, with each scheme subject to a physical error rate of $10^{-3}$ and achieving a logical error rate of $10^{-6}$.

Taming errors is one of the most significant challenges in building a reliable quantum computer. One of the leading approaches to solve this problem is to use a resource state that can be used for fault-tolerant quantum computation, such as the three-dimensional (3D) cluster state. In this study, we outline a new method for augmenting error-correcting capability of the 3D body-centered cubic (bcc) cluster state with a small error-detecting code, improving its fault-tolerance. Our approach can transform unknown errors into erasures at known locations, making the errors easier to correct. We numerically and analytically study the performance of our approach, conclusively demonstrating that our approach outperforms the conventional bcc cluster state under realistic noise models. Our techniques expand our toolkit for building a robust quantum computer.

► BibTeX data

► References

[1] Dorit Aharonov and Michael Ben-Or. Fault-Tolerant Quantum Computation with Constant Error Rate. SIAM Journal on Computing, 38 (4): 1207–1282, July 2008. ISSN 0097-5397. https:/​/​​10.1137/​S0097539799359385.

[2] Panos Aliferis, Daniel Gottesman, and John Preskill. Quantum accuracy threshold for concatenated distance-3 codes. Quantum Info. Comput., 6 (2): 97–165, mar 2006. ISSN 1533-7146. https:/​/​​10.26421/​QIC6.2-1.

[3] Sean D Barrett and Thomas M Stace. Fault tolerant quantum computation with very high threshold for loss errors. Physical review letters, 105 (20): 200502, 2010. https:/​/​​10.1103/​PhysRevLett.105.200502.

[4] Alejandro Bermudez, Xiaosi Xu, Ramil Nigmatullin, Joe O’Gorman, Vlad Negnevitsky, Philipp Schindler, Thomas Monz, UG Poschinger, Cornelius Hempel, Jonathan Home, et al. Assessing the progress of trapped-ion processors towards fault-tolerant quantum computation. Physical Review X, 7 (4): 041061, 2017. https:/​/​​10.1103/​PhysRevX.7.041061.

[5] A Bolt, G Duclos-Cianci, D Poulin, and TM Stace. Foliated quantum error-correcting codes. Physical review letters, 117 (7): 070501, 2016. https:/​/​​10.1103/​PhysRevLett.117.070501.

[6] J Eli Bourassa, Rafael N Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q Baragiola, Saikat Guha, Guillaume Dauphinais, et al. Blueprint for a scalable photonic fault-tolerant quantum computer. Quantum, 5: 392, 2021. https:/​/​​10.22331/​q-2021-02-04-392.

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

[8] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel. Quantum advantage with noisy shallow circuits. Nature Physics, 16 (10): 1040–1045, 2020. https:/​/​​10.1038/​s41567-020-0948-z.

[9] Nikolas P Breuckmann and Xiaotong Ni. Scalable neural network decoders for higher dimensional quantum codes. Quantum, 2: 68, 2018. https:/​/​​10.22331/​q-2018-05-24-68.

[10] Hans J Briegel, David E Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5 (1): 19–26, 2009. https:/​/​​10.1038/​nphys1157.

[11] Benjamin J. Brown and Sam Roberts. Universal fault-tolerant measurement-based quantum computation. Physical Review Research, 2 (3), aug 2020. 10.1103/​physrevresearch.2.033305. URL https:/​/​​10.1103.

[12] Yudong Cao, Jonathan Romero, Jonathan P Olson, Matthias Degroote, Peter D Johnson, Mária Kieferová, Ian D Kivlichan, Tim Menke, Borja Peropadre, Nicolas PD Sawaya, et al. Quantum chemistry in the age of quantum computing. Chemical reviews, 119 (19): 10856–10915, 2019. https:/​/​​10.1021/​acs.chemrev.8b00803.

[13] Christopher Chamberland, Tomas Jochym-O’Connor, and Raymond Laflamme. Thresholds for universal concatenated quantum codes. Physical review letters, 117 (1): 010501, 2016. https:/​/​​10.1103/​PhysRevLett.117.010501.

[14] Christopher Chamberland, Luis Goncalves, Prasahnt Sivarajah, Eric Peterson, and Sebastian Grimberg. Techniques for combining fast local decoders with global decoders under circuit-level noise. Quantum Science and Technology, 8 (4): 045011, jul 2023. https:/​/​​10.1088/​2058-9565/​ace64d.

[15] Rui Chao and Ben W Reichardt. Quantum error correction with only two extra qubits. Physical review letters, 121 (5): 050502, 2018. https:/​/​​10.1103/​PhysRevLett.121.050502.

[16] Ben Criger and Barbara Terhal. Noise thresholds for the [4,2,2]-concatenated toric code. Quantum Info. Comput., 16 (15–16): 1261–1281, nov 2016. ISSN 1533-7146. https:/​/​​10.26421/​QIC16.15-16-1.

[17] Andrew W Cross, David P DiVincenzo, and Barbara M Terhal. A comparative code study for quantum fault-tolerance. arXiv preprint arXiv:0711.1556, 2007. http:/​/​​10.26421/​QIC9.7-8-1.

[18] Poulami Das, Christopher A Pattison, Srilatha Manne, Douglas M Carmean, Krysta M Svore, Moinuddin Qureshi, and Nicolas Delfosse. Afs: Accurate, fast, and scalable error-decoding for fault-tolerant quantum computers. In 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pages 259–273. IEEE, 2022. https:/​/​​10.1109/​HPCA53966.2022.00027.

[19] Nicolas Delfosse. Hierarchical decoding to reduce hardware requirements for quantum computing. arXiv preprint arXiv:2001.11427, 2020. https:/​/​​10.48550/​arXiv.2001.11427.

[20] Nicolas Delfosse and Naomi H Nickerson. Almost-linear time decoding algorithm for topological codes. Quantum, 5: 595, December 2021. ISSN 2521-327X. https:/​/​​10.22331/​q-2021-12-02-595.

[21] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9): 4452–4505, 2002. https:/​/​​10.1063/​1.1499754.

[22] Austin G Fowler, Adam C Whiteside, Angus L McInnes, and Alimohammad Rabbani. Topological code autotune. Physical Review X, 2 (4): 041003, 2012. https:/​/​​10.1103/​PhysRevX.2.041003.

[23] Kosuke Fukui, Akihisa Tomita, Atsushi Okamoto, and Keisuke Fujii. High-threshold fault-tolerant quantum computation with analog quantum error correction. Physical review X, 8 (2): 021054, 2018. https:/​/​​10.1103/​PhysRevX.8.021054.

[24] Iulia M Georgescu, Sahel Ashhab, and Franco Nori. Quantum simulation. Reviews of Modern Physics, 86 (1): 153, 2014. https:/​/​​10.1103/​RevModPhys.86.153.

[25] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction, May 1997.

[26] Daniel Gottesman. Theory of fault-tolerant quantum computation. Physical Review A, 57 (1): 127, 1998. https:/​/​​10.1103/​PhysRevA.57.127.

[27] Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Information & Computation, 14 (15-16): 1338–1372, November 2014. ISSN 1533-7146. https:/​/​​10.1016/​S0003-4916(02)00018-0.

[28] Alexei Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2–30, 2003. ISSN 0003-4916. https:/​/​​10.1016/​S0003-4916(02)00018-0. URL https:/​/​​science/​article/​pii/​S0003491602000180.

[29] Emanuel Knill. Fault-tolerant postselected quantum computation: Schemes. arXiv preprint quant-ph/​0402171, 2004a. https:/​/​​10.48550/​arXiv.quant-ph/​0402171.

[30] Emanuel Knill. Fault-tolerant postselected quantum computation: Threshold analysis. arXiv preprint quant-ph/​0404104, 2004b. https:/​/​​10.48550/​arXiv.quant-ph/​0404104.

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

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

[33] Aleksander Kubica, Arbel Haim, Yotam Vaknin, Fernando Brandão, and Alex Retzker. Erasure qubits: Overcoming the $t_1$ limit in superconducting circuits. arXiv preprint arXiv:2208.05461, 2022. https:/​/​​10.48550/​arXiv.2208.05461.

[34] Daniel Litinski. Magic State Distillation: Not as Costly as You Think. Quantum, 3: 205, December 2019. ISSN 2521-327X. 10.22331/​q-2019-12-02-205. URL https:/​/​​10.22331/​q-2019-12-02-205.

[35] John Napp and John Preskill. Optimal bacon-shor codes. arXiv preprint arXiv:1209.0794, 2012. https:/​/​​10.48550/​arXiv.1209.0794.

[36] Michael Newman, Leonardo A de Castro, and Kenneth R Brown. Generating fault-tolerant cluster states from crystal structures. Quantum, 4: 295, 2020. https:/​/​​10.22331/​q-2020-07-13-295.

[37] Naomi Nickerson and Héctor Bombín. Measurement based fault tolerance beyond foliation. arXiv preprint arXiv:1810.09621, 2018. https:/​/​​10.48550/​arXiv.1810.09621.

[38] Naomi H Nickerson, Ying Li, and Simon C Benjamin. Topological quantum computing with a very noisy network and local error rates approaching one percent. Nature communications, 4 (1): 1–5, 2013. https:/​/​​10.1038/​ncomms2773.

[39] Kyungjoo Noh and Christopher Chamberland. Fault-tolerant bosonic quantum error correction with the surface–gottesman-kitaev-preskill code. Physical Review A, 101 (1): 012316, 2020. https:/​/​​10.1103/​PhysRevA.101.012316.

[40] Kyungjoo Noh, Christopher Chamberland, and Fernando GSL Brandão. Low-overhead fault-tolerant quantum error correction with the surface-gkp code. PRX Quantum, 3 (1): 010315, 2022. https:/​/​​10.1103/​PRXQuantum.3.010315.

[41] David Poulin. Optimal and efficient decoding of concatenated quantum block codes. Physical Review A, 74 (5), nov 2006. https:/​/​​10.1103/​PhysRevA.74.052333. URL https:/​/​​10.1103.

[42] Robert Raussendorf and Jim Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Physical review letters, 98 (19): 190504, 2007. https:/​/​​10.1103/​PhysRevLett.98.190504.

[43] Robert Raussendorf, Sergey Bravyi, and Jim Harrington. Long-range quantum entanglement in noisy cluster states. Phys. Rev. A, 71: 062313, Jun 2005. https:/​/​​10.1103/​PhysRevA.71.062313. URL https:/​/​​10.1103/​PhysRevA.71.062313.

[44] Robert Raussendorf, Jim Harrington, and Kovid Goyal. A fault-tolerant one-way quantum computer. Annals of physics, 321 (9): 2242–2270, 2006. https:/​/​​10.1016/​j.aop.2006.01.012.

[45] Robert Raussendorf, Jim Harrington, and Kovid Goyal. Topological fault-tolerance in cluster state quantum computation. New Journal of Physics, 9 (6): 199, 2007. https:/​/​​10.1088/​1367-2630/​9/​6/​199.

[46] Ben W Reichardt. Postselection threshold against biased noise. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 420–428. IEEE, 2006. https:/​/​​10.1109/​FOCS.2006.64.

[47] Ben W Reichardt. Fault-tolerant quantum error correction for steane’s seven-qubit color code with few or no extra qubits. Quantum Science and Technology, 6 (1): 015007, 2020. https:/​/​​10.1088/​2058-9565/​abc6f4.

[48] Terry Rudolph. Why i am optimistic about the silicon-photonic route to quantum computing. APL photonics, 2 (3): 030901, 2017. https:/​/​​10.1063/​1.4976737.

[49] C Ryan-Anderson, NC Brown, MS Allman, B Arkin, G Asa-Attuah, C Baldwin, J Berg, JG Bohnet, S Braxton, N Burdick, et al. Implementing fault-tolerant entangling gates on the five-qubit code and the color code. arXiv preprint arXiv:2208.01863, 2022. https:/​/​​10.48550/​arXiv.2208.01863.

[50] Ciaran Ryan-Anderson, JG Bohnet, Kenny Lee, Daniel Gresh, Aaron Hankin, JP Gaebler, David Francois, Alexander Chernoguzov, Dominic Lucchetti, NC Brown, et al. Realization of real-time fault-tolerant quantum error correction. Physical Review X, 11 (4): 041058, 2021. https:/​/​​10.1103/​PhysRevX.11.041058.

[51] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994. https:/​/​​10.1109/​SFCS.1994.365700.

[52] Samuel C Smith, Benjamin J Brown, and Stephen D Bartlett. A local pre-decoder to reduce the bandwidth and latency of quantum error correction. arXiv preprint arXiv:2208.04660, 2022. https:/​/​​10.1103/​PhysRevApplied.19.034050.

[53] Federico Spedalieri. Latency in fault-tolerant quantum computing with local, two-dimensional architecture. jun 2007. https:/​/​​10.48660/​07060065. URL https:/​/​​07060065. PIRSA:07060065 see, https:/​/​

[54] Thomas M Stace. Loss tolerance in topological quantum codes. In International Conference on Quantum Information, page QTuC4. Optica Publishing Group, 2011. https:/​/​​10.1364/​ICQI.2011.QTuC4.

[55] Andrew M. Steane. Efficient fault-tolerant quantum computing. Nature, 399 (6732): 124–126, May 1999. ISSN 1476-4687. https:/​/​​10.1038/​20127.

[56] Andrew M. Steane and Ben Ibinson. Fault-tolerant logical gate networks for calderbank-shor-steane codes. Phys. Rev. A, 72: 052335, Nov 2005. https:/​/​​10.1103/​PhysRevA.72.052335.

[57] Ashley M Stephens, William J Munro, and Kae Nemoto. High-threshold topological quantum error correction against biased noise. Physical Review A, 88 (6): 060301, 2013. https:/​/​​10.1103/​PhysRevA.88.060301.

[58] Christophe Vuillot, Hamed Asasi, Yang Wang, Leonid P Pryadko, and Barbara M Terhal. Quantum error correction with the toric gottesman-kitaev-preskill code. Physical Review A, 99 (3): 032344, 2019. https:/​/​​10.1103/​PhysRevA.99.032344.

[59] Chenyang Wang, Jim Harrington, and John Preskill. Confinement-higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory. Annals of Physics, 303 (1): 31–58, jan 2003. 10.1016/​s0003-4916(02)00019-2. URL https:/​/​​10.1016.

[60] David S Wang, Austin G Fowler, and Lloyd CL Hollenberg. Surface code quantum computing with error rates over 1%. Physical Review A, 83 (2): 020302, 2011. https:/​/​​10.1103/​PhysRevA.83.020302.

[61] Yang Wang. Quantum error correction with the gkp code and concatenation with stabilizer codes. arXiv preprint arXiv:1908.00147, 2019. https:/​/​​10.48550/​arXiv.1908.00147.

[62] Fern HE Watson and Sean D Barrett. Logical error rate scaling of the toric code. New Journal of Physics, 16 (9): 093045, 2014. https:/​/​​10.1088/​1367-2630/​16/​9/​093045.

[63] Yue Wu, Shimon Kolkowitz, Shruti Puri, and Jeff D Thompson. Erasure conversion for fault-tolerant quantum computing in alkaline earth rydberg atom arrays. arXiv preprint arXiv:2201.03540, 2022. https:/​/​​10.1038/​s41467-022-32094-6.

[64] Hayata Yamasaki, Kosuke Fukui, Yuki Takeuchi, Seiichiro Tani, and Masato Koashi. Polylog-overhead highly fault-tolerant measurement-based quantum computation: all-gaussian implementation with gottesman-kitaev-preskill code. arXiv preprint arXiv:2006.05416, 2020. https:/​/​​10.48550/​arXiv.2006.05416.

Cited by

[1] Yunzhe Zheng and Keita Kanno, "Minimizing readout-induced noise for early fault-tolerant quantum computers", Physical Review Research 6 2, 023129 (2024).

[2] Thomas J. Bell, Love A. Pettersson, and Stefano Paesani, "Optimizing Graph Codes for Measurement-Based Loss Tolerance", PRX Quantum 4 2, 020328 (2023).

[3] Dimiter Ostrev, Davide Orsucci, Francisco Lázaro, and Balazs Matuz, "Classical product code constructions for quantum Calderbank-Shor-Steane codes", arXiv:2209.13474, (2022).

[4] Jintae Kim, Jung Hoon Han, and Isaac H. Kim, "Fault-tolerant Quantum Error Correction Using a Linear Array of Emitters", arXiv:2403.01376, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 03:24:39) and SAO/NASA ADS (last updated successfully 2024-06-22 03:24:40). The list may be incomplete as not all publishers provide suitable and complete citation data.