More Web Proxy on the site http://driver.im/

research-article

Efficient decoding of random errors for quantum expander codes

Authors:

Antoine Grospellier,

Anthony LeverrierAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 521 - 534

https://doi.org/10.1145/3188745.3188886

Published: 20 June 2018 Publication History

Abstract

We show that quantum expander codes, a constant-rate family of quantum low-density parity check (LDPC) codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Zémor can correct a constant fraction of random errors with very high probability. This is the first construction of a constant-rate quantum LDPC code with an efficient decoding algorithm that can correct a linear number of random errors with a negligible failure probability. Finding codes with these properties is also motivated by Gottesman’s construction of fault tolerant schemes with constant space overhead.

In order to obtain this result, we study a notion of α-percolation: for a random subset E of vertices of a given graph, we consider the size of the largest connected α-subset of E, where X is an α-subset of E if |X ∩ E| ≥ α |X|.

Supplementary Material

MP4 File (4b-4.mp4)

Download
31.32 MB

References

[1]

Joan Adler. 1991. Bootstrap percolation. Physica A: Statistical Mechanics and its Applications 171, 3 (1991), 453–470.

[2]

Dorit Aharonov and Michael Ben-Or. 1997. Fault-tolerant quantum computation with constant error. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 176–188.

Digital Library

[3]

Sergey Bravyi and Barbara Terhal. 2009. A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes. New Journal of Physics 11, 4 (2009), 043029.

[4]

A Robert Calderbank and Peter W Shor. 1996. Good quantum error-correcting codes exist. Physical Review A 54, 2 (1996), 1098.

[5]

Nicolas Delfosse and Naomi H. Nickerson. 2017. Almost-linear time decoding algorithm for topological codes. arXiv preprint arXiv:1709.06218 (2017).

[6]

Nicolas Delfosse and Gilles Zémor. 2010.

[7]

Quantum erasure-correcting codes and percolation on regular tilings of the hyperbolic plane. In Information Theory Workshop (ITW), 2010 IEEE. IEEE, 1–5.

[8]

Nicolas Delfosse and Gilles Zémor. 2013.

[9]

Upper bounds on the Rate of Low Density Stabilizer Codes for the Quantum Erasure Channel. Quantum Information & Computation 13, 9&10 (2013), 0793–0826.

Digital Library

[10]

Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. 2002. Topological quantum memory. J. Math. Phys. 43, 9 (2002), 4452–4505.

[11]

Jack Edmonds. 1965. Maximum matching and a polyhedron with 0, 1-vertices. Journal of Research of the National Bureau of Standards B 69, 125-130 (1965), 55–56.

[12]

Michael H Freedman, David A Meyer, and Feng Luo. 2002. Z2-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall/CRC (2002), 287–320.

[13]

Robert Gallager. 1962.

[14]

Low-density parity-check codes. IRE Transactions on information theory 8, 1 (1962), 21–28.

[15]

Daniel Gottesman. 1997.

[16]

Stabilizer codes and quantum error correction. Ph.D. Dissertation. California Institute of Technology.

[17]

Daniel Gottesman. 2014.

[18]

Fault-tolerant quantum computation with constant overhead. Quantum Information & Computation 14, 15-16 (2014), 1338–1372.

Digital Library

[19]

Larry Guth and Alexander Lubotzky. 2014.

[20]

Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds. J. Math. Phys. 55, 8 (2014), 082202.

[21]

Matthew B Hastings. 2014.

[22]

Decoding in hyperbolic spaces: quantum LDPC codes with linear rate and efficient error correction. Quantum Information & Computation 14, 13-14 (2014), 1187–1202.

Digital Library

[23]

Svante Janson. 2009. On percolation in random graphs with given vertex degrees. Electronic Journal of Probability 14 (2009), 86–118.

[24]

Isaac Hyun Kim. 2007.

[25]

Quantum codes on Hurwitz surfaces. Ph.D. Dissertation. Massachusetts Institute of Technology.

[26]

A Yu Kitaev. 2003. Fault-tolerant quantum computation by anyons. Annals of Physics 303, 1 (2003), 2–30.

[27]

Alexey A Kovalev and Leonid P Pryadko. 2013.

[28]

Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Physical Review A 87, 2 (2013), 020304.

[29]

Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. 2015.

[30]

Quantum expander codes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on. IEEE, 810–824.

Digital Library

[31]

Vivien Londe and Anthony Leverrier. 2017.

[32]

Golden codes: quantum LDPC codes built from regular tessellations of hyperbolic 4-manifolds. arXiv preprint arXiv:1712.08578 (2017).

[33]

Russell Lyons. 1992.

[34]

Random walks, capacity and percolation on trees. The Annals of Probability (1992), 2043–2088.

[35]

Chin Hee Pah and Mohamed Ridza Wahiddin. 2015. Combinatorial Interpretation of Raney Numbers and Tree Enumerations. Open Journal of Discrete Mathematics 5, 01 (2015), 1.

[36]

Tom Richardson and Ruediger Urbanke. 2008.

[37]

