BQP

Im Computerkomplexitätstheorie, Quantenpolynomzeit begrenzt (BQP) ist die Klasse von Entscheidungsprobleme lösbar durch a Quantencomputer in Polynomzeitmit einer Fehlerwahrscheinlichkeit von höchstens 1/3 für alle Fälle.[1] Es ist das Quantenanalogon zum Komplexitätsklasse BPP.

Ein Entscheidungsproblem ist Mitglied von BQP Wenn es vorhanden ist a Quantenalgorithmus (ein Algorithmus Das läuft auf einem Quantencomputer), das das Entscheidungsproblem löst mit hoher Wahrscheinlichkeit und wird garantiert in Polynomzeit laufen. Ein Lauf des Algorithmus löst das Entscheidungsproblem korrekt mit einer Wahrscheinlichkeit von mindestens 2/3.

BQP -Algorithmus (1 Lauf)
Antworten
produziert
Richtig
Antworten
Ja Nein
Ja ≥ 2/3 ≤ 1/3
Nein ≤ 1/3 ≥ 2/3
BQP -Algorithmus (k läuft)
Antworten
produziert
Richtig
Antworten
Ja Nein
Ja > 1 - 2ck < 2ck
Nein < 2ck > 1 - 2ck
für einige Konstante c > 0

Definition

BQP kann als die angesehen werden Sprachen verbunden mit bestimmten begrenzten Uniformfamilien von Quantenschaltungen.[1] Eine Sprache L ist in BQP Wenn und nur wenn es vorhanden ist a Polynomzeituniform Familie der Quantenschaltungen , so dass

  • Für alle , Qn nimmt n Qubits als Eingang und Ausgabe 1 Bit
  • Für alle x in L,
  • Für alle x nicht in L,

Alternativ kann man definieren BQP bezüglich Quanten -Turing -Maschinen. Eine Sprache L ist in BQP Wenn und nur wenn es eine Polynomquantenturing -Maschine gibt, die akzeptiert L mit einer Fehlerwahrscheinlichkeit von höchstens 1/3 für alle Fälle.[2]

Ähnlich wie bei anderen "begrenzten Fehler" probabilistische Klassen ist die Wahl von 1/3 in der Definition willkürlich. Wir können den Algorithmus ständig ausführen und eine Mehrheitsabstimmung abgeben, um eine gewünschte Wahrscheinlichkeit der Korrektheit von weniger als 1 zu erreichen Tschernoff gebunden. Die Komplexitätsklasse bleibt unverändert, indem Fehler von bis zu 1/2 - zuzulassen nc Einerseits oder ein Fehler von nur klein wie 2 benötigtnc Andererseits wo c ist eine positive Konstante und n ist die Länge des Eingangs.[3]

Ein BQP-Complete-Problem

Ähnlich wie der Begriff von NP-Vervollständigung und andere Komplett Probleme, wir können ein BQP-Complete-Problem als ein Problem in BQP definieren und dass jedes Problem in BQP in der Polynomzeit dazu reduziert wird.

Hier ist ein intuitives BQP-Complete-Problem, das direkt aus der Definition von BQP stammt.

Ungefähr-qcircuit-prob-Problem

Bei einer Beschreibung eines Quantenkreislaufs Einwirken auf Qubits mit Tore, wo ist ein Polynom in und jedes Tor wirkt auf ein oder zwei Qubits und zwei Zahlen unterscheiden zwischen den folgenden zwei Fällen:

  • Messung des ersten Qubits des Staates ergibt mit Wahrscheinlichkeit
  • Messung des ersten Qubits des Staates ergibt mit Wahrscheinlichkeit

Beachten Sie, dass das Problem das Verhalten nicht angibt, wenn eine Instanz nicht von diesen beiden Fällen abgedeckt wird.

Beanspruchen. Jedes BQP-Problem reduziert sich auf ca. Qcircuit-prob.

Nachweisen. Angenommen, wir haben einen Algorithmus Das löst ungefähr qcircuit-prob, d. H. Bei einer Quantenschaltung Einwirken auf Qubits und zwei Zahlen , unterscheidet zwischen den oben genannten zwei Fällen. Wir können jedes Problem in BQP mit diesem Orakel durch Einstellen lösen .

