Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code

Sergey Bravyi; Martin Suchara; Alexander Vargo

Source-linked AI summary

Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code

Sergey Bravyi, Martin Suchara, Alexander Vargo

arXiv:1405.4883v1May 19, 2014quant-ph

TL;DR

The paper addresses efficient maximum likelihood decoding for the 2D surface code under noiseless syndrome extraction. It gives an exact O(n^2) implementation for a special noise model and an approximate O(nχ^3) implementation for more general noise, with the MPS decoder approaching optimal performance at modest bond dimensions.

Problem
Maximum likelihood decoding is optimal for a fixed code and noise model, but an exact efficient implementation for surface codes remained elusive.
Method
The paper reduces decoding to matchgate-circuit simulation for bit-flip noise and uses matrix product states to simulate weakly entangled dynamics for more general noise models.
Results
The MPS decoder with χ = 6, 8 is virtually indistinguishable from the optimal decoder, while the depolarizing-noise data suggests a lower-bound threshold ϵ0 ≥14%.
Takeaways & Limitations
The results support using MPS-based decoding for general surface-code noise models and matchgate simulation for exact decoding under suitable noise assumptions.
Takeaways & Limitations
The MPS approach relies on an unproven weak-entanglement conjecture and provides no direct means of estimating its approximation precision.

Abstract

from arXiv · show

We describe two implementations of the optimal error correction algorithm known as the maximum likelihood decoder (MLD) for the 2D surface code with a noiseless syndrome extraction. First, we show how to implement MLD exactly in time $O(n^2)$, where $n$ is the number of code qubits. Our implementation uses a reduction from MLD to simulation of matchgate quantum circuits. This reduction however requires a special noise model with independent bit-flip and phase-flip errors. Secondly, we show how to implement MLD approximately for more general noise models using matrix product states (MPS). Our implementation has running time $O(nχ^3)$ where $χ$ is a parameter that controls the approximation precision. The key step of our algorithm, borrowed from the DMRG method, is a subroutine for contracting a tensor network on the two-dimensional grid. The subroutine uses MPS with a bond dimension $χ$ to approximate the sequence of tensors arising in the course of contraction. We benchmark the MPS-based decoder against the standard minimum weight matching decoder observing a significant reduction of the logical error probability for $χ\ge 4$.

I. INTRODUCTION

The paper develops exact and approximate implementations of maximum likelihood decoding for surface codes, addressing the computational difficulty of this optimal decoding problem under different noise models.

Motivation and background: Maximum likelihood decoding selects the recovery operation with the highest conditional probability of successful correction given the observed syndrome.For stabilizer codes, decoding identifies the most probable stabilizer-group coset compatible with the syndrome.
Motivation and background: The computational problem for surface-code MLD reduces to evaluating a partition function of a classical Ising-like Hamiltonian on a two-dimensional lattice.This connection has motivated both statistical-physics analyses and searches for efficient decoding algorithms.
Contributions: The paper proposes an alternative MLD implementation that maps decoding to simulating quantum dynamics for a chain of qubits.The construction applies to bit-flip and depolarizing noise models.
Contributions: O(n^2) exact MLD is obtained for bit-flip noise, and the same matchgate-based approach also handles independent bit-flip and phase-flip errors.The algorithm uses fermionic Gaussian states to classically simulate the resulting matchgate circuits.
Contributions: O(nχ^3) approximate MLD is obtained for depolarizing noise using matrix product states with bond dimension χ controlling approximation precision.The approach relies on a conjecture that intermediate states remain weakly entangled.
Evaluation: The paper benchmarks exact and approximate MLD against minimum weight matching, including numerical comparisons across code distances and error rates.The comparison is motivated by the fact that minimum weight matching ignores error degeneracy.

III. NOISE MODELS

The paper studies independent stochastic Pauli noise on a square-lattice surface code, focusing on X-noise and depolarizing noise as principal models.

