Quantum cellular automaton

Short description: Abstract model of quantum computation

A quantum cellular automaton (QCA) is an abstract model of quantum computation, devised in analogy to conventional models of cellular automata introduced by John von Neumann.

The same name may also refer to quantum dot cellular automata, which are a proposed physical implementation of "classical" cellular automata by exploiting quantum mechanical phenomena. QCA have attracted attention in nanofabrication, due to its extremely small feature size (at the molecular or even atomic scale) and ultra-low power consumption. This makes it a candidate for replacing CMOS technology.

## Contents

* 1 Usage of the term
* 2 Models
* 2.1 Early proposals
* 2.2 Models of universal quantum computation
* 2.3 Models of physical systems
* 2.4 Quantum dot cellular automata
* 2.5 Models of particle physics
* 3 See also
* 4 References

## Usage of the term

In the context of models of computation or of physical systems, quantum cellular automaton refers to the merger of elements of both (1) the study of cellular automata in conventional computer science and (2) the study of quantum information processing. In particular, the following are features of models of quantum cellular automata:

* The computation is considered to come about by parallel operation of multiple computing devices, or cells. The cells are usually taken to be identical, finite-dimensional quantum systems (e.g. each cell is a qubit).
* Each cell has a neighborhood of other cells. Altogether these form a network of cells, which is usually taken to be regular (e.g. the cells are arranged as a lattice with or without periodic boundary conditions).
* The evolution of all of the cells has a number of physics-like symmetries. Locality is one: the next state of a cell depends only on its current state and that of its neighbours. Homogeneity is another: the evolution acts the same everywhere, and is independent of time.
* The state space of the cells, and the operations performed on them, should be motivated by principles of quantum mechanics.

Another feature that is often considered important for a model of quantum cellular automata is that it should be universal for quantum computation (i.e. that it can efficiently simulate quantum Turing machines,[1][2] some arbitrary quantum circuit[3] or simply all other quantum cellular automata[4][5]).

Models which have been proposed recently impose further conditions, e.g. that quantum cellular automata should be reversible and/or locally unitary, and have an easily determined global transition function from the rule for updating individual cells.[2] Recent results show that these properties can be derived axiomatically, from the symmetries of the global evolution.[6][7][8]

## Models

### Early proposals

In 1982, Richard Feynman suggested an initial approach to quantizing a model of cellular automata.[9] In 1985, David Deutsch presented a formal development of the subject.[10] Later, Gerhard Grössing and Anton Zeilinger introduced the term "quantum cellular automata" to refer to a model they defined in 1988,[11] although their model had very little in common with the concepts developed by Deutsch and so has not been developed significantly as a model of computation.

### Models of universal quantum computation

The first formal model of quantum cellular automata to be researched in depth was that introduced by John Watrous.[1] This model was developed further by Wim van Dam,[12] as well as Christoph Dürr, Huong LêThanh, and Miklos Santha,[13][14] Jozef Gruska.[15] and Pablo Arrighi.[16] However it was later realised that this definition was too loose, in the sense that some instances of it allow superluminal signalling.[6][7] A second wave of models includes those of Susanne Richter and Reinhard Werner,[17] of Benjamin Schumacher and Reinhard Werner,[6] of Carlos Pérez-Delgado and Donny Cheung,[2] and of Pablo Arrighi, Vincent Nesme and Reinhard Werner.[7][8] These are all closely related, and do not suffer any such locality issue. In the end one can say that they all agree to picture quantum cellular automata as just some large quantum circuit, infinitely repeating across time and space. Recent reviews of the topic are available here.[18][19]

### Models of physical systems

Models of quantum cellular automata have been proposed by David Meyer,[20][21] Bruce Boghosian and Washington Taylor,[22] and Peter Love and Bruce Boghosian[23] as a means of simulating quantum lattice gases, motivated by the use of "classical" cellular automata to model classical physical phenomena such as gas dispersion.[24] Criteria determining when a quantum cellular automaton (QCA) can be described as quantum lattice gas automaton (QLGA) were given by Asif Shakeel and Peter Love.[25]

### Quantum dot cellular automata

Main article: Quantum dot cellular automaton

A proposal for implementing classical cellular automata by systems designed with quantum dots has been proposed under the name "quantum cellular automata" by Doug Tougaw and Craig Lent,[26] as a replacement for classical computation using CMOS technology. In order to better differentiate between this proposal and models of cellular automata which perform quantum computation, many authors working on this subject now refer to it as "quantum dot cellular automaton".

### Models of particle physics

