QMA

Im Computerkomplexitätstheorie, QMA, welches dafür steht Quanten Merlin Arthur, ist der Satz von Sprachen, für die, wenn die Antwort ja ist, ein quantenbeweis (ein Quantenzustand) mit Polynomgröße gibt, das a überzeugt Polynomzeit Quantenurifier (auf a Quantencomputer) dieser Tatsache mit hoher Wahrscheinlichkeit. Wenn die Antwort nein ist, wird jeder Quantenzustand in Polynomgröße durch den Verifizierer mit hoher Wahrscheinlichkeit abgelehnt.

Die Beziehung zwischen QMA und BQP ist analog zur Beziehung zwischen Komplexitätsklassen Np und P. Es ist auch analog zur Beziehung zwischen der probabilistischen Komplexitätsklasse Ma und BPP.

QAM ist eine verwandte Komplexitätsklasse, in der fiktive Mittel Arthur und Merlin die Sequenz ausführen: Arthur generiert eine zufällige Zeichenfolge, antwortet Merlin mit einem Quantum Zertifikat und Arthur überprüft es als BQP -Maschine.

Definition

Eine Sprache l ist in ${\ displayStyle {\ mathsf {qma}} (c, s)}$ Wenn es eine Polynomzeit Quantum -Verifizierer V und ein Polynom gibt ${\ displayStyle p (x)}$ so dass:^[1][2][3]

• ${\ displayStyle \ forall x \ in l}$Es gibt einen Quantenzustand ${\ displayStyle | \ psi \ rangle}$ so dass die Wahrscheinlichkeit, dass V die Eingabe akzeptiert ${\ displayStyle (| x \ rangle, | \ psi \ rangle)}$ ist größer als c.
• ${\ displayStyle \ forall x \ notin l}$für alle Quantenzustände ${\ displayStyle | \ psi \ rangle}$die Wahrscheinlichkeit, dass V die Eingabe akzeptiert ${\ displayStyle (| x \ rangle, | \ psi \ rangle)}$ ist weniger als s.

wo ${\ displayStyle | \ psi \ rangle}$ reicht über alle Quantenzustände mit höchstens ${\ displayStyle p (| x |)}$ Qubits.

Die Komplexitätsklasse ${\ displayStyle {\ mathsf {qma}}}$ ist definiert, um gleich zu sein ${\ displayStyle {\ mathsf {qma}} ({2}/{3}, 1/3)}$. Die Konstanten sind jedoch nicht zu wichtig, da die Klasse unverändert bleibt, wenn c und s sind auf alle Konstanten so eingestellt, dass c ist größer als s. Darüber hinaus für Polynome ${\ displayStyle q (n)}$ und ${\ displayStyle r (n)}$, wir haben

