Abstract
Quantumdot cellular automata are an interesting nanoscale computing paradigm. The introduction of the ternary quantumdot cell enabled ternary computing, and with the recent development of a ternary functionally complete set of elementary logic primitives and the ternary memorizing cell design of complex processing structures is becoming feasible. The specific nature of the ternary quantumdot cell makes wire crossings one of the most problematic areas of ternary quantumdot cellular automata circuit design. We hereby present a twolayer wire crossing that uses a specific clocking scheme, which ensures the crossed wires have the same effective delay.
Keywords:
Quantumdot cellular automata; Ternary processing; Wire crossing; Multilayer design; 85.35.Be; MCS: 68Q80; 03B50Background
Since the first introduction of quantumdot cellular automata (QCA), an interesting nanoscale computing paradigm by Lent et al. in 1993 [1], many researchers have embraced its simple concept and potential as a future processing platform [26]. In recent years, a group of researchers have presented a generalization of the basic QCA cell, namely the ternary QCA (tQCA) cell [710], which enables ternary computation. Their principal motivator was the premise that future processing platforms should not disregard the advantages of multivalued processing [1115]. The group presented the basic ternary building blocks, the inverter, majority gate, wire, corner wire and fanout, and more recently also, a functionally complete set of ternary logic functions, based on Post Logic, and a memorizing tQCA circuit [16,17]. Due to the specifics of the tQCA cell, wire crossings seem to be the principal drawback before a more widespread acceptance of tQCA circuitry. Wire crossings are one of the most used steps in systematic logic design. In the classic, binary QCAs, wires can be crossed either in a coplanar fashion by using rotated QCA cells for one of the wires or in a multilayer fashion where two intermediate layers are used to prevent any possible crosstalk between the two crossing lines [18]. Although the multilayer approach proves to be more robust [19], the majority of designs employ the coplanar one; that is in fact one of the most praised features of classic QCA. Since coplanar crossings tend to be prone to robustness issues, much research has been devoted to its increase, even to the extents of altering the design of QCA logic gates [2022], or as in the case of molecular implementations, through the elimination of crossings by logic gate duplication [23,24]. Another approach exploits the pipelined nature of QCAs and uses paralleltoserial converters and a specialized clocking scheme to design a coplanar crossbar network [25]. Coplanar crossings with rotated tQCA cells are not possible, but multilayer crossings are, as it has been reported recently [26]. Here, we go a step further by presenting a wire crossing that is synchronized, i.e., the two wires employ such clocking schemes that the outputs of the two wires have the same effective delay. In addition, the clocking schemes allow for a twolayer design, in other words, removing the requirement for additional layers, whose sole purpose is to prevent possible crosstalk. The article is organized as follows. We first present the overview of a ternary QCA cell, its architecture and intercell interaction. We follow by presenting a twolayer design, where we first show the interlayer interaction followed by presenting the design and clocking scheme of a twolayer synchronized wire crossing.
The ternary QCA cell
A QCA is, in general, a planar array of quantumdot cells (QCA cells) [1]. In the case of a ternary QCA, it is an array of tQCA cells. A tQCA cell [7,8] is a circular arrangement of eight quantumdots and two mobile electrons. The electrons tend to localize only in the quantum dots or tunnel between adjacent quantum dots, and they cannot tunnel outside of the cell. The Coulomb interaction causes the electrons to localize in the quantum dots that ensure their maximal separation (thus achieving the minimal energetic state). The four arrangements, which in the case of an isolated cell, correspond to the energetic minimal state (ground state) are marked as A, B, C, and D (see Figure 1).
Figure 1. Ternary quantumdot cell (tQCA cell) ground states. In the case of an isolated tQCA cell, a circular arrangement of quantum dots with two mobile electrons, there are four electron arrangements that ensure their maximal separation thus achieving a ground state. They are marked A, B, C and D and can be mapped to balanced ternary values 1, 0, and 1.
It turns out that placing a wellpolarized cell (i.e., a cell with electrons fixed in one of the four arrangements) nearby causes one of the four states to become the favored one even in the observed cell. When the wellpolarized cell is on the same plane, but to the left, right, above, or below the observed cell, then the state A or B in the wellpolarized cell induces the same state even in the observed cell. However, state C induces state D, and the same goes for state D, which induces state C in the observed cell. If one interprets state A, B, C, and D as balanced ternary logic values, so that state A represents logic value −1, state B logic value 1, and states C and D both logic value 0, then intercell interaction causes the logic value of the wellpolarized cell to be transferred to the observed cell.
If the wellpolarized cell is placed diagonally to the observed cell, then state A in the wellpolarized cell induces state B in the observed cell, state B induces state A, state C induces state C, and state D induces state D. When the states are interpreted as logic values, this translates to logic negation. With specific planar arrangements of cells, it is thus possible to mimic the behavior of interconnecting wires as well as logic gates [27]. By interconnecting such building blocks, more complex devices capable of processing can be constructed.
The reliability of the logic value transfer throughout a QCA device (i.e., a spatial arrangement of QCA cells) depends foremost on the reliability of the switching process, i.e., the transition of a cell’s state that corresponds to one logic value to a state that corresponds to another. The reliability is ensured via the adiabatic switching concept [9,28], where a cyclic signal, namely adiabatic clock, is used to control the switching dynamics. The cyclic signal is comprised of four phases. The switch phase serves the cell’s gradual update of the state with respect to the neighbors. The hold phase is intended for the stabilization of the cell’s state when it is to be passed on to the neighbors that are in the switch phase. The release phase and the relax phase support the cell’s gradual preparation for a new switch.
Recent research [10] showed that the correct behavior of tQCA logic gates requires a synchronized data transfer, achievable through a pipelined architecture based on the adiabatic clock. The fourphased nature of the clock signal allows any tQCA to be decomposed to smaller stages or subsystems, controlled by phase shifted signals, each defining its own clock zone (Figure 2). With the correct assignment of cells to clock zones (clocking scheme), the direction of data flow can be controlled. The latency of a QCA circuit is determined by the number of clock zones along its critical path. A sequence of four clock zones causes the delay of one clock cycle. Consequently, minimizing the number of clock zones leads to better designs [29].
Figure 2. Clocking scheme. The clock cycle governing the pipeline transmission through a QCA. It is based on four phases, switch [0, ), hold [), release [), and relax [, 1). Indices 0–3 indicate the clock zones, governed by a phase shifted original clock signal C_{0}, so that when a cell in clock zone 0 is in the hold phase, a cell in clock zone 1 is in the switch phase, a cell in clock zone 2 is in the relax phase, and a cell in clock zone 3 is in the release phase.
Methods
Simulations were conducted following the same methods as outlined in the work of Pečar et al. [10]. Interlayer interaction was analyzed as a twocell system of one wellpolarized cell and one observed cell placed directly one over the other but on separated layers. Through a series of sequential steps, a transition from the initial state to neutral and then from the neutral state to the final state is applied to the wellpolarized cell, and the response of the observed cell is computed. The response is computed by numerical diagonalization of a tightbinding Hubbardtype Hamiltonian, where quantum dots are represented as sites, and the degrees of freedom internal to the quantum dots are ignored. The same set of parameters was used as in the work of Pečar et al. [10], with the interlayer distance equal to that between the neighboring cells.
The behavior of the wire crossing was assessed using the intercellular Hartree approximation, as in the work of Pečar et al. [10]. A single simulation consists of the circuit’s total delay time discrete time steps. We use 200 time steps per clock cycle. At each time step, the ground state of the QCA is found by iteratively solving for the ground state of each cell. The ground state of a cell (observed cell) is calculated under the influence of the states of all other cells in the QCA which are momentarily treated as wellpolarized. In turn, each of the QCA cells is chosen as the observed cell, so their states change. This process is iterated until the QCA relaxes, and no further change in any of the cells is observed (i.e., until the QCA reaches its ground state at the corresponding time step). At every simulation, an initial state is applied to cells marked as input cells (X1,X2) and the simulation run for the corresponding total delay time of the QCA circuit. This is when the cells marked as output cells (Y1,Y2) are in the hold phase, and their states are treated as valid. We simulated all possible combinations of initial states.
Results and discussion
Multilayer interaction
QCA processing is based on intercell interaction, where the state of a cell influences the states of its neighbors and vice versa. The same applies for interlayer interaction. The cell that is closest to the observed cell has the largest influence on the observed cell’s state. In a multilayer case, two cells are closest when placed directly one over the other, i.e., on the same location but on separate layers.
Figure 3 presents six state transitions of the wellpolarized cell and the corresponding response functions for the observed cell. The results were obtained by numerical diagonalization of a tightbinding Hubbardtype Hamiltonian, where quantum dots are represented as sites, and the degrees of freedom internal to the quantum dots are ignored. The same set of parameters was used as in the work of Pečar et al. [10], with the interlayer distance equal to that between the neighboring cells. Reverse transitions are not presented as they are symmetrical to those presented. Observing the graphs, it can be noticed that the observed cell saturates very quickly, and the response function is highly nonlinear for the initial and final states and almost flat for the other two. However, the observed cell does not assume the same state as it would if the two cells were on the same layer. State A in the wellpolarized cell induces state B in the observed cell, B induces A, C induces D, and D induces C (for the last two cases interestingly as it would if the two cells were on the same layer). When the states are interpreted as logic values this translates to logic negation since C and D both represent logic value 0, A logic value −1, and B logic value 1.
Figure 3. Interlayer interaction. State transitions of the wellpolarized cell and the corresponding response functions of the observed cell. Six state transitions are presented, namely AB, AC, AD, BC, BD, and CD. For all cases throughout a series of sequential steps, a transition from the initial state to neutral and then from the neutral state to the final state is applied to the wellpolarized cell, and the response of the observed cell is computed. For each transition, there are four graphs depicting the density correlation function _{PS}for states A, B, C, and D. The lighter curve (blue) is for the wellpolarized cell, and the darker curve (orange) is the response of the observed cell. Notice that states A, B, C, and D of the wellpolarized cell induce states B, A, D, and C in the observed cell, respectively.
A negation of the transferred logic value occurs by moving from one layer to the other. When designing a wire crossing, this has no real effect as eventually the transferred logic value will be negated once more upon moving back to the original layer. In the case when processing is to be performed on different layers, however, this fact has to be kept in mind. For states C and D, it presents no real problem, as they both represent the same logic value, and alternating between the two states is achieved through simple addition of another adjacent cell. For states A and B, which represent two opposite logic values (−1 and 1, respectively), this, however, means adding an inverter (which in its simplest form could be just one cell displaced diagonally) or designing the processing element based on an inverted input value.
Synchronized twolayer wire crossing
Figure 4 presents a twolayer synchronized wire crossing that achieves the most compact wire crossing possible. Typically, it will be employed when two wires running parallel to one another have to be swapped. There are only two layers in this design, with the interlayer distance equal to that between neighboring cells. Our experiments showed that this interlayer distance is also the most robust one. The behavior of the wire crossing was assessed using the intercellular Hartree approximation, as in the work of Pečar et al. [10].
Figure 4. Twolayer synchronized wire crossing. The left image (L1:X1Y1) shows the clocking scheme of wire X1Y1. It is based on a diagonal pipelined transmission with blocks of two cells, producing a total delay of one clock cycle. The middle and right images show the clocking scheme of wire X2Y2. The middle image (L1:X2Y2) the part on layer L1; note that the clocking scheme is such that the active cells cause no interference with the cells carrying information of wire X1Y1. The right image (L2:X2Y2) shows the part on layer L2, where the same concept of diagonal pipelined transmission is used as for line X1Y1.
The total delay of the crossing is one clock cycle. The four phases are used so as to keep the distance between active cells (neighboring cells that are currently in the hold or switch phase) as large as possible, as well as to achieve robust intercell transfers. Active cells on the two layers are never directly one over the other, although this would not present a real issue as long as enough cells are active in the same instant. Reducing the number of active cells makes them more susceptible to interlayer crosstalk, all due to the highly nonlinear intercell interaction.
The line, marked X1Y1, travels in a diagonal fashion upwards on layer L1. This is achieved in one clock cycle (four phases), with blocks of two cells, so that the same state that is input to the first cell, marked X1, appears on the last cell, marked Y1, after a delay of one clock cycle.
The line, marked X2Y2, travels first vertically from layer L1 to layer L2, then in a diagonal fashion downwards, and back vertically from layer L2 to layer L1, again all in one clock cycle. This ensures that the state that is input to the first cell, marked X2, appears on the last cell, marked Y2, after a delay of one clock cycle.
Figure 5 presents the twolayer synchronized wire crossing concept applied to a three wire crossing. The total delay is 1.75 clock cycles, but the outputs of all three wires are synchronized, meaning the total latency is the same for all three wires.
Figure 5. Twolayer synchronized three wire crossing. Application of the twolayer synchronized wire crossing concept to a three wire crossing. The total delay is 1.75 clock cycles.
Conclusions
Due to the specifics of the ternary quantumdot cell, the basic building block of ternary quantum dot cellular automata, coplanar wire crossings are not possible. In this article, we present a twolayer synchronized wire crossing; a wire crossing that uses such clocking schemes that the effective latency is equal for both wires (one clock cycle). In addition, the clocking schemes allow for a twolayer design. They override the requirement for additional layers, whose sole purpose is to prevent possible crosstalk.
Our current research is devoted to the study of synchronized twolayer wire crossings that consume fewer clock cycles as well as tilebased solutions, what we find to be one of the more promising approaches for QCA design in general.
Competing interests
The authors declare they have no competing interests.
Author’s contributions
ILB designed the twolayer synchronized wire crossing and the corresponding clocking scheme. He also prepared this manuscript. PP helped in the design of the clocking scheme, performed the simulations, and provided assistance through literature research for the preparation of the manuscript. Both authors read and approved the final manuscript.
Acknowledgements
This work was funded in part by the Slovenian Research Agency through the Pervasive Computing research programme (P20359).
References

