Was ist der Beweis dafür, dass Quantencomputer beliebige quantenmechanische Systeme effizient simulieren können?

JBV schlug vor, einige Kommentare in eine Frage umzuwandeln.

Eine weitere Frage [1] betrifft Anwendungen des QM-Computing. Eine Antwort [2] war "die Quantenmechanik effizient simulieren". Anscheinend geht diese Idee auf Feynmans frühes Schreiben zu diesem Thema zurück; obwohl ich keine Referenz habe. Damit:

Frage. Was ist der Beweis dafür, dass ein Quantencomputer ein beliebiges quantenmechanisches System effizient simulieren kann?

Auf einer Ebene scheint dies grundlegend zu sein. Dies scheint jedoch aus folgendem Grund nicht trivial zu sein: Die meiste Quantencomputerliteratur scheint sich auf Operationen an Gates zu beschränken, die auf zwei Teilchen oder andere kleine Subsysteme wirken. (Ja, Toffoli-Gates wirken auf 3 Eingänge, werden jedoch häufig auf Zwei-Qubit-CNOT-Gates reduziert.)

Aufgrund der Vollständigkeit von Turing steht außer Frage, dass ein Quantencomputer beliebige klassische oder sogar Quantenphysik simulieren kann (obwohl es aufgrund des Unsicherheitsprinzips usw. möglicherweise einige Neinsager gibt - ich wäre auch neugierig, davon zu hören). Aber es scheint mir, dass man, um die arbitäre Quantenphysik effizient zu simulieren, zumindest einen Weg braucht, um willkürliche n-Wege- Wechselwirkungen in meistens / fast 2-Wege- Gates zu simulieren .

Man könnte argumentieren, dass wir willkürliche N-Wege- Tore bauen können, aber der eindeutige Beweis nach vielen Jahren experimenteller Forschung ist, dass selbst 2-Wege- Tore extrem schwer zu bauen sind und dass N-Wege- Tore sicherlich viel schwieriger wären. (Es gibt einige 3-Wege- Quantenexperimente, z. B. 3-Teilchen-Glocken-Ungleichungen, aber sie sind schwer aufzubauen.)

[1] Reale Anwendungen des Quantencomputers (außer für Sicherheit)

[2] /cstheory//a/10241/248

reference-request quantum-computing application-of-theory vzn
quelle

Weitere Gedanken, die allgemeine Idee der QM-Computeräquivalenz mit der QM-Physiksimulation stammt offenbar von Feynman, der dies als gegeben oder angenommen zu betrachten schien [der eher ein brillanter Physiker als ein Informatiker war] ... z. B. in der Arbeit und Vorlesung , Simulation der Physik mit Computern , 1982

vzn

Antworten:

$n$

$n$ $n$ $n$ $n$

$2^n$ $n$ $n$ $O(n)$

$n$ $n$ $k$ $k$

$n$

Ob Quantencomputer können effizient simulieren Quantenfeldtheorie ist noch eine offene Frage, aber der Fortschritt ist zur Zeit wird gemacht auf sich.

Peter Shor
quelle

ist nicht, dass ein Tippfehler in der 1. Zeile "sollte" => "sollte nicht". und beachten Sie, dass ich mich auf das strengere Problem der Effizienz konzentriere, nicht nur auf die Äquivalenz. Akzeptieren Sie, dass QM-Computer vollständig sind. Da Sie sagen, dass dies alles ziemlich einfach ist, wie wäre es mit dem einfachen Fall der Simulation eines n-Teilchen-Quantensystems, bei dem keine Teilchen voneinander isoliert sind? Wie geht das mit Qubits?

VZN

n

$n$

Ich nehme Ihr Wort dafür, aber mein Hauptpunkt - wird dies irgendwo in der Literatur diskutiert? Anscheinend könnten all diese Vorbehalte zumindest ein Papier leicht füllen. Sie scheinen zu behaupten, dass wahrscheinlich alle physischen Hamiltonianer effizient über Qubits simuliert werden können, aber das muss irgendwie mathematisch konkretisiert werden. & Ich denke, es ist nicht trivial genug, dass die Behörden nicht klar sagen sollten, dass eine effiziente QM-Simulation aller willkürlichen QM-Setups an sich machbar ist. Vielleicht könnten Umwelteinflüsse, z. B. angelegte elektrische oder magnetische Feldkonfigurationen, den Hamiltonianer komplizieren.

VZN

Ich glaube, ich habe es irgendwo besprochen gesehen, aber ich erinnere mich nicht, wo. Zu sagen, welche Hamiltonianer physikalisch implementiert werden können, ist eine schwierige Frage ... da die Dynamik der Natur alle aus der Quantenfeldtheorie stammt und zeigt, dass QFT mit einem Quantencomputer effizient simuliert werden kann, könnte diese Frage beantworten, aber (1) wir sind immer noch Es ist wirklich lange her, dies zu beweisen, und (2) dies könnte so etwas wie die Aussage sein, dass wir Turbulenzen mithilfe der zugrunde liegenden Atomdynamik simulieren können. In gewissem Sinne mag es wahr sein, aber es ist eindeutig der falsche Weg, dies zu tun.

Peter Shor