Almost-linear time decoding algorithm for topological codes
Nicolas Delfosse, Naomi Nickerson
Abstract
In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mi>α</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> is the number of physical qubits and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>α</mml:mi></mml:math> is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>α</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>≤</mml:mo><mml:mn>3</mml:mn></mml:math>. We prove that our algorithm performs optimally for errors of weight up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo stretchy="false">(</mml:mo><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:math> and for loss of up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:math> qubits, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math> is the minimum distance of the code. Numerically, we obtain a threshold of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>9.9</mml:mn><mml:mi mathvariant="normal">%</mml:mi></mml:math> for the 2d-toric code with perfect syndrome measurements and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>2.6</mml:mn><mml:mi mathvariant="normal">%</mml:mi></mml:math> with faulty measurements.