Quanten-Zellulärer Automat

Ein Quanten-Zellulärer Automat (QCA, engl. quantum cellular automaton) ist ein abstraktes Modell der Quantenberechnung, das in Analogie zu konventionellen Modellen zellulärer Automaten entwickelt wurde, die von John von Neumann eingeführt wurden. Derselbe Begriff kann sich auch auf Quantenpunkt-Zelluläre Automaten beziehen, die eine vorgeschlagene physikalische Implementierung „klassischer“ zellulärer Automaten darstellen, welche quantenmechanische Phänomene ausnutzen. QCA haben große Aufmerksamkeit erlangt aufgrund ihrer extrem kleinen Strukturgröße (auf molekularer oder sogar atomarer Ebene) und ihres ultra-niedrigen Energieverbrauchs, was sie zu einem Kandidaten für den Ersatz der CMOS-Technologie macht.

Grundlegende Konzepte

Im Kontext von Berechnungsmodellen oder physikalischen Systemen bezieht sich der Begriff Quanten-Zellulärer Automat auf die Verschmelzung von Elementen aus (1) dem Studium zellulärer Automaten in der konventionellen Informatik und (2) dem Studium der Quanteninformationsverarbeitung. Insbesondere weisen Modelle von Quanten-Zellulären Automaten folgende Merkmale auf:

  • Die Berechnung erfolgt durch parallelen Betrieb mehrerer Recheneinheiten oder Zellen. Die Zellen werden üblicherweise als identische, endlichdimensionale Quantensysteme betrachtet (z. B. ist jede Zelle ein Qubit).
  • Jede Zelle hat eine Nachbarschaft anderer Zellen. Zusammen bilden diese ein Netzwerk von Zellen, das üblicherweise als regelmäßig angenommen wird (z. B. sind die Zellen in einem Gitter mit oder ohne periodische Randbedingungen angeordnet).
  • Die Evolution aller Zellen weist eine Reihe physikähnlicher Symmetrien auf. Eine davon ist die Lokalität: Der nächste Zustand einer Zelle hängt nur von ihrem aktuellen Zustand und dem ihrer Nachbarn ab. Eine weitere ist die Homogenität: Die Evolution wirkt überall gleich und ist zeitunabhängig.
  • Der Zustandsraum der Zellen und die an ihnen durchgeführten Operationen sollten durch Prinzipien der Quantenmechanik motiviert sein.

Ein weiteres Merkmal, das oft als wichtig für ein Modell von Quanten-Zellulären Automaten angesehen wird, ist, dass es universell für die Quantenberechnung sein sollte (d. h., dass es effizient Quanten-Turing-Maschinen,[1][2] beliebige Quantenschaltkreise[3] oder einfach alle anderen Quanten-Zellulären Automaten[4][5] simulieren kann).

Kürzlich vorgeschlagene Modelle stellen weitere Bedingungen auf, beispielsweise dass Quanten-Zellularautomaten reversibel und/oder lokal unitär sein sollten und eine leicht bestimmbare globale Übergangsfunktion aus der Regel zur Aktualisierung einzelner Zellen haben sollten.[2] Jüngere Ergebnisse zeigen, dass diese Eigenschaften axiomatisch aus den Symmetrien der globalen Evolution abgeleitet werden können.[6][7][8]

Geschichte

Zelluläre Automaten wurden um 1940 von Stanislaw Ulam in Los Alamos vorgestellt. John von Neumann, ein damaliger Kollege Ulams, griff die Idee auf und erweiterte sie zu einem universellen Berechnungsmodell. Er stellte einen Zellularautomaten mit 29 Zuständen vor, der ein gegebenes Muster immer wieder selbst reproduzieren kann.

Im Jahr 1982 schlug Richard Feynman einen ersten Ansatz zur Quantisierung eines Modells zellulärer Automaten vor.[9] 1985 präsentierte David Deutsch eine formale Entwicklung des Themas.[10]

Später führten Gerhard Grössing und Anton Zeilinger 1988 den Begriff „Quanten-Zellulärer Automat“ für ein von ihnen definiertes Modell ein,[11] obwohl ihr Modell sehr wenig mit den von Deutsch entwickelten Konzepten gemein hatte und daher nicht wesentlich als Berechnungsmodell weiterentwickelt wurde.

Modelle zu Quanten-Zellulären Automaten

Das erste formale Modell von Quanten-Zellulären Automaten, das eingehend erforscht wurde, war das von John Watrous eingeführte Modell.[1] Dieses Modell wurde von Wim van Dam,[12] sowie von Christoph Dürr, Huong LêThanh und Miklos Santha,[13][14] Jozef Gruska[15] und Pablo Arrighi[16] weiterentwickelt. Es wurde jedoch später erkannt, dass diese Definition zu locker war, in dem Sinne, dass einige Instanzen davon überlichtschnelle Signalübertragung ermöglichen würden.[6][7]

