Fixing errors on a quantum computer

Knowing that errors have occurred is important, but it is only half of the rent. In this section, we learnt about decoder and how it is used to analyze the error syndromes and infer the specific locations and types of errors that have corrupted our quantum information.

Decoding algorithms help determine the most likely error configuration. We have seen how algorithms can utilize graph-based representations that model the relationships between qubits and the stabilizer measurement outcomes, allowing decoders to efficiently process and correct occuring errors. We also learned that a correction can be successful or not, and what are the consequences of having an unsuccesful correction.

A correction must be found *extremely* quickly, which is why we introduced two decoding algorithms that are able to find corrections in polynomial time. The MWPM has a higher accuracy than the Union Find, but the Union Find is a *considerably* faster decoder. Depending on the experimental device that you want to protect against errors, it might be more or less convenient to choose one or the other.

We also considered a realistic scenario, where each qubit might be subject to a different source of errors with different probabilities, learning how we can make use of this information about our experimental device to improve our decoding accuracy.

Bibliography

• M. Gimeno-Segovia, “Towards practical linear optical quantum computing,” Nov. 2015. Accepted: 2017-02-02T11:36:32Z Publisher: Imperial College London.

• E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,” Journal of Mathematical Physics, vol. 43, pp. 4452–4505, Sept. 2002. Publisher: American Institute of Physics.

• O. Higgott, “PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching,” ACM Transactions on Quantum Computing, 2021.

• E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, Dec. 1959.

• V. Kolmogorov, “Blossom V: a new implementation of a minimum cost perfect matching algorithm,” Mathematical Programming Computation, vol. 1, pp. 43–67, July 2009.

• N. Delfosse and N. H. Nickerson, “Almost-linear time decoding algorithm for topological codes,” Quantum, vol. 5, p. 595, Dec. 2021. arXiv: 1709.06218.

• N. Delfosse and G. Zémor, “Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel,” Physical Review Research, vol. 2, p. 033042, July 2020.

• S. Huang, M. Newman, and K. R. Brown, “Fault-tolerant weighted union-find decoding on the toric code,” Physical Review A, vol. 102, p. 012419, July 2020.