Quantencomputer realisierbar?

Glaubt ihr, dass Quantencomputer realisierbar sind? Basiert die Theorie von Quantencomputern darauf, dass man wirklich sowas wie Schrödingers Katze baut, also ein makroskopisches Ding, dass mehrere Zustände gleichzeitig hat?

cooky451

https://www.youtube.com/watch?v=g_IaVepNDT4

Quantencomputer sind aber nur bei sehr speziellen Problemen schneller, bei den meisten Algorithmen dürften die heutiger Technik weit unterlegen sein.

Gregor

1. Vor einigen Jahren wurde von der Firma D-Wave ein sogenannter adiabatischer Quantencomputer entwickelt, den wohl auch einige Firmen nutzen. Das ist aber kein allgemeiner Quantencomputer, sondern eben nur ein Computer, der zur Lösung bestimmter Optimierungsprobleme quantenmechanische Effekte ausnutzt. Es ist zweifelhaft, ob diese Art von Computer einen fundamentalen Fortschritt darstellt.

2. Das theoretische Konzept eines Quantencomputers ist seit langem ausformuliert. Problematisch ist aber noch die physikalische Realisierung. Es scheint vor allem ein massives Problem zu sein, das ganze auf mehr als ein paar Qubits hochzuskalieren. Ich habe vor einiger Zeit mal einen Vortrag von einem Wissenschaftler gehört, der sich im Bereich des Quantencomputings einen Namen gemacht hat: David DiVincenzo. Er erschien mir sehr zuversichtlich zu sein, dass die Probleme, die es bisher noch mit einer praktischen Realisierung des Quantencomputings gibt, in den Griff zu kriegen sind. Ich gehe aber davon aus, dass das nicht in den nächsten paar Jahren geschieht. Und wenn es geschieht, dann wird es vermutlich zuerst nur unter Bedingungen realisiert werden können, die ausschließlich für große, institutionelle Anwender realisierbar sind. ...zum Beispiel eine Temperatur von wenigen Kelvin durch Heliumkühlung, damit man supraleitende Qubits nutzen kann.

3. Wie mächtig Quantencomputer letztendlich sind, ist bisher auch nicht klar. Quantencomputer können Probleme aus der Problemklasse BQP effizient lösen, konventionelle Rechner Probleme der Klasse P. Jetzt weiß man von den Problemklassen, dass die Beziehungen $P \subseteq NP \subseteq PSPACE$ und $P \subseteq BQP \subseteq PSPACE$ gelten.

Das heißt, dass Du mit einem Quantencomputer zwar alle Probleme effizient lösen kannst, die Du auch mit einem konventionellen Computer effizient lösen kannst, es ist aber nicht klar, ob Du wirklich mehr Probleme effizient lösen kannst. Allerdings sind momentan für einige Problemstellungen effiziente Quantenalgorithmen bekannt, für die man keine effizienten konventionellen Algorithmen kennt. Die Beziehung zwischen den Problemklassen BQP und NP ist nicht bekannt. Aus meiner Sicht ist es also noch gar nicht wirklich klar, wie viel man von Quantencomputern profitieren würde. Falls zum Beispiel irgendwann ein wissenschaftlicher Artikel rauskommt, in dem gezeigt wird, dass P=NP gilt, könnte das Interesse an Quantencomputern deutlich zurückgehen. Oder vielleicht zeigt einer, dass P=BQP ist.

Gregor schrieb:

Falls zum Beispiel irgendwann ein wissenschaftlicher Artikel rauskommt, in dem gezeigt wird, dass P=NP gilt, könnte das Interesse an Quantencomputern deutlich zurückgehen. Oder vielleicht zeigt einer, dass P=BQP ist.

Was beides enorme Auswirkungen auf unseren Alltag hätte. Da halte ich eine Realisierung des Quantencomputers schon für wahrscheinlicher.

Gregor

bbq_p schrieb:

Gregor schrieb:

Falls zum Beispiel irgendwann ein wissenschaftlicher Artikel rauskommt, in dem gezeigt wird, dass P=NP gilt, könnte das Interesse an Quantencomputern deutlich zurückgehen. Oder vielleicht zeigt einer, dass P=BQP ist.

Was beides enorme Auswirkungen auf unseren Alltag hätte. Da halte ich eine Realisierung des Quantencomputers schon für wahrscheinlicher.

Ja, das stimmt natürlich.

