Union-Find Decoders For Homological Product Codes

Nicolas Delfosse; Matthew B. Hastings

doi:10.22331/q-2021-03-10-406

Union-Find Decoders For Homological Product Codes

Nicolas Delfosse¹ and Matthew B. Hastings^2,1

¹Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA
²Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA

Published:	2021-03-10, volume 5, page 406
Eprint:	arXiv:2009.14226v2
Doi:	https://doi.org/10.22331/q-2021-03-10-406
Citation:	Quantum 5, 406 (2021).

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

Abstract

Homological product codes are a class of codes that can have improved distance while retaining relatively low stabilizer weight. We show how to build union-find decoders for these codes, using a union-find decoder for one of the codes in the product and a brute force decoder for the other code. We apply this construction to the specific case of the product of a surface code with a small code such as a $[[4,2,2]]$ code, which we call an augmented surface code. The distance of the augmented surface code is the product of the distance of the surface code with that of the small code, and the union-find decoder, with slight modifications, can decode errors up to half the distance. We present numerical simulations, showing that while the threshold of these augmented codes is lower than that of the surface code, the low noise performance is improved.

► BibTeX data

@article{Delfosse2021unionfinddecoders,
  doi = {10.22331/q-2021-03-10-406},
  url = {https://doi.org/10.22331/q-2021-03-10-406},
  title = {Union-{F}ind {D}ecoders {F}or {H}omological {P}roduct {C}odes},
  author = {Delfosse, Nicolas and Hastings, Matthew B.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {406},
  month = mar,
  year = {2021}
}

► References

[1] Michael H Freedman and Matthew B Hastings. Quantum systems on non-$ k $-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs. QIC, 14:144, 2014.

[2] Sergey Bravyi and Matthew B Hastings. Homological product codes. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 273–282, 2014.

[3] Mathew B Hastings. Weight reduction for quantum codes. Quantum Information & Computation, 17(15-16):1307–1334, 2017.

[4] Shai Evra, Tali Kaufman, and Gilles Zémor. Decodable quantum ldpc codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders. arXiv preprint arXiv:2004.07935, 2020.
arXiv:2004.07935

[5] Benjamin Audoux and Alain Couvreur. On tensor products of css codes. arXiv preprint arXiv:1512.07081, 2015.
arXiv:1512.07081

[6] 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, 2013. doi:10.1109/isit.2009.5205648.
https://doi.org/10.1109/isit.2009.5205648

[7] 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. IEEE, 2015. doi:10.1109/focs.2015.55.
https://doi.org/10.1109/focs.2015.55

[8] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault-tolerance with quantum expander codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, oct 2018. doi:10.1109/focs.2018.00076.
https://doi.org/10.1109/focs.2018.00076

[9] Pavel Panteleev and Gleb Kalachev. Degenerate quantum ldpc codes with good finite length performance. arXiv preprint arXiv:1904.02703, 2019.
arXiv:1904.02703

[10] Armanda O Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T Campbell. Single-shot error correction of three-dimensional homological product codes. arXiv preprint arXiv:2009.11790, 2020.
arXiv:2009.11790

[11] Nicolas Delfosse and Naomi H Nickerson. Almost-linear time decoding algorithm for topological codes. arXiv preprint arXiv:1709.06218, 2017.
arXiv:1709.06218

[12] Péter Vrana and Máté Farkas. Homological codes and abelian anyons. Reviews in Mathematical Physics, 31(10):1950038, 2019. doi:10.1142/s0129055x19500387.
https://doi.org/10.1142/s0129055x19500387

[13] Ben Criger and Barbara Terhal. Noise thresholds for the [[4, 2, 2]]-concatenated toric code. arXiv preprint arXiv:1604.04062, 2016.
https://doi.org/10.26421/QIC16.15-16
arXiv:1604.04062

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

[15] Michael H Freedman and David A Meyer. Projective plane and planar quantum codes. Foundations of Computational Mathematics, 1(3):325–332, 2001. doi:10.1007/s102080010013.
https://doi.org/10.1007/s102080010013

[16] Hector Bombin and Miguel A Martin-Delgado. Homological error correction: Classical and quantum codes. Journal of mathematical physics, 48(5):052105, 2007. doi:10.1063/1.2731356.
https://doi.org/10.1063/1.2731356

[17] Nicolas Delfosse and Gilles Zémor. Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel. Physical Review Research, 2(3):033042, 2020. doi:10.1103/physrevresearch.2.033042.
https://doi.org/10.1103/physrevresearch.2.033042

Cited by

[1] Eric Sabo, Arun B. Aloshious, and Kenneth R. Brown, "Trellis Decoding for Qudit Stabilizer Codes and Its Application to Qubit Topological Codes", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[2] Nikolas P. Breuckmann and Jens Niklas Eberhardt, "Quantum Low-Density Parity-Check Codes", PRX Quantum 2 4, 040101 (2021).

[3] Armanda O. Quintavalle and Earl T. Campbell, "ReShape: a decoder for hypergraph product codes", arXiv:2105.02370, (2021).

[4] Nicolas Delfosse, Vivien Londe, and Michael Beverland, "Toward a Union-Find decoder for quantum LDPC codes", arXiv:2103.08049, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-31 23:17:20) and SAO/NASA ADS (last updated successfully 2024-08-31 23:17:21). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.