Excellente FAQ sur l'excellence quantique par Scott Aaronson

Il y a quelques jours, un projet d'article de Google sur leur réalisation de la supériorité quantique dans un ordinateur quantique supraconducteur a fuité sur le réseau. Le texte lui-même a été rapidement supprimé, et des rumeurs et des hypothèses, y compris erronées, se sont multipliées autour de lui. L'auteur de l'article est le professeur Scott Aaronson , l'un des principaux spécialistes des algorithmes quantiques, et possède un excellent blog. Dans le dernier article, il répond aux principales questions sur la supériorité quantique.

Du traducteur. Je ne suis pas du tout spécialiste de la complexité algorithmique et des algorithmes quantiques en particulier. Mais le post m'a paru trop intéressant pour ne pas en parler sur Habré, et pour toute erreur de termes ou leur utilisation inhabituelle, merci de me donner un coup de pied en PM.

FAQ sur la suprématie quantique suprême de Scott!

Vous avez déjà vu des histoires - dans le Financial Times , Technology Review , CNET , Facebook, Reddit, Twitter ou ailleurs - qui parlent d'un groupe de Google qui a atteint la supériorité quantique avec un ordinateur supraconducteur à 53 qubits. Ces histoires sont faciles à trouver, je ne les joindrai pas ici, car aucune ne devrait encore exister.

Comme le monde entier le sait maintenant, Google prépare actuellement une grande déclaration sur la supériorité quantique, qui est prévue conjointement avec un article scientifique dans un magazine cool (lequel? Le choix est petit - l'un des deux). J'espère que cela arrivera dans un mois.
Pendant ce temps, la NASA, où travaillent certains des auteurs de l'article, a accidentellement publié une ancienne version de l'article sur un site public. Elle était là pendant une courte période, mais assez longtemps pour être dans le Financial Times, mon courrier et un million d'autres endroits. La spéculation sans faits sur son importance devrait se multiplier.

Il semble que le monde ait été privé du moment pur de «l'atterrissage sur la lune», où la thèse étendue de l'Église-Thuringe est détruite par des preuves expérimentales lors d'une conférence de presse. Ce sera plus comme la fuite des frères Wright - à propos de laquelle des rumeurs et des demi-vérités se sont infiltrées dans l'espace public entre 1903 et 1908, lorsque Will et Orville ont finalement décidé de démontrer leur fuite. (Cette fois, heureusement, tout sera clarifié beaucoup plus rapidement!)
Ce message n'est pas une déclaration officielle ni une confirmation de quoi que ce soit. Bien que les éclairs soient déjà visibles, le tonnerre appartient à un groupe de Google, à l'heure et au lieu de leur choix.

Je veux plutôt arrêter le flux de désinformation et proposer ici, en tant que blogueur et «intellectuel public», ma FAQ Suprême Suprême Suprême quantique de Scott. Vous savez, au cas où vous seriez soudain curieux de connaître la supériorité quantique ou si vous avez toujours voulu savoir ce qui se passerait si soudain une société de recherche de Mountain View ou d'un autre endroit déclarait hypothétiquement que la supériorité quantique avait été atteinte.

Sans plus tarder, le voici:

B1. Qu'est-ce que l'excellence quantique en calcul?

Souvent réduit à une simple «supériorité quantique», le terme fait référence à l'utilisation d'un ordinateur quantique pour résoudre un ensemble spécial de problèmes, dont la solution sur un ordinateur classique utilisant n'importe quel algorithme connu prendrait des ordres de grandeur plus longs - et non pour des raisons aléatoires, mais à partir de en raison de la complexité quantique asymptotique. L'accent est mis ici sur le fait d'être aussi sûr que possible que le problème a été vraiment résolu de manière quantique et vraiment inaccessible de façon classique, et idéalement, cela nous permettra d'atteindre une accélération des calculs dans un avenir proche (avec des ordinateurs quantiques bruyants et non universels que nous avons déjà là ou sera bientôt). Si la tâche est également utile pour quelque chose, tant mieux, mais ce n'est pas nécessaire. L'avion Wright et le tas de bois de Fermi n'étaient pas utiles à eux seuls.

B2. Si Google a vraiment atteint la supériorité quantique, cela signifie -t-il qu'il n'y a plus de code de crack , comme Andrew Young, candidat à la présidence américaine, a récemment fermé ses portes?

Non, ce n'est pas le cas (même si j'aime toujours la candidature de Young).
Il y a deux problèmes. Premièrement, les appareils créés par Google, IBM et autres ont 50-100 qubits et aucune correction d'erreur. Le piratage de RSA à l'aide de l'algorithme Shore nécessitera plusieurs milliers de qubits logiques. Avec des méthodes de correction d'erreurs bien connues, des millions de qubits physiques et une meilleure qualité que celle dont nous disposons actuellement peuvent facilement être nécessaires pour cela. Il ne me semble pas que quiconque soit proche de cela, et nous ne savons pas dans combien de temps ils pourront s'en approcher.

