Quantum cellular automata

From Wikipedia, the free encyclopedia

This article (or section) may need to be wikified to meet Wikipedia's quality standards.
Please help improve this article, especially its section layout, and relevant internal links. (help)
This article has been tagged since December 2006.

Quantum Cellular Automata (QCA) is 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.

The term “Quantum Computer” does not refer to a computer employing a specific technology but to any kind of system that can perform computation making direct use of any distinctively quantum mechanical phenomena , regardless of its materials and implementation method. A handful of quantum technologies exist today. Rapid Single Flux Quantum (RSFQ) logic, Resonant Tunneling Device (RTD) logic, Single Electron Transistor (SET) logic, and Spin Transistor Logic (STL) are among the most popular emerging quantum computing technologies . The type of quantum technology discussed here is Quantum Cellular Automata (QCA).

The concept of Cellular Automata (CA), along with its practical applications, has certainly increased in popularity over the last three decades. It is a relatively new concept that was first proposed to study crystal growth in the 1940’s. A cellular automaton is an abstract system consisting of a uniform (finite or infinite) grid of cells. Each one of these cells can only be in one of a finite number of states at a discrete time. The state of each cell in this grid is determined by the state of its adjacent cells, also called the cell’s “neighborhood”. The most popular example of a cellular automaton was presented by Conway in 1972. He named it “The Game of Life”. He proposed a grid in which individual cells can either be dead or alive, depending on the state of their direct neighbors. The game consists of three very simple rules. If a living cell has less than two living neighbors, it will die in the next generation as if by loneliness. If a living cell has more than three living neighbors, it will die as if by overpopulation. Finally, if a dead cell has exactly three neighbors, it will live in the next generation as if by reproduction. Figure 1 shows several segments of a CA grid in order to observe the behavior that the center cell exhibits under different conditions. The first column represents the current state of the automaton and the second column represents its future state. The rows represent several grid segments.

Figure 1 - Example of a cellular automaton.

The importance of CA lies on the ability to study and predict behaviors of any kind of phenomena by modeling element interactions through simple rules. One of the most recent and significant publications on Cellular Automata is the book “A New Kind of Science”. Stephen Wolfram, the author of the book, studies the possibility of replacing physics as we know it with what he calls “a truly fundamental model”.

“Just over twenty years ago I made what at first seemed like a small discovery: a computer experiment of mine showed something I did not expect. But the more I investigated, the more I realized that what I had seen was the beginning of a crack in the very foundations of existing science, and a first clue towards a whole new kind of science.” 4 – Stephen Wolfram

He argues CA is not just the means to a model, but probably the basis for behavior in all of our universe’s phenomena. Although analyzing the validity and originality of these ideas is outside the scope of this paper, it is sufficient to consider that for some, CA is not merely another way of modeling phenomena, but a potential replacement solution to avoid the limitations of current physics models and mathematics. For now, it will be important to remember that all CA are discrete in time, location and state.

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

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 and consuming extremely small amounts power5. Today, standard solid state QCA cell design considers the distance between quantum dots to be about 20nm, and a distance between cells of about 60nm . 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. 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 QCA represents its polarization, denoted as P. Although arbitrary in meaning, using cell polarization P = -1 to represent logic “0” and P = +1 to represent logic “1” has become standard practice

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

Grid arrangements of quantum-dot cells behave in a 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 do not represent physical implementation, but are shown as means to identify individual cells.

Figure 4 - A wire of quantum-dot cells.

If the polarization of any of the cells in the arrangement shown in figure 4 were to be controllable (driver cell), the rest of the cells would immediately synchronize to its polarization due to Coulombic interactions between them; much like an instantaneous chain reaction. In this way, a wire of quantum-dot cells is realizable. Although the ability to realize conductive wires does not alone provide the means to perform computation, a complete set of universal logic gates can be constructed using the same principle.

Figure 5 - QCA Majority Gate

The fundamental logic gate in QCA is the majority gate. Figure 5 shows a majority gate with three inputs and one output. Assuming 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 as the conjunct electrical field effect of inputs A and B is greater than the one of input C. In other words, the majority gate drives the output cell’s state to be equal to that of the majority of the inputs. Now, if the polarization of input C were to be fixed to say, binary 0, the only way the output’s state becomes binary 1, is if input A and B are also 1. Otherwise, the output cell will exhibit a binary 0 state. This conditional behavior is exactly the same as that of an AND gate. Similarly, an OR gate can be constructed using a majority gate with fixed polarization equivalent to binary 1 at one of its inputs. In this way, if any or both of the remaining inputs exist in the binary 1 state, the output will be also in a binary 1 state. Although not certainly based on a majority gate structure, a NOT gate is just as easily realizable. The key principle behind its functionality lies on the fact that placing a cell at 45 degrees with respect of a pair of cells of same polarity, the polarization of the cell will become opposite to that of its driving pair. Figure 6 shows a standard implementation of a NOT logic gate.

