Superb Quantum Excellence Q & A

Tiré d'un blog de Scott Joel Aronson, spécialiste en informatique et systèmes, chargé de cours, Département d'informatique, Université du Texas à Austin

Vous lisez ces histoires - dans le Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, [ sur Habr / approx. trad.] ou ailleurs - qu'un groupe de chercheurs de Google a atteint la supériorité de l'informatique quantique avec son dispositif supraconducteur à 53 qubits. Ils sont faciles à trouver, mais je ne leur donnerai pas de liens - simplement parce qu'ils ne devraient pas encore exister.

Le monde sait que Google prépare vraiment une grande annonce d'excellence quantique, qui devrait sortir simultanément avec la publication des travaux de recherche dans l'une des revues scientifiques respectées. Et cela est susceptible de se produire dans un mois.

Pendant ce temps, la NASA, qui a participé à ce développement, a accidentellement publié une ancienne version de Google sur un site public. Elle y a passé un court moment, mais suffisamment pour accéder au Financial Times, à ma boîte de réception et à des millions d'autres endroits. Les arguments sur ce travail, dépourvus de faits, sont prévisibles partout.

Apparemment, notre monde a été privé de l’occasion d’annoncer clairement un nouveau moment de «l’entrée de l’homme dans l’espace», dans lequel la thèse de Church-Turing sera réfutée expérimentalement lors d’une conférence de presse. Ce sera plus comme le vol des frères Wright, des rumeurs fragmentaires qui ont fait surface dans l'intervalle de 1903 à 1908, dans lesquelles Wilbur et Orville ont finalement accepté de faire des vols de démonstration (seulement dans notre cas, heureusement, l'explication du problème ira où combien de temps!)

Je suis à jour depuis quelques mois; il était extrêmement difficile pour moi de ne pas écrire à ce sujet sur mon blog. J'ai promis de garder le silence, mais je n'ai pas pu résister au désir de laisser ici et là des indices différents - par exemple, lors de mon discours lors du dernier événement dédié à Paul Bernays , j'ai spécialement conçu le déroulement de mes cours afin qu'ils amènent à ce point.

Cette entrée est l'annonce officielle confirmant ces faits. Et si la foudre est déjà visible pour nous, alors le droit d'exprimer le tonnerre appartient à un groupe de chercheurs de Google, ainsi que le temps et le lieu pour cela.

Au lieu de cela, j'ai décidé de clarifier cette question, de clarifier la désinformation qui circule sur Internet dans mon rôle de blogueuse et «d'intellectuelle sociale», et de vous présenter «Un excellent ensemble de questions et réponses sur la supériorité quantique de Scott». Juste au cas où vous vous êtes soudainement intéressé à la supériorité quantique ou vouliez savoir ce qui se passerait si une société de moteur de recherche de Mountain View ou ailleurs annonçait hypothétiquement la réalisation de la supériorité quantique .

Eh bien, ne tirons pas le chat par la queue:

Question 1: Qu'est-ce que l'excellence quantique en calcul?

