On maximum-likelihood decoding with circuit-level errors

Leonid P. Pryadko

Department of Physics & Astronomy, University of California, Riverside, California 92521, USA

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

Abstract

Error probability distribution associated with a given Clifford measurement circuit is described exactly in terms of the circuit error-equivalence group, or the circuit subsystem code previously introduced by Bacon, Flammia, Harrow, and Shi. This gives a prescription for maximum-likelihood decoding with a given measurement circuit. Marginal distributions for subsets of circuit errors are also analyzed; these generate a family of related asymmetric LDPC codes of varying degeneracy. More generally, such a family is associated with any quantum code. Implications for decoding highly-degenerate quantum codes are discussed.

► BibTeX data

► References

[1] P. W. Shor, ``Scheme for reducing decoherence in quantum computer memory,'' Phys. Rev. A 52, R2493 (1995).
https:/​/​doi.org/​10.1103/​PhysRevA.52.R2493

[2] C. G. Almudever, L. Lao, X. Fu, N. Khammassi, I. Ashraf, D. Iorga, S. Varsamopoulos, C. Eichler, A. Wallraff, L. Geck, A. Kruth, J. Knoch, H. Bluhm, and K. Bertels, ``The engineering challenges in quantum computing,'' in Design, Automation Test in Europe Conference Exhibition (DATE), 2017 (2017) pp. 836–845.
https:/​/​doi.org/​10.23919/​DATE.2017.7927104

[3] P. Aliferis, D. Gottesman, and J. Preskill, ``Quantum accuracy threshold for concatenated distance-3 codes,'' Quantum Inf. Comput. 6, 97–165 (2006), quant-ph/​0504218.
arXiv:quant-ph/0504218
http:/​/​dl.acm.org/​citation.cfm?id=2011665.2011666

