{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T02:24:50Z","timestamp":1784600690408,"version":"3.55.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T00:00:00Z","timestamp":1608163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["QuantERA project QCDA"],"award-info":[{"award-number":["QuantERA project QCDA"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>\n            The\n            <jats:italic>threshold theorem<\/jats:italic>\n            is a seminal result in the field of quantum computing asserting that arbitrarily long quantum computations can be performed on a\n            <jats:italic>faulty<\/jats:italic>\n            quantum computer provided that the noise level is below some constant threshold. This remarkable result comes at the price of increasing the number of qubits (quantum bits) by a large factor that scales polylogarithmically with the size of the quantum computation we wish to realize. Minimizing the space overhead for fault-tolerant quantum computation is a pressing challenge that is crucial to benefit from the computational potential of quantum devices.\n          <\/jats:p>\n          <jats:p>In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation. We show that the polylogarithmic factor in the standard threshold theorem is in fact not needed and that there is a fault-tolerant construction that uses a number of qubits that is only a constant factor more than the number of qubits of the ideal computation. This result was conjectured by Gottesman who suggested to replace the concatenated codes from the standard threshold theorem by quantum error-correcting codes with a constant encoding rate. The main challenge was then to find an appropriate family of quantum codes together with an efficient classical decoding algorithm working even with a noisy syndrome. The efficiency constraint is crucial here: bear in mind that qubits are inherently noisy and that faults keep accumulating during the decoding process. The role of the decoder is therefore to keep the number of errors under control during the whole computation.<\/jats:p>\n          <jats:p>\n            On a technical level, our main contribution is the analysis of the SMALL-SET-FLIP decoding algorithm applied to the family of\n            <jats:italic>quantum expander codes<\/jats:italic>\n            . We show that it can be parallelized to run in constant time while correcting sufficiently many errors on both the qubits and the syndrome to keep the error under control. These tools can be seen as a quantum generalization of the BIT-FLIP algorithm applied to the (classical) expander codes of Sipser and Spielman.\n          <\/jats:p>","DOI":"10.1145\/3434163","type":"journal-article","created":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T23:39:35Z","timestamp":1608248375000},"page":"106-114","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Constant overhead quantum fault tolerance with quantum expander codes"],"prefix":"10.1145","volume":"64","author":[{"given":"Omar","family":"Fawzi","sequence":"first","affiliation":[{"name":"UCBL, LIP Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antoine","family":"Grospellier","sequence":"additional","affiliation":[{"name":"Inria, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anthony","family":"Leverrier","sequence":"additional","affiliation":[{"name":"Inria, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,12,17]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"38","article-title":"Fault-tolerant quantum computation with constant error rate","volume":"4","author":"Aharonov D.","year":"2008","unstructured":"Aharonov , D. , Ben-Or , M . Fault-tolerant quantum computation with constant error rate . SIAM J. Comput 4 , 38 ( 2008 ), 1207--1282. Aharonov, D., Ben-Or, M. Fault-tolerant quantum computation with constant error rate. SIAM J. Comput 4, 38 (2008), 1207--1282.","journal-title":"SIAM J. Comput"},{"key":"e_1_2_1_2_1","first-page":"5","article-title":"Single-shot fault-tolerant quantum error correction","volume":"3","author":"Bomb\u00edn H","year":"2015","unstructured":"Bomb\u00edn , H . Single-shot fault-tolerant quantum error correction . Phys. Rev. X 3 , 5 ( 2015 ), 031043. Bomb\u00edn, H. Single-shot fault-tolerant quantum error correction. Phys. Rev. X 3, 5 (2015), 031043.","journal-title":"Phys. Rev. X"},{"key":"e_1_2_1_3_1","first-page":"54","article-title":"Good quantum error-correcting codes exist","volume":"2","author":"Calderbank A.R.","year":"1996","unstructured":"Calderbank , A.R. , Shor , P.W . Good quantum error-correcting codes exist . Phys. Rev. A 2 , 54 ( 1996 ), 1098. Calderbank, A.R., Shor, P.W. Good quantum error-correcting codes exist. Phys. Rev. A 2, 54 (1996), 1098.","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00076"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188886"},{"key":"e_1_2_1_6_1","first-page":"86","article-title":"Towards practical large-scale quantum computation","volume":"3","author":"Fowler A.G.","year":"2012","unstructured":"Fowler , A.G. , Mariantoni , M. , Martinis , J.M. , Cleland , A.N. Surface codes : Towards practical large-scale quantum computation . Phys. Rev. A 3 , 86 ( 2012 ), 032324. Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A 3, 86 (2012), 032324.","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_7_1","first-page":"320","article-title":"freedom and quantum codes","volume":"287","author":"Freedman M.H.","year":"2002","unstructured":"Freedman , M.H. , Meyer , D.A. , Luo , F. Z2-systolic freedom and quantum codes . Mathematics of Quantum Computation. Chapman & Hall\/CRC , 2002 , 287 -- 320 . Freedman, M.H., Meyer, D.A., Luo, F. Z2-systolic freedom and quantum codes. Mathematics of Quantum Computation. Chapman & Hall\/CRC, 2002, 287--320.","journal-title":"Mathematics of Quantum Computation. Chapman & Hall\/CRC"},{"key":"e_1_2_1_8_1","first-page":"8","article-title":"Low-density parity-check codes","volume":"1","author":"Gallager R","year":"1962","unstructured":"Gallager , R . Low-density parity-check codes . IRE Trans. Inform. Theor. 1 , 8 ( 1962 ), 21--28. Gallager, R. Low-density parity-check codes. IRE Trans. Inform. Theor. 1, 8 (1962), 21--28.","journal-title":"IRE Trans. Inform. Theor."},{"key":"e_1_2_1_9_1","volume-title":"How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. arXiv preprint arXiv:1905.09749","author":"Gidney C.","year":"2019","unstructured":"Gidney , C. , Eker\u00e5 , M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. arXiv preprint arXiv:1905.09749 ( 2019 ). Gidney, C., Eker\u00e5, M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. arXiv preprint arXiv:1905.09749 (2019)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2685179.2685184"},{"key":"e_1_2_1_13_1","volume-title":"Combining hard and soft decoding for hypergraph product codes. arXiv preprint arXiv:2004.11199","author":"Grou\u00e8s L.","year":"2020","unstructured":"Grou\u00e8s , L. , Grospellier , A. , Krishna , A. , Leverrier , A. Combining hard and soft decoding for hypergraph product codes. arXiv preprint arXiv:2004.11199 ( 2020 ). Grou\u00e8s, L., Grospellier, A., Krishna, A., Leverrier, A. Combining hard and soft decoding for hypergraph product codes. arXiv preprint arXiv:2004.11199 (2020)."},{"key":"e_1_2_1_14_1","first-page":"87","article-title":"Fault tolerance of quantum low-density parity check codes with sublinear distance scaling","volume":"2","author":"Kovalev A.A.","year":"2013","unstructured":"Kovalev , A.A. , Pryadko , L.P . Fault tolerance of quantum low-density parity check codes with sublinear distance scaling . Phys. Rev. A 2 , 87 ( 2013 ), 020304. Kovalev, A.A., Pryadko, L.P. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Phys. Rev. A 2, 87 (2013), 020304.","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.55"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.41"},{"key":"e_1_2_1_17_1","first-page":"37","article-title":"On a lower bound for the redundancy of reliable networks with noisy gates","volume":"3","author":"Pippenger N.","year":"1991","unstructured":"Pippenger , N. , Stamoulis , G.D. , Tsitsiklis , J.N . On a lower bound for the redundancy of reliable networks with noisy gates . IEEE Trans. Inform. Theory 3 , 37 ( 1991 ), 639--643. Pippenger, N., Stamoulis, G.D., Tsitsiklis, J.N. On a lower bound for the redundancy of reliable networks with noisy gates. IEEE Trans. Inform. Theory 3, 37 (1991), 639--643.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"e_1_2_1_18_1","first-page":"27","article-title":"A mathematical theory of communication","volume":"3","author":"Shannon C.E","year":"1948","unstructured":"Shannon , C.E . A mathematical theory of communication . Bell Syst. Tech. J. 3 , 27 ( 1948 ), 379--423. Shannon, C.E. A mathematical theory of communication. Bell Syst. Tech. J. 3, 27 (1948), 379--423.","journal-title":"Bell Syst. Tech. J."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_20_1","first-page":"52","article-title":"Scheme for reducing decoherence in quantum computer memory","volume":"4","author":"Shor P.W","year":"1995","unstructured":"Shor , P.W . Scheme for reducing decoherence in quantum computer memory . Phys. Rev. A 4 , 52 ( 1995 ), R2493. Shor, P.W. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A 4, 52 (1995), R2493.","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548464"},{"key":"e_1_2_1_22_1","first-page":"42","article-title":"Expander codes","volume":"6","author":"Sipser M.","year":"1996","unstructured":"Sipser , M. , Spielman , D.A . Expander codes . IEEE Trans. Inform. Theory 6 , 42 ( 1996 ), 1710--1722. Sipser, M., Spielman, D.A. Expander codes. IEEE Trans. Inform. Theory 6, 42 (1996), 1710--1722.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"e_1_2_1_23_1","first-page":"77","article-title":"Error correcting codes in quantum theory","volume":"5","author":"Steane A.M","year":"1996","unstructured":"Steane , A.M . Error correcting codes in quantum theory . Phys. Rev. Lett. 5 , 77 ( 1996 ), 793. Steane, A.M. Error correcting codes in quantum theory. Phys. Rev. Lett. 5, 77 (1996), 793.","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_24_1","first-page":"60","article-title":"Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength","volume":"2","author":"Tillich J.-P.","year":"2014","unstructured":"Tillich , J.-P. , Z\u00e9mor , G . Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength . IEEE Trans. Inform. Theory 2 , 60 ( 2014 ), 1193--1202. Tillich, J.-P., Z\u00e9mor, G. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Trans. Inform. Theory 2, 60 (2014), 1193--1202.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"e_1_2_1_25_1","first-page":"43","article-title":"Probabilistic logics and the synthesis of reliable organisms from unreliable components","volume":"34","author":"Von Neumann J","year":"1956","unstructured":"Von Neumann , J . Probabilistic logics and the synthesis of reliable organisms from unreliable components . Autom. Stud. , 34 ( 1956 ), 43 -- 98 . Von Neumann, J. Probabilistic logics and the synthesis of reliable organisms from unreliable components. Autom. Stud., 34 (1956), 43--98.","journal-title":"Autom. Stud."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434163","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:34Z","timestamp":1750195474000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,17]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1145\/3434163"],"URL":"https:\/\/doi.org\/10.1145\/3434163","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,17]]},"assertion":[{"value":"2020-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}