A quantum computer must be extremely difficult to simulate using a traditional computer. After all, if this were not the case, the former would be of no use, as we could just use the latter.

The functioning of a perfect quantum computer is undeniably difficult to describe due to the immense number of its degrees of freedom. Indeed, the classical resources needed increase exponentially with the number of quantum bits (qubits).

However, the embryonic quantum computers that we have today are not perfect, as their "fidelity" decreases exponentially over time.

In 2019, Google announced that its own device had achieved quantum supremacy, having completed in a matter of minutes a task that would take the most powerful supercomputers about 10,000 years to complete.

This claim is being challenged by the researchers. Instead of trying to simulate a perfect quantum computer, they have sought to simulate a real quantum device, which suffers from decoherence and imprecision. For this, they developed an algorithm that uses "quantum state compression". Just as image compression can reduce the volume of image storage at the cost of a loss of resolution, quantum state compression allows accelerating the simulation exponentially in exchange for a loss of information, similar to that generated by decoherence.

The researchers have shown that simulating a (imperfect) quantum computer on a laptop gives results similar to the Google experiment, at least for certain tasks. And with an algorithm that is a few billion times faster than Google's!

These results suggest that current quantum computers only have a tiny fraction of the computing power that a perfect quantum computer would have. In order to get to this level of power, it would in fact be useless to increase the number of qubits; rather, it would be better to improve their fidelity. This is an extremely difficult task for which there is no systematic method.