Quantum Cellular Automata

Cellular automata (CA) is a discrete system using simple rules and used to model complex systems.  Historically, the initial major contributor to CA was John von Neumann.  von Neumann was trying to find a model of self-replicating systems, a system that could produce exact copies of itself.  Fast forward to the 1980s where Stephen Wolfram made significant contributions to CA by exploring the different rule system, in particular Rule 110 which was postulated to be a universal computational system.  In the early 2000s Matthew Cook along with Wolfram proved that Rule 110 is the simplest known model for universal computation.   Rule 110 is interesting because it exhibits both stable and chaotic patterns.  Rule 110 can be used to simulate a Turing machine,  which is an abstract machine that uses a rule based system for taking a list of some arbitrary sets and manipulates the symbols on the list.


Classical CA has many applications; classification of patterns in nature, chemical reactions, cryptography, random number generators, etc.  However, this article is going to concentrate on quantum CA, where the cells are considered to be qubits in quantum computing.  Think of a quit as the quantum analog to the classical bit (i.e. states 0 or 1), except the qubit is a tow dimensional quantum mechanical system, the quit is a superposition of both 0 and 1 states at the same time.  However, before we get too deep into quits, superposition, and quantum computing, it will be necessary to review some basic quantum theory, specifically the double slit experiment, the work of Neil Born, waves packets and probability, free particle nation, and four postulate of quantum mechanics.


Double Slit Experiment

In physical optics interference patterns are produced by the superposition of waves E and H, and the intensity of the fringes is measured by E2 and H2.  The wave describes the behavior of a beam of hydrogen atoms, and the observed diffraction patterns are the result.    Interference patterns occur only after many independent particles pass through the slits and hit the screen.  Each particle retains its discrete individuality and each travels its own path towards the screen.  When many particles have come through, a regular interference pattern will be formed:


The conclusion is that the wave function ψ describes the behavior of the particles, and has a probabilistic meaning.  The quantity |ψ|2 measures the chance of finding the particle at a certain place.  The appearance of the interference pattern depends on the passage of the wave through both slits at once.  If the wave describes the behavior of a single particle, then it can not be decided which one of the slits the particle has gone.  interestingly, the exact same traces are obtained if one of the slits are closed.  Therefore, the conditions which the interference pattern is produced forbid a determination of the slit through which the particle passes.

Neil Born and Probability Waves

Born suggested in 1927 that |ψ|is termed a probability density.  The function ψ is called thew wave function or state vector of the particle.  The Born postulate states the wave function for the particle ψ(x,y,z,t) is such that :

|ψ|2dxdydz = Pdxdydz

where Pdxdydz is the probability that measurement of the particle’s position at the time t finds it in the volume element dxdydz about he position point x,y,z.

The postulates of quantum mechanics give a technique for calculating the wave function ψ to within an arbitrary multiplicative constant.  The equation to solve for ψ is called the Schrödinger equation.

Dirac Notation

Before we discuss the postulates of quantum mechanics, it is necessary to introduce Dirac notation, commonly refereed to as “Ket” vectors and “bra” vectors.  Any element, or vector, of an abstract space is called a ket vector, or just simply, a ket. It is represented by the symbol | > and inside which is placed a distinctive sign which enables you to distinguish the corresponding ket form all others, for example: |ψ>.

Any element od an abstract space, ξ, is called a bra vector, or just bra.  Its is symbolized by < |.  For example, the bra <χ| designates the linear function χ and is used as follows:


to denote the number obtained by causing the linear function <χ|∈ ξ, to act on the ket |ψ> ∈ ξ:

<χ(|ψ>) = <χ|ψ>

The original this terminology is the word “bracket”, used to denote the symbol < | >.  Hence the name “bra” for the left-hand side, and “ket” for the right-hand side.

Postulates of Quantum Mechanics

In classical mechanics, the motion of any physical system is determined if the position and velocity of each of its points are known as a function of time.  Classically speaking, the total energy of a system is:

E = (P2/2m) + V(r,t)

where P is momentum  and m is mass.  V(r,t), where r is equal to position and t is time, represents the scalar potential, the forces acting on this particle can be derived from this potential.  The corresponding angular momentum with respect to the origin is:

Ι = r x p

Since the total energy of the system is given by the classical Hamiltonian:

Η (r, p, t) = (P2/2m) + V(r,t)

Therefore, the motion of the system can be described by the Hamiltonian-Jacobi equations:

(dr/dt) = (p/m)

(dp/dt) = -∇V

The classical description of a physical system can therefore be summarized.  The postulates of quantum mechanics describe the physical system, these postulates provide an answer for the following questions, corresponding to the classical description

  1. How is the state of a quantum system at a given time described mathematically?
  2. Given this state, how can we predict the results of the measurement of various physical quantities?
  3. How can the state of the system at an arbitrary time t be found when the state at time t0 is known?

Postulate One: Description of the system

At a fixed time t0 the state of a physical system is defined by specifying a ket |ψ(t0)> belonging to the state space ξ.

Since  ξ is a vector space, the first postulate implies a superposition principle: A linear combination of state vectors is a state vector.  This is directly applied to quantum cellular automat, where a quit is a superposition of the bit value of the state (i.e. 0 or 1).


Postulate Two: Description of physical quantities

Every measurable physical quantity A is described by an operator A acting on ξ.  Unlike classical mechanics, quantum mechanics describes in a fundamental different manner that state of the system and the associated physical quantities: A state is represented by a vector, a physical quantity by an operator.  The state of the system with respect to propagation of quantum cellular automata is the cell of interest in a Markov chain, and the operator is the rule based system acting on the state.


Postulate Three: The Measurement of physical quantities

The connection between the operator H and the total energy of the particle when the wave function of the particle whose potential energy V(r) is not time dependent must satisfy the Schrödinger equation:

i ℏ(d/dt)|ψ(t)> = H(t)|ψ(t)>

The only energies that are possible are the eigenvalues of the operator H, and this relation can be extended to all physical quantities.  The only possible result of the measurement of a physical quantity A is one of the eigenvalues of the corresponding observable A.


Postulate Four: Principle of spectral decomposition

Consider a system whose state is characterized, at a given time, by the ket |ψ>, assumed to be normalized to 1:

<ψ|ψ> = 1

The idea is to predict the result of the measurement of a physical quantity A associated with observable A.  The prediction is of a probabilistic sort, for tow different situations.

  1. Case of a discrete non-degenerate spectrum

First assume the spectrum of A is entirely discrete.  If all eigenvalues, an of A are non-degenerate, there is associated with each of them a unique eigenvector |un >:

A|un > = an|un >

since A is an observable, the set of the |un >, which we shall take to be normalized, constitutes a basis in ξ, and the state vector |ψ> can be written:

|ψ> = ∑cn|un >

The probability P(an) of finding an when A is measured is:

P(an) = |cn|2 = |<un|ψ>|2

Therefore, for the case of discrete non-degenerate spectrum: When the physical quantity A is measured on a system in the normalized state |ψ>, the probability P(an) of obtaining the non-degenerate eigenvalue an of the corresponding observable A is:

P(an) = |<un|ψ>|2

  1. Case of a discreet spectrum

If, now, some of the eigenvalues aare degenerate, several ortho-normalized eigenvectors |uni> correspond to them.  When the physical quantity A is measured on a system in the normalized state |ψ>, the probability P(an) of obtaining the eigenvalue an of the corresponding observable A is:

P(an) = ∑gn|<uni|ψ>|2

where gn is the degree of degeneracy of aand {|uni>} (i=1,2, … ,gn) is an orthonormal set  of vectors which forms a basis in the eigensubspace  ξn associated with the eigenvalue an of A.


Quantum Cellular Automata

Now that we have reviewed the basic principles of quantum mechanics, the explanation of quantum cellular automata (QCA) will follow.  We will take the case of one-dimensional quantum cellular automata, which is the most staring forward extension of the classical model.  In 1982, Richard Feynman proposed proposed an approach to quantizing classical cellular automata.  Simply put, QCA is a quantized version of classical cellular automata whose cells have a non-derterminiostic time evolution.


An example of QCA is where each cell is composed of two electrons, hence, four quantum dots, where each electron is allowed to jump between quantum dots based on quantum mechanical tunneling.  However, each electron is not permitted to tunnel between cells.  It is the Coulomb force between the electrons which allows them to occupy different dots.  The following diagram represents the electrons inside the cells:


The blue dots represent spin-up (1/2) and the clear dots represent spin-down (-1/2).  The coupling between the electrons are controlled by the Coulomb force.  Basic boolean function can be derived based on the physical interactions between the cells.  Initially, the electrons are trapped in their respective positions.  Information flow through the cells are provided by a clocking mechanism, this mechanism is used to control the tunneling barrier height in the QCA cells.  When the clock is low the electrons can not tunnel (hold phase).  The cell then goes to the null polarization state when the clock signal is high.  Therefore, between these two conditions, the cells are either switching or releasing.  The following diagram represents these conditions with respect to time and energy:


where the vertical axis and horizontal axis represent the electric field barrier and the time, respectively.  This represent the different phases of the clock, and each individual zone is connected to one of the four phases.  Each cell is then connected to one of four available phases.  Encryption algorithms can be based on reversible cellular automata.  These algorithms are usually based on symmetric key block cipher systems.  A block cipher is a deterministic algorithm operating on a group of fixed length bits, called blocks.  In particular, a Serpent block cipher is described here.  A Serpent is a symmetric key block cipher that ranked second in the AES contest.  In this situation, symmetry represent the fact that the key is a shared secret between two or more parties.

Leave a Reply

Your email address will not be published. Required fields are marked *