Et le deuxième problème est que même dans l'avenir hypothétique du CQ avec correction d'erreur, nous ne pourrons casser que certains codes, mais pas tous, du moins pour autant que nous le sachions maintenant. Par coïncidence, les clés publiques qui peuvent être piratées incluent la plupart des algorithmes que nous utilisons pour sécuriser Internet: RSA, Diffie-Hellman, cryptographie elliptique, etc. Mais la cryptographie basée sur des clés privées ne devrait pas être affectée. Et il existe également des cryptosystèmes pour les clés publiques (par exemple, basés sur des réseaux) que personne ne sait comment cracker en utilisant QC même après plus de 20 ans d'essais, et il y a des tentatives de basculer vers ces systèmes. Par exemple, voir ma lettre à Rebecca Goldstein .

B3. Quel type de calculs Google prévoit-il de faire (ou a-t-il déjà fait), qui sont considérés comme classiquement complexes.

Bien sûr, je peux vous le dire, mais je me sens stupide en même temps. Le calcul est le suivant: l'expérimentateur génère un circuit quantique aléatoire C (c'est-à-dire une séquence aléatoire de 1 qubit et 2 qubit - entre les voisins les plus proches - des portes, avec une profondeur de 20, par exemple, agissant sur un réseau 2D n = 50-60 qubits). Après cela, l'expérimentateur envoie C à l'ordinateur quantique et lui demande d'appliquer C à l'état initial de 0, de mesurer le résultat dans la base {0,1}, de renvoyer la séquence observable de n bits (chaîne) et de répéter plusieurs milliers ou millions de fois. Enfin, en utilisant sa connaissance de C, l'expérimentateur effectue un contrôle statistique de la conformité du résultat avec la sortie attendue de l'ordinateur quantique.

Cette tâche n'est pas l'une des tâches avec la seule réponse correcte, contrairement à la factorisation des nombres. Le résultat du fonctionnement du schéma C se révèle être une distribution statistique (appelons-le D _C ) sur des chaînes de n bits, à partir de laquelle nous devons sélectionner des échantillons. En fait, généralement D _C peut correspondre à 2 ⁿ lignes - tellement que si le QC fonctionne comme prévu, il ne produira jamais deux fois la même ligne dans la sortie. Il est important que la distribution de D _C ne _soit pas uniforme. Certaines raies sont nées à la suite d'interférences constructives d'amplitudes et ont donc une probabilité plus élevée, et d'autres à la suite de destructions, et ont une probabilité plus faible. Et bien que nous n'obtenions qu'une petite fraction de tous les 2 ⁿ échantillons possibles, nous pouvons vérifier statistiquement la distribution de ces échantillons pour la distribution inégale attendue, et nous assurer que nous obtenons quelque chose qui est difficile à reproduire classiquement.

TL; DR, un ordinateur quantique est invité à appliquer une séquence aléatoire (mais connue) d'opérations quantiques - non pas parce que nous sommes intéressés par le résultat, mais parce que nous essayons de prouver que le CQ peut effectuer cette tâche clairement définie mieux qu'un ordinateur classique.

B4. Mais si un ordinateur quantique exécute simplement du code indésirable, dont le seul but est d'être difficile pour la simulation classique, qui s'en soucie? N'est-ce pas un gros over-pie avec ... rien?

Non. Bien sûr, ce n'est pas une tarte avec tout ce qui est savoureux, mais au moins une tarte avec quelque chose.
Ayez au moins un peu de respect pour l'immensité de ce dont nous parlons ici et le genre de génie de l'ingénierie qu'il a fallu pour traduire cela en réalité. Avant la supériorité quantique (KP), les sceptiques KP riaient simplement que même après des milliards de dollars et plus de 20 ans de travail, un ordinateur quantique ne peut toujours pas faire quelque chose de plus rapide que votre ordinateur portable. Du moins pas en utilisant la quantique. Après avoir atteint la suprématie quantique dans le monde, ils ne rient plus. La superposition de 2 ⁵⁰ ou 2 ⁶⁰ nombres complexes a été calculée en utilisant une ressource de temps et de volume de données beaucoup plus petite que 2 ⁵⁰ ou 2 ⁶⁰

