High-Threshold Low-Overhead Fault-Tolerant Classical Computation and the Replacement of Measurements with Unitary Quantum Gates

von Neumann’s classic “multiplexing” method is unique in achieving high-threshold fault-tolerant classical computation (FTCC), but has several significant barriers to implementation: (i) the extremely complex circuits required by randomized connections, (ii) the difficulty of calculating its performance in practical regimes of both code size and logical error rate, and (iii) the (perceived) need for large code sizes. Here we present numerical results indicating that the third assertion is false, and introduce a novel scheme that eliminates the two remaining problems while retaining a threshold very close to von Neumann’s ideal of $1/6$. We present a simple, highly ordered wiring structure that vastly reduces the circuit complexity, demonstrates that randomization is unnecessary, and provides a feasible method to calculate the performance. This in turn allows us to show that the scheme requires only moderate code sizes, vastly outperforms concatenation schemes, and under a standard error model a unitary implementation realizes universal FTCC with an accuracy threshold of $p<5.5\%$, in which $p$ is the error probability for 3-qubit gates. FTCC is a key component in realizing measurement-free protocols for quantum information processing. In view of this, we use our scheme to show that all-unitary quantum circuits can reproduce any measurement-based feedback process in which the asymptotic error probabilities for the measurement and feedback are $(32/63)p\approx 0.51p$ and $1.51p$, respectively.

Figure 1

Unitary constructions for the (a) AMP and (b) MAJ3 gates defined in the text. The unitary version of AMP copies the input qubit in the computational basis by applying a controlled-not (cnot) gate from this input to each of two qubits prepared in the 0 state. The dashed box is the MAJ1 gate.

Figure 2

(a) Solid line: The inverse of the logical error probability, $p_{\mathrm{ss}}$, for our error correction circuit with a 27-bit code. Dashed line: $1/p_{\mathrm{ss}}$ for a hypothetical concatenation scheme with a threshold of $1/6$ [49, 59]. (b) Solid line: $1/p_{\mathrm{ss}}$ for our scheme with an 81-bit code. Dashed lines: $1/p_{\mathrm{ss}}$ for hypothetical concatenation schemes with thresholds of $1/6$ (upper line), and $1/7$ (lower line). (No such concatenation schemes are known to date.) The inset shows the performance of von Neumann’s scheme (dark line) against the new scheme (light line) for 81 bits, for a range of $ϵ$ in which it is feasible to simulate.

Figure 3

(a) The solid line is $ϵ$ and the dashed line is the resulting error probability for a code with $n=3$. The point at which these lines cross gives the threshold. (b) Here we show the wiring lengths required for a code with $n=4$ (243 bits). Each dot and circle represents a MAJ3 gate, so that the squares indicate a cube of 27 MAJ3 gates (an $n=3$, 81-bit code) viewed from the top. The blue line encircles three of these cubes that form a single $n=4$ code block. The curved solid lines are examples of wires required to implement an and gate on the two code blocks consisting of black dots. The dashed lines are examples of wires required to implement an error correction on an individual code block.