[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 (2011).
https:/​/​doi.org/​10.1103/​PhysRevA.83.020302

[5] Christopher T. Chubb and Steven T. Flammia, ``Statistical mechanical models for quantum codes with correlated noise,'' (2018), unpublished, 1809.10704.
arXiv:1809.10704

[6] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, ``Topological quantum memory,'' J. Math. Phys. 43, 4452 (2002).
https:/​/​doi.org/​10.1063/​1.1499754

[7] Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg, ``Towards practical classical processing for the surface code,'' Phys. Rev. Lett. 108, 180501 (2012a).
https:/​/​doi.org/​10.1103/​PhysRevLett.108.180501

[8] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, ``Surface codes: Towards practical large-scale quantum computation,'' Phys. Rev. A 86, 032324 (2012b).
https:/​/​doi.org/​10.1103/​PhysRevA.86.032324

[9] Austin G. Fowler, Adam C. Whiteside, Angus L. McInnes, and Alimohammad Rabbani, ``Topological code autotune,'' Phys. Rev. X 2, 041003 (2012c).
https:/​/​doi.org/​10.1103/​PhysRevX.2.041003

[10] Christopher Chamberland, Guanyu Zhu, Theodore J. Yoder, Jared B. Hertzberg, and Andrew W. Cross, ``Topological and subsystem codes on low-degree graphs with flag qubits,'' Phys. Rev. X 10, 011022 (2020a).
https:/​/​doi.org/​10.1103/​PhysRevX.10.011022

[11] Christopher Chamberland, Aleksander Kubica, Theodore J Yoder, and Guanyu Zhu, ``Triangular color codes on trivalent graphs with flag qubits,'' New Journal of Physics 22, 023019 (2020b).
https:/​/​doi.org/​10.1088/​1367-2630/​ab68fd

[12] Christophe Vuillot, Lingling Lao, Ben Criger, Carmen García Almudéver, Koen Bertels, and Barbara M. Terhal, ``Code deformation and lattice surgery are gauge fixing,'' New Journal of Physics 21, 033028 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab0199

[13] Giacomo Torlai and Roger G. Melko, ``Neural decoder for topological codes,'' Phys. Rev. Lett. 119, 030501 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.119.030501

[14] S. Krastanov and L. Jiang, ``Deep neural network probabilistic decoder for stabilizer codes,'' Scientific Reports 7, 11003 (2017), 1705.09334.
https:/​/​doi.org/​10.1038/​s41598-017-11266-1
arXiv:1705.09334

[15] N. P. Breuckmann and X. Ni, ``Scalable neural network decoders for higher dimensional quantum codes,'' Quantum 2, 68 (2018), 1710.09489.
https:/​/​doi.org/​10.22331/​q-2018-05-24-68
arXiv:1710.09489

[16] Zhih-Ahn Jia, Yuan-Hang Zhang, Yu-Chun Wu, Liang Kong, Guang-Can Guo, and Guo-Ping Guo, ``Efficient machine-learning representations of a surface code with boundaries, defects, domain walls, and twists,'' Phys. Rev. A 99, 012307 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.99.012307

[17] Paul Baireuther, Thomas E. O'Brien, Brian Tarasinski, and Carlo W. J. Beenakker, ``Machine-learning-assisted correction of correlated qubit errors in a topological code,'' Quantum 2, 48 (2018).
https:/​/​doi.org/​10.22331/​q-2018-01-29-48

[18] Christopher Chamberland and Pooya Ronagh, ``Deep neural decoders for near term fault-tolerant experiments,'' Quantum Science and Technology 3, 044002 (2018).
https:/​/​doi.org/​10.1088/​2058-9565/​aad1f7

[19] P. Baireuther, M. D. Caio, B. Criger, C. W. J. Beenakker, and T. E. O'Brien, ``Neural network decoder for topological color codes with circuit level noise,'' New Journal of Physics 21, 013003 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​aaf29e

[20] Nishad Maskara, Aleksander Kubica, and Tomas Jochym-O'Connor, ``Advantages of versatile neural-network decoding for topological codes,'' Phys. Rev. A 99, 052351 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.99.052351

[21] D. Bacon, S. T. Flammia, A. W. Harrow, and J. Shi, ``Sparse quantum codes from quantum circuits,'' in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15 (ACM, New York, NY, USA, 2015) pp. 327–334, 1411.3334.
https:/​/​doi.org/​10.1145/​2746539.2746608
arXiv:1411.3334

[22] D. Bacon, S. T. Flammia, A. W. Harrow, and J. Shi, ``Sparse quantum codes from quantum circuits,'' IEEE Transactions on Information Theory 63, 2464–2479 (2017).
https:/​/​doi.org/​10.1109/​TIT.2017.2663199

[23] Jozef Strečka, ``Generalized algebraic transformations and exactly solvable classical-quantum models,'' Physics Letters A 374, 3718 – 3722 (2010).
https:/​/​doi.org/​10.1016/​j.physleta.2010.07.030

[24] Christopher Chamberland and Michael E. Beverland, ``Flag fault-tolerant error correction with arbitrary distance codes,'' Quantum 2, 53 (2018), 1708.02246.
https:/​/​doi.org/​10.22331/​q-2018-02-08-53
arXiv:1708.02246

[25] C. Chamberland and A. W. Cross, ``Fault-tolerant magic state preparation with flag qubits,'' Quantum 3, 143 (2019), 1811.00566.
https:/​/​doi.org/​10.22331/​q-2019-05-20-143
arXiv:1811.00566

[26] Rui Chao and Ben W. Reichardt, ``Quantum error correction with only two extra qubits,'' Phys. Rev. Lett. 121, 050502 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.121.050502

[27] Héctor Bombín, ``Single-shot fault-tolerant quantum error correction,'' Phys. Rev. X 5, 031043 (2015).
https:/​/​doi.org/​10.1103/​PhysRevX.5.031043

[28] Benjamin J. Brown, Naomi H. Nickerson, and Dan E. Browne, ``Fault-tolerant error correction with the gauge color code,'' Nature Communications 7, 12302 (2016).
https:/​/​doi.org/​10.1038/​ncomms12302

[29] Earl T. Campbell, ``A theory of single-shot error correction for adversarial noise,'' Quantum Science and Technology 4, 025006 (2019), 1805.09271.
https:/​/​doi.org/​10.1088/​2058-9565/​aafc8f
arXiv:1805.09271

[30] I. Dumer, A. A. Kovalev, and L. P. Pryadko, ``Thresholds for correcting errors, erasures, and faulty syndrome measurements in degenerate quantum codes,'' Phys. Rev. Lett. 115, 050502 (2015), 1412.6172.
https:/​/​doi.org/​10.1103/​PhysRevLett.115.050502
arXiv:1412.6172

[31] A. A. Kovalev, S. Prabhakar, I. Dumer, and L. P. Pryadko, ``Numerical and analytical bounds on threshold error rates for hypergraph-product codes,'' Phys. Rev. A 97, 062320 (2018), 1804.01950.
https:/​/​doi.org/​10.1103/​PhysRevA.97.062320
arXiv:1804.01950

[32] David Poulin, ``Stabilizer formalism for operator quantum error correction,'' Phys. Rev. Lett. 95, 230504 (2005).
https:/​/​doi.org/​10.1103/​PhysRevLett.95.230504

[33] Dave Bacon, ``Operator quantum error-correcting subsystems for self-correcting quantum memories,'' Phys. Rev. A 73, 012340 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.012340

[34] Daniel Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, Caltech (1997).
arXiv:quant-ph/9705052

[35] A. R. Calderbank, E. M. Rains, P. M. Shor, and N. J. A. Sloane, ``Quantum error correction via codes over GF(4),'' IEEE Trans. Info. Theory 44, 1369–1387 (1998).
https:/​/​doi.org/​10.1109/​18.681315

[36] Jeroen Dehaene and Bart De Moor, ``Clifford group, stabilizer states, and linear and quadratic operations over GF(2),'' Phys. Rev. A 68, 042318 (2003).
https:/​/​doi.org/​10.1103/​PhysRevA.68.042318

[37] Scott Aaronson and Daniel Gottesman, ``Improved simulation of stabilizer circuits,'' Phys. Rev. A 70, 052328 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[38] Bin Dai, Shilin Ding, and Grace Wahba, ``Multivariate Bernoulli distribution,'' Bernoulli 19, 1465–1483 (2013).
https:/​/​doi.org/​10.3150/​12-BEJSP10

[39] F. Wegner, ``Duality in generalized Ising models and phase transitions without local order parameters,'' J. Math. Phys. 2259, 12 (1971).
https:/​/​doi.org/​10.1063/​1.1665530

[40] A. J. Landahl, J. T. Anderson, and P. R. Rice, ``Fault-tolerant quantum computing with color codes,'' (2011), presented at QIP 2012, December 12 to December 16, arXiv:1108.5738.
arXiv:arXiv:1108.5738

[41] A. A. Kovalev and L. P. Pryadko, ``Spin glass reflection of the decoding transition for quantum error-correcting codes,'' Quantum Inf. & Comp. 15, 0825 (2015), arXiv:1311.7688.
arXiv:arXiv:1311.7688

[42] Lars Onsager, ``Crystal statistics. I. a two-dimensional model with an order-disorder transition,'' Phys. Rev. 65, 117–149 (1944).
https:/​/​doi.org/​10.1103/​PhysRev.65.117

[43] Shigeo Naya, ``On the spontaneous magnetizations of honeycomb and Kagomé Ising lattices,'' Progress of Theoretical Physics 11, 53–62 (1954).
https:/​/​doi.org/​10.1143/​PTP.11.53

[44] Michael E. Fisher, ``Transformations of Ising models,'' Phys. Rev. 113, 969–981 (1959).
https:/​/​doi.org/​10.1103/​PhysRev.113.969

[45] Sergey Bravyi, Martin Suchara, and Alexander Vargo, ``Efficient algorithms for maximum likelihood decoding in the surface code,'' Phys. Rev. A 90, 032326 (2014).
https:/​/​doi.org/​10.1103/​PhysRevA.90.032326

[46] Markus Hauru, Clement Delcamp, and Sebastian Mizera, ``Renormalization of tensor networks using graph-independent local truncations,'' Phys. Rev. B 97, 045111 (2018).
https:/​/​doi.org/​10.1103/​PhysRevB.97.045111

[47] M. de Koning, Wei Cai, A. Antonelli, and S. Yip, ``Efficient free-energy calculations by the simulation of nonequilibrium processes,'' Computing in Science Engineering 2, 88–96 (2000).
https:/​/​doi.org/​10.1109/​5992.841802

[48] Charles H. Bennett, ``Efficient estimation of free energy differences from Monte Carlo data,'' Journal of Computational Physics 22, 245–268 (1976).
https:/​/​doi.org/​10.1016/​0021-9991(76)90078-4

[49] Tobias Preis, Peter Virnau, Wolfgang Paul, and Johannes J. Schneider, ``GPU accelerated monte carlo simulation of the 2d and 3d ising model,'' Journal of Computational Physics 228, 4468 – 4477 (2009).
https:/​/​doi.org/​10.1016/​j.jcp.2009.03.018

[50] A. Gilman, A. Leist, and K. A. Hawick, ``3D lattice Monte Carlo simulations on FPGAs,'' in Proceedings of the International Conference on Computer Design (CDES) (The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp), 2013).

