Integrated circuits of a proposed type based on quantum-dot cellular automata (QCA) would implement permutation matrices. These circuits would serve as prototype building blocks for demonstrating the feasibility of quantum-dot-based computing and for the further development of increasingly complex and increasingly capable quantum-dot-based computing circuits. Permutation matrices were chosen as part of the basis of this development because (1) they play a major role in fast transforms (e.g., the fast Fourier, cosine, and Hartley transforms) that arise in the processing of signals and images and that are amenable to parallel computing by application-specific integrated circuits and (2) in principle, they could be implemented directly in the patterns of circuits of the proposed type.

Figure 1. Quantum-Dot Cellular Automata can be assembled into binary wires, which can cross without adverse effects.
As the development of very-large-scale integrated (VLSI) circuitry approaches the lower limits of practical feature sizes, QCA may offer an alternative that will enable further miniaturization. Of equal if not greater significance is the expectation that QCA may enable a great simplification of VLSI circuit patterns while affording capabilities that, heretofore, have not existed:

At present, wherever two wires in a VLSI circuit cross each other, the wires must not be in the same plane; that is, there must be a layer of electrical insulation between them (unless, of course, they are meant to be connected at the intersection). Much of the complexity and hence cost of VLSI design is associated with minimization of data routing and assignment of layers to minimize crossing of wires. The proposed circuits would enable one to take advantage of a unique feature of QCA; namely, the possibility of coplanar crossing of signal paths. This feature is what makes it possible, in principle, to implement various permutation matrices directly in coplanar patterns of quantum-dot circuit elements. Such a direct and compact implementation would be extremely costly if not impossible in conventional complementary metal oxide/semiconductor (CMOS) VLSI integrated circuitry.

Figure 2. A Simple QCA Circuit would implement the downshift permutation matrix Q4
A quantum-dot cellular automaton contains four quantum dots positioned at the corners of a square (see Figure 1). The cell contains two extra mobile electrons that can tunnel (in the quantum-mechanical sense) between neighboring dots. Tunneling out of the cell is assumed to be completely suppressed by the potential barriers between neighboring cells. The Coulomb repulsion between the two electrons tends to make them occupy antipodal dots in the cell. For an isolated cell, there are two energetically equivalent arrangements (denoted polarization states) of the extra electrons. The cell polarization is used to encode binary information.

The polarization of a nonisolated cell depends on interactions with neighboring cells. The interaction between cells is one of Coulomb repulsion only (no current flows between cells) and provides the basis for computing with QCA. Theoretically, universal logic gates and binary wires could be constructed by assembling QCA of suitable design in suitable patterns. As to the possibility of coplanar crossing of signal paths without adverse effect, a compete theoretical explanation would exceed the space available for this article, but one can gain a partial, qualitative understanding from the illustration of crossed binary QCA wires in the bottom part of Figure 1.

One of the fundamental permutation matrices is the downshift permutation matrix, which is given by

where n is the number of elements to be permuted. Figure 2 illustrates a proposed QCA circuit that would implement the permutation matrix Q4.

This work was done by Amir Fijany, Nikzad Toomarian, and Matthew Spotnitz of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at  under the Electronics & Computers category.


This Brief includes a Technical Support Package (TSP).
Implementing Permutation Matrices by Use of Quantum Dots

(reference NPO-20801) is currently available for download from the TSP library.

Don't have an account? Sign up here.

NASA Tech Briefs Magazine

This article first appeared in the October, 2001 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.