Partial Syndrome Measurement For Hypergraph Product Codes

Republished By Plato

Followers: 0

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.

Abstract

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.

Featured image: Overview of the stacked model. After embedding a quantum code into the grid, each stabilizer generator has a parameter $gamma$ that denotes the radius of the ball containing the qubits in its support. Different embeddings can yield different distributions of $gamma$ over the set of generators. The distribution then informs a measurement schedule for the generators, where the larger generators are measured less frequently than the smaller ones.

Popular summary

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

@article{Berthusen2024partialsyndrome, doi = {10.22331/q-2024-05-14-1345}, url = {https://doi.org/10.22331/q-2024-05-14-1345}, title = {Partial {S}yndrome {M}easurement for {H}ypergraph {P}roduct {C}odes}, author = {Berthusen, Noah and Gottesman, Daniel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1345}, month = may, year = {2024} }

► 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.
https://doi.org/10.1145/258533.258579

[2] A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52 (6): 1191, 1997. 10.1070/RM1997v052n06ABEH002155.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.quant-ph/9811052
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.2109.14599
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.
https://doi.org/10.48550/arXiv.2404.17676
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.
https://doi.org/10.48550/arXiv.2302.04317
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.
https://doi.org/10.48550/arXiv.quant-ph/9705052
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.2210.15844
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.1810.03681
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.2303.15933
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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] Craig Gidney, Michael Newman, Peter Brooks, and Cody Jones, “Yoked surface codes”, arXiv:2312.04522, (2023).

[3] 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).

The above citations are from SAO/NASA ADS (last updated successfully 2024-05-15 00:47:39). 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-15 00:47:38).

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-05-14-1345/

Time Stamp: May 14, 2024

Time Stamp: Sep 26, 2023

Republished By Plato

1000 Quantum papers!

Combinatorial optimization solving by coherent Ising machines based on spiking neural networks

Entanglement catalysis for quantum states and noisy channels

A complete and operational resource theory of measurement sharpness

Preparing quantum many-body scar states on quantum computers

Quantized Nonlinear Transport with Ultracold Atoms

Thermal State Preparation via Rounding Promises

Stabilizer entropies and nonstabilizerness monotones

Impact of conditional modelling for a universal autoregressive quantum state

The quartic Blochnium: an anharmonic quasicharge superconducting qubit

Quantum error correction with fractal topological codes

About Us

Vertical Search & Ai

Platform

Stay Connected

Account