Quantum Computing - Beziehung zwischen Hamilton-Modell und Einheitsmodell

16

Bei der Entwicklung von Algorithmen für das Quantencomputing ist mir aufgefallen, dass es zwei Hauptmodelle gibt, in denen dies durchgeführt wird. Einige Algorithmen - wie zum Beispiel für das Hamilton-NAND-Baum-Problem (Farhi, Goldstone, Guttman) - entwerfen einen Hamilton-Zustand und einen Anfangszustand und lassen das System dann für einige Zeit nach der Schrödinger-Gleichung weiterentwickeln, bevor eine Messung durchgeführt wird.t

Andere Algorithmen - wie Shors Algorithmus für Factoring - entwerfen eine Sequenz von Unitary-Transformationen (analog zu Gates) und wenden diese Transformationen nacheinander auf einen bestimmten Anfangszustand an, bevor eine Messung durchgeführt wird.

Meine Frage ist, wie ist die Beziehung zwischen dem Hamiltonschen Modell und dem unitären Transformationsmodell als Anfänger im Quantencomputing? Einige Algorithmen, wie zum Beispiel für das NAND-Baum-Problem, wurden seitdem angepasst, um mit einer Sequenz von einheitlichen Transformationen zu arbeiten (Childs, Cleve, Jordan, Yonge-Mallo). Kann jeder Algorithmus in einem Modell in einen entsprechenden Algorithmus im anderen umgewandelt werden? Ist es beispielsweise möglich, bei einer gegebenen Folge von einheitlichen Transformationen, um ein bestimmtes Problem zu lösen, einen Hamilton-Operator zu entwerfen und das Problem stattdessen in diesem Modell zu lösen? Was ist mit der anderen Richtung? Wenn ja, in welcher Beziehung steht es zwischen der Zeit, in der sich das System entwickeln muss, und der Anzahl der zur Lösung des Problems erforderlichen einheitlichen Transformationen (Gates)?

Ich habe einige andere Probleme gefunden, für die dies der Fall zu sein scheint, aber keine eindeutigen Argumente oder Beweise, die darauf hindeuten, dass dies immer möglich oder sogar wahr ist. Vielleicht liegt es daran, dass ich nicht weiß, wie dieses Problem heißt, und deshalb bin ich mir nicht sicher, wonach ich suchen soll.

algorithms quantum-computing computation-models user340082710
quelle
3
Jeder Polynom-Zeit-Algorithmus in einem entspricht einem Polynom-Zeit-Algorithmus in dem anderen, aber es ist nicht klar, ob der Grad des Polynoms gleich ist. Hoffentlich kommt jemand mit Referenzen. Diese Ergebnisse wurden in den frühen Tagen der Quantenberechnung bewiesen, und es sollte jetzt bessere Beweise für diese Theoreme geben.
Peter Shor
Bezieht sich dies auf das sogenannte Heisenberg-Schroedinger-Bild des QM, das sich auf die Definition der Operatoren bezieht? auch wenn es nicht in Nielsen & Chuang behandelt wird, dann scheint das ein großes Versehen zu sein! Das NAND-Baumpapier verwendet "Hamilton-Orakel", die offenbar von Farhi / Gutmann 1998 eingeführt wurden. Hier ist ein schöner Übersichtsartikel über Hamilton-Orakel von Mochon 2007
vzn
Der Buchlink, den Sie angegeben haben, ist das Lehrbuch, das wir in meinem Grundstudiengang in Quantum Information Processing verwendet haben. Das Buch ist wirklich auf den einheitlichen Ansatz ausgerichtet (auch im Kontext von Orakeln), aber nicht so sehr im Kontext der Hamiltonianer. Mein Grundstudium konzentrierte sich auf die CS-Perspektive und nicht auf die Physik. Deshalb kenne ich mich am besten mit dem Unitary-Modell aus.
user340082710
Das von Ihnen zur Verfügung gestellte Papier ist im Allgemeinen eine gute Referenz, aber ich glaube auch nicht, dass es meine Frage beantwortet. Zuletzt habe ich mir das Heisenberg-Schroedinger-Bild von QM angesehen und es sieht verwandt aus, aber ich glaube, meine Frage ist anders (obwohl ich mich irren könnte - es war schwierig, den Wikipedia-Einträgen zu folgen).
user340082710
Ich denke, es gibt verschiedene Möglichkeiten, Ihre Frage zu interpretieren. Anstatt alle Interpretationen zu beantworten, möchte ich Sie Folgendes fragen: Können Sie die Version des Hamilton-Modells, an das Sie denken, genauer beschreiben? Was ist das Maß für die Komplexität in diesem Modell? (Das heißt, was zählt, wie schwierig es ist, ein Problem im Hamilton-Modell zu lösen?) Wie ist der Input für das Problem gegeben? Wird es explizit angegeben oder muss die Eingabe über ein Orakel abgefragt werden?
Robin Kothari

Antworten:

10

Um zu zeigen, dass die Hamiltonsche Evolution das Schaltungsmodell simulieren kann, kann man das Paper Universal Computation by Multi-Particle Quantum Walk verwenden , das zeigt, dass eine sehr spezifische Art der Hamiltonschen Evolution (Multi-Particle Quantum Walks) BQP-vollständig ist und somit simulieren kann das Schaltungsmodell.

Hier ist ein Übersichtsartikel zur Simulation der Quantenentwicklung auf einem Quantencomputer. Man kann die Techniken in diesem Artikel verwenden, um das Hamiltonsche Evolutionsmodell von Quantencomputern zu simulieren. Dazu muss "Trotterization" verwendet werden, was die Effizienz der Simulation erheblich verringert (obwohl dies nur eine polynomielle Aufblähung in der Rechenzeit zur Folge hat).

Peter Shor
quelle
Vielen Dank! Diese Referenzen sehen ziemlich gut aus und sollten mir eine Vorstellung davon geben können, wie das gemacht wird.
user340082710