Für jeden Es gibt eine Familie von Quantenschaltungen so dass für alle , ein Staat von Qubits, wenn ; sonst wenn . Beheben Sie einen Eingang von Qubits und die entsprechende Quantenschaltung . Wir können zuerst eine Schaltung konstruieren so dass . Dies kann leicht durch Hardwire erfolgen und eine Sequenz von anwenden Cnot Tore, um die Qubits umzudrehen. Dann können wir zwei Schaltungen kombinieren, um sie zu bekommen , und nun . Und schließlich notwendigerweise die Ergebnisse von wird erhalten, indem mehrere Qubits gemessen werden und einige (klassische) Logik -Tore auf sie angewendet werden. Wir können immer Verschieben Sie die Messung[4][5] und die Schaltkreise so umgeben, dass das erste Qubit von messen Wir bekommen die Ausgabe. Dies wird unsere Schaltung sein und wir entscheiden die Mitgliedschaft von in durch Laufen mit . Per Definition von BQP werden wir entweder in den ersten Fall (Akzeptanz) oder den zweiten Fall (Abstoßung) fallen, also reduziert sich auf ca. Qcircuit-prob.

Ungefähr-Qcircuit-Prob ist nützlich, wenn wir versuchen, die Beziehungen zwischen einigen bekannten Komplexitätsklassen und BQP zu beweisen.

Beziehung zu anderen Komplexitätsklassen

Ungelöstes Problem in der Informatik:

Was ist die Beziehung dazwischen? und ?

Die vermutete Beziehung von BQP zu anderen Problemräumen[1]

BQP ist für Quantencomputer definiert; die entsprechende Komplexitätsklasse für klassische Computer (oder formaler für Probabilistische Turing -Maschinen) ist BPP. So wie P und BPP, BQP ist niedrig für sich selbst, was bedeutet BQPBQP = BQP.[2] Informell gilt dies, da Polynomzeitalgorithmen unter Zusammensetzung geschlossen werden. Wenn ein Polynomzeitalgorithmus Polynomzeitalgorithmen als Unterprogramm nennt, ist der resultierende Algorithmus immer noch die Polynomzeit.

BQP enthält P und BPP und ist in enthalten in AWPP,[6] Pp[7] und PSPACE.[2] In der Tat, BQP ist niedrig zum Pp, was bedeutet, dass a Pp Maschine erzielt keinen Vorteil davon, dass sie lösen können BQP Probleme sofort ein Hinweis auf den möglichen Leistungsunterschied zwischen diesen ähnlichen Klassen. Die bekannten Beziehungen zu klassischen Komplexitätsklassen sind:


Als das Problem von P ≟ PSPACE wurde noch nicht gelöst, der Beweis der Ungleichheit zwischen BQP und die oben genannten Klassen sollen schwierig sein.[2] Die Beziehung zwischen BQP und Np ist nicht bekannt. Im Mai 2018 Informatiker Ran Raz von Princeton Universität und Avishay Tal von Universität in Stanford veröffentlichte ein Papier[8] das zeigte das, relativ zu einem Orakel, BQP war nicht in enthalten PH. Es kann bewiesen werden, dass es ein Orakel gibt und BQPA PHA.[9] In einem äußerst informellen Sinne kann dies als pH- und bqp ein identischer, aber zusätzlicher Fähigkeit und Überprüfung dieses BQP mit dem Orakel betrachten (BQPA) kann Dinge pH machenA kann nicht. Obwohl eine Orakel -Trennung nachgewiesen wurde, ist die Tatsache, dass BQP nicht in PH enthalten ist, nicht nachgewiesen. Eine Orakel -Trennung beweist nicht, ob Komplexitätsklassen gleich sind oder nicht. Die Orakel -Trennung ergibt die Intuition, dass BQP möglicherweise nicht in PH enthalten ist.

Es wird seit vielen Jahren vermutet, dass Fourier -Stichproben ein Problem ist, das innerhalb von BQP besteht, jedoch nicht innerhalb der Polynomhierarchie. Jüngste Vermutungen haben Beweise dafür geliefert, dass ein ähnliches Problem, Fourier Checking, auch in der Klasse BQP der Klasse vorhanden ist, ohne in der enthalten zu sein Polynomhierarchie. Diese Vermutung ist besonders bemerkenswert, da sie darauf hindeutet, dass Probleme, die in BQP existieren NP-Complete Probleme. Gepaart mit der Tatsache, dass viele praktische BQP -Probleme vermutet werden, dass es außerhalb von existiert P (Es wird vermutet und nicht verifiziert, weil es keinen Beweis gibt P np), Dies zeigt die potenzielle Leistung des Quantencomputers in Bezug auf das klassische Computer.[9]

Hinzufügen Nachwahl zu BQP führt in der Komplexitätsklasse Postbqp das ist gleich zu Pp.[10][11]

Wir werden einige dieser Ergebnisse unten nachweisen oder diskutieren.

BQP und Exp

Wir beginnen mit einer leichteren Eindämmung. Zu zeigen, dass Es genügt zu zeigen, dass ungefähr-Qcircuit-Prob in Exp ist, da ungefähr-Qcircuit-Prob BQP-Complete ist.

Beanspruchen-

Nachweisen

Die Idee ist einfach. Da wir exponentielle Leistung haben, angesichts einer Quantenschaltung CWir können klassischen Computer verwenden, um jedes Tor zu stimulieren C Um den endgültigen Zustand zu bekommen.