[51] Kun Yang, Yi-Fan Chen, Georgios Roumpos, Chris Colby, and John Anderson, ``High performance Monte Carlo simulation of Ising model on TPU clusters,'' (2019), unpublished, 1903.11714.
arXiv:1903.11714

[52] D. Poulin and Y. Chung, ``On the iterative decoding of sparse quantum codes,'' Quant. Info. and Comp. 8, 987 (2008), arXiv:0801.1241.
arXiv:arXiv:0801.1241

[53] Ye-Hua Liu and David Poulin, ``Neural belief-propagation decoders for quantum error-correcting codes,'' Phys. Rev. Lett. 122, 200501 (2019), 1811.07835.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.200501
arXiv:1811.07835

[54] Alex Rigby, J. C. Olivier, and Peter Jarvis, ``Modified belief propagation decoders for quantum low-density parity-check codes,'' Phys. Rev. A 100, 012330 (2019), 1903.07404.
https:/​/​doi.org/​10.1103/​PhysRevA.100.012330
arXiv:1903.07404

[55] A. A. Kovalev, I. Dumer, and L. P. Pryadko, ``Design of additive quantum codes via the code-word-stabilized framework,'' Phys. Rev. A 84, 062319 (2011).
https:/​/​doi.org/​10.1103/​PhysRevA.84.062319

