L'algorithme de Grover et sa relation avec les classes de complexité?

Je suis confus à propos de l'algorithme de Grover et de sa connexion aux classes de complexité.

L'algorithme de Grover trouve et l'élément dans une base de données de (tels que ) des éléments avec appels à l'oracle.N = 2 n f ( k ) = 1 ∼ $k$$N=2^n$$f(k)=1$

Nous avons donc le problème suivant:

Problème: trouver un dans la base de données tel quef ( k ) = $k$$f(k)=1$

Maintenant, je suis conscient que ce n'est pas un problème de conception et donc nos définitions normales de classe de complexité , etc. ne s'appliquent pas vraiment. Mais je suis curieux de savoir comment nous définirions la classe de complexité dans un tel cas - et comment cela se fait-il par rapport à ou ?NP N $\text{P}$$\text{NP}$$N$$n$

De plus, l'algorithme de Grover peut être utilisé comme sous-programme. J'ai lu à plusieurs endroits que l'algorithme de Grover ne change pas la classe de complexité d'un problème - existe-t-il une manière heuristique de voir cela.

Sommaire

• Il existe une théorie de la complexité des problèmes de recherche (également appelés problèmes relationnels). Cette théorie comprend des classes appelées FP , FNP et FBQP qui sont effectivement sur la résolution de problèmes de recherche avec différentes sortes de ressources.
• A partir des problèmes de recherche, vous pouvez également définir des problèmes de décision, ce qui vous permet de relier les problèmes de recherche aux classes habituelles P , NP et BQP .
• Que vous considériez la version de recherche de la version de décision du problème, la façon dont vous considérez l'entrée du problème de recherche non structurée déterminera les limites supérieures que vous pouvez mettre sur sa complexité.

La complexité des problèmes relationnels

Comme vous le constatez, le problème de Grover résout un problème de recherche , qui dans la littérature sur la complexité est parfois également connu sous le nom de problème de relation . Autrement dit, il s'agit d'un problème du type suivant:

