Un ordinateur quantique doit être extrêmement difficile à simuler par un ordinateur traditionnel. Si ce n'est pas le cas, le premier n'a aucune utilité, il suffit d'utiliser le second…
Le fonctionnement d'un ordinateur quantique parfait est incontestablement difficile à décrire en raison du nombre gigantesque de ses degrés de liberté : les ressources classiques nécessaires augmentent en effet de manière exponentielle avec le nombre de bits quantiques (qubits).
Les embryons d'ordinateur quantique qui existent aujourd'hui ne sont cependant pas parfaits : leur « fidélité » décroît de façon exponentielle au cours du temps.
En 2019, Google a annoncé que son dispositif avait atteint la suprématie quantique, car il avait accompli en quelques minutes une tâche qui demande environ 10 000 ans aux supercalculateurs les plus puissants.
Des chercheurs remettent en question cette assertion. Au lieu de tenter de simuler un ordinateur quantique parfait, ils ont cherché à simuler un véritable dispositif quantique, qui souffre de décohérence et d'imprécision. Pour cela, ils ont développé un algorithme qui utilise la « compression d'états quantiques » : de même que la compression d'images peut réduire le volume de leur stockage au prix d'une perte de résolution, la compression d'états quantiques permet d'accélérer leur simulation de façon exponentielle, en échange d'une perte d'information, analogue à celle générée par la décohérence.
Ils démontrent que la simulation d'un ordinateur quantique (imparfait) sur un ordinateur portable donne des résultats similaires à ceux de l'expérience de Google, au moins pour certaines tâches. Avec un algorithme quelques milliards de fois plus rapide que celui de Google !
Ces résultats suggèrent que les ordinateurs quantiques actuels ne possèdent qu'une infime partie de la puissance de calcul que possèderait un ordinateur quantique parfait. Pour tendre vers cette puissance, il serait donc inutile d'augmenter le nombre de qubits, mieux vaudrait améliorer leur fidélité. Une tâche extrêmement ardue pour laquelle il n'existe pas de méthode systématique.