En septembre dernier, Google a annoncé avoir atteint « la suprématie quantique » (quantum supremacy). Mais qu’est-ce que cela signifie vraiment? Et pour quel type d’algorithme ? Faut-il, à l’instar des sites conspirationnistes, comprendre que Google a la capacité détruire « military and blockchain grade cryptography security algorithm » ? 😉

Définition de la suprématie quantique.
Ce mot n’a pas été employé par hasard ni par triomphalisme, il correspond à une définition bien précise donnée en 2012 par le professeur John Preskill dans une publication [24].
« We therefore hope to hasten the onset of the era of quantum supremacy, when we will be able to perform tasks with controlled quantum systems going beyond what can be achieved with ordinary digital computers. »
Dans l’article il ajoute 3 précisions importantes :

• « One way to achieve such “quantum supremacy” would be to run an algorithm on a quantum computer which solves a problem with a super-polynomial speedup relative to classical computers »
  C’est à  dire que la complexité algorithme devra être suffisamment élevée pour prouver la supériorité du quantique.Il propose une complexité algorithmique de type super-polynomiale, supérieure à une complexité polynomiale O(n²) mais pas forcément exponentielle O(2ⁿ).
• « To realize that dream, we must overcome the formidable enemy of decoherence »
  Il précise ici qu’il faudra résoudre un des obstacles majeurs actuels, la fiabilité des mesures liée à la décohérence incontrôlée.
• « It seems that superpolynomial speedups are possible only for problems with special structure well matched to the power of a quantum computer. We do not expect superpolynomial speedups for the worst-case instances of problems in the NP class, such as 3-SAT or the Traveling Salesman Problem. »
  Pour l’auteur, seuls certains algorithmes super-polynomiaux pourront bénéficier de la puissance quantique. Le classique problème du voyageur de commerce en est un contre-exemple.

Les travaux publiés par Google : Suprématie ou pas ?

Dans le résumé de cet article qui fera date [25], les auteurs de Google AI Quantum annoncent la couleur : « While our processor takes about 200 seconds to sample one instance of the quantum circuit 1 million times, a state-of-the-art supercomputer would require approximately 10,000 years to perform the equivalent task. » pour aussitôt préciser que  « However, realizing the full promise of quantum computing (e.g. Shor’s algorithm for factoring) still requires technical leaps to engineer fault-tolerant logical qubits ». Car en vérité, si la suprématie, du point de vue de la définition donnée par Preskill est respectée, l’utilité de l’algorithme proposé est discutable. Sur ce sujet, Preskill s’est exprimé en octobre 2019 (voir paragraphe suivant) et a expliqué : « In 2012, I proposed the term “quantum supremacy” to describe the point where quantum computers can do things that classical computers can’t, regardless of whether those tasks are useful. »

De toute façon, algorithme utile ou pas, l’effort considérable pour créer une machine à 53 qubits suffisamment stable et précise pour démontrer cette suprématie est, en soit, un progrès énorme pour la communauté quantique. Preskill ajoute même : « However, the demonstration is still significant. By checking that the output of their quantum computer agrees with the output of a classical supercomputer (in cases where it doesn’t take thousands of years), the team has verified that they understand their device and that it performs as it should. Now that we know the hardware is working, we can begin the search for more useful applications. »

Que fait cet algorithme ?

Le but de l’algorithme est de calculer la distribution de motifs aléatoires (des bitstrings comme 0000101).
Pour cela, un processeur spécifique, nommé « Sycamore », a été créé. C’est une matrice 2D de 54 qubits, chacun étant relié à ses 4 voisins. Le programme est composé de 53 qubits (1 n’a pas fonctionné), de 1113 portes à 1 seul qubit, et 430 portes à 2 qubits (pour intriquer, on les voit bien sur le schéma ci-dessus).
L’objectif est « d’emmeler » (entangle) tous ces qubits par des suites d’opérations logiques répétées afin de créer des chaînes aléatoires. « We design the circuits to entangle a set of quantum bits (qubits) by re- peated application of single-qubit and two-qubit logical operations. Sampling the quantum circuit’s output pro- duces a set of bitstrings, e.g. {0000101, 1011100, …}. Due to quantum interference, the probability distribution of the bitstrings resembles a speckled intensity pattern produced by light interference in laser scatter, such that some bitstrings are much more likely to occur than others. Classically computing this probability distribution becomes exponentially more difficult as the number of qubits (width) and number of gate cycles (depth) grows. »

Pour autant, le problème de la fiabilité des résultats est toujours là. L’article donne les taux d’erreurs unitaires qui restent élevés. Mais l’astuce est de répéter l’opération des millions de fois pour que, statistiquement, les erreurs se lissent et deviennent acceptables. « We predict a total fidelity of 0.2%. This fidelity should be resolvable with a few million measurements. (…) For the largest circuit with 53 qubits and 20 cycles, we collected Ns = 30×106 samples (…) With 5σ confidence (Note : 5 écart-type), we assert that the average fidelity of running these circuits on the quantum processor is greater than at least 0.1%. »

