Towards local testability for quantum coding

Anthony Leverrier; Vivien Londe; Gilles Zémor

doi:10.22331/q-2022-02-24-661

Towards local testability for quantum coding

Anthony Leverrier¹, Vivien Londe², and Gilles Zémor³

¹Inria, France
²Microsoft, France
³Institut de Mathématiques de Bordeaux, UMR 5251, France

Published:	2022-02-24, volume 6, page 661
Eprint:	arXiv:1911.03069v4
Doi:	https://doi.org/10.22331/q-2022-02-24-661
Citation:	Quantum 6, 661 (2022).

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

Abstract

We introduce the hemicubic codes, a family of quantum codes obtained by associating qubits with the $p$-faces of the $n$-cube (for $n \gt p$) and stabilizer constraints with faces of dimension $(p\pm1)$. The quantum code obtained by identifying antipodal faces of the resulting complex encodes one logical qubit into $N = 2^{n-p-1} \tbinom{n}{p}$ physical qubits and displays local testability with a soundness of $\Omega(1/\log(N))$ beating the current state-of-the-art of $1/\log^{2}(N)$ 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$-cube by arbitrary linear classical codes of length $n$. 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$-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.

► BibTeX data

@article{Leverrier2022towardslocal,
  doi = {10.22331/q-2022-02-24-661},
  url = {https://doi.org/10.22331/q-2022-02-24-661},
  title = {Towards local testability for quantum coding},
  author = {Leverrier, Anthony and Londe, Vivien and Z{\'{e}}mor, Gilles},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {661},
  month = feb,
  year = {2022}
}

► References

[1] Dorit Aharonov and Lior Eldar. Quantum locally testable codes. SIAM Journal on Computing, 44 (5): 1230–1262, 2015. 10.1137/140975498.
https://doi.org/10.1137/140975498

[2] Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. ACM SIGACT news, 44 (2): 47–79, 2013. 10.1145/2491533.2491549.
https://doi.org/10.1145/2491533.2491549

[3] Benjamin Audoux. An application of Khovanov homology to quantum codes. Ann. Inst. Henri Poincaré Comb. Phys. Interact, 1: 185–223, 2014. 10.4171/AIHPD/6.
https://doi.org/10.4171/AIHPD/6

[4] Benjamin Audoux and Alain Couvreur. On tensor products of CSS codes. Annales de l’Institut Henri Poincaré D, 2019. 10.4171/AIHPD/71.
https://doi.org/10.4171/AIHPD/71

[5] 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–334, 2015. 10.1145/2746539.2746608.
https://doi.org/10.1145/2746539.2746608

[6] 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–3247, 2010. 10.1137/090779875.
https://doi.org/10.1137/090779875

[7] Cédric Bény 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.
https://doi.org/10.1103/PhysRevLett.104.120501

[8] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of computer and system sciences, 47 (3): 549–595, 1993. 10.1016/0022-0000(93)90044-W.
https://doi.org/10.1016/0022-0000(93)90044-W

[9] 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–490, 2019. 10.1145/3313276.3316384.
https://doi.org/10.1145/3313276.3316384

[10] 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–880. ACM, 2013. 10.1145/2488608.2488719.
https://doi.org/10.1145/2488608.2488719

[11] 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.
https://doi.org/10.1103/PhysRevLett.97.050401

[12] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54: 1098–1105, Aug 1996. 10.1103/PhysRevA.54.1098.
https://doi.org/10.1103/PhysRevA.54.1098

[13] Claude Crépeau, Daniel Gottesman, and Adam Smith. Approximate quantum error-correcting codes and secret sharing schemes. In Ronald Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, pages 285–301, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. 10.1007/11426639_17.
https://doi.org/10.1007/11426639_17

[14] Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54 (3): 12, 2007. 10.1145/1236457.1236459.
https://doi.org/10.1145/1236457.1236459

[15] Dominic Dotterrer. The (co) isoperimetric problem in (random) polyhedra. PhD thesis, University of Toronto, 2013.

[16] Dominic Dotterrer. The filling problem in the cube. Discrete & Computational Geometry, 55 (2): 249–262, 2016. 10.1007/s00454-015-9725-7.
https://doi.org/10.1007/s00454-015-9725-7

[17] 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–49:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021. 10.4230/LIPIcs.ITCS.2021.49.
https://doi.org/10.4230/LIPIcs.ITCS.2021.49

[18] 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–438. IEEE, 2017. 10.1109/FOCS.2017.46.
https://doi.org/10.1109/FOCS.2017.46

[19] S. Evra, T. Kaufman, and G. Zémor. 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–227, 2020. 10.1109/FOCS46700.2020.00029.
https://doi.org/10.1109/FOCS46700.2020.00029

[20] 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–534. ACM, 2018. 10.1145/3188745.3188886.
https://doi.org/10.1145/3188745.3188886

[21] 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–320, 2002.

[22] Oded Goldreich. Short Locally Testable Codes and Proofs: A Survey in Two Parts, pages 65–104. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. 10.1007/978-3-642-16367-8_6.
https://doi.org/10.1007/978-3-642-16367-8_6

[23] Daniel Gottesman. Stabilizer codes and quantum error correction. PhD thesis, California Institute of Technology, 1997.

[24] Matthew B Hastings. Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture. Quantum Information & Computation, 13 (5-6): 393–429, 2013.

[25] 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.
https://doi.org/10.4230/LIPIcs.ITCS.2017.25

[26] 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–1288. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450380539. 10.1145/3406325.3451005.
https://doi.org/10.1145/3406325.3451005

[27] 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–1329. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450380539. 10.1145/3406325.3451029.
https://doi.org/10.1145/3406325.3451029

[28] Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Isoperimetric inequalities for Ramanujan complexes and topological expanders. Geometric and Functional Analysis, 26 (1): 250–287, 2016. 10.1007/s00039-016-0362-y.
https://doi.org/10.1007/s00039-016-0362-y

[29] A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2–30, 2003. 10.1016/S0003-4916(02)00018-0.
https://doi.org/10.1016/S0003-4916(02)00018-0

[30] Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. Quantum expander codes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 810–824. IEEE, 2015. 10.1109/FOCS.2015.55.
https://doi.org/10.1109/FOCS.2015.55

[31] 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–742. IEEE, 2018. 10.1109/FOCS.2018.00075.
https://doi.org/10.1109/FOCS.2018.00075

[32] 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–Leibniz-Zentrum fuer Informatik, 2018. 10.4230/LIPIcs.ICALP.2018.91.
https://doi.org/10.4230/LIPIcs.ICALP.2018.91

[33] Pavel Panteleev and Gleb Kalachev. Quantum LDPC Codes with Almost Linear Minimum Distance. arXiv preprint arXiv:2012.04068, 2020 10.1109/TIT.2021.3119384.
https://doi.org/10.1109/TIT.2021.3119384
arXiv:2012.04068

[34] David Poulin. Stabilizer formalism for operator quantum error correction. Phys. Rev. Lett., 95: 230504, Dec 2005. 10.1103/PhysRevLett.95.230504.
https://doi.org/10.1103/PhysRevLett.95.230504

[35] Joseph J Rotman. An introduction to homological algebra. Springer Science & Business Media, 2008.

[36] A. M. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77: 793–797, Jul 1996a. 10.1103/PhysRevLett.77.793.
https://doi.org/10.1103/PhysRevLett.77.793

[37] Andrew Steane. Multiple-particle interference and quantum error correction. Proc. R. Soc. Lond. A, 452 (1954): 2551–2577, 1996b. 10.1098/rspa.1996.0136.
https://doi.org/10.1098/rspa.1996.0136

[38] Charles A Weibel. An introduction to homological algebra. Number 38. Cambridge University Press, 1995.

Cited by

[1] Lucas Berent, Lukas Burgholzer, and Robert Wille, Proceedings of the 28th Asia and South Pacific Design Automation Conference 709 (2023) ISBN:9781450397834.

[2] Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick, Proceedings of the 55th Annual ACM Symposium on Theory of Computing 905 (2023) ISBN:9781450399135.

[3] Anurag Anshu and Nikolas P. Breuckmann, "A construction of combinatorial NLTS", Journal of Mathematical Physics 63 12, 122201 (2022).

[4] Pavel Panteleev and Gleb Kalachev, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 375 (2022) ISBN:9781450392648.

[5] Pavel Panteleev and Gleb Kalachev, "Asymptotically Good Quantum and Locally Testable Classical LDPC Codes", arXiv:2111.03654, (2021).

[6] Nicolas Delfosse, Vivien Londe, and Michael Beverland, "Toward a Union-Find decoder for quantum LDPC codes", arXiv:2103.08049, (2021).

[7] Uriya A. First and Tali Kaufman, "On Good $2$-Query Locally Testable Codes from Sheaves on High Dimensional Expanders", arXiv:2208.01778, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-28 02:26:35) and SAO/NASA ADS (last updated successfully 2023-09-28 02:26:36). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.