Noise models: The paper assumes stochastic i.i.d. Pauli noise, with total error rate ϵ = ϵX + ϵY + ϵZ.The distribution assigns probabilities to Pauli errors according to their types and Hamming weights.
Noise models: X-noise allows only bit-flip errors, with ϵX = ϵ and ϵY = ϵZ = 0.This is treated as a classical bit-flip noise model.
Noise models: Depolarizing noise assigns equal rates to X, Y, and Z errors: ϵX = ϵY = ϵZ = ϵ/3.It is the more general of the two principal noise models considered.
Noise models: Independent bit-flip and phase-flip errors satisfy ϵX = ϵZ and ϵY = (ϵX)2, allowing the two error types to be corrected independently.Phase-flip correction is equivalent to bit-flip correction on the surface-code lattice rotated by 90°.
Surface-code geometry: The surface code uses a d × d square lattice with open boundaries, encodes one logical qubit into n = d2 + (d −1)2 physical qubits, and has minimum distance d.For odd d, it corrects any combination of (d −1)/2 single-qubit errors.
Surface-code geometry: Site stabilizers are generated by products of Z operators on edges incident to a site, while plaquette stabilizers are generated by products of X operators around plaquettes.The full stabilizer group is generated by both stabilizer types.

V. EXACT ALGORITHM

The section presents an exact MLD implementation for X-noise, reducing coset-probability computation to an algorithm with running time O(n^2).

B. Algorithm for computing the coset probability: The exact algorithm specializes MLD to X-noise and computes coset probabilities for an X-type Pauli operator f.Only X-type errors have nonzero probability, and the relevant probability is π(fGX).
B. Algorithm for computing the coset probability: The input syndrome is converted into a fixed X-type Pauli error by connecting nonzero site syndromes to the left boundary with horizontal X strings.This constructs an error consistent with the observed syndrome under the X-noise model.
B. Algorithm for computing the coset probability: O(n^2) is the overall running time of the exact implementation, since the naive matrix operations cost O(d^3) and the code satisfies n=d2+(d−1)2.The runtime is also expressed as O(d4)=O(n2).
B. Algorithm for computing the coset probability: The surface-code edges are organized into horizontal columns H1, . . . , Hd and vertical columns V1, . . . , Vd−1.Each edge corresponds to a code qubit, and the columns support the algorithm’s lattice-based construction.

C. Reduction to a matchgate quantum circuit

The section maps X-noise coset probabilities to a matrix element of a d-qubit circuit whose gates preserve even Hamming-weight parity and are matchgates.

C. Reduction to a matchgate quantum circuit: Horizontal columns contribute single-qubit gates, while vertical columns contribute two-qubit gates that reconstruct vertical edges from neighboring column bit strings.The vertical gate has the form G′(w)=I⊗I+wX⊗X.
C. Reduction to a matchgate quantum circuit: The circuit U is formed by alternating horizontal and vertical column operators as U=Hd Vd−1 · · · H2 V1 H1.The operators act on the d-qubit Hilbert space associated with the lattice columns.
C. Reduction to a matchgate quantum circuit: Coset-probability computation is expressed as the matrix element ⟨ψe|U|ψe⟩ for a circuit acting on d qubits.ψe is the superposition of all d-bit strings with even Hamming weight.
C. Reduction to a matchgate quantum circuit: The gates G(w) and G′(w) are matchgates, enabling classical simulation of the resulting circuit.The paper uses this matchgate structure to compute the matrix element in O(n^2) time.
C. Reduction to a matchgate quantum circuit: The operators preserve Hamming weight modulo two, so the computation remains in the even-parity subspace generated by ψe.This parity preservation yields the stated matrix-element representation.

D. Fermionic Gaussian states

The section uses fermionic Gaussian states to simulate the matchgate circuit by tracking covariance matrices and norms through successive operators.

D. Fermionic Gaussian states: A fermionic Gaussian state is specified by its covariance matrix M and norm Γ, and its even Majorana expectations obey Wick’s theorem.The relevant expectations are computed using Pfaffians of covariance-matrix submatrices.
D. Fermionic Gaussian states: The initial even-parity state ψe is Gaussian with covariance matrix M0 and norm Γ=2d−1.Its covariance matrix satisfies the Gaussian-state condition MM^T=I.
D. Fermionic Gaussian states: The horizontal and vertical circuit operators preserve Gaussianity, so every intermediate state remains representable by covariance data.This reduces circuit simulation to updating covariance matrices and norms after each operator.
D. Fermionic Gaussian states: The final overlap is obtained after propagating the covariance matrix and norm through the horizontal and vertical operators.The resulting procedure computes Z(w)=⟨ψe|Hd Vd−1 · · · V1 H1|ψe⟩ efficiently.
D. Fermionic Gaussian states: The update calculation decomposes horizontal operators into disjoint Majorana-mode blocks, allowing local covariance and normalization calculations to be combined across the chain.For arbitrary d, the construction takes direct sums of d four-mode covariance matrices and multiplies their normalization coefficients.

