Partial Syndrome Measurement for Hypergraph Product Codes

Noah Berthusen and Daniel Gottesman

Joint Center for Quantum Information and Computer Science, NIST/University of Maryland, College Park, Maryland 20742, USA

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


Hypergraph product codes are a promising avenue to achieving fault-tolerant quantum computation with constant overhead. When embedding these and other constant-rate qLDPC codes into 2D, a significant number of nonlocal connections are required, posing difficulties for some quantum computing architectures. In this work, we introduce a fault-tolerance scheme that aims to alleviate the effects of implementing this nonlocality by measuring generators acting on spatially distant qubits less frequently than those which do not. We investigate the performance of a simplified version of this scheme, where the measured generators are randomly selected. When applied to hypergraph product codes and a modified small-set-flip decoding algorithm, we prove that for a sufficiently high percentage of generators being measured, a threshold still exists. We also find numerical evidence that the logical error rate is exponentially suppressed even when a large constant fraction of generators are not measured.

The surface code, despite showing theoretical and experimental promise, is a poor choice for large-scale quantum computations due to its unfavorable asymptotic scaling. Quantum low-density parity-check (qLDPC) codes have been introduced as performant alternatives; however, they are more difficult to implement on hardware. In this paper, we propose a method that aims to lessen the difficulty of implementing these qLDPC codes on quantum architectures that do not have access to long-range gates. This is done by measuring the generators whose qubits are far apart less frequently than those whose qubits are close together. We provide analytical and numerical evidence that shows quantum expander codes still perform well under a related toy model.

► BibTeX data

► References

[1] D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, page 176–188. Association for Computing Machinery, 1997. 10.1145/​258533.258579.

[2] A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52 (6): 1191, 1997. 10.1070/​RM1997v052n06ABEH002155.

[3] Emanuel Knill, Raymond Laflamme, and Wojciech H. Zurek. Resilient quantum computation: Error models and thresholds. Proc. R. Soc. Lond. A., 454 (1969): 365–384, 1998. 10.1098/​rspa.1998.0166.

[4] Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Info. Comput., 14 (15-16): 1338–1372, 2014. 10.26421/​QIC14.15-16-5.

[5] Nikolas P. Breuckmann and Jens N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, 67 (10): 6653–6674, 2021. 10.1109/​TIT.2021.3097347.

[6] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, page 375–388, 2022. 10.1145/​3519935.3520017.

[7] A. Leverrier and G. Zemor. Quantum tanner codes. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, pages 872–883. IEEE Computer Society, 2022. 10.1109/​FOCS54457.2022.00117.

[8] Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick. Good quantum LDPC codes with linear time decoders. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, page 905–918, 2023. 10.1145/​3564246.3585101.

[9] S. B. Bravyi and A. Yu. Kitaev. Quantum codes on a lattice with boundary. arXiv preprint arXiv:quant-ph/​9811052, 1998. 10.48550/​arXiv.quant-ph/​9811052.

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

[11] Jean-Pierre Tillich and Gilles Zémor. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60 (2): 1193–1202, 2014. 10.1109/​TIT.2013.2292061.

[12] Sergey Bravyi and Barbara Terhal. A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes. New Journal of Physics, 11 (4): 043029, 2009. 10.1088/​1367-2630/​11/​4/​043029.

[13] Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeoffs for reliable quantum information storage in 2D systems. Phys. Rev. Lett., 104: 050503, Feb 2010. 10.1103/​PhysRevLett.104.050503.

[14] Nouédyn Baspin and Anirudh Krishna. Quantifying nonlocality: How outperforming local quantum codes is expensive. Phys. Rev. Lett., 129: 050505, Jul 2022a. 10.1103/​PhysRevLett.129.050505.

[15] Nouédyn Baspin and Anirudh Krishna. Connectivity constrains quantum codes. Quantum, 6: 711, 2022b. 10.22331/​q-2022-05-13-711.

[16] Nicolas Delfosse, Michael E. Beverland, and Maxime A. Tremblay. Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes. arXiv preprint arXiv:2109.14599, 2021. 10.48550/​arXiv.2109.14599.

[17] Noah Berthusen, Dhruv Devulapalli, Eddie Schoute, Andrew M. Childs, Michael J. Gullans, Alexey V. Gorshkov, and Daniel Gottesman. Toward a 2D local implementation of quantum LDPC codes. arXiv preprint arXiv:2404.17676, 2024. 10.48550/​arXiv.2404.17676.

[18] Nouédyn Baspin, Omar Fawzi, and Ala Shayeghi. A lower bound on the overhead of quantum error correction in low dimensions. arXiv preprint arXiv:2302.04317, 2023. 10.48550/​arXiv.2302.04317.

[19] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv preprint arXiv:quant-ph/​9705052, 1997. 10.48550/​arXiv.quant-ph/​9705052.

[20] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane. Quantum error correction and orthogonal geometry. Phys. Rev. Lett., 78: 405–408, 1997. 10.1103/​PhysRevLett.78.405.

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

