One-Way-Quantenverifikation

Die Theorie der Clusterzustandsberechnung ist mittlerweile gut etabliert und zeigt, dass jede BQP-Schaltung so modifiziert werden kann, dass sie nur einzelne Qubit-Quantentore verwendet, die möglicherweise klassisch gesteuert werden, vorausgesetzt, sie liefert ausreichend einen als "Clusterzustand" bekannten Zustand ist ein einfach zu erzeugender Stabilisatorzustand.

Meine Frage ist: Ist ein ähnlicher Begriff für die Quantenüberprüfung bekannt - dh kann man QMA-Schaltungen durch klassisch gesteuerte 1-Qubit-Gatter ersetzen, möglicherweise unter Verwendung eines "speziellen Zustands"? Zumindest anfangs bin ich mir nicht sicher, warum der Clusterstatus in diesem Fall überhaupt funktionieren kann.

quantum-computing Lior Eldar
quelle

Wenn ich das richtig verstehe, ist das Problem, dass Ihnen Merlin in QMA einen Quantennachweis übergibt, den Sie irgendwie in das Modell einbauen müssen? Mit anderen Worten, wenn es QCMA statt QMA war, wo Merlin Ihnen nur eine klassische Saite übergibt, könnten wir einfach die bekannten Ergebnisse für BQP verwenden, oder?

Robin Kothari

Ja das ist richtig. Vielen Dank, dass Sie diesen Unterschied gemacht haben.

Lior Eldar

Zunächst könnte man für BQP die gleiche Frage stellen: Können wir eine Quantenberechnung durchführen, wenn die Leistung für 1-Qubit-Messungen gegeben ist und nicht vertrauenswürdige Clusterzustände (oder ein anderer geeigneter Zustand) vorliegen?

Norbert Schuch

Antworten:

Es ist möglich, den QMA-Verifizierer auf Einzel-Qubit-Messungen und klassische Vor- und Nachbearbeitung (mit Zufallsprinzip) zu beschränken, während die QMA-Vollständigkeit erhalten bleibt.

Um zu sehen, warum, nehmen Sie eine Klasse von lokalen QMA-vollständigen Hamiltonianern auf Qubits. Durch das Hinzufügen einer Konstante der Ordnung und Neuskalierung mit einem Faktor kann der Hamilton - Operator in Form gebracht werden , wobei , und $k$ $\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$

H = \sum_{i} w_{i} h_{i},

$H=\sum_i w_i h_i\ ,$

w_{i} > 0

$w_i>0$

\sum_{i} w_{i} = 1

$\sum_i w_i=1$

, wobei

ein Produkt von Paulis ist. Abschätzen der kleinste Eigenwert von

bis Genauigkeit

ist noch QMA-hart.

h_{i} = \frac{1}{2} (I d \pm P_{i})

$h_i = \tfrac12(\mathrm{Id}\pm P_i)$

P_{i}

$P_i$

H

$H$

1 / p o l y (n)

$1/\mathrm{poly}(n)$

Wir können nun eine Schaltung aufbauen, die nur Einzel-Qubit-Messungen verwendet, die bei gegebenem Zustand , nimmt mit einer Wahrscheinlichkeit von (die durch Konstruktion ist zwischen und ). Wählen Sie zu diesem Zweck zunächst nach dem Zufallsprinzip eines der 's gemäß der Verteilung . Dann misst jede der Paulis in , und nehmen Sie die Parität der Ergebnisse, die nun im Zusammenhang mit $|\psi\rangle$ $1-\langle\psi|H|\psi\rangle$ $0$ $1$ $i$ $w_i$ $P_i$ $\pi$ $\langle\psi|h_i|\psi\rangle$ über Die Schaltung gibt nun, und der Ausgang wird daher verteilt nach.

⟨ ψ | h_{ich} | ψ ⟩ = \frac{1}{2} (1 \pm (- 1)^{π}) \in {0, 1} .

$\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .$

1 - ⟨ ψ | h_{i} | ψ ⟩

$1-\langle\psi|h_i|\psi\rangle$

⟨ ψ | H | ψ ⟩

