Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Natural Computing
Erschienen in: Natural Computing 4/2019

20.09.2019

An overview of quantum cellular automata

verfasst von: P. Arrighi

Erschienen in: Natural Computing | Ausgabe 4/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Quantum cellular automata are arrays of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same). Quantum cellular automata provide a model/architecture for distributed quantum computation. More generally, they encompass most of discrete-space discrete-time quantum theory. We give an overview of their theory, with particular focus on structure results; computability and universality results; and quantum simulation results.
Vorheriger Artikel Turns of different angles and discrete-continuous pedestrian dynamics model
Nächster Artikel A new fixed point theorem in domain theory

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
Ahlbrecht A, Scholz VB, Werner AH (2011) Disordered quantum walks in one lattice dimension. J Math Phys 52(10):102201MathSciNetMATH
Ahlbrecht A, Alberti A, Meschede D, Scholz VB, Werner AH, Werner RF (2012) Molecular binding in interacting quantum walks. New J Phys 14(7):073050
Ambainis A, Childs AM, Reichardt BW, Špalek R, Zhang S (2010) Any and-or formula of size n can be evaluated in time n\(^{\wedge }\)1/2+o(1) on a quantum computer. SIAM J Comput 39(6):2513–2530MathSciNetMATH
Andreu A, Pablo A, Pablo A, Di Molfetta G, Iván M, Dirac PM (2019) Lindblad and telegraph equations. Manuscript, Open quantum walks
Arnault P, Di Molfetta G, Brachet M, Debbasch F (2016) Quantum walks and non-Abelian discrete gauge theory. Phys Rev A 94(1):012335MathSciNet
Arnault P, Pérez A, Arrighi P, Farrelly T (2019) Discrete-time quantum walks as fermions of lattice Gauge theory. Phys Rev A 99:032110
Arrighi P, Fargetton R (2007) Intrinsically universal one-dimensional quantum cellular automata. In: Proceedings of DCM
Arrighi P, Grattage J (2010) A simple \(n\)-dimensional intrinsically universal quantum cellular automaton. Lang Autom Theory Appl 6031:70–81MathSciNetMATH
Arrighi P, Dowek G (2010) On the completeness of quantum computation models. In: Programs, Proofs, Processes: 6th Conference on Computability in Europe, CIE, 2010, Ponta Delgada, Azores, Portugal, June 30–July 4, 2010, Proceedings, vol 6158, pp 21–30
Arrighi P, Dowek G (2012) The physical Church–Turing thesis and the principles of quantum theory. Int J Found Comput Sci 23:1131–1145MathSciNetMATH
Arrighi P, Grattage J (2010) A quantum game of life. In: Second symposium on cellular automata “Journées Automates Cellulaires” (JAC 2010), Turku, 2010. TUCS Lecture Notes, vol 13, pp 31–42
Arrighi P, Nesme V (2010) The block neighborhood. In: TUCS (ed) Proceedings of JAC 2010, Turku, Finlande, pp 43–53
Arrighi P, Nesme V (2011) A simple block representation of reversible cellular automata with time-symmetry. In: 17th international workshop on cellular automata and discrete complex systems, (AUTOMATA 2011), Santiago de Chile
Arrighi P, Grattage J (2012a) Intrinsically universal \(n\)-dimensional quantum cellular automata. J Comput Syst Sci 78:1883–1898MathSciNetMATH
Arrighi P, Grattage J (2012b) Partitioned quantum cellular automata are intrinsically universal. Nat Comput 11:13–22MathSciNetMATH
Arrighi P, Facchini S (2013) Decoupled quantum walks, models of the klein-gordon and wave equations. EPL (Europhys Lett) 104(6):60004
Arrighi P, Nesme V, Werner RF (2008) Quantum cellular automata over finite, unbounded configurations. In: Proceedings of LATA, Lecture Notes in Computer Science, vol 5196. Springer, Berlin, pp 64–75
Arrighi P, Fargetton R, Wang Z (2009) Intrinsically universal one-dimensional quantum cellular automata in two flavours. Fundam Inform 21:1001–1035MathSciNetMATH
Arrighi P, Nesme V, Werner R (2010) Unitarity plus causality implies localizability. J Comput Syst Sci 77:372–378MathSciNetMATH
Arrighi P, Nesme V, Werner R (2011a) Unitarity plus causality implies localizability (full version). J Comput Syst Sci 77(2):372–378MATH
Arrighi P, Nesme V, Werner RF (2011b) One-dimensional quantum cellular automata. IJUC 7(4):223–244MATH
Arrighi P, Fargetton R, Nesme V, Thierry E (2011c) Applying causality principles to the axiomatization of Probabilistic Cellular Automata. In: Proceedings of CiE 2011, Sofia, June 2011, LNCS, vol 6735, pp 1–10MATH
Arrighi P, Nesme V, Forets M (2014a) The dirac equation as a quantum walk: higher dimensions, observational convergence. J Phys A Math Theor 47(46):465302MathSciNetMATH
Arrighi P, Stefano F, Marcelo F (2014b) Discrete lorentz covariance for quantum walks and quantum cellular automata. New J Phys 16(9):093007MathSciNet
Arrighi P, Facchini S, Forets M (2016) Quantum walking in curved spacetime. Quantum Inf Process 15:3467–3486MathSciNetMATH
Avalle M, Genoni MG, Serafini A (2015) Quantum state transfer through noisy quantum cellular automata. J Phys A Math Theor 48(19):195304MathSciNetMATH
Benjamin SC (2000) Schemes for parallel quantum computation without local control of qubits. Phys Rev A 61(2):020301
Bialynicki-Birula I (1994) Weyl, Dirac, and Maxwell equations on a lattice as unitary cellular automata. Phys Rev D 49(12):6920–6927MathSciNet
Bibeau-Delisle A, Bisio A, D’Ariano GM, Perinotti P, Tosini A (2015) Doubly special relativity from quantum cellular automata. EPL (Europhys Lett) 109(5):50003
Bisio A, D’Ariano GM, Tosini A (2012) Quantum field as a quantum cellular automaton i: the dirac free evolution in one dimension. ArXiv preprint arXiv:​1212.​2839
Bisio A, D’Ariano GM, Perinotti P (2017) Quantum walks, Weyl equation and the Lorentz group. Found Phys 47(8):1065–1076MathSciNetMATH
Bisio A, D’Ariano GM, Perinotti P, Tosini A (2018) Thirring quantum cellular automaton. Phys Rev A 97(3):032132
Bloch I (2005) Ultracold quantum gases in optical lattices. Nat Phys 1(1):23–30
Boghosian BM, Taylor W (1998) Quantum lattice-gas model for the many-particle Schrödinger equation in d-dimensions. Phys Rev E 57(1):54–66MathSciNet
Bose S (2007) Quantum communication through spin chain dynamics: an introductory overview. Contemp Phys 48(1):13–30
Bratteli O, Robinson D (1987) Operators algebras and quantum statistical mechanics. Springer, New YorkMATH
Brennen GK, Williams JE (2003) Entanglement dynamics in one-dimensional quantum cellular automata. Phys Rev A 68(4):042311MathSciNet
Cedzich C, Rybár T, Werner AH, Alberti A, Genske M, Werner RF (2013) Propagation of quantum walks in electric fields. Phys Rev Lett 111(16):160601
Chandrashekar CM, Banerjee S, Srikanth R (2010) Relationship between quantum walks and relativistic quantum mechanics. Phys Rev A 81(6):62340
Cirac JI, Perez-Garcia D, Schuch N, Verstraete F (2017) Matrix product unitaries: structure, symmetries, and topological invariants. J Stat Mech Theory Exp 8(2017):083105MathSciNet
Debbasch F (2018) Action principles for quantum automata and lorentz invariance of discrete time quantum walks. ArXiv preprint arXiv:​1806.​02313
Destri C, de Vega HJ (1987) Light cone lattice approach to fermionic theories in 2-d: the massive thirring model. Nucl Phys B 290:363MathSciNet
di Molfetta G, Debbasch F (2012) Discrete-time quantum walks: continuous limit and symmetries. J Math Phys 53(12):123302–123302MathSciNetMATH
Di Molfetta G, Pérez A (2016) Quantum walks as simulators of neutrino oscillations in a vacuum and matter. New J Phys 18(10):103038
Di Molfetta G, Arrighi P (2019) A quantum walk with both a continuous-time discrete-space limit and a continuous spacetime limit. Manuscript
Di Molfetta G, Brachet M, Debbasch F (2014) Quantum walks in artificial electric and gravitational fields. Phys A Stat Mech Appl 397:157–168MathSciNetMATH
Durand-Lose J (2001) Representing reversible cellular automata with reversible block cellular automata. Discret Math Theor Comput Sci 145:154MATH
Dürr C, Santha M (1996) A decision procedure for unitary linear quantum cellular automata. In: Proceedings of the 37th IEEE symposium on foundations of computer science. IEEE, pp 38–45
Dürr C, Le Thanh H, Santha M (1996) A decision procedure for well-formed linear quantum cellular automata. In: Proceedings of STACS 96, Lecture Notes in Computer Science. Springer, pp 281–292
D’Ariano GM, Perinotti P (2013) Derivation of the Dirac equation from principles of information processing. Pre-print arXiv:​1306.​1934
Eisert J, Gross D (2009) Supersonic quantum communication. Phys Rev Lett 102(24):240501
Farrelly T (2019) A review of quantum cellular automaton (To appear on the arXiv)
Farrelly TC, Short AJ (2014) Causal fermions in discrete space–time. Phys Rev A 89(1):012302
Farrelly TC (2015) Insights from quantum information into fundamental physics. PhD thesis, University of Cambridge arXiv:​1708.​08897
Feynman RP (1982) Simulating physics with computers. Int J Theor Phys 21(6):467–488MathSciNet
Feynman RP (1986) Quantum mechanical computers. Found Phys (Hist Arch) 16(6):507–531MathSciNet
Fitzsimons J, Twamley J (2006) Globally controlled quantum wires for perfect qubit transport, mirroring, and computing. Phys Rev Lett 97(9):90502
Gandy R (1980) Church’s thesis and principles for mechanisms. In: The Kleene Symposium, North-Holland Publishing Company, Amsterdam
Genske M, Alt W, Steffen A, Werner AH, Werner RF, Meschede D, Alberti A (2013) Electric quantum walks with individual atoms. Phys Rev Lett 110(19):190601
Gross D, Nesme V, Vogts H, Werner RF (2012) Index theory of one dimensional quantum walks and cellular automata. Commun Math Phys 310(2):419–454MathSciNetMATH
Gu M, Weedbrook C, Perales A, Nielsen MA (2009) More really is different. Phys D Nonlinear Phenom 238(9–10):835–839MathSciNetMATH
Gütschow J (2010) Entanglement generation of Clifford quantum cellular automata. Appl Phys B 98:623–633MATH
Gütschow J, Uphoff S, Werner RF, Zimborás Z (2010) Time asymptotics and entanglement generation of Clifford quantum cellular automata. J Math Phys 51(1):015203MathSciNetMATH
Gütschow J, Nesme V, Werner RF (2012) Self-similarity of cellular automata on abelian groups. J Cell Autom 7(2):83–113MathSciNetMATH
Haah J, Fidkowski L, Hastings MB (2018) Nontrivial quantum cellular automata in higher dimensions. ArXiv preprint arXiv:​1812.​01625
Ibarra OH, Jiang T (1987) On the computing power of one-way cellular arrays. In: Proceedings of ICALP 87. Springer, London, pp 550–562
Inokuchi S, Mizoguchi Y (2005) Generalized partitioned quantum cellular automata and quantization of classical CA. Int J Unconv Comput 1(2):149–160
Joye A, Merkli M (2010) Dynamical localization of quantum walks in random environments. J Stat Phys 140(6):1–29MathSciNetMATH
Karafyllidis IG (2004) Definition and evolution of quantum cellular automata with two qubits per cell. Phys Rev A 70:044301
Kari J (1991) Reversibility of 2D cellular automata is undecidable. In: Cellular automata: theory and experiment, vol 45. MIT Press, pp 379–385
Kari J (1996) Representation of reversible cellular automata with block permutations. Theory Comput Syst 29(1):47–61MathSciNetMATH
Kari J (1999) On the circuit depth of structurally reversible cellular automata. Fundam Inform 38(1–2):93–107MathSciNetMATH
Kari K (2005) Theory of cellular automata: a survey. Theor Comput Sci 334:2005MathSciNet
Kieu TD (2003) Computing the non-computable. Contemp Phys 44(1):51–71
Love P, Boghosian B (2005) From Dirac to diffusion: decoherence in quantum lattice gases. Quantum Inf Process 4(4):335–354MATH
Mallick A, Chandrashekar CM (2016) Dirac cellular automaton from split-step quantum walk. Sci Rep 6:25779
Mallick A, Mandal S, Karan A, Chandrashekar CM (2019) Simulating dirac hamiltonian in curved space-time by split-step quantum walk. J Phys Commun 3(1):015012
Marcos D, Widmer P, Rico E, Hafezi M, Rabl P, Wiese U-J, Zoller P (2014) Two-dimensional lattice gauge theories with superconducting quantum circuits. Ann Phys 351:634–654MathSciNetMATH
Mauro DAG, Franco M, Paolo P, Alessandro T (2014) The feynman problem and fermionic entanglement: fermionic theory versus qubit theory. Int J Mod Phys A 29(17):1430025MathSciNetMATH
Mazoyer J (1987) A six-state minimal time solution to the firing squad synchronization problem. Theor Comput Sci 50:183–238MathSciNetMATH
Meyer DA (1996) From quantum cellular automata to quantum lattice gases. J Stat Phys 85:551–574MathSciNetMATH
Meyer DA, Shakeel A (2016) Quantum cellular automata without particles. Phys Rev A 93(1):012333
Márquez-Martín I, Di Molfetta G, Pérez A (2017) Fermion confinement via quantum walks in (2+ 1)-dimensional and (3+ 1)-dimensional space-time. Phys Rev A 95(4):042112
Nagaj D, Wocjan P (2008) Hamiltonian quantum cellular automata in one dimension. Phys Rev A 78(3):032311
Nielsen MA (1997) Computable functions, quantum measurements, and quantum dynamics. Phys Rev Lett 79(15):2915–2918
Nielsen MA, Chuang IL (2000) Quantum computation and quantum information. Cambridge University Press, CambridgeMATH
Paz JP, Zurek WH (2002) Environment-induced decoherence and the transition from quantum to classical. In: Fundamentals of quantum information, Lecture Notes in Physics. Springer, Berlin, pp 77–148
Pérez-Delgado CA, Cheung D (2007) Local unreversible cellular automaton ableitary quantum cellular automata. Phys Rev A 76(3):32320MathSciNet
Raussendorf R (2005) Quantum cellular automaton for universal quantum computation. Phys Rev A 72(2):22301MathSciNet
Raynal P (2017) Simple derivation of the Weyl and Dirac quantum cellular automata. Phys Rev A 95:062344
Robens C, Brakhane S, Meschede D, Alberti A (2017) Quantum walks with neutral atoms: quantum interference effects of one and two particles. In: Laser spectroscopy: XXII international conference on laser spectroscopy (ICOLS2015). World Scientific, pp 1–15
Sansoni L, Sciarrino F, Vallone G, Mataloni P, Crespi A, Ramponi R, Osellame R (2012) Two-particle Bosonic-Fermionic quantum walk via integrated photonics. Phys Rev Lett 108:010502
Schaeffer L (2015) A physically universal quantum cellular automaton. In: Jarkko K (ed) Cellular automata and discrete complex systems. Springer, Berlin, pp 46–58MATH
Schlingemann DM, Vogts H, Werner RF (2008) On the structure of Clifford quantum cellular automata. J Math Phys 49:112104MathSciNetMATH
Schumacher B, Werner R (2004) Reversible quantum cellular automata. arXiv pre-print quant-ph/0405174,
Shakeel A, Love PJ (2013) When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)? J Math Phys 54(9):092203MathSciNetMATH
Strauch FW (2006a) Connecting the discrete-and continuous-time quantum walks. Phys Rev A 74(3):030301MathSciNet
Strauch FW (2007) Relativistic effects and rigorous limits for discrete-and continuous-time quantum walks. J Math Phys 48:082102MathSciNetMATH
Subrahmanyam V (2004) Entanglement dynamics and quantum-state transport in spin chains. Phys Rev A 69:034304
Subrahmanyam V, Lakshminarayan A (2006) Transport of entanglement through a Heisenberg-XY spin chain. Phys Lett A 349(1–4):164–169
Succi S, Benzi R (1993) Lattice boltzmann equation for quantum mechanics. Phys D Nonlinear Phenom 69(3):327–332MathSciNetMATH
t’Hooft G (2016) The cellular automaton interpretation of quantum mechanics, vol 185. Fundamental theories of physics. Springer, Berlin
Twamley J (2003) Quantum cellular automata quantum computing with endohedral fullerenes. Phys Rev A 67(5):52318–52500MathSciNet
Vallejo A, Romanelli A, Donangelo R (2018) Initial-state-dependent thermalization in open qubits. Phys Rev A 98(3):032319
Van Dam W (1996) A Universal Quantum Cellular Automaton. In: Proceedings of PhysComp96, Inter Journal manuscript 91. New England Complex Systems Institute, pp 323–331
Van Dam W (1996) Quantum cellular automata. Masters thesis, University of Nijmegen, The Netherlands
Vollbrecht KGH, Cirac JI (2006) Reversible universal quantum computation within translation-invariant systems. Phys Rev A 73(1):012324
von Neumann J (1955) Mathematical foundations of quantum mechanics. Princeton University Press, PrincetonMATH
von Neumann J (1966) Theory of self-reproducing automata. University of Illinois Press, Champaign
Wang G (2017) Efficient quantum algorithms for analyzing large sparse electrical networks. Quantum Inf Comput 17(11–12):987–1026MathSciNet
Watrous J (1995) On one-dimensional quantum cellular automata. In: Annual IEEE symposium on foundations of computer science, pp 528–537
Weinstein YS, Hellberg CS (2004) Quantum cellular automata pseudorandom maps. Phys Rev A 69(6):062301MathSciNetMATH
Metadaten
Titel
An overview of quantum cellular automata
verfasst von
P. Arrighi
Publikationsdatum
20.09.2019
Verlag
Springer Netherlands
Erschienen in
Natural Computing / Ausgabe 4/2019
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-019-09762-6

Weitere Artikel der Ausgabe 4/2019

Natural Computing 4/2019 Zur Ausgabe

OriginalPaper

Lattice-based versus lattice-free individual-based models: impact on coexistence in competitive communities

EditorialNotes

Preface

OriginalPaper

A new fixed point theorem in domain theory

OriginalPaper

State-efficient realization of fault-tolerant FSSP algorithms

OriginalPaper

A regularization-reinforced DBN for digital recognition

OriginalPaper

Self-adaptive fruit fly optimizer for global optimization