Lent CS, Tougaw PD, Porod W, Bernstein GH: Quantum cellular automata.
Nanotechnology 1993, 4:49. Publisher Full Text

Lent CS, Tougaw PD: Lines of interacting quantumdot cells: a binary wire.
J Appl Phys 1993, 74(10):6227. Publisher Full Text

Niemier MT, Kontz MJ, Kogge PM: A design of and design tools for novel quantum dot based microprocessor. In DAC ’00: Proceedings of the 37th conference on Design automation. ACM Press, New York; 2000:227232. PubMed Abstract  Publisher Full Text

Niemier MT, Rodrigues AF, Kogge PM: A potentially implementable FPGA for quantum dot cellular automata.
1st Workshop on NonSilicon Computation (NSC1) 2002, 3845.

Huang J, Momenzadeh M, Lombardi F: Design of sequential circuits by quantumdot cellular automata.
Microelectron J 2007, 38(45):525. Publisher Full Text

Vankamamidi V, Ottavi M, Lombardi F: A serial memory by quantumdot cellular automata (QCA).

Lebar Bajec I, Mraz M: Towards multistate based computing using quantumdot cellular automata. In Unconventional Computing 2005: From Cellular Automata to Wetware. Edited by Teucher C, Adamatzky A. Luniver Press, Beckington; 2005:105116.