Many QCAs that simulate quantum field theories in the continuum limit have been devised, and some of them are variants of QCAs on fermionic cells—the so-called Fermionic Cellular Automata (FCA). The simplest ones are Dirac QCAs that, for low-momentum and low mass regime, behave like a Dirac particle.[27][28] The massless version of one of the Dirac QCAs, also known as Weyl QCA, was shown to reproduce the dynamics and statistics of the electromagnetic field in vacuum.[29] Some other QCAs that simulate quantum electrodynamics have also been constructed.[30] However, there remain some problems with these models. For instance, it is not clear how to define a free Dirac vacuum in such models that is stable.[31]

## See also

* Quantum finite automata
* Physics:Quantum Hall effect - Electromagnetic effect in physics

## References

1. ↑ 1.0 1.1 Watrous, John (1995). "On one-dimensional quantum cellular automata". Proceedings of IEEE 36th Annual Foundations of Computer Science. Los Alamitos, CA. pp. 528–537. doi:10.1109/SFCS.1995.492583. ISBN 0-8186-7183-1.
2. ↑ 2.0 2.1 2.2 Pérez-Delgado, Carlos A.; Cheung, Donny (2007). "Local unitary quantum cellular automata". Physical Review A 76 (3). doi:10.1103/PhysRevA.76.032320. Bibcode: 2007PhRvA..76c2320P.
3. ↑ Shepherd, D. J.; Franz, T.; Werner, R. F. (2006). "Universally Programmable Quantum Cellular Automaton". Physical Review Letters 97 (2). doi:10.1103/PhysRevLett.97.020502. PMID 16907423. Bibcode: 2006PhRvL..97b0502S.
4. ↑ Arrighi, Pablo; Fargetton, Renan; Wang, Zizhu (2007). "Intrinsically universal one-dimensional quantum cellular automata in two flavours". arXiv:0704.3961 [quant-ph].
5. ↑ Arrighi, Pablo; Grattage, Jonathan (2010). "A Quantum Game of Life". arXiv:1010.3120 [quant-ph].
6. ↑ 6.0 6.1 6.2 Schumacher, B.; Werner, R. F. (2004). "Reversible quantum cellular automata". arXiv:quant-ph/0405174.
7. ↑ 7.0 7.1 7.2 Arrighi, Pablo; Nesme, Vincent; Werner, Reinhard (2007). "One-dimensional quantum cellular automata over finite, unbounded configurations". arXiv:0711.3517 [quant-ph].
8. ↑ 8.0 8.1 Arrighi, Pablo; Nesme, Vincent; Werner, Reinhard (2007). "Unitarity plus causality implies localizability". arXiv:0711.3975 [quant-ph].
9. ↑ Feynman, Richard P. (1982). "Simulating physics with computers". International Journal of Theoretical Physics 21 (6–7): 467–488. doi:10.1007/BF02650179. Bibcode: 1982IJTP...21..467F.
10. ↑ Deutsch, David (1985). "Quantum theory, the Church–Turing principle and the universal quantum computer". Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400 (1818): 97–117. doi:10.1098/rspa.1985.0070. Bibcode: 1985RSPSA.400...97D.
11. ↑ Grössing, Gerhard; Zeilinger, Anton (1988). "Quantum cellular automata" (in en). Complex Systems 2 (2): 197–208. https://www.oeaw.ac.at/fileadmin/Institute/IQOQI-Vienna/PDF/publications-zeilinger/1988_-_Complex_Systems_-_Quantum_Cellular_Automata.pdf.
12. ↑ W. van Dam, "Quantum cellular automata", Master Thesis, Computer Science Nijmegen, Summer 1996.
13. ↑ Durr, Christoph; Santha, Miklos (1996). "A decision procedure for unitary linear quantum cellular automata". arXiv:quant-ph/9604007.
14. ↑ http://www.arxiv.org/abs/cs.DS/9906024
15. ↑ J. Gruska, "Quantum Computing", McGraw-Hill, Cambridge 1999: Section 4.3.
16. ↑ Arrighi, Pablo (2005). "An algebraic study of unitary one dimensional quantum cellular automata". arXiv:quant-ph/0512040.
17. ↑ Richter, S.; Werner, R. F. (1996). "Ergodicity of quantum cellular automata". Journal of Statistical Physics 82 (3–4): 963–998. doi:10.1007/BF02179798. Bibcode: 1996JSP....82..963R.
18. ↑ Arrighi, Pablo (2019). "An overview of Quantum Cellular Automata". arXiv:1904.12956 [quant-ph].
19. ↑ Farrelly, Terry (2020). "A review of Quantum Cellular Automata". Quantum 4. doi:10.22331/q-2020-11-30-368. Bibcode: 2020Quant...4..368F.
20. ↑ Meyer, David A. (1996). "From quantum cellular automata to quantum lattice gases". Journal of Statistical Physics 85 (5–6): 551–574. doi:10.1007/BF02199356. Bibcode: 1996JSP....85..551M.
21. ↑ Meyer, David A. (1996). "On the absence of homogeneous scalar unitary cellular automata". Physics Letters A 223 (5): 337–340. doi:10.1016/S0375-9601(96)00745-1. Bibcode: 1996PhLA..223..337M.
22. ↑ Boghosian, Bruce M.; Taylor, Washington (1998). "Quantum lattice-gas model for the many-particle Schrödinger equation in d dimensions". Physical Review E 57 (1): 54–66. doi:10.1103/PhysRevE.57.54. Bibcode: 1998PhRvE..57...54B.
23. ↑ Love, Peter J.; Boghosian, Bruce M. (2005). "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases". Quantum Information Processing 4 (4): 335–354. doi:10.1007/s11128-005-7852-4. Bibcode: 2005QuIP....4..335L.
24. ↑ B. Chophard and M. Droz, "Cellular Automata modeling of Physical Systems", Cambridge University Press, 1998.
25. ↑ Shakeel, Asif; Love, Peter J. (2013-09-01). "When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)?". Journal of Mathematical Physics 54 (9): 092203. doi:10.1063/1.4821640. ISSN 0022-2488. Bibcode: 2013JMP....54i2203S.
26. ↑ Tougaw, P. Douglas; Lent, Craig S. (1994). "Logical devices implemented using quantum cellular automata". Journal of Applied Physics 75 (3): 1818–1825. doi:10.1063/1.356375. Bibcode: 1994JAP....75.1818T.
27. ↑ D'Ariano, Giacomo M.; Perinotti, Paolo (2014-12-02). "Derivation of the Dirac equation from principles of information processing". Physical Review A 90 (6). doi:10.1103/PhysRevA.90.062106. ISSN 1050-2947. Bibcode: 2014PhRvA..90f2106D. https://doi.org/10.1103/PhysRevA.90.062106.
28. ↑ Farrelly, Terence C.; Short, Anthony J. (2014-06-16). "Discrete spacetime and relativistic quantum particles". Physical Review A 89 (6). doi:10.1103/physreva.89.062109. ISSN 1050-2947. Bibcode: 2014PhRvA..89f2109F. https://doi.org/10.1103/physreva.89.062109.
29. ↑ Bisio, Alessandro; D'Ariano, Giacomo M.; Perinotti, Paolo (2016). "Quantum cellular automaton theory of light". Annals of Physics 368. doi:10.1016/j.aop.2016.02.009. Bibcode: 2016AnPhy.368..177B. https://doi.org/10.1016/j.aop.2016.02.009.
30. ↑ Arrighi, Pablo; Bény, Cédric; Farrelly, Terry (2020). "A quantum cellular automaton for one-dimensional QED". Quantum Information Processing 19 (3). doi:10.1007/s11128-019-2555-4. Bibcode: 2020QuIP...19...88A.
31. ↑ Gupta, Chaitanya; Short, Anthony J. (2024). "The Dirac Vacuum in Discrete Spacetime". arXiv:2412.03466v1 [quant-ph].