${\ displayStyle {\ mathsf {qma}} \ links ({\ frac {2} {3}}, {\ frac {1} {3}} \ rechts) = {\ mathsf {qma} \ links ({{\ links) FRAC {1} {2}}+{\ frac {1} {q (n)}}, {\ frac {1} {2}}-{\ frac {1} {q (n)} \ rechts) = {\ mathsf {qma}} (1-2^{-r (n)}, 2^{-r (n)})}$.

Probleme in QMA

Da viele interessante Klassen in QMA enthalten sind, wie P, BQP und NP, sind alle Probleme in diesen Klassen ebenfalls in QMA. Es gibt jedoch Probleme in QMA, aber nicht bekannt als NP oder BQP. Einige so bekannte Probleme werden nachstehend erörtert.

Ein Problem soll QMA-hard sein, analog zu Np-harte, wenn jedes Problem in QMA sein kann reduziert dazu. Ein Problem soll QMA- seinKomplett Wenn es QMA-hard und in QMA ist.

Das örtliche Hamiltonsche Problem

Ein K-Local Hamiltonian (Quantenmechanik) ${\ displayStyle H}$ ist ein Hermitische Matrix auf N -Qubits wirken, die als Summe von dargestellt werden können ${\ displayStyle m}$ Hamiltonianische Begriffe, die höchstens einwirken ${\ displayStyle K}$ Qubits jeweils.

${\ displayStyle H = \ sum _ {i = 1}^{m} h_ {i}}$

Das allgemeine k-lokale Hamiltonsche Problem ist ein k-lokaler Hamiltonianer ${\ displayStyle H}$, um den kleinsten Eigenwert zu finden ${\ displayStyle \ lambda}$ von ${\ displayStyle H}$.^[4] ${\ displayStyle \ lambda}$ wird auch als Grundzustand des Hamiltonianer genannt.

Die Entscheidungsversion des k-lokalen Hamiltonschen Problems ist eine Art von Art von Problem versprechen und wird definiert als ein k-lokaler Hamiltonianer und ${\ displayStyle \ Alpha, \ Beta}$ wo ${\ displaystyle \ alpha> \ beta}$, um zu entscheiden, ob es einen Quanten -Eigenstaat gibt ${\ displayStyle | \ psi \ rangle}$ von ${\ displayStyle H}$ mit assoziiertem Eigenwert ${\ displayStyle \ lambda}$, so dass ${\ displaystyle \ lambda \ leq \ Beta}$ oder wenn ${\ displayStyle \ lambda \ Geq \ alpha}$.

Das lokale Hamiltonsche Problem ist das Quantenanalogon von Max-sa. Das k-lokale Hamiltonsche Problem ist für k ≥ 2 QMA-Complete.^[5]

Das 2-lokale Hamiltonsche Problem, das auf ein zweidimensionales Gitter von reagiert wurde Qubits, ist auch QMA-Complete.^[6] Es wurde gezeigt, dass das k-lokale Hamiltonsche Problem auch für Hamiltoner, die eine 1-dimensionale Partikellinie mit Wechselwirkungen mit 12 Zuständen pro Partikel mit 12 Zuständen darstellen, immer noch QMA-Hard ist.^[7] Wenn das System translational-invarianten ist, wird sein lokales Hamilton-Problem zu QMA_Exp-Complete (Da die Problemeingabe in der Systemgröße codiert ist, verfügt der Verifizierer nun exponentielle Laufzeit, während die gleiche Versprechungslücke beibehält).^[8][9]

QMA-Hartness-Ergebnisse sind für einfache Bekanntheit bekannt Gittermodelle von Qubits wie der ZX Hamiltonianer ^[10] $oder {ij} z_ {i} z_ {j}+\ sum _ {i <j} k^{ij} x_ {i} x_ {j}}$ wo ${\ displayStyle z, x}$ repräsentieren Pauli -Matrizen ${\ displaystyle \ sigma _ {z}, \ sigma _ {x}}$. Solche Modelle sind auf Universal anwendbar Adiabatische Quantenberechnung.

k-lokale Hamiltoner-Probleme sind analog zu klassisch Probleme mit der Einschränkung der Zufriedenheit.^[11] Die folgende Tabelle zeigt die analogen Geräte zwischen klassischen CSPs und Hamiltonianern.

Andere QMA-Complete-Probleme

Eine Liste bekannter QMA-Complete-Probleme finden Sie bei https://arxiv.org/abs/1212.6312.

Verwandte Klassen

QCMA (oder MQA^[2]), die für quanten klassisches Merlin Arthur (oder Merlin Quantum Arthur) steht, ähnelt QMA, aber der Beweis muss eine klassische Zeichenfolge sein. Es ist nicht bekannt, ob QMA QCMA entspricht, obwohl QCMA eindeutig in QMA enthalten ist.

QIP (k), welches dafür steht Quanteninteraktiver Polynomzeit (K -Nachrichten) ist eine Verallgemeinerung von QMA, bei der Merlin und Arthur für K -Runden interagieren können. QMA ist QIP (1). Qip (2) ist bekanntermaßen in PSPACE.^[12]

QIP ist QIP (k), wobei k in der Anzahl der Qubits polynomisch sein darf. Es ist bekannt, dass QIP (3) = qip.^[13] Es ist auch bekannt, dass QIP = IP = PSPACE.^[14]

Beziehung zu anderen Klassen

QMA ist mit anderen Bekannten verwandt Komplexitätsklassen durch die folgenden Beziehungen:

$oder mathsf {pp}} \ subseteq {\ mathsf {pspace}}}$

Die erste Aufnahme ergibt sich aus der Definition von Np. Die nächsten beiden Einschlüsse ergeben sich aus der Tatsache, dass der Überprüfer jeweils mächtiger wird. QCMA ist in QMA enthalten, da der Überprüfer den Prover dazu zwingen kann, einen klassischen Beweis zu senden, indem er Beweise misst, sobald sie empfangen werden. Die Tatsache, dass QMA in enthalten ist in Pp wurde gezeigt von Alexei Kitaev und John Watrous. PP ist auch leicht gezeigt, um sich in zu befinden PSPACE.

Es ist nicht bekannt, ob eine dieser Einschlüsse bedingungslos streng ist, da nicht einmal bekannt ist, ob p streng in PSPACE oder P = PSPACE enthalten ist. Die derzeit am besten bekannten Obergrenzen von QMA sind jedoch^{[15] [16]}

${\ displaystyle {\ mathsf {qma}} \ subseteq {\ mathsf {a_ {0} pp}}}$ und $oder$,

wo beide ${\ displaystyle {\ mathsf {a_ {0} pp}}}$ und ${\ displayStyle {\ mathsf {p^{qma [log]}}}}$ sind in ${\ displayStyle {\ mathsf {pp}}}$. Es ist unwahrscheinlich dass ${\ displayStyle {\ mathsf {qma}}}$ gleich ${\ displaystyle {\ mathsf {a_ {0} pp}}}$ oder ${\ displayStyle {\ mathsf {p^{qma [log]}}}}$, wie Gleichheit mit ersteren das zusammenbrechen würde Polynomzeithierarchie (PH), während Gleichheit mit letzterem implizieren würde ${\ displaystyle {\ mathsf {qma}} = {\ mathsf {co}}}$-${\ displayStyle {\ mathsf {qma}}}$. Es ist nicht bekannt, ob $oder$ oder umgekehrt.

Verweise

Externe Links

• Aaronson, Scott. "Phys771 Vortrag 13: Wie groß sind Quantenzustände?".
• Gharibian, Sevag. "Vorlesung 5: Quantenmerlin Arthur (QMA) und starke Fehlerreduzierung" (PDF).
• Komplexitätszoo: QMA