Quantum Characterization

I continue to try to understand how to characterize the algorithmic complexity of different quantum computer use cases and how to characterize the ability of existing quantum computer to run them. Imagine both are curves. I want to know when in the future they meet for each use-case.

To algorithmic characterization. There seem to be three dimensions:

• Minimal logical qubit count - min logical qubits necessary to run the algorithm

• Toffoli gate count - Each logical operation in an algorithm is a gate. There are low-cost gates, which include a class called Clifford gates, and high cost gates, which include a class called Toffoli. The 3/30/26 Babbush et Al paper in my previous piece describes the Toffoli gate count of solving 256-bit ECC as 90M.

• Circuit Depth - This is the notion of parallelism. A quantum algorithm is described as a circuit. The quantum version of a circuit diagram is a line for each logical qubit with “notes” describing gates. Like music.

Imagine Babbush’s ECC-256 operation. 1,200 lines. 90 million “notes” on those lines. If every note had to play one after another - as a solo - the circuit depth would be 90 million.

But if the algorithm can be parallelized, you have an orchestra. With 1,200 qubit wires, many gates fire at the same time. Each beat of the song is one “layer” of simultaneous gates. Circuit depth counts the beats, not the notes.

So gates = notes. Circuit depth = # of beats to play the piece. Average number of parallel gates that can be executed per time step is gate count / circuit depth.

Later, I’ll put together how the algorithms for different quantum use-cases are characterized but gate count, logical qubit count, and circuit depth.

So now I will attempt to characterize the hardware capabilities of quantum computers, so that we can say X algorithm can run on Y computer when it is created in Z months.

• Physical qubit count

• Overhead ratio - How many physical qubits are necessary to represent a logical qubit. This ratio improves (decrease) with novel error correction techniques and algorithm

• Logical gate speed - How long it takes to run a single gate

• Coherence time - How long the entire computer can hold its state before noise from the environment disrupts it.

• Below Threshold Error correction - Whether the computer can find qubits in an error state and fix them without creating net more errors.

For a given algorithm requiring m logical qubits and a circuit depth of d steps, the machine must have physical qubit count ÷ overhead ratio ≥ m. Without below-threshold error correction, d × logical gate speed must be less than the coherence time. With below-threshold error correction, this constraint disappears.

Google’s Babbush Et All paper posits that 256-bit ECC curve encryption can be cracked with 90M Toffoli gates running on 1200 logical qubits. Here state of the art quantum computer capabilities per Claude

Note the two columns on the right are planned or theoretical. What screams here is that the max logical qubit reported count (there are probably pretty good unreported quantum computers) is 98.

If we then ask claude to extrapolate when current progress will reach 1200 logical qubits, we get 2029-2031. Interesting!