Enfin, l’article termine en expliquant comment ils ont simulé le temps de calcul sur un super-ordinateur. A noter qu’à partir de 43 qubits, il n’y a plus assez de RAM pour simuler un état quantique (2^43 = environ 10^13, on est déjà sur du To de RAM). On comprend donc la difficulté d’un ordinateur classique à simuler ce réseau interconnecté de 53 qubits, même en utilisant la puissance de frappe de Google : « On Google Cloud servers, we estimate that perform- ing the same task for m = 20 with 0.1% fidelity using the SFA algorithm would cost 50 trillion core-hours and consume 1 petawatt hour of energy. » Bons princes, ils ont intégrés le taux de fiabilité de 0,1% qui réduit le coût de calcul par 1000 : « we account for the computational cost scaling with FXEB, e.g. the 0.1% fidelity decreases the cost by 1000″. Côté superordinateur (Jülich Supercomputer Center), ce n’est pas mieux, ils ont simulé le cas simplifié à 43 qubits sur une machine ayant 100k coeurs et 250 TB de RAM.
Le résultat est effarant si l’on extrapole les 200 secondes pour 1 million d’itérations demanderaient 10 000 années sur un ordinateur classique. La claque.

L’article se termine avec une note optimiste sur l’évolution des progrès quantiques qui tranche avec la vision des quantum-sceptiques : « We expect their computational power will continue to grow at a double exponential rate: the clas- sical cost of simulating a quantum circuit increases exponentially with computational volume, and hardware im- provements will likely follow a quantum-processor equivalent of Moore’s law, doubling this computational volume every few years. »
Bon, l’utilisation de l’algorithme de Shor pour casser les codes militaires n’est pas pour aujourd’hui, mais Google AI Quantum ne lâche rien ! 😉

Et qu’en pense John Preskill, 7 ans après son article ?

Quelques jours après la publication de l’article en question, John Preskill s’exprime sur Quantamagazine.org. Curieusement, il revient sur le terme de « suprémacie » en regrettant les connotations raciales ou hype qu’il véhicule : « The words “quantum supremacy” — if not the concept — proved to be controversial for two reasons. One is that supremacy, through its association with white supremacy, evokes a repugnant political stance. The other reason is that the word exacerbates the already overhyped reporting on the status of quantum technology« . Cela dit, il confirme que c’est le bon mot pour évoquer une telle supériorité.

Sur le fond, il reconnait que l’algorithme n’est pas d’un intérêt énorme (« It is not otherwise a problem of much practical interest« ) mais qu’il a été très bien choisi : « the problem their machine solved with astounding speed was carefully chosen just for the purpose of demonstrating the quantum computer’s superiority. »

Malgré ce bémol, Preskill reste très confiant dans l’avenir de la recherche et estime que cette percée ouvre de nombreuses portes : « However, the demonstration is still significant. By checking that the output of their quantum computer agrees with the output of a classical supercomputer, the team has verified that they understand their device and that it performs as it should. Now that we know the hardware is working, we can begin the search for more useful applications. (…) The quantum supremacy milestone allegedly achieved by Google is a pivotal step in the quest for practical quantum computers. »

La réponse d’IBM (1 mois plus tard)

Le 21 octobre, des chercheurs d’IBM ont publié un article sur leur blog remettant en cause la « suprématie » atteinte par Google. Ils contestent notamment les 10 000 années nécessaires à réaliser une simulation équivalente (« When their comparison to classical was made, they relied on an advanced simulation that leverages parallelism, fast and error-free computation, and large aggregate RAM, but failed to fully account for plentiful disk storage ») , et disent pouvoir implémenter un algorithme Schrödinger-style en 2 jours et demi. « We argue that an ideal simulation of the same task can be performed on a classical system in 2.5 days and with far greater fidelity« . Ambiance.

Au delà de cet aspect technique, c’est la notion même de suprématie quantique qu’IBM refuse et l’article appele la communauté scientifique a davantage d’humilité – surtout a vue de la complexité de comparer des approches quantiques vs traditionnels (taux d’erreur, etc.)  «  … since we already have ample evidence that the term “quantum supremacy” is being broadly misinterpreted and causing ever growing amounts of confusion, we urge the community to treat claims that, for the first time, a quantum computer did something that a classical computer cannot with a large dose of skepticism due to the complicated nature of benchmarking an appropriate metric. »
Bons princes, ils reconnaissent quand même que  » Google’s experiment is an excellent demonstration of the progress in superconducting-based quantum computing, showing state-of-the-art gate fidelities on a 53-qubit device, but it should not be viewed as proof that quantum computers are “supreme” over classical computers. »

Attendons les prochains épisodes de cette quête passionnante…

Et aussi

• Le blog de Google qui parle de l’article en question (23/10/2019)
• L’article revu et publié le 23/10/2019 sur le site de Nature.
• Voir aussi la vidéo de Olivier Ezratty qui parle de la suprématie quantique :  https://youtu.be/03PnMxE_ixU

Dernière mise à jour le 23/10/2019