[56] Pavithran Iyer and David Poulin, ``Hardness of decoding quantum stabilizer codes,'' IEEE Transactions on Information Theory 61, 5209–5223 (2015), arXiv:1310.3235.
https:/​/​doi.org/​10.1109/​TIT.2015.2422294
arXiv:arXiv:1310.3235

[57] E. A. Kruk, ``Decoding complexity bound for linear block codes,'' Probl. Peredachi Inf. 25, 103–107 (1989), (In Russian).
http:/​/​mi.mathnet.ru/​eng/​ppi665

[58] J. T. Coffey and R. M. Goodman, ``The complexity of information set decoding,'' IEEE Trans. Info. Theory 36, 1031 –1037 (1990).
https:/​/​doi.org/​10.1109/​18.57202

[59] Andrew J. Viterbi, ``Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,'' IEEE Transactions on Information Theory 13, 260–269 (1967).
https:/​/​doi.org/​10.1109/​TIT.1967.1054010

[60] R. G. Gallager, Low-Density Parity-Check Codes (M.I.T. Press, Cambridge, Mass., 1963).
https:/​/​doi.org/​doi=10.1.1.147.683

[61] M. P. C. Fossorier, ``Iterative reliability-based decoding of low-density parity check codes,'' IEEE Journal on Selected Areas in Communications 19, 908–917 (2001).
https:/​/​doi.org/​10.1109/​49.924874

[62] Thomas J. Richardson and Rüdiger L. Urbanke, ``The capacity of low-density parity-check codes under message-passing decoding,'' Information Theory, IEEE Transactions on 47, 599–618 (2001).
https:/​/​doi.org/​10.1109/​18.910577

[63] David Declerq, Marc Fossorier, and Ezio Biglieri, eds., Channel Coding. Theory, Algorithms, and Applications (Academic Press Library in Mobile and Wireless Communications, San Francisco, 2014).
https:/​/​doi.org/​10.1016/​C2011-0-07211-3

[64] Weilei Zeng and Leonid P. Pryadko, ``Iterative decoding of row-reduced quantum LDPC codes,'' (2020), unpublished.

[65] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam, 1981).

[66] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier, ``Efficient decoding of random errors for quantum expander codes,'' (2017), unpublished, 1711.08351.
arXiv:1711.08351

[67] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier, ``Constant overhead quantum fault-tolerance with quantum expander codes,'' in 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 (2018) pp. 743–754.
https:/​/​doi.org/​10.1109/​FOCS.2018.00076

[68] A. Grospellier and A. Krishna, ``Numerical study of hypergraph product codes,'' (2018), unpublished, 1810.03681.
arXiv:1810.03681

[69] Pavel Panteleev and Gleb Kalachev, ``Degenerate quantum LDPC codes with good finite length performance,'' (2019), unpublished, 1904.02703.
arXiv:1904.02703

[70] Antoine Grospellier, Lucien Grouès, Anirudh Krishna, and Anthony Leverrier, ``Combining hard and soft decoders for hypergraph product codes,'' (2020), unpublished, arXiv:2004.11199.
arXiv:arXiv:2004.11199

Cited by

[1] Nicolas Delfosse, Ben W. Reichardt, and Krysta M. Svore, "Beyond single-shot fault-tolerant quantum error correction", arXiv:2002.05180.

The above citations are from SAO/NASA ADS (last updated successfully 2020-12-02 21:00:15). 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 2020-12-02 21:00:13).