Warum programmiert man nicht einfach einen virtuellen Quantencomputer? In dem Video sagen sie, dass ein Qubit ein Elektron in Superposition ist. Und ein Elektron in Superposition hat mit einer bestimmten Wahrscheinlichkeit Spin-up oder Spin-down und diese kann man nur bestimmen, wenn man es misst. Sowas kann man doch relativ einfach simulieren. Und mit diesen simulierten Qubit kann man dann den Algorithmus ausführen der eingentlich auf dem Quantencomputer laufen würde. Haben die irgendwas in dem Video nicht erwähnt, was Qubit noch können, aber nicht so einfach simuliert werden kann?

SeppJ

VM-Quanten schrieb:

Sowas kann man doch relativ einfach simulieren.

Hier ist der Haken. Die Simulation auf einem konventionellen Computer würde eben nicht die besonderen Laufzeiteigenschaften eines Quantencomputers haben, sondern bestenfalls die des besten konventionellen Algorithmus für die gegebene Problemstellung.

Gregor

VM-Quanten schrieb:

Warum programmiert man nicht einfach einen virtuellen Quantencomputer? In dem Video sagen sie, dass ein Qubit ein Elektron in Superposition ist. Und ein Elektron in Superposition hat mit einer bestimmten Wahrscheinlichkeit Spin-up oder Spin-down und diese kann man nur bestimmen, wenn man es misst. Sowas kann man doch relativ einfach simulieren. Und mit diesen simulierten Qubit kann man dann den Algorithmus ausführen der eingentlich auf dem Quantencomputer laufen würde. Haben die irgendwas in dem Video nicht erwähnt, was Qubit noch können, aber nicht so einfach simuliert werden kann?

Ich gehe mal davon aus, dass man dafuer eine zeitliche Entwicklung eines quantenmechanischen Systems simulieren muss, aber lass uns mal einen einfacheren Fall annehmen und nur die zeitunabhaengige Schroedinger-Gleichung betrachten. Du hast dort

\hat{H} \Psi\_i(\vec{r}\_1,\vec{r}\_2,\dots,\vec{r}\_{N_\text{elec}}) = E\_i \Psi\_i(\vec{r}\_1,\vec{r}\_2,\dots,\vec{r}_{N_\text{elec}}),
wobei $\hat{H}$ der Hamilton-Operator ist, $E_i$ der i-te Energieeigenwert und $\Psi_i$ die Vielteilchenwellenfunktion fuer die $N_\text{elec}$ Elektronen. Die Vielteilchenwellenfunktion haengt also von $3 N_\text{elec}$ Koordinaten ab und da sind die Spin-Koordinaten noch gar nicht drin. Wenn man jetzt annimmt, dass man die Wellenfunktion bezueglich jeder Koordinate fuer 10 Punkte speichert, dann muss man $10^{3 N_\text{elec}}$ Werte speichern. Der Speicherbedarf skaliert also exponentiell mit der Anzahl der Elektronen. Es gibt keinen Algorithmus mit exponentiell steigendem Speicherbedarf, der effizient ist. Wenn Du physikalische Systeme auf dieser Basis simulieren moechtest, dann kannst Du damit nur minimal kleine, triviale Systeme handhaben.

Das ist aber natuerlich nur die halbe Wahrheit. In der Physik fuehrt man an solchen Stellen dann typischerweise Naeherungen ein. Zum Beispiel die Hartree Naeherung, in der man annimmt, dass die Vielteilchenwellenfunktion ein Produkt aus Einteilchenwellenfunktionen ist. Das reduziert den Speicherbedarf enorm. Du musst jetzt nur noch $10^3 \cdot N_\text{elec}$ Werte speichern. Allerdings schmeisst Du dadurch jede Menge wichtige Physik weg. Ein naechster Schritt waere die Hartree-Fock-Naeherung, in der an die Wellenfunktion eine zusaetzliche Bedingung gestellt wird. Dort ist die Wellenfunktion eine sogenannte Slater-Determinante.

