Ceci est un catalogue complet des algorithmes quantiques. Si vous remarquez des erreurs ou des omissions, veuillez m'envoyer un e-mail à spj.jordan@gmail.com. (Alternativement, vous pouvez soumettre une pull request sur ce dépôt GitHub.) Bien que je ne puisse garantir une réponse rapide, votre aide est appréciée et sera reconnue.
Algorithmes Algébriques et Théoriques des Nombres
Algorithme : FactorisationAccélération : Superpolynomiale
Implémentation : Classiq, Cirq
Description : Étant donné un entier n-bit, trouver la factorisation en nombres premiers. L'algorithme quantique de Peter Shor résout cela en \( \widetilde{O} (n^3) \) temps [82,125]. L'algorithme classique le plus rapide connu pour la factorisation d'entiers est le crible général des nombres, qui est censé fonctionner en temps \( 2^{\widetilde{O}(n^{1/3})} \). La meilleure limite supérieure rigoureusement prouvée sur la complexité classique de la factorisation est \( O(2^{n/4+o(1)}) \) via l'algorithme de Pollard-Strassen [252, 362]. L'algorithme de factorisation de Shor brise le chiffrement à clé publique RSA et les algorithmes quantiques étroitement liés pour les logarithmes discrets brisent les schémas de signature numérique DSA et ECDSA et le protocole d'échange de clés de Diffie-Hellman. Un algorithme quantique encore plus rapide que celui de Shor pour le cas spécial de la factorisation des « semi-premiers », qui sont largement utilisés en cryptographie, est donné dans [271]. Si de petits facteurs existent, l'algorithme de Shor peut être battu par un algorithme quantique utilisant la recherche de Grover pour accélérer la méthode de factorisation par courbe elliptique [366]. Des versions optimisées supplémentaires de l'algorithme de Shor sont données dans [384, 386, 431]. Il existe des systèmes de chiffrement à clé publique classiques qui ne sont pas censés être brisés par des algorithmes quantiques, cf. [248]. Au cœur de l'algorithme de factorisation de Shor se trouve la recherche d'ordre, qui peut être réduite au problème du sous-groupe caché abélien, qui est résolu à l'aide de la transformation de Fourier quantique. Un certain nombre d'autres problèmes sont connus pour se réduire à la factorisation entière, y compris le problème d'appartenance pour les groupes de matrices sur des corps de degré impair [253], et certains problèmes diophantiens pertinents pour la synthèse de circuits quantiques [254].
Algorithme : Logarithme discret
Accélération : Superpolynomiale
Implémentation : Classiq
Description : Nous avons trois nombres n-bit a, b, et N, avec la promesse que \( b = a^s \mod N \) pour un certain s. La tâche est de trouver s. Comme le montre Shor [82], cela peut être réalisé sur un ordinateur quantique en poly(n) temps. L'algorithme classique le plus rapide nécessite un temps superpolynomial en n. Grâce à des techniques similaires à celles de [82], les ordinateurs quantiques peuvent résoudre le problème du logarithme discret sur des courbes elliptiques, brisant ainsi la cryptographie à courbe elliptique [109, 14]. D'autres optimisations de l'algorithme de Shor sont données dans [385, 432]. L'accélération quantique superpolynomiale a également été étendue au problème du logarithme discret sur des semi-groupes [203, 204]. Voir aussi sous-groupe caché abélien.
Algorithme : Équation de Pell
Accélération : Superpolynomiale
Description : Étant donné un entier positif non carré d, l'équation de Pell est \( x^2 - d y^2 = 1 \). Pour tout d tel que il existe une infinité de paires d'entiers (x,y) résolvant cette équation. Soit \( (x_1,y_1) \) la paire qui minimise \( x+y\sqrt{d} \). Si d est un entier n-bit (c'est-à-dire \( 0 \leq d \lt 2^n \) ), \( (x_1,y_1) \) peut en général nécessiter un nombre exponentiel de bits pour être écrit. Ainsi, il est en général impossible de trouver \( (x_1,y_1) \) en temps polynomial. Soit \( R = \log(x_1+y_1 \sqrt{d}) \). \( \lfloor R \rceil \) identifie de manière unique \( (x_1,y_1) \). Comme le montre Hallgren [49], étant donné un nombre n-bit d, un ordinateur quantique peut trouver \( \lfloor R \rceil \) en poly(n) temps. Aucun algorithme classique en temps polynomial pour ce problème n'est connu. La factorisation se réduit à ce problème. Cet algorithme brise le système de cryptage Buchman-Williams. Voir aussi sous-groupe caché abélien.
Algorithme : Idéal Principal
Accélération : Superpolynomiale
Description : Nous avons un entier n-bit d et un idéal inversible I de l'anneau \( \mathbb{Z}[\sqrt{d}] \). I est un idéal principal s'il existe \( \alpha \in \mathbb{Q}(\sqrt{d}) \) tel que \( I = \alpha \mathbb{Z}[\sqrt{d}] \). \( \alpha \) peut être exponentiellement grand en d. Par conséquent, \( \alpha \) ne peut en général même pas être écrit en temps polynomial. Cependant, \( \lfloor \log \alpha \rceil \) identifie de manière unique \( \alpha \). La tâche est de déterminer si I est principal et si oui, de trouver \( \lfloor \log \alpha \rceil \). Comme le montre Hallgren, cela peut être fait en temps polynomial sur un ordinateur quantique [49]. Un algorithme quantique modifié pour ce problème utilisant moins de qubits a été donné dans [131]. Un algorithme quantique résolvant le problème de l'idéal principal dans des corps de degré arbitraire (c'est-à-dire évoluant polynômialement en degré) a été donné par la suite dans [329]. La factorisation se réduit à la résolution de l'équation de Pell, qui se réduit au problème de l'idéal principal. Ainsi, le problème de l'idéal principal est au moins aussi difficile que la factorisation et n'est donc probablement pas dans P. Voir aussi sous-groupe caché abélien.
Algorithme : Groupe Unitaire
Accélération : Superpolynomiale
Description : Le corps de nombres \( \mathbb{Q}(\theta) \) est dit de degré d si le polynôme de plus bas degré dont \( \theta \) est une racine a un degré d. L'ensemble \( \mathcal{O} \) des éléments de \( \mathbb{Q}(\theta) \) qui sont racines de polynômes moniques dans \( \mathbb{Z}[x] \) forme un anneau, appelé l'anneau des entiers de \( \mathbb{Q}(\theta) \). L'ensemble des unités (éléments inversibles) de l'anneau \( \mathcal{O} \) forme un groupe noté \( \mathcal{O}^* \). Comme le montre Hallgren [50], et indépendamment par Schmidt et Vollmer [116], pour tout \( \mathbb{Q}(\theta) \) de degré fixe, un ordinateur quantique peut trouver en temps polynomial un ensemble de générateurs pour \( \mathcal{O}^* \) donné une description de \( \theta \). Aucun algorithme classique en temps polynomial pour ce problème n'est connu. Hallgren et ses collaborateurs ont ensuite découvert comment obtenir une échelle polynomiale en degré [213]. Voir aussi [329]. Les algorithmes reposent sur la résolution de problèmes de sous-groupes cachés abéliens sur le groupe additif des réels.
Algorithme : Groupe de Classes
Accélération : Superpolynomiale
Description : Le corps de nombres \( \mathbb{Q}(\theta) \) est dit de degré d si le polynôme de plus bas degré dont \( \theta \) est une racine a un degré d. L'ensemble \( \mathcal{O} \) des éléments de \( \mathbb{Q}(\theta) \) qui sont racines de polynômes moniques dans \( \mathbb{Z}[x] \) forme un anneau, appelé l'anneau des entiers de \( \mathbb{Q}(\theta) \), qui est un domaine de Dedekind. Pour un domaine de Dedekind, les idéaux fractionnaires non nuls modulo les idéaux principaux non nuls forment un groupe appelé le groupe de classes. Comme le montre Hallgren [50], un ordinateur quantique peut trouver un ensemble de générateurs pour le groupe de classes de l'anneau des entiers de tout corps de nombres de degré constant, donné une description de \( \theta \), en temps poly(log(\( | \mathcal{O} | \))). Un algorithme quantique amélioré, dont le temps d'exécution est également polynomial en d, a été donné par la suite dans [329]. Aucun algorithme classique en temps polynomial pour ces problèmes n'est connu. Voir aussi sous-groupe caché abélien.
Algorithme : Sommes de Gauss
Accélération : Superpolynomiale
Description : Soit \( \mathbb{F}_q \) un corps fini. Les éléments autres que zéro de \( \mathbb{F}_q \) forment un groupe \( \mathbb{F}_q^\times \) sous multiplication, et les éléments de \( \mathbb{F}_q \) forment un groupe (abélien mais pas nécessairement cyclique) \( \mathbb{F}_q^+ \) sous addition. Nous pouvons choisir un certain caractère \( \chi^\times \) de \( \mathbb{F}_q^\times \) et un caractère \( \chi^+ \) de \( \mathbb{F}_q^+ \). La somme de Gauss correspondante est le produit intérieur de ces caractères : \( \sum_{x \neq 0 \in \mathbb{F}_q} \chi^+(x) \chi^\times(x) \) Comme le montre van Dam et Seroussi [90], les sommes de Gauss peuvent être estimées à une précision polynomiale sur un ordinateur quantique en temps polynomial. Bien qu'un anneau fini ne forme pas un groupe sous multiplication, son ensemble d'unités le fait. En choisissant une représentation pour le groupe additif de l'anneau, et en choisissant une représentation pour le groupe multiplicatif de ses unités, on peut obtenir une somme de Gauss sur les unités d'un anneau fini. Celles-ci peuvent également être estimées à une précision polynomiale sur un ordinateur quantique en temps polynomial [90]. Aucun algorithme classique en temps polynomial pour estimer les sommes de Gauss n'est connu. Le logarithme discret se réduit à l'estimation de la somme de Gauss [90]. Certaines fonctions de partition du modèle Potts peuvent être calculées par un algorithme quantique en temps polynomial lié à l'estimation de la somme de Gauss [47].
Algorithme : Preuve de Primalité
Accélération : Polynomiale
Description : Étant donné un nombre n-bit, retourner une preuve de sa primalité. Les algorithmes classiques les plus rapides sont AKS, dont les meilleures versions [393, 394] ont une complexité essentiellement quartique, et ECPP, où la complexité heuristique de la version la plus rapide [395] est également essentiellement quartique. L'algorithme quantique le plus rapide connu pour ce problème est la méthode de Donis-Vela et Garcia-Escartin [396], avec une complexité \( O(n^2 (\log \ n)^3 \log \ \log \ n) \). Cela améliore un algorithme quantique basé sur la factorisation pour la preuve de primalité [397] qui a une complexité \( O(n^3 \log \ n \ \log \ \log \ n) \). Un résultat récent de Harvey et Van Der Hoeven [398] peut être utilisé pour améliorer la complexité de l'algorithme quantique basé sur la factorisation pour la preuve de primalité à \( O(n^3 \log n) \) et il peut être possible de réduire de manière similaire la complexité de l'algorithme de Donis-Vela-Garcia-Escartin à \( O(n^2 (\log \ n)^3) \) [399].
Algorithme : Résolution de Congruences Exponentielles
Accélération : Polynomiale
Description : Nous avons \( a,b,c,f,g \in \mathbb{F}_q \). Nous devons trouver des entiers \(x,y\) tels que \( a f^x + b g^y = c \). Comme le montre [111], les ordinateurs quantiques peuvent résoudre ce problème en \( \widetilde{O}(q^{3/8}) \) temps alors que le meilleur algorithme classique nécessite \( \widetilde{O}(q^{9/8}) \) temps. L'algorithme quantique de [111] est basé sur les algorithmes quantiques pour les logarithmes discrets et la recherche.
Algorithme : Éléments de Matrice et Coefficients de Kronecker des Représentations de Groupes
Accélération : Superpolynomiale
Description : Toutes les représentations de groupes finis et de groupes linéaires compacts peuvent être exprimées comme des matrices unitaires données un choix approprié de base. Conjuguant la représentation régulière d'un groupe par le circuit de transformation de Fourier quantique sur ce groupe, on obtient une somme directe des représentations irréductibles du groupe. Ainsi, la transformation de Fourier quantique efficace sur le groupe symétrique [196], ainsi que le test de Hadamard, permettent un algorithme quantique rapide pour approximer individuellement les éléments de matrice des représentations irréductibles du \( S_n \). De même, en utilisant la transformation de Schur quantique [197], on peut approximer efficacement les éléments de matrice des représentations irréductibles de SU(n) qui ont un poids polynomial. Des mises en œuvre directes des représentations irréductibles individuelles pour les groupes U(n), SU(n), SO(n), et \( A_n \) par des circuits quantiques efficaces sont données dans [106]. Des instances qui semblent exponentiellement difficiles pour les algorithmes classiques connus sont également identifiées dans [106]. Les coefficients de Kronecker comptent la multiplicité d'une représentation irréductible donnée dans le produit tensoriel d'une paire de représentations irréductibles données. Dans [460], il est montré que les coefficients de Kronecker normalisés du groupe symétrique peuvent être approximés à une erreur additive inverse polynomiale par un algorithme quantique en temps polynomial, tandis qu'aucun algorithme classique en temps polynomial n'est connu pour atteindre cela.
Algorithme : Vérification des Produits de Matrices
Accélération : Polynomiale
Description : Étant donné trois matrices \( n \times n \), A,B, et C, le problème de vérification du produit de matrices consiste à décider si AB=C. Classiquement, le meilleur algorithme (randomisé) atteint cela en temps \( O(n^2) \), tandis que le meilleur algorithme classique pour la multiplication de matrices fonctionne en temps \( O(n^{2.373}) \). Ambainis et al. ont découvert un algorithme quantique pour ce problème avec un temps d'exécution \( O(n^{7/4}) \) [6]. Par la suite, Buhrman et Špalek ont amélioré cela, obtenant un algorithme quantique pour ce problème avec un temps d'exécution \( O(n^{5/3}) \) [19]. Cet algorithme est basé sur des résultats concernant les marches quantiques qui ont été prouvés dans [85].
Algorithme : Sous-ensemble-somme
Accélération : Polynomiale
Description : Étant donné une liste d'entiers \( x_1,\ldots,x_n \), et un entier cible s, le problème de sous-ensemble-somme consiste à déterminer si la somme de n'importe quel sous-ensemble des entiers donnés s'additionne à s. Ce problème est NP-complet, et il est donc peu probable qu'il soit résoluble par des algorithmes classiques ou quantiques avec une complexité pire que polynomiale. Dans les cas difficiles, les entiers donnés sont de l'ordre de \( 2^n \) et de nombreuses recherches sur le problème de sous-ensemble-somme se concentrent sur les instances de cas moyen dans ce régime. Dans [178], un algorithme quantique est donné qui résout de telles instances en temps \( 2^{0.241n} \), jusqu'à des facteurs polynomiaux. Cet algorithme quantique fonctionne en appliquant une variante de l'algorithme de marche quantique d'Ambainis pour l'élément distinct [7] pour accélérer un algorithme classique sophistiqué pour ce problème dû à Howgrave-Graham et Joux. L'algorithme classique le plus rapide pour de telles instances de sous-ensemble-somme fonctionne en temps \( 2^{0.291n} \), jusqu'à des facteurs polynomiaux [404].
Algorithme : Décodage
Accélération : Varie
Description : Les codes de correction d'erreurs classiques permettent la détection et la correction des inversions de bits en stockant les données de manière redondante. Le décodage par maximum de vraisemblance pour des codes linéaires arbitraires est NP-complet dans le pire des cas, mais pour des codes structurés ou des erreurs bornées, des algorithmes de décodage efficaces sont connus. Des algorithmes quantiques ont été formulés pour accélérer le décodage des codes convolutionnels [238] et des codes simplex [239].
Algorithme : Cryptanalyse Quantique
Accélération : Divers
Description : Il est bien connu que les algorithmes de Shor pour la factorisation et les logarithmes discrets [82,125] brisent complètement les systèmes de chiffrement RSA et Diffie-Hellman, ainsi que leurs variantes basées sur les courbes elliptiques [109, 14]. (Un certain nombre de systèmes de chiffrement à clé publique "post-quantique" ont été proposés pour remplacer ces primitives, qui ne sont pas connus pour être brisés par des attaques quantiques.) Au-delà de l'algorithme de Shor, il existe un corpus croissant de travaux sur des algorithmes quantique spécifiquement conçus pour attaquer les systèmes de chiffrement. Ces algorithmes tombent généralement dans trois catégories. La première est des algorithmes quantiques fournissant des attaques en temps polynomial ou sub-exponentiel sur des systèmes de chiffrement sous des hypothèses standard. En particulier, l'algorithme de Childs, Jao et Soukharev pour trouver des isogénies de courbes elliptiques brise certains systèmes de chiffrement basés sur des courbes elliptiques en temps subexponentiel qui n'ont pas déjà été brisés par l'algorithme de Shor [283]. La deuxième catégorie est des algorithmes quantiques réalisant une amélioration polynomiale par rapport aux attaques cryptanalytiques classiques connues en accélérant des parties de ces algorithmes classiques à l'aide de la recherche de Grover, de la recherche de collisions quantiques, etc. De telles attaques sur des clés privées [284, 285, 288, 315, 316] et des clés publiques [262, 287] ne précluent pas l'utilisation des systèmes de chiffrement associés mais peuvent influencer le choix de la taille de la clé. La troisième catégorie est des attaques qui utilisent des requêtes de superposition quantique sur des chiffrements par blocs. Ces attaques dans de nombreux cas brisent complètement les primitives cryptographiques [286, 289, 290, 291, 292]. Cependant, dans la plupart des situations pratiques, de telles requêtes de superposition sont peu susceptibles d'être réalisables.
Algorithmes Oraculaires
Algorithme : RechercheAccélération : Polynomiale
Implémentation : Classiq, Cirq
Description : Nous avons un oracle avec N entrées autorisées. Pour une entrée w ("le gagnant"), la sortie correspondante est 1, et pour toutes les autres entrées, la sortie correspondante est 0. La tâche est de trouver w. Sur un ordinateur classique, cela nécessite \( \Omega(N) \) requêtes. L'algorithme quantique de Lov Grover atteint cela en utilisant \( O(\sqrt{N}) \) requêtes [48], ce qui est optimal [216]. Cet algorithme a ensuite été généralisé pour rechercher en présence de plusieurs "gagnants" [15], évaluer la somme d'une fonction arbitraire [15,16,73], trouver la moyenne, la médiane et le minimum global d'une fonction arbitraire [35,75, 255,465,472], tirer parti d'états initiaux alternatifs [100] ou de priors probabilistes non uniformes [123], travailler avec des oracles dont le temps d'exécution varie entre les entrées [138], approximer des intégrales définies [77], et converger vers un point fixe [208, 209, 433]. Des considérations sur l'optimisation de la profondeur des circuits de recherche quantiques sont données dans [405]. La généralisation de l'algorithme de Grover connue sous le nom d'estimation d'amplitude [17] est maintenant un élément fondamental dans les algorithmes quantiques. L'estimation d'amplitude forme le cœur de la plupart des algorithmes quantiques connus liés à la recherche de collisions et aux propriétés de graphes. Une des applications naturelles de la recherche de Grover est d'accélérer la solution à des problèmes NP-complets tels que 3-SAT. Le faire n'est pas trivial, car le meilleur algorithme classique pour 3-SAT n'est pas tout à fait une recherche brute. Néanmoins, l'amplification d'amplitude permet une accélération quadratique quantique par rapport au meilleur algorithme classique de 3-SAT, comme le montre [133]. Des accélérations quadratiques pour d'autres problèmes de satisfaction de contraintes sont obtenues [134]. (Des accélérations légèrement superquadratiques par rapport à la recherche brute sont obtenues en utilisant des moyens au-delà de l'amplification d'amplitude dans [493,492].) Pour d'autres exemples d'application de la recherche de Grover et de l'amplification d'amplitude, voir [261, 262]. Un problème étroitement lié, mais plus difficile que la recherche de Grover, est la recherche spatiale, dans laquelle les requêtes de base de données sont limitées par une certaine structure de graphe. Sur des graphes suffisamment bien connectés, \(O(\sqrt{n})\) la complexité de requête quantique est toujours réalisable [274,275,303, 304, 305, 306, 330].
Algorithme : Sous-groupe Caché Abélien
Accélération : Superpolynomiale
Implémentation : Classiq, Cirq
Description : Soit G un groupe abélien généré de manière finie, et soit H un sous-groupe de G tel que G/H est fini. Soit f une fonction sur G telle que pour tout \( g_1,g_2 \in G \), \( f(g_1) = f(g_2) \) si et seulement si \( g_1 \) et \( g_2 \) sont dans le même coset de H. La tâche est de trouver H (c'est-à-dire trouver un ensemble de générateurs pour H) en faisant des requêtes à f. Cela est résoluble sur un ordinateur quantique en utilisant \( O(\log \vert G\vert) \) requêtes, tandis que classiquement \( \Omega(|G|) \) sont nécessaires. Cet algorithme a été formulé pour la première fois dans toute sa généralité par Boneh et Lipton dans [14]. Cependant, l'attribution correcte de cet algorithme est difficile car, comme décrit dans le chapitre 5 de [76], il englobe de nombreux algorithmes quantiques historiquement importants comme cas particuliers, y compris l'algorithme de Simon [108], qui a été l'inspiration pour l'algorithme de recherche de période de Shor, qui forme le cœur de ses algorithmes de factorisation et de logarithmes discrets. L'algorithme de sous-groupe caché abélien est également au cœur des algorithmes d'équation de Pell, d'idéal principal, de groupe unitaire et de groupe de classes. Dans certains cas, le problème de sous-groupe caché abélien peut être résolu en utilisant une seule requête plutôt qu'un ordre de \( \log(\vert G\vert) \), comme le montre [30]. Il est normalement supposé dans la recherche de période que la fonction \(f(x) \neq f(y) \) à moins que \( x-y = s \), où \( s \) est la période. Un algorithme quantique qui s'applique même lorsque cette restriction est assouplie est donné dans [388]. La recherche de période a été généralisée pour s'appliquer à des oracles qui ne fournissent que les quelques bits les plus significatifs concernant la fonction sous-jacente dans [389].
Algorithme : Sous-groupe Caché Non-Abélien
Accélération : Superpolynomiale
Description : Soit G un groupe généré de manière finie, et soit H un sous-groupe de G qui a un nombre fini de cosets à gauche. Soit f une fonction sur G telle que pour tout \( g_1, g_2 \), \( f(g_1) = f(g_2) \) si et seulement si \( g_1 \) et \( g_2 \) sont dans le même coset à gauche de H. La tâche est de trouver H (c'est-à-dire trouver un ensemble de générateurs pour H) en faisant des requêtes à f. Cela est résoluble sur un ordinateur quantique en \( O(\log(|G|) \) requêtes, tandis que classiquement \( \Omega(|G|) \) sont nécessaires [37,51]. Cependant, cela ne qualifie pas comme un algorithme quantique efficace car en général, il peut falloir un temps exponentiel pour traiter les états quantiques obtenus à partir de ces requêtes. Des algorithmes quantiques efficaces pour le problème de sous-groupe caché sont connus pour certains groupes non abéliens spécifiques [81,55,72,53,9,22,56,71,57,43,44,28,126,207,273]. Un sondage légèrement obsolète est donné dans [69]. D'un intérêt particulier sont le groupe symétrique et le groupe diédral. Une solution pour le groupe symétrique résoudrait l'isomorphisme de graphes. Une solution pour le groupe diédral résoudrait certains problèmes de réseau [78]. Malgré de nombreux efforts, aucune solution en temps polynomial pour ces groupes n'est connue, sauf dans des cas particuliers [312]. Cependant, Kuperberg [66] a trouvé un algorithme en temps \( 2^{O( \sqrt{\log N})}) \) pour trouver un sous-groupe caché du groupe diédral \( D_N \). Regev a ensuite amélioré cet algorithme de sorte qu'il utilise non seulement un temps subexponentiel mais aussi un espace polynomial [79]. Une autre amélioration dans l'échelle asymptotique du nombre requis de qubits est obtenue dans [218]. Des accélérations de requêtes quantiques (bien que pas nécessairement des algorithmes quantiques efficaces en termes de nombre de portes) pour des problèmes un peu plus généraux de test d'isomorphisme de fonctions sous des ensembles de permutations sont données dans [311]
Algorithme : Bernstein-Vazirani
Accélération : Polynomiale Directement, Superpolynomiale Récursivement
Implémentation : Classiq, Cirq
Description : Nous avons un oracle dont l'entrée est n bits et dont la sortie est un bit. Étant donné l'entrée \( x \in \{0,1\}^n \), la sortie est \( x \odot h \), où h est la chaîne "cachée" de n bits, et \( \odot \) désigne le produit intérieur bit à bit modulo 2. La tâche est de trouver h. Sur un ordinateur classique, cela nécessite n requêtes. Comme le montre Bernstein et Vazirani [11], cela peut être réalisé sur un ordinateur quantique en utilisant une seule requête. De plus, on peut construire des versions récursives de ce problème, appelées échantillonnage de Fourier récursif, telles que les ordinateurs quantiques nécessitent exponentiellement moins de requêtes que les ordinateurs classiques [11]. Voir [256, 257] pour des travaux connexes sur l'ubiquité des accélérations quantiques provenant de circuits quantiques génériques et [258, 270] pour des travaux connexes sur une accélération de requête quantique pour détecter des corrélations entre une fonction oracle et la transformée de Fourier d'une autre.
Algorithme : Deutsch-Jozsa
Accélération : Exponentielle par rapport à P, aucune par rapport à BPP
Implémentation : Classiq
Description : Nous avons un oracle dont l'entrée est n bits et dont la sortie est un bit. Nous avons la promesse que parmi les \( 2^n \) entrées possibles, soit toutes, aucune, ou la moitié d'entre elles donnent une sortie de 1. La tâche est de distinguer le cas équilibré (la moitié de toutes les entrées donnent une sortie de 1) du cas constant (toutes ou aucune des entrées donnent une sortie de 1). Il a été montré par Deutsch [32] que pour n=1, cela peut être résolu sur un ordinateur quantique en utilisant une requête, tandis que tout algorithme classique déterministe nécessite deux. C'était historiquement le premier algorithme quantique bien défini réalisant un gain par rapport au calcul classique. (Un exemple pédagogique connexe et plus récent est donné dans [259].) Un algorithme quantique à requête unique pour un n arbitraire a été développé par Deutsch et Jozsa dans [33]. Bien que probabilistiquement facile à résoudre avec O(1) requêtes, le problème de Deutsch-Jozsa a une complexité de requête déterministe exponentielle dans le pire des cas classiquement.
Algorithme : Évaluation de Formule
Accélération : Polynomiale
Description : Une expression booléenne est appelée formule si chaque variable est utilisée une seule fois. Une formule correspond à un circuit sans fanout, qui a donc la topologie d'un arbre. Grâce à la formalisation du programme de span de Reichardt, il est maintenant connu [158] que la complexité de requête quantique de toute formule de O(1) fanin sur N variables est \( \Theta(\sqrt{N}) \). Ce résultat découle d'une longue lignée de travaux [27,8,80,159,160], qui a commencé avec la découverte par Farhi et al. [38] que les arbres NAND sur \( 2^n \) variables peuvent être évalués sur des ordinateurs quantiques en temps \( O(2^{0.5n}) \) en utilisant une marche quantique continue, tandis que les ordinateurs classiques nécessitent \( \Omega(2^{0.753n}) \) requêtes. Dans de nombreux cas, les algorithmes d'évaluation de formules quantiques sont efficaces non seulement en complexité de requête mais aussi en complexité temporelle. La formalisation du programme de span donne également des bornes inférieures sur la complexité de requête quantique [149]. Bien que découvert à partir d'un point de vue différent, l'algorithme de Grover peut être considéré comme un cas particulier d'évaluation de formule dans lequel chaque porte est un OU. La complexité quantique d'évaluation de formules non booléennes a également été étudiée [29], mais n'est pas aussi bien comprise. Childs et al. ont généralisé le cas où les variables d'entrée peuvent être répétées (c'est-à-dire la première couche du circuit peut inclure un fanout) [101]. Ils ont obtenu un algorithme quantique utilisant \( O(\min \{N,\sqrt{S},N^{1/2} G^{1/4} \}) \) requêtes, où N est le nombre de variables d'entrée sans tenir compte des multiplicités, S est le nombre d'entrées comptant les multiplicités, et G est le nombre de portes dans la formule. Les références [164], [165], et [269] considèrent des cas particuliers du problème de l'arbre NAND dans lequel le nombre de portes NAND prenant des entrées inégales est limité. Certains de ces cas donnent une séparation superpolynomiale entre la complexité quantique et classique.
Algorithme : Déplacement Caché
Accélération : Superpolynomiale
Implémentation : Classiq, Cirq
Description : Nous avons accès à un oracle pour une certaine fonction f sur \( \mathbb{Z}_N \). Nous savons que f(x) = g(x+s) où g est une fonction connue et s est un décalage inconnu. Le problème de décalage caché est de trouver s. Par réduction du problème de Grover, il est clair qu'au moins \( \sqrt{N} \) requêtes sont nécessaires pour résoudre le décalage caché en général. Cependant, certains cas particuliers du problème de décalage caché sont résolubles sur des ordinateurs quantiques en utilisant O(1) requêtes. En particulier, van Dam et al. ont montré que cela peut être fait si f est un caractère multiplicatif d'un anneau ou d'un corps [89]. Le symbole de Legendre décalé précédemment découvert [88,86] est englobé comme un cas particulier de cela, car le symbole de Legendre \( \left(\frac{x}{p} \right) \) est un caractère multiplicatif de \( \mathbb{F}_p \). Aucun algorithme classique fonctionnant en temps O(polylog(N)) n'est connu pour ces problèmes. De plus, l'algorithme quantique pour le problème du symbole de Legendre décalé briserait un certain générateur pseudorandom cryptographique donné la capacité de faire des requêtes quantiques au générateur [89]. Une accélération quantique pour les problèmes de décalage caché de certains ensembles de différences est donnée dans [312], et cela englobe également le problème du symbole de Legendre comme un cas particulier. Roetteler a trouvé des accélérations quantiques exponentielles pour trouver des décalages cachés de certaines fonctions booléennes non linéaires [105,130]. En s'appuyant sur ce travail, Gavinsky, Roetteler et Roland ont montré [142] que le problème de décalage caché sur des fonctions booléennes aléatoires \( f:\mathbb{Z}_2^n \to \mathbb{Z}_2 \) a une complexité quantique moyenne de O(n), tandis que la complexité de requête classique est \( \Omega(2^{n/2}) \). Les résultats dans [143], bien qu'ils soient formulés en termes de problème de sous-groupe caché pour le groupe diédral, impliquent que la complexité de requête quantique du problème de décalage caché pour une fonction injective sur \( \mathbb{Z}_N \) est O(log n), tandis que la complexité de requête classique est \( \Theta(\sqrt{N}) \). Cependant, la meilleure complexité de circuit quantique pour le décalage caché injectif sur \( \mathbb{Z}_N \) est \( O(2^{C \sqrt{\log N}}) \), atteinte par l'algorithme de tamis de Kuperberg [66]. Un résultat récent, s'appuyant sur [408, 43], atteint des accélérations quantiques exponentielles pour certaines généralisations du problème de décalage caché, y compris le problème de décalage multiple caché, dans lequel on a accès à \(f_s(x) = f(x-hs) \) sur une certaine plage autorisée de s et l'on souhaite inférer h [407].
Algorithme : Interpolation Polynomiale
Accélération : Varie
Description : Soit \( p(x) = a_d x^d + \ldots + a_1 x + a_0 \) un polynôme sur le corps fini \( \mathrm{GF}(q) \). On a accès à un oracle qui, donné \( x \in \mathrm{GF}(q) \), retourne \( p(x) \). Le problème de reconstruction de polynôme est, en faisant des requêtes à l'oracle, de déterminer les coefficients \( a_d,\ldots,a_0 \). Classiquement, \( d + 1 \) requêtes sont nécessaires et suffisantes. (Dans certaines sources, on utilise le terme reconstruction au lieu d'interpolation pour ce problème.) Quantiquement, \( d/2 + 1/2 \) requêtes sont nécessaires et \( d/2 + 1 \) requêtes sont suffisantes [360,361]. Pour des polynômes multivariés de degré d dans n variables, le problème d'interpolation a une complexité de requête classique \( \binom{n+d}{d} \). Comme le montre [387], la complexité de requête quantique est \( O \left( \frac{1}{n+1} \binom{n+d}{d} \right) \) sur \( \mathbb{R} \) et \( \mathbb{C} \) et elle est \( O \left( \frac{d}{n+d} \binom{n+d}{d} \right) \) sur \( \mathbb{F}_q \) pour des \( q \) suffisamment grands. Des algorithmes quantiques ont également été découverts pour le cas où l'oracle retourne \( \chi(f(x)) \) où \( \chi \) est un caractère quadratique de \( \mathrm{GF}(q) \) [390], et le cas où l'oracle retourne \( f(x)^e \) [392]. Ceux-ci généralisent l'algorithme de décalage caché de [89] et atteignent une accélération exponentielle par rapport au calcul classique. Un algorithme quantique pour reconstruire des fonctions rationnelles sur des corps finis donné un accès oracle bruyant et incomplet aux valeurs de fonction est donné dans [391].
Algorithme : Correspondance de Modèle
Accélération : Superpolynomiale
Description : Étant donné des chaînes T de longueur n et P de longueur m < n, toutes deux provenant d'un alphabet fini, le problème de correspondance de modèle consiste à trouver une occurrence de P comme sous-chaîne de T ou à signaler que P n'est pas une sous-chaîne de T. Plus généralement, T et P pourraient être des tableaux d-dimensionnels plutôt que des tableaux unidimensionnels (chains). Ensuite, le problème de correspondance de modèle consiste à retourner la position de P comme un bloc de \(m \times m \times \ldots \times m\) dans le tableau \(n \times n \times \ldots \times n\) T ou à signaler qu'aucune telle position n'existe. La complexité de requête \( \Omega(\sqrt{N}) \) pour la recherche non structurée [216] implique que la complexité de requête quantique dans le pire des cas de ce problème est \( \Omega ( \sqrt{n} + \sqrt{m} ) \). Un algorithme quantique atteignant cela, jusqu'à des facteurs logarithmiques, a été obtenu dans [217]. Cet algorithme quantique fonctionne grâce à l'utilisation de l'algorithme de recherche de Grover associé à une méthode classique appelée échantillonnage déterministe. Plus récemment, Montanaro a montré que des accélérations quantiques superpolynomiales peuvent être obtenues sur des instances de cas moyen de correspondance de modèle, à condition que m soit supérieur à logarithmique en n. Plus précisément, l'algorithme quantique donné dans [215] résout la correspondance de modèle dans le cas moyen en \( \widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2} \sqrt{\log m})})\) temps. Cet algorithme quantique est construit en généralisant l'algorithme quantique de tamis de Kuperberg [66] pour les problèmes de sous-groupe caché diédral et de décalage caché de sorte qu'il puisse fonctionner en d dimensions et accommoder de petites quantités de bruit, puis en réduisant classiquement le problème de correspondance de modèle à cette version bruyante d-dimensionnelle du décalage caché. Un algorithme quantique pour la correspondance de chaînes avec une complexité \(\widetilde{O} (\sqrt{n}) \) est donné dans [435] dans un modèle d'entrée différent, où les chaînes sont écrites dans leur intégralité en utilisant \(n + m\) qubits plutôt que par des requêtes quantiques à un oracle fournissant des bits individuels.
Algorithme : Recherche Ordonnée
Accélération : Facteur constant
Description : Nous avons accès à un oracle pour une liste de N nombres dans l'ordre de la plus petite à la plus grande. Étant donné un nombre x, la tâche est de découvrir où dans la liste il s'insérerait. Classiquement, le meilleur algorithme possible est la recherche binaire qui prend \( \log_2 N \) requêtes. Farhi et al. ont montré qu'un ordinateur quantique peut atteindre cela en utilisant 0.53 \( \log_2 N \) requêtes [39]. Actuellement, le meilleur algorithme quantique déterministe connu pour ce problème utilise 0.433 \( \log_2 N \) requêtes [103]. Une borne inférieure de \( \frac{\ln 2}{\pi} \log_2 N \) a été prouvée pour ce problème [219, 24]. Dans [10], un algorithme quantique randomisé est donné dont la complexité de requête attendue est inférieure à \( \frac{1}{3} \log_2 N \).
Algorithme : Propriétés des graphes dans le modèle de matrice d'adjacence
Accélération : Polynomiale
Description : Soit G un graphe de n sommets. Nous avons accès à un oracle, qui, donné une paire d'entiers dans {1,2,...,n}, nous indique si les sommets correspondants sont connectés par une arête. S'appuyant sur des travaux précédents [35,52,36], Dürr et al. [34] montrent que la complexité de requête quantique pour trouver un arbre couvrant minimal de graphes pondérés, et décider de la connectivité pour les graphes dirigés et non dirigés a \( \Theta(n^{3/2}) \) de complexité de requête quantique, et que trouver les chemins de poids minimum a \( O(n^{3/2}\log^2 n) \) de complexité de requête quantique. Décider si un graphe est bipartite, détecter des cycles, et décider si un sommet donné peut être atteint depuis un autre (connectivité st) peut tous être réalisé en utilisant un nombre de requêtes et de portes quantiques qui évoluent comme \( \widetilde{O}(n^{3/2}) \), et seulement logarithmiquement de qubits, comme montré dans [317], s'appuyant sur [13, 272, 318]. Un algorithme quantique basé sur les programmes de span pour détecter des arbres d'une taille donnée comme mineurs en \( \widetilde{O}(n) \) temps est donné dans [240]. Une propriété de graphe est dite éparse s'il existe une constante c telle que chaque graphe avec cette propriété a un ratio d'arêtes par rapport aux sommets au plus c. Childs et Kothari ont montré que toutes les propriétés de graphes éparses ont une complexité de requête \( \Theta(n^{2/3}) \) si elles ne peuvent pas être caractérisées par une liste de sous-graphes interdits et \( o(n^{2/3}) \) (little-o) si elles le peuvent [140]. Le premier algorithme est basé sur la recherche de Grover, le second sur le formalisme de marche quantique de [141]. Selon le théorème de Mader, les propriétés de graphes éparses incluent toutes les propriétés fermées par mineurs non triviaux. Celles-ci incluent la planéité, le fait d'être une forêt, et de ne pas contenir un chemin de longueur donnée. Selon la conjecture largement acceptée d'Aanderaa-Karp-Rosenberg, tous les problèmes ci-dessus ont \( \Omega(n^2) \) de complexité de requête classique. Un autre problème computationnel intéressant est de trouver un sous-graphe H dans un graphe donné G. Le cas le plus simple est de trouver le triangle, c'est-à-dire le clique de taille trois. Le meilleur algorithme quantique connu pour cela trouve un triangle en \( O(n^{5/4}) \) requêtes quantiques [319], améliorant [276, 175, 171, 70, 152, 21]. Des bornes supérieures de complexité de requête quantique plus fortes sont connues lorsque les graphes sont suffisamment épars [319, 320]. Classiquement, la recherche de triangles nécessite \( \Omega(n^2) \) requêtes [21]. Plus généralement, un ordinateur quantique peut trouver un sous-graphe arbitraire de k sommets en utilisant \( O(n^{2-2/k-t}) \) requêtes où \( t=(2k-d-3)/(k(d+1)(m+2)) \) et d et m sont tels que H a un sommet de degré d et m+d arêtes [153]. Cela améliore l'algorithme précédent de [70]. Dans certains cas, cette complexité de requête est battue par l'algorithme quantique de [140], qui trouve H en utilisant \( \widetilde{O}\left( n^{\frac{3}{2}-\frac{1}{\mathrm{vc}(H)+1}} \right) \) requêtes, à condition que G soit épars, où vc(H) est la taille de la couverture minimale des sommets de H. Un algorithme quantique pour trouver des sous-hypergraphes de taille constante sur des hypergraphes 3-uniformes en \( O(n^{1.883}) \) requêtes est donné dans [241].
Algorithme : Propriétés des graphes dans le modèle de liste d'adjacence
Accélération : Polynomiale
Description : Soit G un graphe de N sommets, M arêtes, et degré d. Nous avons accès à un oracle qui, lorsqu'on lui demande le label d'un sommet et \( j \in \{1,2,\ldots,d\} \), renvoie le j-ième voisin du sommet ou null si le sommet a un degré inférieur à d. Supposons que nous avons la promesse que G est soit bipartite, soit éloigné de bipartite dans le sens où une fraction constante des arêtes devrait être supprimée pour atteindre la bipartite. Alors, comme montré dans [144], la complexité quantique de décider de la bipartite est \( \widetilde{O}(N^{1/3}) \). Également dans [144], il est montré que distinguer les graphes expanseurs des graphes qui sont loin d'être expanseurs a une complexité quantique \( \widetilde{O}(N^{1/3}) \) et \( \widetilde{\Omega}(N^{1/4}) \), tandis que la complexité classique est \( \widetilde{\Theta}(\sqrt{N}) \). L'outil algorithmique quantique clé est l'algorithme d'Ambainis pour la distinctivité des éléments. Dans [34], il est montré que trouver un arbre couvrant minimal a une complexité de requête quantique \( \Theta(\sqrt{NM}) \), décider de la connectivité des graphes a une complexité de requête quantique \( \Theta(N) \) dans le cas non dirigé, et \( \widetilde{\Theta}(\sqrt{NM}) \) dans le cas dirigé, et calculer le chemin de poids minimum à partir d'une source donnée vers tous les autres sommets sur un graphe pondéré a une complexité de requête quantique \( \widetilde{\Theta}(\sqrt{NM}) \). Dans [317], des algorithmes quantiques sont donnés pour la connectivité st, décider de la bipartite, et décider si un graphe est une forêt, qui s'exécutent en \( \widetilde{O}(N \sqrt{d}) \) temps et utilisent seulement un nombre logarithmique de qubits.
Algorithme : Arbre soudé
Accélération : Superpolynomiale
Implémentation : Classiq
Description : Certains problèmes computationnels peuvent être formulés en termes de la complexité de requête pour trouver son chemin à travers un labyrinthe. C'est-à-dire qu'il y a un graphe G auquel on a accès par oracle. Lorsqu'on lui demande le label d'un nœud donné, l'oracle renvoie une liste des labels de tous les nœuds adjacents. La tâche consiste, en partant d'un nœud source (c'est-à-dire son label), à trouver le label d'un certain nœud de destination marqué. Comme montré par Childs et al. [26], les ordinateurs quantiques peuvent surpasser exponentiellement les ordinateurs classiques dans cette tâche pour au moins certains graphes. Plus précisément, considérons le graphe obtenu en joignant deux arbres binaires de profondeur n par un "soudage" aléatoire tel que tous les nœuds sauf les deux racines ont un degré de trois. En partant d'une racine, un ordinateur quantique peut trouver l'autre racine en utilisant poly(n) requêtes, tandis que cela est prouvablement impossible avec des requêtes classiques.
Algorithme : Recherche de collisions et distinctivité des éléments
Accélération : Polynomiale
Description : Supposons que nous avons accès à un oracle pour une fonction deux à un f sur un domaine de taille N. Le problème de collision est de trouver une paire \( x,y \in \{1,2,\ldots,N\} \) telle que f(x) = f(y). La complexité de requête classique aléatoire de ce problème est \( \Theta(\sqrt{N}) \), tandis que, comme montré par Brassard et al., un ordinateur quantique peut atteindre cela en utilisant \(O(N^{1/3}) \) requêtes [18]. (Voir aussi [315].) En supprimant la promesse que f est deux à un, on obtient un problème appelé distinctivité des éléments, qui a une complexité de requête classique \( \Theta(N) \). Améliorant [21], Ambainis propose un algorithme quantique avec une complexité de requête de \( O(N^{2/3}) \) pour la distinctivité des éléments, ce qui est optimal [7, 374]. Le problème de décider si des collisions k-fois existent est appelé k-distinctivité. Améliorant [7,154], la meilleure complexité de requête quantique pour k-distinctivité est \( O(n^{3/4 - 1/(4(2^k-1))}) \) [172, 173]. La série de travaux [7, 363], culminant dans [464], montre que c'est aussi la complexité temporelle quantique pour tous k, jusqu'à des facteurs logarithmiques. Étant donné deux fonctions f et g, sur des domaines de taille N et M, respectivement, une griffe est une paire x,y telle que f(x) = g(y). Dans le cas où N=M, l'algorithme de [7] résout la recherche de griffes en \( O(N^{2/3}) \) requêtes, améliorant l'ancien algorithme quantique \( O(N^{3/4} \log N) \) de [21]. D'autres travaux donnent une complexité de requête améliorée pour divers régimes de paramètres dans lesquels \(N \neq M\) [364, 365]. Plus généralement, un problème connexe à la distinctivité des éléments est, étant donné un accès oracle à une séquence, de estimer le \(k^{\mathrm{th}}\) moment de fréquence \(F_k = \sum_j n_j^k \), où \(n_j\) est le nombre de fois que j apparaît dans la séquence. Un gain de vitesse quadratique approximatif pour ce problème est obtenu dans [277]. Voir aussi collision de graphes.
Algorithme : Collision de graphes
Accélération : Polynomiale
Description : Nous avons un graphe non dirigé de n sommets et un accès oracle à un étiquetage des sommets par 1 et 0. Le problème de collision de graphes est, en interrogeant cet oracle, de décider s'il existe une paire de sommets, connectés par une arête, tous deux étiquetés 1. On peut intégrer le problème de recherche non structurée de Grover comme un cas de collision de graphes en choisissant le graphe étoile, étiquetant le centre par 1, et étiquetant les sommets restants par les entrées de la base de données. Ainsi, ce problème a une complexité de requête quantique \( \Omega(\sqrt{n}) \) et une complexité de requête classique \( \Theta (n) \). Dans [70], Magniez, Nayak, et Szegedy ont donné un algorithme quantique de \( O(N^{2/3}) \) pour la collision de graphes sur des graphes généraux. Cela reste la meilleure borne supérieure sur la complexité de requête quantique pour ce problème sur des graphes généraux. Cependant, des bornes supérieures plus fortes ont été obtenues pour plusieurs classes spéciales de graphes. Plus précisément, la complexité de requête quantique sur un graphe G est \( \widetilde{O}(\sqrt{n} + \sqrt{l}) \) où l est le nombre de non-arêtes dans G [161], \(O(\sqrt{n} \alpha^{1/6}) \) où \(\alpha\) est la taille de la plus grande ensemble indépendant de G [172], \(O(\sqrt{n} + \sqrt{\alpha^*})\) où \( \alpha^* \) est le degré total maximum de tout ensemble indépendant de G [200], et \(O(\sqrt{n} t^{1/6}) \) où t est la largeur d'arbre de G [201]. De plus, la complexité de requête quantique est \( \widetilde{O}(\sqrt{n}) \) avec une forte probabilité pour des graphes aléatoires dans lesquels la présence ou l'absence d'une arête entre chaque paire de sommets est choisie indépendamment avec une probabilité fixe, (c'est-à-dire graphes d'Erdős-Rényi) [200]. Voir [201] pour un résumé de ces résultats ainsi que de nouvelles bornes supérieures pour deux classes supplémentaires de graphes qui sont trop compliquées à décrire ici.
Algorithme : Commutativité des matrices
Accélération : Polynomiale
Description : Nous avons accès oracle à k matrices, chacune étant \( n \times n \). Étant donné des entiers \( i,j \in \{1,2,\ldots,n\} \), et \( x \in \{1,2,\ldots,k\} \), l'oracle renvoie l'élément de matrice ij de la \( x^{\mathrm{ème}} \) matrice. La tâche est de décider si toutes ces k matrices commutent. Comme montré par Itakura [54], cela peut être réalisé sur un ordinateur quantique en utilisant \( O(k^{4/5}n^{9/5}) \) requêtes, tandis que classiquement cela nécessite \( \Omega( k n^2 ) \) requêtes.
Algorithme : Commutativité de groupe
Accélération : Polynomiale
Description : Nous avons une liste de k générateurs pour un groupe G et accès à une boîte noire implémentant la multiplication de groupe. En interrogeant cette boîte noire, nous souhaitons déterminer si le groupe est commutatif. Le meilleur algorithme classique connu est dû à Pak et nécessite O(k) requêtes. Magniez et Nayak ont montré que la complexité de requête quantique de cette tâche est \( \widetilde{\Theta}(k^{2/3}) \) [139].
Algorithme : Structures non linéaires cachées
Accélération : Superpolynomiale
Description : Tout groupe abélien G peut être visualisé comme un réseau. Un sous-groupe H de G est un sous-réseau, et les classes de cosets de H sont tous les décalages de ce sous-réseau. Le problème du sous-groupe caché abélien est normalement résolu en obtenant une superposition sur un coset aléatoire du sous-groupe caché, puis en prenant la transformée de Fourier afin d'échantillonner à partir du réseau dual. Plutôt que de généraliser aux groupes non abéliens (voir sous-groupe caché non abélien), on peut plutôt généraliser au problème d'identification de sous-ensembles cachés autres que des réseaux. Comme montré par Childs et al. [23], ce problème est efficacement résoluble sur des ordinateurs quantiques pour certains sous-ensembles définis par des polynômes, tels que des sphères. Decker et al. ont montré comment résoudre efficacement certains problèmes connexes dans [31, 212].
Algorithme : Centre de fonction radiale
Accélération : Polynomiale
Description : Nous avons accès à un oracle qui évalue une fonction f de \( \mathbb{R}^d \) vers un ensemble arbitraire S, où f est spheriquement symétrique. Nous souhaitons localiser le centre de symétrie, jusqu'à une certaine précision. (Pour simplifier, considérons que la précision est fixe.) Dans [110], Liu donne un algorithme quantique, basé sur une transformée de courbe, qui résout ce problème en utilisant un nombre constant de requêtes quantiques indépendantes de d. Cela constitue un gain de vitesse polynomial par rapport à la borne inférieure classique, qui est \( \Omega(d) \) requêtes. L'algorithme fonctionne lorsque la fonction f fluctue à des échelles suffisamment petites, e.g., lorsque les ensembles de niveaux de f sont suffisamment fins en coquilles sphériques. L'algorithme quantique est montré pour fonctionner dans un modèle continu idéalisé, et des arguments non rigoureux suggèrent que les effets de discrétisation devraient être faibles.
Algorithme : Ordre et appartenance de groupe
Accélération : Superpolynomiale
Description : Supposons qu'un groupe fini G soit donné oraculairement de la manière suivante. À chaque élément de G, on attribue un label correspondant. Étant donné une paire ordonnée de labels d'éléments de groupe, l'oracle renvoie le label de leur produit. Il existe plusieurs problèmes classiquement difficiles concernant de tels groupes. L'un consiste à trouver l'ordre du groupe, étant donné les labels d'un ensemble de générateurs. Une autre tâche consiste, étant donné une chaîne de bits, à décider si elle correspond à un élément de groupe. La version constructive de ce problème d'appartenance nécessite, dans le cas positif, une décomposition de l'élément donné comme produit de générateurs de groupe. Classiquement, ces problèmes ne peuvent pas être résolus en utilisant des requêtes polylog(|G|) même si G est abélien. Pour les groupes abéliens, les ordinateurs quantiques peuvent résoudre ces problèmes en utilisant des requêtes polylog(|G|) par réduction au problème de sous-groupe caché abélien, comme montré par Mosca [74]. De plus, comme montré par Watrous [91], les ordinateurs quantiques peuvent résoudre ces problèmes en utilisant des requêtes polylog(|G|) pour tout groupe résoluble. Pour les groupes donnés sous forme de matrices sur un corps fini plutôt que oraculairement, les problèmes de recherche d'ordre et d'appartenance constructive peuvent être résolus en temps polynomial en utilisant les algorithmes quantiques pour le logarithme discret et la factorisation [124]. Voir aussi isomorphisme de groupe.
Algorithme : Isomorphisme de groupe
Accélération : Superpolynomiale
Description : Soit G un groupe fini. À chaque élément de G est attribué un label arbitraire (chaîne de bits). Étant donné une paire ordonnée de labels d'éléments de groupe, l'oracle de groupe renvoie le label de leur produit. Étant donné l'accès aux oracles de groupe pour deux groupes G et G', et une liste de générateurs pour chaque groupe, nous devons décider si G et G' sont isomorphes. Pour les groupes abéliens, nous pouvons résoudre ce problème en utilisant des requêtes poly(log |G|, log |G'|) à l'oracle en appliquant l'algorithme quantique de [127], qui décompose tout groupe abélien en un produit direct canonique de groupes cycliques. L'algorithme quantique de [128] résout le problème de l'isomorphisme de groupe en utilisant des requêtes poly(log |G|, log |G'|) pour une certaine classe de groupes non abéliens. Plus précisément, un groupe G est dans cette classe si G a un sous-groupe abélien normal A et un élément y d'ordre premier avec |A| tel que G = A, y. Zatloukal a récemment donné un gain quantique exponentiel pour certaines instances d'un problème étroitement lié à l'isomorphisme de groupe, à savoir le test d'équivalence des extensions de groupe [202].
Algorithme : Différence statistique
Accélération : Polynomiale
Description : Supposons que nous avons deux boîtes noires A et B dont le domaine est les entiers de 1 à T et dont l'image est les entiers de 1 à N. En choisissant uniformément au hasard parmi les entrées autorisées, nous obtenons une distribution de probabilité sur les sorties possibles. Nous souhaitons approximer à une précision constante la distance L1 entre les distributions de probabilité déterminées par A et B. Classiquement, le nombre de requêtes nécessaires évolue essentiellement de manière linéaire avec N. Comme montré dans [117], un ordinateur quantique peut atteindre cela en utilisant \( O(\sqrt{N}) \) requêtes. L'uniformité approximative et l'orthogonalité des distributions de probabilité peuvent également être décidées sur un ordinateur quantique en utilisant \( O(N^{1/3}) \) requêtes. L'outil principal est l'algorithme de comptage quantique de [16]. Un algorithme quantique amélioré pour cette tâche est obtenu dans [265].
Algorithme : Anneaux finis et idéaux
Accélération : Superpolynomiale
Description : Supposons que nous avons des boîtes noires implémentant les opérations d'addition et de multiplication sur un anneau fini R, pas nécessairement commutatif, avec un ensemble de générateurs pour R. En ce qui concerne l'addition, R forme un groupe abélien fini (R,+). Comme montré dans [119], sur un ordinateur quantique, on peut trouver en temps poly(log |R|) un ensemble de générateurs additifs \( \{h_1,\ldots,h_m\} \subset R \) tel que \( (R,+) \simeq \langle h_1 \rangle \times \ldots \times \langle h_M \rangle\) et m est polylogarithmique en |R|. Cela permet un calcul efficace d'un tenseur de multiplication pour R. Comme montré dans [118], on peut également trouver un ensemble générateur additif pour tout idéal dans R. Cela permet de trouver l'intersection de deux idéaux, de trouver leur quotient, de prouver si un élément d'anneau donné appartient à un idéal donné, de prouver si un élément donné est une unité et, le cas échéant, de trouver son inverse, de trouver les identités additive et multiplicative, de calculer l'ordre d'un idéal, de résoudre des équations linéaires sur des anneaux, de décider si un idéal est maximal, de trouver des annihilateurs, et de tester l'injectivité et la surjectivité des homomorphismes d'anneaux. Comme montré dans [120], on peut également utiliser un ordinateur quantique pour décider efficacement si un polynôme donné est identiquement nul sur un anneau fini en boîte noire donné. Les algorithmes classiques connus pour ces problèmes évoluent comme poly(|R|).
Algorithme : Pièces contrefaites
Accélération : Polynomiale
Description : Supposons que nous avons N pièces, dont k sont contrefaites. Les vraies pièces ont toutes le même poids, et les pièces contrefaites ont toutes un autre poids égal. Nous avons une balance à plateau et pouvons comparer le poids de n'importe quelle paire de sous-ensembles de pièces. Classiquement, nous avons besoin de \( \Omega(k \log(N/k)) \) pesées pour identifier toutes les pièces contrefaites. Nous pouvons introduire un oracle tel que, donné une paire de sous-ensembles de pièces de cardinalité égale, il renvoie un bit indiquant si c'est équilibré ou déséquilibré. S'appuyant sur des travaux précédents de Terhal et Smolin [137], Iwama et al. ont montré [136] que sur un ordinateur quantique, on peut identifier toutes les pièces contrefaites en utilisant \( O(k^{1/4}) \) requêtes. Les techniques fondamentales derrière le gain quantique sont l'amplification d'amplitude et l'algorithme de Bernstein-Vazirani.
Algorithme : Rang de matrice
Accélération : Polynomiale
Description : Supposons que nous ayons accès par oracle aux entrées (entières) d'une matrice \( n \times m \) A. Nous souhaitons déterminer le rang de la matrice. Classiquement, cela nécessite un ordre de \( nm \) requêtes. En s'appuyant sur [149], Belovs [150] propose un algorithme quantique qui peut utiliser moins de requêtes, étant donné la promesse que le rang de la matrice est d'au moins r. Plus précisément, l'algorithme de Belovs utilise \( O(\sqrt{r(n-r+1)}LT) \) requêtes, où L est la racine carrée de la moyenne des inverses des r plus grandes valeurs singulières de A et T est un facteur qui dépend de la parcimonie de la matrice. Pour une matrice générale A, \( T = O(\sqrt{nm}) \). Si A a au plus k entrées non nulles dans n'importe quelle ligne ou colonne, alors \( T = O(k \log(n+m)) \). (Pour atteindre la complexité de requête correspondante dans le cas k-parcimonieux, l'oracle doit prendre un index de colonne comme entrée et fournir une liste des éléments non nuls de la matrice de cette colonne en sortie.) Comme un cas spécial important, on peut utiliser ces algorithmes quantiques pour le problème de déterminer si une matrice carrée est singulière, ce qui est parfois appelé le problème du déterminant. Pour une matrice générale A, la complexité de requête quantique du problème du déterminant n'est pas inférieure à la complexité de requête classique [151]. Cependant, [151] ne rejette pas une accélération quantique donnée une promesse sur A, telle que la parcimonie ou l'absence de petites valeurs singulières.
Algorithme : Multiplication de matrices sur des semi-anneaux
Accélération : Polynomiale
Description : Un semi-anneau est un ensemble doté d'opérations d'addition et de multiplication qui obéissent à tous les axiomes d'un anneau, sauf l'existence d'inverses additifs. La multiplication de matrices sur divers semi-anneaux a de nombreuses applications aux problèmes de graphes. La multiplication de matrices sur des semi-anneaux peut être accélérée par des améliorations directes de Grover sur la multiplication scolaire, donnant un algorithme quantique qui multiplie une paire de matrices \(n \times n\) en \( \widetilde{O}(n^{5/2}) \) temps. Pour certains semi-anneaux, cet algorithme surpasse les algorithmes classiques les plus rapides connus et pour certains semi-anneaux, il ne le fait pas [206]. Un cas d'intérêt particulier est le semi-anneau booléen, dans lequel l'OR sert d'addition et l'ET sert de multiplication. Aucun algorithme quantique n'est connu pour la multiplication de matrices sur un semi-anneau booléen dans le cas général qui surpasse le meilleur algorithme classique, qui a une complexité de \( n^{2.373} \). Cependant, pour des entrées ou des sorties parcimonieuses, des accélérations quantiques sont connues. Plus précisément, soit A,B des matrices booléennes de taille n par n. Soit C=AB, et soit l le nombre d'entrées de C qui sont égales à 1 (c'est-à-dire VRAI). En améliorant [19, 155, 157], la meilleure borne supérieure connue sur la complexité de requête quantique est \(\widetilde{O}(n \sqrt{l}) \), comme montré dans [161]. Si les matrices d'entrée sont parcimonieuses, une accélération quantique par rapport à l'algorithme classique le plus rapide connu a également été trouvée dans un certain régime [206]. Pour une comparaison détaillée avec les algorithmes classiques, voir [155, 206]. Des algorithmes quantiques ont été trouvés pour effectuer la multiplication de matrices sur le semi-anneau (max,min) en \(\widetilde{O}(n^{2.473})\) temps et sur le semi-anneau de dominance de distance en \(\widetilde{O}(n^{2.458})\) temps [206]. L'algorithme classique le plus rapide connu pour ces deux problèmes a une complexité de \(\widetilde{O}(n^{2.687})\).
Algorithme : Recherche de sous-ensembles
Accélération : Polynomiale
Description : Nous avons accès par oracle à une fonction \( f:D \to R \) où D et R sont des ensembles finis. Une propriété \( P \subset (D \times R)^k \) est spécifiée, par exemple sous forme de liste explicite. Notre tâche est de trouver un sous-ensemble de taille-k de D satisfaisant P, c'est-à-dire \( ((x_1,f(x_1)),\ldots,(x_k,f(x_k))) \in P \), ou de rejeter si aucun n'existe. Comme d'habitude, nous souhaitons le faire avec le minimum de requêtes à f. En généralisant le résultat de [7], il a été montré dans [162] que cela peut être réalisé en utilisant \(O(|D|^{k/(k+1)}) \) requêtes quantiques. Comme un cas spécial intéressant, cet algorithme résout le problème de la somme de sous-ensembles k consistant à trouver k nombres d'une liste avec une somme désirée. Une borne inférieure correspondante pour la complexité de requête quantique est prouvée dans [163].
Algorithme : Recherche avec des jokers
Accélération : Polynomiale
Description : Le problème de recherche avec des jokers consiste à identifier une chaîne de bits cachée n x en faisant des requêtes à un oracle f. Étant donné \( S \subseteq \{1,2,\ldots,n\} \) et \( y \in \{0,1\}^{|S|} \), f renvoie un si la sous-chaîne de x spécifiée par S est égale à y, et renvoie zéro sinon. Classiquement, ce problème a une complexité de requête \(\Theta(n)\). Comme montré dans [167], la complexité de requête quantique de ce problème est \( \Theta(\sqrt{n}) \). Fait intéressant, cette accélération quadratique est obtenue non pas par amplification d'amplitude ou marches quantiques, mais plutôt par l'utilisation de la soi-disant Mesure Pretty Good. L'article [167] donne également une accélération quantique pour le problème connexe de test de groupe combinatoire. Ce résultat et des algorithmes quantiques plus rapides pour le test de groupe sont discutés dans l'entrée sur le test de Junta et le test de groupe.
Algorithme : Flux de réseau
Accélération : Polynomiale
Description : Un réseau est un graphe orienté dont les arêtes sont étiquetées par des nombres indiquant leurs capacités de transport, et deux de ses sommets sont désignés comme la source et le puits. Un flux sur un réseau est une attribution de flux aux arêtes telle qu'aucun flux ne dépasse la capacité de cette arête, et pour chaque sommet autre que la source et le puits, le total des entrées est égal au total des sorties. Le problème de flux de réseau consiste, étant donné un réseau, à trouver le flux qui maximise le flux total allant de la source au puits. Pour un réseau avec n sommets, m arêtes, et des capacités entières de magnitude maximale U, [168] propose un algorithme quantique pour trouver le flux maximal en temps \( O(\min \{n^{7/6} \sqrt{m} \ U^{1/3}, \sqrt{nU}m\} \times \log n) \). Le problème de flux de réseau est étroitement lié au problème de trouver un appariement maximal d'un graphe, c'est-à-dire un sous-ensemble maximal d'arêtes qui connecte chaque sommet à au plus un autre sommet. L'article [168] propose des algorithmes pour trouver des appariements maximaux qui s'exécutent en temps \( O(n \sqrt{m+n} \log n) \) si le graphe est bipartite, et \( O(n^2 ( \sqrt{m/n} + \log n) \log n) \) dans le cas général. Le cœur de ces algorithmes est la recherche de Grover. Les bornes supérieures connues sur la complexité classique des problèmes de flux de réseau et d'appariement sont compliquées à énoncer car différents algorithmes classiques sont préférables dans différents régimes de paramètres. Cependant, dans certains régimes, les algorithmes quantiques ci-dessus battent tous les algorithmes classiques connus. (Voir [168] pour plus de détails.)
Algorithme : Résistance Électrique
Accélération : Exponentielle
Description : Nous avons accès par oracle à un graphe pondéré de n sommets et de degré maximum d dont les poids des arêtes doivent être interprétés comme des résistances électriques. Notre tâche est de calculer la résistance entre une paire de sommets choisie. Wang a donné deux algorithmes quantiques dans [210] pour cette tâche qui s'exécutent en temps \(\mathrm{poly}( \log n, d, 1/\phi, 1/\epsilon) \), où \( \phi \) est l'expansion du graphe, et la réponse doit être donnée dans un facteur de \( 1+\epsilon \). Les algorithmes classiques connus pour ce problème sont polynomiaux en n plutôt que \( \log n \). L'un des algorithmes de Wang est basé sur une utilisation novatrice des marches quantiques. L'autre est basé sur l'algorithme quantique de [104] pour résoudre des systèmes d'équations linéaires. Les premières bornes supérieures de complexité de requête quantique pour le problème de résistance électrique dans le modèle de requête d'adjacence sont données dans [280] en utilisant des programmes de portée approximatifs.
Algorithme : Test de Junta et Test de Groupe
Accélération : Polynomiale
Description : Une fonction \(f:\{0,1\}^n \to \{0,1\}\) est une k-junta si elle dépend d'au plus k de ses bits d'entrée. Le problème de test de k-junta consiste à décider si une fonction donnée est une k-junta ou est \( \epsilon \)-loin de toute k-junta. Bien que ce ne soit pas évident, ce problème est étroitement lié au test de groupe. Un problème de test de groupe est défini par une fonction \(f:\{1,2,\ldots,n\} \to \{0,1\}\). On a accès par oracle à F, qui prend en entrée des sous-ensembles de \( \{1,2,\ldots,n\} \). F(S) = 1 s'il existe \(x \in S \) tel que f(x) = 1 et F(S) = 0 sinon. Dans [266], un algorithme quantique est donné pour résoudre le problème de k-junta en utilisant \( \widetilde{O}(\sqrt{k/\epsilon}) \) requêtes et \( \widetilde{O}(n \sqrt{k/\epsilon}) \) temps. C'est une accélération quadratique par rapport à la complexité classique, et cela améliore un algorithme quantique précédent pour le test de k-junta donné dans [267]. Une accélération polynomiale pour une version gappée (c'est-à-dire approximation) du test de groupe est également donnée dans [266], améliorant les résultats antérieurs de [167,268].
Algorithmes d'Approximation et de Simulation
Algorithme : Simulation QuantiqueAccélération : Superpolynomiale
Mise en œuvre : Classiq
Description : La complexité exponentielle de la simulation classique des systèmes quantiques a conduit Feynman à proposer pour la première fois que les ordinateurs quantiques pourraient surpasser les ordinateurs classiques dans certaines tâches [40]. On pense maintenant que pour tout Hamiltonien physiquement réaliste H sur n degrés de liberté, l'opérateur d'évolution temporelle correspondant \( e^{-i H t} \) peut être implémenté en utilisant poly(n,t) portes. À moins que BPP=BQP, ce problème n'est généralement pas résoluble sur un ordinateur classique en temps polynomial. De nombreuses techniques pour la simulation quantique ont été développées de manière abstraite pour des classes générales d'Hamiltoniens. Plus précisément, [95,92,372,278] considèrent des Hamiltoniens quantiques à n corps consistant en un terme cinétique \( \sum_{i=1}^n \nabla_i^2 \) plus un terme potentiel \( V(\mathbf{x}_1,\ldots,\mathbf{x}_n) \). Les travaux [5,25,12,205,211,245,294,295] considèrent des Hamiltoniens généraux épars. Les travaux [170,244,382] considèrent des Hamiltoniens exprimables comme une combinaison linéaire d'opérateurs unitaires efficacement implémentables. Certains travaux, tels que [293,470,496], considèrent le problème de simuler des Hamiltoniens \(H = \sum_j H_j \), où chaque \(e^{i H_j t} \) est efficacement implémentable, tout en restant indifférent à la nature de l'implémentation. Les travaux [468,469,467,466] considèrent les problèmes qui se posent lors de la simulation d'Hamiltoniens dépendants du temps. Les travaux [478,479] montrent que les Hamiltoniens géométriquement locaux sur des réseaux de dimension fixe peuvent être simulés plus efficacement que des Hamiltoniens généraux. Plus précisément, ils montrent que le temps d'exécution quantique dans ce cas est essentiellement linéaire par rapport au volume d'espace-temps du processus simulé. Un résultat connexe sur les implications d'efficacité de la localité approximative dans les systèmes de bosons interagissants est donné dans [480]. Si l'état simulé est de faible énergie, alors la norme de l'opérateur de l'Hamiltonien ne fournit qu'une borne supérieure lâche sur l'erreur de Trotter ; des bornes supérieures plus serrées dans ce cas sont données dans [481,482,483]. D'autres travaux considèrent des contextes physiques spécifiques, tels que la dynamique chimique [63,68,227,310,375], la physique de la matière condensée [1,99, 145], la mécanique quantique relativiste (les équations de Dirac et de Klein-Gordon) [367,369,370,371], les systèmes quantiques ouverts [376, 377,378,379,458], la théorie quantique des champs [107,166,228,229,230,368,484], et la théorie des champs conformes [495]. Bien que le problème de trouver les énergies fondamentales des Hamiltoniens locaux soit QMA-complet et nécessite donc probablement un temps exponentiel sur un ordinateur quantique dans le pire des cas, des algorithmes quantiques ont été développés pour approximer les états fondamentaux [102,231,232,233,234,235,308,321,322,373,380,381], états de faible énergie [463], et états thermiques [132,121,281,282,307, 456,491] pour certaines classes d'Hamiltoniens. Des algorithmes quantiques ont également été développés pour préparer des états d'équilibre pour certaines classes d'équations maîtresses [430]. Des algorithmes quantiques efficaces ont également été obtenus pour préparer certaines classes d'états de réseaux tensoriels [323,324,325,326,327,328]. Fait intéressant, simuler l'évolution temporelle d'Hamiltonien, ainsi que certains problèmes de préparation d'états fondamentaux et thermiques, peut tous être réalisé comme des cas particuliers de la transformation quantique des valeurs singulières [433].
Algorithme : Invariants de Nœud
Accélération : Superpolynomiale
Description : Comme montré par Freedman [42, 41], et al., trouver une certaine approximation additive au polynôme de Jones de la fermeture de plat d'une tresse à \( e^{i 2 \pi/5} \) est un problème BQP-complet. Ce résultat a été reformulé et étendu à \( e^{i 2 \pi/k} \) pour un k arbitraire par Aharonov et al. [4,2]. Wocjan et Yard ont encore généralisé cela, obtenant un algorithme quantique pour estimer le polynôme HOMFLY [93], dont le polynôme de Jones est un cas particulier. Aharonov et al. ont ensuite montré que les ordinateurs quantiques peuvent en temps polynomial estimer une certaine approximation additive au polynôme de Tutte encore plus général pour les graphes planaires [3]. On ne comprend pas entièrement pour quelle plage de paramètres l'approximation obtenue dans [3] est BQP-difficile. (Voir aussi fonctions de partition.) Des algorithmes quantiques en temps polynomial ont également été découverts pour approximer additivement les invariants de lien provenant des doubles quantiques de groupes finis [174]. (Ce problème n'est pas connu pour être BQP-difficile.) Comme montré dans [83], le problème de trouver une certaine approximation additive au polynôme de Jones de la fermeture de trace d'une tresse à \( e^{i 2 \pi/5} \) est DQC1-complet.
Algorithme : Invariants de Trois-Manifolds
Accélération : Superpolynomiale
Description : L'invariant de Turaev-Viro est une fonction qui prend des manifolds tridimensionnels en entrée et produit un nombre réel en sortie. Les manifolds homéomorphes donnent le même nombre. Étant donné un trois-manifold spécifié par une décomposition de Heegaard, un ordinateur quantique peut trouver efficacement une certaine approximation additive de son invariant de Turaev-Viro, et cette approximation est BQP-complete [129]. Auparavant, dans [114], un algorithme quantique en temps polynomial a été donné pour approximer additivement l'invariant Witten-Reshitikhin-Turaev (WRT) d'un manifold donné par une présentation chirurgicale. Le carré de l'invariant WRT donne l'invariant de Turaev-Viro. Cependant, on ne sait pas si l'approximation obtenue dans [114] est BQP-complete. Une suggestion d'un lien possible entre le calcul quantique et les invariants de trois-manifolds a également été donnée dans [115].
Algorithme : Fonctions de Partition
Accélération : Superpolynomiale
Description : Pour un système classique avec un ensemble fini d'états S, la fonction de partition est \( Z = \sum_{s \in S} e^{-E(s)/kT} \), où T est la température et k est la constante de Boltzmann. Essentiellement, chaque quantité thermodynamique peut être calculée en prenant une dérivée partielle appropriée de la fonction de partition. La fonction de partition du modèle Potts est un cas particulier du polynôme de Tutte. Un algorithme quantique pour approximer le polynôme de Tutte est donné dans [3]. Certaines connexions entre ces approches sont discutées dans [67]. Des algorithmes supplémentaires pour estimer les fonctions de partition sur des ordinateurs quantiques sont donnés dans [112,113,45,47]. Un résultat de BQP-complet (où les "énergies" peuvent être complexes) est également donné dans [113]. Une méthode pour approximer les fonctions de partition en simulant des processus de thermalisation est donnée dans [121]. Des accélérations polynomiales pour l'approximation de certaines classes générales de fonctions de partition sont données dans [122,471]. Une méthode basée sur des marches quantiques, atteignant une accélération polynomiale pour évaluer les fonctions de partition, est donnée dans [265].
Algorithme : Fonctions Zeta
Accélération : Superpolynomiale
Description : Soit f(x,y) un polynôme de degré d sur un corps fini \( \mathbb{F}_p \). Soit \( N_r \) le nombre de solutions projectives à f(x,y) = 0 sur le corps d'extension \( \mathbb{F}_{p^r} \). La fonction zeta pour f est définie comme \( Z_f(T) = \exp \left( \sum_{r=1}^\infty \frac{N_r}{r} T^r \right) \). Remarquablement, \( Z_f(T) \) a toujours la forme \( Z_f(T) = \frac{Q_f(T)}{(1-pT)(1-T)} \) où \( Q_f(T) \) est un polynôme de degré 2g et \(g = \frac{1}{2} (d-1)(d-2) \) est appelé le genre de f. Étant donné \( Z_f(T) \), on peut facilement calculer le nombre de zéros de f sur n'importe quel corps d'extension \( \mathbb{F}_{p^r} \). On peut également définir la fonction zeta lorsque le corps d'origine sur lequel f est défini n'a pas d'ordre premier. Comme montré par Kedlaya [64], les ordinateurs quantiques peuvent déterminer la fonction zeta d'une courbe de genre g sur un corps fini \( \mathbb{F}_{p^r} \) en \( \mathrm{poly}(\log p, r, g) \) temps. Les algorithmes classiques connus les plus rapides sont tous exponentiels soit en log(p) soit en g. Dans un contexte différent, mais quelque peu lié, van Dam a conjecturé qu'en raison d'une connexion entre les zéros des fonctions zeta de Riemann et les valeurs propres de certains opérateurs quantiques, les ordinateurs quantiques pourraient être capables d'approximer efficacement le nombre de solutions à des équations sur des corps finis [87].
Algorithme : Énumérateurs de Poids
Accélération : Superpolynomiale
Description : Soit C un code sur n bits, c'est-à-dire un sous-ensemble de \( \mathbb{Z}_2^n \). L'énumérateur de poids de C est \( S_C(x,y) = \sum_{c \in C} x^{|c|} y^{n-|c|} \) où |c| désigne le poids de Hamming de c. Les énumérateurs de poids ont de nombreuses utilisations dans l'étude des codes classiques. Si C est un code linéaire, il peut être défini par \( C = \{c: Ac = 0\} \) où A est une matrice sur \( \mathbb{Z}_2 \). Dans ce cas, \( S_C(x,y) = \sum_{c:Ac=0} x^{|c|} y^{n-|c|} \). Les énumérateurs de poids signés quadratiquement (QWGTs) sont une généralisation de cela : \( S(A,B,x,y) = \sum_{c:Ac=0} (-1)^{c^T B c} x^{|c|} y^{n-|c|} \). Considérons maintenant le cas spécial suivant. Soit A une matrice \( n \times n \) sur \( \mathbb{Z}_2 \) telle que diag(A)=I. Soit lwtr(A) la matrice triangulaire inférieure résultant de la mise à zéro de toutes les entrées au-dessus de la diagonale dans A. Soit l,k des entiers positifs. Étant donné la promesse que \( |S(A,\mathrm{lwtr}(A),k,l)| \geq \frac{1}{2} (k^2+l^2)^{n/2} \) le problème de déterminer le signe de \( S(A,\mathrm{lwtr}(A),k,l) \) est BQP-complet, comme montré par Knill et Laflamme dans [65]. L'évaluation des QWGTs est également étroitement liée à l'évaluation des fonctions de partition des modèles Ising et Potts [67,45,46].
Algorithme : Recuit Simulé
Accélération : Polynomiale
Description : Dans le recuit simulé, on a une série de chaînes de Markov définies par des matrices stochastiques \( M_1, M_2,\ldots,M_n \). Celles-ci varient lentement dans le sens où leurs distributions limites \( \pi_1, \pi_2, \ldots, \pi_n \) satisfont \( |\pi_{t+1} -\pi_t| < \epsilon \) pour un petit \( \epsilon \). Ces distributions peuvent souvent être considérées comme des distributions thermiques à des températures successivement plus basses. Si \( \pi_1 \) peut être facilement préparé, alors en appliquant cette série de chaînes de Markov, on peut échantillonner à partir de \( \pi_n \). Typiquement, on souhaite que \( \pi_n \) soit une distribution sur de bonnes solutions à un problème d'optimisation. Soit \( \delta_i \) l'écart entre les plus grandes et les deuxièmes plus grandes valeurs propres de \( M_i \). Soit \( \delta=\min_i \delta_i \). Le temps d'exécution de cet algorithme classique est proportionnel à \( 1/\delta \). S'appuyant sur les résultats de Szegedy [ 135,85], Somma et al. ont montré [84, 177] que les ordinateurs quantiques peuvent échantillonner à partir de \( \pi_n \) avec un temps d'exécution proportionnel à \( 1/\sqrt{\delta} \). Des méthodes supplémentaires par lesquelles les algorithmes classiques de Monte Carlo par chaînes de Markov peuvent être accélérés en utilisant des marches quantiques sont données dans [265].
Algorithme : Réécriture de Chaînes
Accélération : Superpolynomiale
Description : La réécriture de chaînes est un modèle de calcul assez général. Les systèmes de réécriture de chaînes (parfois appelés grammaires) sont spécifiés par une liste de règles selon lesquelles certaines sous-chaînes peuvent être remplacées par d'autres sous-chaînes. Par exemple, les grammaires sans contexte sont équivalentes aux automates à pile. Dans [59], Janzing et Wocjan ont montré qu'un certain problème de réécriture de chaînes est BQP-complet. Ainsi, les ordinateurs quantiques peuvent le résoudre en temps polynomial, mais les ordinateurs classiques ne le peuvent probablement pas. Étant donné trois chaînes s,t,t', et un ensemble de règles de réécriture de chaînes satisfaisant certaines promesses, le problème consiste à trouver une certaine approximation de la différence entre le nombre de façons d'obtenir t à partir de s et le nombre de façons d'obtenir t' à partir de s. De même, certains problèmes d'approximation de la différence dans le nombre de chemins entre des paires de sommets dans un graphe, et la différence dans les probabilités de transition entre des paires d'états dans une marche aléatoire sont également BQP-complets [58].
Algorithme : Puissances de Matrices
Accélération : Superpolynomiale
Description : Les ordinateurs quantiques ont un avantage exponentiel dans l'approximation des éléments de matrice des puissances de matrices creuses de grande taille exponentielle. Supposons que nous ayons une matrice symétrique \( N \times N \) A telle qu'il y ait au plus polylog(N) entrées non nulles dans chaque ligne, et qu'étant donné un index de ligne, l'ensemble des entrées non nulles puisse être calculé efficacement. La tâche consiste, pour tout \( 1 < i < N \) et tout \( m \) polylogarithmique en N, à approximer \( (A^m)_{ii} \), l'élément diagonal \( i^{\mathrm{th}} \) de la matrice \( A^m \). L'approximation est additive à l'intérieur de \( b^m \epsilon \) où b est une borne supérieure donnée sur |A| et \( \epsilon \) est d'ordre \( 1/\text{polylog}(N) \). Comme montré par Janzing et Wocjan, ce problème est BQP-complet, tout comme le problème correspondant pour les éléments de matrice hors diagonale [60]. Ainsi, les ordinateurs quantiques peuvent le résoudre en temps polynomial, mais les ordinateurs classiques ne le peuvent probablement pas.
Algorithme : Échantillonnage Probabiliste
Accélération : Superpolynomiale
Description : Bien que la plupart des problèmes computationnels soient formulés soit comme des problèmes de décision soit comme des problèmes de recherche, on peut également considérer la complexité de l'échantillonnage à partir d'une distribution donnée de chaînes de bits. Dans [474,473], il a été montré que les ordinateurs quantiques peuvent échantillonner efficacement à partir de certaines distributions qui ne peuvent pas être échantillonnées exactement par un algorithme classique aléatoire efficace, à moins que la hiérarchie polynomiale ne s'effondre au troisième niveau. Les problèmes d'échantillonnage de ce type ont ensuite été utilisés dans des expériences démontrant la capacité des ordinateurs quantiques actuels à réaliser des tâches qui dépassent les capacités des superordinateurs classiques. Cela est parfois appelé "suprématie quantique". Certains algorithmes quantiques atteignant une accélération polynomiale pour des problèmes d'échantillonnage avec des applications pratiques connues ont également été conçus [475].
Optimisation, Numérique et Apprentissage Automatique
Algorithme : Accélérations Quantique Polynomiales pour les Problèmes de Satisfaction de ContraintesAccélération : Polynomiale
Mise en œuvre : Classiq
Description : Les problèmes de satisfaction de contraintes, dont beaucoup sont NP-difficiles, sont omniprésents en informatique, un exemple canonique étant 3-SAT. Si l'on souhaite satisfaire autant de contraintes que possible plutôt que toutes, ceux-ci deviennent des problèmes d'optimisation combinatoire. (Voir aussi algorithmes adiabatiques.) La solution par force brute aux problèmes de satisfaction de contraintes peut être accélérée quadratiquement en utilisant l'algorithme de Grover. Cependant, la plupart des problèmes de satisfaction de contraintes sont résolvables par des algorithmes classiques qui (bien que toujours en temps exponentiel) s'exécutent plus de manière quadratique plus rapidement que la vérification par force brute de toutes les solutions possibles. Néanmoins, une accélération quantique polynomiale par rapport à l'algorithme classique le plus rapide connu pour 3-SAT est donnée dans [133], et des accélérations quantiques polynomiales pour certains autres problèmes de satisfaction de contraintes sont données dans [134,298,493,492]. Dans [423] une accélération quantique quadratique pour des solutions approximatives aux problèmes homogènes QUBO/Ising est obtenue en s'appuyant sur l'algorithme quantique pour la programmation semi-définie. Un algorithme classique couramment utilisé pour la satisfaction de contraintes est le retour en arrière, et pour certains problèmes, cet algorithme est le plus rapide connu. Une accélération quantique générale pour les algorithmes de retour en arrière est donnée dans [264] et améliorée dans [422].
Algorithme : Algorithmes Adiabatiques
Accélération : Inconnue
Description : Dans le calcul quantique adiabatique, on commence avec un Hamiltonien initial dont l'état fondamental est facile à préparer, et on varie lentement l'Hamiltonien vers un dont l'état fondamental encode la solution à un problème computationnel. Par le théorème adiabatique, le système suivra l'état fondamental instantané à condition que la variation de l'Hamiltonien soit suffisamment lente. Le temps d'exécution d'un algorithme adiabatique évolue au pire comme \(1/ \gamma^3 \) où \( \gamma \) est l'écart minimal entre la valeur propre fondamentale et le premier état excité [185]. Si l'Hamiltonien est varié de manière suffisamment lisse, on peut améliorer cela à \( \widetilde{O}(1/\gamma^2) \) [247]. Le calcul quantique adiabatique a été proposé pour la première fois par Farhi et al. comme une méthode pour résoudre des problèmes d'optimisation combinatoire NP-complets [96, 186]. Les algorithmes quantiques adiabatiques pour les problèmes d'optimisation utilisent généralement des Hamiltoniens "stoquastiques", qui ne souffrent pas du problème de signe. De tels algorithmes sont parfois appelés recuit quantique. Le calcul quantique adiabatique avec des Hamiltoniens non-stoquastiques est aussi puissant que le modèle de circuit quantique [97]. Les algorithmes adiabatiques utilisant des Hamiltoniens stoquastiques sont probablement moins puissants [183], mais sont susceptibles d'être plus puissants que le calcul classique [429]. Le temps d'exécution asymptotique des algorithmes d'optimisation adiabatiques est notoirement difficile à analyser, mais certains progrès ont été réalisés [179,180,181,182,187,188,189,190,191,226]. (Il est également pertinent de mentionner une littérature antérieure sur le recuit quantique, qui faisait initialement référence à un algorithme d'optimisation classique qui fonctionne en simulant un processus quantique, tout comme le recuit simulé est un algorithme d'optimisation classique qui fonctionne en simulant un processus thermique. Voir par exemple [199, 198].) Les ordinateurs quantiques adiabatiques peuvent effectuer un processus quelque peu analogue à la recherche de Grover en \( O(\sqrt{N}) \) temps [98]. Les algorithmes quantiques adiabatiques atteignant une accélération quadratique pour une classe plus générale de problèmes sont construits dans [184] en adaptant des techniques de [85]. Des algorithmes quantiques adiabatiques ont été proposés pour plusieurs problèmes spécifiques, y compris PageRank [176], apprentissage automatique [192, 195], recherche de matrices de Hadamard [406], et problèmes de graphes [193, 194]. Certains algorithmes de simulation quantique utilisent également la préparation d'état adiabatique.
Algorithme : Optimisation Approximative Quantique
Accélération : Superpolynomiale
Mise en œuvre : Classiq, Cirq
Description : Pour de nombreux problèmes d'optimisation combinatoire, trouver la solution optimale exacte est NP-complet. Il existe également des résultats de dureté d'approximation prouvant que trouver une approximation avec une erreur suffisamment petite est NP-complet. Pour certains problèmes, il existe un écart entre la meilleure borne d'erreur atteinte par un algorithme classique d'approximation en temps polynomial et la borne d'erreur prouvée comme étant NP-difficile. Dans ce régime, il y a un potentiel d'accélération exponentielle par le calcul quantique. Dans [242] une nouvelle technique algorithmique quantique appelée l'Algorithme d'Optimisation Approximative Quantique (QAOA) a été proposée pour trouver des solutions approximatives à des problèmes d'optimisation combinatoire. Dans [243] il a été montré par la suite que le QAOA résout un problème d'optimisation combinatoire appelé Max E3LIN2 avec un meilleur rapport d'approximation que tout algorithme classique connu en temps polynomial à l'époque. Cependant, un algorithme classique efficace atteignant un rapport d'approximation encore meilleur (en fait, le rapport d'approximation saturant la limite fixée par la dureté d'approximation) a été découvert par la suite [260]. Actuellement, le pouvoir du QAOA par rapport au calcul classique est un domaine de recherche actif [300,301,302, 314,451,452,476].
Algorithme : Estimation de Gradient et Apprentissage de Polynomiales
Accélération : Polynomiale
Description : Supposons que nous ayons un oracle pour calculer une fonction lisse \( f:\mathbb{R}^d \to \mathbb{R} \) avec une précision \( \pm \epsilon \). La tâche consiste à estimer \( \nabla f \) à un point spécifié \( \mathbf{x}_0 \in \mathbb{R}^d \). Comme montré dans [61], un ordinateur quantique peut y parvenir en utilisant une seule requête, tandis qu'un ordinateur classique a besoin d'au moins d+1 requêtes. Dans [436] la dépendance par rapport à \( \epsilon \) a été rigoureusement analysée et améliorée quadratiquement par rapport à [61]. Des analyses de la dépendance par rapport à la régularité de f sont données dans [437,438]. L'extension à des fonctions f à valeurs complexes et une méthode alternative pour améliorer la dépendance à \( \epsilon \) sont données dans [439]. Dans [20], Bulger a suggéré des applications potentielles pour des problèmes d'optimisation. Comme montré dans l'annexe D de [62], un ordinateur quantique peut utiliser l'algorithme de gradient pour trouver le minimum d'une forme quadratique dans d dimensions en utilisant O(d) requêtes, tandis que, comme montré dans [94], un ordinateur classique a besoin d'au moins \( \Omega(d^2) \) requêtes. L'algorithme quantique de [62] peut également extraire tous les \( d^2 \) éléments de matrice de la forme quadratique en utilisant O(d) requêtes, et plus généralement, tous les \( d^n \) n-ièmes dérivées d'une fonction lisse de d variables en \( O(d^{n-1}) \) requêtes. Voir aussi : optimisation convexe.
Algorithme : Programmation Semidéfinitive
Accélération : Polynomiale (avec quelques exceptions)
Description : Étant donné une liste de m + 1 matrices Hermitiennes \(n \times n \) \(C, A_1, A_2, \ldots, A_m\) et m nombres \(b_1, \ldots, b_m \), le problème de la programmation semidéfinitive est de trouver la matrice \( n \times n \) positive semidéfinitive X qui maximise tr(CX) sous les contraintes \( \mathrm{tr} (A_j X) \leq b_j \) pour \( j = 1,2,\ldots, m \). La programmation semidéfinitive a de nombreuses applications en recherche opérationnelle, optimisation combinatoire et information quantique, et elle inclut la programmation linéaire comme cas particulier. Introduite dans [313], et améliorée par la suite dans [383, 425], des algorithmes quantiques sont maintenant connus qui peuvent résoudre approximativement des programmes semidéfinitifs à l'intérieur de \( \pm \epsilon \) en temps \( O (\sqrt{m} \log m \cdot \mathrm{poly}(\log n, r, \epsilon^{-1})) \), où r est le rang du programme semidéfinitif. Cela constitue une accélération quadratique par rapport aux algorithmes classiques les plus rapides lorsque r est petit par rapport à n. L'algorithme quantique est basé sur l'amplification d'amplitude et l'échantillonnage de Gibbs quantique [121, 307]. Dans un modèle où l'entrée est fournie sous forme d'états quantiques, l'algorithme quantique pour la programmation semidéfinitive peut atteindre une accélération superpolynomiale, comme discuté dans [383], bien que des résultats récents de déquantification [421] délimitent les limitations sur le contexte dans lequel une accélération quantique superpolynomiale pour les programmes semidéfinitifs est possible.
Algorithme : Optimisation par Interférométrie Quantique Décodée
Accélération : Superpolynomiale
Mise en œuvre : Classiq
Description : Dans [453], une méthode appelée Interférométrie Quantique Décodée (DQI) est introduite, qui réduit les problèmes d'optimisation à des problèmes de décodage utilisant des transformations de Fourier quantiques. Cela produit des optima approximatifs, où le nombre de contraintes satisfaites est déterminé par le nombre d'erreurs qui peuvent être décodées. Si chaque contrainte dépend d'un nombre limité de variables, alors le problème de décodage résultant est pour un code LDPC classique. Ceux-ci peuvent être décodés à partir d'un grand nombre d'erreurs en utilisant des algorithmes classiques efficaces tels que la propagation de croyance. Une structure supplémentaire dans les contraintes se traduit également dans le problème de décodage et peut dans certains cas être exploitée. En particulier, certains problèmes de recherche d'un polynôme de degré n sur un corps fini \( \mathbb{F}_p \) qui approxime le mieux possible un ensemble de données donné sont réduits via DQI à un décodage de codes Reed-Solomon. Parce que des algorithmes classiques efficaces sont connus pour décoder les codes Reed-Solomon avec de nombreuses erreurs (la moitié de leur distance), DQI atteint une très bonne approximation des problèmes de régression polynomiale d'origine, ce qui n'est pas connu pour être réalisable par un algorithme classique en temps polynomial, atteignant ainsi une accélération exponentielle apparente. Les résultats de [454] donnant une accélération quartique pour un problème d'inférence plantée et les résultats de [455] donnant une séparation exponentielle entre la complexité de requête quantique et classique pour un oracle aléatoire, bien que pas initialement formulés comme des algorithmes d'optimisation quantique, ont des relations étroites avec DQI.
Algorithme : Systèmes Linéaires
Accélération : Superpolynomiale
Mise en œuvre : Classiq(hhl), Classiq(qsvt), Cirq(hhl)
Description : Nous avons accès par oracle à une matrice \( n \times n \) A et une description d'un vecteur b. Nous souhaitons trouver une propriété de f(A)b pour une fonction f calculable efficacement. Supposons que A soit une matrice Hermitienne avec O(polylog n) entrées non nulles dans chaque ligne et un nombre conditionnel k. Comme montré dans [104], un ordinateur quantique peut en \( O(k^2 \log n) \) temps calculer avec une précision polynomiale diverses valeurs d'attente d'opérateurs par rapport au vecteur f(A)b (à condition qu'un état quantique proportionnel à b soit constructible efficacement). Pour certaines fonctions, telles que f(x)=1/x, cette procédure peut être étendue à des matrices non-Hermitiennes et même non carrées A. Le temps d'exécution de cet algorithme a ensuite été amélioré à \( O(k \log^3 k \log n) \) dans [138]. Une amélioration exponentielle de l'échelle de temps d'exécution avec précision a été obtenue dans [263]. D'autres améliorations ont été réalisées dans [494]. Certaines méthodes pour étendre cet algorithme à des matrices non creuses ont été proposées [309,402], bien que celles-ci nécessitent que certaines sommes partielles des éléments de la matrice soient pré-calculées. Des extensions de cet algorithme quantique ont été appliquées à des problèmes d'estimation des sections efficaces de diffusion électromagnétique [249] (voir aussi [369] pour une approche différente), la résolution d'équations différentielles [156, 296], l'estimation de la résistance électrique des réseaux [210], l'ajustement de courbes par moindres carrés [169], la résolution de systèmes de Toeplitz [297], et l'apprentissage automatique [214,222,250,251,309]. Cependant, les algorithmes quantiques basés sur des systèmes linéaires pour les systèmes de recommandation [309] et l'analyse en composantes principales [250] ont ensuite été "déquantifiés" par Tang [400, 401]. C'est-à-dire que Tang a obtenu des algorithmes classiques aléatoires en temps polynomial pour ces problèmes, prouvant ainsi que les algorithmes quantiques proposés pour ces tâches n'atteignent pas une accélération exponentielle. Certaines limitations des algorithmes d'apprentissage automatique quantiques basés sur des systèmes linéaires sont bien résumées dans [246]. Dans [220], il a été montré que les ordinateurs quantiques peuvent inverser des matrices \( n \times n \) bien conditionnées en utilisant seulement \( O( \log n ) \) qubits, tandis que le meilleur algorithme classique utilise un ordre de \( \log^2 n \) bits. Des améliorations ultérieures à cet algorithme quantique sont données dans [279]. Des variantes du problème des systèmes linéaires, y compris le calcul des pseudoinverses de Moore-Penrose, peuvent être obtenues comme des cas particuliers de la transformation de valeur singulière quantique [433].
Algorithme : Apprentissage Automatique
Accélération : Varie
Mise en œuvre : Classiq(qsvm), Classiq(autoencoder)
Description : L'apprentissage automatique englobe une grande variété de problèmes computationnels et peut être abordé par une grande variété de techniques algorithmiques. Cette entrée résume les techniques algorithmiques quantiques pour améliorer l'apprentissage automatique. Beaucoup des algorithmes quantiques ici sont également répertoriés sous d'autres rubriques. Dans [214,250,251,309,338,339,359,403], les algorithmes quantiques pour résoudre des systèmes linéaires [104] sont appliqués pour accélérer la recherche de clusters, l'analyse en composantes principales, la classification binaire, l'entraînement de réseaux de neurones, et diverses formes de régression, à condition que les données satisfassent certaines conditions. (Voir aussi [433] pour des améliorations ultérieures de l'analyse en composantes principales quantiques.) Cependant, un certain nombre d'algorithmes d'apprentissage automatique quantiques basés sur des systèmes linéaires ont depuis été "déquantifiés". En particulier, Tang a montré dans [400, 401] que les problèmes de systèmes de recommandation et d'analyse en composantes principales résolus par les algorithmes quantiques de [251,309] peuvent en fait également être résolus en temps polynomial par des algorithmes classiques randomisés. Les travaux [222,487,488,489,490] donnent des algorithmes quantiques pour l'analyse de données topologiques par homologie persistante. Une méthode de recherche de clusters non basée sur l'algorithme des systèmes linéaires de [104] est donnée dans [336]. Les articles [192,195,344,345,346,348] explorent l'utilisation de techniques d'optimisation adiabatiques pour l'entraînement de classificateurs. Dans [456], des machines quantiques Ising sont utilisées pour l'entraînement de réseaux de neurones classiques. Dans [221], une méthode est proposée pour entraîner des machines de Boltzmann en manipulant des états quantiques cohérents avec des amplitudes proportionnelles aux poids de Boltzmann. Des accélérations polynomiales peuvent être obtenues en appliquant la recherche de Grover et des techniques connexes telles que l'amplification d'amplitude à des sous-routines appropriées des algorithmes d'apprentissage automatique classiques à la pointe de la technologie. Voir, par exemple [358,340,341,342,343]. D'autres algorithmes d'apprentissage automatique quantiques ne relevant pas de l'une des catégories ci-dessus incluent [337,349]. Certaines limitations des algorithmes d'apprentissage automatique quantiques sont bien résumées dans [246]. De nombreux autres algorithmes de requête quantique qui extraient la structure cachée de la fonction boîte noire pourraient être considérés comme des algorithmes d'apprentissage automatique. Voir par exemple [146,23,11,31,212]. Des algorithmes de requête pour apprendre les fonctions de majorité et "battleship" sont donnés dans [224]. D'importants avantages quantiques pour l'apprentissage à partir d'oracles bruyants sont donnés dans [236,237]. Dans [428], l'estimation de noyau quantique est utilisée pour mettre en œuvre un classificateur à vecteurs de support résolvant un problème d'apprentissage qui est prouvablement aussi difficile que le logarithme discret. Plusieurs articles de revue récents [299,332,333] et un livre [331] sont disponibles qui résument l'état du domaine. Il existe un corpus de travaux connexes, pas strictement dans le cadre standard des algorithmes quantiques, concernant l'apprentissage quantique dans le cas où les données elles-mêmes sont quantiquement cohérentes. Voir par exemple [350,334,335,351,352,353,354,355,356,357].
Algorithme : Analyse en Composantes Principales Tensorielle
Accélération : Polynomiale (quartique)
Description : Dans [424], un algorithme quantique est donné pour un problème idéalisé motivé par des applications d'apprentissage automatique sur des ensembles de données de haute dimension. Considérons \(T = \lambda v_{\mathrm{sig}}^{\otimes p} + G \) où G est un tenseur de variables aléatoires gaussiennes à p indices, symétrisé sur toutes les permutations d'indices, et \(v_{\mathrm{sig}}\) est un vecteur N-dimensionnel de magnitude \(\sqrt{N}\). La tâche est de récupérer \(v_{\mathrm{sig}}\). Considérons \( \lambda = \alpha N^{-p/4}\). Les meilleurs algorithmes classiques réussissent lorsque \( \alpha \gg 1\) et ont une complexité temporelle et spatiale qui évolue exponentiellement en \( \alpha^{-1}\). L'algorithme quantique de [424] résout ce problème dans un espace polynomial et avec un temps d'exécution évoluant quartiquement mieux en \( \alpha^{-1} \) que l'algorithme spectral classique. L'algorithme quantique fonctionne en encodant le problème dans l'eigenspectre d'un Hamiltonien à plusieurs corps et en appliquant l'estimation de phase ainsi que l'amplification d'amplitude.
Algorithme : Résolution d'Équations Différentielles Linéaires
Accélération : Superpolynomiale
Mise en œuvre : Classiq
Description : Considérons l'équation différentielle linéaire du premier ordre \( \frac{d}{dt} \mathbf{x} = A(t) \mathbf{x} + \mathbf{b}(t) \), où \( \mathbf{x} \) et \( \mathbf{b} \) sont des vecteurs N-dimensionnels et A est une matrice \(N \times N\). Étant donné une condition initiale \( \mathbf{x}(0) \), on souhaite calculer la solution \( \mathbf{x}(t) \) à un moment ultérieur t avec une précision \( \epsilon \) dans le sens où le vecteur normalisé \( x(t)/\|x(t)\| \) produit a une distance d'au plus \( \epsilon \) de la solution exacte. Dans [156], Berry propose un algorithme quantique pour ce problème qui s'exécute en temps \( O(t^2 \mathrm{poly}(1/\epsilon) \mathrm{poly log} N) \), tandis que les algorithmes classiques les plus rapides s'exécutent en temps \( O ( t \ \mathrm{poly} N ) \). Le résultat final est produit sous la forme d'un état de superposition quantique sur \( O(log N) \) qubits dont les amplitudes contiennent les composants de \( \mathbf{x}(t) \). L'algorithme fonctionne en réduisant le problème à l'algèbre linéaire via une méthode de différences finies d'ordre élevé et en appliquant le primitive d'algèbre linéaire quantique de [104]. Dans [410], un algorithme quantique amélioré pour ce problème a été donné qui réduit la dépendance à epsilon à \( \mathrm{poly log}(1/\epsilon) \). La technique de traitement des valeurs propres quantiques de [459] offre également des améliorations d'efficacité pour résoudre des équations différentielles linéaires. Dans [440], il est montré que la simulation quantique des EDO linéaires régissant des oscillateurs harmoniques classiques couplés peut être résolue exponentiellement plus rapidement sur des ordinateurs quantiques que sur des ordinateurs classiques lorsque la connectivité est un graphe expanse. Les équations différentielles partielles peuvent être réduites à des équations différentielles ordinaires par discrétisation, et les équations différentielles d'ordre supérieur peuvent être réduites au premier ordre par ajout de variables auxiliaires. Par conséquent, ces problèmes plus généraux peuvent être résolus par les méthodes de [156, 104]. Cependant, les algorithmes quantiques conçus pour résoudre ces problèmes directement peuvent être plus efficaces (et pour des problèmes spécifiques, on peut analyser la complexité des tâches qui ne sont pas spécifiées dans une formulation plus générale telle que la préparation des états initiaux pertinents). Dans [442], l'échelle avec précision est améliorée pour simuler des équations différentielles linéaires elliptiques d'ordre deux. Dans [249], un algorithme quantique est donné qui résout l'équation des ondes en appliquant des méthodes d'éléments finis pour la réduire à l'algèbre linéaire et ensuite en appliquant l'algorithme d'algèbre linéaire quantique de [104] avec préconditionnement. Dans [369], un algorithme quantique est donné pour résoudre l'équation des ondes en la discrétisant avec des différences finies et en la transformant en une équation de Schrödinger qui est ensuite simulée en utilisant la méthode de [245]. Le problème résolu par [369] n'est pas équivalent à celui résolu par [249] parce que dans [249] le problème est réduit à un problème indépendant du temps en supposant une dépendance temporelle sinusoïdale et en appliquant la séparation des variables, tandis que [369] résout le problème dépendant du temps. L'accélération quantique obtenue par rapport aux méthodes classiques pour résoudre l'équation des ondes en d-dimensions est polynomiale pour un d fixe mais exponentielle en d. Des estimations concrètes des ressources pour les algorithmes quantiques visant à résoudre des équations différentielles sont données dans [412, 413, 414]. Un algorithme quantique pour résoudre des équations différentielles partielles linéaires utilisant l'informatique quantique à variables continues est donné dans [415]. Dans [296], les méthodes d'éléments finis quantiques sont analysées dans un cadre général. Une méthode spectrale quantique pour résoudre des équations différentielles est donnée dans [416]. L'analyse des algorithmes quantiques appliqués à l'équation de chaleur en
Algorithme : Résolution d'Équations Différentielles Non Linéaires
Accélération : Superpolynomiale
Description : Un algorithme quantique pour résoudre des équations différentielles non linéaires, dans le sens d'obtenir une solution encodée dans les amplitudes, est décrit dans [411], qui a une échelle exponentielle en t. Dans [426], une méthode est introduite pour résoudre des équations différentielles non linéaires en utilisant la linéarisation de Carleman, dont le temps d'exécution évolue comme \( O(t^2) \) lorsque l'équation différentielle satisfait les conditions nécessaires pour que l'algorithme quantique s'applique. Une analyse plus approfondie et une amélioration des algorithmes quantiques basés sur Carleman sont données dans [434,441]. Dans [427], en s'appuyant sur l'intuition de l'équation de Schrödinger non linéaire, un autre algorithme quantique est donné pour résoudre des équations non linéaires qui évolue également comme \( O(t^2) \). Notez que les algorithmes quantiques pour résoudre des équations non linéaires encodent généralement la solution dans les amplitudes d'un état quantique, et donc l'universalité implique que les algorithmes ne seront pas efficaces si ces solutions ont une norme qui croît ou diminue trop rapidement. Un algorithme quantique pour résoudre une PDE non linéaire appelée l'équation de Vlasov, qui apparaît en physique des plasmas, est donné dans [417]. Plusieurs travaux donnent des algorithmes quantiques pour remplacer les simulations de Monte Carlo des équations différentielles non linéaires, réduisant la dépendance au temps d'exécution par rapport à la précision de \( O(\epsilon^{-2})\) à \( O(\epsilon^{-1}) \). Plus précisément, [443, 447, 448, 450] le font dans le contexte de la finance (y compris les équations différentielles stochastiques), et [444, 445] le font dans le contexte de la dynamique des fluides. Une heuristique quantique pour résoudre l'équation de Black-Scholes en la reliant à l'évolution de Schrödinger en temps imaginaire est proposée dans [449].
Algorithme : Programmation Dynamique Quantique
Accélération : Polynomiale
Description : Dans [409], les auteurs introduisent un problème appelé chemin-dans-le-cube. Dans ce problème, on donne un sous-graphe du cube et on demande s'il existe un chemin le long de ce sous-graphe qui commence à partir du sommet de tous zéros, se termine au sommet de tous uns, et effectue uniquement des mouvements d'augmentation de poids de Hamming. (Les sommets du graphe du cube correspondent à des chaînes de bits de longueur n et le graphe du cube relie des sommets de distance de Hamming un.) De nombreux problèmes NP-complets pour lesquels le meilleur algorithme classique est la programmation dynamique peuvent être modélisés comme des instances de chemin-dans-le-cube. En combinant la recherche de Grover avec des méthodes de programmation dynamique, un algorithme quantique peut résoudre le chemin-dans-le-cube en temps \( O^*(1.817^n) \), où la notation \( O^* \) indique que les facteurs polynomiaux sont omis. L'algorithme classique le plus rapide pour ce problème s'exécute en temps \( O^*(2^n) \). En utilisant ce primitive, des algorithmes quantiques peuvent être construits qui résolvent des problèmes d'ordonnancement de sommets en \( O^*(1.817^n) \) contre \( O^* (2^n) \) classiquement, la bande passante du graphe en \( O^*(2.946^n) \) contre \( O^*(4.383^n) \) classiquement, le voyageur de commerce et l'ensemble de rétroaction en \( O^*(1.729^n) \) contre \( O^*(2^n) \) classiquement, et le minimum de l'ensemble en \( O( \mathrm{poly}(m,n) 1.728^n ) \) contre \( O(nm2^n) \) classiquement.
Algorithme : Calcul de l'Eigenvecteur Principal
Accélération : Polynomiale
Description : Étant donné un accès par requête aux éléments de la matrice d'un \( d \times d \) matrice hermitienne A, notre problème est de obtenir l'eigenvecteur principal de A, c'est-à-dire l'eigenvecteur correspondant à la plus grande valeur propre. Si nous souhaitions obtenir cet eigenvecteur sous forme d'état quantique, cela serait équivalent au problème de l'état fondamental. Cependant, nous voulons plutôt une description classique de l'eigenvecteur. Des algorithmes quantiques résolvant ce problème et certains problèmes connexes sont donnés dans [462]. L'algorithme quantique de [462] s'exécute en temps \( \widetilde{O}(d^{3/2}) \) tandis que le meilleur algorithme classique s'exécute en temps \( \widetilde{O}(d^2) \).
Algorithme : Approximations des Équilibres de Nash
Accélération : Polynomiale
Description : Étant donné un accès oracle à une matrice de paiement \( m \times n \) d'un jeu à somme nulle, nous souhaitons calculer un équilibre de Nash approximatif \(\epsilon\). Classiquement, le meilleur algorithme pour cela a un temps d'exécution \( \widetilde{O}((m+n) \epsilon^{-2}) \). L'algorithme quantique de [485], améliorant le résultat précédent de [486], atteint cela en temps d'exécution \( \widetilde{O}( \sqrt{m+n} \epsilon^{-2.5} + \epsilon^{-3}) \) en établissant un lien entre les équilibres de Nash et l'échantillonnage de Gibbs.
Algorithme : Problèmes de Réseaux par Filtrage
Accélération : Exponentielle
Description : Nous avons un ensemble de vecteurs de base dans \( \mathbb{Z}^n \) et nous considérons le réseau \( \mathcal{L} \) défini par toutes les combinaisons linéaires entières de ces vecteurs de base. En général, trouver le plus court vecteur non nul dans \( \mathcal{L} \) est un problème NP-difficile. Étant donné un point cible \( \mathbf{x} \in \mathbb{Z}^n \), trouver l'élément le plus proche de \( \mathcal{L} \) est également NP-difficile. Il existe divers problèmes de recherche de solutions approximativement optimales, ou de recherche de solutions données certaines promesses sur le $\mathcal{L}$ qui ne sont pas connues pour être NP-difficiles mais qui manquent de solutions classiques en temps polynomial. De tels problèmes, versions de qui sous-tendent de nombreux systèmes cryptographiques post-quantiques, constituent des cibles très importantes pour la recherche sur les algorithmes quantiques. Dans [498], Chen, Liu et Zhandry ont obtenu des algorithmes quantiques en temps polynomial pour certains problèmes de réseaux qui n'ont pas de solutions classiques en temps polynomial connues. Ces algorithmes quantiques s'appliquent dans un régime de paramètres qui ne compromet pas les principaux candidats aux systèmes cryptographiques post-quantiques. Un ingrédient clé dans ces algorithmes est l'observation de [78, 5] selon laquelle la transformation de Fourier quantique permet des réductions efficaces dans les deux directions entre les problèmes de plus court vecteur sur un réseau et les problèmes de vecteur le plus proche sur le réseau dual. Dans [498], les auteurs ajoutent également un nouvel ingrédient, qui est une technique de filtrage utilisant des mesures quantiques dans des bases non triviales pour améliorer les paramètres de ces réductions de manière à atteindre un avantage quantique.
Remerciements
Je remercie les personnes suivantes pour avoir contribué de leur expertise (dans l'ordre chronologique).- Daniel Lidar
- Wim van Dam
- Geordie Rose
- Yi-Kai Liu
- Robin Kothari
- Martin Schwarz
- Dorit Aharonov
- Alessandro Cosentino
- Andrew Childs
- Stacey Jeffery
- Lov Grover
- Eduin H. Serna
- Charles Greathouse
- Juani Bermejo-Vega
- Luis Kowada
- Keith Britt
- Aram Harrow
- Zafer Gedik
- David Cornwell
- Cedric Lin
- Shelby Kimmel
- Jeremy Singer
- Dan Boneh
- Rich Schroeppel
- Yuan Su
- Tim Stevens
- Martin Ekerå
- Igor Shparlinski
- Timothy Chase
- Alejandro Pozas-Kerstjens
- Nikhil Vyas
- Kevin Lui
- Vladimir Korepin
- Andriyan Suksmono
- Jack Hidary
- Donny Greenberg
- Nicola Vitucci
- Kunal Marwaha
- José Ignacio Espinoza Camacho
- Vincenzo Savona
- Barry Sanders
- Jeremy Wright
- Sarah Kaiser
- Benjamin Tokgöz
- Armando Bellante
- Seongbin Park
- Xujie Song
- Alexis Fimeyer
Références
- 1
-
Daniel S. Abrams et Seth Lloyd
Simulation de systèmes de Fermi à plusieurs corps sur un ordinateur quantique universel. (Simulation of many-body Fermi systems on a universal quantum computer)
Physical Review Letters, 79(13):2586-2589, 1997.
[arXiv:quant-ph/9703054]
- 2
-
Dorit Aharonov et Itai Arad
La BQP-difficulté d'approximer le polynôme de Jones. (The BQP-hardness of approximating the Jones polynomial)
New Journal of Physics 13:035019, 2011.
[arXiv:quant-ph/0605181]
- 3
-
Dorit Aharonov, Itai Arad, Elad Eban et Zeph Landau
Algorithmes quantiques polynomiaux pour des approximations additives du modèle de Potts et d'autres points du plan de Tutte. (Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane)
arXiv:quant-ph/0702008, 2007.
- 4
-
Dorit Aharonov, Vaughan Jones et Zeph Landau
Un algorithme quantique polynômial pour approximer le polynôme de Jones. (A polynomial quantum algorithm for approximating the Jones polynomial)
Dans Proceedings of the 38th ACM Symposium on Theory of Computing, 2006.
[arXiv:quant-ph/0511096]
- 5
-
Dorit Aharonov et Amnon Ta-Shma
Génération d'état quantique adiabatique et connaissance zéro statistique. (Adiabatic quantum state generation and statistical zero knowledge)
Dans Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.
[arXiv:quant-ph/0301023]
- 6
-
A. Ambainis, H. Buhrman, P. Høyer, M. Karpinizki et P. Kurur
Vérification de matrice quantique. (Quantum matrix verification)
Manuscrit non publié, 2002.
- 7
-
Andris Ambainis
Algorithme de marche quantique pour la distinctesse des éléments. (Quantum walk algorithm for element distinctness)
SIAM Journal on Computing, 37:210-239, 2007.
[arXiv:quant-ph/0311001]
- 8
-
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek et
Shengyu Zheng
Chaque formule AND-OR de taille N peut être évaluée en temps \( n^{1/2+o(1)} \) sur un ordinateur quantique. (Every AND-OR formula of size N can be evaluated in time \( n^{1/2+o(1)} \) on a quantum computer)
Dans Proceedings of the 48th IEEE Symposium on the Foundations of Computer Science, pages 363-372, 2007.
[ arXiv:quant-ph/0703015 et arXiv:0704.3628]
- 9
-
Dave Bacon, Andrew M. Childs et Wim van Dam
De la mesure optimale aux algorithmes quantiques efficaces pour le problème du sous-groupe caché sur des groupes de produit semi-direct. (From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups)
Dans Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pages 469-478, 2005.
[arXiv:quant-ph/0504083]
- 10
-
Michael Ben-Or et Avinatan Hassidim
Recherche quantique dans une liste ordonnée via un apprentissage adaptatif. (Quantum search in an ordered list via adaptive learning)
arXiv:quant-ph/0703231, 2007.
- 11
-
Ethan Bernstein et Umesh Vazirani
Théorie de la complexité quantique. (Quantum complexity theory)
Dans Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 11-20, 1993.
- 12
-
D.W. Berry, G. Ahokas, R. Cleve et B. C. Sanders
Algorithmes quantiques efficaces pour simuler des Hamiltoniens clairsemés. (Efficient quantum algorithms for simulating sparse Hamiltonians)
Communications in Mathematical Physics, 270(2):359-371, 2007.
[arXiv:quant-ph/0508139]
- 13
-
A. Berzina, A. Dubrovsky, R. Frivalds, L. Lace et O. Scegulnaja
Complexité de requête quantique pour certains problèmes de graphes. (Quantum query complexity for some graph problems)
Dans Proceedings of the 30th Conference on Current Trends in Theory and Practice of Computer Science, pages 140-150, 2004.
- 14
-
D. Boneh et R. J. Lipton
Cryptanalyse quantique de fonctions linéaires cachées. (Quantum cryptanalysis of hidden linear functions)
Dans Don Coppersmith, éditeur, CRYPTO '95, Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, 1995.
- 15
-
M. Boyer, G. Brassard, P. Høyer et A. Tapp
Limites serrées sur la recherche quantique. (Tight bounds on quantum searching)
Fortschritte der Physik, 46:493-505, 1998.
- 16
-
G. Brassard, P. Høyer et A. Tapp
Comptage quantique. (Quantum counting)
arXiv:quant-ph/9805082, 1998.
- 17
-
Gilles Brassard, Peter Høyer, Michele Mosca et Alain Tapp
Amplification et estimation d'amplitude quantique. (Quantum amplitude amplification and estimation)
Dans Samuel J. Lomonaco Jr. et Howard E. Brandt, éditeurs, Quantum Computation and Quantum Information: A Millennium Volume, volume 305 de AMS Contemporary Mathematics Series. American Mathematical Society, 2002.
[arXiv:quant-ph/0005055]
- 18
-
Gilles Brassard, Peter Høyer et Alain Tapp
Algorithme quantique pour le problème de collision. (Quantum algorithm for the collision problem)
ACM SIGACT News, 28:14-19, 1997.
[arXiv:quant-ph/9705002]
- 19
-
Harry Buhrman et Robert Špalek
Vérification quantique des produits de matrices. (Quantum verification of matrix products)
Dans Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 880-889, 2006.
[arXiv:quant-ph/0409035]
- 20
-
David Bulger
Basin quantique avec optimisation locale basée sur le gradient. (Quantum basin hopping with gradient-based local optimisation)
arXiv:quant-ph/0507193, 2005.
- 21
-
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer,
Frédéric Magniez, Miklos Santha et Ronald de Wolf
Algorithmes quantiques pour la distinctesse des éléments. (Quantum algorithms for element distinctness)
Dans Proceedings of the 16th IEEE Annual Conference on Computational Complexity, pages 131-137, 2001.
[arXiv:quant-ph/0007016]
- 22
-
Dong Pyo Chi, Jeong San Kim et Soojoon Lee
Notes sur le problème du sous-groupe caché sur certains groupes de produit semi-direct. (Notes on the hidden subgroup problem on some semi-direct product groups)
Phys. Lett. A 359(2):114-116, 2006.
[arXiv:quant-ph/0604172]
- 23
-
A. M. Childs, L. J. Schulman et U. V. Vazirani
Algorithmes quantiques pour des structures non linéaires cachées. (Quantum algorithms for hidden nonlinear structures)
Dans Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pages 395-404, 2007.
[arXiv:0705.2784]
- 24
-
Andrew Childs et Troy Lee
Bornes inférieures optimales pour l'adversaire quantique dans la recherche ordonnée. (Optimal quantum adversary lower bounds for ordered search)
Proceedings of ICALP 2008
[arXiv:0708.3396]
- 25
-
Andrew M. Childs
Traitement de l'information quantique en temps continu. (Quantum information processing in continuous time)
Thèse de doctorat, MIT, 2004.
- 26
-
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann et
Daniel A. Spielman
Accélération algorithmique exponentielle par marche quantique. (Exponential algorithmic speedup by quantum walk)
Dans Proceedings of the 35th ACM Symposium on Theory of Computing, pages 59-68, 2003.
[arXiv:quant-ph/0209131]
- 27
-
Andrew M. Childs, Richard Cleve, Stephen P. Jordan et David Yonge-Mallo
Algorithme quantique à requête discrète pour les arbres NAND. (Discrete-query quantum algorithm for NAND trees)
Theory of Computing, 5:119-123, 2009.
[arXiv:quant-ph/0702160]
- 28
-
Andrew M. Childs et Wim van Dam
Algorithme quantique pour un problème de décalage caché généralisé. (Quantum algorithm for a generalized hidden shift problem)
Dans Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 1225-1232, 2007.
[arXiv:quant-ph/0507190]
- 29
-
Richard Cleve, Dmitry Gavinsky et David L. Yonge-Mallo
Algorithmes quantiques pour évaluer les arbres MIN-MAX. (Quantum algorithms for evaluating MIN-MAX trees)
Dans Theory of Quantum Computation, Communication, and Cryptography, pages 11-15,
Springer, 2008. (LNCS Vol. 5106)
[arXiv:0710.5794]
- 30
-
J. Niel de Beaudrap, Richard Cleve et John Watrous
Séparations nettes de complexité de requête quantique par rapport à la classique. (Sharp quantum versus classical query complexity separations)
Algorithmica, 34(4):449-461, 2002.
[arXiv:quant-ph/0011065v2]
- 31
-
Thomas Decker, Jan Draisma et Pawel Wocjan
Algorithme quantique pour identifier des polynômes cachés. (Quantum algorithm for identifying hidden polynomials)
Quantum Information and Computation, 9(3):215-230, 2009.
[arXiv:0706.1219]
- 32
-
David Deutsch
Théorie quantique, le principe de Church-Turing et l'ordinateur quantique universel. (Quantum theory, the Church-Turing principle, and the universal quantum computer)
Proceedings of the Royal Society of London Series A, 400:97-117, 1985.
- 33
-
David Deutsch et Richard Jozsa
Solution rapide de problèmes par calcul quantique. (Rapid solution of problems by quantum computation)
Proceedings of the Royal Society of London Series A, 493:553-558, 1992.
- 34
-
Christoph Dürr, Mark Heiligman, Peter Høyer et Mehdi Mhalla
Complexité de requête quantique de certains problèmes de graphes. (Quantum query complexity of some graph problems)
SIAM Journal on Computing, 35(6):1310-1328, 2006.
[arXiv:quant-ph/0401091]
- 35
-
Christoph Dürr et Peter Høyer
Un algorithme quantique pour trouver le minimum. (A quantum algorithm for finding the minimum)
arXiv:quant-ph/9607014, 1996.
- 36
-
Christoph Dürr, Mehdi Mhalla et Yaohui Lei
Complexité de requête quantique de la connectivité des graphes. (Quantum query complexity of graph connectivity)
arXiv:quant-ph/0303169, 2003.
- 37
-
Mark Ettinger, Peter Høyer et Emanuel Knill
La complexité de requête quantique du problème du sous-groupe caché est polynomiale. (The quantum query complexity of the hidden subgroup problem is polynomial)
Information Processing Letters, 91(1):43-48, 2004.
[arXiv:quant-ph/0401083]
- 38
-
Edward Farhi, Jeffrey Goldstone et Sam Gutmann
Un algorithme quantique pour l'arbre NAND Hamiltonien. (A quantum algorithm for the Hamiltonian NAND tree)
Theory of Computing 4:169-190, 2008.
[arXiv:quant-ph/0702144]
- 39
-
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et Michael Sipser
Algorithmes quantiques invariants pour l'insertion dans une liste ordonnée. (Invariant quantum algorithms for insertion into an ordered list)
arXiv:quant-ph/9901059, 1999.
- 40
-
Richard P. Feynman
Simulation de la physique avec des ordinateurs. (Simulating physics with computers)
International Journal of Theoretical Physics, 21(6/7):467-488, 1982.
- 41
-
Michael Freedman, Alexei Kitaev et Zhenghan Wang
Simulation de théories de champs topologiques par des ordinateurs quantiques. (Simulation of topological field theories by quantum computers)
Communications in Mathematical Physics, 227:587-603, 2002.
- 42
-
Michael Freedman, Michael Larsen et Zhenghan Wang
Un foncteur modulaire qui est universel pour le calcul quantique. (A modular functor which is universal for quantum computation)
Comm. Math. Phys. 227(3):605-622, 2002.
[arXiv:quant-ph/0001108]
- 43
-
K. Friedl, G. Ivanyos, F. Magniez, M. Santha et P. Sen
Traduction cachée et coset traduisant en informatique quantique. (Hidden translation and translating coset in quantum computing)
SIAM Journal on Computing Vol. 43, pp. 1-24, 2014.
Apparu plus tôt dans Proceedings of the 35th ACM Symposium on Theory of Computing, pages 1-9, 2003.
[arXiv:quant-ph/0211091]
- 44
-
D. Gavinsky
Solution quantique au problème du sous-groupe caché pour les groupes poly-near-Hamiltoniens. (Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian-groups)
Quantum Information and Computation, 4:229-235, 2004.
- 45
-
Joseph Geraci
Une nouvelle connexion entre circuits quantiques, graphes et la fonction de partition d'Ising. (A new connection between quantum circuits, graphs and the Ising partition function)
Quantum Information Processing, 7(5):227-242, 2008.
[arXiv:0801.4833]
- 46
-
Joseph Geraci et Frank Van Bussel
Un théorème sur l'évaluation quantique des énumérateurs de poids pour une certaine classe de codes cycliques avec une note sur les cosets cyclotomiques. (A theorem on the quantum evaluation of weight enumerators for a certain class of cyclic Codes with a note on cyclotomic cosets)
arXiv:cs/0703129, 2007.
- 47
-
Joseph Geraci et Daniel A. Lidar
Sur l'évaluation exacte de certaines instances de la fonction de partition de Potts par des ordinateurs quantiques. (On the exact evaluation of certain instances of the Potts partition function by quantum computers)
Comm. Math. Phys. Vol. 279, pg. 735, 2008.
[arXiv:quant-ph/0703023]
- 48
-
Lov K. Grover
La mécanique quantique aide à chercher une aiguille dans une botte de foin. (Quantum mechanics helps in searching for a needle in a haystack)
Physical Review Letters, 79(2):325-328, 1997.
[arXiv:quant-ph/9605043]
- 49
-
Sean Hallgren
Algorithmes quantiques en temps polynomial pour l'équation de Pell et le problème de l'idéal principal. (Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem)
Dans Proceedings of the 34th ACM Symposium on Theory of Computing, 2002.
- 50
-
Sean Hallgren
Algorithmes quantiques rapides pour le calcul du groupe unitaire et du groupe de classes d'un corps numérique. (Fast quantum algorithms for computing the unit group and class group of a number field)
Dans Proceedings of the 37th ACM Symposium on Theory of Computing, 2005.
- 51
-
Sean Hallgren, Alexander Russell et Amnon Ta-Shma
Reconstruction de sous-groupes normaux et calcul quantique utilisant des représentations de groupes. (Normal subgroup reconstruction and quantum computation using group representations)
SIAM Journal on Computing, 32(4):916-934, 2003.
- 52
-
Mark Heiligman
Algorithmes quantiques pour les chemins de poids minimum et les arbres couvrants dans des graphes complets. (Quantum algorithms for lowest weight paths and spanning trees in complete graphs)
arXiv:quant-ph/0303131, 2003.
- 53
-
Yoshifumi Inui et François Le Gall
Algorithmes quantiques efficaces pour le problème du sous-groupe caché sur une classe de groupes de produit semi-direct. (Efficient quantum algorithms for the hidden subgroup problem over a class of semi-direct product groups)
Quantum Information and Computation, 7(5/6):559-570, 2007.
[arXiv:quant-ph/0412033]
- 54
-
Yuki Kelly Itakura
Algorithme quantique pour le test de commutativité d'un ensemble de matrices. (Quantum algorithm for commutativity testing of a matrix set)
Thèse de maîtrise, Université de Waterloo, 2005.
[arXiv:quant-ph/0509206]
- 55
-
Gábor Ivanyos, Frédéric Magniez et Miklos Santha
Algorithmes quantiques efficaces pour certaines instances du problème du sous-groupe caché non abélien. (Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem)
Dans Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, pages 263-270, 2001.
[arXiv:quant-ph/0102014]
- 56
-
Gábor Ivanyos, Luc Sanselme et Miklos Santha
Un algorithme quantique efficace pour le problème du sous-groupe caché dans des groupes extraspéciaux. (An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups)
Dans Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science, 2007.
[arXiv:quant-ph/0701235]
- 57
-
Gábor Ivanyos, Luc Sanselme et Miklos Santha
Un algorithme quantique efficace pour le problème du sous-groupe caché dans des groupes nil-2. (An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups)
Dans LATIN 2008: Theoretical Informatics, pg. 759-771, Springer (LNCS 4957).
[arXiv:0707.1260]
- 58
-
Dominik Janzing et Pawel Wocjan
Problèmes BQP-complets concernant les propriétés de mélange des marches aléatoires classiques sur des graphes clairsemés. (BQP-complete problems concerning mixing properties of classical random walks on sparse graphs)
arXiv:quant-ph/0610235, 2006.
- 59
-
Dominik Janzing et Pawel Wocjan
Un problème de réécriture de chaînes promiseBQP-complet. (A promiseBQP-complete string rewriting problem)
Quantum Information and Computation, 10(3/4):234-257, 2010.
[arXiv:0705.1180]
- 60
-
Dominik Janzing et Pawel Wocjan
Un problème de matrice promiseBQP-complet simple. (A simple promiseBQP-complete matrix problem)
Theory of Computing, 3:61-79, 2007.
[arXiv:quant-ph/0606229]
- 61
-
Stephen P. Jordan
Algorithme quantique rapide pour l'estimation du gradient numérique. (Fast quantum algorithm for numerical gradient estimation)
Physical Review Letters, 95:050501, 2005.
[arXiv:quant-ph/0405146]
- 62
-
Stephen P. Jordan
Quantum Computation Beyond the Circuit Model. (Quantum Computation Beyond the Circuit Model)
Thèse de doctorat, Massachusetts Institute of Technology, 2008.
[arXiv:0809.2307]
- 63
-
Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni et Alán
Aspuru-Guzik
Algorithmes quantiques pour la simulation de la dynamique chimique. (Quantum algorithms for the simulation of chemical dynamics)
Proc. Natl. Acad. Sci. Vol. 105, pg. 18681, 2008.
[arXiv:0801.2986]
- 64
-
Kiran S. Kedlaya
Calcul quantique des fonctions zêta des courbes. (Quantum computation of zeta functions of curves)
Computational Complexity, 15:1-19, 2006.
[arXiv:math/0411623]
- 65
-
E. Knill et R. Laflamme
Calcul quantique et énumérateurs de poids signés quadratiquement. (Quantum computation and quadratically signed weight enumerators)
Information Processing Letters, 79(4):173-179, 2001.
[arXiv:quant-ph/9909094]
- 66
-
Greg Kuperberg
Un algorithme quantique en temps subexponentiel pour le problème du sous-groupe caché diédral. (A subexponential-time quantum algorithm for the dihedral hidden subgroup problem)
SIAM Journal on Computing, 35(1):170-188, 2005.
[arXiv:quant-ph/0302112]
- 67
-
Daniel A. Lidar
Sur la complexité computationnelle quantique de la fonction de partition du verre de spin Ising et des invariants de nœuds. (On the quantum computational complexity of the Ising spin glass partition function and of knot invariants)
New Journal of Physics Vol. 6, pg. 167, 2004.
[arXiv:quant-ph/0309064]
- 68
-
Daniel A. Lidar et Haobin Wang
Calcul du constant de taux thermique avec un gain exponentiel sur un ordinateur quantique. (Calculating the thermal rate constant with exponential speedup on a quantum computer)
Physical Review E, 59(2):2429-2438, 1999.
[arXiv:quant-ph/9807009]
- 69
-
Chris Lomont
Le problème du sous-groupe caché - revue et problèmes ouverts. (The hidden subgroup problem - review and open problems)
arXiv:quant-ph/0411037, 2004.
- 70
-
Frédéric Magniez, Miklos Santha et Mario Szegedy
Algorithmes quantiques pour le problème du triangle. (Quantum algorithms for the triangle problem)
SIAM Journal on Computing, 37(2):413-424, 2007.
[arXiv:quant-ph/0310134]
- 71
-
Carlos Magno, M. Cosme et Renato Portugal
Algorithme quantique pour le problème du sous-groupe caché sur une classe de groupes de produit semi-direct. (Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups)
arXiv:quant-ph/0703223, 2007.
- 72
-
Cristopher Moore, Daniel Rockmore, Alexander Russell et Leonard Schulman
Le pouvoir de la sélection de base dans l'échantillonnage de Fourier : le problème du sous-groupe caché dans les groupes affines. (The power of basis selection in Fourier sampling: the hidden subgroup problem in affine groups)
Dans Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pages 1113-1122, 2004.
[arXiv:quant-ph/0211124]
- 73
-
M. Mosca
Recherche quantique, comptage et amplification d'amplitude par analyse d'eigenvecteur. (Quantum searching, counting, and amplitude amplification by eigenvector analysis)
Dans R. Freivalds, éditeur, Proceedings of International Workshop on Randomized Algorithms, pages 90-100, 1998.
- 74
-
Michele Mosca
Algorithmes d'ordinateur quantique. (Quantum Computer Algorithms)
Thèse de doctorat, Université d'Oxford, 1999.
- 75
-
Ashwin Nayak et Felix Wu
La complexité de requête quantique pour l'approximation de la médiane et des statistiques connexes. (The quantum query complexity of approximating the median and related statistics)
Dans Proceedings of 31st ACM Symposium on the Theory of Computing, 1999.
[arXiv:quant-ph/9804066]
- 76
-
Michael A. Nielsen et Isaac L. Chuang.
Calcul quantique et information quantique. (Quantum Computation and Quantum Information)
Cambridge University Press, Cambridge, UK, 2000.
- 77
-
Erich Novak
Complexité quantique de l'intégration. (Quantum complexity of integration)
Journal of Complexity, 17:2-16, 2001.
[arXiv:quant-ph/0008124]
- 78
-
Oded Regev
Calcul quantique et problèmes de réseau. (Quantum computation and lattice problems)
Dans Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002.
[arXiv:cs/0304005]
- 79
-
Oded Regev
Un algorithme en temps subexponentiel pour le problème du sous-groupe caché diédral avec espace polynomial. (A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space)
arXiv:quant-ph/0406151, 2004.
- 80
-
Ben Reichardt et Robert Špalek
Algorithme quantique basé sur le programme de span pour évaluer des formules. (Span-program-based quantum algorithm for evaluating formulas)
Proceedings of STOC 2008
[arXiv:0710.2630]
- 81
-
Martin Roetteler et Thomas Beth
Solution en temps polynomial au problème du sous-groupe caché pour une classe de groupes non abéliens. (Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups)
arXiv:quant-ph/9812070, 1998.
- 82
-
Peter W. Shor
Algorithmes en temps polynomial pour la factorisation des nombres premiers et les logarithmes discrets sur un ordinateur quantique. (Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer)
SIAM Journal on Computing, 26(5):1484-1509, 1997.
[arXiv:quant-ph/9508027]
- 83
-
Peter W. Shor et Stephen P. Jordan
L'estimation des polynômes de Jones est un problème complet pour un qubit propre. (Estimating Jones polynomials is a complete problem for one clean qubit)
Quantum Information and Computation, 8(8/9):681-714, 2008.
[arXiv:0707.2831]
- 84
-
R. D. Somma, S. Boixo et H. Barnum
Recuit simulé quantique. (Quantum simulated annealing)
arXiv:0712.1008, 2007.
- 85
-
M. Szegedy
Accélération quantique des algorithmes basés sur les chaînes de Markov. (Quantum speed-up of Markov chain based algorithms)
Dans Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pg. 32, 2004.
- 86
-
Wim van Dam
Algorithmes quantiques pour peser des matrices et des résidus quadratiques. (Quantum algorithms for weighing matrices and quadratic residues)
Algorithmica, 34(4):413-428, 2002.
[arXiv:quant-ph/0008059]
- 87
-
Wim van Dam
Calcul quantique et zéros des fonctions zêta. (Quantum computing and zeros of zeta functions)
arXiv:quant-ph/0405081, 2004.
- 88
-
Wim van Dam et Sean Hallgren
Algorithmes quantiques efficaces pour des problèmes de caractères quadratiques décalés. (Efficient quantum algorithms for shifted quadratic character problems)
arXiv:quant-ph/0011067, 2000.
- 89
-
Wim van Dam, Sean Hallgren et Lawrence Ip
Algorithmes quantiques pour certains problèmes de décalage caché. (Quantum algorithms for some hidden shift problems)
SIAM Journal on Computing, 36(3):763-778, 2006.
[arXiv:quant-h/0211140]
- 90
-
Wim van Dam et Gadiel Seroussi
Algorithmes quantiques efficaces pour estimer les sommes de Gauss. (Efficient quantum algorithms for estimating Gauss sums)
arXiv:quant-ph/0207131, 2002.
- 91
-
John Watrous
Algorithmes quantiques pour des groupes résolvables. (Quantum algorithms for solvable groups)
Dans Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 60-67, 2001.
[arXiv:quant-ph/0011023]
- 92
-
Stephen Wiesner
Simulations de systèmes quantiques à plusieurs corps par un ordinateur quantique. (Simulations of many-body quantum systems by a quantum computer)
arXiv:quant-ph/9603028, 1996.
- 93
-
Pawel Wocjan et Jon Yard
Le polynôme de Jones : algorithmes quantiques et applications dans la théorie de la complexité quantique. (The Jones polynomial: quantum algorithms and applications in quantum complexity theory)
Quantum Information and Computation 8(1/2):147-180, 2008.
[arXiv:quant-ph/0603069]
- 94
-
Andrew Yao
Sur le calcul des minima de formes quadratiques. (On computing the minima of quadratic forms)
Dans Proceedings of the 7th ACM Symposium on Theory of Computing, pages 23-26, 1975.
- 95
-
Christof Zalka
Simulation efficace de systèmes quantiques par des ordinateurs quantiques. (Efficient simulation of quantum systems by quantum computers)
Proceedings of the Royal Society of London Series A, 454:313, 1996.
[arXiv:quant-ph/9603026]
- 96
-
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et Michael Sipser
Calcul quantique par évolution adiabatique. (Quantum computation by adiabatic evolution)
arXiv:quant-ph/0001106, 2000.
- 97
-
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd et Oded Regev
Le calcul quantique adiabatique est équivalent au calcul quantique standard. (Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation)
SIAM Journal on Computing, 37(1):166-194, 2007.
[arXiv:quant-ph/0405098]
- 98
-
Jérémy Roland et Nicolas J. Cerf
Recherche quantique par évolution adiabatique locale. (Quantum search by local adiabatic evolution)
Physical Review A, 65(4):042308, 2002.
[arXiv:quant-ph/0107015]
- 99
-
L.-A. Wu, M.S. Byrd et D. A. Lidar
Simulation en temps polynomial de modèles de couplage sur un ordinateur quantique. (Polynomial-Time Simulation of Pairing Models on a Quantum Computer)
Physical Review Letters, 89(6):057904, 2002.
[arXiv:quant-ph/0108110]
- 100
-
Eli Biham, Ofer Biham, David Biron, Markus Grassl et Daniel Lidar
L'algorithme de recherche quantique de Grover pour une distribution d'amplitude initiale arbitraire. (Grover's quantum search algorithm for an arbitrary initial amplitude distribution)
Physical Review A, 60(4):2742, 1999.
[arXiv:quant-ph/9807027 et arXiv:quant-ph/0010077]
- 101
-
Andrew Childs, Shelby Kimmel et Robin Kothari
La complexité de requête quantique des formules à lecture multiple. (The quantum query complexity of read-many formulas)
Dans Proceedings of ESA 2012, pg. 337-348, Springer. (LNCS 7501)
[arXiv:1112.0548]
- 102
-
Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love et Martin Head-Gordon
Calcul quantique simulé des énergies moléculaires. (Simulated quantum computation of molecular energies)
Science, 309(5741):1704-1707, 2005.
[arXiv:quant-ph/0604193]
- 103
-
A. M. Childs, A. J. Landahl et P. A. Parrilo
Algorithmes quantiques pour le problème de recherche ordonnée via la programmation semi-définie. (Quantum algorithms for the ordered search problem via semidefinite programming)
Physical Review A, 75 032335, 2007.
[arXiv:quant-ph/0608161]
- 104
-
Aram W. Harrow, Avinatan Hassidim et Seth Lloyd
Algorithme quantique pour résoudre des systèmes d'équations linéaires. (Quantum algorithm for solving linear systems of equations)
Physical Review Letters 15(103):150502, 2009.
[arXiv:0811.3171]
- 105
-
Martin Roetteler
Algorithmes quantiques pour des fonctions booléennes hautement non linéaires. (Quantum algorithms for highly non-linear Boolean functions)
Proceedings of SODA 2010
[arXiv:0811.3208]
- 106
-
Stephen P. Jordan
Algorithmes quantiques rapides pour approximer les représentations irréductibles des groupes. (Fast quantum algorithms for approximating the irreducible representations of groups)
arXiv:0811.0562, 2008.
- 107
-
Tim Byrnes et Yoshihisa Yamamoto
Simulation des théories de jauge sur un ordinateur quantique. (Simulating lattice gauge theories on a quantum computer)
Physical Review A, 73, 022328, 2006.
[arXiv:quant-ph/0510027]
- 108
-
D. Simon
Sur le pouvoir du calcul quantique. (On the Power of Quantum Computation)
Dans Proceedings of the 35th Symposium on Foundations of Computer Science, pg. 116-123, 1994.
- 109
-
John Proos et Christof Zalka
L'algorithme quantique de logarithme discret de Shor pour les courbes elliptiques. (Shor's discrete logarithm quantum algorithm for elliptic curves)
Quantum Information and Computation, Vol. 3, No. 4, pg.317-344, 2003.
[arXiv:quant-ph/0301141]
- 110
-
Yi-Kai Liu
Algorithmes quantiques utilisant la transformation de courbe. (Quantum algorithms using the curvelet transform)
Proceedings of STOC 2009, pg. 391-400.
[arXiv:0810.4968]
- 111
-
Wim van Dam et Igor Shparlinski
Algorithmes classiques et quantiques pour les congruences exponentielles. (Classical and quantum algorithms for exponential congruences)
Proceedings of TQC 2008, pg. 1-10.
[arXiv:0804.1109]
- 112
-
Itai Arad et Zeph Landau
Calcul quantique et évaluation des réseaux de tenseurs. (Quantum computation and the evaluation of tensor networks)
SIAM Journal on Computing, 39(7):3089-3121, 2010.
[arXiv:0805.0040]
- 113
-
M. Van den Nest, W. Dür, R. Raussendorf et H. J. Briegel
Algorithmes quantiques pour les modèles de spin et ensembles de portes simulables pour le calcul quantique. (Quantum algorithms for spin models and simulable gate sets for quantum computation)
Physical Review A, 80:052334, 2009.
[arXiv:0805.1214]
- 114
-
Silvano Garnerone, Annalisa Marzuoli et Mario Rasetti
Traitement quantique efficace des invariants topologiques des 3-variétés. (Efficient quantum processing of 3-manifold topological invariants)
Advances in Theoretical and Mathematical Physics, 13(6):1601-1652, 2009.
[arXiv:quant-ph/0703037]
- 115
-
Louis H. Kauffman et Samuel J. Lomonaco Jr.
Réseaux de spin q-déformés, polynômes de nœuds et calcul quantique topologique anyonique. (q-deformed spin networks, knot polynomials and anyonic topological quantum computation)
Journal of Knot Theory, Vol. 16, No. 3, pg. 267-332, 2007.
[arXiv:quant-ph/0606114]
- 116
-
Arthur Schmidt et Ulrich Vollmer
Algorithme quantique en temps polynomial pour le calcul du groupe unitaire d'un corps numérique. (Polynomial time quantum algorithm for the computation of the unit group of a number field)
Dans Proceedings of the 37th Symposium on the Theory of Computing, pg. 475-480, 2005.
- 117
-
Sergey Bravyi, Aram Harrow et Avinatan Hassidim
Algorithmes quantiques pour tester les propriétés des distributions. (Quantum algorithms for testing properties of distributions)
IEEE Transactions on Information Theory 57(6):3971-3981, 2011.
[arXiv:0907.3920]
- 118
-
Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi et Joseph P. Brennan
Traitement quantique efficace des idéaux dans les anneaux finis. (Efficient quantum processing of ideals in finite rings)
arXiv:0908.0022, 2009.
- 119
-
V. Arvind, Bireswar Das et Partha Mukhopadhyay
La complexité des problèmes d'anneau en boîte noire. (The complexity of black-box ring problems)
Dans Proceedings of COCCOON 2006, pg 126-145.
- 120
-
V. Arvind et Partha Mukhopadhyay
Complexité de requête quantique des tests d'identité multilinéaires. (Quantum query complexity of multilinear identity testing)
Dans Proceedings of STACS 2009, pg. 87-98.
- 121
-
David Poulin et Pawel Wocjan
Échantillonnage à partir de l'état de Gibbs quantique thermique et évaluation des fonctions de partition avec un ordinateur quantique. (Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer)
Physical Review Letters 103:220502, 2009.
[arXiv:0905.2199]
- 122
-
Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe et Daniel Nagaj
Accélération quantique pour l'approximation des fonctions de partition. (Quantum speed-up for approximating partition functions)
Physical Review A 80:022340, 2009.
[arXiv:0811.0596]
- 123
-
Ashley Montanaro
Recherche quantique avec conseils. (Quantum search with advice)
Dans Proceedings of the 5th conference on Theory of quantum computation, communication, and cryptography (TQC 2010)
[arXiv:0908.3066]
- 124
-
Laszlo Babai, Robert Beals et Akos Seress
Théorie en temps polynomial des groupes de matrices. (Polynomial-time theory of matrix groups)
Dans Proceedings of STOC 2009, pg. 55-64.
- 125
-
Peter Shor
Algorithmes pour le calcul quantique : logarithmes discrets et factorisation. (Algorithms for Quantum Computation: Discrete Logarithms and Factoring)
Dans Proceedings of FOCS 1994, pg. 124-134.
- 126
-
Aaron Denney, Cristopher Moore et Alex Russell
Recherche de sous-groupes stabilisateurs conjugués dans PSL(2;q) et groupes connexes. (Finding conjugate stabilizer subgroups in PSL(2;q) and related groups)
Quantum Information and Computation 10(3):282-291, 2010.
[arXiv:0809.2445]
- 127
-
Kevin K. H. Cheung et Michele Mosca
Décomposition des groupes abéliens finis. (Decomposing finite Abelian groups)
Quantum Information and Computation 1(2):26-32, 2001.
[arXiv:cs/0101004]
- 128
-
François Le Gall
Un algorithme quantique efficace pour certaines instances du problème d'isomorphisme de groupe. (An efficient quantum algorithm for some instances of the group isomorphism problem)
Dans Proceedings of STACS 2010.
[arXiv:1001.0608]
- 129
-
Gorjan Alagic, Stephen Jordan, Robert Koenig et Ben Reichardt
L'approximation des invariants de 3-variétés de Turaev-Viro est universelle pour le calcul quantique. (Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation)
Physical Review A 82, 040302(R), 2010.
[arXiv:1003.0923]
- 130
-
Martin Rötteler
Algorithmes quantiques pour résoudre le problème de décalage caché pour les quadratiques et pour les fonctions de grande norme de Gowers. (Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm)
Dans Proceedings of MFCS 2009, pg 663-674.
[arXiv:0911.4724]
- 131
-
Arthur Schmidt
Algorithmes quantiques pour des fonctions à plusieurs à une pour résoudre le problème du régulateur et le problème de l'idéal principal. (Quantum Algorithms for many-to-one Functions to Solve the Regulator and the Principal Ideal Problem)
arXiv:0912.4807, 2009.
- 132
-
K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin et F. Verstraete
Échantillonnage de Metropolis quantique. (Quantum Metropolis Sampling)
Nature, Vol. 471, pg. 87-90, 2011.
[arXiv:0911.3635]
- 133
-
Andris Ambainis
Algorithmes de recherche quantique. (Quantum Search Algorithms)
SIGACT News, 35 (2):22-35, 2004.
[arXiv:quant-ph/0504012]
- 134
-
Nicolas J. Cerf, Lov K. Grover et Colin P. Williams
Recherche quantique imbriquée et problèmes NP-difficiles. (Nested quantum search and NP-hard problems)
Applicable Algebra in Engineering, Communication and Computing, 10 (4-5):311-338, 2000.
- 135
-
Mario Szegedy
Spectres des marches quantifiées et une règle \( \sqrt{\delta \epsilon} \).
arXiv:quant-ph/0401053, 2004.
- 136
-
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond et Junichi Teruyama
Problèmes de pièces contrefaites quantiques. (Quantum Counterfeit Coin Problems)
Dans Proceedings of 21st International Symposium on Algorithms and Computation (ISAAC2010), LNCS 6506, pp.73-84, 2010.
[arXiv:1009.0416]
- 137
-
Barbara Terhal et John Smolin
Interrogation quantique unique d'une base de données. (Single quantum querying of a database)
Physical Review A 58:1822, 1998.
[arXiv:quant-ph/9705041]
- 138
-
Andris Ambainis
Amplification d'amplitude à temps variable et un algorithme quantique plus rapide pour résoudre des systèmes d'équations linéaires. (Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations)
arXiv:1010.4458, 2010.
- 139
-
Frédéric Magniez et Ashwin Nayak
Complexité quantique du test de commutativité des groupes. (Quantum complexity of testing group commutativity)
Dans Proceedings of 32nd International Colloquium on Automata, Languages and Programming. LNCS 3580, pg. 1312-1324, 2005.
[arXiv:quant-ph/0506265]
- 140
-
Andrew Childs et Robin Kothari
Complexité de requête quantique des propriétés des graphes fermés par mineur. (Quantum query complexity of minor-closed graph properties)
Dans Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), pg. 661-672
[arXiv:1011.1443]
- 141
-
Frédéric Magniez, Ashwin Nayak, Jérémy Roland et Miklos Santha
Recherche via marche quantique. (Search via quantum walk)
Dans Proceedings STOC 2007, pg. 575-584.
[arXiv:quant-ph/0608026]
- 142
-
Dmitry Gavinsky, Martin Roetteler et Jérémy Roland
Algorithme quantique pour le problème de décalage caché booléen. (Quantum algorithm for the Boolean hidden shift problem)
Dans Proceedings of the 17th annual international conference on Computing and combinatorics (COCOON '11), 2011.
[arXiv:1103.3017]
- 143
-
Mark Ettinger et Peter Høyer
Sur les algorithmes quantiques pour les sous-groupes cachés non commutatifs. (On quantum algorithms for noncommutative hidden subgroups)
Advances in Applied Mathematics, Vol. 25, No. 3, pg. 239-251, 2000.
[arXiv:quant-ph/9807029]
- 144
-
Andris Ambainis, Andrew Childs et Yi-Kai Liu
Test de propriété quantique pour les graphes de degré borné. (Quantum property testing for bounded-degree graphs)
Dans Proceedings of RANDOM '11: Lecture Notes in Computer Science 6845, pp. 365-376, 2011.
[arXiv:1012.3174]
- 145
-
G. Ortiz, J.E. Gubernatis, E. Knill et R. Laflamme
Algorithmes quantiques pour les simulations fermioniques. (Quantum algorithms for Fermionic simulations)
Physical Review A 64: 022319, 2001.
[arXiv:cond-mat/0012334]
- 146
-
Ashley Montanaro
La complexité de requête quantique de l'apprentissage des polynômes multilinéaires. (The quantum query complexity of learning multilinear polynomials)
Information Processing Letters, 112(11):438-442, 2012.
[arXiv:1105.3310]
- 147
-
Tad Hogg
Recherches hautement structurées avec des ordinateurs quantiques. (Highly structured searches with quantum computers)
Physical Review Letters 80: 2473, 1998.
- 148
-
Markus Hunziker et David A. Meyer
Algorithmes quantiques pour des problèmes de recherche hautement structurés. (Quantum algorithms for highly structured search problems)
Quantum Information Processing, Vol. 1, No. 3, pg. 321-341, 2002.
- 149
-
Ben Reichardt
Programmes de span et complexité de requête quantique : La borne d'adversaire générale est presque serrée pour chaque fonction booléenne. (Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function)
Dans Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS '09), pg. 544-551, 2009.
[arXiv:0904.2759]
- 150
-
Aleksandrs Belovs
Algorithme quantique basé sur les programmes de span pour le problème de rang. (Span-program-based quantum algorithm for the rank problem)
arXiv:1103.0842, 2011.
- 151
-
Sebastian Dörn et Thomas Thierauf
La complexité de requête quantique du déterminant. (The quantum query complexity of the determinant)
Information Processing Letters Vol. 109, No. 6, pg. 305-328, 2009.
- 152
-
Aleksandrs Belovs
Programmes de span pour des fonctions avec des certificats de taille constante. (Span programs for functions with constant-sized 1-certificates)
Dans Proceedings of STOC 2012, pg. 77-84.
[arXiv:1105.4024]
- 153
-
Troy Lee, Frédéric Magniez et Mikos Santha
Un algorithme de requête quantique basé sur un graphe d'apprentissage pour trouver des sous-graphes de taille constante. (A learning graph based quantum query algorithm for finding constant-size subgraphs)
Chicago Journal of Theoretical Computer Science, Vol. 2012, Article 10, 2012.
[arXiv:1109.5135]
- 154
-
Aleksandrs Belovs et Troy Lee
Algorithme quantique pour la k-distinctesse avec connaissance préalable sur l'entrée. (Quantum algorithm for k-distinctness with prior knowledge on the input)
arXiv:1108.3022, 2011.
- 155
-
François Le Gall
Algorithmes quantiques améliorés sensibles à la sortie pour la multiplication de matrices booléennes. (Improved output-sensitive quantum algorithms for Boolean matrix multiplication)
Dans Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12), 2012.
- 156
-
Dominic Berry
Algorithmes quantiques pour résoudre des équations différentielles linéaires. (Quantum algorithms for solving linear differential equations)
J. Phys. A: Math. Theor.47, 105301, 2014.
[arXiv:1010.2745].
- 157
-
Virginia Vassilevska Williams et Ryan Williams
Équivalences subcubiques entre les problèmes de chemin, de matrice et de triangle. (Subcubic equivalences between path, matrix, and triangle problems)
Dans 51st IEEE Symposium on Foundations of Computer Science (FOCS '10) pg. 645 - 654, 2010.
- 158
-
Ben W. Reichardt
Réflexions pour les algorithmes de requête quantique. (Reflections for quantum query algorithms)
Dans Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pg. 560-569, 2011.
[arXiv:1005.1601]
- 159
-
Ben W. Reichardt
Algorithme quantique basé sur les programmes de span pour évaluer des formules déséquilibrées. (Span-program-based quantum algorithm for evaluating unbalanced formulas)
arXiv:0907.1622, 2009.
- 160
-
Ben W. Reichardt
Algorithme quantique plus rapide pour évaluer des arbres de jeu. (Faster quantum algorithm for evaluating game trees)
Dans Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pg. 546-559, 2011.
[arXiv:0907.1623]
- 161
-
Stacey Jeffery, Robin Kothari et Frédéric Magniez
Amélioration de la complexité de requête quantique de la multiplication de matrices booléennes en utilisant la collision de graphes. (Improving quantum query complexity of Boolean matrix multiplication using graph collision)
Dans Proceedings of ICALP 2012, pg. 522-532.
[arXiv:1112.5855]
- 162
-
Andrew M. Childs et Jason M. Eisenberg
Algorithmes quantiques pour la recherche de sous-ensembles. (Quantum algorithms for subset finding)
Quantum Information and Computation 5(7):593-604, 2005.
[arXiv:quant-ph/0311038]
- 163
-
Aleksandrs Belovs et Robert Špalek
Borne inférieure d'adversaire pour le problème k-sum. (Adversary lower bound for the k-sum problem)
Dans Proceedings of ITCS 2013, pg. 323-328.
[arXiv:1206.6528]
- 164
-
Bohua Zhan, Shelby Kimmel et Avinatan Hassidim
Accélérations quantiques super-polynomiales pour les arbres d'évaluation booléenne avec structure cachée. (Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure)
ITCS 2012: Proceedings of the 3rd Innovations in Theoretical Computer Science, ACM, pg. 249-265.
[arXiv:1101.0796]
- 165
-
Shelby Kimmel
Borne supérieure d'adversaire quantique. (Quantum adversary (upper) bound)
39th International Colloquium on Automata, Languages and Programming - ICALP 2012 Volume 7391, p. 557-568.
[arXiv:1101.0797]
- 166
-
Stephen Jordan, Keith Lee et John Preskill
Algorithmes quantiques pour les théories des champs quantiques. (Quantum algorithms for quantum field theories)
Science, Vol. 336, pg. 1130-1133, 2012.
[arXiv:1111.3633]
- 167
-
Andris Ambainis et Ashley Montanaro
Algorithmes quantiques pour la recherche avec des jokers et le test de groupe combinatoire. (Quantum algorithms for search with wildcards and combinatorial group testing)
arXiv:1210.1148, 2012.
- 168
-
Andris Ambainis et Robert Špalek
Algorithmes quantiques pour l'appariement et les flux de réseau. (Quantum algorithms for matching and network flows)
Dans Proceedings of STACS 2007, pg. 172-183.
[arXiv:quant-ph/0508205]
- 169
-
Nathan Wiebe, Daniel Braun et Seth Lloyd
Ajustement de données quantiques. (Quantum data-fitting)
Physical Review Letters 109, 050505, 2012.
[arXiv:1204.5242]
- 170
-
Andrew Childs et Nathan Wiebe
Simulation d'Hamiltonien utilisant des combinaisons linéaires d'opérations unitaires. (Hamiltonian simulation using linear combinations of unitary operations)
Quantum Information and Computation 12, 901-924, 2012.
[arXiv:1202.5822]
- 171
-
Stacey Jeffery, Robin Kothari et Frédéric Magniez
Marches quantiques imbriquées avec des structures de données quantiques. (Nested quantum walks with quantum data structures)
Dans Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pg. 1474-1485, 2013.
[arXiv:1210.1199]
- 172
-
Aleksandrs Belovs
Algorithme quantique basé sur un graphe d'apprentissage pour la k-distinctesse. (Learning-graph-based quantum algorithm for k-distinctness)
Dans Proceedings of STOC 2012, pg. 77-84.
[arXiv:1205.1534]
- 173
-
Andrew Childs, Stacey Jeffery, Robin Kothari et Frédéric Magniez
Une marche quantique efficace en temps pour la 3-distinctesse utilisant des mises à jour imbriquées. (A time-efficient quantum walk for 3-distinctness using nested updates)
arXiv:1302.7316, 2013.
- 174
-
Hari Krovi et Alexander Russell
Transformées de Fourier quantiques et complexité des invariants de lien pour les doubles quantiques de groupes finis. (Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups)
Commun. Math. Phys. 334, 743-777, 2015
[arXiv:1210.1550]
- 175
-
Troy Lee, Frédéric Magniez et Miklos Santha
Algorithmes quantiques améliorés pour la recherche de triangles et le test d'associativité. (Improved quantum query algorithms for triangle finding and associativity testing)
arXiv:1210.1014, 2012.
- 176
-
Silvano Garnerone, Paolo Zanardi et Daniel A. Lidar
Algorithme quantique adiabatique pour le classement des moteurs de recherche. (Adiabatic quantum algorithm for search engine ranking)
Physical Review Letters 108:230506, 2012.
- 177
-
R. D. Somma, S. Boixo, H. Barnum et E. Knill
Simulations quantiques de l'annealing classique. (Quantum simulations of classical annealing)
Physical Review Letters 101:130504, 2008.
[arXiv:0804.1571]
- 178
-
Daniel J. Bernstein, Stacey Jeffery, Tanja Lange et Alexander Meurer
Algorithmes quantiques pour le problème de la somme de sous-ensembles. (Quantum algorithms for the subset-sum problem)
from cr.yp.to.
- 179
-
Boris Altshuler, Hari Krovi et Jérémie Roland
La localisation d'Anderson jette des ombres sur l'optimisation quantique adiabatique. (Anderson localization casts clouds over adiabatic quantum optimization)
Proceedings of the National Academy of Sciences 107(28):12446-12450, 2010.
[arXiv:0912.0746]
- 180
-
Ben Reichardt
L'algorithme d'optimisation adiabatique quantique et les minima locaux. (The quantum adiabatic optimization algorithm and local minima)
Dans Proceedings of STOC 2004, pg. 502-510. [Erratum].
- 181
-
Edward Farhi, Jeffrey Goldstone et Sam Gutmann
Algorithmes d'évolution adiabatique quantique versus recuit simulé. (Quantum adiabatic evolution algorithms versus simulated annealing)
arXiv:quant-ph/0201031, 2002.
- 182
-
E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H. B. Meyer et P. Shor
Algorithmes adiabatiques quantiques, petits écarts et chemins différents. (Quantum adiabatic algorithms, small gaps, and different paths)
Quantum Information and Computation, 11(3/4):181-214, 2011.
[arXiv:0909.4766]
- 183
-
Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira et Barbara M. Terhal
La complexité des problèmes de Hamiltonien local stoquastique. (The Complexity of Stoquastic Local Hamiltonian Problems)
Quantum Information and Computation, 8(5):361-385, 2008.
[arXiv:quant-ph/0606140]
- 184
-
Rolando D. Somma et Sergio Boixo
Amplification de l'écart spectral. (Spectral gap amplification)
SIAM Journal on Computing, 42:593-610, 2013.
[arXiv:1110.2494]
- 185
-
Sabine Jansen, Mary-Beth Ruskai et Ruedi Seiler
Bornes pour l'approximation adiabatique avec des applications à la computation quantique. (Bounds for the adiabatic approximation with applications to quantum computation)
Journal of Mathematical Physics, 48:102111, 2007.
[arXiv:quant-ph/0603175]
- 186
-
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren et D. Preda
Un algorithme d'évolution adiabatique quantique appliqué à des instances aléatoires d'un problème NP-complet. (A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem)
Science, 292(5516):472-475, 2001.
[arXiv:quant-ph/0104129]
- 187
-
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et Daniel Nagaj
Comment faire échouer l'algorithme adiabatique quantique. (How to make the quantum adiabatic algorithm fail)
International Journal of Quantum Information, 6(3):503-516, 2008.
[arXiv:quant-ph/0512159]
- 188
-
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et Daniel Nagaj
Aléatoire non structuré, petits écarts et localisation. (Unstructured randomness, small gaps, and localization)
Quantum Information and Computation, 11(9/10):840-854, 2011.
[arXiv:1010.0009]
- 189
-
Edward Farhi, Jeffrey Goldstone et Sam Gutmann
Algorithmes d'évolution adiabatique quantique avec différents chemins. (Quantum adiabatic evolution algorithms with different paths)
arXiv:quant-ph/0208135, 2002.
- 190
-
Wim van Dam, Michele Mosca et Umesh Vazirani
Quelle est la puissance du calcul quantique adiabatique ? (How powerful is adiabatic quantum computation?)
Dans Proceedings of FOCS 2001, pg. 279-287.
arXiv:quant-ph/0206003 [Voir aussi ceci.]
- 191
-
E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young et F. Zamponi
La performance de l'algorithme adiabatique quantique sur des instances aléatoires de deux problèmes d'optimisation sur des hypergraphes réguliers. (The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs)
Physical Review A, 86:052334, 2012.
[arXiv:1208.3757]
- 192
-
Kristen L. Pudenz et Daniel A. Lidar
Apprentissage machine adiabatique quantique. (Quantum adiabatic machine learning)
Quantum Information Processing, 12:2027, 2013.
[arXiv:1109.0325]
- 193
-
Frank Gaitan et Lane Clark
Nombres de Ramsey et calcul quantique adiabatique. (Ramsey numbers and adiabatic quantum computing)
Physical Review Letters, 108:010501, 2012.
[arXiv:1103.1345]
- 194
-
Frank Gaitan et Lane Clark
Isomorphisme de graphes et calcul quantique adiabatique. (Graph isomorphism and adiabatic quantum computing)
Physical Review A, 89(2):022342, 2014.
[arXiv:1304.5773]
- 195
-
Hartmut Neven, Vasil S. Denchev, Geordie Rose et William G. Macready
Entraîner un classificateur binaire avec l'algorithme adiabatique quantique. (Training a binary classifier with the quantum adiabatic algorithm)
arXiv:0811.0416, 2008.
- 196
-
Robert Beals
Calcul quantique des transformations de Fourier sur des groupes symétriques. (Quantum computation of Fourier transforms over symmetric groups)
Dans Proceedings of STOC 1997, pg. 48-53.
- 197
-
Dave Bacon, Isaac L. Chuang et Aram W. Harrow
La transformation de Schur quantique : I. circuits efficaces pour les qudits. (The quantum Schur transform: I. efficient qudit circuits)
Dans Proceedings of SODA 2007, pg. 1235-1244.
[arXiv:quant-ph/0601001]
- 198
-
S. Morita et H. Nishimori
Fondation mathématique de l'annealing quantique. (Mathematical foundation of quantum annealing)
Journal of Mathematical Physics, 49(12):125210, 2008.
- 199
-
A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson et J. D. Doll
Recuit quantique : une nouvelle méthode pour minimiser des fonctions multidimensionnelles. (Quantum annealing: a new method for minimizing multidimensional functions)
Chemical Physics Letters, 219:343-348, 1994.
- 200
-
D. Gavinsky et T. Ito
Un algorithme de requête quantique pour le problème de collision de graphes. (A quantum query algorithm for the graph collision problem)
arXiv:1204.1527, 2012.
- 201
-
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Raitis Ozols et
Juris Smotrovs
Complexité de requête quantique paramétrée de la collision de graphes. (Parameterized quantum query complexity of graph collision)
arXiv:1305.1021, 2013.
- 202
-
Kevin C. Zatloukal
Algorithmes classiques et quantiques pour tester l'équivalence des extensions de groupes. (Classical and quantum algorithms for testing equivalence of group extensions)
arXiv:1305.1327, 2013.
- 203
-
Andrew Childs et Gábor Ivanyos
Calcul quantique des logarithmes discrets dans des semi-groupes. (Quantum computation of discrete logarithms in semigroups)
arXiv:1310.6238, 2013.
- 204
-
Matan Banin et Boaz Tsaban
Une réduction du DLP de semi-groupe au DLP classique. (A reduction of semigroup DLP to classic DLP)
arXiv:1310.7903, 2013.
- 205
-
D. W. Berry, R. Cleve et R. D. Somma
Amélioration exponentielle de la précision pour la simulation de l'évolution Hamiltonienne. (Exponential improvement in precision for Hamiltonian-evolution simulation)
arXiv:1308.5424, 2013.
- 206
-
François Le Gall et Harumichi Nishimura
Algorithmes quantiques pour les produits de matrices sur des semi-anneaux. (Quantum algorithms for matrix products over semirings)
arXiv:1310.3898, 2013.
- 207
-
Nolan Wallach
Un algorithme polylogarithmique quantique pour les sous-groupes cachés cycliques maximaux non normaux dans le groupe affine d'un corps fini. (A quantum polylog algorithm for non-normal maximal cyclic hidden subgroups in the affine group of a finite field)
arXiv:1308.1415, 2013.
- 208
-
Lov Grover
Recherche quantique à point fixe. (Fixed-point quantum search)
Phys. Rev. Lett. 95(15):150501, 2005.
[arXiv:quant-ph/0503205]
- 209
-
Tathagat Tulsi, Lov Grover et Apoorva Patel
Un nouvel algorithme pour la recherche quantique à point fixe. (A new algorithm for fixed point quantum search)
Quantum Information and Computation 6(6):483-494, 2005.
[arXiv:quant-ph/0505007]
- 210
-
Guoming Wang
Algorithmes quantiques pour approximer les résistances effectives des réseaux électriques. (Quantum algorithms for approximating the effective resistances of electrical networks)
arXiv:1311.1851
- 211
-
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari et Rolando D. Somma
Amélioration exponentielle de la précision pour simuler des Hamiltoniens épars. (Exponential improvement in precision for simulating sparse Hamiltonians)
arXiv:1312.1414
- 212
-
Thomas Decker, Peter Høyer, Gabor Ivanyos et Miklos Santha
Algorithmes quantiques en temps polynomial pour certains problèmes polynomiaux cachés bivariés. (Polynomial time quantum algorithms for certain bivariate hidden polynomial problems)
arXiv:1305.1543
- 213
-
Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev et Fang Song
Un algorithme quantique pour calculer le groupe unitaire d'un corps de nombre d'un degré arbitraire. (A quantum algorithm for computing the unit group of an arbitrary degree number field)
Dans Proceedings of STOC 2014 pg. 293-302.
- 214
-
Seth Lloyd, Masoud Mohseni et Patrick Robentrost
Algorithmes quantiques pour l'apprentissage machine supervisé et non supervisé. (Quantum algorithms for supervised and unsupervised machine learning)
arXiv:1307.0411
- 215
-
Ashley Montanaro
Correspondance quantique rapide en moyenne. (Quantum pattern matching fast on average)
arXiv:1408.1816
- 227
-
Matthew B. Hastings, Dave Wecker, Bela Bauer et Matthias Troyer
Amélioration des algorithmes quantiques pour la chimie quantique. (Improving quantum algorithms for quantum chemistry)
Quantum Information and Computation, 15(1/2):0001-0021, 2015.
[arXiv:1403.1539]
- 228
-
Stephen P. Jordan, Keith S. M. Lee et John Preskill
Simulation quantique de la diffusion dans les théories de champs quantiques scalaires. (Quantum simulation of scattering in scalar quantum field theories)
Quantum Information and Computation, 14(11/12):1014-1080, 2014.
[arXiv:1112.4833]
- 229
-
Stephen P. Jordan, Keith S. M. Lee et John Preskill
Algorithmes quantiques pour les théories de champs quantiques fermioniques. (Quantum algorithms for fermionic quantum field theories)
arXiv:1404.7115
- 230
-
Gavin K. Brennen, Peter Rohde, Barry C. Sanders et Sukhi Singh
Simulation quantique multi-échelle de la théorie quantique des champs utilisant des ondelettes. (Multi-scale quantum simulation of quantum field theory using wavelets)
arXiv:1412.0750
- 231
-
Hefeng Wang, Sabre Kais, Alán Aspuru-Guzik et Mark R. Hoffmann.
Algorithme quantique pour obtenir le spectre d'énergie des systèmes moléculaires. (Quantum algorithm for obtaining the energy spectrum of molecular systems)
Physical Chemistry Chemical Physics, 10(35):5388-5393, 2008.
[arXiv:0907.0854]
- 232
-
Ivan Kassal et Alán Aspuru-Guzik
Algorithme quantique pour les propriétés moléculaires et l'optimisation de la géométrie. (Quantum algorithm for molecular properties and geometry optimization)
Journal of Chemical Physics, 131(22), 2009.
[arXiv:0908.1921]
- 233
-
James D. Whitfield, Jacob Biamonte et Alán Aspuru-Guzik
Simulation des Hamiltoniens de structure électronique utilisant des ordinateurs quantiques. (Simulation of electronic structure Hamiltonians using quantum computers)
Molecular Physics, 109(5):735-750, 2011.
[arXiv:1001.3855]
- 234
-
Borzu Toloui et Peter J. Love
Algorithmes quantiques pour la chimie quantique basés sur la parcimonie de la matrice CI. (Quantum algorithms for quantum chemistry based on the sparsity of the CI-matrix)
arXiv:1312.2529
- 235
-
James D. Whitfield
Simulations computationnelles quantiques sans spin et états adaptés à la symétrie. (Spin-free quantum computational simulations and symmetry adapted states)
Journal of Chemical Physics, 139(2):021105, 2013.
[arXiv:1306.1147]
- 236
-
Andrew W. Cross, Graeme Smith et John A. Smolin
Apprentissage quantique robuste au bruit. (Quantum learning robust to noise)
arXiv:1407.5088
- 237
-
Aram W. Harrow et David J. Rosenbaum
Uselessness for an oracle model with internal randomness. (Uselessness for an oracle model with internal randomness)
Quantum Information and Computation 14(7/8):608-624, 2014
[arXiv:1111.1462]
- 238
-
Jon R. Grice et David A. Meyer
Un algorithme quantique pour le décodage de Viterbi des codes convolutionnels classiques. (A quantum algorithm for Viterbi decoding of classical convolutional codes)
arXiv:1405.7479
- 239
-
Alexander Barg et Shiyu Zhou
Un algorithme de décodage quantique du code simplex. (A quantum decoding algorithm of the simplex code)
Proceedings of the 36th Annual Allerton Conference, 1998
Disponible sur la page d'accueil de l'auteur.
- 240
-
Guoming Wang
Algorithme quantique basé sur les programmes de span pour la détection d'arbres. (Span-program-based quantum algorithm for tree detection)
arXiv:1309.7713, 2013.
- 241
-
François Le Gall, Harumichi Nishimura et Seiichiro Tani
Algorithme quantique pour trouver des sous-hypergraphes de taille constante sur des hypergraphes 3-uniformes. (Quantum algorithm for finding constant-sized sub-hypergraphs over 3-uniform hypergraphs)
Dans Proceedings of COCOON, 2014. pg. 429-440
[arXiv:1310.4127]
- 242
-
Edward Farhi, Jeffrey Goldstone et Sam Gutmann
Un algorithme d'optimisation approximative quantique. (A quantum approximate optimization algorithm)
arXiv:1411.4028, 2014.
- 243
-
Edward Farhi, Jeffrey Goldstone et Sam Gutmann
Un algorithme d'optimisation approximative quantique appliqué à un problème de contrainte d'occurrence bornée. (A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem)
arXiv:1412.6062, 2014.
- 244
-
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari et Rolando D. Somma
Simulation de la dynamique Hamiltonienne avec une série de Taylor tronquée. (Simulating Hamiltonian dynamics with a truncated Taylor series)
arXiv:1412.4687, 2014.
- 245
-
Dominic W. Berry, Andrew M. Childs et Robin Kothari
Simulation Hamiltonienne avec une dépendance presque optimale sur tous les paramètres. (Hamiltonian simulation with nearly optimal dependence on all parameters)
arXiv:1501.01715, 2015.
- 246
-
Scott Aaronson
Lisez les petites lignes. (Read the fine print)
Nature Physics 11:291-293, 2015.
[texte intégral]
- 247
-
Alexander Elgart et George A. Hagedorn
Une note sur le théorème adiabatique de commutation. (A note on the switching adiabatic theorem)
Journal of Mathematical Physics 53(10):102202, 2012.
[arXiv:1204.2318]
- 248
-
Daniel J. Bernstein, Johannes Buchmann et Erik Dahmen, Eds.
Cryptographie post-quantique. (Post-Quantum Cryptography)
Springer, 2009.
- 249
-
B. D. Clader, B. C. Jacobs et C. R. Sprouse
Algorithme quantique de système linéaire préconditionné. (Preconditioned quantum linear system algorithm)
Phys. Rev. Lett. 110:250504, 2013.
[arXiv:1301.2340]
- 250
-
S. Lloyd, M. Mohseni et P. Rebentrost
Analyse en composantes principales quantiques. (Quantum principal component analysis)
Nature Physics. 10(9):631, 2014.
[arXiv:1307.0401]
- 251
-
Patrick Rebentrost, Masoud Mohseni et Seth Lloyd
Machine à vecteurs de support quantique pour la classification de grandes données. (Quantum support vector machine for big data classification)
Phys. Rev. Lett. 113, 130503, 2014.
[arXiv:1307.0471]
- 252
-
J. M. Pollard
Théorèmes sur la factorisation et le test de primalité. (Theorems on factorization and primality testing)
Proceedings of the Cambridge Philosophical Society. 76:521-228, 1974.
- 253
-
L. Babai, R. Beals et A. Seress
Théorie des groupes de matrices en temps polynomial. (Polynomial-time theory of matrix groups)
Dans Proceedings of STOC 2009, pg. 55-64.
- 254
-
Neil J. Ross et Peter Selinger
Approximation optimale de Clifford+T sans ancilla pour les rotations z. (Optimal ancilla-free Clifford+T approximations of z-rotations)
arXiv:1403.2975, 2014.
- 255
-
L. A. B. Kowada, C. Lavor, R. Portugal et C. M. H. de Figueiredo
Un nouvel algorithme quantique pour résoudre le problème de recherche minimum. (A new quantum algorithm for solving the minimum searching problem)
International Journal of Quantum Information, Vol. 6, No. 3, pg. 427-436, 2008.
- 256
-
Sean Hallgren et Aram Harrow
Accélérations superpolynomiales basées sur presque n'importe quel circuit quantique. (Superpolynomial speedups based on almost any quantum circuit)
Proceedings of ICALP 2008, pg. 782-795.
[arXiv:0805.0007]
- 257
-
Fernando G.S.L. Brandao et Michal Horodecki
Les accélérations quantiques exponentielles sont génériques. (Exponential quantum speed-ups are generic)
Quantum Information and Computation, Vol. 13, Pg. 0901, 2013
[arXiv:1010.3654]
- 258
-
Scott Aaronson et Andris Ambainis
Forrelation : Un problème qui sépare de manière optimale l'informatique quantique de l'informatique classique. (Forrelation: A problem that optimally separates quantum from classical computing.)
arXiv:1411.5729, 2014.
- 259
-
Z. Gedik
Accélération computationnelle avec un seul qutrit. (Computational speedup with a single qutrit)
arXiv:1403.5861, 2014.
- 260
-
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded
Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David
Witmer et John Wright
Battre l'affectation aléatoire sur des problèmes de satisfaction de contraintes de degré borné. (Beating the random assignment on constraint satisfaction problems of bounded degree)
arXiv:1505.03424, 2015.
- 261
-
David Cornwell
Transformations quantiques amplifiées. (Amplified Quantum Transforms)
arXiv:1406.0190, 2015.
- 262
-
T. Laarhoven, M. Mosca et J. van de Pol
Résoudre le problème du plus court vecteur dans les réseaux plus rapidement en utilisant la recherche quantique. (Solving the shortest vector problem in lattices faster using quantum search)
Proceedings of PQCrypto13, pp. 83-101, 2013.
[arXiv:1301.6176]
- 263
-
Andrew M. Childs, Robin Kothari et Rolando D. Somma
Algorithme quantique de systèmes linéaires avec une dépendance exponentiellement améliorée sur la précision. (Quantum linear systems algorithm with exponentially improved dependence on precision)
arXiv:1511.02306, 2015.
- 264
-
Ashley Montanaro
Accélération de la recherche quantique des algorithmes de retour en arrière. (Quantum walk speedup of backtracking algorithms)
arXiv:1509.02374, 2015.
- 265
-
Ashley Montanaro
Accélération quantique des méthodes de Monte Carlo. (Quantum speedup of Monte Carlo methods)
arXiv:1504.06987, 2015.
- 266
-
Andris Ambainis, Aleksandrs Belovs, Oded Regev et Ronald de Wolf
Algorithmes quantiques efficaces pour les tests de groupes (gappés) et les tests de junte. (Efficient quantum algorithms for (gapped) group testing and junta testing)
arXiv:1507.03126, 2015.
- 267
-
A. Atici et R. A. Servedio
Algorithmes quantiques pour l'apprentissage et le test des juntes. (Quantum algorithms for learning and testing juntas)
Quantum Information Processing, 6(5):323-348, 2007.
[arXiv:0707.3479]
- 268
-
Aleksandrs Belovs
Algorithmes quantiques pour l'apprentissage des juntes symétriques via la borne d'adversaire. (Quantum algorithms for learning symmetric juntas via the adversary bound)
Computational Complexity, 24(2):255-293, 2015.
(Apparaît également dans les actes de CCC'14).
[arXiv:1311.6777]
- 269
-
Stacey Jeffery et Shelby Kimmel
NAND-arbres, complexité de choix moyenne et résistance effective. (NAND-trees, average choice complexity, and effective resistance)
arXiv:1511.02235, 2015.
- 270
-
Scott Aaronson, Shalev Ben-David et Robin Kothari
Séparations dans la complexité des requêtes utilisant des feuilles de triche. (Separations in query complexity using cheat sheets)
arXiv:1511.01937, 2015.
- 271
-
Frédéric Grosshans, Thomas Lawson, François
Morain et Benjamin Smith
Factoring safe semiprimes with a single quantum query. (Factoring safe semiprimes with a single quantum query)
arXiv:1511.04385, 2015.
- 272
-
Agnis Āriņš
Algorithmes quantiques basés sur des programmes de span pour la bipartition des graphes et la connectivité. (Span-program-based quantum algorithms for graph bipartiteness and connectivity)
arXiv:1510.07825, 2015.
- 273
-
Juan Bermejo-Vega et Kevin C. Zatloukal
Hypergroupes abéliens et computation quantique. (Abelian hypergroups and quantum computation)
arXiv:1509.05806, 2015.
- 274
-
Andrew Childs et Jeffrey Goldstone
Recherche spatiale par marche quantique. (Spatial search by quantum walk)
Physical Review A, 70:022314, 2004.
[arXiv:quant-ph/0306054]
- 275
-
Shantanav Chakraborty, Leonardo Novo, Andris Ambainis et Yasser Omar
La recherche spatiale par marche quantique est optimale pour presque tous les graphes. (Spatial search by quantum walk is optimal for almost all graphs)
arXiv:1508.01327, 2015.
- 276
-
François Le Gall
Algorithme quantique amélioré pour la recherche de triangles via des arguments combinatoires. (Improved quantum algorithm for triangle finding via combinatorial arguments)
Dans Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pg. 216-225, 2014.
[arXiv:1407.0085]
- 277
- Ashley Montanaro
La complexité quantique d'approximer les moments de fréquence. (The quantum complexity of approximating the frequency moments)
arXiv:1505.00113, 2015.
- 278
- Rolando D. Somma
Simulations quantiques de systèmes quantiques unidimensionnels. (Quantum simulations of one dimensional quantum systems)
arXiv:1503.06319, 2015.
- 279
- Bill Fefferman et Cedric Yen-Yu Lin
Une caractérisation complète de l'espace quantique unitaire. (A complete characterization of unitary quantum space)
arXiv:1604.01384, 2016.
- 280
- Tsuyoshi Ito et Stacey Jeffery
Programmes de span approximatifs. (Approximate span programs)
arXiv:1507.00432, 2015.
- 281
- Arnau Riera, Christian Gogolin et Jens Eisert
Thermalisation dans la nature et sur un ordinateur quantique. (Thermalization in nature and on a quantum computer)
Physical Review Letters, 108:080402 (2012)
[arXiv:1102.2389]
- 282
- Michael J. Kastoryano et Fernando G. S. L. Brandao
Échantillonneurs de Gibbs quantiques : le cas commutatif. (Quantum Gibbs Samplers: the commuting case)
Communications in Mathematical Physics, 344(3):915-957 (2016)
[arXiv:1409.3435]
- 283
- Andrew M. Childs, David Jao et Vladimir Soukharev
Construction d'isogénies de courbes elliptiques dans un temps quantique subexponentiel. (Constructing elliptic curve isogenies in quantum subexponential time)
Journal of Mathematical Cryptology, 8(1):1-29 (2014)
[arXiv:1012.4019]
- 284
- Markus Grassl, Brandon Langenberg, Martin Roetteler et Rainer Steinwandt
Application de l'algorithme de Grover à l'AES : estimations des ressources quantiques. (Applying Grover's algorithm to AES: quantum resource estimates)
arXiv:1512.04965, 2015.
- 285
- M. Ami, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent et J. Schanck
Estimation du coût des attaques quantiques génériques par pré-image sur SHA-2 et SHA-3. (Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3)
arXiv:1603.09383, 2016.
- 286
- Marc Kaplan, Gaetan Leurent, Anthony Leverrier et Maria Naya-Plasencia
Cryptanalyse différentielle et linéaire quantique. (Quantum differential and linear cryptanalysis)
arXiv:1510.05836, 2015.
- 287
- Scott Fluhrer
Cryptanalyse quantique de NTRU. (Quantum Cryptanalysis of NTRU)
Cryptology ePrint Archive: Report 2015/676, 2015.
- 288
- Marc Kaplan
Attaques quantiques contre les chiffrements par blocs itérés. (Quantum attacks against iterated block ciphers)
arXiv:1410.1434, 2014.
- 289
- H. Kuwakado et M. Morii
Distingueur quantique entre le chiffre de Feistel à 3 tours et la permutation aléatoire. (Quantum distinguisher between the 3-round Feistel cipher and the random permutation)
Dans Proceedings of IEEE International Symposium on Information Theory (ISIT), pg. 2682-2685, 2010.
- 290
- H. Kuwakado et M. Morii
Sécurité sur le chiffre Even-Mansour de type quantique. (Security on the quantum-type Even-Mansour cipher)
Dans Proceedings of International Symposium on Information Theory and its Applications (ISITA), pg. 312-316, 2012.
- 291
- Martin Roetteler et Rainer Steinwandt
Une note sur les attaques quantiques liées aux clés. (A note on quantum related-key attacks)
arXiv:1306.2301, 2013.
- 292
- Thomas Santoli et Christian Schaffner
Utilisation de l'algorithme de Simon pour attaquer les primitives cryptographiques à clé symétrique. (Using Simon's algorithm to attack symmetric-key cryptographic primitives)
arXiv:1603.07856, 2016.
- 293
- Rolando D. Somma
Une approximation de Trotter-Suzuki pour les groupes de Lie avec des applications à la simulation Hamiltonienne. (A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation)
arXiv:1512.03416, 2015.
- 294
- Guang Hao Low et Isaac Chuang
Simulation Hamiltonienne optimale par traitement de signal quantique. (Optimal Hamiltonian simulation by quantum signal processing)
arXiv:1606.02685, 2016.
- 295
- Dominic W. Berry et Leonardo Novo
Marche quantique corrigée pour une simulation Hamiltonienne optimale. (Corrected quantum walk for optimal Hamiltonian simulation)
arXiv:1606.03443, 2016.
- 296
- Ashley Montanaro et Sam Pallister
Algorithmes quantiques et méthode des éléments finis. (Quantum algorithms and the finite element method)
arXiv:1512.05903, 2015.
- 297
- Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Fei Gao et Qiao-Yan Wen
Algorithme quantique pour les systèmes de Toeplitz. (Quantum algorithm for the Toeplitz systems)
arXiv:1608.02184, 2016.
- 298
- Salvatore Mandra, Gian Giacomo Guerreschi et Alan Aspuru-Guzik
Algorithme quantique plus rapide que classique pour des formules d'exacte satisfiabilité et des problèmes d'occupation. (Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems)
arXiv:1512.00859, 2015.
- 299
- J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price,
et S. Stanisic
Avancées dans l'apprentissage automatique quantique. (Advances in quantum machine learning)
arXiv:1512.02900, 2015.
- 300
- Cedric Yen-Yu Lin et Yechao Zhu
Performance de QAOA sur des instances typiques de problèmes de satisfaction de contraintes avec degré borné. (Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree)
arXiv:1601.01744, 2016.
- 301
- Dave Wecker, Matthew B. Hastings et Matthias Troyer
Entraînement d'un optimiseur quantique. (Training a quantum optimizer)
arXiv:1605.05370, 2016.
- 302
- Edward Farhi et Aram W. Harrow
Suprématie quantique par le biais de l'algorithme d'optimisation approximative quantique. (Quantum supremacy through the quantum approximate optimization algorithm)
arXiv:1602.07674, 2016.
- 303
- Thomas G. Wong
Recherche quantique sur les graphes de Johnson. (Quantum walk search on Johnson graphs)
arXiv:1601.04212, 2016.
- 304
- Jonatan Janmark, David A. Meyer et Thomas G. Wong
La symétrie globale n'est pas nécessaire pour une recherche quantique rapide. (Global symmetry is unnecessary for fast quantum search)
Physical Review Letters 112:210502, 2014.
[arXiv:1403.2228]
- 305
- David A. Meyer et Thomas G. Wong
La connectivité est un mauvais indicateur d'une recherche quantique rapide. (Connectivity is a poor indicator of fast quantum search)
Physical Review Letters 114:110503, 2014.
[arXiv:1409.5876]
- 306
- Thomas G. Wong
Recherche spatiale par marche quantique en temps continu avec plusieurs sommets marqués. (Spatial search by continuous-time quantum walk with multiple marked vertices)
Quantum Information Processing 15(4):1411-1443, 2016.
[arXiv:1501.07071]
- 307
- Anirban Naryan Chowdhury et Rolando D. Somma
Algorithmes quantiques pour l'échantillonnage de Gibbs et l'estimation du temps d'atteinte. (Quantum algorithms for Gibbs sampling and hitting-time estimation)
arXiv:1603.02940, 2016.
- 308
- Edward Farhi, Shelby Kimmel et Kristan Temme
Une version quantique de l'algorithme de Schoning appliquée au 2-SAT quantique. (A quantum version of Schoning's algorithm applied to quantum 2-SAT)
arXiv:1603.06985, 2016.
- 309
- Iordanis Kerenidis et Anupam Prakash
Systèmes de recommandation quantiques. (Quantum recommendation systems)
Innovations in Theoretical Computer Science (ITCS 2017), LIPIcs, vol. 67, pg. 1868-8969.
[arXiv:1603.08675]
- 310
- Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker et Matthias Troyer
Élucider les mécanismes de réaction sur des ordinateurs quantiques. (Elucidating reaction mechanisms on quantum computers)
arXiv:1605.03590, 2016.
- 311
- Aram W. Harrow et Ashley Montanaro
Mesures séquentielles, perturbation et test de propriété. (Sequential measurements, disturbance, and property testing)
arXiv:1607.03236, 2016.
- 312
- Martin Roetteler
Algorithmes quantiques pour les ensembles de différences abéliens et applications aux sous-groupes cachés diédraux. (Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups)
arXiv:1608.02005, 2016.
- 313
- Fernando G.S.L. Brandao et Krysta Svore
Accélérations quantiques pour la programmation semi-définie. (Quantum speed-ups for semidefinite programming)
arXiv:1609.05537, 2016.
- 314
- Z-C Yang, A. Rahmani, A. Shabani, H. Neven et C. Chamon
Optimisation des algorithmes quantiques variationnels en utilisant le principe du minimum de Pontryagin. (Optimizing variational quantum algorithms using Pontryagins's minimum principle)
arXiv:1607.06473, 2016.
- 315
- Gilles Brassard, Peter Høyer et Alain Tapp
Cryptanalyse quantique des fonctions de hachage et sans griffes. (Quantum cryptanalysis of hash and claw-free functions)
Dans Proceedings of the 3rd Latin American symposium on Theoretical Informatics (LATIN'98), pg. 163-169, 1998.
- 316
- Daniel J. Bernstein
Analyse des coûts des collisions de hachage : les ordinateurs quantiques rendront-ils les SHARCS obsolètes ? (Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?)
Dans Proceedings of the 4th Workshop on Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS'09), pg. 105-116, 2009.
[disponible ici]
- 317
- Chris Cade, Ashley Montanaro et Aleksandrs Belovs
Algorithmes quantiques efficaces en temps et en espace pour détecter des cycles et tester la bipartition. (Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness)
arXiv:1610.00581, 2016.
- 318
- A. Belovs et B. Reichardt
Programmes de span et algorithmes quantiques pour la connectivité st et la détection de griffes. (Span programs and quantum algorithms for st-connectivity and claw detection)
Dans European Symposium on Algorithms (ESA'12), pg. 193-204, 2012.
[arXiv:1203.2603]
- 319
- Titouan Carette, Mathieu Laurière et Frédéric Magniez
Graphes d'apprentissage étendus pour la recherche de triangles. (Extended learning graphs for triangle finding)
arXiv:1609.07786, 2016.
- 320
- F. Le Gall et N. Shogo
Algorithme quantique pour la recherche de triangles dans des graphes clairsemés. (Quantum algorithm for triangle finding in sparse graphs)
Dans Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15), pg. 590-600, 2015.
- 321
- Or Sattath et Itai Arad
Un lemme local de Lovász quantique constructif pour des projecteurs commutants. (A constructive quantum Lovász local lemma for commuting projectors)
Quantum Information and Computation, 15(11/12)987-996pg, 2015.
[arXiv:1310.7766]
- 322
- Martin Schwarz, Toby S. Cubitt et Frank Verstraete
Une preuve informationnelle du lemme local commutatif de Lovász quantique constructif. (An information-theoretic proof of the constructive commutative quantum Lovász local lemma)
arXiv:1311.6474
- 323
- C. Shoen, E. Solano, F. Verstraete, J. I. Cirac et M. M. Wolf
Génération séquentielle d'états multi-qubits intriqués. (Sequential generation of entangled multi-qubit states)
Physical Review Letters, 95:110503, 2005.
[arXiv:quant-ph/0501096]
- 324
- C. Shoen, K. Hammerer, M. M. Wolf, J. I. Cirac et E. Solano
Génération séquentielle d'états de produit matriciel dans la QED de cavité. (Sequential generation of matrix-product states in cavity QED)
Physical Review A, 75:032311, 2007.
[arXiv:quant-ph/0612101]
- 325
- Yimin Ge, András Molnár et J. Ignacio Cirac
Préparation adiabatique rapide d'états PEPS injectifs et d'états de Gibbs. (Rapid adiabatic preparation of injective PEPS and Gibbs states)
Physical Review Letters, 116:080503, 2016.
[arXiv:1508.00570]
- 326
- Martin Schwarz, Kristan Temme et Frank Verstraete
Préparation d'états de paires intriquées projetées sur un ordinateur quantique. (Preparing projected entangled pair states on a quantum computer)
Physical Review Letters, 108:110502, 2012.
[arXiv:1104.1410]
- 327
- Martin Schwarz, Toby S. Cubitt, Kristan Temme, Frank Verstraete et David Perez-Garcia
Préparation de PEPS topologiques sur un ordinateur quantique. (Preparing topological PEPS on a quantum computer)
Physical Review A, 88:032321, 2013.
[arXiv:1211.4050]
- 328
- M. Schwarz, O. Buerschaper et J. Eisert
Approximation des observables locales sur des états de paires intriquées projetées. (Approximating local observables on projected entangled pair states)
arXiv:1606.06301, 2016.
- 329
- Jean-François Biasse et Fang Song
Algorithmes quantiques efficaces pour le calcul des groupes de classes et la résolution du problème d'idéal principal dans des corps de degré arbitraire. (Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields)
Dans Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), pg. 893-902, 2016.
- 330
- Peter Høyer et Mojtaba Komeili
Marche quantique efficace sur la grille avec plusieurs éléments marqués. (Efficient quantum walk on the grid with multiple marked elements)
Dans Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 42, 2016.
[arXiv:1612.08958]
- 331
- Peter Wittek
Apprentissage machine quantique : ce que l'informatique quantique signifie pour l'exploration de données. (Quantum Machine Learning: what quantum computing means to data mining)
Academic Press, 2014.
- 332
- Maria Schuld, Ilya Sinayskiy et Francesco Petruccione
Une introduction à l'apprentissage machine quantique. (An introduction to quantum machine learning)
Contemporary Physics, 56(2):172, 2014.
[arXiv:1409.3097]
- 333
- J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe et S. Lloyd
Apprentissage machine quantique. (Quantum machine learning)
arXiv:1611.09347
- 334
- Esma Aïmeur, Gilles Brassard et Sébastien Gambs
Apprentissage machine dans un monde quantique. (Machine learning in a quantum world)
Dans Advances in Artificial Intelligence: 19th Conference of the Canadian Society for Computational Studies of Intelligence pg. 431-442, Springer, 2006.
- 335
- Vedran Dunjko, Jacob Taylor et Hans Briegel
Apprentissage renforcé amélioré par quantique. (Quantum-enhanced machine learning)
Phys. Rev. Lett 117:130501, 2016.
- 336
- Nathan Wiebe, Ashish Kapoor et Krysta Svore
Algorithmes quantiques pour les méthodes de voisinage pour l'apprentissage supervisé et non supervisé. (Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning)
Quantum Information and Computation 15(3/4): 0318-0358, 2015.
[arXiv:1401.2142]
- 337
- Seokwon Yoo, Jeongho Bang, Changhyoup Lee et Junhyoug Lee
Un accélérateur quantique dans l'apprentissage machine : trouver une fonction booléenne N-bit pour une classification. (A quantum speedup in machine learning: finding a N-bit Boolean function for a classification)
New Journal of Physics 6(10):103014, 2014.
[arXiv:1303.6055]
- 338
- Maria Schuld, Ilya Sinayskiy et Francesco Petruccione
Prédiction par régression linéaire sur un ordinateur quantique. (Prediction by linear regression on a quantum computer)
Physical Review A 94:022342, 2016.
[arXiv:1601.07823]
- 339
- Zhikuan Zhao, Jack K. Fitzsimons et Joseph F. Fitzsimons
Régression de processus gaussiens assistée par quantique. (Quantum assisted Gaussian process regression)
arXiv:1512.03929
- 353
- Srinivasan Arunachalam et Ronald de Wolf
Complexité d'échantillonnage quantique optimale des algorithmes d'apprentissage. (Optimal quantum sample complexity of learning algorithms)
arXiv:1607.00932, 2016.
- 354
- Alex Monràs, Gael Sentís et Peter Wittek
Apprentissage quantique inductif : pourquoi vous le faites presque bien. (Inductive quantum learning: why you are doing it almost right)
arXiv:1605.07541, 2016.
- 355
- A. Bisio, G. Chiribella, G. M. D'Ariano, S. Facchini et P. Perinotti
Apprentissage quantique optimal d'une transformation unitaire. (Optimal quantum learning of a unitary transformation)
Physical Review A 81:032324, 2010.
[arXiv:0903.0543]
- 356
- M. Sasaki, A. Carlini et R. Jozsa
Correspondance de modèles quantiques. (Quantum template matching)
Physical Review A 64:022317, 2001.
[arXiv:quant-ph/0102020]
- 357
- Masahide Sasaki et Alberto Carlini
Apprentissage quantique et machine de correspondance quantique universelle. (Quantum learning and universal quantum matching machine)
Physical Review A 66:022303, 2002.
[arXiv:quant-ph/0202173]
- 358
- Esma Aïmeur, Gilles Brassard et Sébastien Gambs
Algorithmes de clustering quantique. (Quantum clustering algorithms)
Dans Proceedings of the 24th International Conference on Machine Learning (ICML), pg. 1-8, 2007.
- 359
- Iordanis Kerenidis et Anupam Prakash
Descente de gradient quantique pour les systèmes linéaires et les moindres carrés. (Quantum gradient descent for linear systems and least squares)
arXiv:1704.04992, 2017.
- 360
- Dan Boneh et Mark Zhandry
Codes d'authentification de message sécurisés par quantique. (Quantum-secure message authentication codes)
Dans Proceedings of Eurocrypt, pg. 592-608, 2013.
- 361
- A. M. Childs, W. van Dam, S-H Hung et I. E. Shparlinski
Algorithme quantique optimal pour l'interpolation polynomiale. (Optimal quantum algorithm for polynomial interpolation)
Dans Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pg. 16:1-16:13, 2016.
[arXiv:1509.09271]
- 362
- Volker Strassen
Quelques résultats sur la complexité de calcul. (Einige Resultate über Berechnungskomplexität)
Dans Jahresbericht der Deutschen Mathematiker-Vereinigung, 78(1):1-8, 1976/1977.
- 363
- Stacey Jeffery
Frameworks for Quantum Algorithms
Thèse de doctorat, U. Waterloo, 2014.
- 364
- Seiichiro Tani
Un algorithme amélioré de recherche de griffes utilisant la marche quantique. (An improved claw finding algorithm using quantum walk)
Dans Mathematical Foundations of Computer Science (MFCS), pg. 536-547, 2007.
[arXiv:0708.2584]
- 365
- K. Iwama et A. Kawachi
Un nouvel algorithme quantique de recherche de griffes pour trois fonctions. (A new quantum claw-finding algorithm for three functions)
New Generation Computing, 21(4):319-327, 2003.
- 366
- D. J. Bernstein, N. Heninger, P. Lou et L. Valenta
RSA post-quantique. (Post-quantum RSA)
IACR e-print 2017/351, 2017.
- 367
- Francois Fillion-Gourdeau, Steve MacLean et Raymond Laflamme
Algorithme quantique pour la solution de l'équation de Dirac. (Quantum algorithm for the solution of the Dirac equation)
arXiv:1611.05484, 2016.
- 368
- Ali Hamed Moosavian et Stephen Jordan
Algorithme quantique plus rapide pour simuler la théorie quantique des champs fermioniques. (Faster quantum algorithm to simulate Fermionic quantum field theory)
arXiv:1711.04006, 2017.
- 369
- Pedro C.S. Costa, Stephen Jordan et Aaron Ostrander
Algorithme quantique pour simuler l'équation des ondes. (Quantum algorithm for simulating the wave equation)
arXiv:1711.05394, 2017.
- 370
- Jeffrey Yepez
Modèle de gaz quantique hautement covariant de l'équation de Dirac. (Highly covariant quantum lattice gas model of the Dirac equation)
arXiv:1106.0739, 2011.
- 371
- Jeffrey Yepez
Modèle de gaz quantique de particules de Dirac en 1+1 dimensions. (Quantum lattice gas model of Dirac particles in 1+1 dimensions)
arXiv:1307.3595, 2013.
- 372
- Bruce M. Boghosian et Washington Taylor
Simulation de la mécanique quantique sur un ordinateur quantique. (Simulating quantum mechanics on a quantum computer)
Physica D 120:30-42, 1998.
[arXiv:quant-ph/9701019]
- 373
- Yimin Ge, Jordi Tura et J. Ignacio Cirac
Préparation plus rapide de l'état fondamental et estimation de l'énergie fondamentale à haute précision sur un ordinateur quantique. (Faster ground state preparation and high-precision ground energy estimation on a quantum computer)
arXiv:1712.03193, 2017.
- 374
- Renato Portugal
Distinctness des éléments revisitée. (Element distinctness revisited)
arXiv:1711.11336, 2017.
- 375
- Kanav Setia et James D. Whitfield
Simulation super rapide de Bravyi-Kitaev des fermions sur un ordinateur quantique. (Bravyi-Kitaev superfast simulation of fermions on a quantum computer)
arXiv:1712.00446, 2017.
- 376
- Richard Cleve et Chunhao Wang
Algorithmes quantiques efficaces pour simuler l'évolution de Lindblad. (Efficient quantum algorithms for simulating Lindblad evolution)
arXiv:1612.09512, 2016.
- 377
- M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano et J. Eisert
Théorème de Church-Turing quantique dissipatif. (Dissipative quantum Church-Turing theorem)
Physical Review Letters 107(12):120501, 2011.
[arXiv:1105.3986]
- 378
- A. M. Childs et T. Li
Simulation efficace de dynamiques quantiques markoviennes clairsemées. (Efficient simulation of sparse Markovian quantum dynamics)
arXiv:1611.05543, 2016.
- 379
- R. Di Candia, J. S. Pedernales, A. del Campo, E. Solano et J. Casanova
Simulation quantique de processus dissipatifs sans ingénierie de réservoir. (Quantum simulation of dissipative processes without reservoir engineering)
Scientific Reports 5:9981, 2015.
- 380
- R. Babbush, D. Berry, M. Kieferová, G. H. Low, Y. Sanders, A. Sherer et N. Wiebe
Techniques améliorées pour préparer les états propres des Hamiltoniens fermioniques. (Improved techniques for preparing eigenstates of Fermionic Hamiltonians)
arXiv:1711.10460, 2017.
- 381
- D. Poulin, A. Kitaev, D. S. Steiger, M. B. Hasting et M. Troyer
Algorithme quantique rapide pour les propriétés spectrales. (Fast quantum algorithm for spectral properties)
arXiv:1711.11025, 2017.
- 382
- Guang Hao Low et Isaac Chuang
Simulation Hamiltonienne par qubitisation. (Hamiltonian simulation by qubitization)
arXiv:1610.06546, 2016.
- 383
- F.G.S.L. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore et X. Wu
Solveurs SDP quantiques : grandes accélérations, optimalité et applications à l'apprentissage quantique. (Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning)
Proceedings of ICALP 2019
[arXiv:1710.02581]
- 384
- M. Ekerå et J. Håstad
Algorithmes quantiques pour le calcul de logarithmes discrets courts et la factorisation d'entiers RSA. (Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers)
Proceedings of PQCrypto 2017, pg. 347-363. (LNCS Volume 10346), 2017.
- 385
- M. Ekerå
Sur le post-traitement dans l'algorithme quantique pour le calcul de logarithmes discrets courts. (On post-processing in the quantum algorithm for computing short discrete logarithms)
IACR ePrint Archive Report 2017/1122, 2017.
- 386
- D. J. Bernstein, J.-F. Biasse et M. Mosca
Un algorithme de factorisation quantique à faible ressource. (A low-resource quantum factoring algorithm)
Proceedings of PQCrypto 2017, pg. 330-346 (LNCS Volume 10346), 2017.
- 387
- Jianxin Chen, Andrew M. Childs et Shih-Han Hung
Algorithme quantique pour l'interpolation polynomiale multivariée. (Quantum algorithm for multivariate polynomial interpolation)
Proceedings of the Royal Society A, 474:20170480, 2017.
arXiv:1701.03990
- 388
- Lisa Hales et Sean Hallgren
Un algorithme amélioré de transformation de Fourier quantique et ses applications. (An improved quantum Fourier transform algorithm and applications.)
Dans Proceedings of FOCS 2000, pg. 515-525.
- 389
- Igor Shparlinski et Arne Winterhof
Reconstruction quantique de périodes de séquences approximatives. (Quantum period reconstruction of approximate sequences)
Information Processing Letters, 103:211-215, 2007.
- 390
- Alexander Russell et Igor E. Shparlinski
Reconstruction de fonctions classiques et quantiques via l'évaluation de caractères. (Classical and quantum function reconstruction via character evaluation)
Journal of Complexity, 20:404-422, 2004.
- 391
- Sean Hallgren, Alexander Russell et Igor Shparlinski
Reconstruction de fonctions rationnelles quantiques bruyantes. (Quantum noisy rational function reconstruction)
Dans Proceedings of COCOON 2005, pg. 420-429.
- 392
- G. Ivanyos, M. Karpinski, M. Santha, N. Saxena et I. Shparlinski
Interpolation polynomiale et test d'identité à partir de puissances élevées sur des corps finis. (Polynomial interpolation and identity testing from high powers over finite fields)
Algorithmica, 80:560-575, 2017.
- 393
- Qi Cheng
Preuve de primalité via un tour dans ECPP et une itération dans AKS. (Primality Proving via One Round in ECPP and One Iteration in AKS)
Journal of Cryptology, Volume 20, Issue 3, pg. 375-387, juillet 2007.
- 394
- Daniel J. Bernstein
Preuve de primalité en temps aléatoire essentiellement quartique. (Proving primality in essentially quartic random time)
Mathematics of Computation, Vol. 76, pg. 389-403, 2007.
- 395
- F. Morain
Implémentation de la version asymptotiquement rapide de l'algorithme de preuve de primalité par courbe elliptique. (Implementing the asymptotically fast version of the elliptic curve primality proving algorithm)
Mathematics of Computation, Vol. 76, pg. 493-505, 2007.
- 396
- Alvaro Donis-Vela et Juan Carlos Garcia-Escartin
Un test de primalité quantique avec recherche d'ordre. (A quantum primality test with order finding)
arXiv:1711.02616, 2017.
- 397
- H. F. Chau et H.-K. Lo
Test de primalité via la factorisation quantique. (Primality test via quantum factorization)
International Journal of Modern Physics C, Vol. 8, No. 2, pg. 131-138, 1997.
[arXiv:quant-ph/9508005]
- 398
- David Harvey et Joris Van Der Hoeven
Multiplication entière en temps \( O(n \log n) \). (Integer multiplication in time \( O(n \log n) \))
hal-02070778, 2019.
- 399
- Charles Greathouse
communication personnelle, 2019.
- 400
- Ewin Tang
Un algorithme classique inspiré par quantique pour les systèmes de recommandation. (A quantum-inspired classical algorithm for recommendation systems)
Dans Proceedings of STOC 2019, pg. 217-228.
[arXiv:1807.04271]
- 401
- Ewin Tang
Algorithmes classiques inspirés par quantique pour l'analyse en composantes principales et le clustering supervisé. (Quantum-inspired classical algorithms for principal component analysis and supervised clustering)
arXiv:1811.00414, 2018.
- 402
- L. Wossnig, Z. Zhao, et A. Prakash
Un algorithme quantique pour les systèmes linéaires denses. (A quantum linear system algorithm for dense matrices)
Physical Review Letters vol. 120, no. 5, pg. 050502, 2018.
arXiv:1704.06174, 2017.
- 403
- Zhikuan Zhao, Alejandro Pozas-Kerstjens, Patrick Rebentrost, et Peter Wittek
Apprentissage profond bayésien sur un ordinateur quantique. (Bayesian Deep Learning on a Quantum Computer)
Quantum Machine Intelligence vol. 1, pg. 41-51, 2019.
[arXiv:1806.11463]
- 404
- Anja Becker, Jean-Sébastien Coron, et Antoine Joux
Amélioration des algorithmes génériques pour les sacs à dos difficiles. (Improved generic algorithms for hard knapsacks)
Proceedings of Eurocrypt 2011 pg. 364-385
[IACR eprint 2011/474]
- 405
- Kun Zhang et Vladimir E. Korepin
Algorithme de recherche quantique à faible profondeur. (Low depth quantum search algorithm)
arXiv:1908.04171, 2019.
- 406
- Andriyan Bayo Suksmono et Yuichiro Minato
Recherche de matrices de Hadamard par une machine d'optimisation quantique. (Finding Hadamard matrices by a quantum annealing machine)
Scientific Reports 9:14380, 2019.
[arXiv:1902.07890]
- 407
- Gábor Ivanyos, Anupam Prakash, et Miklos Santha
Sur l'apprentissage des fonctions linéaires à partir de sous-ensembles et ses applications en informatique quantique. (On learning linear functions from subset and its applications in quantum computing)
26th Annual European Symposium on Algorithms (ESA 2018), LIPIcs volume 112, 2018.
[arXiv:1806.09660]
- 408
- Gábor Ivanyos
Sur la résolution de systèmes de déséquations linéaires aléatoires. (On solving systems of random linear disequations)
Quantum Information and Computation, 8(6):579-594, 2008.
[arXiv:0704.2988]
- 409
- A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prusis, et J. Vihrovs
Accélérations quantiques pour les algorithmes de programmation dynamique en temps exponentiel. (Quantum speedups for exponential-time dynamic programming algorithms)
Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 19), pg. 1783-1793, 2019.
[arXiv:1807.05209]
- 410
- Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, et Guoming Wang
Algorithme quantique pour les équations différentielles linéaires avec une dépendance exponentiellement améliorée sur la précision. (Quantum algorithm for linear differential equations with exponentially improved dependence on precision)
Communications in Mathematical Physics, 356(3):1057-1081, 2017.
[arXiv:1701.03684]
- 411
- Sarah K. Leyton et Tobias J. Osborne
Algorithme quantique pour résoudre des équations différentielles non linéaires. (Quantum algorithm to solve nonlinear differential equations)
arXiv:0812.4423
- 412
- Y. Cao, A. Papageorgiou, I. Petras, J. Traub, et S. Kais
Algorithme quantique et conception de circuits résolvant l'équation de Poisson. (Quantum algorithm and circuit design solving the Poisson equation)
New Journal of Physics 15(1):013021, 2013.
[arXiv:1207.2485]
- 413
- S. Wang, Z. Wang, W. Li, L. Fan, Z. Wei, et Y. Gu
Solveur de Poisson quantique rapide : l'algorithme et la conception de circuits modulaires. (Quantum fast Poisson solver: the algorithm and modular circuit design)
arXiv:1910.09756, 2019.
- 414
- A. Scherer, B. Valiron, S.-C. Mau, S. Alexander, E. van den Berg, et T. Chapuran
Analyse concrète des ressources de l'algorithme quantique de systèmes linéaires utilisé pour calculer la section efficace de diffusion électromagnétique d'une cible 2D. (Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering crossection of a 2D target)
Quantum Information Processing 16:60, 2017.
[arXiv:1505.06552]
- 415
- Juan Miguel Arrazola, Timjan Kalajdziavski, Christian Weedbrook, et Seth Lloyd
Algorithme quantique pour les équations différentielles partielles linéaires non homogènes. (Quantum algorithm for nonhomogeneous linear partial differential equations)
Physical Review A 100:032306, 2019.
[arXiv:1809.02622]
- 416
- Andrew Childs et Jin-Peng Liu
Méthodes spectrales quantiques pour les équations différentielles. (Quantum spectral methods for differential equations)
arXiv:1901.00961
- 417
- Alexander Engle, Graeme Smith, et Scott E. Parker
Un algorithme quantique pour l'équation de Vlasov. (A quantum algorithm for the Vlasov equation)
arXiv:1907.09418
- 418
- Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, et Xiaodi Wu
Algorithmes quantiques et bornes inférieures pour l'optimisation convexe. (Quantum algorithms and lower bounds for convex optimization)
arXiv:1809.01731
- 419
- S. Chakrabarti, A. M. Childs, S.-H. Hung, T. Li, C. Wang, et X. Wu
Algorithme quantique pour estimer les volumes de corps convexes. (Quantum algorithm for estimating volumes of convex bodies)
arXiv:1908.03903
- 420
- Joran van Apeldoorn, András Gilyén, Sander Gribling, et Ronald de Wolf
Optimisation de l'optimisation quantique via un calcul de gradient quantique plus rapide. (Optimizing quantum optimization algorithms via faster quantum gradient computation)
arXiv:1809.00643
- 421
- Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, et Chunhao Wang
Cadre arithmétique de matrice à faible rang sublinéaire basé sur l'échantillonnage pour déquantifier l'apprentissage automatique quantique. (Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning)
Proceedings of STOC 2020, pg. 387-400
[arXiv:1910.06151]
- 422
- Andris Ambainis et Martins Kokainis
Algorithme quantique pour l'estimation de la taille d'un arbre, avec des applications à la recherche exhaustive et aux jeux à 2 joueurs. (Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games)
Proceedings of STOC 2017, pg. 989-1002
[arXiv:1704.06774]
- 445
- G. Xu, A. J. Daley, P. Givi, et R. D. Somma
Algorithme quantique pour le calcul du taux de conversion des réactifs dans une turbulence homogène. (Quantum algorithm for the computation of the reactant conversion rate in homogeneous turbulence)
Combustion Theory and Modelling 23(6):1090-1104, 2018.
- 446
-
Noah Linden, Ashley Montanaro, Changpeng Shao
Algorithmes quantiques vs. classiques pour résoudre l'équation de la chaleur. (Quantum vs. classical algorithms for solving the heat equation)
Communications in Mathematical Physics 395:601, 2022.
[arXiv:2004.06516]
- 447
-
K. Kaneko, K. Miyamoto, N. Takeda, et K. Yoshino
Accélération quantique de l'intégration de Monte Carlo dans la direction de la dimension et son application à la finance. (Quantum speedup of Monte Carlo integration in the direction of dimension and its application to finance)
Quantum Information Processing 20:185, 2021.
[arXiv:2011.02165]
- 448
-
P. Rebentrost, B. Gupt, et T. R. Bromley
Finance computationnelle quantique : tarification Monte Carlo des dérivés financiers. (Quantum computational finance: Monte Carlo pricing of financial derivatives)
Physical Review A 98(2):022321, 2018.
[arXiv:1805.00109]
- 449
-
Javier Gonzalez-Conde, Ángel Rodríguez-Rozas, Enrique Solano, et Mikel Sanz
Simulation Hamiltonienne efficace pour résoudre la dynamique des prix d'options. (Efficient Hamiltonian simulation for solving option price dynamics)
Physical Review Research 5:043220, 2024.
[arXiv:2101.04023]
- 450
-
Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, Anupam Prakash
Perspectives et défis de la finance quantique. (Prospects and challenges of quantum finance)
arXiv:2011.06492, 2020.
- 451
-
R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun,
Y. Alexeev, J. M. Dreiling,
J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, J.
Johansen, M. Matheny, T. Mengle,
M. Mills, S. A. Moses, B. Neyenhuis, P. Siegfried, R. Yalovetzky, et M. Pistoia
Preuve d'un avantage d'échelle pour l'algorithme d'optimisation approximative quantique sur un problème classiquement intraitable. (Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem)
Science Advances 10(22):eadm6761, 2024.
[arXiv:2308.02342]
- 452
-
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, et Leo Zhou
L'algorithme d'optimisation approximative quantique à grande profondeur pour MaxCut sur des graphes réguliers à grand girth et le modèle de Sherrington-Kirkpatrick. (The Quantum Approximate Optimization Algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington-Kirkpatrick model)
Proceedings of TQC22 7:1-7:21, 2022.
[arXiv:2110.14206]
- 453
-
Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V.
Isakov, et Ryan Babbush
Optimisation par interférométrie quantique décodée. (Optimization by Decoded Quantum Interferometry)
arXiv:2408.08292, 2024.
- 454
-
Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, et Ryan Babbush
Accélérations quantiques quartiques pour l'inférence plantée. (Quartic quantum speedups for planted inference)
arXiv:2406.19378, 2024.
- 466
-
Kaoru Mizuta et Keisuke Fujii
Simulation Hamiltonienne optimale pour les systèmes périodiques dans le temps. (Optimal Hamiltonian simulation for time-periodic systems)
Quantum, 7:962, 2023.
[arXiv:2209.05048]
- 467
-
Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, et Nathan Wiebe
Simulation Hamiltonienne dépendante du temps avec mise à l'échelle L1-norm. (Time-dependent Hamiltonian simulation with L1-norm scaling)
Quantum, 4:254, 2020.
[arXiv:1906.07115]
- 468
-
David Poulin, Angie Qarry, Rolando Somma, et Frank Verstraete
Simulation quantique des Hamiltoniens dépendants du temps et l'illusion pratique de l'espace de Hilbert. (Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space)
Physical Review Letters, 106(17):170501, 2011.
[arXiv:1102.1360]
- 469
-
Mária Kieferová, Artur Scherer, et Dominic W. Berry
Simulation de la dynamique des Hamiltoniens dépendants du temps avec une série de Dyson tronquée. (Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series)
Physical Review A, 99(4):042314, 2019.
[arXiv:1805.00582]
- 470
-
Guang Hao Low et Nathan Wiebe
Simulation Hamiltonienne dans l'image d'interaction. (Hamiltonian simulation in the interaction picture)
arXiv:1805.00675, 2018.
- 471
-
Arjan Cornelissen et Yassine Hamoudi
Un algorithme quantique en temps sous-linéaire pour approximer les fonctions de partition. (A sublinear-time quantum algorithm for approximating partition functions)
Dans Proceedings of SODA23, 1245-1264, 2023.
[arXiv:2207.08643]
- 472
-
Arjan Cornelissen, Yassine Hamoudi, Sofiene Jerbi
Algorithmes quantiques presque optimaux pour l'estimation de la moyenne multivariée. (Near-optimal quantum algorithms for multivariate mean estimation)
Dans Proceedings of STOC22, 33-43, 2022.
[arXiv:2111.09787]
- 473
-
Scott Aaronson et Alex Arkhipov
La complexité computationnelle de l'optique linéaire. (The computational complexity of linear optics)
Dans Proceedings of STOC11, 333-342, 2011.
[arXiv:1011.3245]
- 474
-
Dan Shepherd et Michael J. Bremner
Calcul quantique temporellement non structuré. (Temporally unstructured quantum computation)
Dans Proceedings of the Royal Society A, 465(2105):1413-1439, 2009.
[arXiv:0809.0847]
- 475
-
Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang
Algorithmes quantiques pour l'échantillonnage de distributions log-concaves et l'estimation de constantes de normalisation. (Quantum algorithms for sampling log-concave distributions and estimating normalizing constants)
Advances in Neural Information Processing Systems (NeurIPS), 35:23205-23217, 2022.
[arXiv:2210.06539]
- 476
-
Sami Boulebnane et Ashley Montanaro
Résolution de problèmes de satisfaisabilité booléenne avec l'algorithme d'optimisation approximative quantique. (Solving boolean satisfiability problems with the quantum approximate optimization algorithm)
arXiv:2208.06909, 2022.
- 477
-
Ankit Garg, Robin Kothari, Praneeth Netrapalli, et Suhail Sherif
Pas d'accélération quantique par rapport à la descente de gradient pour l'optimisation convexe non lisse. (No quantum speedup over gradient descent for non-smooth convex optimization)
arXiv:2010.01801, 2020.
- 478
-
Jeongwan Haah, Matthew B. Hastings, Robin Kothari, et Guang Hao Low
Algorithme quantique pour simuler l'évolution en temps réel des Hamiltoniens de réseau. (Quantum algorithm for simulating real time evolution of lattice Hamiltonians)
SIAM Journal on Computing, 52(6):10.1137, 2018.
[arXiv:1801.03922]
- 479
-
Andrew M. Childs et Yuan Su
Simulation de réseau presque optimale par formules de produit. (Nearly optimal lattice simulation by product formulas)
Physical Review Letters, 123(5):050503, 2019.
[arXiv:1901.00564]
- 480
-
Tomotaka Kuwahara, Tan Van Vu, et Keiji Saito
Simulation quantique efficace de cônes lumineux et simulation numérique de bosons interactifs. (Effective light cone and digital quantum simulation of interacting bosons)
Nature Communications, 15:2520, 2024.
[arXiv:2206.14736]
- 481
-
Burak Şahinoğlu et Rolando D. Somma
Simulation Hamiltonienne dans le sous-espace d'énergie basse. (Hamiltonian simulation in the low-energy subspace)
npj Quantum Information, 7:119, 2021.
[arXiv:2006.02660]
- 482
-
Weiyuan Gong, Shuo Zhou, et Tongyang Li
Complexité de la simulation quantique numérique dans le sous-espace d'énergie basse : applications et une borne inférieure. (Complexity of digital quantum simulation in the low-energy subspace: applications and a lower bound)
Quantum, 8:1409, 2024.
[arXiv:2312.08867]
- 483
-
Kasra Hejazi, Modjtaba Shokrian Zini, et Juan Miguel Arrazola
Meilleures bornes pour les formules de produit à faible énergie. (Better bounds for low-energy product formulas)
arXiv:2402.10362, 2024.
- 484
-
Yu Tong, Victor V. Albert, Jarrod R. McClean, John Preskill, et Yuan Su
Simulation prouvée précise des théories de jauge et des systèmes bosoniques. (Provably accurate simulation of gauge theories and bosonic systems)
Quantum, 6:816, 2022.
[arXiv:2110.06942]
- 485
-
Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, et Kevin Tian
Accélérations quantiques pour les jeux à somme nulle via un échantillonnage dynamique Gibbs amélioré. (Quantum Speedups for zero-sum games via improved dynamic Gibbs sampling)
Proceedings of ICML23, 2023.
[arXiv:2301.03763]
- 486
-
Joran van Apeldoorn et András Gilyén
Algorithmes quantiques pour les jeux à somme nulle. (Quantum algorithms for zero-sum games)
arXiv:1904.03180, 2019.
- 487
-
Sam McArdle, András Gilyén, et Mario Berta
Un algorithme quantique rationalisé pour l'analyse de données topologiques avec exponentiellement moins de qubits. (A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits)
arXiv:2209.12887, 2022.
- 488
-
Bernardo Ameneyro, Vasileios Maroulas, et George Siopsis
Homologie persistante quantique. (Quantum persistent homology)
Journal of Applied and Computational Topology, 1-20, 2024.
[arXiv:2202.12965]
- 489
-
Ryu Hayakawa
Algorithme quantique pour les nombres de Betti persistants et l'analyse de données topologiques. (Quantum algorithm for persistent Betti numbers and topological data analysis)
Quantum, 6:873, 2022.
[arXiv:2111.00433]
- 490
-
Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput,
Nathan Wiebe, Vedran Dunjko, et Ryan Babbush
Analyse des perspectives d'avantage quantique dans l'analyse de données topologiques. (Analyzing prospects for quantum advantage in topological data analysis)
PRX Quantum, 5:010319, 2022.
[arXiv:2209.13581]
- 491
-
Zoe Holmes, Gopikrishnan Muraleedharan, Rolando D. Somma, Yigit Subasi, et Burak Şahinoğlu
Algorithmes quantiques issus des théorèmes de fluctuation : préparation d'état thermique. (Quantum algorithms from fluctuation theorems: Thermal-state preparation)
Quantum, 6:825, 2022.
[arXiv:2203.08882]
- 492
-
Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, et Fernando G.S.L. Brandão
Attention à l'écart : atteindre une accélération quantique super-Grover en sautant à la fin. (Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end)
Proceedings of STOC23, 1131 - 1144, 2023.
[arXiv:2212.01513]
- 493
-
M. B. Hastings
Un algorithme quantique à chemin court pour l'optimisation exacte. (A short path quantum algorithm for exact optimization)
Quantum, 2:78, 2018.
[arXiv:1802.10124]
- 494
-
Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, et Dominic W. Berry
Résolveur de systèmes linéaires quantiques à mise à l'échelle optimale via le théorème adiabatique discret. (Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem)
PRX Quantum, 3:040303, 2022.
[arXiv:2111.08152]
- 495
-
Tobias J. Osborne et Alexander Stottmeister
Simulation quantique de la théorie des champs conformes. (Quantum simulation of conformal field theory)
arXiv:2109.14214, 2021.
- 496
-
Changhao Yi et Elizabeth Crosson
Analyse spectrale des formules de produit pour la simulation quantique. (Spectral analysis of product formulas for quantum simulation)
npj Quantum Information, 8:38, 2022.
[arXiv:2102.12655]
- 497
-
Yanlin Chen et Ronald de Wolf
Algorithmes quantiques et bornes inférieures pour la régression linéaire avec contraintes de norme. (Quantum algorithms and lower bounds for linear regression with norm constraints)
arXiv:2110.13086, 2021.
- 498
-
Yilei Chen, Qipeng Liu, et Mark Zhandry
Algorithmes quantiques pour des variantes de problèmes de réseau en moyenne via le filtrage. (Quantum algorithms for variants of average-case lattice problems via filtering)
Proceedings of EUROCRYPT22, 372 - 401, 2022.
[arXiv:2108.11015]
Stephen Jordan