Quantum cellular automaton

Last updated

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 a lot of attention as a result of its extremely small feature size (at the molecular or even atomic scale) and its ultra-low power consumption, making it one candidate for replacing CMOS technology.

Contents

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:

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

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 this as a quantum dot cellular automaton.

See also

Related Research Articles

<span class="mw-page-title-main">Cellular automaton</span> Discrete model studied in computer science

A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.

In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

A cellular automaton (CA) is Life-like if it meets the following criteria:

A continuous automaton can be described as a cellular automaton extended so the valid states a cell can take are not just discrete, but continuous, for example, the real number range [0,1]. The cells however remain discretely separated from each other. One example is called computational verb cellular network (CVCN), of which the states of cells are in the region of [0,1].

<span class="mw-page-title-main">Block cellular automaton</span> Kind of cellular automaton

A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.

A topological quantum computer is a theoretical quantum computer proposed by Russian-American physicist Alexei Kitaev in 1997. It employs quasiparticles in two-dimensional systems, called anyons, whose world lines pass around one another to form braids in a three-dimensional spacetime. These braids form the logic gates that make up the computer. The advantage of a quantum computer based on quantum braids over using trapped quantum particles is that the former is much more stable. Small, cumulative perturbations can cause quantum states to decohere and introduce errors in the computation, but such small perturbations do not change the braids' topological properties. This is like the effort required to cut a string and reattach the ends to form a different braid, as opposed to a ball bumping into a wall.

A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.

Brosl Hasslacher was a theoretical physicist.

Quantum dot cellular automata are a proposed improvement on conventional computer design (CMOS), which have been devised in analogy to conventional models of cellular automata introduced by John von Neumann.

<span class="mw-page-title-main">Von Neumann neighborhood</span> Cellular automaton neighborhood consisting of four adjacent cells

In cellular automata, the von Neumann neighborhood is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, who used it to define the von Neumann cellular automaton and the von Neumann universal constructor within it. It is one of the two most commonly used neighborhood types for two-dimensional cellular automata, the other one being the Moore neighborhood.

The majority problem, or density classification task, is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting.

<span class="mw-page-title-main">Rule 184</span> Elementary cellular automaton

Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:

<span class="mw-page-title-main">Feynman checkerboard</span> Fermion path integral approach in 1+1 dimensions

The Feynman checkerboard, or relativistic chessboard model, was Richard Feynman’s sum-over-paths formulation of the kernel for a free spin-½ particle moving in one spatial dimension. It provides a representation of solutions of the Dirac equation in (1+1)-dimensional spacetime as discrete sums.

<span class="mw-page-title-main">Lattice gas automaton</span> Type of cellular automaton

Lattice gas automata (LGCA), or lattice gas cellular automata, are a type of cellular automaton used to simulate fluid flows, pioneered by Hardy–Pomeau–de Pazzis and Frisch–Hasslacher–Pomeau. They were the precursor to the lattice Boltzmann methods. From lattice gas automata, it is possible to derive the macroscopic Navier–Stokes equations. Interest in lattice gas automaton methods levelled off in the early 1990s, as the interest in the lattice Boltzmann started to rise. However, an LGCA variant, termed BIO-LGCA, is still widely used to model collective migration in biology.

<span class="mw-page-title-main">Vladimir Korepin</span> Russian physicist and mathematician

Vladimir E. Korepin is a professor at the C. N. Yang Institute of Theoretical Physics of the Stony Brook University. Korepin made research contributions in several areas of mathematics and physics.

<span class="mw-page-title-main">John Watrous (computer scientist)</span> Theoretical computer scientist

John Harrison Watrous is the Technical Director of IBM Quantum Education at IBM and was a professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, a member of the Institute for Quantum Computing, an affiliate member of the Perimeter Institute for Theoretical Physics and a Fellow of the Canadian Institute for Advanced Research. He was a faculty member in the Department of Computer Science at the University of Calgary from 2002 to 2006 where he held a Canada Research Chair in quantum computing.

<span class="mw-page-title-main">Epidemic models on lattices</span>

Classic epidemic models of disease transmission are described in Compartmental models in epidemiology. Here we discuss the behavior when such models are simulated on a lattice. Lattice models, which were first explored in the context of cellular automata, act as good first approximations of more complex spatial configurations, although they do not reflect the heterogeneity of space. Lattice-based epidemic models can also be implemented as fixed agent-based models.

Norman H. Margolus is a Canadian-American physicist and computer scientist, known for his work on cellular automata and reversible computing. He is a research affiliate with the Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology.