Der grosse Trend in der Simulation von quantenmechanischen Systemen in den letzten Jahrzehnten ist allerdings die Dichtefunktionaltheorie. Es gibt einen zentralen Satz (das Hohenberg-Kohn Theorem), der besagt, dass ein quantenmechanisches System exakt durch die Elektronendichte $\rho(\vec{r})$ des Grundzustands bestimmt ist. Das ist natuerlich viel angenehmer, da Du hier nur 3 Koordinaten hast. Das Problem ist jetzt aber, wie man an diese Elektronendichte kommt. In der Praxis konstruiert man sich hierfuer ein Hilfssystem (Das Kohn-Sham System) aus nicht-interagierenden Elektronen, das die gleiche Elektronendichte wie das Vielteilchensystem mit interagierenden Elektronen aufweist und bestimmt die selbstkonsistente Elektronendichte fuer dieses System mit einem iterativen Verfahren. Hier gibt es jetzt 2 Probleme: Zum einen fuehrt man bei der Konstruktion des Kohn-Sham Systems in der Praxis wieder einige sehr relevante Naeherungen ein, vor allem werden sogenannte Korrelations- und Austauscheffekte unter den Elektronen angenaehert, zum anderen ist dieses iterative Verfahren letztendlich ein Loesungsverfahren fuer ein Minimierungsproblem. In der Praxis heisst letzteres, dass es alles andere als trivial ist, an die Loesung zu kommen. Abhaengig vom quantenmechanischen System benoetigt man hierfuer zum einen sehr viele Iterationen, zum anderen auch noch einen Menschen, der das Verfahren mit sehr viel Know-How lenkt. Ich habe mir nie ernsthafte Gedanken darueber gemacht, in welcher Komplexitaetsklasse dieses Optimierungsproblem liegt, gehe aber davon aus, dass es NP-vollstaendig ist. In der Praxis kann man es aber fuer die meisten Systeme effizient loesen. Mit Dichtefunktionaltheorie simuliert man inzwischen auf Supercomputern quantenmechanische Systeme mit bis zu 10.000 oder gar 100.000 Elektronen. Das hoert sich auf den ersten Blick vielleicht viel an, aber letztendlich sind das noch wesentlich kleinere Systeme als beispielsweise heutige Transistoren in integrierten Schaltkreisen. Du kannst also noch keinen Transistor auf dieser Ebene simulieren.

Jenseits davon bleibt bei diesen Simulationen natuerlich auch die Frage, ob man durch die Naeherungen nicht wesentliche Aspekte der Quantenmechanik wegwirft, die einen Quantencomputer maechtig machen koennten und, ob man hier ueberhaupt eine effiziente Moeglichkeit findet, solche Systeme zu simulieren.

Wie weiter oben bereits geschrieben: Es ist nicht klar, wie viel maechtiger die Problemklasse BQP im Vergleich zur Klasse P ist. Das impliziert natuerlich auch, dass man nicht weiss, wie Komplex die Simulation der wesentlichen Aspekte eines Quantencomputers auf einem klassischen Computer ist.

Jodocus

Funktioniert das überhaupt? Einen Quantencomputer mit Näherungen der Many-Body-Physik/Quantenstatistik zu simulieren? Für einen Quantencomputer sollte es m.E. sehr entscheidend sein, wie die Zustände konkret aussehen, wie sie verschränkt sind, nach Messungen in Eigenzustände kollabieren etc. (also exakte Zustände).

Aber das klingt alles so, als ob am Ende nach allen "höchstens" noch ein paar Dichteoperatoren/Erwartungswerte übrig bleiben (statt Zuständen/Eigenwerte) und wir einen Brei in einer Art thermischem Gleichgewicht haben, mit dem man zwar ganz nette statistische Aussagen machen kann, aber längst nicht mehr Spiele wie Messungen auf hermiteschen Operatoren und Wellenfunktionkollaps machen kann. Sprich: quantum computation lebt gerade davon, dass man eine riesige Zahl von Zuständen/Superpositionen hat und die nicht einfach wegmitteln/nähern kann, damit man das ganze auf einer "klassischen Maschine" simuliert.

Gregor

@Jodocus: Jede Observable eines quantenmechanischen Systems ist ein Funktional der Grundzustandsdichte. Das ist eine exakte Aussage, in der keine Naeherung einfliesst. Was man in dem Zusammenhang allerdings im Allgemeinen nicht weiss ist, wie diese Funktionale aussehen. Bei einigen Groessen weiss man aber natuerlich, wie man sie aus der Grundzustandsdichte berechnet. Die zentrale Groesse eines quantenmechanischen Systems ist die Gesamtenergie. Fuer diese hat man ein Funktional, in das allerdings eine Naeherung einfliesst: Das sind die schon erwaehnten Austausch- und Korrelationseffekte.

Im Prinzip kann man so eine Naeherung natuerlich als eine Abaenderung der Physik ansehen. Man sagt praktisch, dass die Wechselwirkungen zwischen den Elektronen etwas anders ist, als sie in der Natur ist. Die Frage ist, inwiefern so etwas die Maechtigkeit eines Quantencomputers beeinflussen wuerde.

Aber wie gesagt: Ich sehe auch nicht, dass man ueber diesen Weg einen Quantencomputer effizient simulieren koennte.