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 à ce jour le modèle de circuit quantique..
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 exécutée sur un ordinateur quantique. Tout algorithme classique peut être exécuté sur un ordinateur quantique. , mais l'expression « algorithme quantique » est généralement réservé aux algorithmes qui semblent intrinsèquement quantiques, ou qui utilisent une caractéristique essentielle du calcul quantique (superposition quantique ou intrication quantique).
Les problèmes indécidables avec les ordinateurs classiques restent indécidables avec les ordinateurs quantiques.. Cependant, les algorithmes quantiques peuvent à certaines conditions résoudre certains problèmes bien plus rapidement que les algorithmes classiques, car la superposition quantique et l'intrication quantique qu'exploitent les algorithmes quantiques ne peuvent généralement pas être simulées efficacement sur des ordinateurs classiques (on parle de suprématie quantique).
Les algorithmes les plus connus sont l'algorithme de Shor pour la factorisation, et l'algorithme de Grover pour la recherche au sein d'une base de données non structurée ou au sein d'une liste non ordonnée. L'algorithme de Shor, s'il était implémenté, fonctionnerait beaucoup (presque exponentiellement) plus vite que l'algorithme classique le plus efficace connu pour la factorisation, le crible du corps de nombres généralisé.. De même, l'algorithme de Grover fonctionnerait quadratiquement plus vite que le meilleur algorithme classique possible pour la même tâche., la recherche linéaire.
Aperçu Les algorithmes quantiques sont généralement décrits, dans le modèle de circuit couramment utilisé en calcul quantique, par un circuit quantique agissant sur des qubits d'entrée, et se terminant par une mesure. Un circuit quantique est constitué de portes quantiques simples, chacune agissant sur un nombre fini de qubits. Les algorithmes quantiques peuvent également être exprimés dans d'autres modèles de calcul quantique, comme le modèle d'oracle hamiltonien..
Les algorithmes quantiques peuvent être classés selon les principales techniques utilisées. Parmi les techniques et concepts fréquemment utilisés en algorithmes quantiques, on peut citer le retour de phase (phase kick-back), l'estimation de phase, la transformée de Fourier quantique, les marches quantiques (quantum walks), l'amplification d'amplitude et la théorie quantique topologique des champs. Les algorithmes quantiques peuvent aussi être classés selon le type de problème résolu ; voir, par exemple, l'étude 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 (analogue quantique de la transformée de Fourier discrète) est utilisée dans plusieurs algorithmes quantiques. La transformée de Hadamard est un exemple de transformée de Fourier quantique sur un espace vectoriel n-dimensionnel sur le corps . La transformée de Fourier quantique peut être implémentée sur un ordinateur quantique en utilisant seulement un nombre polynomial de portes quantiques.
Algorithme de Deutsch-Jozsa vignette|Algorithme de Deutsch-Jozsa L'algorithme de Deutsch-Jozsa résout un problème de boîte noire (qui nécessite un nombre exponentiel de requêtes pour tout ordinateur classique déterministe, mais qui peut être résolu en une seule requête pour un ordinateur quantique). Cependant, la comparaison entre les algorithmes classiques et quantiques à erreur bornée ne présente aucun gain d'accélération, car un algorithme probabiliste classique peut résoudre le problème avec un nombre constant de requêtes et une faible probabilité d'erreur. L'algorithme détermine si une fonction f est constante (0 sur toutes les entrées ou 1 sur toutes les entrées) ou équilibrée (renvoie 1 pour la moitié du domaine d'entrée et 0 pour l'autre moitié).
Algorithme de Bernstein – Vazirani C'est le premier algorithme quantique à résoudre un problème plus efficacement que le meilleur algorithme classique connu. Il a été conçu pour créer une entre BQP et BPP.
L'algorithme de Simon Il résout un problème de boîte noire exponentiellement plus vite que n'importe quel algorithme classique connu pour être efficace, y compris les algorithmes probabilistes à erreur bornée. Il a été à l'origine de l'algorithme de factorisation de Shor.
Algorithme d'estimation de phase quantique L'algorithme d'estimation de phase quantique permet de déterminer (mesurer) la phase propre du vecteur propre d'une porte unitaire (une « phase » particulière, associée à un état quantique particulier). Pour cela, il faut disposer d'un état quantique lié à cet état et pouvoir utiliser la porte quantique correspondante.
Cet algorithme est souvent utilisé comme une étape intermédiaire dans d'autres algorithmes quantiques plus complexes.
L'algorithme de Shor Cet algorithme résout rapidement le problème du logarithme discret et le problème de factorisation entière en temps polynomial., alors que les algorithmes classiques les plus connus prennent un temps super-polynomial pour cela.
On ignore si ces problèmes sont en P ou NP-complet. C'est aussi l'un des rares algorithmes quantiques qui résout un problème de non-boîte noire en temps polynomial, là où les algorithmes classiques les plus connus s'exécutent en temps super-polynomial (en algorithmique quantique ou classique, on dit qu'un algorithme s'exécute en temps polynomial si le nombre d'étapes nécessaires croît comme une puissance du nombre d'entrées, tandis qu'un temps super-polynomial désigne une croissance plus rapide que toute puissance polynomiale - par exemple exponentielle ou quasi-exponentielle - et donc beaucoup plus coûteuse à grande échelle).
Problème de sous-groupe caché Le problème du sous-groupe caché abélien est une généralisation de nombreux problèmes solubles par 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. Des algorithmes quantiques efficaces sont connus pour le problème du sous-groupe caché abélien.. Le problème plus général du sous-groupe caché, où le groupe n'est pas nécessairement abélien, est une généralisation des problèmes mentionnés précédemment, ainsi que de l'isomorphisme de graphes et de certains problèmes de treillis. 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 de graphes et le groupe diédrique, qui résoudrait certains problèmes de treillis.
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. Puisque 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 calculer les 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 vérification de Fourier Considérons un oracle composé de fonctions booléennes aléatoires mappant des chaînes de bits à une valeur booléenne, dans le but de trouver chaînes de bits telles que pour la transformée de Hadamard-Fourier, au moins 3/4 des chaînes satisfassent,
,
et au moins 1/4 satisfont,
Cela peut être réalisé en temps polynomial quantique à erreur bornée (BQP)..
Algorithmes basés sur l'amplification d'amplitude L'amplification d'amplitude est une technique permettant d'amplifier un sous-espace choisi d'un état quantique. Ses applications conduisent généralement à des accélérations quadratiques par rapport aux algorithmes classiques correspondants. Elle peut être considérée comme une généralisation de l'algorithme de Grover.
L'algorithme de Grover L'algorithme de Grover recherche une entrée marquée dans une base de données non structurée (ou une liste non ordonnée) avec N entrées, en utilisant uniquement requêtes au lieu de la requêtes requises classiquement.. Classiquement, des requêtes sont nécessaires même en autorisant des algorithmes probabilistes à erreur limitée.
Les théoriciens ont envisagé une généralisation hypothétique d'un ordinateur quantique standard qui pourrait accéder aux historiques des variables cachées dans la mécanique bohmienne. (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 implémenter une recherche dans une base de données N-item dans au plus étapes. C'est légèrement plus rapide que le Étapes suivies par l'algorithme de Grover. Cependant, aucune méthode 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..
Comptage quantique Le comptage quantique résout une généralisation du problème de recherche. Il résout le problème du comptage du nombre d'entrées marquées dans une liste non ordonnée, au lieu de simplement détecter leur existence. Plus précisément, il compte le nombre d'entrées marquées dans une liste non ordonnée. -liste d'éléments avec une erreur d'au plus en faisant seulement 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 précision .
Algorithmes basés sur les marches quantiques Une marche quantique est l'analogue quantique d'une marche aléatoire classique. Une marche aléatoire classique peut être décrite par une distribution de probabilité sur certains états, tandis qu'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 type boîte noire...
Elles fournissent aussi des accélérations polynomiales pour de nombreux problèmes. Il existe un cadre pour la création d'algorithmes de marche quantique, un outil polyvalent..
Problème d'échantillonnage de bosons