EITC/QI/QIF Quantum Information Fundamentals est le programme européen de certification informatique sur les aspects théoriques et pratiques de l'information quantique et du calcul quantique, basé sur les lois de la physique quantique plutôt que sur la physique classique et offrant des avantages qualitatifs par rapport à leurs homologues classiques.
Le programme de l'EITC/QI/QIF Quantum Information Fundamentals couvre l'introduction à la mécanique quantique (y compris la prise en compte de l'expérience de la double fente et de l'interférence des ondes de matière), l'introduction à l'information quantique (les qubits et leur représentation géométrique), la polarisation de la lumière, le principe d'incertitude, la intrication, paradoxe EPR, violation de l'inégalité de Bell, abandon du réalisme local, traitement de l'information quantique (y compris transformation unitaire, portes à un et deux qubits), théorème de non-clonage, téléportation quantique, mesure quantique, calcul quantique (y compris introduction au multi -systèmes qubit, famille universelle de portes, réversibilité du calcul), algorithmes quantiques (dont transformée de Fourier quantique, algorithme de Simon, thèse Churh-Turing étendue, algorithme de factorisation quantique Shor'q, algorithme de recherche quantique de Grover), observables quantiques, équation de Shrodinger, implémentations de qubits, théorie de la complexité quantique, calcul quantique adiabatique ion, BQP, introduction au spin, dans la structure suivante, englobant un contenu didactique vidéo complet comme référence pour cette certification EITC.
L'information quantique est l'information sur l'état d'un système quantique. C'est l'entité de base de l'étude de la théorie de l'information quantique et elle peut être manipulée à l'aide de techniques de traitement de l'information quantique. L'information quantique fait référence à la fois à la définition technique en termes d'entropie de Von Neumann et au terme informatique général.
L'information et le calcul quantiques sont un domaine interdisciplinaire qui implique la mécanique quantique, l'informatique, la théorie de l'information, la philosophie et la cryptographie, entre autres domaines. Son étude est également pertinente pour des disciplines telles que les sciences cognitives, la psychologie et les neurosciences. Son objectif principal est d'extraire des informations de la matière à l'échelle microscopique. L'observation en science est un critère distinctif fondamental de la réalité et l'un des moyens les plus importants d'acquérir des informations. Par conséquent, la mesure est nécessaire pour quantifier l'observation, ce qui la rend cruciale pour la méthode scientifique. En mécanique quantique, en raison du principe d'incertitude, les observables non commutants ne peuvent pas être mesurés avec précision simultanément, car un état propre dans une base n'est pas un état propre dans l'autre base. Comme les deux variables ne sont pas simultanément bien définies, un état quantique ne peut jamais contenir d'informations définitives sur les deux variables. En raison de cette propriété fondamentale de la mesure en mécanique quantique, cette théorie peut être généralement caractérisée comme étant non déterministe contrairement à la mécanique classique, qui est entièrement déterministe. L'indéterminisme des états quantiques caractérise les informations définies comme états des systèmes quantiques. En termes mathématiques, ces états sont des superpositions (combinaisons linéaires) d'états de systèmes classiques.
Comme l'information est toujours codée dans l'état d'un système physique, elle est physique en soi. Alors que la mécanique quantique traite de l'examen des propriétés de la matière au niveau microscopique, la science de l'information quantique se concentre sur l'extraction d'informations à partir de ces propriétés, et le calcul quantique manipule et traite les informations quantiques - effectue des opérations logiques - en utilisant des techniques de traitement de l'information quantique.
L'information quantique, comme l'information classique, peut être traitée à l'aide d'ordinateurs, transmise d'un endroit à un autre, manipulée avec des algorithmes et analysée avec l'informatique et les mathématiques. Tout comme l'unité de base de l'information classique est le bit, l'information quantique concerne les qubits, qui peuvent exister en superposition de 0 et 1 (étant simultanément un peu vrai et faux). Les informations quantiques peuvent également exister dans des états dits intriqués, qui manifestent des corrélations non locales purement non classiques dans leurs mesures, permettant des applications telles que la téléportation quantique. Le niveau d'intrication peut être mesuré à l'aide de l'entropie de Von Neumann, qui est également une mesure de l'information quantique. Récemment, le domaine de l'informatique quantique est devenu un domaine de recherche très actif en raison de la possibilité de perturber le calcul, la communication et la cryptographie modernes.
L'histoire de l'information quantique a commencé au tournant du XXe siècle, lorsque la physique classique a été révolutionnée en physique quantique. Les théories de la physique classique prédisaient des absurdités telles que la catastrophe ultraviolette ou la spirale d'électrons dans le noyau. Au début, ces problèmes ont été écartés en ajoutant des hypothèses ad hoc à la physique classique. Bientôt, il est devenu évident qu'une nouvelle théorie devait être créée afin de donner un sens à ces absurdités, et la théorie de la mécanique quantique était née.
La mécanique quantique a été formulée par Schrödinger en utilisant la mécanique ondulatoire et Heisenberg en utilisant la mécanique matricielle. L'équivalence de ces méthodes a été prouvée plus tard. Leurs formulations décrivaient la dynamique des systèmes microscopiques mais présentaient plusieurs aspects insatisfaisants dans la description des processus de mesure. Von Neumann a formulé la théorie quantique en utilisant l'algèbre d'opérateurs de manière à décrire la mesure ainsi que la dynamique. Ces études ont mis l'accent sur les aspects philosophiques de la mesure plutôt que sur une approche quantitative de l'extraction d'informations via des mesures.
Dans les années 1960, Stratonovich, Helstrom et Gordon ont proposé une formulation des communications optiques utilisant la mécanique quantique. Ce fut la première apparition historique de la théorie de l'information quantique. Ils ont principalement étudié les probabilités d'erreur et les capacités des canaux de communication. Plus tard, Holevo a obtenu une limite supérieure de vitesse de communication dans la transmission d'un message classique via un canal quantique.
Dans les années 1970, des techniques de manipulation d'états quantiques à un seul atome, telles que le piège à atomes et le microscope à effet tunnel, ont commencé à se développer, permettant d'isoler des atomes uniques et de les disposer en réseaux. Avant ces développements, un contrôle précis sur des systèmes quantiques uniques n'était pas possible, et les expériences utilisaient un contrôle simultané plus grossier sur un grand nombre de systèmes quantiques. Le développement de techniques viables de manipulation à un seul état a conduit à un intérêt accru dans le domaine de l'information et du calcul quantiques.
Dans les années 1980, on s'est demandé s'il serait possible d'utiliser des effets quantiques pour réfuter la théorie de la relativité d'Einstein. S'il était possible de cloner un état quantique inconnu, il serait possible d'utiliser des états quantiques intriqués pour transmettre des informations plus rapidement que la vitesse de la lumière, réfutant la théorie d'Einstein. Cependant, le théorème de non-clonage a montré qu'un tel clonage est impossible. Le théorème était l'un des premiers résultats de la théorie de l'information quantique.
Développement à partir de la cryptographie
Malgré toute l'excitation et l'intérêt suscités par l'étude de systèmes quantiques isolés et la tentative de trouver un moyen de contourner la théorie de la relativité, la recherche en théorie de l'information quantique est devenue stagnante dans les années 1980. Cependant, à peu près au même moment, une autre voie a commencé à s'intéresser à l'information et au calcul quantiques : la cryptographie. Dans un sens général, la cryptographie est le problème de la communication ou du calcul impliquant deux ou plusieurs parties qui peuvent ne pas se faire confiance.
Bennett et Brassard ont développé un canal de communication sur lequel il est impossible d'écouter sans être détecté, un moyen de communiquer secrètement sur de longues distances en utilisant le protocole cryptographique quantique BB84. L'idée clé était l'utilisation du principe fondamental de la mécanique quantique selon lequel l'observation perturbe l'observé, et l'introduction d'une écoute indiscrète dans une ligne de communication sécurisée permettra immédiatement aux deux parties essayant de communiquer de savoir la présence de l'écoute indiscrète.
Développement à partir de l'informatique et des mathématiques
Avec l'avènement des idées révolutionnaires d'Alan Turing sur un ordinateur programmable, ou machine de Turing, il a montré que tout calcul du monde réel peut être traduit en un calcul équivalent impliquant une machine de Turing. C'est ce qu'on appelle la thèse Church-Turing.
Bientôt, les premiers ordinateurs ont été fabriqués et le matériel informatique s'est développé à un rythme si rapide que la croissance, grâce à l'expérience de la production, a été codifiée dans une relation empirique appelée loi de Moore. Cette « loi » est une tendance projective qui stipule que le nombre de transistors dans un circuit intégré double tous les deux ans. Alors que les transistors commençaient à devenir de plus en plus petits afin de contenir plus de puissance par surface, des effets quantiques ont commencé à apparaître dans l'électronique, entraînant des interférences par inadvertance. Cela a conduit à l'avènement de l'informatique quantique, qui a utilisé la mécanique quantique pour concevoir des algorithmes.
À ce stade, les ordinateurs quantiques semblaient prometteurs d'être beaucoup plus rapides que les ordinateurs classiques pour certains problèmes spécifiques. Un tel exemple de problème a été développé par David Deutsch et Richard Jozsa, connu sous le nom d'algorithme Deutsch-Jozsa. Ce problème n'avait cependant que peu ou pas d'applications pratiques. Peter Shor en 1994 a proposé un problème très important et pratique, celui de trouver les facteurs premiers d'un nombre entier. Le problème du logarithme discret, comme on l'appelait, pouvait être résolu efficacement sur un ordinateur quantique mais pas sur un ordinateur classique, ce qui montre que les ordinateurs quantiques sont plus puissants que les machines de Turing.
Développement à partir de la théorie de l'information
À l'époque, l'informatique faisait une révolution, tout comme la théorie de l'information et de la communication, à travers Claude Shannon. Shannon a développé deux théorèmes fondamentaux de la théorie de l'information : le théorème de codage de canal sans bruit et le théorème de codage de canal bruyant. Il a également montré que des codes de correction d'erreurs pouvaient être utilisés pour protéger les informations envoyées.
La théorie de l'information quantique a également suivi une trajectoire similaire, Ben Schumacher en 1995 a fait un analogue au théorème de codage silencieux de Shannon en utilisant le qubit. Une théorie de la correction d'erreur a également été développée, qui permet aux ordinateurs quantiques d'effectuer des calculs efficaces indépendamment du bruit et d'établir une communication fiable sur des canaux quantiques bruyants.
Qubits et théorie de l'information
L'information quantique diffère fortement de l'information classique, incarnée par le bit, à bien des égards frappants et peu familiers. Alors que l'unité fondamentale de l'information classique est le bit, l'unité la plus élémentaire de l'information quantique est le qubit. L'information classique est mesurée à l'aide de l'entropie de Shannon, tandis que l'analogue de la mécanique quantique est l'entropie de Von Neumann. Un ensemble statistique de systèmes mécaniques quantiques est caractérisé par la matrice de densité. De nombreuses mesures d'entropie dans la théorie classique de l'information peuvent également être généralisées au cas quantique, comme l'entropie de Holevo et l'entropie quantique conditionnelle.
Contrairement aux états numériques classiques (qui sont discrets), un qubit est à valeur continue, descriptible par une direction sur la sphère de Bloch. Bien qu'il soit continuellement valorisé de cette manière, un qubit est la plus petite unité possible d'information quantique, et bien que l'état du qubit soit à valeur continue, il est impossible de mesurer la valeur avec précision. Cinq théorèmes célèbres décrivent les limites de la manipulation de l'information quantique :
- le théorème de non-téléportation, qui stipule qu'un qubit ne peut pas être (entièrement) converti en bits classiques ; c'est-à-dire qu'il ne peut pas être entièrement "lu",
- théorème de non-clonage, qui empêche la copie d'un qubit arbitraire,
- théorème de non-suppression, qui empêche la suppression d'un qubit arbitraire,
- le théorème de non-diffusion, qui empêche qu'un qubit arbitraire soit livré à plusieurs destinataires, bien qu'il puisse être transporté d'un endroit à l'autre (par exemple via la téléportation quantique),
- théorème de non-cachage, qui démontre la conservation de l'information quantique,Ces théorèmes prouvent que l'information quantique dans l'univers est conservée et ils ouvrent des possibilités uniques dans le traitement de l'information quantique.
Traitement de l'information quantique
L'état d'un qubit contient toutes ses informations. Cet état est fréquemment exprimé sous forme de vecteur sur la sphère de Bloch. Cet état peut être modifié en leur appliquant des transformations linéaires ou des portes quantiques. Ces transformations unitaires sont décrites comme des rotations sur la sphère de Bloch. Alors que les portes classiques correspondent aux opérations familières de la logique booléenne, les portes quantiques sont des opérateurs unitaires physiques.
En raison de la volatilité des systèmes quantiques et de l'impossibilité de copier des états, le stockage d'informations quantiques est beaucoup plus difficile que le stockage d'informations classiques. Néanmoins, avec l'utilisation de la correction d'erreur quantique, les informations quantiques peuvent toujours être stockées de manière fiable en principe. L'existence de codes de correction d'erreurs quantiques a également conduit à la possibilité d'un calcul quantique tolérant aux pannes.
Les bits classiques peuvent être encodés et récupérés par la suite à partir de configurations de qubits, grâce à l'utilisation de portes quantiques. En soi, un seul qubit ne peut transmettre qu'un bit d'information classique accessible sur sa préparation. C'est le théorème de Holevo. Cependant, dans le codage superdense, un expéditeur, en agissant sur l'un des deux qubits intriqués, peut transmettre deux bits d'informations accessibles sur leur état commun à un récepteur.
L'information quantique peut être déplacée, dans un canal quantique, analogue au concept de canal de communication classique. Les messages quantiques ont une taille finie, mesurée en qubits ; les canaux quantiques ont une capacité de canal finie, mesurée en qubits par seconde.
L'information quantique et les modifications de l'information quantique peuvent être mesurées quantitativement en utilisant un analogue de l'entropie de Shannon, appelée entropie de von Neumann.
Dans certains cas, des algorithmes quantiques peuvent être utilisés pour effectuer des calculs plus rapidement que dans n'importe quel algorithme classique connu. L'exemple le plus célèbre en est l'algorithme de Shor qui peut factoriser les nombres en temps polynomial, par rapport aux meilleurs algorithmes classiques qui prennent un temps sous-exponentiel. Comme la factorisation est un élément important de la sécurité du chiffrement RSA, l'algorithme de Shor a déclenché le nouveau domaine de la cryptographie post-quantique qui tente de trouver des schémas de chiffrement qui restent sûrs même lorsque des ordinateurs quantiques sont en jeu. D'autres exemples d'algorithmes qui démontrent la suprématie quantique incluent l'algorithme de recherche de Grover, où l'algorithme quantique donne une accélération quadratique par rapport au meilleur algorithme classique possible. La classe de complexité des problèmes pouvant être résolus efficacement par un ordinateur quantique est connue sous le nom de BQP.
La distribution quantique de clés (QKD) permet une transmission sécurisée inconditionnelle des informations classiques, contrairement au cryptage classique, qui peut toujours être cassé en principe, sinon en pratique. Notez que certains points subtils concernant la sécurité de QKD sont encore vivement débattus.
L'étude de tous les sujets et différences ci-dessus comprend la théorie de l'information quantique.
Relation avec la mécanique quantique
La mécanique quantique est l'étude de la façon dont les systèmes physiques microscopiques changent dynamiquement dans la nature. Dans le domaine de la théorie de l'information quantique, les systèmes quantiques étudiés sont abstraits de toute contrepartie du monde réel. Un qubit peut par exemple être physiquement un photon dans un ordinateur quantique optique linéaire, un ion dans un ordinateur quantique à ions piégés, ou il peut s'agir d'une grande collection d'atomes comme dans un ordinateur quantique supraconducteur. Quelle que soit l'implémentation physique, les limites et les caractéristiques des qubits impliquées par la théorie de l'information quantique sont valables car tous ces systèmes sont mathématiquement décrits par le même appareil de matrices de densité sur les nombres complexes. Une autre différence importante avec la mécanique quantique est que, alors que la mécanique quantique étudie souvent des systèmes de dimension infinie tels qu'un oscillateur harmonique, la théorie de l'information quantique concerne à la fois les systèmes à variable continue et les systèmes de dimension finie.
Calcul quantique
L'informatique quantique est un type de calcul qui exploite les propriétés collectives des états quantiques, telles que la superposition, l'interférence et l'intrication, pour effectuer des calculs. Les appareils qui effectuent des calculs quantiques sont connus sous le nom d'ordinateurs quantiques. : I-5 Bien que les ordinateurs quantiques actuels soient trop petits pour surpasser les ordinateurs habituels (classiques) pour des applications pratiques, ils sont censés être capables de résoudre certains problèmes de calcul, tels que la factorisation d'entiers (qui sous-tend le cryptage RSA), nettement plus rapide que les ordinateurs classiques. L'étude de l'informatique quantique est un sous-domaine de la science de l'information quantique.
L'informatique quantique a commencé en 1980 lorsque le physicien Paul Benioff a proposé un modèle mécanique quantique de la machine de Turing. Richard Feynman et Yuri Manin ont suggéré plus tard qu'un ordinateur quantique avait le potentiel de simuler des choses qu'un ordinateur classique ne pourrait pas faire. En 1994, Peter Shor a développé un algorithme quantique pour factoriser des nombres entiers avec le potentiel de décrypter les communications cryptées RSA. En 1998, Isaac Chuang, Neil Gershenfeld et Mark Kubinec ont créé le premier ordinateur quantique à deux qubits capable d'effectuer des calculs. Malgré les progrès expérimentaux en cours depuis la fin des années 1990, la plupart des chercheurs pensent que "l'informatique quantique tolérante aux pannes [est] encore un rêve assez lointain". Ces dernières années, les investissements dans la recherche en informatique quantique ont augmenté dans les secteurs public et privé. Le 23 octobre 2019, Google AI, en partenariat avec la National Aeronautics and Space Administration (NASA) des États-Unis, a affirmé avoir effectué un calcul quantique qui était irréalisable sur n'importe quel ordinateur classique, mais la question de savoir si cette affirmation était ou est toujours valide est un sujet de discussion. recherche active.
Il existe plusieurs types d'ordinateurs quantiques (également connus sous le nom de systèmes informatiques quantiques), notamment le modèle de circuit quantique, la machine quantique de Turing, l'ordinateur quantique adiabatique, l'ordinateur quantique unidirectionnel et divers automates cellulaires quantiques. Le modèle le plus largement utilisé est le circuit quantique, basé sur le bit quantique, ou « qubit », qui est quelque peu analogue au bit dans le calcul classique. Un qubit peut être dans un état quantique 1 ou 0, ou dans une superposition des états 1 et 0. Quand il est mesuré, cependant, c'est toujours 0 ou 1 ; la probabilité de l'un ou l'autre résultat dépend de l'état quantique du qubit immédiatement avant la mesure.
Les efforts visant à construire un ordinateur quantique physique se concentrent sur des technologies telles que les transmons, les pièges à ions et les ordinateurs quantiques topologiques, qui visent à créer des qubits de haute qualité. : 2–13 Ces qubits peuvent être conçus différemment, selon le modèle informatique complet de l'ordinateur quantique, qu'il s'agisse de portes logiques quantiques, de recuit quantique ou de calcul quantique adiabatique. Il existe actuellement un certain nombre d'obstacles importants à la construction d'ordinateurs quantiques utiles. Il est particulièrement difficile de maintenir les états quantiques des qubits, car ils souffrent de la décohérence quantique et de la fidélité des états. Les ordinateurs quantiques nécessitent donc une correction d'erreur.
Tout problème de calcul qui peut être résolu par un ordinateur classique peut également être résolu par un ordinateur quantique. Inversement, tout problème pouvant être résolu par un ordinateur quantique peut également être résolu par un ordinateur classique, du moins en principe avec suffisamment de temps. En d'autres termes, les ordinateurs quantiques obéissent à la thèse de Church-Turing. Cela signifie que si les ordinateurs quantiques n'offrent aucun avantage supplémentaire par rapport aux ordinateurs classiques en termes de calculabilité, les algorithmes quantiques pour certains problèmes ont des complexités temporelles nettement inférieures à celles des algorithmes classiques connus correspondants. Notamment, on pense que les ordinateurs quantiques sont capables de résoudre rapidement certains problèmes qu'aucun ordinateur classique ne pourrait résoudre en un laps de temps raisonnable - un exploit connu sous le nom de «suprématie quantique». L'étude de la complexité computationnelle des problèmes liés aux ordinateurs quantiques est connue sous le nom de théorie de la complexité quantique.
Le modèle dominant de calcul quantique décrit le calcul en termes de réseau de portes logiques quantiques. Ce modèle peut être considéré comme une généralisation linéaire-algébrique abstraite d'un circuit classique. Étant donné que ce modèle de circuit obéit à la mécanique quantique, un ordinateur quantique capable de faire fonctionner efficacement ces circuits est considéré comme physiquement réalisable.
Une mémoire composée de n bits d'information possède 2^n états possibles. Un vecteur représentant tous les états de la mémoire a donc 2^n entrées (une pour chaque état). Ce vecteur est vu comme un vecteur de probabilité et représente le fait que la mémoire se trouve dans un état particulier.
Dans la vue classique, une entrée aurait une valeur de 1 (c'est-à-dire une probabilité de 100 % d'être dans cet état) et toutes les autres entrées seraient nulles.
En mécanique quantique, les vecteurs de probabilité peuvent être généralisés aux opérateurs de densité. Le formalisme du vecteur d'état quantique est généralement introduit en premier parce qu'il est conceptuellement plus simple et parce qu'il peut être utilisé à la place du formalisme de la matrice de densité pour les états purs, où l'ensemble du système quantique est connu.
un calcul quantique peut être décrit comme un réseau de portes logiques quantiques et de mesures. Cependant, toute mesure peut être reportée à la fin du calcul quantique, bien que ce report puisse avoir un coût de calcul, de sorte que la plupart des circuits quantiques décrivent un réseau composé uniquement de portes logiques quantiques et d'aucune mesure.
Tout calcul quantique (qui est, dans le formalisme ci-dessus, toute matrice unitaire sur n qubits) peut être représenté comme un réseau de portes logiques quantiques à partir d'une assez petite famille de portes. Un choix de famille de portes permettant cette construction est connu sous le nom d'ensemble de portes universel, car un ordinateur capable de faire fonctionner de tels circuits est un ordinateur quantique universel. Un tel ensemble commun comprend toutes les portes à un seul qubit ainsi que la porte CNOT d'en haut. Cela signifie que tout calcul quantique peut être effectué en exécutant une séquence de portes à un seul qubit avec des portes CNOT. Bien que cet ensemble de portes soit infini, il peut être remplacé par un ensemble de portes fini en faisant appel au théorème de Solovay-Kitaev.
Algorithmes quantiques
Les progrès dans la recherche d'algorithmes quantiques se concentrent généralement sur ce modèle de circuit quantique, bien qu'il existe des exceptions comme l'algorithme adiabatique quantique. Les algorithmes quantiques peuvent être grossièrement classés selon le type d'accélération obtenue par rapport aux algorithmes classiques correspondants.
Les algorithmes quantiques qui offrent plus qu'une accélération polynomiale par rapport à l'algorithme classique le plus connu incluent l'algorithme de Shor pour la factorisation et les algorithmes quantiques associés pour le calcul de logarithmes discrets, la résolution de l'équation de Pell et plus généralement la résolution du problème de sous-groupe caché pour les groupes finis abéliens. Ces algorithmes dépendent de la primitive de la transformée de Fourier quantique. Aucune preuve mathématique n'a été trouvée qui montre qu'un algorithme classique aussi rapide ne peut pas être découvert, bien que cela soit considéré comme peu probable. est dans le modèle de requête quantique, qui est un modèle restreint où les limites inférieures sont beaucoup plus faciles à prouver et ne se traduisent pas nécessairement par des accélérations pour des problèmes pratiques.
D'autres problèmes, y compris la simulation de processus physiques quantiques issus de la chimie et de la physique du solide, l'approximation de certains polynômes de Jones et l'algorithme quantique pour les systèmes linéaires d'équations, ont des algorithmes quantiques semblant donner des accélérations super-polynomiales et sont BQP-complets. Parce que ces problèmes sont BQP-complets, un algorithme classique tout aussi rapide pour eux impliquerait qu'aucun algorithme quantique ne donne une accélération super-polynomiale, ce qui est considéré comme peu probable.
Certains algorithmes quantiques, comme l'algorithme de Grover et l'amplification d'amplitude, donnent des accélérations polynomiales par rapport aux algorithmes classiques correspondants. Bien que ces algorithmes donnent une accélération quadratique relativement modeste, ils sont largement applicables et donnent donc des accélérations pour un large éventail de problèmes. De nombreux exemples d'accélérations quantiques prouvables pour les problèmes de requête sont liés à l'algorithme de Grover, y compris l'algorithme de Brassard, Høyer et Tapp pour trouver des collisions dans des fonctions deux à un, qui utilise l'algorithme de Grover, et l'algorithme de Farhi, Goldstone et Gutmann pour évaluer NAND arbres, qui est une variante du problème de recherche.
Applications cryptographiques
Une application notable du calcul quantique concerne les attaques contre les systèmes cryptographiques actuellement utilisés. La factorisation d'entiers, qui sous-tend la sécurité des systèmes cryptographiques à clé publique, est considérée comme irréalisable sur le plan informatique avec un ordinateur ordinaire pour les grands nombres entiers s'ils sont le produit de quelques nombres premiers (par exemple, les produits de deux nombres premiers de 300 chiffres). En comparaison, un ordinateur quantique pourrait résoudre efficacement ce problème en utilisant l'algorithme de Shor pour trouver ses facteurs. Cette capacité permettrait à un ordinateur quantique de casser de nombreux systèmes cryptographiques utilisés aujourd'hui, dans le sens où il y aurait un algorithme de temps polynomial (dans le nombre de chiffres de l'entier) pour résoudre le problème. En particulier, la plupart des chiffrements à clé publique populaires sont basés sur la difficulté de factoriser des nombres entiers ou sur le problème du logarithme discret, qui peuvent tous deux être résolus par l'algorithme de Shor. En particulier, les algorithmes RSA, Diffie-Hellman et Diffie-Hellman à courbe elliptique pourraient être brisés. Ceux-ci sont utilisés pour protéger les pages Web sécurisées, les e-mails cryptés et de nombreux autres types de données. Les briser aurait des ramifications importantes pour la confidentialité et la sécurité électroniques.
L'identification des systèmes cryptographiques qui peuvent être sécurisés contre les algorithmes quantiques est un sujet activement recherché dans le domaine de la cryptographie post-quantique. Certains algorithmes à clé publique sont basés sur des problèmes autres que la factorisation entière et les problèmes de logarithme discret auxquels s'applique l'algorithme de Shor, comme le cryptosystème McEliece basé sur un problème de théorie du codage. Les cryptosystèmes basés sur des réseaux ne sont pas non plus connus pour être cassés par les ordinateurs quantiques, et trouver un algorithme de temps polynomial pour résoudre le problème du sous-groupe caché dièdre, qui casserait de nombreux cryptosystèmes basés sur des réseaux, est un problème ouvert bien étudié. Il a été prouvé que l'application de l'algorithme de Grover pour casser un algorithme symétrique (clé secrète) par force brute nécessite un temps égal à environ 2n/2 invocations de l'algorithme cryptographique sous-jacent, contre environ 2n dans le cas classique, ce qui signifie que les longueurs de clé symétriques sont effectivement réduit de moitié: AES-256 aurait la même sécurité contre une attaque utilisant l'algorithme de Grover qu'AES-128 contre la recherche classique par force brute (voir Taille de la clé ).
La cryptographie quantique pourrait potentiellement remplir certaines des fonctions de la cryptographie à clé publique. Les systèmes cryptographiques quantiques pourraient donc être plus sûrs que les systèmes traditionnels contre le piratage quantique.
Problèmes de recherche
L'exemple le plus connu d'un problème admettant une accélération quantique polynomiale est la recherche non structurée, trouvant un élément marqué parmi une liste de n éléments dans une base de données. Cela peut être résolu par l'algorithme de Grover en utilisant des requêtes O (sqrt (n)) à la base de données, quadratiquement moins que les requêtes Omega (n) requises pour les algorithmes classiques. Dans ce cas, l'avantage est non seulement prouvable mais également optimal : il a été démontré que l'algorithme de Grover donne la probabilité maximale possible de trouver l'élément souhaité pour un nombre quelconque de recherches d'oracle.
Les problèmes qui peuvent être résolus avec l'algorithme de Grover ont les propriétés suivantes :
- Il n'y a pas de structure de recherche dans la collection de réponses possibles,
- Le nombre de réponses possibles à vérifier est le même que le nombre d'entrées dans l'algorithme, et
- Il existe une fonction booléenne qui évalue chaque entrée et détermine si c'est la bonne réponse
Pour les problèmes avec toutes ces propriétés, le temps d'exécution de l'algorithme de Grover sur un ordinateur quantique est égal à la racine carrée du nombre d'entrées (ou d'éléments dans la base de données), par opposition à la mise à l'échelle linéaire des algorithmes classiques. Une classe générale de problèmes auxquels l'algorithme de Grover peut être appliqué est le problème de satisfaisabilité booléenne , où la base de données à travers laquelle l'algorithme itère est celle de toutes les réponses possibles. Un exemple et une application (possible) de ceci est un craqueur de mot de passe qui tente de deviner un mot de passe. Les chiffrements symétriques tels que Triple DES et AES sont particulièrement vulnérables à ce type d'attaque. [citation nécessaire] Cette application de l'informatique quantique est un intérêt majeur des agences gouvernementales.
Simulation de systèmes quantiques
Étant donné que la chimie et la nanotechnologie reposent sur la compréhension des systèmes quantiques, et que ces systèmes sont impossibles à simuler de manière efficace de manière classique, beaucoup pensent que la simulation quantique sera l'une des applications les plus importantes de l'informatique quantique. La simulation quantique pourrait également être utilisée pour simuler le comportement des atomes et des particules dans des conditions inhabituelles telles que les réactions à l'intérieur d'un collisionneur. Des simulations quantiques pourraient être utilisées pour prédire les futurs trajets des particules et des protons sous superposition dans l'expérience à double fente. l'industrie des engrais tandis que les organismes naturels produisent également de l'ammoniac. Des simulations quantiques pourraient être utilisées pour comprendre ce processus augmentant la production.
Recuit quantique et optimisation adiabatique
Le recuit quantique ou le calcul quantique adiabatique repose sur le théorème adiabatique pour effectuer les calculs. Un système est placé dans l'état fondamental d'un hamiltonien simple, qui évolue lentement vers un hamiltonien plus compliqué dont l'état fondamental représente la solution au problème en question. Le théorème adiabatique stipule que si l'évolution est suffisamment lente, le système restera dans son état fondamental à tout moment tout au long du processus.
Apprentissage automatique
Étant donné que les ordinateurs quantiques peuvent produire des sorties que les ordinateurs classiques ne peuvent pas produire efficacement, et que le calcul quantique est fondamentalement algébrique linéaire, certains expriment l'espoir de développer des algorithmes quantiques qui peuvent accélérer les tâches d'apprentissage automatique. Par exemple, l'algorithme quantique pour les systèmes linéaires d'équations, ou "algorithme HHL", du nom de ses découvreurs Harrow, Hassidim et Lloyd, est censé fournir une accélération par rapport à ses homologues classiques. Certains groupes de recherche ont récemment exploré l'utilisation du matériel de recuit quantique pour la formation des machines de Boltzmann et des réseaux de neurones profonds.
Biologie computationnelle
Dans le domaine de la biologie computationnelle, l'informatique quantique a joué un rôle important dans la résolution de nombreux problèmes biologiques. L'un des exemples les plus connus serait la génomique computationnelle et la façon dont l'informatique a considérablement réduit le temps de séquencer un génome humain. Compte tenu de la façon dont la biologie computationnelle utilise la modélisation et le stockage de données génériques, ses applications à la biologie computationnelle devraient également se développer.
Conception de médicaments assistée par ordinateur et chimie générative
Les modèles de chimie générative profonde apparaissent comme des outils puissants pour accélérer la découverte de médicaments. Cependant, la taille et la complexité immenses de l'espace structurel de toutes les molécules médicamenteuses possibles posent des obstacles importants, qui pourraient être surmontés à l'avenir par les ordinateurs quantiques. Les ordinateurs quantiques sont naturellement bons pour résoudre des problèmes quantiques complexes à plusieurs corps et peuvent donc jouer un rôle déterminant dans les applications impliquant la chimie quantique. Par conséquent, on peut s'attendre à ce que les modèles génératifs améliorés quantiques, y compris les GAN quantiques, puissent éventuellement être développés en algorithmes de chimie générative ultimes. Les architectures hybrides combinant des ordinateurs quantiques avec des réseaux classiques profonds, tels que les auto-encodeurs variationnels quantiques, peuvent déjà être formées sur des recuits disponibles dans le commerce et utilisées pour générer de nouvelles structures moléculaires de type médicament.
Développer des ordinateurs quantiques physiques
Défis
Il existe un certain nombre de défis techniques dans la construction d'un ordinateur quantique à grande échelle. Le physicien David DiVincenzo a énuméré ces exigences pour un ordinateur quantique pratique :
- Physiquement évolutif pour augmenter le nombre de qubits,
- Qubits pouvant être initialisés à des valeurs arbitraires,
- Des portes quantiques plus rapides que le temps de décohérence,
- Ensemble de portail universel,
- Qubits qui peuvent être lus facilement.
L'approvisionnement en pièces pour les ordinateurs quantiques est également très difficile. De nombreux ordinateurs quantiques, comme ceux construits par Google et IBM, ont besoin d'hélium-3, un sous-produit de la recherche nucléaire, et de câbles supraconducteurs spéciaux fabriqués uniquement par la société japonaise Coax Co.
Le contrôle des systèmes multi-qubit nécessite la génération et la coordination d'un grand nombre de signaux électriques avec une résolution temporelle serrée et déterministe. Cela a conduit au développement de contrôleurs quantiques qui permettent l'interface avec les qubits. La mise à l'échelle de ces systèmes pour prendre en charge un nombre croissant de qubits est un défi supplémentaire.
Décohérence quantique
L'un des plus grands défis liés à la construction d'ordinateurs quantiques est le contrôle ou la suppression de la décohérence quantique. Cela signifie généralement isoler le système de son environnement car les interactions avec le monde extérieur provoquent la décohérence du système. Cependant, d'autres sources de décohérence existent également. Les exemples incluent les portes quantiques, les vibrations du réseau et le spin thermonucléaire de fond du système physique utilisé pour mettre en œuvre les qubits. La décohérence est irréversible, car elle est effectivement non unitaire, et est généralement quelque chose qui doit être hautement contrôlé, voire évité. Les temps de décohérence pour les systèmes candidats en particulier, le temps de relaxation transverse T2 (pour la technologie RMN et IRM, également appelé temps de déphasage), sont typiquement compris entre les nanosecondes et les secondes à basse température. Actuellement, certains ordinateurs quantiques exigent que leurs qubits soient refroidis à 20 millikelvins (généralement à l'aide d'un réfrigérateur à dilution) afin d'éviter une décohérence importante. Une étude de 2020 soutient que les rayonnements ionisants tels que les rayons cosmiques peuvent néanmoins provoquer la décohérence de certains systèmes en quelques millisecondes.
En conséquence, des tâches chronophages peuvent rendre certains algorithmes quantiques inopérants, car le maintien de l'état des qubits pendant une durée suffisamment longue finira par corrompre les superpositions.
Ces problèmes sont plus difficiles pour les approches optiques car les échelles de temps sont des ordres de grandeur plus courts et une approche souvent citée pour les surmonter est la mise en forme des impulsions optiques. Les taux d'erreur sont généralement proportionnels au rapport entre le temps de fonctionnement et le temps de décohérence, par conséquent, toute opération doit être effectuée beaucoup plus rapidement que le temps de décohérence.
Comme décrit dans le théorème du seuil quantique, si le taux d'erreur est suffisamment faible, on pense qu'il est possible d'utiliser la correction d'erreur quantique pour supprimer les erreurs et la décohérence. Cela permet au temps de calcul total d'être plus long que le temps de décohérence si le schéma de correction d'erreurs peut corriger les erreurs plus rapidement que la décohérence ne les introduit. Un chiffre souvent cité pour le taux d'erreur requis dans chaque porte pour le calcul tolérant aux pannes est de 10−3, en supposant que le bruit est dépolarisant.
Le respect de cette condition d'évolutivité est possible pour une large gamme de systèmes. Cependant, l'utilisation de la correction d'erreurs entraîne le coût d'un nombre considérablement accru de qubits requis. Le nombre requis pour factoriser des entiers à l'aide de l'algorithme de Shor est toujours polynomial et se situerait entre L et L2, où L est le nombre de chiffres du nombre à factoriser ; les algorithmes de correction d'erreur gonfleraient ce chiffre d'un facteur supplémentaire de L. Pour un nombre de 1000 bits, cela implique un besoin d'environ 104 bits sans correction d'erreur. Avec la correction d'erreurs, le chiffre passerait à environ 107 bits. Le temps de calcul est d'environ L2 ou d'environ 107 pas et à 1 MHz, d'environ 10 secondes.
Une approche très différente du problème de stabilité-décohérence consiste à créer un ordinateur quantique topologique avec des anyons, des quasi-particules utilisées comme fils et s'appuyant sur la théorie de la tresse pour former des portes logiques stables.
Suprématie quantique
La suprématie quantique est un terme inventé par John Preskill faisant référence à l'exploit d'ingénierie consistant à démontrer qu'un dispositif quantique programmable peut résoudre un problème au-delà des capacités des ordinateurs classiques de pointe. Le problème n'a pas besoin d'être utile, donc certains considèrent le test de suprématie quantique uniquement comme une future référence potentielle.
En octobre 2019, Google AI Quantum, avec l'aide de la NASA, est devenu le premier à prétendre avoir atteint la suprématie quantique en effectuant des calculs sur l'ordinateur quantique Sycamore plus de 3,000,000 XNUMX XNUMX fois plus rapidement que sur Summit, généralement considéré comme le plus rapide au monde. l'ordinateur. Cette affirmation a ensuite été contestée : IBM a déclaré que Summit peut effectuer des échantillons beaucoup plus rapidement que prévu, et les chercheurs ont depuis développé de meilleurs algorithmes pour le problème d'échantillonnage utilisé pour revendiquer la suprématie quantique, permettant des réductions substantielles ou la fermeture de l'écart entre Sycomore et supercalculateurs classiques.
En décembre 2020, un groupe de l'USTC a mis en œuvre un type d'échantillonnage Boson sur 76 photons avec un ordinateur quantique photonique Jiuzhang pour démontrer la suprématie quantique. Les auteurs affirment qu'un supercalculateur contemporain classique nécessiterait un temps de calcul de 600 millions d'années pour générer le nombre d'échantillons que leur processeur quantique peut générer en 20 secondes. Le 16 novembre 2021, lors du sommet sur l'informatique quantique, IBM a présenté un microprocesseur de 127 qubits nommé IBM Eagle.
Implémentations physiques
Pour implémenter physiquement un ordinateur quantique, de nombreux candidats différents sont recherchés, parmi lesquels (distingués par le système physique utilisé pour réaliser les qubits):
- Calcul quantique supraconducteur (qubit implémenté par l'état des petits circuits supraconducteurs, jonctions Josephson)
- Ordinateur quantique à ions piégés (qubit implémenté par l'état interne des ions piégés)
- Atomes neutres dans les réseaux optiques (qubit implémenté par des états internes d'atomes neutres piégés dans un réseau optique)
- Ordinateur à points quantiques, basé sur le spin (par exemple, l'ordinateur quantique Loss-DiVincenzo) (qubit donné par les états de spin des électrons piégés)
- Ordinateur à points quantiques, basé sur l'espace (qubit donné par la position des électrons dans la double boîte quantique)
- L'informatique quantique utilisant des puits quantiques artificiels, qui pourrait en principe permettre la construction d'ordinateurs quantiques fonctionnant à température ambiante
- Fil quantique couplé (qubit implémenté par une paire de fils quantiques couplés par un contact ponctuel quantique)
- Ordinateur quantique à résonance magnétique nucléaire (NMRQC) mis en œuvre avec la résonance magnétique nucléaire de molécules en solution, où les qubits sont fournis par des spins nucléaires dans la molécule dissoute et sondés avec des ondes radio
- Ordinateurs quantiques RMN Kane à l'état solide (qubit réalisé par l'état de spin nucléaire des donneurs de phosphore dans le silicium)
- Ordinateurs quantiques à électrons sur hélium (qubit est le spin de l'électron)
- Électrodynamique quantique de cavité (CQED) (qubit fourni par l'état interne d'atomes piégés couplés à des cavités à haute finesse)
- Aimant moléculaire (qubit donné par les états de spin)
- Ordinateur quantique ESR basé sur les fullerènes (qubit basé sur le spin électronique d'atomes ou de molécules enfermés dans des fullerènes)
- Ordinateur quantique optique non linéaire (qubits réalisés en traitant les états de différents modes de lumière à travers des éléments linéaires et non linéaires)
- Ordinateur quantique optique linéaire (qubits réalisés en traitant les états de différents modes de lumière à travers des éléments linéaires, par exemple des miroirs, des séparateurs de faisceau et des déphaseurs)
- Ordinateur quantique à base de diamant (qubit réalisé par le spin électronique ou nucléaire des centres à lacunes d'azote dans le diamant)
- Ordinateur quantique à base de condensat de Bose-Einstein
- Ordinateur quantique à transistors - ordinateurs quantiques à cordes avec entraînement de trous positifs à l'aide d'un piège électrostatique
- Ordinateurs quantiques à base de cristaux inorganiques dopés aux ions de métaux rares (qubit réalisé par l'état électronique interne des dopants dans les fibres optiques)
- Ordinateurs quantiques à base de nanosphères de carbone de type métallique
- Le grand nombre de candidats démontre que l'informatique quantique, malgré des progrès rapides, en est encore à ses balbutiements.
Il existe un certain nombre de modèles d'informatique quantique, qui se distinguent par les éléments de base dans lesquels le calcul est décomposé. Pour les implémentations pratiques, les quatre modèles de calcul pertinents sont :
- Réseau de portes quantiques (calcul décomposé en une séquence de portes quantiques à quelques qubits)
- Ordinateur quantique unidirectionnel (calcul décomposé en une séquence de mesures d'un qubit appliquées à un état initial ou à un état de cluster hautement intriqué)
- Ordinateur quantique adiabatique, basé sur le recuit quantique (calcul décomposé en une lente transformation continue d'un hamiltonien initial en un hamiltonien final, dont les états fondamentaux contiennent la solution)
- Ordinateur quantique topologique (calcul décomposé en tressage d'anyons dans un réseau 2D)
La machine quantique de Turing est théoriquement importante mais l'implémentation physique de ce modèle n'est pas réalisable. Les quatre modèles de calcul se sont avérés équivalents; chacun peut simuler l'autre sans plus d'un surcoût polynomial.
Pour vous familiariser en détail avec le programme de certification, vous pouvez développer et analyser le tableau ci-dessous.
Le programme de certification EITC/QI/QIF Quantum Information Fundamentals fait référence à du matériel didactique en libre accès sous forme de vidéo. Le processus d'apprentissage est divisé en une structure étape par étape (programmes -> leçons -> sujets) couvrant les parties pertinentes du programme. Des conseils illimités avec des experts du domaine sont également fournis.
Pour plus de détails sur la procédure de certification, consultez Comment cela fonctionne.
Principales notes de cours
Notes de cours U. Vazirani :
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Notes de cours de soutien
L. Jacak et al. notes de cours (avec matériel supplémentaire) :
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Manuel de soutien principal
Manuel de calcul quantique et d'information quantique (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Notes de cours supplémentaires
Notes de cours de J. Preskill :
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A. Notes de cours de Childs :
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Notes de cours de S. Aaronson :
https://scottaaronson.blog/?p=3943
Notes de cours de R. de Wolf :
https://arxiv.org/abs/1907.09415
Autres manuels recommandés
Calcul classique et quantique (Kitaev, Shen, Vyalyi)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
L'informatique quantique depuis Démocrite (Aaronson)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
La théorie de l'information quantique (Watrous)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Théorie de l'information quantique (Wilde)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Téléchargez le matériel préparatoire complet d'auto-apprentissage hors ligne pour le programme EITC/QI/QIF Quantum Information Fundamentals dans un fichier PDF.
Documents préparatoires EITC/QI/QIF – version standard
Documents préparatoires EITC/QI/QIF – version étendue avec questions de révision