Formaler, lassen Sie es C ein Polynomgröße Quantenkreis auf sein n Qubits und m Gates, wo m in n polynomisch ist. Lassen und Sei der Staat nach dem i-D -Tor in der Schaltung wird auf angewendet . Jeder Staat kann in einem klassischen Computer als Einheitsvektor in dargestellt werden . Darüber hinaus kann jedes Tor durch eine Matrix in dargestellt werden . Daher der endgültige Zustand kann berechnet werden Zeit und damit alle zusammen, wir haben eine Zeitalgorithmus zur Berechnung des endgültigen Zustands und damit die Wahrscheinlichkeit, dass das erste Qubit als eins gemessen wird. Dies impliziert das .

Beachten Sie, dass dieser Algorithmus ebenfalls erfordert Platz zum Speichern der Vektoren und der Matrizen. Wir werden im folgenden Abschnitt zeigen, dass wir die Raumkomplexität verbessern können.

BQP und PSPACE

Beweisen Wir stellen zunächst eine Technik vor, die als Summe der Geschichten bezeichnet wird.

Summe der Geschichten [12]

Die Summe der Geschichten ist eine vom Physiker eingeführte Technik Richard Feynman zum Pfadintegrale Formulierung. Wir wenden diese Technik auf das Quantencomputer an, um ungefähr-Qcircuit-Prob zu lösen.

Summe des Geschichtenbaums

Betrachten Sie einen Quantenkreislauf C, was aus ... besteht t Tore, , wo jeweils kommt von a Universal Gate Set und wirkt auf höchstens zwei Qubits. Um zu verstehen, was die Summe der Geschichten ist, visualisieren wir die Entwicklung eines Quantenzustands mit einem Quantenschaltungskreis als Baum. Die Wurzel ist die Eingabe und jeder Knoten im Baum hat Kinder, die jeweils einen Staat repräsentieren in . Das Gewicht einer Baumkante von einem Knoten in j-TH -Stufe, die einen Staat darstellt zu einem Knoten in -TH -Stufe, die einen Staat darstellt ist die Amplitude von Nach dem Bewerbungen an . Die Übergangsamplitude eines Wurzel-Blatt-Pfades ist das Produkt aller Gewichte an den Kanten entlang des Weges. Die Wahrscheinlichkeit des endgültigen Zustands zu bekommen Wir fassen die Amplituden aller Wurzelwegen zusammen, die an einem Knoten enden, der darstellt .

Formaler für den Quantenkreis CSeine Summe über Geschichten ist ein Baum der Tiefe m, mit einer Ebene für jedes Tor Zusätzlich zur Wurzel und mit Verzweigungsfaktor .

Definieren-Eine Geschichte ist ein Weg in der Summe des Geschichtenbaums. Wir werden eine Geschichte durch eine Sequenz bezeichnen Für einen endgültigen Zustand x.

Definieren-Lassen . Lassen Sie die Amplitude der Kante in dem j-TH -Stufe der Summe über den Geschichtenbaum sein . Für jede Geschichte Die Übergangsamplitude der Geschichte ist das Produkt .

Beanspruchen-Für eine Geschichte . Die Übergangsamplitude der Geschichte ist in der Polynomzeit berechnet.

Nachweisen

Jedes Tor kann zerlegt werden in Für einen einheitlichen Betreiber Auf zwei Qubits wirken, die ohne Verlust der Allgemeinheit als die ersten beiden angesehen werden können. Somit, die in Polynomzeit in berechnet werden können n. Seit m ist Polynom in nDie Übergangsamplitude der Geschichte kann in der Polynomzeit berechnet werden.

Beanspruchen-Lassen Seien Sie der letzte Zustand des Quantenkreislaufs. Für einige die Amplitude kann berechnet werden von .

Nachweisen

Wir haben . Das Ergebnis erfolgt direkt durch Einfügen zwischen , und und so weiter und dann die Gleichung ausdehnen. Dann entspricht jeder Term a , wo

Beanspruchen-

Beachten Sie die Summe über den Histories -Algorithmus, um eine gewisse Amplitude zu berechnen Es wird zu einem bestimmten Zeitpunkt in der Berechnung nur eine Geschichte gespeichert. Daher verwendet die Summe über den Geschichtenalgorithmus Raum zu berechnen für jeden x seit Es werden Bits benötigt, um die Geschichte zusätzlich zu einigen Arbeitsbereichsvariablen zu speichern.

Daher können wir im Polynomraum berechnen gesamt x Mit dem ersten Qubit -Wesen 1, was ist die Wahrscheinlichkeit, dass das erste Qubit bis zum Ende der Schaltung als 1 gemessen wird.