La structure d'un problème de recherche général.
Étant donné une entrée et une relation binaire , trouvez un tel que vrai.R y R ( x , y $x$$R$$y$$R(x,y)$

Les classes de complexité FP et FNP sont définies en fonction de tels problèmes, où en particulier on s'intéresse au cas où a au plus une longueur une fonction polynomiale de la longueur de , et où la relation peut elle-même être calculé en un temps limité par un polynôme de la longueur de .x R ( x , y ) ( x , y $y$$x$$R(x,y)$$(x,y)$

En particulier: l'exemple du problème de «recherche de base de données» pour lequel la recherche de Grover est généralement appliquée peut être décrit comme suit.

Recherche non structurée.
Étant donné un oracle d'entrée tels que pour une fonction , trouvez un tel que . O | un ⟩ | b ⟩ = | un ⟩ | b ⊕ f ( a ) ⟩ f : { 0 , 1 } m → { 0 , 1 } y O | y ⟩ | 0 ⟩ = | y ⟩ | 1 $\mathcal O: \mathcal H_2^{\otimes m+1} \!\to \mathcal H_2^{\otimes m+1}$$\mathcal O \lvert a \rangle \lvert b \rangle = \lvert a \rangle \lvert b \oplus f(a) \rangle$$f: \{0,1\}^m \to \{0,1\}$$y$$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Ici, l'oracle lui-même est l'entrée du problème: il joue le rôle de , et la relation que nous calculons est R ( O , y $x$

Supposons qu'au lieu d'un oracle, on nous fournisse une entrée spécifique qui décrit comment la fonction doit être calculée, nous pouvons alors considérer à quelle classe de complexité ce problème appartient. Comme indiqué , la classe de complexité appropriée que nous obtenons dépend de la façon dont l'entrée est fournie.$x$$f$pyramids

• Supposons que la fonction d'entrée soit fournie sous forme de base de données (comme le problème est parfois décrit), où chaque entrée de la base de données a une certaine longueur . Si est la longueur de la chaîne utilisée pour décrire la base de données entière , alors la base de données a entrées. Il est alors possible de rechercher exhaustivement la base de données entière en interrogeant chacune des entrées en séquence, et de s'arrêter si l'on trouve une entrée telle que . En supposant que chaque requête dans la base de données prend quelque chose comme , cette procédure s'arrête dans le tempsn x N = n / ℓ N y f ( y ) = 1 O ( log N ) ⊆ O ( log n ) O ( N log N ) ⊆ O ( n log n $\ell$$n$$x$$N = n\big/\ell$$N$$y$$f(y) = 1$$O(\log N) \subseteq O(\log n)$$O(N \log N) \subseteq O(n \log n)$, de sorte que le problème se trouve dans FP .

  En supposant que la recherche de base de données peut être effectuée en superposition cohérente, l'algorithme de Grover permet que ce problème se trouve dans FBQP . Cependant, comme FP  ⊆  FBQP , la recherche exhaustive classique prouve également que ce problème est en FBQP . Tout ce que nous obtenons (jusqu'aux facteurs de journalisation) est une accélération quadratique en raison d'une économie dans le nombre de requêtes de base de données.
  
  

• Supposons que la fonction d'entrée soit décrite succinctement, par un algorithme polynomial qui prend une spécification et un argument et calculesur une base standard, état , où peut être beaucoup plus grand que . Un exemple serait où spécifie la forme CNF d'une fonction booléenne pour , auquel cas nous pouvons évaluer efficacement sur une entrée y ∈ { 0 , 1 } m O : H m + 1$x \in \{0,1\}^n$$y \in \{0,1\}^m$$\mathcal O : \mathcal H_2^{m+1} \!\to \mathcal H_2^{m+1}\!$m Ω ( log n ) x f : { 0 , 1 } m → { 0 , 1 } m ∈ O ( n ) f ( y ) y ∈ { 0 , 1 } m $\lvert y \rangle\lvert b \rangle$$m$$\Omega(\log n)$$x$$f: \{0,1\}^m \to \{0,1\}$$m \in O(n)$$f(y)$$y \in \{0,1\}^m$et ainsi évaluer efficacement sur des états de base standard. Cela pose le problème dans FNP .$\mathcal O$

  Étant donné une procédure pour évaluer partir de dans le temps pour , l'algorithme de Grover résout le problème de la recherche non structurée de dans le temps . Ce n'est pas un polynôme en , et ne suffit donc pas pour mettre ce problème en FBQP : nous n'obtenons qu'une accélération quadratique - bien que ce soit encore une économie potentiellement énorme de temps de calcul, en supposant que l'avantage fourni par l'algorithme de Grover ne soit pas perdu pour la surcharge requise pour le calcul quantique tolérant aux pannes.( x , y ) O ( p ( n ) ) n = | x | O O ( p ( n ) $f(y)$$(x,y)$$O(p(n))$$n = \lvert x \rvert$$\mathcal O$⊆O(p(n)$O(p(n) \sqrt{2^m})$ $\subseteq O(p(n) \sqrt{2^n})$$n$
  
  

Dans les deux cas, la complexité est déterminée en fonction de la longueur de la chaîne * qui indique comment calculer l'oracle . Dans le cas où représente une table de correspondance, nous avons , auquel cas la performance en fonction de est similaire à la performance en fonction de ; mais dans le cas où spécifie succinctement , et , le message général que Grover résout le problème dansx O x N = n / ℓ N n x O N ∈ O ( 2 n / 2 ) O ( $n$$x$$\mathcal O$$x$$N = n\big/\ell$$N$$n$$x$$\mathcal O$$N \in O(2^{n/2})$$O(\sqrt N)$ les requêtes obscurcissent le message plus fin que cet algorithme est toujours à temps exponentiel pour un ordinateur quantique.

Complexité de la décision due aux problèmes relationnels

Il existe un moyen simple d'obtenir des problèmes de décision à partir de problèmes relationnels, ce qui est bien connu de la théorie des problèmes NP- complets : transformer le problème de recherche en une question de l'existence d'une solution valide.

La version de décision d'un problème de recherche général.
Étant donné une entrée et une relation binaire , déterminez si est valable.R ∃ y : R ( x , y $x$$R$$\exists y: R(x,y)$

La classe de complexité NP peut être essentiellement définie en termes de tels problèmes, lorsque la relation est efficacement calculable: les problèmes NP les plus connus (CNF-SAT, HAMCYCLE, 3-COLORING) concernent la simple existence d'une solution valable pour un problème de relation efficacement vérifiable. Ce passage de la production de solutions à la simple affirmation de l'existence de solutions est aussi ce qui nous permet de décrire les versions de factorisation entière qui sont en BQP (en demandant s'il existe des facteurs non triviaux, plutôt que de demander les valeurs des facteurs non triviaux) .$R$

Dans le cas de la recherche non structurée, la classe de complexité qui décrit le mieux le problème dépend à nouveau de la structure de l'entrée. Déterminer s'il existe une solution à un problème relationnel peut se réduire à trouver et à vérifier une solution à ce problème. Ainsi, dans le cas où l'entrée est une chaîne spécifiant l'oracle comme table de correspondance, le problème de la recherche non structurée est dans P ; et plus généralement si spécifie un moyen efficace d'évaluer l'oracle, le problème est en NP . Il est également possible qu'il existe un moyen de déterminer s'il existe$x$$x$ une solution pour la recherche non structurée qui le fait sans trouver réellement une solution, bien qu'il ne soit pas clair en général comment le faire d'une manière qui fournirait un avantage sur la recherche d'une solution.

Complexité Oracle

J'ai visiblement été en train de passer de parler de l'oracle , de manière qu'une entrée peut être utilisé pour spécifier (et évaluer) l'oracle . Mais bien sûr, la principale façon dont nous considérons l'algorithme de Grover est comme un résultat oracle dans lequel l'évaluation de l'oracle prend un seul pas de temps et ne nécessite aucune spécification. Comment considérons-nous la complexité du problème dans ce cas? x $\mathcal O$$x$$\mathcal O$

Dans ce cas, nous avons affaire à un modèle de calcul relativisé , dans lequel l'évaluation de cet oracle spécifique (qui, rappelez-vous, est l'entrée du problème) est une opération primitive. Cet oracle est défini sur toutes les tailles d'entrée: pour considérer le problème de recherche sur les chaînes de longueur , vous devez spécifier que vous envisagez la façon dont l'oracle agit sur les entrées de longueur , ce qui serait encore fait en considérant la longueur d'une chaîne booléenne prise en entrée. Dans ce cas, la manière dont nous présenterions le problème pourrait être la suivante. n O n $\mathcal O$$n$$\mathcal O$$n$$x$

Recherche déstructuré par rapport à Oracle . $\mathcal O$ Étant donné une entrée de longueur , x=11⋯1n
$x = 11\cdots 1$$n$

• trouver un (problème de relation) ou$y \in \{0,1\}^n$

• déterminer s'il existe un (problème de décision)$y \in \{0,1\}^n$

de telle sorte que .$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Ce problème se trouve dans (pour le problème de décision) ou (pour le problème de relation), selon la version du problème que vous souhaitez résoudre. considérer. Étant donné que l'algorithme de Grover n'est pas un algorithme polynomial, ce problème n'est pas connu pour être dans ou . En fait, nous pouvons dire quelque chose de plus fort, comme nous le verrons bientôt.$\mathsf{NP}^{\mathcal O}$$\mathsf{FNP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$$\mathsf{FBQP}^{\mathcal O}$

La raison pour laquelle j'ai effleuré la description réelle, basée sur Oracle, de la recherche non structurée était pour aborder votre point de complexité, et en particulier pour aborder la question de la taille des entrées . La complexité des problèmes est largement régie par la façon dont les entrées sont spécifiées: comme spécification succincte (dans le cas de la façon dont une fonction est spécifiée dans CNF-SAT), comme spécification explicite (dans le cas d'une table de recherche pour un , ou même comme un entier spécifié en unaire, c'est-à-dire comme la longueur d'une chaîne de 1 comme ci-dessus (comme dans "Recherche non structurée relative à Oracle " ci-dessus).$\mathcal O$

Comme nous pouvons le voir dans ce dernier cas, si nous ne traitons l'entrée que comme un oracle, la situation semble un peu peu intuitive et il est certainement impossible de parler des façons dont la "base de données" peut être réalisée. Mais une vertu de considérer la version relativisée du problème, avec un véritable oracle, est que nous pouvons prouver des choses que nous ne savons pas comment prouver autrement. Si nous pouvions prouver que la version décisionnelle du problème de recherche succincte non structurée se trouvait dans BQP , nous réaliserions alors une énorme percée dans le calcul pratique; et si nous pouvions prouver que le problème de décision n'était pas réellement dans BQP , alors nous aurions montré que P ≠ PSPACE, ce qui représenterait une énorme percée dans la complexité informatique. Nous ne savons pas non plus comment faire. Mais pour le problème relativisé, nous pouvons montrer qu'il existe des oracles pour lesquels la version de décision de "Recherche non structurée relative à " est dans mais pas dans . Cela nous permet de montrer que bien que l'informatique quantique soit potentiellement puissante, il y a des raisons de s'attendre à ce que BQP ne contienne probablement pas NP , et que la version relationnelle de la recherche non structurée en particulier ne soit probablement pas contenue dans FBQP sans imposer de fortes contraintes sur la façon dont l'entrée est représentée.$\mathcal O$$\mathcal O$$\mathsf{NP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$

Les classes de complexité sont généralement définies en fonction de la taille de l'entrée. Les tailles pertinentes ici sont (le nombre de qubits sur lesquels vous laissez l'algorithme de Grover fonctionner) et un nombre que vous n'avez pas encore mentionné, appelez-le , de bits nécessaires pour décrire le sous-programme généralement appelé l'oracle. En règle générale, l'oracle sera efficacement implémenté d'une manière qui évolue polynomialement en , ce qui est le cas, par exemple, si vous encodez un problème de satisfiabilité booléenne typique dans l'oracle.$n$$m$$n$

Dans tous les cas, vous n'obtenez pas de gain de classe de complexité en utilisant l'algorithme de Grover: il faut exponentiellement de nombreuses opérations quantiques, généralement , pour résoudre un problème que nous pourrions forcer en force de manière exponentielle en plusieurs étapes, généralement , sur un ordinateur classique de toute façon. Cela signifie que les problèmes connus (par exemple EXPTIME) ou suspectés (par exemple NP) de prendre un runtime exponentiel nécessiteront toujours un runtime exponentiel.$m*2^{n/2}$$m*2^{n-1}$

Cependant, les physiciens aiment faire appel à l'idée qu'il s'agit toujours d'une accélération exponentielle sans équivalent classique connu (ou même facilement concevable). Cela est plus évident dans l'exemple de base de données où la fonction oracle est une recherche dans la base de données et l'algorithme de Grover peut obliger une personne à avoir besoin de beaucoup moins de recherches que de données dans la base de données. En ce sens, il y a toujours un avantage significatif, bien qu'il soit complètement perdu dans l'image de la classe de complexité.

Tout comptage se fait en termes de , le nombre de bits requis pour décrire l'entrée.$n$

Nous définissons la classe de problèmes de la manière suivante (ou, c'est une façon de le faire):$\text{NP}$

Soit une fonction qui accepte une entrée et renvoie une valeur de bit unique 0 ou 1. La tâche est que vous devez trouver si une valeur donnée de renvoie un 1. Cependant, il y a une autre structure au problème: si , vous êtes assuré qu'il existe une preuve (de taille ) telle qu'une fonction seulement si , et la fonction est efficacement calculable (c'est-à-dire qu'elle a un temps d'exécution de .$f(x)$$x\in\{0,1\}^n$$x$$f(x)=1$$p_x$$m\sim\text{poly}(n)$$g(x,p_x)=1$$f(x)=1$$g(x,p_x)$$\text{poly}(n)$

Permettez-moi de donner quelques exemples (voici peut-être ce que vous demandiez ici ?):

• Parité: répond à la question «est-ce impair?». C'est si trivial (prenez juste le bit le moins significatif de ) que est calculé efficacement directement, et donc une preuve n'est pas nécessaire, .$f(x)$$x$$x$$f(x)$$g(x,p_x)=f(x)$

• Nombres composites: répond à la question «la représentation décimale de un nombre composite?». Une preuve possible dans la direction du oui (il suffit de prouver cette direction) est de donner une paire de facteurs. par exemple , . Alors implique simplement de multiplier ensemble les facteurs et de vérifier qu'ils sont égaux à .$f(x)$$x$$x=72$$p_x=(8,9)$$g(x,p)$$x$

• graphes: Étant donné deux graphes et (ici contient la description des deux graphes), répond à la question 'les deux graphes sont-ils isomorphes?'. La preuve est une permutation: un énoncé de la façon dont les sommets de correspondent à ceux de . La fonction vérifie que est une permutation valide, permute les sommets de utilisant la permutation spécifiée et vérifie que la matrice d'adjacence est la même que celle de .$G_1$$G_2$$x$$f(x)$$p_x$$G_1$$G_2$$g(x,p_x)$$p_x$$G_1$$G_2$

• Démineur : l'ancien jeu préféré intégré aux fenêtres (et autres) peut être exprimé ainsi. Imaginez une planche de dragueur de mines partiellement découverte, donc certaines cellules sont inconnues, et certaines cellules ont été découvertes pour révéler le nombre de mines dans les cellules voisines. Tout cela est intégré à la variable . pose la question «y a-t-il une affectation valide de mines sur la région non couverte?». La preuve, est simplement une de ces affectations de mines. Ceci est facilement vérifié en utilisant qui assure simplement la cohérence avec toutes les contraintes connues.$x$$f(x)$$p_x$$g(x,p_x)$

Tous ces problèmes sont dans car ils correspondent à la définition d'une solution efficacement vérifiable. Certains d'entre eux sont également connus pour être dans : nous avons déjà déclaré que les tests étranges se trouvent dans . Les nombres composites le sont également, car il est efficace de vérifier si un nombre est premier en utilisant le test de primalité AKS .$\text{NP}$$\text{P}$$\text{P}$

L'isomorphisme du graphe et le dragueur de mines ne sont pas connus pour être dans . En effet, le dragueur de mines est connu pour être complet, c'est-à-dire que s'il peut être résolu efficacement, chaque problème dans est dans . Beaucoup de gens soupçonnent que , et donc le Démineur aurait des instances qui prennent plus de temps que le polynôme à résoudre.$\text{P}$$\text{NP}$$\text{NP}$$\text{P}$$\text{P}\neq\text{NP}$

Une façon possible de résoudre un problème est, pour un fixe , simplement de tester toutes les preuves possibles jusqu'à une longueur maximale , et de voir s'il existe une solution satisfaisante, c'est-à-dire rechercher une solution . Évidemment, cela prend du temps , car il y a de façon exponentielle de nombreux éléments à rechercher, chacun nécessitant un temps polynomial pour calculer. Ceci peut être amélioré en implémentant la recherche de Grover: nous cherchons simplement une solution (c'est-à-dire que le valide devient l'élément marqué), et cela prend un tempsx p x m = poly ( n ) g ( x , p x ) = 1 O ( 2 m poly ( m ) ) g ( x , p x ) = 1 p x O ( 2 m / 2 poly ( m ) $\text{NP}$$x$$p_x$$m=\text{poly}(n)$$g(x,p_x)=1$$O(2^m\text{poly}(m))$$g(x,p_x)=1$$p_x$$O(2^{m/2}\text{poly}(m))$. Ceci est massivement plus rapide, mais ne change pas l'appréciation de savoir si le temps de fonctionnement est polynomial ou quelque chose de pire; il n'est pas devenu un algorithme polynomial temporel. Par exemple, l'isomorphisme des graphes devrait rechercher toutes les permutations possibles. Le dragueur de mines devrait rechercher toutes les affectations possibles de mines sur des carrés non couverts.

Bien sûr, une partie du temps, une structure supplémentaire dans le problème permet différentes solutions qui ne nécessitent pas la recherche de toutes les preuves possibles. Là, la recherche de Grover ne nous est pas utile, voire pas du tout, mais il se pourrait que nous puissions proposer un algorithme de temps polynomial d'une autre manière. Par exemple, le cas des tests composites: classiquement, trouver les facteurs d'un nombre semble difficile: nous ne pouvons pas faire beaucoup mieux que de tester tous les facteurs possibles, donc l'utilisation de cette forme de preuve n'aide pas beaucoup, mais , comme déjà mentionné, la question peut être résolue efficacement via une autre route, le test de primalité AKS.

Oubliez la base de données. L'algorithme de Grover résout le problème de satisfaction booléenne , à savoir:

Vous avez un circuit booléen avec entrées et une seule sortie. Le circuit délivre pour une configuration unique de bits d'entrée, sinon il s'agit des sorties . Trouvez la configuration des bits d'entrée.1 $n$$1$$0$

Le problème est connu pour être NP-complet.