Error Correction
Code Distance
The minimum number of physical errors that can cause an undetected logical error; higher distance means stronger protection.
Definition
Code distance is the single most important number describing how well a quantum error-correcting code protects information. It counts how many qubits would have to go wrong, in just the right way, before the code fails to notice. A distance-3 code can fix any single error, a distance-5 code can fix any two, and a distance-7 code any three. Making the distance larger is how engineers make logical qubits more reliable, at the price of using more physical qubits.
In depth
The importance of distance comes from the way logical errors scale. If physical errors occur independently with probability p, and p is below the code's threshold, the logical error rate falls exponentially with distance, roughly as p over p threshold to the power of (d plus 1) over 2. Increasing the distance by 2 multiplies the suppression by a constant factor, which Google called the error suppression factor, lambda. In its 2024 Willow experiment, going from distance 3 to 5 to 7 reduced the logical error rate by about a factor of 2 at each step.
The cost is qubit count. In the surface code, the qubit overhead grows as the square of the distance, so a distance-25 logical qubit uses on the order of 1,000 physical qubits. To run a long algorithm with millions of operations at acceptable overall failure, resource estimates often need distances in the 20s, which is why useful fault-tolerant machines are projected to need hundreds of thousands to millions of physical qubits. Higher-rate codes, such as quantum LDPC codes, aim to reach similar protection with far fewer qubits.
Distance also determines how fast the decoder must work and how long a logical operation takes, since lattice surgery operations take about d rounds of syndrome measurement. Experimenters study distance by running the same code at several sizes and checking that the logical error falls, which is the signature of operating below threshold.
Technical Definition
The distance d of a stabilizer code is the minimum weight of a Pauli operator that commutes with all stabilizers but is not in the stabilizer group, that is, a nontrivial logical operator. The code can correct up to floor of (d minus 1) over 2 arbitrary errors and detect up to d minus 1. For the rotated surface code, a distance-d patch uses d squared data qubits and d squared minus 1 measurement qubits.
Visual Explanation: An Analogy
Think of a message sent in triplicate. If one copy gets garbled you can tell which is right by majority, and if two copies are garbled you cannot. The number of garbled copies that the scheme survives is its distance, and sending more copies raises it.
Key facts
| Item | Detail |
|---|---|
| Correctable errors | Up to (d minus 1) over 2 arbitrary errors |
| Surface code size | About 2 d squared minus 1 physical qubits per logical qubit |
| Logical error scaling | Falls roughly exponentially with d when physical error is below threshold |
| Willow result | Distances 3, 5, and 7 showed logical error falling by about a factor of 2 per step (2024) |
| Typical large-scale need | Distances in the 20s for useful algorithms |
Where the idea comes from
The concept comes from classical coding theory, where Hamming introduced code distance in 1950. For quantum codes, it was part of the original stabilizer formalism of Gottesman, and experimental distance-scaling studies began with Google's distance-3 and distance-5 surface codes in 2021 and 2023.
Real-World Use Cases
- Choosing how large a logical qubit must be for a target error rate.
- Estimating the physical qubit requirements of fault-tolerant algorithms.
- Demonstrating below-threshold operation by comparing several distances.
- Setting decoder speed requirements and lattice surgery timing.
How it differs from related ideas
- Code distance measures protection strength, while code rate measures how many logical qubits per physical qubit.
- Larger distance means more qubits and slower operations, so it is a tradeoff.
- A code can have large distance but a high threshold needed to benefit from it.
Common Misconceptions
- A higher distance does not help if the physical error rate is above threshold. Errors then grow with distance.
- Distance is not the number of qubits. It is the smallest number of errors that defeat the code.
- A distance-3 code cannot correct two errors in general.
Frequently asked questions
What is code distance?
The smallest number of physical qubit errors that can produce a logical error the code cannot detect.
Why is it important?
Because logical error rates fall exponentially with distance when the hardware is below threshold, making distance the main knob for reliability.
How many qubits does a larger distance need?
For the surface code, roughly twice the distance squared, so doubling the distance quadruples the qubit count.
Related Terms
Keep exploring
- Algorithm: Quantum Error-Correcting Codes (Shor Code, Surface Code)
- Hardware: Google Willow