Lebar Bajec I, Zimic N, Mraz M: The ternary quantumdot cell and ternary logic.
Nanotechnology 2006, 17(8):1937. Publisher Full Text

Pečar P, Mraz M, Zimic N, Janež M, Lebar Bajec I: Solving the ternary QCA logic gate problem by means of adiabatic switching.
Jpn J Appl Phys 2008, 47(6):5000. Publisher Full Text

Pečar P, Ramšak A, Zimic N, Mraz M, Lebar Bajec I: Adiabatic pipelining: a key to ternary computing with quantum dots.
Nanotechnology 2008, 19(49):495401. PubMed Abstract  Publisher Full Text

Frieder G: Ternary computers: Part 1: motivation for ternary computers. In MICRO 5: Conference record of the 5th annual workshop on Microprogramming, September 1972; Urbana, Illinois. ACM, New York; 1972:8386.

Rine DC (Ed): Computer science and multiplevalued logic: theory and applications. Elsevier/NorthHolland, Amsterdam; 1984.

Dubrova E, Jamal Y, Mathew J: Nonsilicon nonBinary computing: why not? In 1st Workshop on NonSilicon Computation (NSC1), February 2002. , Boston, Massachusetts; 2002:2329.

Fitting M, Orlowska E (Eds): Beyond two: theory and applications of multiplevalued logic. PhysicaVerlag, Heidelberg; 2003.

Pečar P, Janež M, Zimic N, Mraz M, Lebar Bajec I: The ternary quantumdot cellular automata memorizing cell. In Proc. of ISVLSI 2009. IEEE Computer Society, Los Alamitos, CA; 2009:223228.

Pečar P, Lebar Bajec I: The key elements of logic design in ternary quantumdot cellular automata.

Walus K, Schulhof G, Jullien GA: High level exploration of quantumdot cellular automata (QCA). In Proc. of Signals, Systems & Computers 2004. IEEE Computer Society, Los Alamitos, CA; 2004:3033. PubMed Abstract  Publisher Full Text

Schulhof G, Walus K, Jullien GA: Simulation of random cell displacements in QCA.

Bhanja S, Ottavi M, Lombardi F, Pontarelli S: QCA Circuits for robust coplanar crossing.
J Electron Test 2007, 23:193. Publisher Full Text

Sen B, Dalui M, Sikdar BK: Introducing universal QCA logic gate for synthesizing symmetric functions with minimum wirecrossings. In Proc. of ICWET 2010. ACM, New York, NY; 2010:828833.

Sen B, Sengupta A, Dalui M, Sikdar BK: Design of testable universal logic gate targeting minimum wirecrossings in QCA logic circuit. In Proc. of DSD 2010. IEEE Computer Society, Los Alamitos, CA; 2010:613620.

