What does reliable quantum computation cost?

The question in perspective

A physical error rate that looks small for one gate can be unacceptable for a computation with billions of operations. The fundamental question is whether reliability can improve as a machine grows, and what extra qubits, time, control, and classical processing that improvement requires.

Why redundancy can change the scaling

Begin with a restricted noise model: three qubits independently suffer a bit flip with probability \(p\). Encode \(\alpha\ket0+\beta\ket1\) as \(\alpha\ket{000}+\beta\ket{111}\), and assume perfect parity checks and correction. Majority correction fails for two or three flips:

\[p_L=3p^2(1-p)+p^3=3p^2-2p^3.\]

The leading failure is quadratic rather than linear. At \(p=0.01\), \(p_L=0.000298\). Parity measurements reveal which bits disagree without reading the encoded amplitudes. This code does not correct arbitrary phase errors, and its perfect-check assumption hides real hardware costs.

A code’s distance \(d\) is the minimum weight of an undetectable logical error. It can correct arbitrary errors supported on at most \(\lfloor(d-1)/2\rfloor\) qubits when syndrome extraction is ideal. In a below-threshold operating regime, an illustrative odd-distance phenomenological fit is

\[p_L(d)\approx A\left(\frac p{p_{\rm th}}\right)^{(d+1)/2}.\]

Here \(p_L\) is failure per protected location, \(p_{\rm th}\) is a threshold for a specified noise/circuit/decoder model, and \(A\) is a fitted constant. It is not a universal law. For \(L\) protected locations, the union bound gives \(p_{\rm fail}\leq Lp_L\) when each location has failure probability at most \(p_L\); independence is unnecessary for that inequality.

If the model is applicable and \(p<p_{\rm th}\), targeting total failure \(\varepsilon\) suggests

\[d\gtrsim\frac{2\ln(AL/\varepsilon)}{\ln(p_{\rm th}/p)}-1.\]

For \(A=0.1,p/p_{\rm th}=0.1,L=10^6,\varepsilon=0.01\), this gives \(d\geq13\) within the fit. A planar surface-code patch uses order \(d^2\) qubits; protected gates and additional state factories require further resources.

What is established

Stabilizer codes supply a framework for protecting quantum information. Concatenated-code constructions establish fault-tolerant scaling under specified noise assumptions. A threshold theorem is conditional on those assumptions.

Constant-overhead proposals and low-overhead memory constructions show why surface-code estimates are not universal limits. Memory performance alone does not establish the cost of a universal gate set or a complete application.

What remains unresolved

Which code and architecture minimize useful application cost under realistic leakage, correlations, connectivity, and decoding latency? A code’s asymptotic parameters cannot answer this alone. Comparisons need a target computation, a total failure criterion, a realizable gate schedule, and a calibrated noise model.

A concrete next investigation

Reproduce: derive the repetition-code polynomial and compare it with Monte Carlo sampling. Then add imperfect parity measurements and identify why a single majority vote is insufficient.

Check: reconstruct the distance estimate above, round up to an allowed distance, and report sensitivity to \(A\) and \(p/p_{\rm th}\).

Extend: compare two codes for the same logical circuit, including syndrome rounds, routing, auxiliary states, and classical latency. A defensible improvement reduces a stated resource without moving omitted costs elsewhere.

Selected references

1. Stabilizer Codes and Quantum Error Correction

   Daniel Gottesman. 1997. Doctoral thesis

   Develops the stabilizer framework used to describe many quantum error-correcting codes.

2. Concatenated Quantum Codes

   Emanuel Knill, Raymond Laflamme. 1996. Research paper

   A construction supporting fault-tolerant scaling under specified error assumptions.

3. Fault-Tolerant Quantum Computation with Constant Overhead

   Daniel Gottesman. 2013. Research paper

   Asymptotic constant qubit-overhead constructions with stated code and fault-tolerance requirements.

4. High-threshold and low-overhead fault-tolerant quantum memory

   Sergey Bravyi et al.. 2023. Research paper

   Studies a low-overhead memory protocol with explicit code, connectivity, decoding, and noise assumptions.

Years refer to first arXiv submission. Publication details are available in the linked records.