Modern coding theory. Cambridge University Press.

Digital Library

[38]

Michael Sipser and Daniel A Spielman. 1996. Expander codes. IEEE Transactions on Information Theory 42, 6 (1996), 1710–1722.

Digital Library

[39]

Andrew M Steane. 1996.

[40]

Error correcting codes in quantum theory. Physical Review Letters 77, 5 (1996), 793.

[41]

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

Digital Library

[42]

Ryuhei Uehara et al. 1999. The number of connected components in graphs and its applications. Manuscript.

[43]

David S Wang, Austin G Fowler, Ashley M Stephens, and Lloyd Christopher L Hollenberg. 2009. Threshold error rates for the toric and surface codes. arXiv preprint arXiv:0905.0531 (2009).

Cited By

Berthusen NGottesman D(2024)Partial Syndrome Measurement for Hypergraph Product CodesQuantum10.22331/q-2024-05-14-13458(1345)Online publication date: 14-May-2024
https://doi.org/10.22331/q-2024-05-14-1345
Goto H(2024)High-performance fault-tolerant quantum computing with many-hypercube codesScience Advances10.1126/sciadv.adp638810:36Online publication date: 6-Sep-2024
https://doi.org/10.1126/sciadv.adp6388
Golowich LGuruswami V(2024)Decoding Quasi-Cyclic Quantum LDPC Codes2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00029(344-368)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00029
Show More Cited By

Index Terms

Efficient decoding of random errors for quantum expander codes
1. Hardware
  1. Emerging technologies
    1. Quantum technologies
      1. Quantum computation
        Quantum error correction and fault tolerance
2. Theory of computation
  1. Models of computation
    1. Quantum computation theory
      1. Quantum information theory

Recommendations

An Efficient Decoder for a Linear Distance Quantum LDPC Code
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time ...
Decoding of Expander Codes at Rates Close to Capacity

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding ...
Error Exponents of Expander Codes under Linear-Complexity Decoding

A class of codes is said to reach capacity {\scriptsize $Ç$} of the binary symmetric channel if for any rate $R<$ {\scriptsize $Ç$} and any $\varepsilon>0$ there is a sufficiently large N such that codes of length $\ge N$ and rate R from this class ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Agence Nationale de la Recherche

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)15

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Berthusen NGottesman D(2024)Partial Syndrome Measurement for Hypergraph Product CodesQuantum10.22331/q-2024-05-14-13458(1345)Online publication date: 14-May-2024
https://doi.org/10.22331/q-2024-05-14-1345
Goto H(2024)High-performance fault-tolerant quantum computing with many-hypercube codesScience Advances10.1126/sciadv.adp638810:36Online publication date: 6-Sep-2024
https://doi.org/10.1126/sciadv.adp6388
Golowich LGuruswami V(2024)Decoding Quasi-Cyclic Quantum LDPC Codes2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00029(344-368)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00029
Xu QBonilla Ataides JPattison CRaveendran NBluvstein DWurtz JVasić BLukin MJiang LZhou H(2024)Constant-overhead fault-tolerant quantum computation with reconfigurable atom arraysNature Physics10.1038/s41567-024-02479-z20:7(1084-1090)Online publication date: 29-Apr-2024
https://doi.org/10.1038/s41567-024-02479-z
Yamasaki HKoashi M(2024)Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum ComputationNature Physics10.1038/s41567-023-02325-820:2(247-253)Online publication date: 16-Jan-2024
https://doi.org/10.1038/s41567-023-02325-8
Raveendran NValls JPradhan ARengaswamy NGarcia-Herrero FVasić B(2023)Soft syndrome iterative decoding of quantum LDPC codes and hardware architecturesEPJ Quantum Technology10.1140/epjqt/s40507-023-00201-110:1Online publication date: 19-Oct-2023
https://doi.org/10.1140/epjqt/s40507-023-00201-1
Huang THu TUeng Y(2023)Branch-Assisted Sign-Flipping Belief Propagation Decoding for Topological Quantum Codes Based on Hypergraph Product StructureIEEE Transactions on Quantum Engineering10.1109/TQE.2023.32793794(1-15)Online publication date: 2023
https://doi.org/10.1109/TQE.2023.3279379
Fan JLi JWang YLi YHsieh MDu J(2023)Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound AsymptoticallyIEEE Transactions on Information Theory10.1109/TIT.2022.320123969:1(262-272)Online publication date: Jan-2023
https://doi.org/10.1109/TIT.2022.3201239
Raveendran NRengaswamy NRozpędek FRaina AJiang LVasić B(2022)Finite Rate QLDPC-GKP Coding Scheme that Surpasses the CSS Hamming BoundQuantum10.22331/q-2022-07-20-7676(767)Online publication date: 20-Jul-2022
https://doi.org/10.22331/q-2022-07-20-767
Leverrier ALonde VZémor G(2022)Towards local testability for quantum codingQuantum10.22331/q-2022-02-24-6616(661)Online publication date: 24-Feb-2022
https://doi.org/10.22331/q-2022-02-24-661
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents