Si P = NP était vrai, les ordinateurs quantiques seraient-ils utiles?

29

Supposons que P = NP soit vrai. Y aurait-il alors une application pratique à la construction d'un ordinateur quantique, telle que la résolution plus rapide de certains problèmes, ou une telle amélioration serait-elle sans pertinence étant donné que P = NP est vrai? Comment caractériseriez-vous l'amélioration de l'efficacité qui se produirait si un ordinateur quantique pouvait être construit dans un monde où P = NP, par opposition à un monde dans lequel P! = NP?

Voici un exemple inventé de ce que je recherche:

Si P! = NP, nous voyons que la classe de complexité ABC est égale à la classe de complexité quantique XYZ ... mais si P = NP, la classe ABC s'effondre quand même dans la classe associée UVW.

(Motivation: je suis curieux à ce sujet et relativement nouveau pour l'informatique quantique; veuillez migrer cette question si elle n'est pas suffisamment avancée.)

Philip White
la source
9
Nous ne savons pas si implique B Q P = P , de sorte qu'il pourrait y avoir un problème dans B Q P qui n'est pas dans P même si P = N P .... C'est même aussi une question ouverte de savoir si ou pas B Q P est en P H ....P=NPBQP=PBQPPP=NPBQPPH
Tayfun Pay
4
Plus fondamentalement, la classe capture des algorithmes quantiques «efficaces» (temps polynomial quantique à erreur bornée). C'est pourquoi la formalisation par Tayfun de votre question est la plus naturelle, par exemple si P = N P , y a-t-il encore des problèmes dans P , mais pas dans B Q P ? Et apparemment, cela est conforme à nos connaissances actuelles que cela se produit. BQPP=NPPBQP
usul

Réponses:

30

L'article " BQP et la hiérarchie polynomiale " de Scott Aaronson répond directement à votre question. Si P = NP, alors PH s'effondrerait. Si de plus BQP était en PH, aucune accélération quantique ne serait possible dans ce cas. D'un autre côté, Aaronson donne la preuve d'un problème d'accélération quantique en dehors du PH, donc une telle accélération survivrait à un effondrement du PH.

Martin Schwarz
la source
10
En fait, Aaronson lui-même a prouvé que la conjecture qu'il était basé sur ce travail était fausse. Voir scottaaronson.com/papers/glnfalse.pdf
Alex Grilo
5
@AlexGrilo Certains des résultats de l'article étaient inconditionnels et sont toujours valables: il existe une séparation oracle entre les versions relationnelles de BQP et de PH.
Sasho Nikolov
8
Une clarification: alors que la "Conjecture Liniale-Nisan Généralisée" s'est avérée fausse, la conjecture selon laquelle le problème de vérification de Fourier / "Forrelation" n'est pas en PH reste valable. C'est juste qu'une autre approche sera nécessaire pour le prouver. Aussi, je peux renforcer mon résultat qu'il existe un oracle par rapport auquel il y a des problèmes de relation BQP pas dans BPP ^ PH, pour montrer qu'il existe un oracle par rapport auquel P = NP, mais il y a encore des problèmes de relation BQP pas dans BPP . C'est une extension simple, mais malheureusement je ne l'ai pas encore écrite.
Scott Aaronson
9

La réponse est un oui sans équivoque. Les ordinateurs quantiques seraient certainement encore utiles.

Les ordinateurs quantiques ne sont pas des oracles pour BQP, mais plutôt des dispositifs qui traitent des états quantiques et peuvent communiquer en utilisant des états quantiques. Tout comme la capacité de faire des requêtes non déterministes est fondamentalement plus puissante que la capacité de faire des requêtes purement déterministes, indépendamment du statut de P vs NP (et en fait c'est la racine des séparations d'oracle), la capacité de faire des requêtes quantiques et communiquer en utilisant des états quantiques est fondamentalement plus puissant que son homologue purement classique.

Cela conduit à des avantages dans une large gamme d'applications

  1. La possibilité d'interroger des oracles ou des bases de données externes en superposition fournit une séparation prouvable entre les ordinateurs quantiques et les ordinateurs classiques en termes de complexité des requêtes.
  2. Il existe une variété de tâches de communication qui entraînent des réductions drastiques des coûts de communication grâce à la communication quantique.
  3. Le traitement de l'information quantique permet de disposer de protocoles théoriquement sûrs pour un éventail de problèmes plus large que ce qui est classiquement possible. Certes, QKD ne nécessite pas la mise en œuvre d'un ordinateur quantique universel, mais de nombreux protocoles pour d'autres tâches le font.
  4. Le pré et le post-traitement de grands états quantiques intriqués vous permettent de violer la limite de bruit de tir en métrologie, ce qui donne des mesures plus précises.

Outre les arguments de complexité, il existe une autre raison pratique de vouloir des ordinateurs quantiques. Une grande partie des données traitées sur les ordinateurs classiques ces jours-ci provient de la détection du monde naturel (par exemple via le CCD dans un appareil photo numérique). Cependant, de telles mesures jettent nécessairement certaines informations sur le système afin de rendre le résultat de la mesure sous la forme d'une chaîne de bits classique (par exemple, la superposition spatiale de photons) et il n'est pas toujours clair quelles informations seront plus tard considérées comme les plus importantes lorsque enregistrer initialement les données. Il est donc raisonnable de croire que la capacité de stocker et de traiter directement des états quantiques, plutôt que de les réduire d'une certaine manière avant le traitement, deviendra de plus en plus souhaitable.

Joe Fitzsimons
la source
4

Aborder la partie pratique.

P=NPO(n2dix3)

O(ndix10000)

Autant que je sache, un ordinateur quantique suffisamment puissant sera d'un intérêt pratique dans ce cas.

joro
la source
n2dix3
Sasho Nikolov
@SashoNikolov J'ai abordé la question pratique . Un ordinateur quantique qui factorise efficacement les entiers de 2048 bits serait pour moi d'un intérêt pratique à cause des clés RSA;).
joro
Je crois que l'on peut obtenir des algorithmes de tri temporel linéaire avec des ordinateurs quantiques.
Baby Dragon
2

Il existe des études sur la relation entre BQP et la hiérarchie polynomiale PH. Par exemple, il y a un problème par rapport auquel BQP n'est pas contenu dans PH ( http://arxiv.org/abs/0910.4698 ), et une conjecture qui prouve le même résultat dans un monde non relativisé ( http://arxiv.org /abs/1007.0305P#PBPPPH

En conclusion, nous ne savons pas quelle est la puissance exacte des ordinateurs quantiques, mais certains résultats suggèrent que le BQP pourrait être en dehors du PH.

néophyte
la source