Pour qu’il soit utile, un ordinateur quantique doit être très difficile à simuler sur des ordinateurs traditionnels ; sinon il suffirait d’utiliser ces derniers. Un ordinateur quantique parfait, comme tout système possédant un nombre exponentiel de degrés de liberté, est incontestablement difficile à simuler dans la mesure où les ressources classiques nécessaires augmentent de manière exponentielle avec le nombre de qubits ou la profondeur du circuit (nombre d'opérations par qubit). Les embryons d’ordinateur quantique qui existent aujourd’hui ne sont cependant pas parfaits. Ils se caractérisent par une « fidélité » qui décroit de façon exponentielle avec le temps de calcul.
L'année dernière, Google a affirmé que son dispositif d’ordinateur quantique avait atteint la « suprématie quantique », en accomplissant en quelques minutes une tâche qui prendrait environ 10000 ans au plus gros superordinateur classique. Des chercheurs de notre institut ont remis cette assertion en question. Au lieu de tenter de simuler un ordinateur quantique parfait, les chercheurs ont cherché à simuler un véritable dispositif quantique, dispositif qui souffre de décohérence et d'imprécision. Ils ont développé des algorithmes qui utilisent la compression d'états quantiques.
La compression d’états quantiques, un peu comme la compression d’image, permet d’accélérer la simulation de façon exponentielle en échange d’une perte d’information analogue à celle générée par la décohérence. Les chercheurs démontrent que la simulation d’un ordinateur quantique sur un ordinateur portable traditionnel donne des résultats similaires à ceux de l'expérience de Google, au moins pour certaines tâches. Leur algorithme est quelques milliards de fois plus rapide que l’algorithme de référence 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 l’ordinateur quantique parfait. Les auteurs concluent que, pour augmenter cette puissance, il est inutile d’augmenter le nombre de qubits. Il faut au contraire améliorer leur fidélité, une tâche extrêmement ardue pour laquelle il n’existe pas de méthode systématique.