VI. APPROXIMATE ALGORITHM

The section presents an approximate algorithm for computing coset probabilities for general stochastic i.i.d. Pauli noise, including depolarizing noise.

VI. APPROXIMATE ALGORITHM: The approximate algorithm computes coset probabilities for a general stochastic i.i.d. Pauli noise model, including depolarizing noise.It is formulated using matrix product states and tensor networks.

A. Construction of the tensor network

The decoder’s coset probability is expressed as a contraction value of a tensor network on an extended surface-code lattice. Local tensors depend only on stabilizer variables adjacent to each code-qubit edge, while constraint tensors enforce valid link labelings.

Local tensor construction: Each edge restriction depends only on four adjacent binary stabilizer variables, with boundary edges omitting variables that are absent.The variables are αu(e), αv(e), βp(e), and βq(e).
Extended lattice: The extended lattice contains stabilizer nodes and horizontal- and vertical-edge qubit nodes, forming a two-dimensional tensor-network grid.Its general dimensions are (2d −1) × (2d −1).
Valid link labelings: Stabilizer configurations α and β induce valid link labelings in which all links incident to each stabilizer node share one label.The labeling copies α variables from site stabilizers and β variables from plaquette stabilizers to incident links.
Constraint tensors: Extending the sum to all link labelings introduces 0–1 stabilizer-node tensors that equal one exactly when incident links have identical labels.These tensors eliminate invalid labelings without changing the sum over valid ones.
Tensor-network representation: The resulting product over all lattice nodes and sum over link labelings is the contraction value of the tensor network.Each tensor depends only on labels of links incident to its node.

B. Approximate contraction algorithm

The approximate decoder contracts the two-dimensional tensor network column by column using matrix product states and operators. Canonicalization and SVD-based truncation keep bond dimension bounded while controlling approximation through χ.

Column decomposition: The extended lattice is partitioned into horizontal columns H1, …, Hd and vertical columns V1, …, Vd−1 for sequential contraction.Internal horizontal and vertical columns define MPOs, while the first and last horizontal columns define MPSs.
Approximation control: The algorithm uses bond dimension χ to control approximation accuracy, becoming exact when χ is exponentially large in d.The maintained state is represented by 2d −1 tensors with O(dχ^2) real parameters.
MPS updates: Each column update applies an MPO to the current MPS, initially set to H1, increasing the intermediate bond dimension from χ to 2χ.Tensor products for updates take time O(dχ^2).
Orthogonality: Left- and right-canonical tensor families form orthonormal state families, enabling the Schmidt-decomposition-based truncation.The left-canonical construction yields ⟨φβ|φα⟩ = δα,β.
Canonicalization: LeftCanonical transforms an MPS into an equivalent scalar-times-MPS with left canonical form at every qubit.QR decompositions preserve the represented state up to normalization and cost O(Lχ^3).
Bond-dimension truncation: Truncate computes a Schmidt decomposition from an SVD and retains the χ largest Schmidt coefficients to produce the best rank-χ approximation.The retained singular values become the truncated Schmidt coefficients.

VII. NUMERICAL RESULTS

The paper reports numerical studies of combinations of noise models and decoders, but the supplied passage does not state their outcomes.

Experimental setup: The numerical-results section studies combinations of noise models and decoders.

3. X-noise, MWM decoder

For X-noise, the MWM decoder remains close to optimal, while the exact MLD threshold is estimated near 11% and small-bond-dimension MPS closely matches optimal performance.

MWM comparison: MWM remains nearly optimal across simulated X-noise error rates, with badness parameter ≤2 at code distance d = 25.Its slight disadvantage is attributed to ignoring error degeneracy.
MPS comparison: MPS decoders with χ = 6 and 8 are virtually indistinguishable from the optimal decoder in logical error probability.This provides numerical evidence supporting the MPS decoder's correctness for the tested X-noise settings.
Numerical stability: The exact MLD implementation becomes sensitive to rounding errors at large code distances and small error rates.The authors use QR-based stabilization to suppress this numerical issue.
Threshold performance: 10.9% ≤ ϵ0 ≤ 11% is the exact MLD threshold estimate for X-noise, agreeing with the spin-model estimate ϵ0 = 10.93(2)%.The MWM threshold is approximately 10.31%.
Coset probabilities: MPS coset probabilities converge very quickly for the most likely coset but poorly for the remaining cosets.Because decoding only requires identifying the most likely coset, slower convergence for unlikely cosets may not be a serious drawback.