Je parle de l'avion Wright uniquement parce que l'écart entre ce dont nous parlons et le déni, quelque chose que je vois dans différentes parties d'Internet, est complètement incompréhensible. C'est comme si vous pensiez qu'il était impossible de voler en principe, puis vous avez vu un avion en bois fragile - cela ne pourrait pas ébranler votre foi, mais cela ne devrait certainement pas le renforcer.
Avais-je raison, m'inquiétant il y a de nombreuses années que le battage médiatique constant au sujet des réalisations bien moindres du KK fatiguera les gens et qu'ils s'en soucieront quand quelque chose de vraiment intéressant se produira enfin?

B5. Il y a de nombreuses années, vous avez accusé les masses de leur enthousiasme pour D-Wave et de leurs prétentions à un avantage quantique étonnant dans les problèmes d'optimisation utilisant le recuit quantique. Vous leur reprochez maintenant leur manque d'enthousiasme pour la supériorité quantique. Pourquoi es-tu si capricieux?

Parce que mon objectif n'est pas de déplacer le niveau d'enthousiasme dans une direction clairement choisie, mais d'avoir raison. Avec le recul, n’avais-je pas principalement raison à propos de D-Wave, même lorsque mes déclarations me rendaient très impopulaire dans certains milieux? Eh bien, maintenant j'essaie d'avoir raison sur la supériorité quantique aussi.

B6. Si les calculs de supériorité quantique sont simplement basés sur des échantillons d'une distribution de probabilité, comment peut-on vérifier qu'ils sont faits correctement?

Merci d'avoir demandé! C'est précisément le sujet sur lequel moi et d'autres avons développé de nombreuses bases théoriques au cours des dix dernières années. J'ai déjà dit la version courte dans ma réponse B3: vous testez cela en exécutant des tests statistiques sur les échantillons que l'ordinateur quantique donne pour vérifier qu'ils sont concentrés autour des pics de la distribution de probabilité aléatoire D _C. Une manière pratique de le faire, que Google appelle le «test d'entropie croisée linéaire», consiste simplement à additionner tous les Pr [C donne s _i ] pour tous les échantillons s ₁ , ..., s _k que KK a renvoyés, puis déclarer le test réussi si et seulement si la somme dépasse un certain niveau - disons, bk / 2 ⁿ , où b est une constante entre 1 et 2.

