How Many Qubits Are Needed for Quantum Supremacy?

Quantum computers theoretically can prove more powerful than any supercomputer, and now scientists calculate just what quantum computers need to attain such quantum supremacy," and whether or not Google achieved it with its claims last year.

Whereas classical computers switch transistors either on or off to symbolize data as ones or zeroes, quantum computers use quantum bits-qubits-that, because of the bizarre nature of quantum physics, can be in a state of superposition where they are both 1 and 0 simultaneously.

Superposition lets one qubit perform two calculations at once, and if two qubits are linked through a quantum effect known as entanglement, they can help perform 2² or four calculations simultaneously; three qubits, 2³ or eight calculations; and so on. In principle, a quantum computer with 300 qubits could perform more calculations in an instant than there are atoms in the visible universe.

It remains controversial how many qubits are needed to achieve quantum supremacy over standard computers. Last year, Google claimed to achieve quantum supremacy with just 53 qubits, performing a calculation in 200 seconds that the company estimated would take the world's most powerful supercomputer 10,000 years, but IBM researchers argued in a blog post that an ideal simulation of the same task can be performed on a classical system in 2.5 days and with far greater fidelity."

To see what quantum supremacy might actually demand, researchers analyzed three different ways quantum circuits that might solve problems conventional computers theoretically find intractable. Instantaneous Quantum Polynomial-Time (IQP) circuits are an especially simple way to connect qubits into quantum circuits. Quantum Approximate Optimization Algorithm (QAOA) circuits are more advanced, using qubits to find good solutions to optimization problems. Finally, boson sampling circuits use photons instead of qubits, analyzing the paths such photons take after interacting with one another.

Assuming these quantum circuits were competing against supercomputers capable of up to a quintillion (10¹⁸) floating-point operations per second (FLOPS), the researchers calculated that quantum supremacy could be reached with 208 qubits with IQP circuits, 420 qubits with QAOA circuits and 98 photons with boson sampling circuits.

I'm a little bit surprised that we were ultimately able to produce a number that is not so far from the kinds of numbers we see in devices that already exist," says study lead author Alexander Dalzell, a quantum physicist at the California Institute of Technology, in Pasadena. The first approach we had suggested 10,000 or more qubits would be necessary, and the second approach still suggested almost 2,000. Finally, on the third approach we were able to eliminate a lot of the overhead in our analysis and reduce the numbers to the mere hundreds of qubits that we quote."

The scientists add that quantum supremacy might be possible with even fewer qubits. In general, we make a lot of worst-case assumptions that might not be necessary," Dalzell says.

When it comes to Google, the researchers note that the company's claims are challenging to analyze because Google chose a quantum computing task that was difficult to compare to any known algorithm in classical computation.

I think the claim that they did something with a quantum device that we don't know how to do on a classical device, without immense resources, is basically accurate as far as I can tell," Dalzell says. I'm less confident that there isn't some yet-undiscovered classical simulation algorithm that, if we only knew about it, would allow us to replicate Google's experiment, or even a somewhat larger version of their experiment, on a realistic classical device. To be clear, I'm not saying I think such an algorithm exists. I'm just saying that if it did exist, it wouldn't be completely and totally surprising."

In the end, have we reached quantum computational supremacy when we've done something that we don't know how to do with a classical device? Or do we really want to be confident that it's impossible even using algorithms we might have not yet discovered?" Dalzell asks. Google seems to be pretty clearly taking the former position, even acknowledging that they expect algorithmic innovations to bring down the cost of classical simulation, but that they also expect the improvement of quantum devices to be sufficient to maintain a state of quantum computational supremacy. They rely on arguments from complexity theory only to suggest that extreme improvements in classical simulation are unlikely. This is definitely a defensible interpretation."

Future research can analyze how quantum supremacy estimates deal with noise in quantum circuits. When there's no noise, the quantum computational supremacy arguments are on pretty solid footing," Dalzell says. But add in noise, and you give something that a classical algorithm might be able to exploit."

The scientists detailed their findings online on 17 April in a study accepted in the journal Quantum.