$\langle\psi|H|\psi\rangle$

Dies ist, wenn wir eine Ja-Instanz des (QMA-complete) lokalen Hamilton - Problem aufgenommen, es ist ein Zustand so dass dieser mit einiger Wahrscheinlichkeit Verifizierer akzeptiert , während andernfalls jeder Zustand mit Wahrscheinlichkeit verworfen wird , mit . Die Variante von QMA, bei der der Verifizierer auf Ein-QBit-Messungen beschränkt ist, ist daher für einige QMA-vollständig. $|\psi\rangle$ $\ge a$ $\le b$ $a-b>1/\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$ Spalt. Schließlich kann diese Version von QMA unter Verwendung nur der herkömmlichen Verstärkungstechniken für QMA verstärkt werden, was schließlich beweist, dass sie unabhängig von der Lücke QMA-vollständig ist (innerhalb des gleichen Bereichs wie QMA).

Norbert Schuch
quelle

Können Sie eine kurze Erklärung oder einen Hinweis geben, warum das Problem der Schätzung des kleinsten Eigenwerts von

immer noch QMA-schwer ist? Vielen Dank!

H

$H$

Henry Yuen

Wir gehen von einem Hamilton - Operator

für das dieses Problem [bis

] ist QMA-abgeschlossen ist , eine Änderung in ein Hamilton - Operator

, wobei

und

, so dass die Energie des GS Abschätzen

