The December 2022 issue of IEEE Spectrum is here!

Close bar

How Many Qubits Are Needed for Quantum Supremacy?

Whether Google achieved quantum supremacy depends on perspective

3 min read
Quantum computing qubit
Illustration: iStockphoto

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 22 or four calculations simultaneously; three qubits, 23 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 (1018) 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.

The Conversation (1)
Antoni Grzanka09 Jan, 2022

Alexander Dalzell's page is not found (9 Jan 2022). How to understand?

Why Functional Programming Should Be the Future of Software Development

It’s hard to learn, but your code will produce fewer nasty surprises

11 min read
A plate of spaghetti made from code
Shira Inbar

You’d expectthe longest and most costly phase in the lifecycle of a software product to be the initial development of the system, when all those great features are first imagined and then created. In fact, the hardest part comes later, during the maintenance phase. That’s when programmers pay the price for the shortcuts they took during development.

So why did they take shortcuts? Maybe they didn’t realize that they were cutting any corners. Only when their code was deployed and exercised by a lot of users did its hidden flaws come to light. And maybe the developers were rushed. Time-to-market pressures would almost guarantee that their software will contain more bugs than it would otherwise.

Keep Reading ↓Show less