Grovers Algorithmus und seine Beziehung zu Komplexitätsklassen?

Ich bin verwirrt über Grovers Algorithmus und seine Verbindung zu Komplexitätsklassen.

Der Algorithmus des Grovers findet und element in einer Datenbank von (so dass ) von Elementen mit Aufrufen zum Orakel.$k$$N=2^n$$f(k)=1$

Wir haben also folgendes Problem:

Problem: Finde ein in der Datenbank, so dass$k$$f(k)=1$

Jetzt bin ich mir bewusst, dass dies kein Entscheidungsproblem ist und daher unsere normalen Definitionen der Komplexitätsklasse , usw. nicht wirklich zutreffen. Aber ich bin gespannt, wie wir in einem solchen Fall die Komplexitätsklasse definieren würden - und ob dies in Bezug auf oder geschieht ?$\text{P}$$\text{NP}$$N$$n$

Darüber hinaus kann der Algorithmus des Grovers als Subroutine verwendet werden. Ich habe an mehreren Stellen gelesen, dass der Algorithmus des Grovers die Komplexitätsklasse nicht zum Problem macht - gibt es eine heuristische Möglichkeit, dies zu sehen?

Zusammenfassung

• Es gibt eine Theorie der Komplexität von Suchproblemen (auch Beziehungsprobleme genannt). Diese Theorie beinhaltet Klassen mit den Namen FP , FNP und FBQP, in denen es effektiv darum geht, Suchprobleme mit verschiedenen Arten von Ressourcen zu lösen.
• Aus Suchproblemen können Sie auch Entscheidungsprobleme definieren, mit denen Sie Suchprobleme mit den üblichen Klassen P , NP und BQP in Beziehung setzen können .
• Unabhängig davon, ob Sie die Suchversion der Entscheidungsversion des Problems berücksichtigen, bestimmt die Art und Weise, wie Sie die Eingabe für das Problem der unstrukturierten Suche berücksichtigen, welche Obergrenzen Sie für die Komplexität des Problems festlegen können.

Die Komplexität von Beziehungsproblemen

Wie Sie bemerken, löst das Problem von Grover ein Suchproblem , das in der Komplexitätsliteratur manchmal auch als Beziehungsproblem bezeichnet wird. Das heißt, es ist ein Problem der folgenden Art:

Die Struktur eines allgemeinen Suchproblems. Finden Sie bei
gegebener Eingabe und einer binären Beziehung R ein y, so dass R ( x , y ) gilt.$x$$R$$y$$R(x,y)$

Die Komplexitätsklassen FP und FNP werden im Hinblick auf solche Probleme definiert, wobei insbesondere der Fall von Interesse ist, bei dem höchstens eine Polynomfunktion der Länge von x hat und die Beziehung R ( x , y ) selbst kann in einer Zeitspanne berechnet werden, die durch ein Polynom in der Länge von ( x , y ) begrenzt ist .$y$$x$$R(x,y)$$(x,y)$

Insbesondere: Das Beispiel für das Problem der Datenbanksuche, auf das Grovers Suche normalerweise angewendet wird, kann wie folgt beschrieben werden.

Unstrukturierte Suche.
Bei einem eingegebenen Orakel so dass O | ein ⟩ | b ⟩ = | ein ⟩ | b ⊕ f ( a ) ⟩ für eine Funktion f : { 0 , 1 } m → { 0 , 1 } , finde a y so, dass O | y ⟩ | 0 ⟩ = | y ⟩ | $\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$

