Algorithme quantique

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^[1].

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és sur un ordinateur quantique^{[2] :126}, 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 qui sont indécidables avec les ordinateurs classiques restent indécidables avec les ordinateurs quantiques^{[3] :127} , mais 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 général de corps de nombres^[4]. De même, l'algorithme de Grover fonctionnerait quadratiquement plus vite que le meilleur algorithme classique possible pour la même tâche^[5] (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 oracle hamiltonien^[6].

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^[7].

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 <sub id="mwUQ">corps</sub> <b id="mwUA">F₂</b>. La transformée de Fourier quantique peut être implémentée sur un ordinateur quantique en utilisant seulement un nombre polynomial de portes quantiques^{[ citation nécessaire ]}.

Algorithme de Deutsch-Jozsa

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 séparation oracle 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^[8], 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^[9]. 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 n fonctions booléennes aléatoires mappant des chaînes de n bits à une valeur booléenne, dans le but de 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 satisfassent

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

et au moins 1/4 satisfont

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

Cela peut être réalisé en temps polynomial quantique à erreur bornée (BQP)^[10].

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. ^{[ citation nécessaire ]}

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 ${\displaystyle O({\sqrt {N}})}$ requêtes au lieu de la ${\displaystyle O({N})}$ requêtes requises classiquement^[11]. Classiquement, ${\displaystyle O({N})}$ 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 ${\displaystyle O({\sqrt[{3}]{N}})}$ étapes. C'est légèrement plus rapide que le ${\displaystyle O({\sqrt {N}})}$ É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^[12].

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. ${\displaystyle N}$ -liste d'éléments avec une erreur d'au plus ${\displaystyle \varepsilon }$ en faisant seulement ${\displaystyle \Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)}$ requêtes, où ${\displaystyle k}$ est le nombre d'éléments marqués dans la liste^[13],[14]. Plus précisément, l'algorithme génère une estimation ${\displaystyle k'}$ pour ${\displaystyle k}$, le nombre d'entrées marquées, avec précision ${\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. 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^[15],[16].

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^[17].

Problème d'échantillonnage de bosons

Le problème d'échantillonnage de bosons dans une configuration expérimentale suppose^[18] une entrée de bosons (par exemple, des photons) en nombre modéré qui sont dispersés aléatoirement dans un grand nombre de modes de sortie, contraints par une unitarité définie. Lorsque des photons individuels sont utilisés, le problème est isomorphe à une marche quantique multiphotonique^[19]. Le problème est alors de produire un échantillon équitable de la distribution de probabilité de la sortie qui dépend de la disposition d'entrée des bosons et de l'unitarité^[20]. Résoudre ce problème avec un algorithme informatique classique nécessite de calculer la permanente de la matrice de transformée unitaire, ce qui peut prendre un temps prohibitif ou être totalement impossible. En 2014, il a été proposé^[21] 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 en utilisant des algorithmes quantiques. En 2015, une étude a prédit^[22] que le problème d'échantillonnage avait une complexité similaire pour les entrées autres que les photons à l'état de Fock et a identifié une transition dans la complexité de calcul de classiquement simulable à tout aussi difficile que le problème d'échantillonnage de boson, en fonction de la taille des entrées d'amplitude cohérentes.

Problème de distinction des éléments

Le « problème de distinction des éléments » consiste à déterminer si tous les éléments d'une liste sont distincts. Classiquement, ${\displaystyle \Omega (N)}$ des requêtes sont requises pour une liste de taille ${\displaystyle N}$ ; cependant, cela peut être résolu en ${\displaystyle \Theta (N^{2/3})}$ requêtes sur un ordinateur quantique.

L'algorithme optimal a été proposé par Andris Ambainis^[23] et Yaoyun Shi a d'abord prouvé une borne inférieure stricte lorsque la taille de la plage est suffisamment grande^[24] Ambainis^[25] et Kutin^[26] ont indépendamment (et via des preuves différentes) étendu ce travail pour obtenir la borne inférieure pour toutes les fonctions.

Problème de recherche de triangles

Le problème de recherche de triangles consiste à déterminer si un graphe donné contient un triangle (une clique de taille 3). La borne inférieure la plus connue pour les algorithmes quantiques est ${\displaystyle \Omega (N)}$, mais le meilleur algorithme connu nécessite O( N ^1,297) requêtes, une amélioration par rapport aux meilleures requêtes précédentes O( N ^1,3 )^[17],[27].

Évaluation de la formule

Une formule est un arbre comportant une porte à chaque nœud interne et un bit d'entrée à chaque nœud feuille. Le problème consiste à évaluer la formule, qui est la sortie du nœud racine, en disposant d'un accès Oracle à l'entrée.

Une formule bien étudiée est l'arbre binaire équilibré avec seulement des portes NAND^[28]. Ce type de formule nécessite ${\displaystyle \Theta (N^{c})}$ requêtes utilisant le caractère aléatoire^[29], où ${\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754}$. Avec un algorithme quantique, il peut cependant être résolu en ${\displaystyle \Theta (N^{1/2})}$ Requêtes. Aucun algorithme quantique meilleur n'était connu pour ce cas jusqu'à ce qu'un autre soit trouvé pour le modèle oracle hamiltonien non conventionnel^[6] ; le même résultat a rapidement suivi pour la définition standard.

Des algorithmes quantiques rapides pour des formules plus complexes sont également connus^[30].

Commutativité de groupe

Le problème consiste à déterminer si un groupe de type boîte noire, donné par k générateurs, est commutatif. En informatique quantique, une fonction oracle est une « boîte noire » qui fournit sur demande les opérations du groupe (comme la multiplication, l'inversion ou le test d'identité) sans révéler sa structure interne. Un groupe de type boîte noire est un groupe doté d'une fonction oracle, qui doit être utilisée pour effectuer les opérations de groupe (multiplication, inversion et comparaison avec identité). L'intérêt dans ce contexte réside dans la complexité de la requête, qui correspond au nombre d'appels oracle nécessaires à la résolution du problème. Les complexités des requêtes déterministes et randomisées sont : ${\displaystyle \Theta (k^{2})}$ et ${\displaystyle \Theta (k)}$, respectivement^[31]. Un algorithme quantique nécessite ${\displaystyle \Omega (k^{2/3})}$ requêtes, tandis que l'algorithme classique le plus connu utilise ${\displaystyle O(k^{2/3}\log k)}$ requêtes^[32].

Problèmes BQP-complets

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

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

Calcul des invariants de nœuds

Witten a montré que la théorie quantique topologique des champs de Chern-Simons (TQFT) peut être résolue en termes de polynômes de Jones.

Un ordinateur quantique peut simuler une TQFT et ainsi approximer le polynôme de Jones^[34], qui est difficile à calculer classiquement dans le pire des cas. ^{[ citation nécessaire ]}

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, alors que les systèmes quantiques à plusieurs corps sont capables de « se résoudre eux-mêmes »^[35].

Depuis lors, l'idée que les ordinateurs quantiques puissent simuler des processus de physique quantique exponentiellement plus vite 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 les systèmes bosoniques et fermioniques^[36], ainsi que pour la simulation de réactions chimiques au-delà des capacités des supercalculateurs classiques actuels, en utilisant seulement quelques centaines de qubits^[37]. Les ordinateurs quantiques peuvent aussi simuler les théories quantiques topologiques des champs^[38]. Outre 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^[39] et de HOMFLY^[40] et l'invariant de Turaev-Viro des variétés tridimensionnelles^[41].

Résolution d'un système d'équations linéaires

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

À condition que le système linéaire soit clairsemé et ait un faible nombre de conditions ${\displaystyle \kappa }$, et que l'utilisateur est intéressé par le résultat d'une mesure scalaire sur le vecteur solution (au lieu des valeurs du vecteur solution lui-même), alors l'algorithme a un temps d'exécution de ${\displaystyle O(\log(N)\kappa ^{2})}$, où ${\displaystyle N}$ 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 en ${\displaystyle O(N\kappa )}$ (ou ${\displaystyle O(N{\sqrt {\kappa }})}$ pour les matrices semi-définies positives).

Algorithmes hybrides quantiques/classiques

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

QAOA

L'algorithme d'optimisation approximative quantique s'inspire du recuit quantique et réalise une approximation discrétisée du recuit quantique à l'aide d'un circuit quantique. Il 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 objective ».

Solveur propre quantique variationnel

L'algorithme de résolution propre quantique variationnelle (VQE) applique une optimisation classique pour minimiser la valeur d'espérance énergétique d'un état ansatz afin de trouver l'état fondamental d'un opérateur hermitien, tel que l'hamiltonien d'une molécule^[44]. Il peut également être étendu pour trouver les énergies excitées des hamiltoniens moléculaires^[45].

Résolveur propre quantique contracté

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