Union-Find Decoders For Homological Product Codes

Nicolas Delfosse1 and Matthew B. Hastings2,1

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

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


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

► 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.

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

[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.

[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.

[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.

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

[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.

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

[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.

[13] Ben Criger and Barbara Terhal. Noise thresholds for the [[4, 2, 2]]-concatenated toric code. arXiv preprint arXiv:1604.04062, 2016.

[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.

[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.

[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.

[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.

Cited by

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

[2] Nikolas P. Breuckmann and Jens Niklas Eberhardt, "LDPC Quantum Codes", arXiv:2103.06309.

The above citations are from SAO/NASA ADS (last updated successfully 2021-04-23 11:02:08). 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-04-23 11:02:05).