* v
* t
* e

Quantum mechanics

Background|

* Introduction
* History
* timeline
* Glossary
* Classical mechanics
* Old quantum theory

Fundamentals|

* Bra–ket notation
* Casimir effect
* Complementarity
* Density matrix
* Energy level
* ground state
* excited state
* degenerate levels
* Vacuum state
* Zero-point energy
* QED vacuum
* QCD vacuum
* Hamiltonian
* Operator
* Quantum coherence
* Quantum decoherence
* Measurement
* Quantum
* Quantum realm
* Quantum system
* Quantum state
* Quantum number
* Quantum entanglement
* Quantum superposition
* Quantum nonlocality
* Quantum tunnelling
* Quantum levitation
* Quantum fluctuation
* Quantum annealing
* Quantum foam
* Quantum noise
* Heisenberg uncertainty principle
* Spontaneous parametric down-conversion
* Von Neumann entropy
* Spin
* Scattering theory
* Symmetry in quantum mechanics
* Symmetry breaking
* Spontaneous symmetry breaking
* Wave propagation
* Quantum interference
* Wave function
* Wave function collapse
* Wave–particle duality
* Matter wave
* Qubit
* Qutrit
* Observable
* Probability distribution

Formulations|

* Formulations
* Heisenberg
* Interaction
* Matrix mechanics
* Schrödinger
* Path integral formulation
* Phase space

