Benutzer:Tino Cannst/Quantenglühen
Quantenglühen (englisch Quantum annealing) ist eine Metaheuristik zum Finden des globalen Minimums einer gegebenen Zielfunktion über eine gegebene Menge von Kandidatenlösungen durch ein Verfahren, das auf der Quantenmechanik beruht.
Quantenglühen wird hauptsächlich für kobinatorische Probleme verwendet, bei denen der Suchraum diskret ist mit vielen lokalen Minima; wie z.B. das Finden des Grundzustands eines Spin-Glases [1] oder das Problem des Handlungsreisenden. Es wurde in seiner gegenwärtigen Form von T. Kadowaki und H. Nishimori (ja) in "Quantum annealing in the transverse Ising model "[2] formuliert, obwohl ein Vorschlag in einer anderen Form von A. B. Finnila, M. A. Gomez, C. Sebenik und J. D. Doll in "Quantum annealing" gemacht worden war: Eine neue Methode zur Minimierung mehrdimensionaler Funktionen" n "Quantum annealing: A new method for minimizing multidimensional functions".[3].
Quantenglühen geht von einer quantenmechanischen Überlagerung aller möglichen Zustände mit gleichen Gewichten aus. Dann entwickelt sich das System nach der zeitabhängigen Schrödinger-Gleichung, der natürlichen quantenmechanischen Evolution physikalischer Systeme. Die Amplitude aller Zustände ändert sich ständig, wodurch eine Quantenparallelität realisiert wird, entsprechend der zeitabhängigen Stärke des transversalen Feldes, die ein Quantentunneln zwischen den Zuständen bewirkt. Wenn die Änderungsrate des transversalen Feldes langsam genug ist, bleibt das System nahe am Grundzustand des momentanen Hamiltonian [4] Wenn sich die Änderungsrate des transversalen Feldes erhöht, kann das System den Grundzustand vorübergehend verlassen, produziert aber eine höhere Wahrscheinlichkeit, im Grundzustand des finalen Problem-Hamiltonians, entsprechend einer nicht-adiabatischen Quantenberechnung [5][6] Das transversale Feld wird schließlich abgeschaltet, und es wird erwartet, dass das System den Grundzustand des klassischen Ising-Modells erreicht hat, der der Lösung des ursprünglichen Optimierungsproblems entspricht. Unmittelbar nach dem ersten theoretischen Vorschlag wurde über eine experimentelle Demonstration des Erfolgs des Quantenglühens für zufällige Magnete berichtet.[7] Eine Einführung in kombinatorische Optimierungsprobleme (NP-hard), die allgemeine Struktur der auf Quantenglühen basierenden Algorithmen und zwei Beispiele für diese Art von Algorithmen zur Lösung von Instanzen der Max-SAT- und Minimum-Multicut-Probleme sowie ein Überblick über die von D-Wave Systems hergestellten Quantenglühsysteme werden vorgestellt i
If the rate of change of the transverse field is accelerated, the system may leave the ground state temporarily but produce a higher likelihood of concluding in the ground state of the final problem Hamiltonian, i.e., diabatic quantum computation. The transverse field is finally switched off, and the system is expected to have reached the ground state of the classical Ising model that corresponds to the solution to the original optimization problem. An experimental demonstration of the success of quantum annealing for random magnets was reported immediately after the initial theoretical proposal.[7] An introduction to combinatorial optimization (NP-hard) problems, the general structure of quantum annealing-based algorithms and two examples of this kind of algorithms for solving instances of the max-SAT and Minimum Multicut problems together with an overview of the quantum annealing systems manufactured by D-Wave Systems are presented in.[8]
Comparison to simulated annealing
[Bearbeiten | Quelltext bearbeiten]Das Quantenglühen kann mit simuliertem Glühen verglichen werden, dessen Parameter Temperatur eine ähnliche Rolle spielt wie die Tunnelfeldstärke der QS. Beim simulierten Glühen bestimmt die Temperatur die Wahrscheinlichkeit, von einem einzigen aktuellen Zustand in einen Zustand mit höherer "Energie" überzugehen. Beim Quantenglühen bestimmt die Stärke des Querfeldes die quantenmechanische Wahrscheinlichkeit, die Amplituden aller Zustände parallel zu verändern. Analytisch [9] and numerical [10] evidence suggests that quantum annealing outperforms simulated annealing under certain conditions (see [11] for a careful analysis).
Quantum mechanics: analogy and advantage
[Bearbeiten | Quelltext bearbeiten]![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/12/Quant-annl.jpg/300px-Quant-annl.jpg)
Das Tunnelfeld ist im Grunde ein kinetischer Energiebegriff, der nicht mit dem klassischen potentiellen Energieanteil des ursprünglichen Glases pendelt. Der gesamte Prozess kann in einem Computer mit Quanten-Monte-Carlo simuliert werden. (oder eine andere stochastische Technik), und erhalten so einen heuristischen Algorithmus zur Ermittlung des Grundzustands des klassischen Glases.
Im Falle des Glühens einer rein mathematischen objektiven Funktion kann man die Variablen des Problems als klassische Freiheitsgrade und die Kostenfunktionen als potenzielle Energiefunktion (klassisch Hamiltonian) betrachten. Dann muss ein passender Begriff, der aus nicht pendelnden Variablen besteht (d.h. Variablen, die einen Kommutator ungleich Null mit den Variablen des ursprünglichen mathematischen Problems haben), künstlich in das Hamiltonianisch eingeführt werden, um die Rolle des Tunnelvortriebsfeldes (kinetischer Teil) zu spielen.
Übersetzt mit www.DeepL.com/Translator (kostenlose Version)[12] Since thermal transition probabilities (proportional to , with the temperature and the Boltzmann constant) depend only on the height of the barriers, for very high barriers, it is extremely difficult for thermal fluctuations to get the system out from such local minima. However, as argued earlier in 1989 by Ray, Chakrabarti & Chakrabarti,[1] the quantum tunneling probability through the same barrier (considered in isolation) depends not only on the height of the barrier, but also on its width and is approximately given by , where is the tunneling field.[13] This additional handle through the width , in presence of quantum tunneling, can be of major help: If the barriers are thin enough (i.e. ), quantum fluctuations can surely bring the system out of the shallow local minima. For an -spin glass, the barrier height becomes of order . For constant value of one gets proportional to for the annealing time (instead of proportional to for thermal annealing), while can even become -independent for cases where decreases as .[14] [15]
Es wird spekuliert, dass in einem Quantencomputer solche Simulationen viel effizienter und genauer als in einem klassischen Computer wären, weil er das Tunneln direkt durchführen kann, anstatt es von Hand hinzufügen zu müssen. Darüber hinaus ist er möglicherweise in der Lage, dies ohne die strengen Fehlerkontrollen zu tun, die erforderlich sind, um die Quantenverschränkung zu nutzen, die in traditionelleren Quantenalgorithmen verwendet wird. Eine gewisse Bestätigung dafür findet sich in einer exakt lösbaren Modellvorstellung bei der Auswahl des nicht pendelnden Terms, und die Effizienz des Glühens kann davon abhängen.
Es wurde sowohl experimentell als auch theoretisch nachgewiesen, dass das Quantenglühen in bestimmten Fällen tatsächlich das thermische Glühen (simuliertes Glühen) übertreffen kann, insbesondere wenn die potenzielle Energie-(Kosten-)Landschaft aus sehr hohen, aber dünnen Barrieren
Übersetzt mit www.DeepL.com/Translator (kostenlose Version).[16]
Implementierung von D-Wave
[Bearbeiten | Quelltext bearbeiten]![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/17/DWave_128chip.jpg/220px-DWave_128chip.jpg)
Im Jahr 2011 kündigte D-Wave Systems] das erste kommerzielle Quantenglühgerät auf dem Markt unter dem Namen D-Wave One an und veröffentlichte einen Artikel in Nature über dessen Leistung.[17] Das Unternehmen behauptet, dass dieses System einen Chipsatz mit 128 qubit Prozessoren verwendet.[18] Am 25. Mai 2011 gab D-Wave bekannt, dass Lockheed Martin] das erste kommerzielle Quantenglühgerät auf dem Markt unter dem Namen D-Wave One Corporation eine Vereinbarung über den Kauf eines D-Wave One Systems.[19] Am 28. Oktober 2011 nahm das Institut für Informationswissenschaften der Universität von Südkalifornien (University of Southern California|USC) das D-Wave One System von Lockheed in Empfang.
Im Mai 2013 wurde bekannt gegeben, dass ein Konsortium aus Google, NASA Ames und der gemeinnützigen Universities Space Research Association einen adiabatischen Quantencomputer von D-Wave Systems mit 512 Qubits gekauft hat. [20][21] Eine umfassende Studie über seine Leistungsfähigkeit als Quantenglüher im Vergleich zu einigen klassischen Glühalgorithmen ist bereits verfügbar.[22]
Im Juni 2014 kündigte D-Wave ein neues Quantenanwendungs-Ökosystem mit der Computer-Finanzfirma 1QB Information Technologies an. (1QBit) und der Krebsforschungsgruppe DNA-SEQ, die sich auf die Lösung von Problemen aus der realen Welt mit Quanten-Hardware konzentrieren wird.[23] Als erstes Unternehmen, das sich der Herstellung von Software-Anwendungen für kommerziell erhältliche Quantencomputer verschrieben hat, hat sich die Forschungs- und Entwicklungsabteilung von 1QBit auf die Quantenglühprozessoren von D-Wave konzentriert und erfolgreich nachgewiesen, dass diese Prozessoren für die Lösung von Anwendungen in der realen Welt geeignet sind. [24]
Mit Verschränkungsdemonstrationen veröffentlicht,[25] die Frage, ob die D-Wave-Maschine eine Quantenbeschleunigung über alle klassischen Computer demonstrieren kann, bleibt unbeantwortet. Eine im Juni 2014 in Science veröffentlichte Studie, die als "wahrscheinlich die gründlichste und präziseste Studie, die zur Leistung der D-Wave-Maschine durchgeführt wurde"[26] und "der bisher fairste Vergleich", beschrieben wurde, versuchte, die Quantenbeschleunigung zu definieren und zu messen. Es wurden mehrere Definitionen vorgeschlagen, da einige von ihnen durch empirische Tests nicht überprüfbar sein mögen, während andere, obwohl gefälscht, dennoch die Existenz von Leistungsvorteilen zulassen würden. Die Studie kam zu dem Ergebnis, dass der D-Wave-Chip "keine Quantenbeschleunigung erzeugt" und schloss die Möglichkeit in zukünftigen Tests nicht aus.[27] Tie Forscher unter der Leitung von Matthias Troyer an der Eidgenössischen Technischen Hochschule fanden "keine Quantenbeschleunigung" über die gesamte Bandbreite ihrer Tests und nur unschlüssige Ergebnisse bei der Betrachtung von Teilmengen der Tests. Ihre Arbeit illustrierte "die subtile Natur der Frage nach der Quantenbeschleunigung". Weitere Arbeit >ref name="Amin15">Mohammad H. Amin, "Searching for quantum speedup in quasistatic quantum annealers" {1503.04216</ref> hat das Verständnis dieser Testmetriken und ihrer Abhängigkeit von äquilibrierten Systemen vorangetrieben, wodurch jegliche Signaturen von Vorteilen aufgrund der Quantendynamik fehlen.
Es gibt viele offene Fragen bezüglich der Quantenbeschleunigung. Die ETH-Referenz im vorigen Abschnitt bezieht sich nur auf eine Klasse von Benchmark-Problemen. Möglicherweise.[28]
Im Dezember 2015 gab Google bekannt, dass die D-Welle 2X sowohl Simulated Annealing als auch Quantum Monte Carlo bei einer Reihe von harten Optimierungsproblemen um bis zu einem Faktor von 100.000.000 übertrifft.[29]
Die Architektur von D-Wave unterscheidet sich von traditionellen Quantencomputern. Es ist nicht bekannt, dass es polynomial äquivalent zu einem universellen Quantencomputer ist und insbesondere kann es nicht Shor's Algorithmus ausführen, da der Shor'sche Algorithmus kein Hillclimbing-Prozess ist. Der Shor'sche Algorithmus erfordert einen universellen Quantencomputer. D-Wave behauptet, nur Quantenglühen durchzuführen.{Vorlage:Zitat benötigt
References
[Bearbeiten | Quelltext bearbeiten]Further reading
[Bearbeiten | Quelltext bearbeiten]- Salvador E. Venegas-Andraca, William Cruz-Santos, Catherine McGeoch, Marco Lanzagorta: A cross-disciplinary introduction to quantum annealing-based algorithms. In: Contemporary Physics. 59. Jahrgang, Nr. 2, 2018, S. 174–197, doi:10.1080/00107514.2018.1450720, arxiv:1803.03372, bibcode:2018ConPh..59..174V.
- ? (iop.org).
- S. Suzuki, J.-i. Inoue & B. K. Chakrabarti, Quantum Ising Phases & Transitions in Transverse Ising Models, Springer, Heidelberg (2013), Chapter 8 on Quantum Annealing.
- V. Bapst, L. Foini, F. Krzakala, G. Semerjian, F. Zamponi: The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective. In: Physics Reports. 523. Jahrgang, Nr. 3, 2013, S. 127–205, doi:10.1016/j.physrep.2012.10.002, arxiv:1210.0811, bibcode:2013PhR...523..127B.
- Arnab Das and Bikas K Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, 679, Springer, Heidelberg (2005).
- Anjan K. Chandra, Arnab Das and Bikas K Chakrabarti (Eds.), Quantum Quenching, Annealing and Computation, Lecture Note in Physics, 802, Springer, Heidelberg (2010).
- Fuxiang Li, V. Y. Chernyak, N. A. Sinitsyn: Quantum Annealing and Computation: A Brief Documentary Note. 2013, arxiv:1310.1339, bibcode:2013arXiv1310.1339G. .
- A. Dutta, G. Aeppli, B. K. Chakrabarti, U. Divakaran, T.F. Rosenbaum & D. Sen, "Quantum Phase Transitions in Transverse Field Spin Models: From Statistical Physics to Quantum Information, Cambridge University Press, Cambridge & Delhi (2015).
- S. Tanaka, R. Tamura & B. K. Chakrabarti, Quantum Spin Glasses, Annealing & Computation, Cambridge University Press, Cambridge & Delhi (2017).
- Indian Science News Association, Special Issue of "Science & Culture" on 'A Quantum Jump in Computation', Vol. 85 (5-6), May-June (2019)
Vorlage:Optimization algorithms Vorlage:Quantum information [[Category:Stochastic optimization]] [[Category:Optimization algorithms and methods]] [[Category:Quantum algorithms]]
- ↑ a b P. Ray, B. K. Chakrabarti, Arunava Chakrabarti: Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations. In: Physical Review B. 39. Jahrgang, Nr. 16, 1989, S. 11828–11832, doi:10.1103/PhysRevB.39.11828, PMID 9948016, bibcode:1989PhRvB..3911828R.
- ↑ T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model" Phys. Rev. E 58, 5355 (1998). doi:10.1103/PhysRevE.58.5355.
- ↑ A.B. Finnila, M.A. Gomez, C. Sebenik, C. Stenson, J.D. Doll: Quantum annealing: A new method for minimizing multidimensional functions. In: Chemical Physics Letters. 219. Jahrgang, Nr. 5–6, 1994, S. 343–348, doi:10.1016/0009-2614(94)00117-0, arxiv:chem-ph/9404003, bibcode:1994CPL...219..343F.
- ↑ E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Ludgren and D. Preda, "A Quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem" Science 292, 472 (2001). doi:10.1126/science.1057726.
- ↑ E. Crosson, E. Farhi, C.Y-Y. Lin, H-H. Lin, and P. Shor, "Different Strategies for Optimization Using the Quantum Adiabatic Algorithm" arxiv:1401.7320
- ↑ D. Muthukrishnan, T. Albash, and D.A. Lidar, "When Diabatic Trumps Adiabatic in Quantum Optimization" arxiv:1505.01249
- ↑ J. Brooke, D. Bitko, T. F. Rosenbaum and G. Aeppli, "Quantum annealing of a disordered magnet", Science 284 779 (1999)
- ↑ S.E. Venegas-Andraca, W. Cruz-Santos, C. McGeoch, and M. Lanzagorta, "A cross-disciplinary introduction to quantum annealing-based algorithms". Contemporary Physics 59(2), pp. 174–196 (2018). doi:10.1080/00107514.2018.1450720. arxiv:1803.03372
- ↑ Satoshi Morita, Hidetoshi Nishimori: Mathematical foundation of quantum annealing. In: Journal of Mathematical Physics. 49. Jahrgang, Nr. 12, 2008, S. 125210, doi:10.1063/1.2995837, arxiv:0806.1859, bibcode:2008JMP....49l5210M.
- ↑ G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: quantum annealing through adiabatic evolution" J. Phys. A 39, R393 (2006)
- ↑ B. Heim, T. F. Rønnow, S. V. Isakov and M. Troyer, "Quantum versus classical annealing of Ising spin glasses" Science 348, pp. 215–217 (2015)
- ↑ local/global minima/maxima.
- ↑ A. Das, B.K. Chakrabarti, and R.B. Stinchcombe, "Quantum annealing in a kinetically constrained system", Phys. Rev. E 72 art. 026701 (2005)
- ↑ See e.g., S. Mukherjee, and B. K. Chakrabarti "Multivariable Optimization: Quantum Annealing & Computation", Eur. Phys. J. ST 224 pp 17–24 (2015) arxiv:1408.3262
- ↑ A. Das, B. K. Chakrabarti: Quantum Annealing and Analog Quantum Computation. In: Rev. Mod. Phys. 80. Jahrgang, Nr. 3, 2008, S. 1061–1081, doi:10.1103/RevModPhys.80.1061, arxiv:0801.2193, bibcode:2008RvMP...80.1061D.
- ↑ F. Li, V. Y. Chernyak, N. A. Sinitsyn: Quantum annealing and thermalization: insights from integrability. In: Physical Review Letters. 121. Jahrgang, Nr. 19, 2018, S. 190601, doi:10.1103/PhysRevLett.121.190601, PMID 30468584, arxiv:1804.00371, bibcode:2018arXiv180400371L.
- ↑ M. W. Johnson et al, "Quantum annealing with manufactured spins", Nature 473' 194 (2011)
- ↑ title=Learning to program the D-Wave One }
- ↑ url=http://www.dwavesys.com/en/pressreleases.html#lm_2011
- ↑ N. Jones, "Google und NASA schnappen sich Quantencomputer", Nature (2013), {10.1038/nature.2013.12999
- ↑ V. N. Smelyanskiy, E. G. Rieffel, S. I. Knysh, C. P. Williams, M. W. Johnson, M. C. Thom, W. G. Macready, K. L. Pudenz, "A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration", arxiv:2821 1204. 2821 1204. 2821}}
- ↑ S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, M. Troyer, "Beweise für Quantenglühen mit mehr als hundert Qubits", Naturphysik, 10, S. 218-224 (2014)"
- ↑ D-Wave Systems Building Quantum Application Ecosystem, kündigt Partnerschaften mit der DNA-SEQ Alliance und 1QBit. In: D-Wave Systems. Abgerufen am 22. Juni 2014. }
- ↑ title=1QBit Research
- ↑ Vorlage:Zitierte Zeitschrift}
- ↑ Helmut Katzgraber, zitiert in Cho.
- ↑ Vorlage:Citation.
- ↑ Vorlage:Citation
- ↑ Wann kann Quantum Annealing gewinnen? In: Forschungs-Blog. Abgerufen am 21. Januar 2016. }