Existe-t-il une déclaration générale sur les types de problèmes qui peuvent être résolus plus efficacement en utilisant un ordinateur quantique?

Existe-t-il une déclaration générale sur les types de problèmes qui peuvent être résolus plus efficacement en utilisant des ordinateurs quantiques (modèle à porte quantique uniquement)? Les problèmes pour lesquels un algorithme est connu aujourd'hui ont-ils une propriété commune?

Autant que je sache, l'informatique quantique aide à résoudre le problème des sous-groupes cachés (Shor); L'algorithme de Grover permet d'accélérer les problèmes de recherche. J'ai lu que les algorithmes quantiques peuvent fournir une accélération si vous recherchez une «propriété globale» d'une fonction (Grover / Deutsch).

1. Existe-t-il un énoncé plus concis et correct sur la manière dont l'informatique quantique peut aider?
2. Est-il possible d'expliquer pourquoi la physique quantique peut y aider (de préférence quelque chose de plus profond que «les interférences peuvent être exploitées»)? Et pourquoi cela n'aidera probablement pas pour d'autres problèmes (par exemple pour des problèmes NP-complets)?

Y a-t-il des articles pertinents qui en discutent exactement?

J'avais déjà posé cette question sur cstheory.stackexchange.com mais elle peut être plus appropriée ici.

Sur l'utilité du calcul en général

Sans vous en rendre compte, vous posez une version de l'une des questions les plus difficiles que vous puissiez poser sur l'informatique théorique. Vous pouvez poser la même question sur les ordinateurs classiques, mais au lieu de demander si l'ajout de «quantumness» est utile, vous pouvez demander:

• Existe-t-il une déclaration concise sur la manière dont les algorithmes randomisés peuvent aider?

  Il est possible de dire quelque chose de très vague ici - si vous pensez que les solutions sont abondantes (ou que le nombre de solutions à un sous-problème est abondant) mais qu'il peut être difficile d'en construire systématiquement un, alors il est utile de pouvoir faire choix au hasard pour dépasser le problème de la construction systématique. Mais attention, parfois la raison pour laquelle vous savez qu'il existe de nombreuses solutions à un sous-problème est qu'il existe une preuve utilisant la méthode probabiliste . Lorsque c'est le cas, vous savez que le nombre de solutions est abondant par réduction à ce qui est en fait un algorithme randomisé utile!

  Sauf si vous avez une autre façon de justifier le fait que le nombre de solutions est abondant pour ces cas, il n'y a pas de description simple du moment où un algorithme aléatoire peut aider. Et si vous avez suffisamment d'exigences d'utilité (un avantage superpolynomial), alors ce que vous demandez, c'est si , qui est un problème non résolu dans la théorie de la complexité. $\mathsf P \ne \mathsf{BPP}$
  
  

• Existe-t-il une déclaration concise sur la manière dont les algorithmes parallélisés peuvent aider?

  Ici, les choses peuvent être un peu mieux. Si un problème semble pouvoir être décomposé en de nombreux sous-problèmes indépendants, alors il peut être mis en parallèle - bien que ce soit un vague, "vous le saurez quand vous le verrez" une sorte de critère. La question principale est, le saurez- vous quand vous le verrez? Auriez-vous deviné que tester la faisabilité de systèmes d'équations linéaires sur les rationnels est non seulement parallélisable, mais pourrait être résolu en utilisant des circuits de profondeur [cf  Comput. Complexe. 8 (pp. 99-126), 1999 ]?$O(\log^2 n)$

  Une façon dont les gens essaient de brosser un tableau d'ensemble est d'approcher la question de la direction opposée et de dire quand on sait qu'un algorithme parallélisé n'aidera pas . Plus précisément, cela n'aidera pas si le problème a un aspect intrinsèquement séquentiel. Mais c'est circulaire, car «séquentiel» signifie simplement que la structure que vous pouvez voir pour le problème n'est pas parallèle.

  Encore une fois, il n'y a pas de description simple et complète du moment où un algorithme parallélisé peut aider. Et si vous avez suffisamment d'exigences d'utilité (une limite supérieure poly-logarithmique sur la quantité de temps, en supposant une parallélisation polynomiale), alors ce que vous demandez, c'est si $\mathsf P \ne \mathsf{NC}$ , qui est encore un problème non résolu dans la théorie de la complexité .
  
  