Eine zweite Welle von Modellen umfasst die von Susanne Richter und Reinhard Werner,[17] von Benjamin Schumacher und Reinhard Werner,[6] von Carlos Pérez-Delgado und Donny Cheung,[2] und von Pablo Arrighi, Vincent Nesme und Reinhard Werner.[7][18] Diese sind alle eng verwandt und leiden nicht unter solchen Lokalitätsproblemen. Letztendlich kann man sagen, dass sie alle darin übereinstimmen, Quanten-Zelluläre Automaten als eine Art großen Quantenschaltkreis zu betrachten, der sich unendlich über Zeit und Raum wiederholt. Aktuelle Übersichtsarbeiten zu diesem Thema sind verfügbar.[19][20]

Quantengitter-Gas-Automaten

Modelle von Quanten-Zellulären Automaten wurden von David Meyer,[21][22] Bruce Boghosian und Washington Taylor,[23] sowie Peter Love und Bruce Boghosian[24] als Mittel zur Simulation von Quantengittergasen vorgeschlagen, motiviert durch die Verwendung „klassischer“ zellulärer Automaten zur Modellierung klassischer physikalischer Phänomene wie Gasdispersion.[25] Kriterien zur Bestimmung, wann ein Quanten-Zellulärer Automat (QCA) als Quantengitter-Gas-Automat (QLGA) beschrieben werden kann, wurden von Asif Shakeel und Peter Love gegeben.[26]

Quantenpunkt-Zelluläre Automaten

Ein Vorschlag zur Implementierung klassischer zellulärer Automaten durch Systeme, die mit Quantenpunkten entworfen wurden, wurde unter dem Namen „Quanten-Zellulärer Automat“ von Doug Tougaw und Craig Lent[27] als Ersatz für klassische Berechnungen mit CMOS-Technologie vorgeschlagen. Um zwischen diesem Vorschlag und Modellen zellulärer Automaten, die Quantenberechnungen durchführen, besser zu unterscheiden, bezeichnen viele Autoren, die an diesem Thema arbeiten, dies nun als Quantenpunkt-Zellulärer Automat.

Simulation von Quantenfeldtheorien

Viele QCAs, die Quantenfeldtheorien im Kontinuumslimit simulieren, wurden entwickelt. Der einfachste ist der Dirac-QCA, der sich für niedrige Impuls- und niedrige Massenbereiche wie ein Dirac-Teilchen verhält.[28] Einige andere QCAs, die Quantenelektrodynamik simulieren, wurden ebenfalls konstruiert.[29] Es bleiben jedoch einige Probleme mit diesen Modellen. Zum Beispiel ist nicht klar, wie man in solchen Modellen ein freies Dirac-Vakuum definieren kann, das stabil ist.[30]

Gerard 't Hoofts Interpretation

Der niederländische Physiker und Nobelpreisträger Gerard 't Hooft hat eine deterministische Interpretation der Quantenmechanik entwickelt, die auf zellulären Automaten basiert. In seinem 2016 erschienenen Buch The Cellular Automaton Interpretation of Quantum Mechanics argumentiert 'T Hooft, dass die Quantenmechanik als Werkzeug zur Analyse von Systemen betrachtet werden kann, die im Kern klassisch sind, aber durch Quantentechniken analysiert werden können. Sein Ansatz belebt die Idee verborgener Variabler, jedoch in einer systematischeren Weise als üblich. 't Hooft zeigt, wie dieser Ansatz, obwohl er auf verborgenen Variablen basiert, plausibel mit dem Bell-Theorem in Einklang gebracht werden kann und wie die üblichen Einwände gegen die Idee des „Superdeterminismus“ zumindest im Prinzip überwunden werden können.

Literatur

Grundlegende Arbeiten

  • John von Neumann, Arthur W. Burks (Hrsg.): Theory of Self-Reproducing Automata. University of Illinois Press, Urbana 1966
  • Richard Feynman: Simulating physics with computers. In: International Journal of Theoretical Physics. Band 21, 1982, S. 467–488
  • David Deutsch: Quantum theory, the Church-Turing principle and the universal quantum computer. In: Proceedings of the Royal Society of London A. Band 400, 1985, S. 97–117
  • Gerhard Grössing, Anton Zeilinger: Quantum cellular automata. In: Complex Systems. Band 2, Nr. 2, 1988, S. 197–208 und 611–623

Aktuelle Forschung

  • Gerard 't Hooft: The Cellular Automaton Interpretation of Quantum Mechanics. Springer, 2016, ISBN 978-3-319-41284-9
  • Pablo Arrighi: An overview of quantum cellular automata. arXiv:1904.12956, 2019
  • Terry Farrelly: A review of Quantum Cellular Automata. arXiv:1904.13318, 2019

Deutsche Forschung

  • Klaus Mainzer, Leon Chua: The Universe as Automaton. From Simplicity and Symmetry to Complexity. Springer, Heidelberg 2012, ISBN 978-3-642-23476-7
  • Andreas Deutsch: Zelluläre Automaten als Modelle von Musterbildungsprozessen in biologischen Systemen. In: Rolf Hofestädt u. a. (Hrsg.): Informatik in den Biowissenschaften. Springer, Berlin/Heidelberg 1993
  • Quantentechnologien und Quanten-Ökosysteme. Fraunhofer ISI Studie im Auftrag der Expertenkommission Forschung und Innovation (EFI), 2025

