Quantum Goalposts

Two “bombshell” quantum papers came out last week.

The first from, Google which simulated a novel quantum circuit on a classical computer and found that the 256-bit elliptic curve cryptography (ECC) could theoretically be cracked with 500,000 physical qubits. The state of the art estimate prior to publication was 9 million.

The second, from Oratomic, a quantum computing startup, and researchers from Caltech and Berkeley also simulated a novel quantum circuit, this one using neutral atoms, and found it could theoretically crack 256-bit ECC with 26,000 physical qubits.

The most interesting charts from these papers are the ones showing the physical qubit estimates for cracking popular crypto over time decrease exponentially. Here’s the chart from the Oratomic paper show 256-ECC and RSA-2048:

And this one is from the Google paper showing number of qubits necessary to crack RSA-2048.

Note that both these charts are on log scales. Fast progress.

Also worth pointing out that the best quantum computer in existence today can only run 48 logical qubits on 98 physical qubits with a 1/1000 error rate per gate. Per Google paper, cracking 256-ECC with a low number of qubits requires on the order of 10^8 gates.

You can read the tea leaves on the logical qubit/time chart of quantum computers but either way you slice there’s a big gap between 98 and 26,000, the number suggested by the Oratomic paper. Of course, the quantum computers that crack crypto will be run by national intelligence services, don’t publish their benchmarks, and will be effective for a long time before the world knows. Think WWII Enigma. Fifty years from now, I’d say there’s a 5% chance some government document is declassified showing the NSA was cracking 256-ECC as of today. 40% it’s as of 2028.

Code-cracking is an amazing nation-state use-case for a quantum computer, but not great for private enterprise because, well, the act is considered criminal.

What I’m more interested is in modeling small molecules for drugs and materials. Put optimistically and likely in a way that would make a quantum computer research cringe: the materials of Star Trek are likely to come from a quantum computer. I actually think more likely than from AI. Or perhaps an AI programming a quantum computer.

I am digressing a bit. An interesting hypothesis of the rapidly decreasing number of physical qubits to crack RSA is that there is a similar decrease in physical qubit (PQ) requirements for other quantum use cases, likely toward some asymptote.

I’m not sure how to think about this asymptote yet. Beauregard in ‘02 found a way to execute Shor’s algorithm on RSA-2048 with 4099 logical qubits. There is some minimum number overhead ratio, which is the number of physical qubits per logical qubit.

So what I want to do is take a few small molecule use cases, multiply them by an asymptotic overhead ratio to determine how many physical qubits they need. I’ll also need to estimate the circuit depth (# gates) for this problem. Then I can look at how far along actual quantum computers are (not simulations) and estimate when the computer will be capable of the problem.