<span class="mw-page-title-main">Reversible cellular automaton</span> Cellular automaton that can be run backwards

A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.

The following timeline starts with the invention of the modern computer in the late interwar period.

References

  1. 1 2 Watrous, John (1995), "On one-dimensional quantum cellular automata", Proc. 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995), Los Alamitos, CA: IEEE Comput. Soc. Press, pp. 528–537, doi:10.1109/SFCS.1995.492583, ISBN   0-8186-7183-1, MR   1619103, S2CID   7441203 .
  2. 1 2 3 C. Pérez-Delgado and D. Cheung, "Local Unitary Quantum Cellular Automata", Phys. Rev. A 76, 032320, 2007. See also arXiv:0709.0006 (quant-ph)
  3. ↑ D.J. Shepherd, T. Franz, R.F. Werner: Universally programmable Quantum Cellular Automaton. Phys. Rev. Lett. 97, 020502 (2006)
  4. ↑ P. Arrighi, R. Fargetton, Z. Wang, Intrinsically universal one-dimensional quantum cellular automata in two flavours, Fundamenta Informaticae Vol.91, No.2, pp.197-230, (2009). See also (quant-ph)
  5. ↑ P. Arrighi, J. Grattage, A quantum Game of Life, Proceedings of JAC 2010, Turku, December 2010. TUCS Lecture Notes 13, 31-42, (2010). See also (quant-ph) and (Companion Website)
  6. 1 2 3 B. Schumacher and R. Werner, "Reversible quantum cellular automata", quant-ph/0405174
  7. 1 2 3 Pablo Arrighi, Vincent Nesme, Reinhard Werner, One-dimensional quantum cellular automata over finite, unbounded configurations. See also (quant-ph)
  8. 1 2 Pablo Arrighi, Vincent Nesme, Reinhard Werner, N-dimensional quantum cellular automata. See also (quant-ph)
  9. ↑ R. Feynman, "Simulating physics with computers", Int. J. Theor. Phys. 21, 1982: pp. 467–488.
  10. ↑ D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer" Proceedings of the Royal Society of London A 400 (1985), pp. 97–117.
  11. ↑ G. Grossing and A. Zeilinger, "Quantum cellular automata", Complex Systems 2 (2), 1988: pp. 197–208 and 611–623.
  12. ↑ W. van Dam, "Quantum cellular automata", Master Thesis, Computer Science Nijmegen, Summer 1996.
  13. ↑ C. Dürr and M. Santha, "A decision procedure for unitary linear quantum cellular automata", quant-ph/9604007 .
  14. ↑ C. Dürr, H. LêTanh, M. Santha, "A decision procedure for well-formed linear quantum cellular automata", Rand. Struct. Algorithms 11, 1997: pp. 381–394. See also cs.DS/9906024.
  15. ↑ J. Gruska, "Quantum Computing", McGraw-Hill, Cambridge 1999: Section 4.3.
  16. ↑ Pablo Arrighi, An algebraic study of unitary one dimensional quantum cellular automata, Proceedings of MFCS 2006, LNCS 4162, (2006), pp122-133. See also quant-ph/0512040
  17. ↑ S. Richter and R.F. Werner, "Ergodicity of quantum cellular automata", J. Stat. Phys. 82, 1996: pp. 963–998. See also cond-mat/9504001
  18. ↑ P. Arrighi, An overview of quantum cellular automata, arXiv:1904.12956
  19. ↑ Terry Farrelly, A review of Quantum Cellular Automata arXiv:1904.13318
  20. ↑ D. Meyer, "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics 85, 1996: pp. 551–574. See also quant-ph/9604003.
  21. ↑ D. Meyer, "On the absence of homogeneous scalar unitary cellular automata'", Physics Letters A 223, 1996: pp. 337–340. See also quant-ph/9604011.
  22. ↑ B. Boghosian and W. Taylor, "Quantum lattice-gas model for the many-particle Schrödinger equation in d dimensions", Physical Review E 57, 1998: pp. 54–66.
  23. ↑ P. Love and B. Boghosian, "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases", Quantum Information Processing 4, 2005, pp. 335–354.
  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. arXiv: 1209.5367 . Bibcode:2013JMP....54i2203S. doi:10.1063/1.4821640. ISSN   0022-2488. S2CID   2351651.
  26. ↑ P. Tougaw, C. Lent, "Logical devices implemented using quantum cellular automata", J. Appl. Phys. 75, 1994: pp. 1818–1825
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.