Honnêtement, pour appliquer ce test, vous devez calculer toutes les probabilités que Pr [C donne s _i ] sur un ordinateur classique - et la seule façon connue de le faire est d'itérer sur une période de ~ 2 ⁿ . Mais cela dérange-t-il quelqu'un? Non, si n = 50, et que vous cherchez sur Google et que vous pouvez compter des nombres comme 2 ⁵⁰ (bien que vous n'obtiendrez pas 2 ¹⁰⁰⁰ , ce qui est supérieur à Google , khe-khe). Après avoir chassé un grand groupe de cœurs classiques pendant, disons, un mois, vous vous retrouverez avec le résultat que le CC a produit en quelques secondes - en même temps, assurez-vous que le CC est plus rapide de quelques commandes. Néanmoins, cela signifie que les expériences basées sur l'échantillonnage sont presque spécialement conçues pour les appareils avec environ 50 qubits. Même avec 100 qubits, nous ne savons pas comment garantir le résultat même en utilisant toute la puissance de calcul disponible sur Terre.
(Je note séparément que ce problème est spécifique uniquement aux expériences d'échantillonnage, similaire à ce qui est en cours. Si vous avez utilisé l'algorithme Shor pour factoriser un nombre à 2000 chiffres, vous pouvez facilement vérifier le résultat en multipliant simplement tous les facteurs et en vérifiant leur simplicité. Exactement ainsi si KK est utilisé pour simuler une biomolécule complexe, vous pouvez vérifier le résultat en expérimentant la molécule.)

B7. Attends un instant. Si les ordinateurs classiques ne peuvent vérifier les résultats d'une expérience sur la supériorité quantique que dans un mode où les ordinateurs classiques peuvent encore simuler une expérience (quoique très lentement), comment parler de «supériorité quantique»?

Et bien toi. Avec une puce à 53 qubits, vous voyez l'accélération plusieurs millions de fois, et vous pouvez toujours vérifier le résultat et également vérifier que l'accélération croît de façon exponentielle avec le nombre de qubits, comme le prédit l'analyse asymptotique. Ce n'est pas anodin.

B8 Existe-t-il des preuves mathématiques qu'aucun ordinateur classique rapide ne peut battre les résultats d'une expérience KP basée sur l'échantillonnage?

Pas pour le moment. Mais ce n'est pas la faute des chercheurs de supériorité quantique! Tant que les théoriciens ne peuvent pas prouver même des hypothèses de base, telles que P ≠ NP ou P ≠ PSPACE, et sans cela, nous ne pouvons pas exclure inconditionnellement la possibilité d'une simulation classique rapide. Le mieux que nous puissions espérer est la complexité conditionnelle. Et nous avons quelques résultats à ce sujet, par exemple, un article sur l' échantillonnage des bosons ou un article de Bouldand et al. sur la complexité # P moyenne du calcul des amplitudes des circuits aléatoires, ou mon article avec Lijie Chen ("Fondements théoriques de la complexité des expériences de suprématie quantique"). La question ouverte la plus importante dans ce domaine, à mon avis, est la preuve des meilleures difficultés conditionnelles.

B9. Y a-t-il une utilité pour l'échantillonnage de la supériorité quantique?

Jusqu'à récemment, la réponse était évidemment non! (Et je sais, parce que j'étais moi-même une de ces personnes). Récemment, cependant, la situation a changé - par exemple, grâce à mon protocole de randomisation certifié , qui montre comment le KP basé sur l'échantillonnage peut être utilisé indépendamment pour générer des bits qui peuvent être prouvés aléatoires même pour un tiers sceptique (sous des hypothèses sur les calculs). Celui-ci a à son tour une application dans la crypto-monnaie et d'autres protocoles cryptographiques. J'espère que de telles applications arriveront bientôt.

B10. Si les expériences sur la supériorité quantique produisent des bits aléatoires, pourquoi est-ce intéressant du tout? N'est-il pas possible de convertir trivialement des qubits en bits aléatoires en les mesurant simplement?

L'essentiel est que QC génère des bits aléatoires distribués de manière non uniforme. Au lieu de cela, il crée une sélection à partir d'une distribution de probabilité corrélée complexe sur des chaînes de 50 à 60 bits. Dans mon protocole, les écarts par rapport à l'uniformité jouent un rôle central dans la façon dont le QC convainc le sceptique qu'il a réellement sélectionné des bits aléatoires plutôt que d'utiliser une sorte de générateur pseudo-aléatoire en secret.

B11. Des décennies d'expériences de mécanique quantique, par exemple, avec violation de l'inégalité de Bell, n'ont-elles pas démontré une supériorité quantique?