Equations|

* Dirac
* Klein–Gordon
* Pauli
* Rydberg
* Schrödinger

Interpretations|

* Interpretations
* Bayesian
* Consistent histories
* Copenhagen
* de Broglie–Bohm
* Ensemble
* Hidden variables
* Many worlds
* Objective collapse
* Quantum logic
* Relational
* Stochastic
* Transactional
* Cosmological

Experiments|

* Afshar
* Bell's inequality
* Cold Atom Laboratory
* Davisson–Germer
* Delayed-choice quantum eraser
* Double-slit
* Franck–Hertz experiment
* Leggett–Garg inequality
* Mach-Zehnder inter.
* Elitzur–Vaidman
* Popper
* Quantum eraser
* Schrödinger's cat
* Quantum suicide and immortality
* Stern–Gerlach
* Wheeler's delayed choice

Science|

* Q-analog
* List
* Quantum algebra
* Quantum calculus
* Quantum differential calculus
* Quantum geometry
* Quantum group
* Quantum Bayesianism
* Quantum biology
* Quantum chemistry
* Quantum chaos
* Quantum cognition
* Quantum cosmology
* Quantum dynamics
* Quantum economics
* Quantum evolution
* Quantum finance
* Quantum game theory
* Quantum measurement problem
* Quantum mind
* Quantum probability
* Quantum social science
* Quantum stochastic calculus
* Quantum spacetime

Technology|

* Quantum algorithms
* Quantum amplifier
* Quantum cellular automata
* Quantum finite automata
* Quantum electronics
* Quantum logic gates
* Quantum clock
* Quantum channel
* Quantum bus
* Quantum circuit
* Phase qubit
* Matrix isolation
* Quantum dot
* Quantum dot display
* Quantum dot solar cell
* Quantum dot cellular automaton
* Quantum dot single-photon source
* Quantum dot laser
* Quantum well
* Quantum computing
* Timeline
* Quantum cryptography
* Post-quantum cryptography
* Quantum error correction
* Quantum imaging
* Quantum image processing
* Quantum information
* Quantum key distribution
* Quantum machine
* Quantum machine learning
* Quantum metamaterial
* Quantum metrology
* Quantum network
* Quantum neural network
* Quantum optics
* Quantum programming
* Quantum sensors
* Quantum simulator
* Quantum teleportation
* Quantum levitation
* Time travel
* Quantum complexity theory

Extensions|

* Quantum statistical mechanics
* Relativistic quantum mechanics
* Quantum field theory
* Axiomatic quantum field theory
* Quantum field theory in curved spacetime
* Thermal quantum field theory
* Topological quantum field theory
* Local quantum field theory
* Conformal field theory
* Two-dimensional conformal field theory
* Liouville field theory
* History
* Quantum gravity

* Category
* Physics Portal
* Physics WikiProject
* Commons

* v
* t
* e

Richard Feynman

Career|

* Feynman diagram
* Feynman–Kac formula
* Wheeler–Feynman absorber theory
* Bethe–Feynman formula
* Hellmann–Feynman theorem
* Feynman slash notation
* Feynman parametrization
* Path integral formulation
* Parton model
* Sticky bead argument
* One-electron universe
* Quantum cellular automaton
* Rogers Commission Report
* Feynman checkerboard

Works|

* "There's Plenty of Room at the Bottom" (1959)
* The Feynman Lectures on Physics (1964)
* The Character of Physical Law (1965)
* QED: The Strange Theory of Light and Matter (1985)
* Surely You're Joking, Mr. Feynman! (1985)
* What Do You Care What Other People Think? (1988)
* The Motion of Planets Around the Sun (1997)
* The Meaning of It All (1999)
* The Pleasure of Finding Things Out (1999)
* Perfectly Reasonable Deviations from the Beaten Track (2005)

Family|

* Joan Feynman (sister)
* Charles Hirshberg (nephew)

Related|

* Namesakes
* Cargo cult science
* Quantum Man
* Tuva or Bust!
* Feynman Prize in Nanotechnology
* Infinity (1996 film)
* QED (2001 play)
* The Challenger (2013 film)

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Quantum cellular automaton. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Quantum_cellular_automaton&oldid=4369518"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template