H^{'}

$H'$

ϵ = 1 / p o l y (n)

$\epsilon=1/\mathrm{poly}(n)$

H = x (H^{'} + y)

$H=x(H'+y)$

x = 1 / p o l y (n)

$x=1/\mathrm{poly}(n)$

y = p o l y (n)

$y=\mathrm{poly}(n)$

H

$H$ bis Genauigkeit

ist noch QMA-hart.

x ϵ = 1 / p o l y (n)

$x\epsilon=1/\mathrm{poly}(n)$

Norbert Schuch

Können Sie immer annehmen, dass

ein Projektor auf einen Eigenraum eines Pauli Hamiltonian ist?

h_{i}

$h_i$

Henry Yuen

Nun, jeder Term

in der ursprünglichen Hamilton - Operator kann als Summe geschrieben werden

Pauli Produkte (

für

) und der Vorfaktor jedes Pauli Produkt

ist

h^{'}

$h'$

4^{k}

$4^k$

4^{k} = p o l y (n)

$4^k=\mathrm{poly}(n)$

k = O (\log (n))

$k=O(\log(n))$

P_{i}

$P_i$

t r [P_{i} h^{'}] / 2^{k} \leq ‖ h^{'} ‖_{\infty}

$\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$

Norbert Schuch

Meine Interpretation der Frage ist, dass Sie sich fragen, können wir annehmen, dass die Verifiziererschaltung für ein QMA-Protokoll nur Einzel-Qubit-Messungen verwendet? (Die Idee ist, dass der Prüfer Ihnen sowohl den Quantensicherungs- als auch den Quantenclusterstatus sendet, der zur Implementierung der ursprünglichen Verifizierungsschaltung durch "Einweg-Quantencomputing" erforderlich ist.)

Das Problem ist natürlich, dass der Prüfer Ihnen möglicherweise keinen gültigen Clusterstatus sendet. Der Prüfer müsste also den empfangenen Status testen, um sicherzustellen, dass es sich wirklich um einen Clusterstatus handelt. Der Prüfer führt dazu Einzel-Qubit-Messungen durch und überprüft, ob die Korrelationen den erforderlichen Stabilisatorprüfungen entsprechen. Da solche Tests für den Staat destruktiv sind, müsste es ein Verfahren geben, bei dem der Prüfer viele Kopien des Staates erhält, die meisten prüft und für die Berechnung eine zufällige verwendet. Reichen polynomisch viele Kopien aus?

Ich glaube nicht, dass dies ein bekannter Satz ist. Ich sehe kein offensichtliches Gegenbeispiel (mit Gedanken einer Minute), also könnte es glaubwürdig sein. Bekannte Proof-Technologie für Testzustände scheint ausreichend zu sein, um dies zu überprüfen. Siehe zum Beispiel Matthew McKagues Artikel arXiv: 1010.1989 [quant-ph]. Wenn Sie einen Proof erhalten, der funktioniert, senden Sie das Papier an QIP (Frist: 5. Oktober)!

Anonym
quelle

Vielleicht verstehe ich diese Frage falsch. Wenn Sie sich fragen, ob Sie die Überprüfungsschaltung für ein Problem in QMA mithilfe einer messungsbasierten Berechnung implementieren können, bei der Merlin die Eingabeebene und Arthur alle weiteren Qubits im Ressourcenzustand bereitstellt und beide Qubitsätze verwickelt, bevor die Messungen beginnen Die Antwort ist trivial ja. Dies ergibt sich direkt aus der Tatsache, dass jede Quantenschaltung als messungsbasierte Berechnung implementiert werden kann, unabhängig davon, ob Sie sich für die klassische Eingabe oder die Quanteneingabe interessieren.

Sie werden feststellen, dass in den meisten Arbeiten zu messbasierten Berechnungen Eingabeseiten im Allgemeinen getrennt von den anderen Seiten identifiziert werden, und dies ist der Grund (dh speziell für den Fall der Quanteneingabe).

Joe Fitzsimons
quelle

Eigentlich bin ich mir in diesem Punkt nicht sicher. In den Arbeiten zur messungsbasierten Berechnung, die ich mir angesehen habe, geht die Transformation von einer BQP-Schaltung mit klassischem Eingang zu einer Einweg-Berechnungsschaltung ausgehend vom Cluster-Zustand. Das heißt, es wird NICHT als eine Transformation beschrieben, die einen beliebigen Einheitsschaltkreis U unabhängig von der Eingabe in einen messungsbasierten Schaltkreis U_1 umwandelt. Während die Komplexitätsfrage, die ich gestellt hatte, nun nach Norberts Antwort gelöst ist, möchte ich diesen Punkt dennoch verstehen.

Lior Eldar

@LiorEldar: Dann solltest du dir das Originalpapier von Raussendorf und Briegel oder das von Raussendorf, Browne und Briegel ansehen. Sie bauen explizit jeweils ein Gate auf und zeigen, dass jedes Messmuster ein bestimmtes Gate auf der Eingangsschicht implementiert, das sich in einem beliebigen Zustand befinden kann. Sie können auf jeden Fall beliebige Schaltkreise auf beliebigen Eingängen implementieren.

Joe Fitzsimons

Lior war tatsächlich hier in Aachen, als wir darüber diskutierten, und ein Weg, die Frage zu verstehen, basiert auf dieser Idee: Könnte Merlin den Beweis liefern, der in einen (nicht vertrauenswürdigen) Cluster-Zustand eingebaut ist, und Arthur verwendet seine Ein-Qubit-Messungen, um beide zu verifizieren der Cluster oder überprüfen Sie den Beweis mit MBQC? (Vielleicht könnte man ähnliche Ideen verwenden wie in Blind Comp., Wo die Fehlerkorrektur verwendet wird?) Leider braucht man diese nette Idee nicht, um die QMA-Härte zu beweisen. ;-( Allerdings glaube ich, dass es immer noch eine interessante Frage ist, zu verstehen, ob dies funktionieren würde, und Sie wären der Experte, um dies zu zeigen :-)

Norbert Schuch

@Lior: Wenn Sie MBQC verwenden möchten, um die Eingabe zu verifizieren, müssen Sie natürlich zusätzlich zu den Ein-Qubit-Messungen auch 2-Qubit-Gatter verwenden (da Sie die Eingabe mit Ihrem Cluster-Status verwickeln müssen).

Norbert Schuch

@Joe: Übrigens, die gleiche Frage für BQP (können wir BQP mit 1-Qubit-Messungen unter Verwendung eines nicht vertrauenswürdigen Cluster-Zustands ausführen) ist natürlich noch offen, und ich denke, dass die bei Blindberechnungen verwendeten Ideen der richtige Weg sind .

Norbert Schuch