Ce terme est souvent abrégé simplement en supériorité quantique (KP). Cela dénote l'utilisation d'un ordinateur quantique (CQ) pour résoudre un certain ensemble de problèmes bien définis, dont la solution, en utilisant les algorithmes connus aujourd'hui sur les ordinateurs classiques existants aujourd'hui, prendra des ordres de grandeur plus longs - et pas seulement comme ça, mais en raison de la complexité quantique asymptotique. L'accent est mis ici sur la certitude à 100% que la tâche est résolue sur QC, et elle ne peut vraiment pas être abordée à l'aide d'ordinateurs classiques; Idéalement, la tâche devrait être telle qu'elle puisse déjà être résolue dans un proche avenir (à l'aide de QC bruyants et non universels qui existent déjà ou apparaîtront bientôt). Et si cette tâche est toujours utile, tant mieux - mais ce n'est pas nécessaire. L'avion Wright Brothers ou le Chicago Woodpile n'étaient pas utiles en eux-mêmes.

Q2: Si les chercheurs de Google ont vraiment atteint HF, cela signifie-t-il que "n'importe quel code peut être piraté", comme l'a récemment tweeté le candidat à la présidence du Parti démocrate américain, Andrew Young?



Pas vrai (même si en tant que candidat, Young est jolie pour moi).

Il y a deux problèmes. Premièrement, les appareils que Google, IBM et d'autres créent aujourd'hui se composent de 50 à 100 qubits et n'ont pas de système de correction d'erreurs. Pour exécuter l'algorithme Shore pour casser le chiffrement RSA, plusieurs milliers de qubits logiques sont nécessaires. Et avec les méthodes de correction d'erreurs connues aujourd'hui, cela peut facilement nécessiter des millions de qubits physiques, et la qualité est meilleure que celles existantes. Je ne pense pas que quiconque s'en soit approché, et nous ne savons pas combien de temps cela prendra.

Deuxièmement, même dans un avenir hypothétique, des QC évolutifs avec correction d'erreur seront, comme il nous semble aujourd'hui, capables de casser certains codes, mais pas tous. Par coïncidence, les clés publiques qu'elles peuvent cracker incluent la plupart des clés que nous utilisons aujourd'hui pour la sécurité Internet: RSA, le protocole Diffie-Hellman, les courbes elliptiques, etc. Le chiffrement par clé privée aura un impact minimal. Et il existe également des candidats pour les systèmes à clé publique (par exemple, basés sur des réseaux), dont la méthode de piratage n'est connue de personne depuis 20 ans de tentatives de contrôle de qualité; en outre, des tentatives sont déjà faites pour passer à de tels systèmes. Les détails sont dans ma lettre à Rebecca Goldstein .

Q3: Quels calculs, considérés comme classiquement complexes, Google prévoit-il d'effectuer ou a-t-il déjà effectués?

Je peux dire, même si je suis gêné. Les calculs sont les suivants: le «testeur» génère un circuit quantique aléatoire C (une séquence aléatoire de portes de 1 qubit et le deuxième qubit le plus proche, profondeur 20 environ, sur un réseau bidimensionnel de 50-60 qubits). Ensuite, le testeur envoie C à l'ordinateur quantique et lui demande d'appliquer le circuit à l'état initial de tout-0, de mesurer le résultat avec la base {0,1}, d'envoyer la chaîne observée de n bits et de répéter cette opération plusieurs milliers ou millions de fois. Enfin, en utilisant sa connaissance de C, le testeur classique applique un test statistique pour vérifier que la sortie confirme que le QC a effectué les calculs.

Autrement dit, ce n'est pas une tâche comme l'affacturage, ayant une bonne réponse. Le circuit C produit une distribution de probabilité, appelons-la D _C , sur des chaînes de n bits, et la tâche consiste à produire des échantillons à partir de cette distribution. En fait, 2 ⁿ lignes parleront en faveur de D _C - et il y en aura tellement que si le QC fonctionne comme il se doit, alors nous ne verrons jamais la même sortie. Surtout, la distribution de D _{C n'est} pas uniforme. Certaines lignes subiront des interférences constructives d'amplitudes, et leurs probabilités seront plus grandes, tandis que d'autres souffriront d'interférences destructrices, et leurs probabilités seront moindres. Et bien que nous ne verrons que quelques échantillons, dont le nombre par rapport à 2 ⁿ sera minuscule, nous pouvons vérifier s'ils gravitent vers les lignes, ce que nous considérons plus probable, et à la fin cela augmentera notre confiance dans le fait que quelque chose de classiquement inaccessible se produit .

En termes simples, il sera simplement demandé à KK d'effectuer une séquence d'opérations aléatoire (mais connue) - non pas parce que nous avons besoin d'un résultat spécifique, mais parce que nous essayons de prouver qu'il peut devancer un ordinateur classique dans une tâche clairement définie.

Q4: Mais si KK n'existe que pour donner des déchets aléatoires, la seule signification étant qu'il est difficile de simuler sur un ordinateur classique, alors qui s'en soucie? N'est-ce pas un sandwich en conserve avec rien?

Non. Comme je l'ai déjà écrit, ce n'est pas un sandwich avec tout à la fois, mais définitivement un sandwich avec quelque chose!

Respectez l'immensité du sujet en discussion et les réalisations d'ingénierie terriblement complexes nécessaires à sa mise en œuvre. Avant le début du PC, les sceptiques peuvent s'amuser en même temps qu'après tous les milliards dépensés en plus de 20 ans, aucun KK n'a jamais été utilisé pour résoudre un problème qu'il aurait résolu plus rapidement que votre ordinateur portable, ou du moins le problème n'a pas pu être résolu d'une manière qui dépend de la nature quantique de cet ordinateur. Mais dans le monde du prochain KP, c'est déjà faux. Une superposition de 2 ⁵⁰ ou 2 ⁶⁰ nombres complexes a été maîtrisée par calcul, en utilisant du temps et des ressources minimes par rapport à 2 ⁵⁰ ou 2 ⁶⁰ .

Je me souviens constamment de l'avion des frères Wright parce que je suis frappé par l'abîme entre ce dont nous parlons et la négligence sur Internet de toutes parts à ce sujet. Cela ressemble à la réaction d'une personne qui croyait sacrément qu'il était impossible de faire un vol utile dans les airs, puis il a vu un avion à hélice en bois flottant dans les airs - ce spectacle ne réfuterait pas ses vues, mais ne soutiendrait pas non plus.

Ai-je vraiment été inquiet pendant toutes ces années pour rien que le battage médiatique constant concernant les étapes beaucoup moins importantes atteintes par le CC épuisera la patience des gens, et ils ne se soucieront pas de ce qui se passe vraiment?

Q5: Il y a de nombreuses années, vous avez fait honte aux masses pour avoir trop loué D-Wave et ses déclarations sur l'énorme accélération quantique de la résolution de problèmes d'optimisation par recuit quantique. Maintenant, vous avez honte des masses qu'elles ne sont pas suffisamment enthousiastes à propos du Parti communiste. Pourquoi ne décidez-vous pas?

Parce que mon objectif n'est pas de conduire le "niveau d'enthousiasme" dans une direction particulière, mais de m'assurer qu'il est correct! Ne pouvez-vous pas dire, en regardant en arrière, que j'avais généralement raison sur la D-Wave, même lorsque ma critique de ce sujet m'a rendu impopulaire dans certains milieux? Donc à propos du KP, j'essaie aussi d'avoir raison.

Q6: Si les calculs liés au KP ne prennent en compte que des échantillons de la distribution de probabilité, comment puis-je vérifier que les calculs sont corrects?

Heureusement que vous avez demandé! Il s'agit de la théorie que nous et d'autres scientifiques avons développée au cours de la dernière décennie. Je l'ai déjà expliqué brièvement en B3: les calculs peuvent être vérifiés statistiquement à partir des échantillons retournés par le QC, et s'assurer qu'ils préfèrent ajouter aux «pics» de la distribution de probabilité D _C. Une des façons pratiques de le faire est ce que Google appelle un «contrôle d'entropie croisée linéaire»: il s'agit de additionner Pr [C sortie s _i ] pour tous les échantillons s ₁ , .., s _k que le QC produit, puis déclarer la vérification réussie si ce montant sort au-delà d'une certaine limite - par exemple, bk / 2 ⁿ pour une constante 1 <b <2.

Bien entendu, pour effectuer ce test, il est nécessaire de calculer les probabilités Pr [C sortie s _i ] sur un ordinateur classique - et la seule façon de le faire est de prendre exhaustivement 2 ⁿ temps. Y a-t-il un problème avec cela? Non, si n = 50, et vous êtes Google, et vous pouvez traiter des nombres comme 2 ⁵⁰ (bien que vous ne puissiez pas faire face à 2 ¹⁰⁰⁰ , un nombre qui dépasse googol - ha, ha). En lançant un cluster de noyaux classiques quelque part pendant un mois, vous pourrez finalement confirmer la sortie correcte de votre QC, qu'il a émis en quelques secondes - et en même temps que le QC fonctionne de plusieurs ordres de grandeur plus rapidement. Cependant, cela signifie également que les expériences de CP basées sur l'échantillonnage sont conçues pour les dispositifs à 50 qubits qu'elles créent aujourd'hui. Et même avec une centaine de qubits, nous ne serions pas en mesure de confirmer les résultats du QC, même en utilisant toute la puissance de calcul de la planète.

Je souligne que ce problème est typique des expériences avec des échantillons similaires à celui que nous menons actuellement. Si l'algorithme de Shore factorisait un nombre de 2000 chiffres, nous vérifierions facilement cela en multipliant simplement les facteurs résultants et en vérifiant qu'ils appartiennent aux nombres premiers. Ou, si CC était utilisé pour simuler une biomolécule complexe, nous pourrions tester son fonctionnement dans une expérience.

Q7: Attendez une minute. Si les ordinateurs classiques ne peuvent vérifier les résultats d'une expérience sur KP que dans le mode de simulation de l'expérience (bien que lent), alors comment cela peut-il être une "supériorité quantique"?

Allez, viens. Avec une puce de 53 qubits, il est tout à fait logique de s'attendre à une accélération plusieurs millions de fois dans le mode dans lequel vous pouvez toujours vérifier directement le résultat du travail, et voir également que l'accélération croît de façon exponentielle avec une augmentation du nombre de qubits - tout comme l'analyse asymptotique l'a prédit.

Q8: Existe-t-il une preuve mathématique qu'il n'y a pas d'algorithme classique rapide qui dépasserait l'expérience KP avec échantillonnage?

Non aujourd'hui. Mais ce n'est pas la faute des chercheurs du KP! Les experts en informatique théorique ne sont même pas en mesure de prouver les hypothèses les plus simples, telles que P ≠ NP ou P ≠ PSPACE, il ne faut donc pas espérer qu'il sera possible d'exclure sans ambiguïté la présence d'une simulation classique rapide. Nous ne pouvons qu'espérer une complexité conditionnelle. Et nous avons vraiment prouvé certains de ces résultats . Le problème théorique le plus important dans ce domaine est la preuve des meilleurs résultats de complexité conditionnelle.

Q9: La base de sondage elle-même a-t-elle des utilisations utiles?

En pensant à ce sujet pour la première fois, les gens pensaient généralement que la réponse évidente à cette question était «non» (et j'étais l'un d'eux). Mais dernièrement, la situation a changé - par exemple, grâce à mon protocole d'aléatoire confirmé, qui montre comment une expérience avec un CP avec échantillonnage peut être très rapidement transformée en un générateur de bits, dont l'aléatoire peut être prouvé à un observateur tiers sceptique (sous certaines hypothèses de calcul). Et cela peut potentiellement être appliqué à la création de crypto - monnaies PoS et d'autres protocoles cryptographiques. J'espère que dans un proche avenir, d'autres applications de ce type seront découvertes.

Q10: Si les expériences KP génèrent simplement des bits aléatoires, est-ce intéressant? N'est-ce pas une tâche banale de transformer des qubits en bits aléatoires en les mesurant simplement?

L'essentiel est que l'expérience avec le KP ne génère pas de bits aléatoires uniformes. Il fait une sélection à partir d'une distribution de probabilité de corrélation complexe sur des lignes de 50 bits ou 60 bits. Dans mon protocole de randomisation confirmé, les écarts par rapport à l'homogénéité jouent un rôle central dans la façon dont le CP peut convaincre le sceptique classique que les bits sont vraiment aléatoires et n'ont pas de système secret (comme un générateur de nombres pseudo-aléatoires).

Q11: Mais des décennies d'expériences de mécanique quantique - par exemple, celles qui violent les inégalités de Bell - n'ont-elles pas déjà démontré le KP?

Ce n'est qu'une confusion de termes. Ces expériences ont montré d'autres types de «supériorité quantique». Par exemple, en cas de violation des inégalités de Bell, il s'agissait de «supériorité de corrélation quantique». Il n'a pas montré de supériorité informatique, c'est-à-dire quelque chose qui ne peut pas être simulé sur un ordinateur classique (malgré le fait que la simulation classique n'aurait pas de restrictions sur la localisation spatiale ou quelque chose comme ça). Aujourd'hui, les gens entendent généralement la supériorité de l'informatique quantique par KP.

Q12: Eh bien, mais il existe d'innombrables exemples de matériaux et de réactions chimiques difficiles à simuler classiquement, ainsi que des simulateurs quantiques spéciaux (par exemple, le groupe Lukin de Harvard). Pourquoi ne sont-ils pas considérés comme des exemples de KP?

Selon certaines définitions, ils peuvent être considérés comme des exemples de KP! La principale différence entre les travaux des chercheurs de Google est que leur appareil est entièrement programmable - il peut être programmé dans une séquence arbitraire de portes à 2 qubits avec le plus proche voisin, envoyant simplement les signaux nécessaires à partir d'un ordinateur quantique.

En d'autres termes, les sceptiques KP ne peuvent plus grogner que, disent-ils, s'il existe des systèmes quantiques difficiles à simuler classiquement, c'est uniquement parce que la nature est difficile à simuler, et nous ne pouvons pas changer arbitrairement le composé chimique aléatoire que nous trouvons dans par conséquent, ces systèmes ne peuvent pas être considérés comme des «ordinateurs qui se simulent». Selon toute définition raisonnable, les appareils supraconducteurs que Google, IBM et d'autres sociétés construisent aujourd'hui sont de vrais ordinateurs.

Q13: Avez-vous inventé le concept de supériorité quantique?

Non. J'ai joué un rôle dans sa définition, c'est pourquoi Sabina Hossenfelder et d'autres m'ont attribué un rôle trop important dans cette idée. Le terme «supériorité quantique» a été inventé par John Preskill en 2012, bien que, à certains égards, le concept clé remonte au début de l'informatique quantique elle-même au début des années 1980. En 1994, l'utilisation de l'algorithme Shore pour factoriser de grands nombres est devenue une véritable expérience dans le domaine du KP - bien que ce problème soit trop difficile à résoudre aujourd'hui.

L'essence de l'idée, qui était plutôt de démontrer le CP en utilisant le problème d'échantillonnage, à ma connaissance, a été proposée pour la première fois par Barbara Theral et David Divincenzo dans un travail visionnaire de 2002. Les tentatives «modernes» d'organiser des expériences ont commencé en 2011, quand Alex Arkhipov et moi avons publié nos travaux sur l'échantillonnage de bosons, et Bremner, Yosa et Shepherd ont publié nos travaux sur les hamiltoniens commutés. Ces travaux ont montré non seulement que des systèmes quantiques «simples» et non universels peuvent résoudre des problèmes apparemment complexes avec l'échantillonnage, mais aussi qu'un algorithme classique efficace pour ces problèmes entraînera l' effondrement de la hiérarchie polynomiale . Arkhipov et moi avons également pris les premières mesures pour prouver que même des versions approximatives de problèmes d'échantillonnage quantique peuvent être classiquement complexes.

Pour autant que je sache, l'idée d'un «échantillonnage aléatoire des circuits» - c'est-à-dire de générer un problème d'échantillonnage complexe par la sélection de séquences de valves aléatoires à 2 qubits dans une architecture supraconductrice - est apparue dans la correspondance électronique que j'ai commencée en décembre 2015, à laquelle John a également participé. , , , , , , , . « 40 », « ».J'ai discuté de certains des avantages et des inconvénients de trois options pour démontrer KP avec échantillonnage: (1) contours aléatoires, (2) hamiltoniens commutés, (3) échantillonnage de boson. Après que Cooperberg ait défendu la première option, un consensus s'est rapidement dégagé parmi les participants selon lequel la première option était en effet la meilleure d'un point de vue technique - et que si l'analyse théorique existante pour (1) ne suffit pas, alors nous pouvons trouver quelque chose.

Après cela, un groupe de Google a effectué un grand nombre d'analyses d'échantillons de contours aléatoires, à la fois théoriques et numériques, et Lijie Chen et Buland et mes collègues ont présenté des preuves de différents types pour la complexité classique du problème.

Q14: Si KP est atteint, qu'est-ce que cela signifie pour les sceptiques?

Je ne voudrais pas être à leur place! Ils peuvent se déplacer vers une position où le KP est possible (et qui a dit que c'était impossible? Ils ne le sont certainement pas!), Et cette correction quantique des erreurs a toujours été un vrai problème. Et beaucoup d'entre eux ont vraiment soutenu cette position particulière. Mais d'autres, dont mon ami Gil Kalay, ici même sur un blog, ont fait valoir que le KP ne pouvait pas être atteint pour des raisons fondamentales. Et je ne les laisserai pas sortir.

Q15: Et ensuite?

Atteindre KP signifie que le groupe Google dispose déjà de l'équipement nécessaire pour démontrer mon protocole de génération de bits aléatoires confirmés. Et c'est vraiment l'une des premières choses que nous prévoyons de faire.

La prochaine étape évidente sera l'utilisation d'un QC programmable avec 50-100 qubits pour des simulations quantiques utiles (par exemple, des systèmes à états condensés) qui sont plus rapides que toutes les méthodes classiques connues. Le deuxième jalon évident sera la démonstration de l'utilisation de la correction d'erreur quantique afin que le qubit codé vive plus longtemps que les qubits physiques sous-jacents. Il ne fait aucun doute que Google, IBM et d'autres joueurs se précipiteront pour viser ces deux étapes.

Après avoir publié l'article, Steve Girwin m'a rappelé que le groupe de Yale avait déjà atteintcorrection d'erreur quantique, bien que dans le système bosonique, et non dans le système des qubits supraconducteurs. Donc, peut-être, le prochain jalon est mieux formulé comme suit: atteindre la supériorité informatique quantique et la correction d'erreur quantique utile dans un système.