Aller au contenu

Algorithme quantique

Un article de Wikipédia, l'encyclopédie libre.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

La typographie de cet article ou de cette section ne respecte pas les conventions de Wikipédia (indiquez la date de pose grâce au paramètre date).

Vous pouvez corriger, en discuter sur l’Atelier typographique ou créer la discussion.

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 indécidables avec les ordinateurs classiques restent indécidables avec les ordinateurs quantiques[3] :127. 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 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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]
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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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é

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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 1 ,..., z n 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)[10].

Algorithmes basés sur l'amplification d'amplitude

[modifier | modifier le code]

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

[modifier | modifier le code]

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[11]. 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[12].

Comptage quantique

[modifier | modifier le code]

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[13],[14]. 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

[modifier | modifier le code]

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

[modifier | modifier le code]
Article détaillé : Boson sampling.

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

[modifier | modifier le code]

Le « problème de distinction des éléments » consiste à déterminer si tous les éléments d'une liste sont distincts. Classiquement, des requêtes sont requises pour une liste de taille  ; cependant, cela peut être résolu en 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

[modifier | modifier le code]

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 , 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

[modifier | modifier le code]

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 requêtes utilisant le caractère aléatoire[29], où . Avec un algorithme quantique, il peut cependant être résolu en 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

[modifier | modifier le code]

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 : et , respectivement[31]. Un algorithme quantique nécessite requêtes, tandis que l'algorithme classique le plus connu utilise requêtes[32].

Problèmes BQP-complets

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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 , 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 , 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 en (ou pour les matrices semi-définies positives).

Algorithmes hybrides quantiques/classiques

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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é

[modifier | modifier le code]

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

Références