Einzelnachweise

  1. ↑ a b Watrous, John (1995): "On one-dimensional quantum cellular automata", Proc. 36th Annual Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Comput. Soc. Press, S. 528–537
  2. ↑ a b c C. Pérez-Delgado und D. Cheung (2007): "Local Unitary Quantum Cellular Automata", Phys. Rev. A 76, 032320
  3. ↑ D.J. Shepherd, T. Franz, R.F. Werner (2006): "Universally programmable Quantum Cellular Automaton", Phys. Rev. Lett. 97, 020502
  4. ↑ P. Arrighi, R. Fargetton, Z. Wang (2009): "Intrinsically universal one-dimensional quantum cellular automata in two flavours", Fundamenta Informaticae Vol. 91, No. 2, S. 197–230
  5. ↑ P. Arrighi, J. Grattage (2010): "A quantum Game of Life", Proceedings of JAC 2010, Turku, TUCS Lecture Notes 13, S. 31–42
  6. ↑ a b c B. Schumacher, R. Werner: Reversible quantum cellular automata. In: arXiv:quant-ph/0405174, 2004. (online)
  7. ↑ a b c Pablo Arrighi, Vincent Nesme, Reinhard Werner: One-dimensional quantum cellular automata over finite, unbounded configurations. In: arXiv:0711.3517, 2007. (online)
  8. ↑ Pablo Arrighi, Vincent Nesme, Reinhard Werner: N-dimensional quantum cellular automata. In: arXiv:0711.3975, 2007. (online)
  9. ↑ R. Feynman (1982): "Simulating physics with computers", Int. J. Theor. Phys. 21, S. 467–488
  10. ↑ D. Deutsch (1985): "Quantum theory, the Church-Turing principle and the universal quantum computer", Proceedings of the Royal Society of London A 400, S. 97–117
  11. ↑ G. Grossing und A. Zeilinger (1988): "Quantum cellular automata", Complex Systems 2 (2), S. 197–208 und 611–623
  12. ↑ W. van Dam (1996): "Quantum cellular automata", Master Thesis, Computer Science Nijmegen
  13. ↑ C. Dürr und M. Santha: "A decision procedure for unitary linear quantum cellular automata", arXiv:quant-ph/9604007
  14. ↑ C. Dürr, H. LêTanh, M. Santha (1997): "A decision procedure for well-formed linear quantum cellular automata", Rand. Struct. Algorithms 11, S. 381–394
  15. ↑ J. Gruska (1999): Quantum Computing, McGraw-Hill, Cambridge, Section 4.3
  16. ↑ Pablo Arrighi (2006): "An algebraic study of unitary one dimensional quantum cellular automata", Proceedings of MFCS 2006, LNCS 4162, S. 122–133
  17. ↑ S. Richter und R.F. Werner (1996): "Ergodicity of quantum cellular automata", J. Stat. Phys. 82, S. 963–998
  18. ↑ Pablo Arrighi, Vincent Nesme, Reinhard Werner: "N-dimensional quantum cellular automata", arXiv:0711.3975
  19. ↑ P. Arrighi (2019): "An overview of quantum cellular automata", arXiv:1904.12956
  20. ↑ Terry Farrelly (2019): "A review of Quantum Cellular Automata", arXiv:1904.13318
  21. ↑ D. Meyer (1996): "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics 85, S. 551–574
  22. ↑ D. Meyer (1996): "On the absence of homogeneous scalar unitary cellular automata", Physics Letters A 223, S. 337–340
  23. ↑ B. Boghosian und W. Taylor (1998): "Quantum lattice-gas model for the many-particle Schrödinger equation in d dimensions", Physical Review E 57, S. 54–66
  24. ↑ P. Love und B. Boghosian (2005): "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases", Quantum Information Processing 4, S. 335–354
  25. ↑ B. Chophard und M. Droz (1998): Cellular Automata modeling of Physical Systems, Cambridge University Press
  26. ↑ Shakeel, Asif; Love, Peter J. (2013): "When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)?", Journal of Mathematical Physics 54 (9): 092203
  27. ↑ P. Tougaw, C. Lent (1994): "Logical devices implemented using quantum cellular automata", J. Appl. Phys. 75, S. 1818–1825
  28. ↑ Farrelly, Terence C.; Short, Anthony J. (2014): "Discrete spacetime and relativistic quantum particles", Physical Review A 89 (6): 062109
  29. ↑ Arrighi, Pablo; Bény, Cédric; Farrelly, Terry (2020): "A quantum cellular automaton for one-dimensional QED", Quantum Information Processing 19 (3): 88
  30. ↑ "The Dirac Vacuum in Discrete Spacetime" (2024), arXiv:2412.03466v1
Dieser Artikel wurde von Wikipedia herausgegeben. Der Text ist unter Creative Commons Attribution-Share Alike 4.0 verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.