Les perspectives de «descriptions concises et correctes du moment où [X] est utile» ne semblent pas trop grandes à ce stade. Bien que vous puissiez protester que nous sommes trop stricts ici: au motif d'exiger plus qu'un avantage polynomial, nous ne pouvions même pas prétendre que les machines de Turing non déterministes étaient `` utiles '' (ce qui est clairement absurde). Nous ne devrions pas exiger une barre aussi élevée - en l'absence de techniques pour résoudre efficacement la satisfiabilité, nous devrions au moins accepter que si nous pouvions en quelque sorte obtenir une machine de Turing non déterministe, nous la trouverions en effet très très utile . Mais c'est différent de pouvoir caractériser précisément les problèmes pour lesquels nous trouverions cela utile.

Sur l'utilité des ordinateurs quantiques

En prenant du recul, y a-t-il quelque chose que nous puissions dire sur les domaines où les ordinateurs quantiques sont utiles?

Nous pouvons dire ceci: un ordinateur quantique ne peut faire quelque chose d'intéressant que s'il profite de la structure d'un problème, qui n'est pas disponible pour un ordinateur classique. (Ceci est indiqué par les remarques sur la «propriété globale» d'un problème, comme vous le mentionnez). Mais nous pouvons en dire plus: les problèmes résolus par les ordinateurs quantiques dans le modèle de circuit unitaire instancieront certaines caractéristiques de ce problème en tant qu’opérateurs unitaires . Les caractéristiques du problème qui ne sont pas disponibles pour les ordinateurs classiques seront toutes celles qui n'ont pas de relation statistiquement significative (prouvée) avec la base standard.

• Dans le cas de l'algorithme de Shor, cette propriété est les valeurs propres d'un opérateur de permutation qui est défini en termes de multiplication sur un anneau.
• Dans le cas de l'algorithme de Grover, cette propriété est de savoir si la réflexion sur l'ensemble des états marqués commute avec la réflexion sur la superposition uniforme - cela détermine si l'itérateur Grover a des valeurs propres qui ne sont pas .$\pm 1$

Il n'est pas particulièrement surprenant de voir que dans les deux cas, les informations se rapportent aux valeurs propres et aux vecteurs propres. Il s'agit d'un excellent exemple de propriété d'un opérateur qui n'a pas besoin d'avoir de relation significative avec la base standard. Mais il n'y a aucune raison particulière pour laquelle l'information doit être une valeur propre. Tout ce qui est nécessaire est de pouvoir décrire un opérateur unitaire, encodant une caractéristique pertinente du problème qui n'est pas évidente lors de l'inspection de la base standard, mais qui est accessible d'une autre manière facilement décrite.

En fin de compte, tout cela dit, c'est qu'un ordinateur quantique est utile lorsque vous pouvez trouver un algorithme quantique pour résoudre un problème. Mais au moins, c'est un aperçu général d'une stratégie pour trouver des algorithmes quantiques, ce qui n'est pas pire que les grandes lignes des stratégies que j'ai décrites ci-dessus pour les algorithmes randomisés ou parallélisés.

Remarques sur le moment où un ordinateur quantique est «utile»

Comme d'autres l'ont remarqué ici, «où l'informatique quantique peut aider» dépend de ce que vous entendez par «aide».

• L'algorithme de Shor est souvent évoqué dans de telles discussions, et de temps en temps les gens remarqueront que nous ne savons pas que la factorisation n'est pas résoluble en temps polynomial. Savons-nous donc que "l'informatique quantique serait utile pour factoriser les nombres"?

  Mis à part la difficulté de réaliser des ordinateurs quantiques, je pense que la réponse raisonnable est ici «oui»; non pas parce que nous savons que vous ne pouvez pas factoriser efficacement avec des ordinateurs conventionnels, mais parce que nous ne savons pas comment vous le feriez avec des ordinateurs conventionnels. Si les ordinateurs quantiques vous aident à faire quelque chose que vous n'avez pas de meilleure approche, il me semble que cela «aide».

• Vous mentionnez l'algorithme de Grover, qui produit une accélération de racine carrée bien connue par rapport à la recherche par force brute. Il ne s'agit que d'une accélération polynomiale et d'une accélération sur un algorithme classique naïf - nous avons de meilleurs algorithmes classiques que la recherche par force brute, même pour des problèmes concurrents NP . Par exemple, dans le cas d'instances 3-SAT avec une seule affectation satisfaisante, l' algorithme PPSZ a un temps d'exécution de , qui surpasse l'algorithme original de Grover. L'algorithme de Grover est-il donc «utile»?$O(2^{0.386\,n})$

  Peut-être que l'algorithme de Grover en tant que tel n'est pas particulièrement utile. Cependant, il peut être utile si vous l'utilisez pour élaborer des stratégies classiques plus intelligentes au-delà de la recherche par force brute: en utilisant l' amplification en amplitude , la généralisation naturelle de l'algorithme de Grover à des paramètres plus généraux, nous pouvons améliorer les performances de nombreux algorithmes non triviaux pour SAT (voir par exemple [ACM SIGACT News  36 (pp.103-108), 2005 - lien PDF gratuit ]; chapeau à Martin Schwarz qui m'a fait référence à cette référence dans les commentaires).

  Comme pour l'algorithme de Grover, l'amplification d'amplitude ne produit que des accélérations polynomiales: mais en pratique, même une accélération polynomiale peut être intéressante si elle n'est pas effacée par les frais généraux associés à la protection des informations quantiques contre le bruit.