[modifier | modifier le code]
  1. ↑ Michael A. Nielsen et Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, (ISBN 978-0-521-63503-5)
  2. ↑ Marco Lanzagorta et Jeffrey K. Uhlmann, Quantum Computer Science, Morgan & Claypool Publishers, (ISBN 978-1-59829-732-4, lire en ligne)
  3. ↑ Michael A. Nielsen et Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge, 2nd, (ISBN 978-1-107-00217-3, lire en ligne)
  4. ↑ « Shor's algorithm » [archive du ] (consulté le )
  5. ↑ « IBM quantum composer user guide: Grover's algorithm » [archive du ], quantum-computing.ibm.com (consulté le )
  6. ↑ a et b Farhi, Goldstone et Gutmann, « A Quantum Algorithm for the Hamiltonian NAND Tree », Theory of Computing, vol. 4,‎ , p. 169–190 (DOI 10.4086/toc.2008.v004a008, arXiv quant-ph/0702144)
  7. ↑ Childs et van Dam, « Quantum algorithms for algebraic problems », Reviews of Modern Physics, vol. 82, no 1,‎ , p. 1–52 (DOI 10.1103/RevModPhys.82.1, Bibcode 2010RvMP...82....1C, arXiv 0812.0380, S2CID 119261679)
  8. ↑ Shor, « Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer », SIAM Journal on Scientific and Statistical Computing, vol. 26, no 5,‎ , p. 1484–1509 (DOI 10.1137/s0097539795293172, Bibcode 1995quant.ph..8027S, arXiv quant-ph/9508027, S2CID 2337707)
  9. ↑ (en) D. Boneh et R. J. Lipton « Quantum cryptoanalysis of hidden linear functions » ()
    — « (ibid.) », dans Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, Springer-Verlag (ISBN 3-540-60221-6), p. 424-437
  10. ↑ (en) S. Aaronson, « BQP and the Polynomial Hierarchy », .
  11. ↑ (en) Lov K. Grover, « A fast quantum mechanical algorithm for database search », .
  12. ↑ Aaronson, « Quantum Computing and Hidden Variables »
  13. ↑ G. Brassard, P. Hoyer et A. Tapp, Automata, Languages and Programming, vol. 1443, coll. « Lecture Notes in Computer Science », , 820–831 p. (ISBN 978-3-540-64781-2, DOI 10.1007/BFb0055105, arXiv quant-ph/9805082, S2CID 14147978), « Quantum counting »
  14. ↑ G. Brassard, P. Hoyer, M. Mosca et A. Tapp, Quantum Computation and Quantum Information, vol. 305, coll. « AMS Contemporary Mathematics », , 53–74 p. (ISBN 978-0-8218-2140-4, DOI 10.1090/conm/305/05215, Bibcode 2000quant.ph..5055B, arXiv quant-ph/0005055, S2CID 54753), « Quantum Amplitude Amplification and Estimation »
  15. ↑ A. M. Childs et R. Cleve « Exponential algorithmic speedup by quantum walk » () (DOI 10.1145/780542.780552, arXiv quant-ph/0209131)
    — « (ibid.) », dans Proceedings of the 35th Symposium on Theory of Computing, Association for Computing Machinery (ISBN 1-58113-674-9), p. 59–68
  16. ↑ A. M. Childs et L. J. Schulman « Quantum Algorithms for Hidden Nonlinear Structures » () (DOI 10.1109/FOCS.2007.18, arXiv 0705.2784)
    — « (ibid.) », dans Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, IEEE (ISBN 978-0-7695-3010-9), p. 395–404
  17. ↑ a et b F. Magniez et A. Nayak « Search via quantum walk » () (DOI 10.1145/1250790.1250874, arXiv quant-ph/0608026)
    — « (ibid.) », dans Proceedings of the 39th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ISBN 978-1-59593-631-8), p. 575–584
  18. ↑ Ralph, « Figure 1: The boson-sampling problem », Nature Photonics, Nature, vol. 7, no 7,‎ , p. 514–515 (DOI 10.1038/nphoton.2013.175, S2CID 110342419, lire en ligne Inscription nécessaire, consulté le )
  19. ↑ (en) Peruzzo, Lobino, Matthews et Matsuda, « Quantum Walks of Correlated Photons », Science, vol. 329, no 5998,‎ , p. 1500–1503 (ISSN 0036-8075, PMID 20847264, DOI 10.1126/science.1193515, Bibcode 2010Sci...329.1500P, arXiv 1006.4764, hdl 10072/53193, S2CID 13896075, lire en ligne)
  20. ↑ Lund, Laing, Rahimi-Keshari et Rudolph, « Boson Sampling from Gaussian States », Phys. Rev. Lett., vol. 113, no 10,‎ (PMID 25238340, DOI 10.1103/PhysRevLett.113.100502, Bibcode 2014PhRvL.113j0502L, arXiv 1305.4346, S2CID 27742471)
  21. ↑ « The quantum revolution is a step closer », Phys.org, Omicron Technology Limited (consulté le )
  22. ↑ Seshadreesan, Olson, Motes et Rohde, « Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics », Physical Review A, vol. 91, no 2,‎ (DOI 10.1103/PhysRevA.91.022334, Bibcode 2015PhRvA..91b2334S, arXiv 1402.0531, S2CID 55455992)
  23. ↑ Ambainis, « Quantum Walk Algorithm for Element Distinctness », SIAM Journal on Computing, vol. 37, no 1,‎ , p. 210–239 (DOI 10.1137/S0097539705447311, arXiv quant-ph/0311001, S2CID 6581885)
  24. ↑ Y. Shi « The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. » () (DOI 10.1109/SFCS.2002.1181975, arXiv quant-ph/0112086)
    —Proceedings of the 43rd Symposium on Foundations of Computer Science
  25. ↑ Ambainis, « Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range », Theory of Computing, vol. 1, no 1,‎ , p. 37–46 (DOI 10.4086/toc.2005.v001a003)
  26. ↑ Kutin, « Quantum Lower Bound for the Collision Problem with Small Range », Theory of Computing, vol. 1, no 1,‎ , p. 29–36 (DOI 10.4086/toc.2005.v001a002)
  27. ↑ Magniez, Santha et Szegedy, « Quantum Algorithms for the Triangle Problem », SIAM Journal on Computing, vol. 37, no 2,‎ , p. 413–424 (DOI 10.1137/050643684, arXiv quant-ph/0310134, S2CID 594494)
  28. ↑ Aaronson, « NAND now for something completely different », Shtetl-Optimized, (consulté le )
  29. ↑ M.E. Saks et A. Wigderson « Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees » () (DOI 10.1109/SFCS.1986.44, lire en ligne)
    — « (ibid.) », dans Proceedings of the 27th Annual Symposium on Foundations of Computer Science, IEEE (ISBN 0-8186-0740-8), p. 29–38
  30. ↑ B. W. Reichardt et R. Spalek « Span-program-based quantum algorithm for evaluating formulas » () (DOI 10.1145/1374376.1374394, arXiv 0710.2630)
    — « (ibid.) », dans Proceedings of the 40th Annual ACM symposium on Theory of Computing, Association for Computing Machinery (ISBN 978-1-60558-047-0), p. 103–112
  31. ↑ Pak, « Testing commutativity of a group and the power of randomization », LMS Journal of Computation and Mathematics, vol. 15,‎ , p. 38–43 (DOI 10.1112/S1461157012000046)
  32. ↑ Magniez et Nayak, « Quantum Complexity of Testing Group Commutativity », Algorithmica, vol. 48, no 3,‎ , p. 221–232 (DOI 10.1007/s00453-007-0057-8, arXiv quant-ph/0506265, S2CID 3163328)
  33. ↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. (ISBN 0-521-63503-9).
  34. ↑ D. Aharonov et V. Jones « A polynomial quantum algorithm for approximating the Jones polynomial » () (DOI 10.1145/1132516.1132579, arXiv quant-ph/0511096)
    — « (ibid.) », dans Proceedings of the 38th Annual ACM symposium on Theory of Computing, Association for Computing Machinery (ISBN 1-59593-134-1), p. 427–436
  35. ↑ Feynman, « Simulating physics with computers », International Journal of Theoretical Physics, vol. 21, nos 6–7,‎ , p. 467–488 (DOI 10.1007/BF02650179, Bibcode 1982IJTP...21..467F, S2CID 124545445, CiteSeerx 10.1.1.45.9310)
  36. ↑ Abrams et Lloyd, « Simulation of many-body Fermi systems on a universal quantum computer », Physical Review Letters, vol. 79, no 13,‎ , p. 2586–2589 (DOI 10.1103/PhysRevLett.79.2586, Bibcode 1997PhRvL..79.2586A, arXiv quant-ph/9703054, S2CID 18231521)
  37. ↑ Kassal, Jordan, Love et Mohseni, « Polynomial-time quantum algorithm for the simulation of chemical dynamics », Proceedings of the National Academy of Sciences of the United States of America, vol. 105, no 48,‎ , p. 18681–86 (PMID 19033207, PMCID 2596249, DOI 10.1073/pnas.0808245105, Bibcode 2008PNAS..10518681K, arXiv 0801.2986)
  38. ↑ Freedman, Kitaev et Wang, « Simulation of Topological Field Theories by Quantum Computers », Communications in Mathematical Physics, vol. 227, no 3,‎ , p. 587–603 (DOI 10.1007/s002200200635, Bibcode 2002CMaPh.227..587F, arXiv quant-ph/0001071, S2CID 449219)
  39. ↑ Aharonov, Jones et Landau, « A polynomial quantum algorithm for approximating the Jones polynomial », Algorithmica, vol. 55, no 3,‎ , p. 395–421 (DOI 10.1007/s00453-008-9168-0, arXiv quant-ph/0511096, S2CID 7058660)
  40. ↑ Wocjan et Yard, « The Jones polynomial: quantum algorithms and applications in quantum complexity theory », Quantum Information and Computation, vol. 8, no 1,‎ , p. 147–180 (DOI 10.26421/QIC8.1-2-10, Bibcode 2006quant.ph..3069W, arXiv quant-ph/0603069, S2CID 14494227)
  41. ↑ Alagic, Jordan, König et Reichardt, « Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation », Physical Review A, vol. 82, no 4,‎ (DOI 10.1103/PhysRevA.82.040302, Bibcode 2010PhRvA..82d0302A, arXiv 1003.0923, S2CID 28281402)
  42. ↑ Harrow, Hassidim et Lloyd, « Quantum algorithm for solving linear systems of equations », Physical Review Letters, vol. 103, no 15,‎ (PMID 19905613, DOI 10.1103/PhysRevLett.103.150502, Bibcode 2009PhRvL.103o0502H, arXiv 0811.3171, S2CID 5187993)
  43. ↑ Moll, Barkoutsos, Bishop et Chow, « Quantum optimization using variational algorithms on near-term quantum devices », Quantum Science and Technology, vol. 3, no 3,‎ , p. 030503 (DOI 10.1088/2058-9565/aab822, Bibcode 2018QS&T....3c0503M, arXiv 1710.01022, S2CID 56376912)
  44. ↑ (en) Peruzzo, McClean, Shadbolt et Yung, « A variational eigenvalue solver on a photonic quantum processor », Nature Communications, vol. 5, no 1,‎ , p. 4213 (ISSN 2041-1723, PMID 25055053, PMCID 4124861, DOI 10.1038/ncomms5213, Bibcode 2014NatCo...5.4213P, arXiv 1304.3061)
  45. ↑ Higgott, Wang et Brierley, « Variational Quantum Computation of Excited States », Quantum, vol. 3,‎ (DOI 10.22331/q-2019-07-01-156, Bibcode 2019Quant...3..156H, arXiv 1805.08138, S2CID 119185497)
  46. ↑ (en) Smart et Mazziotti, « Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices », Phys. Rev. Lett., vol. 125, no 7,‎ (PMID 33666467, DOI 10.1103/PhysRevLett.126.070504, Bibcode 2021PhRvL.126g0504S, arXiv 2004.11416, S2CID 216144443)
  47. ↑ (en) Mazziotti, « Anti-Hermitian Contracted Schrödinger Equation: Direct Determination of the Two-Electron Reduced Density Matrices of Many-Electron Molecules », Phys. Rev. Lett., vol. 97, no 14,‎ (PMID 17155245, DOI 10.1103/PhysRevLett.97.143002, Bibcode 2006PhRvL..97n3002M)

Voir aussi

[modifier | modifier le code]

Bibliographie

[modifier | modifier le code]

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Algorithme_quantique&oldid=230509723 ».