Chaudhary A, Chen DZ, Hu XS, Whitton K, Niemier M, Ravichandran R: Eliminating wire crossings for molecular quantumdot cellular automata implementation. In Proc. of ICCAD 2005. IEEE Computer Society, Washington, DC, USA; 2005:565572.

Chaudhary A, Chen DZ, Hu XS, Niemier MT, Ravichandran R, Whitton K: Fabricatable interconnect and molecular QCA circuits.
IEEE Trans Comput Aided Des Integr Circuits Syst 2007, 26(11):1978.

Graunke CR, Wheeler DI, Tougaw D, Will JD: Implementation of a crossbar network using quantumdot cellular automata.
IEEE Trans Nanotechnol 2005, 4:435. Publisher Full Text

Pečar P: Introducing interconnection crossing in ternary quantumdot cellular automata. In Proc. of ICQNM 2011. IARIA; 2011:15.

Tougaw PD, Lent CS: Logical devices implemented using quantum cellular automata.
J Appl Phys 1994, 75(3):1818. Publisher Full Text

Tougaw PD, Lent CS: Dynamic behaviour of quantum cellular automata.
J Appl Phys 1996, 80(8):4722. Publisher Full Text

Niemier MT, Kogge PM: Problems in designing with QCAs: layout = timing.
Int J Circuit Theory Appl 2001, 29:49. Publisher Full Text