Error correction for encoded quantum annealing

Recently, W. Lechner, P. Hauke, and P. Zoller [Sci. Adv. 1, e1500838 (2015)] have proposed a quantum annealing architecture, in which a classical spin glass with all-to-all pairwise connectivity is simulated by a spin glass with geometrically local interactions. We interpret this architecture as a classical error-correcting code, which is highly robust against weakly correlated bit-flip noise, and we analyze the code's performance using a belief-propagation decoding algorithm. Our observations may also apply to more general encoding schemes and noise models.

Figure 1

The bipartite Forney-style factor graph (FFG) for the $[7,4,3]$ Hamming code, with linear constraint nodes denoted $\oplus$ and variable nodes denoted ($=$). Constraint nodes correspond to rows of the parity-check matrix $H$ in Eq. (1), and variable nodes correspond to columns; an edge connects two nodes if a 1 appears in $H$ where the corresponding row and column meet.

Figure 2

An FFG for the LDPC code of the LHZ scheme, based on Fig. 1 of Ref. [2], shown for $N=5$. Here the variable nodes represent the physical spin variables $\left\{g_{ij}\right\}$, with $i\in [1,N-1]$ and $j\in [2,N]$. The geometrically local linear constraints ensure that certain closed loops of spins have even parity.

Figure 3

One iteration of the BP realization for the case $\varepsilon =0.1$ and $N=4$. Each number shown is the probability $g_{ij}\left(0\right)$ that the associated node $\left(ij\right)$ has the value 0. (a) The prior distribution assuming each measured physical spin has the value 0, except for one spin in the lower right corner which has value 1. This value is incompatible with the rest, indicating a likely error. (b) Values of $g_{jk}\left(0\right)$ passed from variable nodes $(=)$ to neighboring constraint nodes $\oplus$. (c) Values of ${\left(g_{ij}\right)}_{a\to v}$, computed by the sum-product formula, passed from constraint nodes to neighboring variable nodes. (d) Updated a posteriori values for $g_{ij}\left(0\right)$, calculated as the (normalized) product of received messages and prior probabilities.

Figure 4

Performance of iterative BP decoding algorithm. The probability of a decoding error is plotted as a function of the number $N$ of encoded spins for various values of the physical error probability $\varepsilon$. Each data point was obtained by averaging over 5000 noise realizations, and for each realization the BP algorithm was iterated five times, incorporating information about loops up to length $33=2^5+1$. The decoding performance is significantly better than for a single BP iteration, where only loops of size $\le 3$ are considered. The logical error probability starts at $p_{\mathrm{fail}}^{\mathrm{total}}=\varepsilon$ for $N=2$ and rises with $N$ until the onset of exponential decay, which begins for a smaller value of $N$ than suggested by Eq. (7).