[22] M. Sipser and D.A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42 (6): 1710–1722, 1996. 10.1109/​18.556667.

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

[24] 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, page 521–534, 2018. 10.1145/​3188745.3188886.

[25] Daniel Gottesman. Opportunities and challenges in fault-tolerant quantum computation. arXiv preprint arXiv:2210.15844, 2022. 10.48550/​arXiv.2210.15844.

[26] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault tolerance with quantum expander codes. Commun. ACM, 64 (1): 106–114, 2020. 10.1145/​3434163.

[27] Antoine Grospellier. Constant time decoding of quantum expander codes and application to fault-tolerant quantum computation. PhD Thesis, 2019. Sorbonne Université.

[28] Alexey A. Kovalev, Sanjay Prabhakar, Ilya Dumer, and Leonid P. Pryadko. Numerical and analytical bounds on threshold error rates for hypergraph-product codes. Phys. Rev. A, 97: 062320, 2018. 10.1103/​PhysRevA.97.062320.

[29] Antoine Grospellier and Anirudh Krishna. Numerical study of hypergraph product codes. arXiv preprint arXiv:1810.03681, 2019. 10.48550/​arXiv.1810.03681.

[30] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell. Decoding across the quantum low-density parity-check code landscape. Phys. Rev. Res., 2: 043423, Dec 2020. 10.1103/​PhysRevResearch.2.043423.

[31] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier. Combining hard and soft decoders for hypergraph product codes. Quantum, 5: 432, 2021. 10.22331/​q-2021-04-15-432.

[32] Zijun Chen et al. Exponential suppression of bit or phase errors with cyclic error correction. Nature, 595 (78677867): 383–387, 2021. 10.1038/​s41586-021-03588-y.

[33] Nikolas P. Breuckmann and Barbara M. Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE Transactions on Information Theory, 62 (6): 3731–3744, 2016. 10.1109/​TIT.2016.2555700.

[34] Oscar Higgott and Craig Gidney. Sparse blossom: correcting a million errors per core second with minimum-weight matching. arXiv preprint arXiv:2303.15933, 2023. 10.48550/​arXiv.2303.15933.

[35] Héctor Bombín. Single-shot fault-tolerant quantum error correction. Phys. Rev. X, 5: 031043, 2015. 10.1103/​PhysRevX.5.031043.

[36] Earl T Campbell. A theory of single-shot error correction for adversarial noise. Quantum Science and Technology, 4 (2): 025006, 2019. 10.1088/​2058-9565/​aafc8f.

[37] Larry Guth and Alexander Lubotzky. Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds. J. Math. Phys., 55 (8), 2014. ISSN 0022-2488. 10.1063/​1.4891487.

[38] Matthew B. Hastings. Decoding in hyperbolic spaces: quantum LDPC codes with linear rate and efficient error correction. Quantum Info. Comput., 14 (13–14): 1187–1202, 2014. 10.48550/​arXiv.1312.2546.

[39] Nikolas P. Breuckmann and Vivien Londe. Single-shot decoding of linear rate LDPC quantum codes with high performance. IEEE Trans. Inf. Theory, 68 (1): 272–286, 2022. 10.1109/​TIT.2021.3122352.

[40] Alexey A. Kovalev and Leonid P. Pryadko. Quantum kronecker sum-product low-density parity-check codes with finite rate. Phys. Rev. A, 88: 012311, 2013. 10.1103/​PhysRevA.88.012311.

[41] Sergey Bravyi, Andrew W. Cross, Jay M. Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J. Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature, 627: 778–782, 2024. 10.1038/​s41586-024-07107-7.

[42] Charles H. Bennett, Gilles Brassard, Sandu Popescu, Benjamin Schumacher, John A. Smolin, and William K. Wootters. Purification of noisy entanglement and faithful teleportation via noisy channels. Phys. Rev. Lett., 76: 722–725, 1996a. 10.1103/​PhysRevLett.76.722.

[43] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. Mixed-state entanglement and quantum error correction. Phys. Rev. A, 54: 3824–3851, 1996b. 10.1103/​PhysRevA.54.3824.

[44] Pavel Panteleev and Gleb Kalachev. Degenerate quantum LDPC codes with good finite length performance. Quantum, 5: 585, 2021. 10.22331/​q-2021-11-22-585.

Cited by

[1] Yifan Hong, Matteo Marinelli, Adam M. Kaufman, and Andrew Lucas, "Long-range-enhanced surface codes", arXiv:2309.11719, (2023).

[2] Noah Berthusen, Dhruv Devulapalli, Eddie Schoute, Andrew M. Childs, Michael J. Gullans, Alexey V. Gorshkov, and Daniel Gottesman, "Toward a 2D Local Implementation of Quantum LDPC Codes", arXiv:2404.17676, (2024).

[3] Craig Gidney, Michael Newman, Peter Brooks, and Cody Jones, "Yoked surface codes", arXiv:2312.04522, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2024-05-26 13:23:09). 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 2024-05-26 13:23:07).