{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,22]],"date-time":"2024-06-22T06:05:31Z","timestamp":1719036331681},"reference-count":17,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T00:00:00Z","timestamp":1615334400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 [<\/mml:mo>[<\/mml:mo>4<\/mml:mn>,<\/mml:mo>2<\/mml:mn>,<\/mml:mo>2<\/mml:mn>]<\/mml:mo>]<\/mml:mo><\/mml:math> 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.<\/jats:p>","DOI":"10.22331\/q-2021-03-10-406","type":"journal-article","created":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T13:12:34Z","timestamp":1615381954000},"page":"406","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Union-Find Decoders For Homological Product Codes"],"prefix":"10.22331","volume":"5","author":[{"given":"Nicolas","family":"Delfosse","sequence":"first","affiliation":[{"name":"Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA"}]},{"given":"Matthew B.","family":"Hastings","sequence":"additional","affiliation":[{"name":"Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA"},{"name":"Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA"}]}],"member":"9598","published-online":{"date-parts":[[2021,3,10]]},"reference":[{"key":"0","unstructured":"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."},{"key":"1","doi-asserted-by":"crossref","unstructured":"Sergey Bravyi and Matthew B Hastings. Homological product codes. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 273\u2013282, 2014.","DOI":"10.1145\/2591796.2591870"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Mathew B Hastings. Weight reduction for quantum codes. Quantum Information & Computation, 17(15-16):1307\u20131334, 2017.","DOI":"10.26421\/QIC17.15-16-4"},{"key":"3","unstructured":"Shai Evra, Tali Kaufman, and Gilles Z\u00e9mor. Decodable quantum ldpc codes beyond the $\\sqrt{n}$ distance barrier using high dimensional expanders. arXiv preprint arXiv:2004.07935, 2020."},{"key":"4","unstructured":"Benjamin Audoux and Alain Couvreur. On tensor products of css codes. arXiv preprint arXiv:1512.07081, 2015."},{"key":"5","doi-asserted-by":"publisher","unstructured":"Jean-Pierre Tillich and Gilles Z\u00e9mor. 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\u20131202, 2013. doi:10.1109\/isit.2009.5205648.","DOI":"10.1109\/isit.2009.5205648"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Anthony Leverrier, Jean-Pierre Tillich, and Gilles Z\u00e9mor. Quantum expander codes. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 810\u2013824. IEEE, 2015. doi:10.1109\/focs.2015.55.","DOI":"10.1109\/focs.2015.55"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/focs.2018.00076"},{"key":"8","unstructured":"Pavel Panteleev and Gleb Kalachev. Degenerate quantum ldpc codes with good finite length performance. arXiv preprint arXiv:1904.02703, 2019."},{"key":"9","unstructured":"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."},{"key":"10","unstructured":"Nicolas Delfosse and Naomi H Nickerson. Almost-linear time decoding algorithm for topological codes. arXiv preprint arXiv:1709.06218, 2017."},{"key":"11","doi-asserted-by":"publisher","unstructured":"P\u00e9ter Vrana and M\u00e1t\u00e9 Farkas. Homological codes and abelian anyons. Reviews in Mathematical Physics, 31(10):1950038, 2019. doi:10.1142\/s0129055x19500387.","DOI":"10.1142\/s0129055x19500387"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Ben Criger and Barbara Terhal. Noise thresholds for the [[4, 2, 2]]-concatenated toric code. arXiv preprint arXiv:1604.04062, 2016.","DOI":"10.26421\/QIC16.15-16"},{"key":"13","doi-asserted-by":"publisher","unstructured":"A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2\u201330, 2003. doi:10.1016\/s0003-4916(02)00018-0.","DOI":"10.1016\/s0003-4916(02)00018-0"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Michael H Freedman and David A Meyer. Projective plane and planar quantum codes. Foundations of Computational Mathematics, 1(3):325\u2013332, 2001. doi:10.1007\/s102080010013.","DOI":"10.1007\/s102080010013"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1063\/1.2731356"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Nicolas Delfosse and Gilles Z\u00e9mor. 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.","DOI":"10.1103\/physrevresearch.2.033042"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-03-10-406\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T13:13:11Z","timestamp":1615381991000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-03-10-406\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,10]]},"references-count":17,"URL":"https:\/\/doi.org\/10.22331\/q-2021-03-10-406","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,10]]},"article-number":"406"}}