Existe-t-il des problèmes dans lesquels les ordinateurs quantiques sont connus pour fournir un avantage exponentiel?

Il est généralement admis et affirmé que les ordinateurs quantiques peuvent surpasser les appareils classiques dans au moins certaines tâches.

L' un des exemples d'un problème le plus fréquemment cités dans les ordinateurs quantiques seraient surperformer les dispositifs classiques est , mais là encore, il est ne sait pas si est aussi efficace résoluble avec un ordinateur classique (qui est, si ).$\text{Factoring}$$\text{Factoring}$$\text{Factoring}\in \text{P}$

Pour d'autres problèmes couramment cités dans lesquels les ordinateurs quantiques sont connus pour fournir un avantage, tels que la recherche dans la base de données, l'accélération n'est que polynomiale.

Y a-t-il des cas connus de problèmes dans lesquels il peut être démontré (prouvé ou prouvé sous de fortes hypothèses de complexité de calcul) que les ordinateurs quantiques fourniraient un avantage exponentiel?

Supposons qu'une fonction ait la propriété curieuse suivante: Il existe s ∈ { 0 , 1 } n tel que f ( x ) = f ( y ) si et seulement si x + y = s . Si s = 0 est la seule solution, cela signifie que f est 1 à 1; sinon il y a une valeur non nulle de telle sorte que f ( x $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$$s \in \{0,1\}^n$$f(x) = f(y)$$x + y = s$$s = 0$$f$$s$ pour tout x , ce qui, parce que 2 = 0 , signifie que f est 2 pour 1.$f(x) = f(x + s)$$x$$2 = 0$$f$

Quel est le coût, pour une probabilité de réussite prescrite, sur un ordinateur classique ou quantique, de distinguer une fonction aléatoire uniforme 1-à-1 d'une fonction aléatoire aléatoire 2-à-1 satisfaisant cette propriété, si chaque option (1 à -1 ou 2 à 1) a une probabilité égale?

C'est-à-dire que je lance secrètement une pièce; si je reçois des têtes je vous remets un circuit de boîte noire (classique ou quantique, resp.) pour une fonction aléatoire uniforme de 1 à 1 , alors que si je reçois des queues je vous donne un circuit de boîte noire pour un aléatoire uniforme de 2 à -1 fonction f . Combien devez-vous payer pour obtenir une probabilité de succès prescrite p de dire si j'ai des têtes ou des queues?$f$$f$$p$

C'est le scénario de l'algorithme de Simon . Elle a des applications ésotériques dans cryptanalyse aucun sens , ^* et il était un instrument au début de l' étude des classes de complexité BQP et BPP et un début d' inspiration pour l'algorithme de Shor.

Simon a présenté un algorithme quantique (§3.1, p. 7) qui coûte qubits et le temps O ( n ⋅ T f ( n ) + G ( n ) ) prévu pour une probabilité proche de 1 de réussite, où T f ( n ) est le temps pour calculer une superposition de valeurs de f sur une entrée de taille n et où G ( n ) est le temps pour résoudre un$O(n + |f|)$$O(n \cdot T_f(n) + G(n))$$T_f(n)$$f$$n$$G(n)$ système d'équations linéaires dans F 2 .$n \times n$$\mathbb F_2$

Simon a ensuite esquissé une preuve (théorème 3.1, p. 9) qu'un algorithme classique évaluant à pas plus de 2 n / 4 valeurs distinctes distinctes ne peut pas deviner la pièce avec un avantage meilleur que 2 - n / 2 sur une supposition aléatoire uniforme.$f$$2^{n/4}$$2^{-n/2}$

Dans un certain sens, cela répond positivement à votre question: un calcul quantique nécessitant un nombre linéaire d'évaluations de fonction aléatoire sur une superposition quantique d'entrées peut atteindre une bien meilleure probabilité de succès qu'un calcul classique nécessitant un nombre exponentiel d'évaluations d'une fonction aléatoire sur discret entrées , dans la taille des entrées. Mais dans un autre sens, cela ne répond pas du tout à votre question, car il se pourrait que pour chaque fonction particulière il existe un moyen plus rapide de calculer la recherche.$f$

L' algorithme de Deutsch – Jozsa sert d'illustration similaire à un problème artificiel légèrement différent pour étudier différentes classes de complexité, P et EQP, dont les détails sont laissés en exercice au lecteur.

_{^* Simon n'a pas de sens pour la cryptanalyse, car seul un idiot inconcevablement confus alimenterait sa clé secrète dans le circuit quantique de l'adversaire pour l'utiliser sur une superposition quantique d'entrées, mais pour une raison quelconque, il fait sensation à chaque fois que quelqu'un publie un nouvel article sur l'utilisation de l'algorithme de Simon. briser les clés des idiots avec du matériel imaginaire, c'est ainsi que fonctionnent toutes ces attaques. Exception: il est possible que cela brise la cryptographie en boîte blanche , mais l'histoire de la sécurité de la cryptographie en boîte blanche, même contre les adversaires classiques, n'est pas prometteuse.}

Je ne sais pas si c'est exactement ce que vous recherchez; et je ne sais pas si je qualifierais cela d '"exponentiel" (je ne suis pas non plus un informaticien donc ma capacité à faire des analyses d'algorithmes est plus ou moins inexistante ...), mais un résultat récent de Bravyi et. al a présenté une classe de «problèmes de fonction linéaire cachée 2D» qui utilisent de manière prouvée moins de ressources sur un dispositif parallèle quantique.

$N\times N$$A$$b$$q$

$\log{N}$$>7/8$

La preuve revient essentiellement à un état de graphe spécifique étant difficile à simuler pour un circuit classique, ce sous-résultat a été prouvé un peu plus tôt . Ensuite, le reste de l'article montre que la plus grande classe de problèmes contient ce problème difficile.

$\neq$

$\textbf{BPP}^O \neq \textbf{BQP}^O$ $\neq$

Bien que je ne puisse pas fournir de preuve formelle, la simulation (de l'évolution temporelle) d'un système quantique est supposée être un tel cas: il n'y a pas de meilleure façon connue de le faire sur un ordinateur classique qu'en temps exponentiel mais un ordinateur quantique peut le faire trivialement en temps polynomial.

L'idée d'un tel simulateur quantique (voir également l' article de wikipedia ) est en fait la première proposition des ordinateurs quantiques.