Beachten Sie, dass im Vergleich zu der Simulation für den Beweis dafür Unser Algorithmus nimmt hier weit weniger Platz, aber stattdessen viel mehr Zeit. In der Tat braucht es Zeit, eine einzelne Amplitude zu berechnen!

BQP und pp

Ein ähnliches Argument für Summenüberwachen kann verwendet werden, um dies zu zeigen . [13]

BQP, P und NP

Erstens wissen wir Da jeder klassische Schaltkreis durch einen Quantenkreis simuliert werden kann. [14]

Es wird vermutet, dass BQP harte Probleme außerhalb von P löst, insbesondere Probleme in NP. Die Behauptung ist unbestimmt, weil wir nicht wissen, ob p = np, daher wissen wir nicht, ob diese Probleme tatsächlich in P. unten sind ein Hinweis auf die Vermutung:

Wir kennen jedoch auch ein Analogon von im Sinne "Black-Box". Betrachten Sie das unstrukturierte Suchproblem: Bei einem Oracle -Zugriff auf eine unbekannte Funktion , finden x so dass . Dieses Problem ist eindeutig in NP. Der optimale Quantenalgorithmus für dieses Problem hingegen ist Grovers Algorithmus, was eine Komplexität von hat Wenn Sie nur zugreifen können f über dieses Orakel.[16]

Siehe auch

Verweise

  1. ^ a b c Michael Nielsen und Isaac Chuang (2000). Quantenberechnung und Quanteninformation. Cambridge: Cambridge University Press. ISBN0-521-63503-9.
  2. ^ a b c d Bernstein, Ethan; Vazirani, Umesh (Oktober 1997). "Quantenkomplexitätstheorie". Siam Journal über Computing. 26 (5): 1411–1473. Citeseerx 10.1.1.655.1186. doi:10.1137/s0097539796300921.
  3. ^ Barak, Sanjeev Arora, Boaz (2009). Rechenkomplexität: Ein moderner Ansatz / Sanjeev Arora und Boaz Barak. Cambridge. p. 122. Abgerufen 24. Juli 2018.
  4. ^ Michael A. Nielsen; Isaac L. Chuang (9. Dezember 2010). "4.4 Messung". Quantenberechnung und Quanteninformationen: 10 -jährige Jubiläumsausgabe. Cambridge University Press. p. 186. ISBN 978-1-139-49548-6.
  5. ^ Odel A. Cross (5. November 2012). "5.2.2 Aufgeschobene Messung". Themen im Quantencomputer. O. A. Cross. p. 348. ISBN 978-1-4800-2749-7.
  6. ^ Fortnow, Lance; Rogers, John (1999). "Komplexitätsbeschränkungen bei der Quantenberechnung" (PDF). J. Comput. System. Sci. 59 (2): 240–252. Arxiv:CS/9811023. doi:10.1006/jcs.1999.1651. ISSN 0022-0000. S2CID 42516312.
  7. ^ L. Adleman, J. DeMarrais und M.-D. Huang. Quantenberechnbarkeit. Siam J. Comput., 26 (5): 1524–1540, 1997.
  8. ^ George, Michael Goderbauer, Stefan. "ECCC - TR18-107". ECCC.Weizmann.ac.il. Abgerufen 2018-08-03.
  9. ^ a b Aaronson, Scott (2010). "BQP und die Polynomhierarchie" (PDF). Verfahren von ACM STOC 2010.
  10. ^ Aaronson, Scott (2005). "Quantum Computing, Nachwahl und probabilistische Polynomzeit". Verfahren der königlichen Gesellschaft a. 461 (2063): 3473–3482. Arxiv:Quant-Ph/0412187. Bibcode:2005RSPSA.461.3473a. doi:10.1098/rspa.2005.1546. S2CID 1770389.. Preprint erhältlich bei [1]
  11. ^ Aaronson, Scott (2004-01-11). "Komplexitätsklasse der Woche: PP". Rechenkomplexität Weblog. Abgerufen 2008-05-02.
  12. ^ E. Bernstein und U. Vazirani. Quantenkomplexitätstheorie, Siam Journal on Computing, 26 (5): 1411-1473, 1997.
  13. ^ L. Adleman, J. DeMarrais und M. Huang. Quantum Computability, SIAM Journal über Computer 26: 1524-1540, 1997.
  14. ^ Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantenberechnung und Quanteninformationen, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.
  15. ^ a b ARXIV: Quant-Ph/9508027v2 Polynomzeitalgorithmen für Primfaktorisierung und diskrete Logarithmen auf einem QuantencomputerPeter W. Shor
  16. ^ Zalka, Christof (1999-10-01). "Grovers Quantensuchalgorithmus ist optimal". Physische Bewertung a. 60 (4): 2746–2751. Arxiv:Quant-Ph/9711070. doi:10.1103/PhysReva.60.2746.

Externe Links