TL; DR: Non, nous n'avons pas de déclaration "générale" précise sur le type exact de problèmes que les ordinateurs quantiques peuvent résoudre , en termes de théorie de la complexité. Cependant, nous avons une idée approximative.

Selon le sous-article de Wikipedia sur la relation avec la théorie de la complexité informatique

La classe de problèmes qui peuvent être résolus efficacement par les ordinateurs quantiques est appelée BQP , pour "erreur bornée, quantique, temps polynomial". Les ordinateurs quantiques exécutent uniquement des algorithmes probabilistes , de sorte que le BQP sur les ordinateurs quantiques est l'équivalent du BPP («erreur bornée, probabiliste, temps polynomial») sur les ordinateurs classiques. Il est défini comme l'ensemble des problèmes pouvant être résolus avec un algorithme à temps polynomial, dont la probabilité d'erreur est limitée à la moitié . Un ordinateur quantique est censé "résoudre" un problème si, dans tous les cas, sa réponse sera exacte avec une forte probabilité. Si cette solution s'exécute en temps polynomial, alors ce problème est en BQP.

BQP est contenu dans la classe de complexité #P (ou plus précisément dans la classe associée de problèmes de décision P ^#P ), qui est une sous-classe de PSPACE .

Le BQP est soupçonné d'être disjoint de NP-complet et d'un sur-ensemble strict de P, mais cela n'est pas connu. La factorisation entière et le log discret sont tous deux en BQP. Ces deux problèmes sont des problèmes de NP soupçonnés d'être en dehors du BPP, et donc en dehors de P. Les deux sont soupçonnés de ne pas être NP-complets. Il existe une idée fausse répandue selon laquelle les ordinateurs quantiques peuvent résoudre des problèmes NP-complets en temps polynomial. Ce n'est pas connu pour être vrai, et est généralement soupçonné d'être faux.

La capacité d'un ordinateur quantique à accélérer les algorithmes classiques a des limites rigides - les limites supérieures de la complexité du calcul quantique. La partie écrasante des calculs classiques ne peut pas être accélérée sur un ordinateur quantique. Un fait similaire se produit pour des tâches de calcul particulières, comme le problème de recherche, pour lequel l'algorithme de Grover est optimal.

${\displaystyle O({\sqrt[{3}]{N}})}$$\displaystyle O({\sqrt {N}})$

