Document Open Access Logo

Towards Local Testability for Quantum Coding

Authors Anthony Leverrier , Vivien Londe, Gilles Zémor

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.65.pdf
  • Filesize: 421 kB
  • 11 pages

Document Identifiers

Author Details

Anthony Leverrier
  • Inria, Paris, France
Vivien Londe
  • Microsoft, Issy-les-moulineaux, France
Gilles Zémor
  • Institut de Mathématiques de Bordeaux, UMR 5251, France

Funding

  • Leverrier, Anthony: Agence Nationale de la Recherche (ANR): QuantERA project QCDA.
  • Zémor, Gilles: Agence Nationale de la Recherche (ANR): ANR-18-CE47-0010 project QUDATA.

Acknowledgements

We would like to thank Benjamin Audoux, Alain Couvreur, Omar Fawzi, Antoine Grospellier and Jean-Pierre Tillich for many fruitful discussions on quantum codes.

Cite AsGet BibTex

Anthony Leverrier, Vivien Londe, and Gilles Zémor. Towards Local Testability for Quantum Coding. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 65:1-65:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.65

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 > p) and stabilizer constraints with faces of dimension (p ± 1). The quantum code obtained by identifying antipodal faces of the resulting complex encodes one logical qubit into N = 2^{n-p-1} binom(n,p) physical qubits and displays local testability with a soundness of Ω(1/log(N)) beating the current state-of-the-art of 1/log²(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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Quantum error correcting code

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. ACM SIGACT news, 44(2):47-79, 2013. Google Scholar
  2. Dorit Aharonov and Lior Eldar. Quantum locally testable codes. SIAM Journal on Computing, 44(5):1230-1262, 2015. Google Scholar
  3. Benjamin Audoux. An application of Khovanov homology to quantum codes. Ann. Inst. Henri Poincaré Comb. Phys. Interact, 1:185-223, 2014. Google Scholar
  4. 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. Google Scholar
  5. Cédric Bény and Ognyan Oreshkov. General conditions for approximate quantum error correction and near-optimal recovery channels. Physical review letters, 104(12):120501, 2010. Google Scholar
  6. 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. Google Scholar
  7. 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. Google Scholar
  8. 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. Google Scholar
  9. S Bravyi, MB Hastings, and F Verstraete. Lieb-robinson bounds and the generation of correlations and topological quantum order. Physical Review Letters, 97(5):050401, 2006. Google Scholar
  10. Claude Crépeau, Daniel Gottesman, and Adam Smith. Approximate quantum error-correcting codes and secret sharing schemes. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 285-301. Springer, 2005. Google Scholar
  11. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54(3):12, 2007. Google Scholar
  12. Dominic Dotterrer. The (co) isoperimetric problem in (random) polyhedra. PhD thesis, University of Toronto, 2013. Google Scholar
  13. Dominic Dotterrer. The filling problem in the cube. Discrete & Computational Geometry, 55(2):249-262, 2016. Google Scholar
  14. Lior Eldar. Robust quantum entanglement at (nearly) room temperature. manuscript, 2019. Google Scholar
  15. 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. Google Scholar
  16. Shai Evra, Tali Kaufman, and Gilles Zémor. Decodable quantum ldpc codes beyond the √n distance barrier using high dimensional expanders. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.07935.
  17. 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. Google Scholar
  18. Michael H Freedman, David A Meyer, and Feng Luo. Z2-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall/CRC, pages 287-320, 2002. Google Scholar
  19. Oded Goldreich. Short locally testable codes and proofs: A survey in two parts. In Property testing, pages 65-104. Springer, 2010. Google Scholar
  20. Matthew B Hastings. Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture. Quantum Information & Computation, 13(5-6):393-429, 2013. Google Scholar
  21. 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. Google Scholar
  22. Matthew B Hastings. Quantum codes from high-dimensional manifolds. In LIPIcs-Leibniz International Proceedings in Informatics, volume 67. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  23. Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Isoperimetric inequalities for ramanujan complexes and topological expanders. Geometric and Functional Analysis, 26(1):250-287, 2016. Google Scholar
  24. Tali Kaufman and Ran J Tessler. Quantum LDPC codes with Ω(√nlog^k n) distance, for any k. arXiv preprint, 2020. URL: http://arxiv.org/abs/2008.09495.
  25. A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2-30, 2003. Google Scholar
  26. Anthony Leverrier, Vivien Londe, and Gilles Zémor. Towards local testability for quantum coding. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.03069.
  27. 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. Google Scholar
  28. 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. Google Scholar
  29. 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. Google Scholar
  30. David Poulin. Stabilizer formalism for operator quantum error correction. Physical Review Letters, 95(23):230504, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact