Algorithme quantique - Quantum algorithm

En informatique quantique , un algorithme quantique est un algorithme qui s'exécute sur un modèle réaliste de calcul quantique , le modèle le plus couramment utilisé étant le modèle de circuit quantique de calcul. Un algorithme classique (ou non quantique) est une séquence finie d'instructions, ou une procédure étape par étape pour résoudre un problème, où chaque étape ou instruction peut être exécutée sur un ordinateur classique . De même, un algorithme quantique est une procédure étape par étape, où chacune des étapes peut être effectuée sur un ordinateur quantique . Bien que tous les algorithmes classiques puissent également être exécutés sur un ordinateur quantique, le terme algorithme quantique est généralement utilisé pour les algorithmes qui semblent intrinsèquement quantiques, ou utilisent une caractéristique essentielle du calcul quantique telle que la superposition quantique ou l'intrication quantique .

Les problèmes indécidables avec les ordinateurs classiques restent indécidables avec les ordinateurs quantiques. Ce qui rend les algorithmes quantiques intéressants, c'est qu'ils pourraient être capables de résoudre certains problèmes plus rapidement que les algorithmes classiques car la superposition quantique et l'intrication quantique qu'exploitent les algorithmes quantiques ne peuvent probablement pas être simulées efficacement sur des ordinateurs classiques (voir Suprématie quantique ).

Les algorithmes les plus connus sont l'algorithme de Shor pour la factorisation et l'algorithme de Grover pour rechercher une base de données non structurée ou une liste non ordonnée. Les algorithmes de Shor s'exécutent beaucoup (presque exponentiellement) plus rapidement que l'algorithme classique le plus connu pour la factorisation, le tamis général des champs de nombres . L'algorithme de Grover s'exécute quadratiquement plus rapidement que le meilleur algorithme classique possible pour la même tâche, une recherche linéaire .

Aperçu

Les algorithmes quantiques sont généralement décrits, dans le modèle de circuit couramment utilisé du calcul quantique, par un circuit quantique qui agit sur certains qubits d' entrée et se termine par une mesure . Un circuit quantique est constitué de portes quantiques simples qui agissent sur au plus un nombre fixe de qubits. Le nombre de qubits doit être fixe car un nombre changeant de qubits implique une évolution non unitaire. Les algorithmes quantiques peuvent également être énoncés dans d'autres modèles de calcul quantique, tels que le modèle oracle hamiltonien .

Les algorithmes quantiques peuvent être classés par les principales techniques utilisées par l'algorithme. Certaines techniques couramment utilisées / idées dans les algorithmes quantiques comprennent kick-back de phase , estimation de phase , la quantique transformée de Fourier , marches quantiques , amplification d' amplitude et la théorie topologique du champ quantique . Les algorithmes quantiques peuvent également être regroupés par type de problème résolu, par exemple voir l'enquête sur les algorithmes quantiques pour les problèmes algébriques.

Algorithmes basés sur la transformée de Fourier quantique

La transformée de Fourier quantique est l'analogue quantique de la transformée de Fourier discrète et est utilisée dans plusieurs algorithmes quantiques. La transformée de Hadamard est également un exemple de transformée de Fourier quantique sur un espace vectoriel à n dimensions sur le champ F ₂ . La transformée de Fourier quantique peut être efficacement implémentée sur un ordinateur quantique en utilisant seulement un nombre polynomial de portes quantiques .

Algorithme Deutsch-Jozsa

Algorithme Deutsch-Jozsa

L'algorithme de Deutsch-Jozsa résout un problème de boîte noire qui nécessite probablement de nombreuses requêtes exponentielles à la boîte noire pour tout ordinateur classique déterministe, mais peut être fait avec exactement une requête par un ordinateur quantique. Si nous autorisons à la fois les algorithmes quantiques à erreur bornée et classiques, alors il n'y a pas d'accélération puisqu'un algorithme probabiliste classique peut résoudre le problème avec un nombre constant de requêtes avec une faible probabilité d'erreur. L'algorithme détermine si une fonction f est soit constante (0 sur toutes les entrées ou 1 sur toutes les entrées) soit équilibrée (renvoie 1 pour la moitié du domaine d'entrée et 0 pour l'autre moitié).

Algorithme de Bernstein-Vazirani

L'algorithme de Bernstein-Vazirani est le premier algorithme quantique qui résout un problème plus efficacement que le meilleur algorithme classique connu. Il a été conçu pour créer une séparation d'oracle entre BQP et BPP .

L'algorithme de Simon

L'algorithme de Simon résout un problème de boîte noire exponentiellement plus rapidement que n'importe quel algorithme classique, y compris les algorithmes probabilistes à erreur bornée. Cet algorithme, qui atteint une accélération exponentielle par rapport à tous les algorithmes classiques que nous considérons efficaces, a été la motivation de l'algorithme de factorisation de Shor.

Algorithme d'estimation de phase quantique

L' algorithme d'estimation de phase quantique est utilisé pour déterminer la phase propre d'un vecteur propre d'une porte unitaire étant donné un état quantique proportionnel au vecteur propre et à l'accès à la porte. L'algorithme est fréquemment utilisé comme sous-programme dans d'autres algorithmes.

Algorithme de Shor

L'algorithme de Shor résout le problème du logarithme discret et le problème de la factorisation d'entiers en temps polynomial, alors que les algorithmes classiques les plus connus prennent un temps super-polynomial. Ces problèmes ne sont pas connus pour être en P ou NP-complet . C'est également l'un des rares algorithmes quantiques qui résout un problème non-boîte noire en temps polynomial où les algorithmes classiques les plus connus fonctionnent en temps super-polynomial.

Problème de sous-groupe caché

Le problème du sous-groupe caché abélien est une généralisation de nombreux problèmes pouvant être résolus par un ordinateur quantique, tels que le problème de Simon, la résolution de l'équation de Pell , le test de l' idéal principal d'un anneau R et la factorisation . Il existe des algorithmes quantiques efficaces connus pour le problème du sous-groupe caché abélien. Le problème de sous-groupe caché plus général, où le groupe n'est pas nécessairement abélien, est une généralisation des problèmes mentionnés précédemment et de l' isomorphisme des graphes et de certains problèmes de réseau . Des algorithmes quantiques efficaces sont connus pour certains groupes non abéliens. Cependant, aucun algorithme efficace n'est connu pour le groupe symétrique , ce qui donnerait un algorithme efficace pour l'isomorphisme des graphes et le groupe dièdre , qui résoudrait certains problèmes de réseau.

Problème d'échantillonnage de boson

Le problème d'échantillonnage de bosons dans une configuration expérimentale suppose une entrée de bosons (par exemple des photons de lumière) d'un nombre modéré se dispersant de manière aléatoire dans un grand nombre de modes de sortie contraints par une unité définie . Le problème est alors de produire un échantillon équitable de la distribution de probabilité de la sortie qui dépend de l'arrangement des bosons en entrée et de l'Unitarité. Résoudre ce problème avec un algorithme informatique classique nécessite de calculer la permanente de la matrice de transformation unitaire, ce qui peut être impossible ou prendre un temps prohibitif. En 2014, il a été proposé que la technologie existante et les méthodes probabilistes standard de génération d'états de photons uniques pourraient être utilisées comme entrée dans un réseau optique linéaire calculable quantique approprié et que l'échantillonnage de la distribution de probabilité de sortie serait manifestement supérieur à l'aide d'algorithmes quantiques. En 2015, une enquête a prédit que le problème d'échantillonnage avait une complexité similaire pour les entrées autres que les photons d' état de Fock et a identifié une transition dans la complexité de calcul d'une simulation classique à tout aussi difficile que le problème d'échantillonnage de Boson, en fonction de la taille des entrées d'amplitude cohérente.

Estimation des sommes de Gauss

Une somme de Gauss est un type de somme exponentielle . L'algorithme classique le plus connu pour estimer ces sommes prend un temps exponentiel. Étant donné que le problème du logarithme discret se réduit à l'estimation de la somme de Gauss, un algorithme classique efficace pour estimer les sommes de Gauss impliquerait un algorithme classique efficace pour le calcul des logarithmes discrets, ce qui est considéré comme peu probable. Cependant, les ordinateurs quantiques peuvent estimer les sommes de Gauss avec une précision polynomiale en temps polynomial.

Pêche de Fourier et contrôle de Fourier

Nous avons un oracle composé de n fonctions booléennes aléatoires mappant des chaînes de n bits à une valeur booléenne. Nous devons trouver n chaînes de n bits z ₁ ,..., z _n telles que pour la transformée de Hadamard-Fourier, au moins 3/4 des chaînes satisfont

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 1}$

et au moins 1/4 satisfait

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 2.}$

Cela peut être fait en temps polynomial quantique à erreur bornée (BQP).

Algorithmes basés sur l'amplification d'amplitude

L'amplification d'amplitude est une technique qui permet l'amplification d'un sous-espace choisi d'un état quantique. Les applications d'amplification d'amplitude conduisent généralement à des accélérations quadratiques par rapport aux algorithmes classiques correspondants. Il peut être considéré comme une généralisation de l'algorithme de Grover.

Algorithme de Grover

L'algorithme de Grover recherche une base de données non structurée (ou une liste non ordonnée) avec N entrées, pour une entrée marquée, en utilisant uniquement des requêtes au lieu des requêtes requises classiquement. Classiquement, des requêtes sont nécessaires même autorisant des algorithmes probabilistes à erreur bornée. ${\style d'affichage O({\sqrt {N}})}$${\style d'affichage O({N})}$${\style d'affichage O({N})}$