C'est une question purement lexicale. Ces expériences ont démontré d'autres types de supériorité quantique: par exemple, dans le cas de l'inégalité de Bell, elles peuvent être appelées «supériorité de corrélation quantique». Ils n'ont pas montré de supériorité informatique quantique, c'est-à-dire la capacité de trouver quelque chose d'inaccessible à un ordinateur classique (où la simulation classique n'a pas de restrictions spatiales localement, etc.). De nos jours, lorsque les gens utilisent l'expression «supériorité quantique», ils signifient la supériorité informatique quantique.

B12. Malgré cela, il n'existe pas d'innombrables exemples de matériaux et de réactions chimiques difficiles à simuler classiquement, et des simulateurs quantiques spécialement construits (tels que ceux du groupe Lukin à Harvard). Pourquoi ne sont-ils pas considérés comme une supériorité informatique quantique?

Dans les définitions de certaines personnes, elles sont prises en compte! La principale différence avec un ordinateur Google est qu'il a un ordinateur entièrement programmable - vous pouvez entrer n'importe quelle séquence arbitraire de portes à 2 qubits (pour les qubits voisins) en entrant simplement les commandes d'un ordinateur classique.

En d'autres termes, les sceptiques de KP ne peuvent plus se moquer de façon moqueuse que, bien sûr, les systèmes quantiques sont difficiles à simuler classiquement, mais c'est simplement parce que la nature est généralement difficile à simuler, et vous ne pouvez pas reprogrammer la molécule aléatoire trouvée sur le terrain dans un ordinateur pour se simuler elle-même vous. Selon toute définition raisonnable, les appareils supraconducteurs créés par Google, IBM et d'autres sont des ordinateurs au sens plein du terme.

B13 Avez-vous (Scott Aaronson) inventé le concept d'excellence quantique?

Non. J'ai joué un rôle dans son développement et, par exemple, Sabina Hosenfelder, entre autres, m'a attribué à tort la paternité de l'idée. Le terme «supériorité quantique» a été proposé par John Preskill en 2012, bien que dans un sens, l'idée de base soit apparue à l'aube des contributions quantiques au début des années 80. En 1994, l'utilisation de l'algorithme de Shore pour factoriser un grand nombre est devenue la principale expérience pour tester la supériorité quantique, bien que pour l'instant cela soit encore trop difficile à produire.

L'idée clé selon laquelle l'échantillonnage peut être utilisé à la place a été, pour autant que je sache, proposée pour la première fois par Barbara Terhal et David DiVincenzo dans un article de 2002. L'effort actuel sur un PC échantillonné a commencé vers 2011, quand Alex Arkhipov et moi avons publié notre article sur l' échantillonnage bosonique , et Bremner, Jozsa et Shepherd ont publié de manière indépendante un article sur les modèles de Hamiltoniens de navettage . Ces articles ont montré non seulement des systèmes quantiques «simples» et non universels qui peuvent résoudre des problèmes d'échantillonnage manifestement complexes, mais aussi que l'existence d'un algorithme classique efficace signifierait une chute de la hiérarchie polynomiale . Arkhipov et moi avons également jeté les bases de l'argument selon lequel même des versions approximatives de l'échantillonnage quantique peuvent être classiquement complexes.

Autant que je sache, l'idée de «circuits d'échantillonnage aléatoire» - c'est-à-dire de générer un problème d'échantillonnage complexe en sélectionnant au hasard une séquence de portes à 2 qubits dans, disons, une architecture supraconductrice - leur correspondance est née, que j'ai commencée en décembre 2015, y compris John Martinis, Hartmut Neven , Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg et autres. Le fil était intitulé «Problèmes d'échantillonnage difficiles avec 40 Qubits» et la lettre commençait par «Désolé pour le spam».Dans ce document, j'ai discuté des divers avantages et inconvénients de trois options pour démontrer un avantage quantique à l'aide de l'échantillonnage: (1) circuits aléatoires, (2) Hamiltoniens de navettage, (3) échantillonnage des bosons. Après que Greg Cooperberg ait défendu l'option (1), un consensus s'est rapidement formé que (1) serait vraiment la meilleure option d'un point de vue technique, et que si nous n'avons pas encore de justification théorique satisfaisante pour (1), nous pouvons d'une manière ou d'une autre contourner cela.

Après cela, l'équipe de Google a fait un excellent travail d'analyse des schémas d'échantillonnage aléatoire, à la fois théoriquement et numériquement, tandis que Lijie Chen et I et Bouland et al. fourni des preuves différentes de la complexité classique de ce problème du point de vue de la théorie de la complexité.

B14. Si la supériorité quantique est atteinte, qu'est-ce que cela signifie pour les sceptiques?

Wow, je ne voudrais pas être à leur place maintenant! Ils peuvent se rabattre sur la position selon laquelle, bien sûr, la supériorité quantique est possible (et qui a dit le contraire? Et en fait, certains l'ont dit dès le début. Et d'autres, mon bon ami Gil Kalai, parmi eux, en écrivant, directement sur ce blog, ont prédit que la supériorité quantique ne serait jamais atteinte pour des raisons fondamentales. Maintenant, ils ne seront pas vissés.

B15. Et maintenant?

Si cette supériorité quantique est vraiment atteinte, je pense que le groupe Google a tout le matériel pour démontrer mon protocole de génération de bits aléatoires certifiés. Et c'est en fait l'une des choses suivantes dans leur plan.
Et en plus de cela, la prochaine étape évidente consiste à utiliser un QC programmable, avec 50-100 qubits pour une simulation quantique utile (par exemple, un système avec un état condensé de la matière) beaucoup plus rapidement que toute méthode classique. Et la deuxième étape évidente consiste à démontrer l'utilisation de la correction d'erreur pour maintenir le qubit logique en vie plus longtemps que la durée de vie des qubits physiques sur lesquels il est basé. Il ne fait aucun doute qu'IBM, Google et le reste des joueurs se poursuivront pour la primauté dans ces étapes.