Hardness results for decoding the surface code with Pauli noise
Department of Physics and Astronomy, Center for Quantum Information and Control, University of New Mexico, Albuquerque, New Mexico 87106, USA
| Published: | 2024-10-28, volume 8, page 1511 |
| Eprint: | arXiv:2309.10331v5 |
| Doi: | https://doi.org/10.22331/q-2024-10-28-1511 |
| Citation: | Quantum 8, 1511 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Real quantum computers will be subject to complicated, qubit-dependent noise, instead of simple noise such as depolarizing noise with the same strength for all qubits. We can do quantum error correction more effectively if our decoding algorithms take into account this prior information about the specific noise present. This motivates us to consider the complexity of surface code decoding where the input to the decoding problem is not only the syndrome-measurement results, but also a noise model in the form of probabilities of single-qubit Pauli errors for every qubit. In this setting, we show that quantum maximum likelihood decoding (QMLD) and degenerate quantum maximum likelihood decoding (DQMLD) for the surface code are NP-hard and #P-hard, respectively. We reduce directly from SAT for QMLD, and from #SAT for DQMLD, by showing how to transform a boolean formula into a qubit-dependent Pauli noise model and set of syndromes that encode the satisfiability properties of the formula. We also give hardness of approximation results for QMLD and DQMLD. These are worst-case hardness results that do not contradict the empirical fact that many efficient surface code decoders are correct in the average case (i.e., for most sets of syndromes and for most reasonable noise models). These hardness results are nicely analogous with the known hardness results for QMLD and DQMLD for arbitrary stabilizer codes with independent $X$ and $Z$ noise.
Featured image: Noise model and possible errors used in our reduction from circuit-SAT to surface code decoding.
Popular summary
Our work shows that various different formulations of the decoding problem for the surface code are computationally hard, in a rigorous sense. We do this by showing that surface code decoding problems can express other computationally hard problems. Our results require that the decoding problem be formulated such that the input to the problem includes a fine-grained description of possible errors that can occur. The practical impact of our work is not to discourage surface code use, but to show that practically useful decoding algorithms for the surface code cannot hope to solve the problem when the problem includes this fine-grained description of possible errors, else the problem would be too computationally hard. It tells us that we should focus research efforts for these algorithms on simpler cases that are not provably hard.
► BibTeX data
► References
[1] Sergey B Bravyi and A Yu Kitaev. ``Quantum codes on a lattice with boundary'' (1998). arXiv:quant-ph/9811052.
arXiv:quant-ph/9811052
[2] Joe O’Gorman, Naomi H Nickerson, Philipp Ross, John JL Morton, and Simon C Benjamin. ``A silicon-based surface code quantum computer''. npj Quantum Information 2, 1–14 (2016). arXiv:1406.5149.
https://doi.org/10.1038/npjqi.2015.19
arXiv:1406.5149
[3] Charles D Hill, Eldad Peretz, Samuel J Hile, Matthew G House, Martin Fuechsle, Sven Rogge, Michelle Y Simmons, and Lloyd CL Hollenberg. ``A surface code quantum computer in silicon''. Science advances 1, e1500707 (2015).
https://doi.org/10.1126/sciadv.1500707
[4] Jay M Gambetta, Jerry M Chow, and Matthias Steffen. ``Building logical qubits in a superconducting quantum computing system''. npj quantum information 3, 2 (2017). arXiv:1510.04375.
https://doi.org/10.1038/s41534-016-0004-0
arXiv:1510.04375
[5] Sebastian Krinner, Nathan Lacroix, Ants Remm, Agustin Di Paolo, Elie Genois, Catherine Leroux, Christoph Hellings, Stefania Lazar, Francois Swiadek, Johannes Herrmann, et al. ``Realizing repeated quantum error correction in a distance-three surface code''. Nature 605, 669–674 (2022). arXiv:2112.03708.
https://doi.org/10.1038/s41586-022-04566-8
arXiv:2112.03708
[6] Youwei Zhao, Yangsen Ye, He-Liang Huang, Yiming Zhang, Dachao Wu, Huijie Guan, Qingling Zhu, Zuolin Wei, Tan He, Sirui Cao, et al. ``Realization of an error-correcting surface code with superconducting qubits''. Physical Review Letters 129, 030501 (2022). arXiv:2112.13505.
https://doi.org/10.1103/PhysRevLett.129.030501
arXiv:2112.13505
[7] Google Quantum AI. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676–681 (2023). arXiv:2207.06431.
https://doi.org/10.1038/s41586-022-05434-1
arXiv:2207.06431
[8] Craig Gidney and Martin Ekerå. ``How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits''. Quantum 5, 433 (2021). arXiv:1905.09749.
https://doi.org/10.22331/q-2021-04-15-433
arXiv:1905.09749
[9] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Physical Review A 86, 032324 (2012). arXiv:1208.0928.
https://doi.org/10.1103/PhysRevA.86.032324
arXiv:1208.0928
[10] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452–4505 (2002). arXiv:quant-ph/0110143.
https://doi.org/10.1063/1.1499754
arXiv:quant-ph/0110143
[11] Sergey Bravyi, Martin Suchara, and Alexander Vargo. ``Efficient algorithms for maximum likelihood decoding in the surface code''. Physical Review A 90, 032326 (2014). arXiv:1405.4883.
https://doi.org/10.1103/PhysRevA.90.032326
arXiv:1405.4883
[12] Antonio deMarti iOlius, Patricio Fuentes, Román Orús, Pedro M. Crespo, and Josu Etxezarreta Martinez. ``Decoding algorithms for surface codes'' (2023). arXiv:2307.14989.
https://doi.org/10.22331/q-2024-10-10-1498
arXiv:2307.14989
[13] Min-Hsiu Hsieh and François Le Gall. ``Np-hardness of decoding quantum error-correction codes''. Physical Review A 83, 052331 (2011). arXiv:1009.1319.
https://doi.org/10.1103/PhysRevA.83.052331
arXiv:1009.1319
[14] Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. ``On the inherent intractability of certain coding problems (corresp.)''. IEEE Transactions on Information Theory 24, 384–386 (1978).
https://doi.org/10.1109/TIT.1978.1055873
[15] Kao-Yueh Kuo and Chung-Chin Lu. ``On the hardness of decoding quantum stabilizer codes under the depolarizing channel''. In 2012 International Symposium on Information Theory and its Applications. Pages 208–211. IEEE (2012). arXiv:1306.5173.
arXiv:1306.5173
[16] Kao-Yueh Kuo and Chung-Chin Lu. ``On the hardnesses of several quantum decoding problems''. Quantum Information Processing 19, 1–17 (2020). arXiv:1306.5173.
https://doi.org/10.1007/s11128-020-02622-8
arXiv:1306.5173
[17] Pavithran Iyer and David Poulin. ``Hardness of decoding quantum stabilizer codes''. IEEE Transactions on Information Theory 61, 5209–5223 (2015). arXiv:1310.3235.
https://doi.org/10.1109/TIT.2015.2422294
arXiv:1310.3235
[18] Antonio deMarti iOlius, Josu Etxezarreta Martinez, Patricio Fuentes, Pedro M. Crespo, and Javier Garcia-Frias. ``Performance of surface codes in realistic quantum hardware''. Phys. Rev. A 106, 062428 (2022). arXiv:2203.15695.
https://doi.org/10.1103/PhysRevA.106.062428
arXiv:2203.15695
[19] Konstantin Tiurev, Peter-Jan H. S. Derks, Joschka Roffe, Jens Eisert, and Jan-Michael Reiner. ``Correcting non-independent and non-identically distributed errors with surface codes''. Quantum 7, 1123 (2023). arXiv:2208.02191.
https://doi.org/10.22331/q-2023-09-26-1123
arXiv:2208.02191
[20] Mark Jerrum and Alistair Sinclair. ``Polynomial-time approximation algorithms for the ising model''. SIAM Journal on computing 22, 1087–1116 (1993).
https://doi.org/10.1137/0222066
[21] Francisco Barahona. ``On the computational complexity of ising spin glass models''. Journal of Physics A: Mathematical and General 15, 3241 (1982).
https://doi.org/10.1088/0305-4470/15/10/028
[22] Héctor Bombin, Ruben S Andrist, Masayuki Ohzeki, Helmut G Katzgraber, and Miguel A Martin-Delgado. ``Strong resilience of topological codes to depolarization''. Physical Review X 2, 021004 (2012). arXiv:1202.1852.
https://doi.org/10.1103/PhysRevX.2.021004
arXiv:1202.1852
[23] Christopher T Chubb and Steven T Flammia. ``Statistical mechanical models for quantum codes with correlated noise''. Annales de l’Institut Henri Poincaré D 8, 269–321 (2021). arXiv:1809.10704.
https://doi.org/10.4171/AIHPD/105
arXiv:1809.10704
[24] Héctor Bombín and Miguel A Martin-Delgado. ``Optimal resources for topological two-dimensional stabilizer codes: Comparative study''. Physical Review A 76, 012305 (2007). arXiv:quant-ph/0703272.
https://doi.org/10.1103/PhysRevA.76.012305
arXiv:quant-ph/0703272
[25] Stephen A. Cook. ``The complexity of theorem-proving procedures''. In Proceedings of the Third Annual ACM Symposium on Theory of Computing. Page 151–158. STOC '71New York, NY, USA (1971). Association for Computing Machinery.
https://doi.org/10.1145/800157.805047
[26] Leslie G Valiant. ``The complexity of computing the permanent''. Theoretical computer science 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[27] Dan Roth. ``On the hardness of approximate reasoning''. Artificial Intelligence 82, 273–302 (1996).
https://doi.org/10.1016/0004-3702(94)00092-1
[28] Sanjeev Arora and Boaz Barak. ``Computational complexity: a modern approach''. Cambridge University Press. (2009).
https://doi.org/10.1017/CBO9780511804090
[29] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell. ``Improved decoding of circuit noise and fragile boundaries of tailored surface codes''. Phys. Rev. X 13, 031007 (2023). arXiv:2203.04948.
https://doi.org/10.1103/PhysRevX.13.031007
arXiv:2203.04948
Cited by
[1] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).
[2] Abtin Molavi, Feras Saad, and Aws Albarghouthi, "Analyzing Decoders for Quantum Error Correction", arXiv:2603.20127, (2026).
The above citations are from SAO/NASA ADS (last updated successfully 2026-08-09 13:11:22). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-09 13:11:19).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.