Hier ist das Orakel selbst der Input für das Problem: Es spielt die Rolle von , und die Beziehung, die wir berechnen, ist R ( O , y $x$

Angenommen, wir haben anstelle eines Orakels eine bestimmte Eingabe die beschreibt, wie die Funktion f berechnet werden soll. Dann können wir überlegen, zu welcher Komplexitätsklasse dieses Problem gehört. Wie angegeben , hängt die entsprechende Komplexitätsklasse davon ab, wie die Eingabe bereitgestellt wird.$x$$f$pyramids

• Angenommen, die Eingabefunktion wird als Datenbank bereitgestellt (wie das Problem manchmal beschrieben wird), wobei jeder Eintrag in die Datenbank eine Länge . Wenn n die Länge der Zeichenfolge x ist , mit der die gesamte Datenbank beschrieben wird , hat die Datenbank N = n / ℓ Einträge. Es ist dann möglich, die gesamte Datenbank vollständig zu durchsuchen, indem jeder der N Einträge der Reihe nach abgefragt wird, und anzuhalten, wenn wir einen Eintrag y finden , der f ( y ) = 1 ist . Angenommen, jede Abfrage in der Datenbank benötigt so etwas wie O $\ell$$n$$x$$N = n\big/\ell$$N$$y$$f(y) = 1$ Zeit, dieser Vorgang stoppt in der Zeit O ( N log N ) ⊆ O ( n log n ) , so dass das Problem inFP liegt.$O(\log N) \subseteq O(\log n)$$O(N \log N) \subseteq O(n \log n)$

  Unter der Annahme, dass die Datenbanksuche in kohärenter Überlagerung erfolgen kann, lässt der Algorithmus von Grover zu, dass dieses Problem in FBQP vorliegt . Als FP  ⊆  FBQP beweist die klassische umfassende Suche jedoch auch, dass es sich um ein FBQP- Problem handelt . Alles, was wir (bis zu Protokollfaktoren) erhalten, ist eine quadratische Beschleunigung aufgrund einer Einsparung bei der Anzahl von Datenbankabfragen.
  
  

• Angenommen, die Eingabefunktion wird kurz und bündig durch einen Polynom-Zeit-Algorithmus beschrieben, der eine Spezifikation und ein Argument y ∈ { 0 , 1 } m verwendet und O : H m + 1 2 berechnet$x \in \{0,1\}^n$$y \in \{0,1\}^m$$\mathcal O : \mathcal H_2^{m+1} \!\to \mathcal H_2^{m+1}\!$auf einem Standard - Basiszustand , wobei m kann viel größer sein als Ω ( log n ) . Ein Beispiel wäre, wenn x die CNF-Form einer booleschen Funktion f angibt : { 0 , 1 } m → { 0 , 1 } für m ∈ O ( n ) . In diesem Fall können wir f ( y ) an einer Eingabe effizient auswerten y $\lvert y \rangle\lvert b \rangle$$m$$\Omega(\log n)$$x$$f: \{0,1\}^m \to \{0,1\}$$m \in O(n)$$f(y)$ und werten dadurch O auf Standardbasiszuständeneffizient aus. Dies versetzt das Problem inFNP.$y \in \{0,1\}^m$$\mathcal O$

  Eine Prozedur gegeben, um aus ( x , y ) in der Zeit O ( p ( n ) ) für n = | zu bewerten x | Der Algorithmus von Grover löst das Problem der unstrukturierten Suche nach O in der Zeit 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})$ . Dies ist innkein Polynomund reicht daher nicht aus, um dieses Problem inFBQP umzusetzen: Wir erhalten nur eine quadratische Beschleunigung - obwohl dies immer noch eine potenziell enorme Einsparung an Rechenzeit darstellt, vorausgesetzt, der Vorteil, den der Algorithmus von Grover bietet, geht nicht verloren der für die fehlertolerante Quantenberechnung erforderliche Overhead.$\subseteq O(p(n) \sqrt{2^n})$$n$
  
  

