{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T05:28:03Z","timestamp":1732166883277,"version":"3.28.0"},"reference-count":29,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T00:00:00Z","timestamp":1730073600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF STAQ project","award":["PHY-1818914"],"award-info":[{"award-number":["PHY-1818914"]}]},{"name":"NSF STAQ project","award":["PHY-2325080"],"award-info":[{"award-number":["PHY-2325080"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mi><\/mml:math> and Z<\/mml:mi><\/mml:math> noise.<\/jats:p>","DOI":"10.22331\/q-2024-10-28-1511","type":"journal-article","created":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T16:20:51Z","timestamp":1730132451000},"page":"1511","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Hardness results for decoding the surface code with Pauli noise"],"prefix":"10.22331","volume":"8","author":[{"given":"Alex","family":"Fischer","sequence":"first","affiliation":[{"name":"Department of Physics and Astronomy, Center for Quantum Information and Control, University of New Mexico, Albuquerque, New Mexico 87106, USA"}]},{"given":"Akimasa","family":"Miyake","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy, Center for Quantum Information and Control, University of New Mexico, Albuquerque, New Mexico 87106, USA"}]}],"member":"9598","published-online":{"date-parts":[[2024,10,28]]},"reference":[{"key":"0","unstructured":"Sergey B Bravyi and A Yu Kitaev. ``Quantum codes on a lattice with boundary'' (1998). arXiv:quant-ph\/9811052."},{"key":"1","doi-asserted-by":"publisher","unstructured":"Joe O\u2019Gorman, Naomi H Nickerson, Philipp Ross, John JL Morton, and Simon C Benjamin. ``A silicon-based surface code quantum computer''. npj Quantum Information 2, 1\u201314 (2016). arXiv:1406.5149.","DOI":"10.1038\/npjqi.2015.19"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1126\/sciadv.1500707"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41534-016-0004-0"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u2013674 (2022). arXiv:2112.03708.","DOI":"10.1038\/s41586-022-04566-8"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.129.030501"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Google Quantum AI. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676\u2013681 (2023). arXiv:2207.06431.","DOI":"10.1038\/s41586-022-05434-1"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Craig Gidney and Martin Eker\u00e5. ``How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits''. Quantum 5, 433 (2021). arXiv:1905.09749.","DOI":"10.22331\/q-2021-04-15-433"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452\u20134505 (2002). arXiv:quant-ph\/0110143.","DOI":"10.1063\/1.1499754"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.90.032326"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Antonio deMarti iOlius, Patricio Fuentes, Rom\u00e1n Or\u00fas, Pedro M. Crespo, and Josu Etxezarreta Martinez. ``Decoding algorithms for surface codes'' (2023). arXiv:2307.14989.","DOI":"10.22331\/q-2024-10-10-1498"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Min-Hsiu Hsieh and Fran\u00e7ois Le Gall. ``Np-hardness of decoding quantum error-correction codes''. Physical Review A 83, 052331 (2011). arXiv:1009.1319.","DOI":"10.1103\/PhysRevA.83.052331"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. ``On the inherent intractability of certain coding problems (corresp.)''. IEEE Transactions on Information Theory 24, 384\u2013386 (1978).","DOI":"10.1109\/TIT.1978.1055873"},{"key":"14","unstructured":"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\u2013211. IEEE (2012). arXiv:1306.5173."},{"key":"15","doi-asserted-by":"publisher","unstructured":"Kao-Yueh Kuo and Chung-Chin Lu. ``On the hardnesses of several quantum decoding problems''. Quantum Information Processing 19, 1\u201317 (2020). arXiv:1306.5173.","DOI":"10.1007\/s11128-020-02622-8"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Pavithran Iyer and David Poulin. ``Hardness of decoding quantum stabilizer codes''. IEEE Transactions on Information Theory 61, 5209\u20135223 (2015). arXiv:1310.3235.","DOI":"10.1109\/TIT.2015.2422294"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.106.062428"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2023-09-26-1123"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Mark Jerrum and Alistair Sinclair. ``Polynomial-time approximation algorithms for the ising model''. SIAM Journal on computing 22, 1087\u20131116 (1993).","DOI":"10.1137\/0222066"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Francisco Barahona. ``On the computational complexity of ising spin glass models''. Journal of Physics A: Mathematical and General 15, 3241 (1982).","DOI":"10.1088\/0305-4470\/15\/10\/028"},{"key":"21","doi-asserted-by":"publisher","unstructured":"H\u00e9ctor 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.","DOI":"10.1103\/PhysRevX.2.021004"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Christopher T Chubb and Steven T Flammia. ``Statistical mechanical models for quantum codes with correlated noise''. Annales de l\u2019Institut Henri Poincar\u00e9 D 8, 269\u2013321 (2021). arXiv:1809.10704.","DOI":"10.4171\/AIHPD\/105"},{"key":"23","doi-asserted-by":"publisher","unstructured":"H\u00e9ctor Bomb\u00edn 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.","DOI":"10.1103\/PhysRevA.76.012305"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Stephen A. Cook. ``The complexity of theorem-proving procedures''. In Proceedings of the Third Annual ACM Symposium on Theory of Computing. Page 151\u2013158. STOC '71New York, NY, USA (1971). Association for Computing Machinery.","DOI":"10.1145\/800157.805047"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Leslie G Valiant. ``The complexity of computing the permanent''. Theoretical computer science 8, 189\u2013201 (1979).","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Dan Roth. ``On the hardness of approximate reasoning''. Artificial Intelligence 82, 273\u2013302 (1996).","DOI":"10.1016\/0004-3702(94)00092-1"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Boaz Barak. ``Computational complexity: a modern approach''. Cambridge University Press. (2009).","DOI":"10.1017\/CBO9780511804090"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevX.13.031007"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-10-28-1511\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T12:13:22Z","timestamp":1732104802000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-10-28-1511\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,28]]},"references-count":29,"URL":"https:\/\/doi.org\/10.22331\/q-2024-10-28-1511","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2024,10,28]]},"article-number":"1511"}}