Quantum dot cellular automaton

Short description: Type of cellular automaton

Quantum dot cellular automata (QDCA, sometimes referred to simply as quantum cellular automata, or QCA) 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.

Background

Any device designed to represent data and perform computation, regardless of the physics principles it exploits and materials used to build it, must have two fundamental properties: distinguishability and conditional change of state, the latter implying the former. This means that such a device must have barriers that make it possible to distinguish between states, and that it must have the ability to control these barriers to perform conditional change of state. For example, in a digital electronic system, transistors play the role of such controllable energy barriers, making it extremely practical to perform computing with them.

Cellular automata

A cellular automaton (CA) is a discrete dynamical system consisting of a uniform (finite or infinite) grid of cells. Each cell can be in only one of a finite number of states at a discrete time. As time moves forward, the state of each cell in the grid is determined by a transformation rule that factors in its previous state and the states of the immediately adjacent cells (the cell's "neighborhood"). The most well-known example of a cellular automaton is John Horton Conway's "Game of Life", which he described in 1970.

Quantum-dot cells

Origin

Cellular automata are commonly implemented as software programs. However, in 1993, Lent et al. proposed a physical implementation of an automaton using quantum-dot cells. The automaton quickly gained popularity and it was first fabricated in 1997. Lent combined the discrete nature of both cellular automata and quantum mechanics, to create nano-scale devices capable of performing computation at very high switching speeds (order of Terahertz) and consuming extremely small amounts of electrical power.

Modern cells

Today, standard solid state QCA cell design considers the distance between quantum dots to be about 20 nm, and a distance between cells of about 60 nm. Just like any CA, Quantum (-dot) Cellular Automata are based on the simple interaction rules between cells placed on a grid. A QCA cell is constructed from four quantum dots arranged in a square pattern. These quantum dots are sites electrons can occupy by tunneling to them.

Cell design

Figure 2 - A simplified diagram of a four-dot QCA cell.

Figure 3 - The two possible states of a four-dot QCA cell.

Figure 2 shows a simplified diagram of a quantum-dot cell. If the cell is charged with two electrons, each free to tunnel to any site in the cell, these electrons will try to occupy the furthest possible site with respect to each other due to mutual electrostatic repulsion. Therefore, two distinguishable cell states exist. Figure 3 shows the two possible minimum energy states of a quantum-dot cell. The state of a cell is called its polarization, denoted as P. Although arbitrarily chosen, using cell polarization P = -1 to represent logic “0” and P = +1 to represent logic “1” has become standard practice.

QCA wire

Figure 4 - A wire of quantum-dot cells. Note that the relative distances between cells and dots in a cell are not to scale (cells are much farther apart than dots within a cell).

Grid arrangements of quantum-dot cells behave in ways that allow for computation. The simplest practical cell arrangement is given by placing quantum-dot cells in series, to the side of each other. Figure 4 shows such an arrangement of four quantum-dot cells. The bounding boxes in the figure do not represent physical implementation, but are shown as means to identify individual cells.

If the polarization of any of the cells in the arrangement shown in figure 4 were to be changed (by a "driver cell"), the rest of the cells would immediately synchronize to the new polarization due to Coulombic interactions between them. In this way, a "wire" of quantum-dot cells can be made that transmits polarization state. Configurations of such wires can form a complete set of logic gates for computation.

There are two types of wires possible in QCA: A simple binary wire as shown in Figure 4 and an inverter chain, which is constituted by placing 45-degree inverted QCA cells side by side.

Logic gates

Majority gate

Majority gate and inverter (NOT) gate are considered as the two most fundamental building blocks of QCA. Figure 5 shows a majority gate with three inputs and one output. In this structure, the electrical field effect of each input on the output is identical and additive, with the result that whichever input state ("binary 0" or "binary 1") is in the majority becomes the state of the output cell — hence the gate's name. For example, if inputs A and B exist in a “binary 0” state and input C exists in a “binary 1” state, the output will exist in a “binary 0” state since the combined electrical field effect of inputs A and B together is greater than that of input C alone.

Figure 5 - QCA Majority Gate

Other gates

Other types of gates, namely AND gates and OR gates, can be constructed using a majority gate with fixed polarization on one of its inputs. A NOT gate, on the other hand, is fundamentally different from the majority gate, as shown in Figure 6. The key to this design is that the input is split and both resulting inputs impinge obliquely on the output. In contrast with an orthogonal placement, the electric field effect of this input structure forces a reversal of polarization in the output.

Figure 6 - Standard Implementation of a NOT gate. Note that the labeling of the input and output values follows a convention exactly opposite to that of the rest of this article.

State transition

Figure 7 - The QCA clock, its stages and its effects on a cell's energy barriers.

There is a connection between quantum-dot cells and cellular automata. Cells can only be in one of 2 states and the conditional change of state in a cell is dictated by the state of its adjacent neighbors. However, a method to control data flow is necessary to define the direction in which state transition occurs in QCA cells. The clocks of a QCA system serve two purposes: powering the automaton, and controlling data flow direction. QCA clocks are areas of conductive material under the automaton's lattice, modulating the electron tunneling barriers in the QCA cells above it.

Four stages

A QCA clock induces four stages in the tunneling barriers of the cells above it. In the first stage, the tunneling barriers start to rise. The second stage is reached when the tunneling barriers are high enough to prevent electrons from tunneling. The third stage occurs when the high barrier starts to lower. And finally, in the fourth stage, the tunneling barriers allow electrons to freely tunnel again. In simple words, when the clock signal is high, electrons are free to tunnel. When the clock signal is low, the cell becomes latched.

Figure 7 shows a clock signal with its four stages and the effects on a cell at each clock stage. A typical QCA design requires four clocks, each of which is cyclically 90 degrees out of phase with the prior clock. If a horizontal wire consisted of say, 8 cells and each consecutive pair, starting from the left were to be connected to each consecutive clock, data would naturally flow from left to right. The first pair of cells will stay latched until the second pair of cells gets latched and so forth. In this way, data flow direction is controllable through clock zones

Wire-crossing

Figure 8 - Basic Wire-Crossing Technique. Note that this is schematic and distances are not to scale; cells are much farther apart than dots within cells.

Wire-crossing in QCA cells can be done by using two different quantum dot orientations (one at 45 degrees to the other) and allowing a wire composed of one type to pass perpendicularly "through" a wire of the other type, as shown schematically in figure 8. The distances between dots in both types of cells are exactly the same, producing the same Coulombic interactions between the electrons in each cell. Wires composed of these two cell types, however, are different: one type propagates polarization without change; the other reverses polarization from one adjacent cell to the next. The interaction between the different wire types at the point of crossing produces no net polarization change in either wire, thereby allowing the signals on both wires to be preserved.

Fabrication problems

Although this technique is rather simple, it represents an enormous fabrication problem. A new kind of cell pattern potentially introduces as much as twice the amount of fabrication cost and infrastructure; the number of possible quantum dot locations on an interstitial grid is doubled and an overall increase in geometric design complexity is inevitable. Yet another problem this technique presents is that the additional space between cells of the same orientation decreases the energy barriers between a cell's ground state and a cell's first excited state. This degrades the performance of the device in terms of maximum operating temperature, resistance to entropy, and switching speed.

Crossbar network

A different wire-crossing technique, which makes fabrication of QCA devices more practical, was presented by Christopher Graunke, David Wheeler, Douglas Tougaw, and Jeffrey D. Will, in their paper “Implementation of a crossbar network using quantum-dot cellular automata”. The paper not only presents a new method of implementing wire-crossings, but it also gives a new perspective on QCA clocking.

Their wire-crossing technique introduces the concept of implementing QCA devices capable of performing computation as a function of synchronization. This implies the ability to modify the device's function through the clocking system without making any physical changes to the device. Thus, the fabrication problem stated earlier is fully addressed by: a) using only one type of quantum-dot pattern and, b) by the ability to make a universal QCA building block of adequate complexity, which function is determined only by its timing mechanism (i.e., its clocks).

Quasi-adiabatic switching, however, requires that the tunneling barriers of a cell be switched relatively slowly compared to the intrinsic switching speed of a QCA. This prevents ringing and metastable states observed when cells are switched abruptly. Therefore, the switching speed of a QCA is limited not by the time it takes for a cell to change polarization, but by the appropriate quasi-adiabatic switching time of the clocks being used.

Parallel to serial

When designing a device capable of computing, it is often necessary to convert parallel data lines into a serial data stream. This conversion allows different pieces of data to be reduced to a time-dependent series of values on a single wire. Figure 9 shows such a parallel-to-serial conversion QCA device. The numbers on the shaded areas represent different clocking zones at consecutive 90-degree phases. Notice how all the inputs are on the same clocking zone. If parallel data were to be driven at the inputs A, B, C and D, and then driven no more for at least the remaining 15 serial transmission phases, the output X would present the values of D, C, B and A –in that order, at phases three, seven, eleven and fifteen. If a new clocking region were to be added at the output, it could be clocked to latch a value corresponding to any of the inputs by correctly selecting an appropriate state-locking period.

The new latching clock region would be completely independent from the other four clocking zones illustrated in figure 9. For instance, if the value of interest to the new latching region were to be the value that D presents every 16th phase, the clocking mechanism of the new region would have to be configured to latch a value in the 4th phase and every 16th phase from then on, thus, ignoring all inputs but D.

Figure 9 - Parallel to serial conversion.

Additional serial lines

Adding a second serial line to the device, and adding another latching region would allow for the latching of two input values at the two different outputs. To perform computation, a gate that takes as inputs both serial lines at their respective outputs is added. The gate is placed over a new latching region configured to process data only when both latching regions at the end of the serial lines hold the values of interest at the same instant. Figure 10 shows such an arrangement. If correctly configured, latching regions 5 and 6 will each hold input values of interest to latching region 7. At this instant, latching region 7 will let the values latched on regions 5 and 6 through the AND gate, thus the output could be configured to be the AND result of any two inputs (i.e. R and Q) by merely configuring the latching regions 5, 6 and 7.

This represents the flexibility to implement 16 functions, leaving the physical design untouched. Additional serial lines and parallel inputs would obviously increase the number of realizable functions. However, a significant drawback of such devices is that, as the number of realizable functions increases, an increasing number of clocking regions is required. As a consequence, a device exploiting this method of function implementation may perform significantly slower than its traditional counterpart.

Figure 10 – Multifunction QCA Device.

Fabrication

Generally speaking, there are four different classes of QCA implementations: metal-island, semiconductor, molecular, and magnetic.

Metal-island

The metal-island implementation was the first fabrication technology created to demonstrate the concept of QCA. It was not originally intended to compete with current technology in the sense of speed and practicality, as its structural properties are not suitable for scalable designs. The method consists of building quantum dots using aluminum islands. Earlier experiments were implemented with metal islands as big as 1 micrometer in dimension. Because of the relatively large-sized islands, metal-island devices had to be kept at extremely low temperatures for quantum effects (electron switching) to be observable.

Semiconductor

Semiconductor (or solid state) QCA implementations could potentially be used to implement QCA devices with the same highly advanced semiconductor fabrication processes used to implement CMOS devices. Cell polarization is encoded as charge position, and quantum-dot interactions rely on electrostatic coupling. However, current semiconductor processes have not yet reached a point where mass production of devices with such small features (≈20 nanometers) is possible. Serial lithographic methods, however, make QCA solid state implementation achievable, but not necessarily practical. Serial lithography is slow, expensive and unsuitable for mass-production of solid-state QCA devices. Today, most QCA prototyping experiments are done using this implementation technology.

Molecular

A proposed but not yet implemented method consists of building QCA devices out of single molecules. The expected advantages of such a method include: highly symmetric QCA cell structure, very high switching speeds, extremely high device density, operation at room temperature, and even the possibility of mass-producing devices by means of self-assembly. A number of technical challenges, including choice of molecules, the design of proper interfacing mechanisms, and clocking technology remain to be solved before this method can be implemented.

Magnetic

Magnetic QCA, commonly referred to as MQCA (or QCA: M), is based on the interaction between magnetic nanoparticles. The magnetization vector of these nanoparticles is analogous to the polarization vector in all other implementations. In MQCA, the term “Quantum” refers to the quantum-mechanical nature of magnetic exchange interactions and not to the electron-tunneling effects. Devices constructed this way could operate at room temperature.

Improvement over CMOS

Complementary metal-oxide semiconductor (CMOS) technology has been the industry standard for implementing Very Large Scale Integrated (VLSI) devices for the last four decades, mainly due to the consequences of miniaturization of such devices (i.e. increasing switching speeds, increasing complexity and decreasing power consumption). Quantum Cellular Automata (QCA) is only one of the many alternative technologies proposed as a replacement solution to the fundamental limits CMOS technology will impose in the years to come.

Although QCA solves most of the limitations of CMOS technology, it also brings its own. Research suggests that intrinsic switching time of a QCA cell is at best in the order of terahertz. However, the actual speed may be much lower, in the order of megahertz for solid state QCA and gigahertz for molecular QCA, due to the proper quasi-adiabatic clock switching frequency setting.

References

• Debashis De, Sitanshu Bhattacharaya and K. P. Ghatak, Quantum Dots and Quantum Cellular Automata: Recent Trends and Applications,Nova, 2013
• Srivastava, S.; Asthana, A.; Bhanja, S.; Sarkar, S., "QCAPro - An error-power estimation tool for QCA circuit design," in Circuits and Systems (ISCAS), 2011 IEEE International Symposium on, vol., no., pp. 2377-2380, 15–18 May 2011
• V.V. Zhirnov, R.K. Cavin, J.A. Hutchby, and G.I. Bourianoff, “Limits to binary logic switch scaling—A gedanken model,” Proc. IEEE, vol. 91, p. 1934, Nov. 2003.
• S. Bhanja, and S. Sarkar, “Probabilistic Modeling of QCA Circuits using Bayesian Networks”, IEEE Transactions on Nanotechnology, Vol. 5(6), p. 657-670, 2006.
• S. Srivastava, and S. Bhanja, “Hierarchical Probabilistic Macromodeling for QCA Circuits”, IEEE Transactions on Computers,Vol. 56(2), p. 174-190, Feb. 2007.
• Beth, T. Proceedings. “Quantum computing: an introduction” The 2000 IEEE International Symposium on Circuits and Systems, 2000. May 2000 p. 735-736 vol.1
• Victor V. Zhirnov, James A. Hutchby, George I. Bourianoff and Joe E. Brewer “Emerging Research Logic Devices” IEEE Circuits & Devices Magazine May 2005 p. 4
• Wolfram, Stephen “A New Kind of Science”, Wolfram Media May, 2002 p. ix (Preface)
• C.S. Lent, P. Tougaw, W. Porod, and G. Bernstein, “Quantum cellular automata” Nanotechnology, vol. 4, 1993 p. 49-57.
• Victor V. Zhirnov, James A. Hutchby, George I. Bourianoff and Joe E. Brewer “Emerging Research Logic Devices” IEEE Circuits & Devices Magazine May 2005 p. 7
• Konrad Walus and G. A. Jullien “Quantum-Dot Cellular Automata Adders” Department of Electrical & Computer Eng. University of Calgary Calgary, AB, Canada p. 4 - 6
• S. Henderson, E. Johnson, J. Janulis, and D. Tougaw, “Incorporating standard CMOS design process methodologies into the QCA logic design process” IEEE Trans. Nanotechnology, vol. 3, no. 1, Mar. 2004. p. 2 - 9
• Christopher Graunke, David Wheeler, Douglas Tougaw, Jeffreay D. Will. “Implementation of a crossbar network using quantum-dot cellular automata” IEEE Transactions on Nanotechnology, vol. 4, no. 4, Jul. 2005 p. 1 - 6
• G. T´oth and C. S. Lent, “Quasiadiabatic switching for metal-island quantum-dot cellular automata”, Journal of Applied Physics, vol. 85, no. 5, 1999 p. 2977 - 2984
• G. T´oth, C. S. Lent, “Quantum computing with quantum-dot cellular automata”, Physics Rev. A, vol. 63, 2000 p. 1 - 9
• C. S. Lent, B. Isaksen, M. Lieberman, “Molecular Quantum-Dot Cellular Automata”, J. Am. Chem. Soc., vol. 125, 2003 p. 1056 - 1063
• K. Walus, G. A. Jullien, V. S. Dimitrov, “Computer Arithmetic Structures for Quantum Cellular Automata” Department of Electrical & Computer Eng. University of Calgary, Calgary, AB, Canada p. 1 - 4
• Rui Zhang, Pallav Gupta, and Niraj K. Jha “Synthesis of Majority and Minority Networks and Its Applications to QCA, TPL and SET Based Nanotechnologies” Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design 2005 p. 229- 234
• The first published reports introducing the concept of Quantum Automaton:
• Baianu, I. 1971a. "Categories, Functors and Quantum Automata Theory". The 4th Intl. Congress LMPS, August-Sept.1971;
• Baianu, I.1971b. "Organismic Supercategories and Qualitative Dynamics of Systems." Bull. Math. Biophys., 33 (339-353): http://cogprints.ecs.soton.ac.uk/archive/00003674/01/ORganismic_supercategories_and_qualitative_dynamics_of_systems_final3.pdf.
• Niemier, M. 2004. Designing Digital Systems In Quantum Cellular Automata, Ph.D. thesis, University of Notre Dame.
• Recent Updates:
• Quantum Reversible Automata: http://cogprints.org/3697/
• Quantum Nano-Automata.: http://doc.cern.ch/archive/electronic/other/ext/ext-2004-125/Quantumnanoautomata.doc
• Categories of Quantum Automata.: [1]

External links

• [2] – QCA home page at Notre Dame