In beiden Fällen wird die Komplexität durch die Länge der Zeichenkette x * bestimmt, die angibt, wie das Orakel O berechnet wird . In dem Fall, dass x eine Nachschlagetabelle darstellt, ist N = n / ℓ , in welchem ​​Fall die Leistung als Funktion von N der Leistung als Funktion von n ähnlich ist ; Aber in dem Fall, dass x genau O und N ∈ O ( 2 n / 2 ) angibt , löst Grovers große Botschaft das Problem in $n$$x$$\mathcal O$$x$$N = n\big/\ell$$N$$n$$x$$\mathcal O$$N \in O(2^{n/2})$Abfragen verschleiern die feinkörnige Nachricht, dass dieser Algorithmus für einen Quantencomputer immer noch Exponentialzeit ist.$O(\sqrt N)$

Entscheidungskomplexität aus Beziehungsproblemen

Es gibt einen einfachen Weg, Entscheidungsprobleme aus Beziehungsproblemen zu ziehen, der aus der Theorie der NP- vollständigen Probleme bekannt ist: das Suchproblem in eine Frage nach der Existenz einer gültigen Lösung umzuwandeln .

Die Entscheidungsversion eines allgemeinen Suchproblems. Bestimmen Sie bei
gegebener Eingabe und einer binären Beziehung R , ob ∃ y : R ( x , y ) gilt.$x$$R$$\exists y: R(x,y)$

Die Komplexitätsklasse NP kann im Wesentlichen anhand solcher Probleme definiert werden, wenn die Beziehung effizient berechenbar ist: Bei den bekanntesten NP- vollständigen Problemen (CNF-SAT, HAMCYCLE, 3-COLORING) handelt es sich um die bloße Existenz einer gültigen Lösung für ein effizient überprüfbares Beziehungsproblem. Dieser Wechsel von der Erzeugung von Lösungen zur einfachen Behauptung der Existenz von Lösungen ermöglicht es uns auch, Versionen der ganzzahligen Faktorisierung zu beschreiben, die sich in BQP befinden (indem wir fragen, ob es nicht-triviale Faktoren gibt, anstatt nach den Werten nicht-trivialer Faktoren zu fragen ). .$R$

Im Fall der unstrukturierten Suche hängt es wiederum davon ab, wie die Eingabe strukturiert ist, welche Komplexitätsklasse das Problem am besten beschreibt. Das Ermitteln, ob es eine Lösung für ein Beziehungsproblem gibt, kann sich darauf beschränken , eine Lösung für dieses Problem zu finden und zu überprüfen . Für den Fall, dass die Eingabe eine Zeichenfolge , die das Orakel als Nachschlagetabelle angibt, liegt das Problem der unstrukturierten Suche in P ; und allgemeiner, wenn x ein effizientes Mittel zur Bewertung des Orakels angibt, liegt das Problem in NP . Es ist auch möglich, dass es eine Möglichkeit gibt, festzustellen, ob es eine gibt$x$$x$ eine Lösung für die unstrukturierte Suche, bei der keine Lösung gefunden wird, obwohl im Allgemeinen nicht klar ist, wie dies in einer Weise erfolgen soll, die einen Vorteil gegenüber der tatsächlichen Suche nach einer Lösung bietet.

Oracle Komplexität

Ich habe auffällig von der Rede über das Orakel zu Möglichkeiten übergegangen , mit denen eine Eingabe x verwendet werden kann, um das Orakel O zu spezifizieren (und zu bewerten) . Wir betrachten den Algorithmus von Grover jedoch hauptsächlich als ein Orakelergebnis, bei dem die Bewertung des Orakels nur einen einzigen Zeitschritt dauert und keine Angabe erforderlich ist. Wie beurteilen wir die Komplexität des Problems in diesem Fall?$\mathcal O$$x$$\mathcal O$

