Faculty of Mechanics and Mathematics, Moscow State University, GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We study the performance of medium-length quantum LDPC (QLDPC) codes in the depolarizing channel. Only degenerate codes with the maximal stabilizer weight much smaller than their minimum distance are considered. It is shown that with the help of OSD-like post-processing the performance of the standard belief propagation (BP) decoder on many QLDPC codes can be improved by several orders of magnitude. Using this new BP-OSD decoder we study the performance of several known classes of degenerate QLDPC codes including hypergraph product codes, hyperbicycle codes, homological product codes, and Haah’s cubic codes. We also construct several interesting examples of short generalized bicycle codes. Some of them have an additional property that their syndromes are protected by small BCH codes, which may be useful for the fault-tolerant syndrome measurement. We also propose a new large family of QLDPC codes that contains the class of hypergraph product codes, where one of the used parity-check matrices is square. It is shown that in some cases such codes have better performance than hypergraph product codes. Finally, we demonstrate that the performance of the proposed BP-OSD decoder for some of the constructed codes is better than for a relatively large surface code decoded by a near-optimal decoder.
Featured image: The impact of the OSD post-processing on the error-correcting performance of the BP decoder for the depolarizing noise model. The simulation results of the BP and BP-OSD decoders are shown for a new QLDPC code with weight-6 stabilizers constructed in the current work. These results are compared with the performance of a surface code under the near-optimal decoder proposed by Bravyi, Suchara, and Vargo. While the number of physical qubits in both quantum codes are almost the same, the new QLDPC code provides 28 times more logical qubits than the surface code.
The conference talk at the 5th International Conference on Quantum Error Correction (QEC’19) – held from 29th July to 2nd August 2019 at Senate House in London.
Popular summary
► BibTeX data
► References
[1] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452–4505, 2002. doi:10.1063/1.1499754.
https://doi.org/10.1063/1.1499754
[2] Michael H. Freedman and David A. Meyer. Projective plane and planar quantum codes. Foundations of Computational Mathematics, 1(3):325–332, Jul 2001. doi:10.1007/s102080010013.
https://doi.org/10.1007/s102080010013
[3] H. Bombin and M. A. Martin-Delgado. Topological quantum distillation. Phys. Rev. Lett., 97:180501, Oct 2006. doi:10.1103/PhysRevLett.97.180501.
https://doi.org/10.1103/PhysRevLett.97.180501
[4] David S. Wang, Austin G. Fowler, and Lloyd C. L. Hollenberg. Surface code quantum computing with error rates over 1%. Phys. Rev. A, 83:020302, Feb 2011. doi:10.1103/PhysRevA.83.020302.
https://doi.org/10.1103/PhysRevA.83.020302
[5] Sergey Bravyi, Martin Suchara, and Alexander Vargo. Efficient algorithms for maximum likelihood decoding in the surface code. Phys. Rev. A, 90:032326, Sep 2014. doi:10.1103/PhysRevA.90.032326.
https://doi.org/10.1103/PhysRevA.90.032326
[6] Nikolas P. Breuckmann and Barbara M. Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE Transactions on Information Theory, 62(6):3731–3744, June 2016. doi:10.1109/TIT.2016.2555700.
https://doi.org/10.1109/TIT.2016.2555700
[7] J. Tillich and G. Zémor. Quantum LDPC codes with positive rate and minimum distance proportional to $n^{1/2}$. In 2009 IEEE International Symposium on Information Theory, pages 799–803, June 2009. doi:10.1109/ISIT.2009.5205648.
https://doi.org/10.1109/ISIT.2009.5205648
[8] Sergey Bravyi and Matthew B. Hastings. Homological product codes. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC ’14, pages 273–282, New York, NY, USA, 2014. ACM. doi:10.1145/2591796.2591870.
https://doi.org/10.1145/2591796.2591870
[9] A. A. Kovalev and L. P. Pryadko. Improved quantum hypergraph-product LDPC codes. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 348–352, July 2012. doi:10.1109/ISIT.2012.6284206.
https://doi.org/10.1109/ISIT.2012.6284206
[10] Alexey A. Kovalev and Leonid P. Pryadko. Quantum kronecker sum-product low-density parity-check codes with finite rate. Phys. Rev. A, 88:012311, Jul 2013. doi:10.1103/PhysRevA.88.012311.
https://doi.org/10.1103/PhysRevA.88.012311
[11] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. Fifteen years of quantum LDPC coding and improved decoding strategies. IEEE Access, 3:2492–2519, 2015. doi:10.1109/ACCESS.2015.2503267.
https://doi.org/10.1109/ACCESS.2015.2503267
[12] M. Hagiwara and H. Imai. Quantum quasi-cyclic LDPC codes. In 2007 IEEE International Symposium on Information Theory, pages 806–810, June 2007. doi:10.1109/ISIT.2007.4557323.
https://doi.org/10.1109/ISIT.2007.4557323
[13] M. P. C. Fossorier and Shu Lin. Soft-decision decoding of linear block codes based on ordered statistics. IEEE Transactions on Information Theory, 41(5):1379–1396, Sep. 1995. doi:10.1109/18.412683.
https://doi.org/10.1109/18.412683
[14] M. P. C. Fossorier. Iterative reliability-based decoding of low-density parity check codes. IEEE Journal on Selected Areas in Communications, 19(5):908–917, may 2001. doi:10.1109/49.924874.
https://doi.org/10.1109/49.924874
[15] B. Dorsch. A decoding algorithm for binary block codes and $j$-ary output channels (corresp.). IEEE Transactions on Information Theory, 20(3):391–394, may 1974. doi:10.1109/TIT.1974.1055217.
https://doi.org/10.1109/TIT.1974.1055217
[16] Matthew B. Hastings, Jeongwan Haah, and Ryan O’Donnell. Fiber bundle codes: Breaking the n1/2 polylog(n) barrier for quantum LDPC codes. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1276–1288. Association for Computing Machinery, New York, NY, USA, June 2021. doi:10.1145/3406325.3451005.
https://doi.org/10.1145/3406325.3451005
[17] Pavel Panteleev and Gleb Kalachev. Quantum LDPC codes with almost linear minimum distance. IEEE Transactions on Information Theory, pages 1–1, 2021. doi:10.1109/TIT.2021.3119384.
https://doi.org/10.1109/TIT.2021.3119384
[18] Nikolas P. Breuckmann and Jens N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, 67(10):6653–6674, October 2021. doi:10.1109/TIT.2021.3097347.
https://doi.org/10.1109/TIT.2021.3097347
[19] Michael Freedman and Matthew Hastings. Building manifolds from quantum codes. Geometric and Functional Analysis, June 2021. doi:10.1007/s00039-021-00567-3.
https://doi.org/10.1007/s00039-021-00567-3
[20] Jeongwan Haah. Local stabilizer codes in three dimensions without string logical operators. Phys. Rev. A, 83:042330, Apr 2011. doi:10.1103/PhysRevA.83.042330.
https://doi.org/10.1103/PhysRevA.83.042330
[21] D. Poulin and Yeojin C. On the iterative decoding of sparse quantum codes. Quantum Info. Comput., 8(10):987–1000, November 2008. doi:10.5555/2016985.2016993.
https://doi.org/10.5555/2016985.2016993
[22] Y. Wang, B. C. Sanders, B. Bai, and X. Wang. Enhanced feedback iterative decoding of sparse quantum codes. IEEE Transactions on Information Theory, 58(2):1231–1241, Feb 2012. doi:10.1109/TIT.2011.2169534.
https://doi.org/10.1109/TIT.2011.2169534
[23] Alex Rigby, J. C. Olivier, and Peter Jarvis. Modified belief propagation decoders for quantum low-density parity-check codes. Physical Review A, 100(1):012330, July 2019. doi:10.1103/PhysRevA.100.012330.
https://doi.org/10.1103/PhysRevA.100.012330
[24] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology, 1997. doi:10.7907/rzr7-dt72.
https://doi.org/10.7907/rzr7-dt72
[25] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54:1098–1105, Aug 1996. doi:10.1103/PhysRevA.54.1098.
https://doi.org/10.1103/PhysRevA.54.1098
[26] A. M. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77:793–797, Jul 1996. doi:10.1103/PhysRevLett.77.793.
https://doi.org/10.1103/PhysRevLett.77.793
[27] R. G. Gallager. Low-Density Parity-Check Codes. M.I.T. Press, Cambridge, MA, 1963. doi:10.7551/mitpress/4347.001.0001.
https://doi.org/10.7551/mitpress/4347.001.0001
[28] R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533–547, September 1981. doi:10.1109/TIT.1981.1056404.
https://doi.org/10.1109/TIT.1981.1056404
[29] F.R. Kschischang, B.J. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, February 2001. doi:10.1109/18.910572.
https://doi.org/10.1109/18.910572
[30] E. Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5):5–9, September 1962. doi:10.1109/TIT.1962.1057777.
https://doi.org/10.1109/TIT.1962.1057777
[31] Jack Edmonds. Matroids and the greedy algorithm. Mathematical Programming, 1(1):127–136, December 1971. doi:10.1007/BF01584082.
https://doi.org/10.1007/BF01584082
[32] M.P.C. Fossorier, Shu Lin, and J. Snyders. Reliability-based syndrome decoding of linear block codes. IEEE Transactions on Information Theory, 44(1):388–398, January 1998. doi:10.1109/18.651070.
https://doi.org/10.1109/18.651070
[33] Raymond Laflamme, Cesar Miquel, Juan Pablo Paz, and Wojciech Hubert Zurek. Perfect quantum error correcting code. Physical Review Letters, 77(1):198–201, July 1996. doi:10.1103/PhysRevLett.77.198.
https://doi.org/10.1103/PhysRevLett.77.198
[34] Kao-Yueh Kuo and Ching-Yi Lai. Refined belief propagation decoding of sparse-graph quantum codes. IEEE Journal on Selected Areas in Information Theory, 1(2):487–498, August 2020. doi:10.1109/JSAIT.2020.3011758.
https://doi.org/10.1109/JSAIT.2020.3011758
[35] Marc Fossorier, David Declercq, and Ezio Biglieri. Channel Coding: Theory, Algorithms, and Applications. Academic Press, July 2014. doi:10.1016/C2011-0-07211-3.
https://doi.org/10.1016/C2011-0-07211-3
[36] Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, 1965/ed. doi:10.4153/CJM-1965-045-4.
https://doi.org/10.4153/CJM-1965-045-4
[37] D. J. C. MacKay, G. Mitchison, and P. L. McFadden. Sparse-graph codes for quantum error correction. IEEE Transactions on Information Theory, 50(10):2315–2330, Oct 2004. doi:10.1109/TIT.2004.834737.
https://doi.org/10.1109/TIT.2004.834737
[38] H Bombin, R W Chhajlany, M Horodecki, and M A Martin-Delgado. Self-correcting quantum computers. New Journal of Physics, 15(5):055023, may 2013. doi:10.1088/1367-2630/15/5/055023.
https://doi.org/10.1088/1367-2630/15/5/055023
[39] Yuichiro Fujiwara. Ability of stabilizer quantum error correction to protect itself from its own imperfection. Phys. Rev. A, 90:062304, Dec 2014. doi:10.1103/PhysRevA.90.062304.
https://doi.org/10.1103/PhysRevA.90.062304
[40] Tom Richardson. Error-floors of LDPC codes. In Proceedings of the 41st Annual Conference on Communication, Control and Computing, pages 1426–1435, 2003.
[41] Ye-Hua Liu and David Poulin. Neural belief-propagation decoders for quantum error-correcting codes. Physical Review Letters, 122(20):200501, May 2019. doi:10.1103/PhysRevLett.122.200501.
https://doi.org/10.1103/PhysRevLett.122.200501
[42] Kristine Lally and Patrick Fitzpatrick. Algebraic structure of quasicyclic codes. Discrete Applied Mathematics, 111(1):157–175, July 2001. doi:10.1016/S0166-218X(00)00350-4.
https://doi.org/10.1016/S0166-218X(00)00350-4
[43] Roxana Smarandache and Pascal O. Vontobel. Quasi-cyclic LDPC codes: Influence of proto- and tanner-graph structure on minimum hamming distance upper bounds. IEEE Transactions on Information Theory, 58(2):585–607, February 2012. doi:10.1109/TIT.2011.2173244.
https://doi.org/10.1109/TIT.2011.2173244
[44] San Ling, Harald Niederreiter, and Patrick Solé. On the algebraic structure of quasi-cyclic codes IV: Repeated roots. Designs, Codes and Cryptography, 38:337–361, 2006. doi:10.1007/s10623-005-1431-7.
https://doi.org/10.1007/s10623-005-1431-7
[45] I. Dumer, A. A. Kovalev, and L. P. Pryadko. Distance verification for classical and quantum LDPC codes. IEEE Transactions on Information Theory, 63(7):4675–4686, 2017. doi:10.1109/TIT.2017.2690381.
https://doi.org/10.1109/TIT.2017.2690381
Cited by
[1] Pavel Panteleev and Gleb Kalachev, “Quantum LDPC Codes with Almost Linear Minimum Distance”, arXiv:2012.04068.
[2] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell, “Decoding across the quantum low-density parity-check code landscape”, Physical Review Research 2 4, 043423 (2020).
[3] Nikolas P. Breuckmann and Vivien Londe, “Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High Performance”, arXiv:2001.03568.
[4] Nikolas P. Breuckmann and Jens Niklas Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2 4, 040101 (2021).
[5] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier, “Combining hard and soft decoders for hypergraph product codes”, arXiv:2004.11199.
[6] Armanda O. Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T. Campbell, “Single-Shot Error Correction of Three-Dimensional Homological Product Codes”, PRX Quantum 2 2, 020340 (2021).
[7] J. Eli Bourassa, Rafael N. Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q. Baragiola, Saikat Guha, Guillaume Dauphinais, Krishna K. Sabapathy, Nicolas C. Menicucci, and Ish Dhand, “Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer”, arXiv:2010.02905.
[8] Anirudh Krishna and David Poulin, “Fault-tolerant gates on hypergraph product codes”, arXiv:1909.07424.
[9] Ryan Babbush, Jarrod McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven, “Focus beyond quadratic speedups for error-corrected quantum advantage”, arXiv:2011.04149.
[10] Nicolas Delfosse, Vivien Londe, and Michael Beverland, “Toward a Union-Find decoder for quantum LDPC codes”, arXiv:2103.08049.
[11] Nikolas P. Breuckmann and Jens N. Eberhardt, “Balanced Product Quantum Codes”, arXiv:2012.09271.
[12] Nithin Raveendran and Bane Vasić, “Trapping Sets of Quantum LDPC Codes”, arXiv:2012.15297.
[13] Simon Burton and Dan Browne, “Limitations on transversal gates for hypergraph product codes”, arXiv:2012.05842.
[14] Anthony Leverrier, Simon Apers, and Christophe Vuillot, “Quantum XYZ Product Codes”, arXiv:2011.09746.
[15] Nicolas Delfosse and Matthew B. Hastings, “Union-Find Decoders For Homological Product Codes”, arXiv:2009.14226.
[16] Eric Sabo, Arun B. Aloshious, and Kenneth R. Brown, “Trellis Decoding For Qudit Stabilizer Codes And Its Application To Qubit Topological Codes”, arXiv:2106.08251.
[17] Kao-Yueh Kuo and Ching-Yi Lai, “Exploiting Degeneracy in Belief Propagation Decoding of Quantum Codes”, arXiv:2104.13659.
[18] T. R. Scruby, D. E. Browne, P. Webster, and M. Vasmer, “Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code”, arXiv:2012.08536.
[19] Leonid P. Pryadko, “On maximum-likelihood decoding with circuit-level errors”, arXiv:1909.06732.
[20] Ching-Yi Lai and Kao-Yueh Kuo, “Log-domain decoding of quantum LDPC codes over binary finite fields”, arXiv:2104.00304.
[21] Armanda O. Quintavalle and Earl T. Campbell, “Lifting decoders for classical codes to decoders for quantum codes”, arXiv:2105.02370.
[22] Nicolas Delfosse, Michael E. Beverland, and Maxime A. Tremblay, “Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes”, arXiv:2109.14599.
[23] Kao-Yueh Kuo and Ching-Yi Lai, “Refined Belief Propagation Decoding of Sparse-Graph Quantum Codes”, arXiv:2002.06502.
[24] Kao-Yueh Kuo and Ching-Yi Lai, “Refined Belief-Propagation Decoding of Quantum Codes with Scalar Messages”, arXiv:2102.07122.
[25] Patricio Fuentes, Josu Etxezarreta Martinez, Pedro M. Crespo, and Javier Garcia-Frias, “On the logical error rate of sparse quantum codes”, arXiv:2108.10645.
[26] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland, “Constant-overhead quantum error correction with thin planar connectivity”, arXiv:2109.14609.
[27] Narayanan Rengaswamy, Ankur Raina, Nithin Raveendran, and Bane Vasić, “Distilling GHZ States using Stabilizer Codes”, arXiv:2109.06248.
The above citations are from SAO/NASA ADS (last updated successfully 2021-11-29 14:07:28). 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 2021-11-29 14:07:25).
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.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.
Source: https://quantum-journal.org/papers/q-2021-11-22-585/
