Zeitlich flaches One-Way-Quantum-Computing

18

Im Grunde bin ich Physiker, und deshalb finde ich One-Way-Quantum-Computing brillant. Insbesondere das auf Graph State Measurement basierende Quantum Computing (MBQC) ist eine wirklich gute Entwicklung in der Quantum Computing-Forschung, wie sie von Raussendorf & Briegel entwickelt wurde . Man muss nur einen mehrteiligen verschränkten Zustand wie in einem Diagramm beschrieben vorbereiten und dann sequentielle Messungen an jedem Knoten oder Qubit durchführen (adaptive Messungen für deterministische Berechnungen).

Ein weiterer hervorragender Aspekt dieses Ansatzes ist, dass Clifford-Schaltungen in einer einzigen Messrunde implementiert werden können, wie von Raussendorf, Browne und Briegel gezeigt . Diese Schaltkreise können, wie von Gottesman und Knill gezeigt, klassisch (effizient) simuliert werden, sodass eine interessante Verbindung zwischen klassischer Simulation und zeitlichen Ressourcen besteht.

Es wird jedoch angenommen, dass nicht alle zeitlich flachen Graph State MBQC-Schaltungen (bestehend aus einer Messrunde) klassisch simulierbar sind. Beispielsweise können Schaltungsfamilien im Quantenschaltungsmodell, die aus Pendelgattern bestehen, die als IQP-Schaltungen bezeichnet werden und von Shepherd und Bremner eingeführt wurden, in MBQC in einem einzigen Zeitschritt implementiert werden. Es wird angenommen, dass diese IQP-Schaltungen nicht klassisch simulierbar sind (in Bezug auf die Komplexität der Berechnung würde dies zu einem Zusammenbruch der Polynomhierarchie führen) .

Siehe auch eine nette Beschreibung einer Klasse von Schaltkreisen, die in einem Zeitschritt hier implementiert wurden . Angesichts dessen, dass Kommutierungs- / Diagonal-Unitaries ein interessantes Verhalten aufweisen können, Nicht-Kommutierungsschaltungen jedoch klassisch simulierbar sind. Es wäre interessant, wenn es nicht pendelnde Schaltkreise gäbe, die implementiert werden könnten, sich aber noch nicht als klassisch simulierbar erwiesen haben.

Wie auch immer, meine Frage ist:

Gibt es andere interessante Schaltungen, die in einem einzigen Zeitschritt in MBQC implementiert werden können?

Obwohl ich Beziehungen der Komplexität von Rechnungen oder der klassischen Simulation vorziehen würde, würde ich alles Interessante finden.

Edit: Nach Joes hervorragender Antwort unten sollte ich ein paar Dinge klarstellen. Wie Joe sagte (und etwas peinlich, das habe ich in einer meiner eigenen Veröffentlichungen gesagt), sind MBQC-Schaltungen mit Einzelmessung in IQP. Genauer gesagt interessieren mich interessante Schaltkreise für die Probleme in IQP, die in einer Messrunde in MBQC implementiert werden können. Clifford-Schaltungen sind ein interessantes Beispiel. Wenn es noch andere Beispiele gibt, die klassisch simulierbar sind, wäre das äußerst interessant. Da die Simulation von IQP-Schaltungen klassisch als unwahrscheinlich angesehen wird, wäre es interessant, Instanzen von Schaltungen zu finden, bei denen es sich um solche handelt.

Matty Hoban
quelle

Antworten:

5

Angesichts der Aktualisierung der Frage hielt ich es für das Beste, diese als neue Antwort zu veröffentlichen, da sie sich völlig von meiner vorherigen Antwort unterscheidet und hoffentlich interessant ist.

Durch die neue Formulierung der Frage scheint es eine versteckte Annahme zu geben, dass der MBQC-Ressourcenzustand eine Anzahl von Qubit-Polynomen in der Anzahl von logischen Qubits aufweist. Dies muss nicht unbedingt der Fall sein, was zu einer möglicherweise interessanten Situation führt. Es ist möglich, auf Einzelschichtmessungen basierende Berechnungen zu konstruieren, für die der Ressourcenzustand in der Anzahl der logischen Qubits notwendigerweise exponentiell ist .n

Um dies zu sehen Hinweis nur , dass jeder Qubit in einem Graphen Zustand, der in der gemessen wird - Ebene hat die gleiche Wirkung wie die Bedienungsperson der Anwendung wobei reiche über alle benachbarten Qubits von . Beachten Sie, dass der Verwicklungsoperator, der auf angewendet wird, . Da das Qubit anfänglich im Zustand vorbereitet wird, ist das Nettoergebnis, dass der folgende Operator auf die benachbarten Qubits angewendet wird:jXZexp(ichθichZich)ichjj|00|ich+|11|ichZich|+12(|0ich+|1ichZich). Wenn das Qubit dann um das Ergebnis . Somit wir bis zu einer Pauli-Korrektur von den Operator deterministisch um. das ist nur eine alternative Form von .exp(ichθX)12(|0(cosθich+ichSündeichZich)+|1(ichZich)(cosθich+ichSündeichZich)ichZichcosθich+ichSündeichZichexp(ichθichZich)

Beachten Sie, dass solche Operatoren die Hadamard-Transformation der Grundbausteine ​​von X-Programmen sind und dass alle diese Operatoren unabhängig davon pendeln, auf welchen Qubits sie arbeiten. IQP ist definiert als X-Programme, die auf eine Anzahl von Begriffen beschränkt sind, die höchstens ein Polynom in der Anzahl von Qubits aufweisen. Es gibt jedoch eine exponentielle Anzahl unabhängiger solcher Terme, und so ist es möglich, zeitlich flache Berechnungen zu spezifizieren, die X-Programme exponentieller Größe haben. In der Tat ist das Eingangsphasen-Toffoli-Gate (dh dasnC....CZgate) ist ein Beispiel für eine solche Operation, die eine exponentielle Anzahl von Pendeltoren erfordert, obwohl sie mit einer linearen Anzahl von Nicht-Pendeltoren erreicht werden kann. Somit ist es möglich, auf Einzelschichtmessungen basierende Berechnungen zu konstruieren, die X-Programme implementieren, die in der Anzahl der logischen Qubits exponentiell sind, und daher außerhalb von IQP für die logischen Qubits (obwohl innerhalb von IQP für die physikalischen Qubits).

Möglicherweise besteht hier ein Problem darin, dass eine exponentielle Anzahl von Parametern erforderlich ist, um alle Paare im X-Programm eindeutig anzugeben. Wenn Sie jedoch davon ausgehen, dass solche Winkel algorithmisch generiert werden (z. B. mit der Einschränkung, dass jeder Winkel in Polynomzeit berechnet werden kann), ist nicht einmal klar, ob eine solche Berechnung in BQP simuliert werden kann.

Joe Fitzsimons
quelle
9

Es macht für mich keinen Sinn zu fragen, ob pendelfreie Operatoren in einem einzigen Zeitschritt implementiert werden (obwohl eine konstante Tiefe durchaus Sinn macht). Sie können jedoch nicht kommutierende Gatter im logischen Unterraum eines MBQC implementieren, die mithilfe von Kommutierungsmessungen für den Ressourcenzustand implementiert werden, obwohl die implementierten Gatter nicht deterministisch sind.

Eigentlich glaube ich, dass Sie IQP enger sehen, als Sie wahrscheinlich sollten. Die Antwort auf Ihre Frage lautet, dass jede MBQC, die in einer einzelnen Messebene in MBQC implementiert werden kann, in IQP enthalten ist. Dies liegt einfach daran, dass Sie das Ergebnis nicht als logischen Hilbert-Raum, sondern als eine Reihe von Pendeloperationen für die physischen Qubits ausdrücken können. Shepherd und Bremner beschäftigen sich in ihrer Arbeit tatsächlich damit (in Abschnitt 5.2, wo solche Operationen als Graph-Programme bezeichnet werden).

Joe Fitzsimons
quelle
Danke, Joe. Ich habe genau über diese Grafikprogramme nachgedacht, als ich über IQP gesprochen habe, und sie haben gezeigt, dass jedes X-Programm von einem Grafikprogramm implementiert werden kann. Man konstruiert jedoch ein Graph-Programm in einer vorgeschriebenen Weise, um ein X-Programm auszuführen. Vielleicht ist meine Formulierung in der Frage etwas abweisend. Ich vermute, mein Problem mit nicht pendelnden Gattern ist, nach einem Beispiel wie einer Clifford-Schaltung zu suchen, die in einem Zeitschritt implementiert werden kann.
Matty Hoban
@Matty: Mein Punkt ist, dass die Clifford-Gruppentore Pendeltore auf dem physischen System sind, nur nicht in dem logischen Heisenberg-Bild, das wir normalerweise verwenden, um die Berechnung in einem MBQC zu betrachten. Da sie im physischen System pendeln, fallen sie in den IQP. Es ist einfach die logische Qubit-Interpretation, die darüber gelegt wird und die Dinge verändert. Grundsätzlich ist jede MBQC-Einzelschichtberechnung aus genau diesem Grund in IQP enthalten.
Joe Fitzsimons
Ah, natürlich. Ich verstehe, was du jetzt meinst. Tut mir leid, dass ich ein bisschen langsam bin. Natürlich gibt es auch Schaltungen in IQP, die in MBQC nicht in einem Zeitschritt implementiert werden können. Danke für diesen Punkt, Joe. Meine anfängliche Motivation bestand darin, Beispiele für Schaltungen in IQP zu finden, die von Interesse sein könnten - im Grunde genommen für ein paar Absätze in meiner Dissertation.
Matty Hoban
1
Ich habe die Frage so bearbeitet, dass sie etwas weniger vage ist. Nochmals vielen Dank für Ihre Antwort. Übrigens, ich liebe TP.SE, also danke auch dafür :).
Matty Hoban