Bien que les ordinateurs quantiques puissent être plus rapides que les ordinateurs classiques pour certains types de problèmes, ceux décrits ci-dessus ne peuvent résoudre aucun problème que les ordinateurs classiques ne peuvent pas déjà résoudre. Une machine de Turing peut simuler ces ordinateurs quantiques, de sorte qu'un tel ordinateur quantique ne pourrait jamais résoudre un problème indécidable comme le problème d'arrêt. L'existence d'ordinateurs quantiques «standard» ne réfute pas la thèse de Church-Turing. Il a été émis l'hypothèse que les théories de la gravité quantique, telles que la théorie M ou la gravité quantique en boucle, pourraient permettre la construction d'ordinateurs encore plus rapides. Actuellement, définir le calcul dans de telles théories est un problème ouvert en raison du problème de temps, c'est-à-dire qu'il n'existe actuellement aucun moyen évident de décrire ce que signifie pour un observateur de soumettre des données à un ordinateur et de recevoir des données ultérieurement.

Quant à savoir pourquoi les ordinateurs quantiques peuvent résoudre efficacement les problèmes BQP:

1. $n$$2n$

2. Habituellement, le calcul sur un ordinateur quantique se termine par une mesure. Cela conduit à un effondrement de l'état quantique à l'un des états de base. On peut dire que l'état quantique est mesuré pour être dans le bon état avec une forte probabilité.

Fait intéressant, si nous autorisons théoriquement la post-sélection (qui n'a pas d'implémentation pratique évolutive), nous obtenons la classe de complexité post-BQP :

Dans la théorie de la complexité computationnelle, PostBQP est une classe de complexité composée de tous les problèmes de calcul résolus en temps polynomial sur une machine de Turing quantique avec post-sélection et erreur bornée (dans le sens où l'algorithme est correct au moins 2/3 du temps sur tous les contributions). Cependant, la post-sélection n'est pas considérée comme une caractéristique qu'un ordinateur réaliste (même quantique) possède, mais néanmoins les machines de post-sélection sont intéressantes d'un point de vue théorique.

Je voudrais ajouter ce que le lézard @Discrete a mentionné dans la section des commentaires. Vous n'avez pas explicitement défini ce que vous entendez par "peut aider", cependant, la règle empirique dans la théorie de la complexité est que si un ordinateur quantique "peut aider" en termes de résolution en temps polynomial (avec une erreur liée) si la classe de problème qu'il peut résoudre réside dans BQP mais pas dans P ou BPP. La relation générale entre les classes de complexité dont nous avons discuté ci-dessus est supposée être:

$\text{P $\subseteq$ BPP $\subseteq$ BQP $\subseteq$ PSPACE}$

Cependant, P = PSPACE, est un problème ouvert en informatique . De plus, la relation entre P et NP n'est pas encore connue.

Il n'y a pas une telle déclaration générale et il est peu probable qu'il y en ait une bientôt. Je vais expliquer pourquoi c'est le cas. Pour une réponse partielle à votre question, l'examen des problèmes des deux classes de complexité BQP et PostBQP pourrait vous aider.

Les classes de complexité qui se rapprochent le plus des problèmes pouvant être résolus efficacement par les ordinateurs quantiques du modèle de porte quantique sont

1. BQP ; et
2. PostBQP

BQP se compose des problèmes qui peuvent être résolus en temps polynomial sur un circuit quantique. Les algorithmes quantiques les plus importants, tels que l'algorithme de Shor, résolvent les problèmes de BQP.

$=$

Cependant, il n'existe actuellement aucune méthode pour implémenter pratiquement la post-sélection, donc PostBQP est plus d'intérêt théorique.

La relation entre P, NP et BQP est actuellement inconnue; et un problème ouvert de l'ordre de P vs NP. Comme une déclaration générale sur les types de problèmes qui peuvent être résolus plus efficacement en utilisant des ordinateurs quantiques, il faut répondre à la question BQP vs P (si BQP = P, alors les ordinateurs quantiques ne sont pas plus efficaces (pour les théoriciens de la complexité, au moins))

Semblable à l'image de Blue, j'aime mieux celle du magazine Quanta , car elle semble résumer visuellement ce dont nous parlons.