Les théoriciens ont envisagé une généralisation hypothétique d'un ordinateur quantique standard qui pourrait accéder aux histoires des variables cachées de la mécanique bohème . (Un tel ordinateur est complètement hypothétique et ne serait pas un ordinateur quantique standard, ni même possible selon la théorie standard de la mécanique quantique.) Un tel ordinateur hypothétique pourrait mettre en œuvre une recherche dans une base de données à N éléments au plus par étapes. C'est légèrement plus rapide que les étapes prises par l'algorithme de Grover . Aucune des deux méthodes de recherche ne permettrait à l'un ou l'autre modèle d'ordinateur quantique de résoudre des problèmes NP-complets en temps polynomial. ${\displaystyle O({\sqrt[{3}]{N}})}$${\style d'affichage O({\sqrt {N}})}$

Comptage quantique

Le comptage quantique résout une généralisation du problème de recherche. Il résout le problème de compter le nombre d'entrées marquées dans une liste non ordonnée, au lieu de simplement détecter s'il en existe une. Plus précisément, il compte le nombre d'entrées marquées dans une liste d'éléments, avec des erreurs en ne faisant que des requêtes, où est le nombre d'éléments marqués dans la liste. Plus précisément, l'algorithme génère une estimation pour , le nombre d'entrées marquées, avec la précision suivante : . ${\style d'affichage N}$${\displaystyle \varepsilon }$${\displaystyle \Theta \left({\frac {1}{\varepsilon }}{\sqrt {\frac {N}{k}}}\right)}$${\style d'affichage k}$${\style d'affichage k'}$${\style d'affichage k}$${\displaystyle |k-k'|\leq \varepsilon k}$

Algorithmes basés sur les marches quantiques

Une marche quantique est l'analogue quantique d'une marche aléatoire classique , qui peut être décrite par une distribution de probabilité sur certains états. Une marche quantique peut être décrite par une superposition quantique sur des états. Les marches quantiques sont connues pour donner des accélérations exponentielles pour certains problèmes de boîte noire. Ils fournissent également des accélérations polynomiales pour de nombreux problèmes. Un cadre pour la création d'algorithmes de marche quantique existe et est un outil assez polyvalent.

Problème de distinction des éléments

Le problème de distinction des éléments est le problème de déterminer si tous les éléments d'une liste sont distincts. Classiquement, des requêtes Ω( N ) sont nécessaires pour une liste de taille N . Cependant, il peut être résolu dans des requêtes sur un ordinateur quantique. L'algorithme optimal est celui d' Andris Ambainis . Yaoyun Shi a d' abord prouvé une limite inférieure serrée lorsque la taille de la plage est suffisamment grande. Ambainis et Kutin indépendamment (et via différentes preuves) ont étendu son travail pour obtenir la borne inférieure pour toutes les fonctions. ${\displaystyle \Thêta (N^{2/3})}$

Problème de recherche de triangle

Le problème de recherche de triangle est le problème de déterminer si un graphique donné contient un triangle (une clique de taille 3). La limite inférieure la plus connue pour les algorithmes quantiques est Ω( N ), mais le meilleur algorithme connu nécessite des requêtes O( N ^1,297 ), une amélioration par rapport aux meilleures requêtes O( N ^1,3 ) précédentes .

Évaluation de la formule

Une formule est un arbre avec une porte à chaque nœud interne et un bit d'entrée à chaque nœud feuille. Le problème est d'évaluer la formule, qui est la sortie du nœud racine, compte tenu de l'accès oracle à l'entrée.

Une formule bien étudiée est l'arbre binaire équilibré avec uniquement des portes NAND. Ce type de formule nécessite des requêtes Θ( N ^c ) utilisant le caractère aléatoire, où . Avec un algorithme quantique cependant, il peut être résolu en requêtes Θ( N ^0.5 ). Aucun meilleur algorithme quantique pour ce cas n'était connu jusqu'à ce qu'on en trouve un pour le modèle d'oracle hamiltonien non conventionnel. Le même résultat pour le réglage standard suivit bientôt. ${\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754}$

Des algorithmes quantiques rapides pour des formules plus compliquées sont également connus.

La commutativité de groupe

Le problème est de déterminer si un groupe de boîtes noires , donné par k générateurs, est commutatif . Un groupe boîte noire est un groupe avec une fonction oracle, qui doit être utilisé pour effectuer les opérations de groupe (multiplication, inversion et comparaison avec l'identité). Nous nous intéressons à la complexité de la requête, qui est le nombre d'appels d'oracle nécessaires pour résoudre le problème. Les complexités des requêtes déterministes et aléatoires sont et respectivement. Un algorithme quantique nécessite des requêtes mais l'algorithme le plus connu utilise des requêtes. ${\displaystyle \Thêta (k^{2})}$${\displaystyle \Thêta (k)}$${\displaystyle \Omega (k^{2/3})}$${\displaystyle O(k^{2/3}\log k)}$

Problèmes BQP-complet

La classe de complexité BQP (bounded-error quantum polynomial time) est l'ensemble des problèmes de décision pouvant être résolus par un ordinateur quantique en temps polynomial avec une probabilité d'erreur d'au plus 1/3 pour toutes les instances. C'est l'analogue quantique de la classe de complexité classique BPP .

Un problème est BQP -complet s'il est en BQP et tout problème en BQP peut s'y réduire en temps polynomial . De manière informelle, la classe des problèmes BQP -complets sont ceux qui sont aussi difficiles que les problèmes les plus difficiles de BQP et sont eux-mêmes efficacement résolvables par un ordinateur quantique (avec erreur bornée).

Calcul des invariants de nœuds

Witten avait montré que la théorie des champs quantiques topologiques de Chern-Simons (TQFT) peut être résolue en termes de polynômes de Jones . Un ordinateur quantique peut simuler un TQFT, et ainsi approximer le polynôme de Jones, qui, à notre connaissance, est difficile à calculer classiquement dans le pire des cas.

Simulation quantique

L'idée que les ordinateurs quantiques pourraient être plus puissants que les ordinateurs classiques est née de l'observation de Richard Feynman selon laquelle les ordinateurs classiques semblent nécessiter un temps exponentiel pour simuler des systèmes quantiques à plusieurs particules. Depuis lors, l'idée que les ordinateurs quantiques peuvent simuler des processus physiques quantiques de manière exponentielle plus rapidement que les ordinateurs classiques a été considérablement étoffée et élaborée. Des algorithmes quantiques efficaces (c'est-à-dire en temps polynomial) ont été développés pour simuler à la fois les systèmes bosoniques et fermioniques et, en particulier, la simulation de réactions chimiques au-delà des capacités des superordinateurs classiques actuels ne nécessite que quelques centaines de qubits. Les ordinateurs quantiques peuvent également simuler efficacement les théories topologiques des champs quantiques. En plus de son intérêt intrinsèque, ce résultat a conduit à des algorithmes quantiques efficaces pour estimer des invariants topologiques quantiques tels que les polynômes de Jones et HOMFLY , et l' invariant de Turaev-Viro des variétés tridimensionnelles.

Résoudre un système linéaire d'équations

En 2009, Aram Harrow , Avinatan Hassidim et Seth Lloyd ont formulé un algorithme quantique pour la résolution de systèmes linéaires . L' algorithme estime le résultat d'une mesure scalaire sur le vecteur solution à un système linéaire d'équations donné.

À condition que le système linéaire soit clairsemé et ait un nombre de condition faible , et que l'utilisateur s'intéresse au résultat d'une mesure scalaire sur le vecteur de solution, au lieu des valeurs du vecteur de solution lui-même, alors l'algorithme a une durée d'exécution de , où est le nombre de variables dans le système linéaire. Cela offre une accélération exponentielle par rapport à l'algorithme classique le plus rapide, qui s'exécute dans (ou pour des matrices semi-définies positives). ${\style d'affichage \kappa }$${\displaystyle O(\log(N)\kappa ^{2})}$${\style d'affichage N}$${\style d'affichage O(N\kappa )}$${\displaystyle O(N{\sqrt {\kappa }})}$