Figure 6 - Standard Implementation of a NOT gate.

By now, the connection between quantum-dot cells and cellular automata must have become evident to the reader. 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. Like stated before, QCA requires very small amounts of power. This is due to the fact that cells do not require external power apart from the automaton’s clocks. QCA clocks are areas of conductive material under the automaton’s lattice, modulating the electron tunneling barriers in the QCA cells above it . 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 90 degrees out of phase from each other. If a horizontal wire consisted of say, 8 cells and each consecutive pair, starting form 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. Further discussion on clocks is to be presented later.

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

A fundamental implementation problem might have become obvious to the reader at this point: wire-crossing. Without the ability to fabricate an automaton in which wire-crossing is possible, QCA would be of very little interest, to say the least. However, basic QCA wire-crossing is conceptually simple to do. So far, a square quantum-dot pattern for cells has proven appropriate to represent a cell’s state. If a “plus-sign” pattern were to be used instead, it would prove as effective; the distances between a plus-sign pattern and a square pattern are exactly the same, allowing for the same Coulombic interactions between electrons in a cell. Interestingly, when a wire of square cells crosses a wire of plus-sign cells, they do not interact, thus the signals on each wire are preserved. Figure 8 shows a plus-sign cell wire crossing a square cell wire. 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 cells 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 speed9.

Figure 8 - Basic Wire-Crossing Technique.

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). It is important, however to take into account that “quasi-adiabatic switching” –a process described earlier and shown in Fig. 7, 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 abruptly9. 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.

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-dependant series of values on a single wire9. 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. Now, 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. It is important to note that this new latching clock region would be completely independent form 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.

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 big 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. More generally, “if there were N signals being distributed, this device would require (4N + 1) clocking regions. In addition, as the number of horizontal wires increases, the length of the vertical wires will increase, which could lead to an increase in the clock period to maintain the quasi-adiabatic switching required for this device.”9 As stated before, the method solves various fabrication problems, but it adds a great deal of time restrictions which may result in reduced computing speed.

Figure 10 – Multifunction QCA Device.

Having discussed the basic theoretical principles of QCA devices, attention is directed towards current fabrication methods. As discussed earlier, the core element behind QCA computation is a bi-stable cell capable of interacting with its local neighbors. The cell is not required to remain quantum-mechanically coherent at all times; therefore, many non-quantum-mechanical implementations of QCA have emerged. Generally speaking, there are four different classes of QCA implementations: Metal-Island, Semiconductor, Molecular, and Magnetic.

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 . Again, this method only served as means to prove that the concept is attainable in practice.

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. The problem with this method is that 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 by no means 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.

Although not yet possible, molecular implementation represents the most advantageous of all. The concept consists of building QCA devices out of single molecules. The main advantages of such implementations 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. All of these attractive features are limited by some challenges yet to be overcome. Which molecules are most suitable for this application remains unknown. Designing proper interfacing mechanisms and clocking technology for complex circuit design are the main challenges in molecular QCA implementations .

Finally, a new, more versatile (than its semiconductor counterpart) class of implementation has emerged. 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. “One of the immediate advantages of considering such a technology is that MQCA cells would operate at room temperature, even for large device features on the order of a few hundred nanometers.”

Complementary metal-oxide semiconductor (CMOS) technology has been the industry standard for implementing Very Large Scale Integrated (VLSI) devices for the last two decades , and for very good reasons –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 CMOS technology, it also brings its own. Optimistic assumptions suggest that intrinsic switching time of a QCA cell is in the order of terahertz, however, as mentioned earlier, switching speed is not limited by a cell’s intrinsic switching speed but by the proper quasi-adiabatic clock switching frequency setting. “Comparative analysis of circuit performance of QCA and CMOS against a representative computer task, suggests that realistic circuits of solid state QCA will have the maximum operating frequency of several megahertz. Small circuits of hypothetical molecular QCA might have the maximum operating frequency of several GHz, however, as the circuit size increases, capacitive loading effects will reduce the speed.”6 Moreover, solid-state QCA devices cannot operate at room temperature. The only alternative to this temperature limitation is the recently proposed “Molecular QCA” which theoretically has an inter-dot distance of 2nm and an inter-cell distance of 6nm. Molecular QCA is also considered to be the only feasible implementation method for mass production of QCA devices. QCA technology resolves, in principle, the problems of current CMOS technology, and it is only limited by the availability of its practical fabrication methods.

[edit] References

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, “Quatum 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, AL, 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, AL, 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;