For it to be useful, a quantum computer must be very difficult to simulate on traditional computers; otherwise it would be enough to use them. A perfect quantum computer, like any system with an exponential number of degrees of freedom, is unquestionably difficult to simulate since the classical resources required increase exponentially with the number of qubits or the depth of the circuit. However, the small “quantum computers” that exist today are far from perfect; they are characterized by a "fidelity" that decreases exponentially with the computing time.

Last year, Google claimed that its quantum computer device had achieved "quantum supremacy", completing in a matter of minutes a task that would take the largest classical supercomputer about 10,000 years to complete. Researchers at our institute have challenged this claim. Instead of trying to simulate a perfect quantum computer, the researchers focused on simulating a real quantum device, a device that suffers from decoherence and imprecision. They developed algorithms that use quantum state compression. Quantum state compression, similar to image compression, allows to accelerate the simulation exponentially in exchange for a loss of information similar to that generated by decoherence. Researchers show that simulating a quantum computer on a traditional laptop gives results similar to those of the Google experiment, at least for certain tasks. Their algorithm is a few billion times faster than Google's reference algorithm. 

These results suggest that today's quantum computers have only a tiny fraction of the computing power that the perfect quantum computer would have. The authors conclude that, to increase this power, it is irrelevant to increase the number of qubits. On the contrary, it is necessary to improve their fidelity, an extremely difficult task for which there is no systematic method.