Algorithmes hybrides quantiques/classiques

Les algorithmes hybrides quantiques/classiques combinent la préparation et la mesure de l'état quantique avec l'optimisation classique. Ces algorithmes visent généralement à déterminer le vecteur propre et la valeur propre de l'état fondamental d'un opérateur hermitien.

QAOA

L' algorithme d'optimisation approximative quantique est un modèle jouet de recuit quantique qui peut être utilisé pour résoudre des problèmes de théorie des graphes. L'algorithme utilise l'optimisation classique des opérations quantiques pour maximiser une fonction objectif.

Solveur propre quantique variationnel

L'algorithme VQE applique l'optimisation classique pour minimiser l'espérance d'énergie d'un état ansatz pour trouver l'énergie de l'état fondamental d'une molécule. Cela peut également être étendu pour trouver les énergies excitées des molécules.

Solveur propre quantique sous contrat

L'algorithme CQE minimise le résidu d'une contraction (ou projection) de l'équation de Schrödinger sur l'espace de deux (ou plus) électrons pour trouver l'énergie à l'état fondamental ou excité et la matrice de densité réduite à deux électrons d'une molécule. Il est basé sur des méthodes classiques de résolution d'énergies et de matrices à densité réduite à deux électrons directement à partir de l'équation de Schrödinger contractée anti-hermitienne.

Voir également

• Apprentissage automatique quantique
• Algorithmes d'optimisation quantique
• Tri quantique
• Test de primalité

Les références

Liens externes

• The Quantum Algorithm Zoo : Une liste complète d'algorithmes quantiques qui offrent une accélération par rapport aux algorithmes classiques connus les plus rapides.
• Notes de cours d'Andrew Childs sur les algorithmes quantiques
• L'algorithme de recherche quantique - force brute .

Enquêtes

• Smith, J.; Mosca, M. (2012). "Algorithmes pour les ordinateurs quantiques". Manuel d'informatique naturelle . p. 1451. doi : 10.1007/978-3-540-92910-9_43 . ISBN 978-3-540-92909-3. S2CID  16565723 .
• Childs, AM; Van Dam, W. (2010). « Algorithmes quantiques pour les problèmes algébriques ». Critiques de la physique moderne . 82 (1) : 1-52. arXiv : 0812.0380 . Bibcode : 2010RvMP ... 82 .... 1C . doi : 10.1103/RevModPhys.82.1 . S2CID  119261679 .