In diesem Fall haben wir es mit einem relativierte Modell der Berechnung, bei der Auswertung dieses eine spezifische Orakel (was, denken Sie daran, ist der Eingang zu dem Problem) eine primitive Operation ist. Dieses Orakel ist für alle Eingabegrößen definiert: Um das Problem bei der Suche nach Zeichenfolgen der Länge n zu berücksichtigen, müssen Sie angeben, wie sich das Orakel O auf Eingaben der Länge n auswirkt , was wiederum unter Berücksichtigung der Länge von a erfolgen würde Boolescher String x wird als Eingabe verwendet. In diesem Fall könnte das Problem folgendermaßen dargestellt werden.$\mathcal O$$n$$\mathcal O$$n$$x$

Suchen relativ unstrukturierten zu Oracle . $\mathcal O$
Bei einer Eingabe der Länge n ,$x = 11\cdots 1$$n$

• finde ein (Beziehungsproblem) oder$y \in \{0,1\}^n$

• festzustellen, ob es ein (Entscheidungsproblem)$y \in \{0,1\}^n$

so dass .$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Dieses Problem wird in (für das Entscheidungsproblem) oder F N P O (für das Beziehungsproblem) angegeben, je nachdem, welche Version des Problems Sie berücksichtigen möchten. Da der Algorithmus von Grover kein Polynom-Zeit-Algorithmus ist, ist nicht bekannt, dass dieses Problem in B Q P O oder F B Q P O vorliegt . Tatsächlich können wir etwas Stärkeres sagen, wie wir gleich sehen werden.$\mathsf{NP}^{\mathcal O}$$\mathsf{FNP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$$\mathsf{FBQP}^{\mathcal O}$

Der Grund, warum ich die eigentliche, orakelbasierte Beschreibung der unstrukturierten Suche überflogen habe, bestand darin, Ihre Komplexität und insbesondere die Frage der Eingabegröße zu behandeln . Die Komplexität der Probleme hängt weitgehend davon ab, wie die Eingaben angegeben werden: als prägnante Spezifikation (für den Fall, dass eine Funktion in CNF-SAT angegeben wird), als explizite Spezifikation (für eine Nachschlagetabelle für a function) oder auch als Ganzzahl in unary angegeben, dh als Länge einer Zeichenfolge von 1s wie oben (wie oben in "Unstructured Search relativ zu Oracle ").$\mathcal O$

Wie wir aus dem letzteren Fall sehen können, sieht die Situation ein wenig unintuitiv aus, wenn wir die Eingabe nur als Orakel behandeln, und es ist sicherlich unmöglich, darüber zu sprechen, wie die "Datenbank" realisiert werden kann. Eine Tugend der Betrachtung der relativierten Version des Problems mit einem tatsächlichen Orakel ist jedoch, dass wir Dinge beweisen können, die wir sonst nicht beweisen können. Wenn wir nachweisen könnten, dass die Entscheidungsversion des kurzen Problems der unstrukturierten Suche in BQP enthalten ist , würden wir einen enormen Durchbruch in der praktischen Berechnung erzielen. und wenn wir nachweisen könnten, dass das Entscheidungsproblem nicht in BQP bestand , hätten wir gezeigt, dass P ≠ PSPACEDies wäre ein enormer Durchbruch bei der Komplexität der Berechnungen. Wir wissen auch nicht, wie wir das machen sollen. Aber für das relativiert Problem, können wir zeigen , dass es Orakel , für die die Entscheidung Version von „Unstructured Suche in Bezug auf O “ ist in N P O , aber nicht in B Q P O . Auf diese Weise können wir zeigen, dass Quantencomputer zwar potenziell leistungsfähig sind, es jedoch Gründe gibt, zu erwarten, dass BQP wahrscheinlich kein NP enthält und dass insbesondere die Beziehungsversion von Unstructured Search wahrscheinlich nicht in FBQP enthalten ist, ohne dass die Art und Weise stark eingeschränkt wird Die Eingabe wird dargestellt.$\mathcal O$$\mathcal O$$\mathsf{NP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$

Komplexitätsklassen werden im Allgemeinen in Bezug auf die Größe der Eingabe definiert. Die relevanten Größen sind hier (die Anzahl der Qubits, mit denen Sie Grovers Algorithmus arbeiten lassen) und eine Anzahl, die Sie noch nicht erwähnt haben (nennen Sie es m) , von Bits, die zur Beschreibung der allgemein als Orakel bezeichneten Subroutine benötigt werden. In der Regel wird das Orakel auf eine Weise effizient implementiert , die in n polynomial skaliert , was beispielsweise der Fall ist, wenn Sie ein typisches boolesches Erfüllbarkeitsproblem im Orakel codieren.$n$$m$$n$

Auf jeden Fall erzielen Sie mit dem Algorithmus von Grover keinen Gewinn in der Komplexitätsklasse: Es sind exponentiell viele Quantenoperationen erforderlich, typischerweise , um ein Problem zu lösen, das wir in exponentiell vielen Schritten, typischerweise m ∗ 2, brachial erzwingen könnten n - 1 , sowieso auf einem klassischen Computer. Dies bedeutet, dass Probleme, von denen bekannt ist (z. B. EXPTIME) oder von denen vermutet wird (z. B. NP), dass sie eine exponentielle Laufzeit haben, weiterhin eine exponentielle Laufzeit erfordern.$m*2^{n/2}$$m*2^{n-1}$

Physiker appellieren jedoch gerne an die Vorstellung, dass dies immer noch eine exponentielle Beschleunigung ist, ohne dass ein klassisches Äquivalent bekannt (oder durchaus vorstellbar) wäre. Dies zeigt sich am deutlichsten im Datenbankbeispiel, in dem die Oracle-Funktion eine Datenbanksuche ist und der Algorithmus von Grover dazu führen kann, dass viel weniger Suchvorgänge erforderlich sind, als Daten in der Datenbank vorhanden sind. In diesem Sinne gibt es noch einen signifikanten Vorteil, obwohl er im Komplexitätsklassenbild völlig verloren geht.

Alle Zählungen erfolgen in Form von , der Anzahl der zur Beschreibung der Eingabe erforderlichen Bits.$n$

Wir definieren die Klasse der Probleme folgendermaßen (oder dies ist eine Möglichkeit, dies zu tun):$\text{NP}$

Sei eine Funktion, die eine Eingabe x ∈ { 0 , 1 } n akzeptiert und einen einzelnen Bitwert 0 oder 1 zurückgibt. Die Aufgabe besteht darin, herauszufinden, ob ein gegebener Wert von x eine 1 zurückgibt. Das Problem hat eine weitere Struktur: Wenn f ( x ) = 1 ist , ist garantiert, dass es einen Beweis p x (der Größe m ∼ poly ( n ) ) gibt, so dass eine Funktion g ( x , p x$f(x)$$x\in\{0,1\}^n$$x$$f(x)=1$$p_x$$m\sim\text{poly}(n)$ nur wenn f ( x ) = 1 ist und die Funktion g ( x , p x ) effizient berechenbar ist (dh eine Laufzeit von poly ( n ) hat) .$g(x,p_x)=1$$f(x)=1$$g(x,p_x)$$\text{poly}(n)$

Lassen Sie mich einige Beispiele nennen (vielleicht sind diese , was Sie fragen , wurden hier ?):

• Parität: beantwortet die Frage 'ist x ungerade?'. Dies ist so trivial (nimm einfach das niedrigstwertige Bit von x ), dass f ( x ) effizient direkt berechnet wird und daher ein Beweis nicht erforderlich ist, g ( x , p x ) = f ( x ) .$f(x)$$x$$x$$f(x)$$g(x,p_x)=f(x)$

• Zusammengesetzte Zahlen: beantwortet die Frage 'Ist die Dezimaldarstellung von x eine zusammengesetzte Zahl?'. Ein möglicher Beweis in der Ja-Richtung (Sie müssen nur diese Richtung beweisen) besteht darin, ein Paar von Faktoren anzugeben. zB x = 72 , p x = ( 8 , 9 ) . Dann besteht g ( x , p ) einfach darin, die Faktoren zu multiplizieren und zu überprüfen, ob sie gleich x sind .$f(x)$$x$$x=72$$p_x=(8,9)$$g(x,p)$$x$

• Graphisomorphie: Bei zwei Graphen und G 2 (hier enthält x die Beschreibung beider Graphen ) beantwortet f ( x ) die Frage, ob die beiden Graphen isomorph sind. Der Beweis p x ist eine Permutation: eine Aussage darüber, wie die Eckpunkte in G 1 denen von G 2 entsprechen . Die Funktion g ( x , p x ) verifiziert, dass p x eine gültige Permutation ist, und permutiert die Eckpunkte von G $G_1$$G_2$$x$$f(x)$$p_x$$G_1$$G_2$$g(x,p_x)$$p_x$$G_1$unter Verwendung der angegebenen Permutation und überprüft, ob die Adjazenzmatrix mit der von identisch ist .$G_2$

• Minesweeper : Das alte Lieblingsspiel, das in Windows (und anderen) eingebaut ist, kann so ausgedrückt werden. Stellen Sie sich ein Minensuchbrett vor, das teilweise freigelegt ist. Einige Zellen sind also unbekannt, und einige Zellen wurden freigelegt, um zu ermitteln, wie viele Minen sich in den benachbarten Zellen befinden. Dies ist alles in die Variable eingebaut . f ( x ) stellt die Frage "Gibt es eine gültige Zuordnung von Minen in der nicht abgedeckten Region?". Der Beweis p x ist einfach eine solche Zuordnung von Minen. Dies lässt sich leicht mit g ( x , p x ) überprüfen, was einfach die Konsistenz mit jeder bekannten Einschränkung sicherstellt.$x$$f(x)$$p_x$$g(x,p_x)$

$\text{NP}$$\text{P}$$\text{P}$

Graph isomorphism and minesweeper are not known to be in $\text{P}$. Indeed, minesweeper is known to be $\text{NP}$-complete, i.e. if it can be solved efficiently, every problem in $\text{NP}$ is in $\text{P}$. Many people suspect that $\text{P}\neq\text{NP}$, and hence Minesweeper would have instances which take longer than polynomial time to solve.

One possible way to solve an $\text{NP}$ problem is, for a fixed $x$, simply to test all possible proofs $p_x$ up to a maximum length $m=\text{poly}(n)$, and see if there's a satisfying solution, i.e. to search for a solution $g(x,p_x)=1$. Obviously, that takes time $O(2^m\text{poly}(m))$, as there are exponentially many items to search, each requiring a polynomial time to compute. This can be improved by implementing Grover's search: we just search for a solution $g(x,p_x)=1$ (i.e. the valid $p_x$ becomes the marked item), and this takes a time $O(2^{m/2}\text{poly}(m))$. This is massively faster, but does not change the assessment of whether the running time is polynomial or something worse; it has not become a polynomial time algorithm. For example, graph isomorphism would have to search over all possible permutations. Minesweeper would have to search over all possible assignments of mines on uncovered squares.

Of course, some of the time, additional structure in the problem permits different solutions that do not require the searching of all possible proofs. There, Grover's search is of less, or even no, use to us, but it might be that we can come up with a polynomial time algorithm in another way. For example, the case of composite testing: classically, finding the factors of a number appears to be hard: we can't do much better than testing all possible factors, so making use of that form of proof doesn't help much, but, as already mentioned, the question can be resolved efficiently via another route, AKS primality testing.

Forget about database. Grover's algorithm solves Boolean Satisfiability Problem, namely:

You have a boolean circuit with $n$ inputs and a single output. The circuit outputs $1$ for a single configuration of input bits, otherwise is outputs $0$. Find the configuration of input bits.

The problem is known to be NP-complete.