{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:19:05Z","timestamp":1767860345510,"version":"3.49.0"},"reference-count":38,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/anr","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["QCDA"],"award-info":[{"award-number":["QCDA"]}],"id":[{"id":"10.13039\/anr","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We introduce the hemicubic codes, a family of quantum codes obtained by associating qubits with the p<\/mml:mi><\/mml:math>-faces of the n<\/mml:mi><\/mml:math>-cube (for n<\/mml:mi>&#x003E;<\/mml:mo>p<\/mml:mi><\/mml:math>) and stabilizer constraints with faces of dimension (<\/mml:mo>p<\/mml:mi>&#x00B1;<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:math>. The quantum code obtained by identifying antipodal faces of the resulting complex encodes one logical qubit into N<\/mml:mi>=<\/mml:mo>2<\/mml:mn>n<\/mml:mi>&#x2212;<\/mml:mo>p<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>(<\/mml:mo><\/mml:mrow>n<\/mml:mi>p<\/mml:mi><\/mml:mfrac>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:mstyle><\/mml:math> physical qubits and displays local testability with a soundness of &#x03A9;<\/mml:mi>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>N<\/mml:mi>)<\/mml:mo>)<\/mml:mo><\/mml:math> beating the current state-of-the-art of 1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>log<\/mml:mi>2<\/mml:mn><\/mml:mrow><\/mml:msup>&#x2061;<\/mml:mo>(<\/mml:mo>N<\/mml:mi>)<\/mml:mo><\/mml:math> due to Hastings. We exploit this local testability to devise an efficient decoding algorithm that corrects arbitrary errors of size less than the minimum distance, up to polylog factors.We then extend this code family by considering the quotient of the n<\/mml:mi><\/mml:math>-cube by arbitrary linear classical codes of length n<\/mml:mi><\/mml:math>. We establish the parameters of these generalized hemicubic codes. Interestingly, if the soundness of the hemicubic code could be shown to be constant, similarly to the ordinary n<\/mml:mi><\/mml:math>-cube, then the generalized hemicubic codes could yield quantum locally testable codes of length not exceeding an exponential or even polynomial function of the code dimension.<\/jats:p>","DOI":"10.22331\/q-2022-02-24-661","type":"journal-article","created":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T19:54:29Z","timestamp":1645732469000},"page":"661","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":13,"title":["Towards local testability for quantum coding"],"prefix":"10.22331","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6707-1458","authenticated-orcid":false,"given":"Anthony","family":"Leverrier","sequence":"first","affiliation":[{"name":"Inria, France"}]},{"given":"Vivien","family":"Londe","sequence":"additional","affiliation":[{"name":"Microsoft, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6041-9554","authenticated-orcid":false,"given":"Gilles","family":"Z\u00e9mor","sequence":"additional","affiliation":[{"name":"Institut de Math\u00e9matiques de Bordeaux, UMR 5251, France"}]}],"member":"9598","published-online":{"date-parts":[[2022,2,24]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov and Lior Eldar. Quantum locally testable codes. SIAM Journal on Computing, 44 (5): 1230\u20131262, 2015. 10.1137\/140975498.","DOI":"10.1137\/140975498"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. ACM SIGACT news, 44 (2): 47\u201379, 2013. 10.1145\/2491533.2491549.","DOI":"10.1145\/2491533.2491549"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Benjamin Audoux. An application of Khovanov homology to quantum codes. Ann. Inst. Henri Poincar\u00e9 Comb. Phys. Interact, 1: 185\u2013223, 2014. 10.4171\/AIHPD\/6.","DOI":"10.4171\/AIHPD\/6"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Benjamin Audoux and Alain Couvreur. On tensor products of CSS codes. Annales de l\u2019Institut Henri Poincar\u00e9 D, 2019. 10.4171\/AIHPD\/71.","DOI":"10.4171\/AIHPD\/71"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Dave Bacon, Steven T Flammia, Aram W Harrow, and Jonathan Shi. Sparse quantum codes from quantum circuits. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 327\u2013334, 2015. 10.1145\/2746539.2746608.","DOI":"10.1145\/2746539.2746608"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, and Michael Viderman. Locally testable codes require redundant testers. SIAM Journal on Computing, 39 (7): 3230\u20133247, 2010. 10.1137\/090779875.","DOI":"10.1137\/090779875"},{"key":"6","doi-asserted-by":"publisher","unstructured":"C\u00e9dric B\u00e9ny and Ognyan Oreshkov. General conditions for approximate quantum error correction and near-optimal recovery channels. Phys. Rev. Lett., 104: 120501, Mar 2010. 10.1103\/PhysRevLett.104.120501.","DOI":"10.1103\/PhysRevLett.104.120501"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing\/correcting with applications to numerical problems. Journal of computer and system sciences, 47 (3): 549\u2013595, 1993. 10.1016\/0022-0000(93)90044-W.","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Thomas C Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen. Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 481\u2013490, 2019. 10.1145\/3313276.3316384.","DOI":"10.1145\/3313276.3316384"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Fernando GSL Brandao and Aram W Harrow. Product-state approximations to quantum ground states. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 871\u2013880. ACM, 2013. 10.1145\/2488608.2488719.","DOI":"10.1145\/2488608.2488719"},{"key":"10","doi-asserted-by":"publisher","unstructured":"S. Bravyi, M. B. Hastings, and F. Verstraete. Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order. Phys. Rev. Lett., 97: 050401, Jul 2006. 10.1103\/PhysRevLett.97.050401.","DOI":"10.1103\/PhysRevLett.97.050401"},{"key":"11","doi-asserted-by":"publisher","unstructured":"A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54: 1098\u20131105, Aug 1996. 10.1103\/PhysRevA.54.1098.","DOI":"10.1103\/PhysRevA.54.1098"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Claude Cr\u00e9peau, Daniel Gottesman, and Adam Smith. Approximate quantum error-correcting codes and secret sharing schemes. In Ronald Cramer, editor, Advances in Cryptology \u2013 EUROCRYPT 2005, pages 285\u2013301, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. 10.1007\/11426639_17.","DOI":"10.1007\/11426639_17"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54 (3): 12, 2007. 10.1145\/1236457.1236459.","DOI":"10.1145\/1236457.1236459"},{"key":"14","unstructured":"Dominic Dotterrer. The (co) isoperimetric problem in (random) polyhedra. PhD thesis, University of Toronto, 2013."},{"key":"15","doi-asserted-by":"publisher","unstructured":"Dominic Dotterrer. The filling problem in the cube. Discrete & Computational Geometry, 55 (2): 249\u2013262, 2016. 10.1007\/s00454-015-9725-7.","DOI":"10.1007\/s00454-015-9725-7"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Lior Eldar. Robust Quantum Entanglement at (Nearly) Room Temperature. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185, pages 49:1\u201349:20. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 2021. 10.4230\/LIPIcs.ITCS.2021.49.","DOI":"10.4230\/LIPIcs.ITCS.2021.49"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Lior Eldar and Aram W Harrow. Local Hamiltonians whose ground states are hard to approximate. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 427\u2013438. IEEE, 2017. 10.1109\/FOCS.2017.46.","DOI":"10.1109\/FOCS.2017.46"},{"key":"18","doi-asserted-by":"publisher","unstructured":"S. Evra, T. Kaufman, and G. Z\u00e9mor. Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 218\u2013227, 2020. 10.1109\/FOCS46700.2020.00029.","DOI":"10.1109\/FOCS46700.2020.00029"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Efficient decoding of random errors for quantum expander codes. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 521\u2013534. ACM, 2018. 10.1145\/3188745.3188886.","DOI":"10.1145\/3188745.3188886"},{"key":"20","doi-asserted-by":"crossref","unstructured":"Michael H Freedman, David A Meyer, and Feng Luo. $Z_2$-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall\/CRC, pages 287\u2013320, 2002.","DOI":"10.1201\/9781420035377.ch12"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Oded Goldreich. Short Locally Testable Codes and Proofs: A Survey in Two Parts, pages 65\u2013104. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. 10.1007\/978-3-642-16367-8_6.","DOI":"10.1007\/978-3-642-16367-8_6"},{"key":"22","unstructured":"Daniel Gottesman. Stabilizer codes and quantum error correction. PhD thesis, California Institute of Technology, 1997."},{"key":"23","doi-asserted-by":"crossref","unstructured":"Matthew B Hastings. Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture. Quantum Information & Computation, 13 (5-6): 393\u2013429, 2013.","DOI":"10.26421\/QIC13.5-6-3"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Matthew B Hastings. Quantum codes from high-dimensional manifolds. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. 10.4230\/LIPIcs.ITCS.2017.25.","DOI":"10.4230\/LIPIcs.ITCS.2017.25"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell. Fiber Bundle Codes: Breaking the $n^{1\/2} Polylog(n)$ Barrier for Quantum LDPC Codes, page 1276\u20131288. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450380539. 10.1145\/3406325.3451005.","DOI":"10.1145\/3406325.3451005"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Tali Kaufman and Ran J. Tessler. New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with $\\Omega(\\sqrt{n} \\log^k n)$ Distance, page 1317\u20131329. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450380539. 10.1145\/3406325.3451029.","DOI":"10.1145\/3406325.3451029"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Isoperimetric inequalities for Ramanujan complexes and topological expanders. Geometric and Functional Analysis, 26 (1): 250\u2013287, 2016. 10.1007\/s00039-016-0362-y.","DOI":"10.1007\/s00039-016-0362-y"},{"key":"28","doi-asserted-by":"publisher","unstructured":"A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2\u201330, 2003. 10.1016\/S0003-4916(02)00018-0.","DOI":"10.1016\/S0003-4916(02)00018-0"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Anthony Leverrier, Jean-Pierre Tillich, and Gilles Z\u00e9mor. Quantum expander codes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 810\u2013824. IEEE, 2015. 10.1109\/FOCS.2015.55.","DOI":"10.1109\/FOCS.2015.55"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 731\u2013742. IEEE, 2018. 10.1109\/FOCS.2018.00075.","DOI":"10.1109\/FOCS.2018.00075"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Chinmay Nirkhe, Umesh Vazirani, and Henry Yuen. Approximate low-weight check codes and circuit lower bounds for noisy ground states. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107, page 91. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2018. 10.4230\/LIPIcs.ICALP.2018.91.","DOI":"10.4230\/LIPIcs.ICALP.2018.91"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Pavel Panteleev and Gleb Kalachev. Quantum LDPC Codes with Almost Linear Minimum Distance. arXiv preprint arXiv:2012.04068, 2020 10.1109\/TIT.2021.3119384.","DOI":"10.1109\/TIT.2021.3119384"},{"key":"33","doi-asserted-by":"publisher","unstructured":"David Poulin. Stabilizer formalism for operator quantum error correction. Phys. Rev. Lett., 95: 230504, Dec 2005. 10.1103\/PhysRevLett.95.230504.","DOI":"10.1103\/PhysRevLett.95.230504"},{"key":"34","doi-asserted-by":"crossref","unstructured":"Joseph J Rotman. An introduction to homological algebra. Springer Science & Business Media, 2008.","DOI":"10.1007\/b98977"},{"key":"35","doi-asserted-by":"publisher","unstructured":"A. M. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77: 793\u2013797, Jul 1996a. 10.1103\/PhysRevLett.77.793.","DOI":"10.1103\/PhysRevLett.77.793"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Andrew Steane. Multiple-particle interference and quantum error correction. Proc. R. Soc. Lond. A, 452 (1954): 2551\u20132577, 1996b. 10.1098\/rspa.1996.0136.","DOI":"10.1098\/rspa.1996.0136"},{"key":"37","doi-asserted-by":"crossref","unstructured":"Charles A Weibel. An introduction to homological algebra. Number 38. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9781139644136"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-02-24-661\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T20:59:53Z","timestamp":1646859593000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-02-24-661\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":38,"URL":"https:\/\/doi.org\/10.22331\/q-2022-02-24-661","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,24]]},"article-number":"661"}}