How Many Qubits Are Needed For Quantum Supremacy?
(IEEESpectrum) 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. 1) Instantaneous Quantum Polynomial-Time (IQP) circuits are an especially simple way to connect qubits into quantum circuits. 2) Quantum Approximate Optimization Algorithm (QAOA) circuits are more advanced, using qubits to find good solutions to optimization problems. 3) Finally, boson sampling circuits use photons instead of qubits, analyzing the paths such photons take after interacting with one another.
“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,” says Alexander Dalzell, a quantum physicist at the California Institute of Technology in Pasadena. 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.”