Two-Dimensional Universal Automaton with Electron-like Tokens

Michael Biafore

June 5, 1990

Abstract

This report describes a reversible, computation-universal, two-dimensional cellular automaton constructed subject to constraints similar to those imposed by physics on optically driven compound heterostructure implementations of CA architectures which have been proposed previously by several groups[1, 2].

Keywords: Cellular Automata, Quantum Computation.

Contents

1 Introduction 2

2 The Billiard Ball Model, BBM 3

2.1 Partitioning Cellular Automata . . . . . . . . . . . . . . . . . . . . . 4

2.1.1 Margolus’s Billiard Ball Cellular Automaton . . . . . . . . . . 5 2.2 The TM gas variation on the Billiard Ball Model . . . . . . . . . . . 6

3 Construction of the Automaton 7 3.1 Geometrical Arrangement . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Transistion Table Broadcast . . . . . . . . . . . . . . . . . . . . . . . 8

4 Discussion 10

5 Acknowledgments 11

List of Figures

1 Partitioning CA with 2 × 2 block neighborhoods. . . . . . . . . . . . 4 2 The transition table for the usual (HPP-type) Billiard Ball CA. … 5 3 The complete transition table for the even (left) and odd (right) parti-

tions of the TM-variant of the Billiard Ball CA, up to rotations of the neighborhood blocks. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Single-electron transfer between regions. . . . . . . . . . . . . . . . . 7 5 The geometrical layout of the proposed automaton. Three even rows

and two odd rows, each containing two octagons, are shown. . . . . . 9 6 Time evolution of the automaton array. . . . . . . . . . . . . . . . . . 13

1 Introduction

The basic goal of our work is to take a step from the CA side of this interdisciplinary endeavor toward designing computationally interesting rules that also begin to subject themselves to some of the constraints imposed physically by the limited repertoire of physically realizable interactions, constraints of two-dimensional geometry, etc., that Toffoli[3] has spoken of. The idea is to take a simple interacting system considered tractable by the condensed-matter physicists, abstract away as many of the constraints present as our understanding of the physics allows, and then attempt to develop techniques for working within those constraints.

Here we have in mind a system and switching dynamics similar to the III-V semiconductor heterostructure and optical single-mode dissipative dynamics described by Obermayer, Teich, and Mahler[2]. In particular, we want incorporate two abstract features of that system into our set of restrictions

1. The notion of transitions induced by the broadcast of an external field

2. The dependence of such transitions on the occupation status of nearby cells

In the work of Obermayer et. al., the first feature corresponds to an external photon field, tuned to the transition energy between a discrete valence state, localized on one side of the structure, and a transient conduction band state, and applied for a sufficient period of time that the population of a second valence level, localized on the opposite side of the structure, becomes close to unity. Those authors use a generalized rotating wave approximation to solve for the time evolution of the electron subsystem’s density matrix in the presence of the photon driving field and the phonon reservoir. Their solution for the density matrix element corresponding to the population of the second valence level shows that when there is a sufficient separation between the time scales for phonon induced tunneling across the barrier, τ_{d}, and the characteristic time for spontaneous decay from the conduction level, τ_{r}, the result of this “single-mode dissipative” illumination is a reliable method of switching a single electron from the region of localization of the first valence level to the region where the second valence level is localized.

The second feature enumerated above is achieved in their work by evaluating the transition frequency shifts due to Coulomb renormalization of the energy levels in the valence band, which depend, via e.g. dipole-dipole interactions, on the occupancy status of localized levels which are nearby.

In what follows, we show how to construct a variant of the well-known Billiard Ball Model cellular automaton (which is reversible and computationally universal) satisfying the two stylized constraints derived (albeit somewhat distantly) from the physics relevant to some proposed structures for so-called quantum computation. The constructed automaton retains all of the essential properties of the Billiard Ball CA, although it utilizes much more space, and runs about one-sixth as fast as would a naive embedding of the formal automaton array which permitted itself local interactions of an otherwise arbitrary type. The automaton rule is of a partitioning, 2-phase type, and these concepts will be briefly reviewed in Section 2 before the automaton rule of central interest in the present context is introduced. Section 3 contains a discussion of the physical arrangement and operation of the construction. The final Section contains some elaboration of the limitations and prospects of this and similar models.

2 The Billiard Ball Model, BBM

The Billiard Ball Model was originally devised by Edward Fredkin[6] of MIT as a model of digital computation which would obey the reversible classical equations of motion governing the evolution of a gas of infinitely hard billiard balls. By interpreting the presence or absence of a ball as a binary variable, and the relation between the pre- and post-collision locations of two streams of balls undergoing finite impact parameter collisions with each other as a logical function of the binary values in the input streams, the evolution of particular microscopic initial states of the gas can be interpreted as the operation of a computation-universal computer. In addition to the gas particles, it is necessary to employ infinitely massive rigid walls, which act as mirrors, and are used to redirect streams of balls, which act as wires carrying signals, to common collision regions, which act as the logical gates.

Realizing this reversible continuum model in the discrete domain of cellular automata proved to be a non-trivial task. The essential difficulty, in informationtheoretic or statistical-mechanical terms, lay in the fact that reversibility requires that the evolution lose no information (generate no entropy), so that after a timereversal operation, the system can retrace its trajectory without tapping an “external memory” agent. Unfortunately, previously known types of automata made it difficult to arrange for the careful hoarding and later re-collection of all this information that makes reversibility possible. The solution to the problem of facilitating the construction of provably reversible automata was the introduction by N. Margolus[5] of a new type of automaton, the partitioning cellular automaton.

Figure 1: Partitioning CA with 2 × 2 block neighborhoods.

2.1 Partitioning Cellular Automata

Partitioning cellular automata generalize the notion of “neighborhood” such as the familiar Moore, and von Neumann neighborhoods. For a given array of automaton cells, a series of two or more partitions is introduced. Each partition consists of a collection of disjoint “blocks” (usually 2×2 squares of cells) which completely cover the cellular array. Only the members of the same block are considered to be neighbors, and the updating consists of a mapping from the old block configuration to the new block configuration.The rule is then reversible if and only if the mapping is bijective. Clearly, for any single partition the system is decoupled into a large number of small non-interacting subsystems. For this reason, it is essential to choose at least two partitions which “link” the entire cellular array in the sense that information can eventually travel between any two regions of the array. Figure 1 illustrates these concepts. The small light-dotted squares visible in some parts of the figure delimit the individual cells of the automaton. The larger dashed squares and heavy-line squares represent blocks of the “even” and “odd” partitions respectively. The shaded square is the lower right cell of a block in the even partition, and the upper left cell of a block in the odd partition.

All rules discussed in this paper will utilize these two partitions. The rule for updating a block may, but need not, vary from the even “phase” to the “odd” phase. The Billiard Ball Model cellular automaton based on the HPP (Hardy-dePazzis-Pomeau) lattice gas, like HPP itself, uses the same rule for both phases, while the BBM based on the TM (Toffoli-Margolus) lattice gas, has a distinct rule for the even and odd

Figure 2: The transition table for the usual (HPP-type) Billiard Ball CA.

phases.

2.1.1 Margolus’s Billiard Ball Cellular Automaton

This is a partitioning binary cellular automaton rule, with two phases corresponding to the two overlapping partitions of the space into 2 × 2 neighborhoods as shown in Fig.1. The transition rules for the Billiard Ball Model with HPP-like free propagation are the same for both phases, that is, it is independent of whether the even or odd partition is currently in effect, and since it is rotationally invariant, we only need to define the block transitions for the six block configurations which are inequivalent under rotations of the block. To find the update of a block configuration which is related to one of the initial configurations shown in Fig.2 by a rotation R, one simply applies that rotation to the corresponding final configuration.

Like its continuum progenitor, Fredkin’s Billiard Ball gas, this rule is computationally universal, and logical operations are performed by finite impact parameter collisions between streams of balls, which are represented directly as cells with binary value 1. The streams are directed using stationary “mirrors” consisting of static (or small period cyclic) configurations of cells which reflect the “balls” without acquiring any momentum themselves. Unfortunately, this particular incarnation of the Billiard Ball Model does not seem to admit a “direct translation” using the restricted set of physics-inspired transition primitives we are allowing ourselves. The problem appears to boil down to the difficulty of crossing signals in two dimensions when trying to simultaneously implement the diagonal HPP-like propagation of single particles for all four possible directions (See the second row of Fig.2). Because of these difficul-Figure 3: The complete transition table for the even (left) and odd (right) partitions of the TM-variant of the Billiard Ball CA, up to rotations of the neighborhood blocks.

ties, we were led to consider an equivalent, but less well-known variation of the BBM which does not have any troublesome diagonal propagation in its transition table.

2.2 The TM gas variation on the Billiard Ball Model

This variant is derived by requiring that the free propagation of “particles” occur along directions collinear with the cellular rectangular lattice directions, and constructing the remainder of the rule consistent with this requirement and the action of the original Billiard Ball Model. At the expense of both space and time resources, such variants are constructable under general conditions[4, p.91]. The construction consists of taking the rotation-reduced block transition table shown in Fig.2 and rotating the updated blocks in the clockwise direction for the even partition (which is assumed to hold on the even time steps), and in the counter-clockwise direction for the odd partition (which is assumed to hold on the odd time steps). The resulting rule table of the variant we intend to use is shown in Fig. 3.

For the even partition, the update consists of rotating the data in the clockwise direction for the majority of the cases, and counter-clockwise for the minority case of a single occupied cell in the block, and no change for the diagonal occupancy case (or for the completely empty block or completely occupied block cases). When the odd partition is in effect, all rotational directions are reversed. The majority of block

Figure 4: Single-electron transfer between regions.

configurations, namely those with two non-diagonal or three occupied cells, rotate their occupied cells counter-clockwise, while the single occupied cell rotates in the minority, or clockwise direction and the diagonal case again remains stationary.

Since, unlike the HPP-based Billiard Ball Model, this rule has different transition tables for the two phases, we will need to apply a longer sequence of external frequencies in order to induce just those transfers of the electron-like tokens (representing bit = 1) which will insure the automaton updates itself correctly.

3 Construction of the Automaton

First, we introduce the elementary “one-electron shift” operation based on an idealization of the single-mode dissipative dynamics of Teich et. al.[2]. The localization along one spatial axis, and energy eigenvalue along the vertical axis of the basic structure analyzed in that work are shown in the top of Fig. 4. The lower part of that figure introduces the corresponding schematic notation we will use to display the final construction, by showing the top view of a hypothetical layout along the surface of the xy−plane, which suggests that the components of the automaton to be constructed may more nearly resemble the proposed planar resonant field-effect quantum-well proposals[8] than grown structures, in which the wells would typically be perpendicular to the surface.

The structure which would corresond to a one-bit cell of Teich et. al. is depicted here by two polygonal regions, one for each side where the valence states are localized, and a space between them where the higher energy transient state occurs. The automaton proposed here simply consists of an collection of such polygonal regions in the plane, arranged so that the total occupancy number of their nearest and nextnearest neighbor cells provide sufficient conditionality to implement the variant of the BBM displayed in Fig.3.

3.1 Geometrical Arrangement

The proposed automaton is shown in Fig.5. Each polygonal region represents the localization region of a low-lying electron state which is an approximate energy eigenstate for time scales less than the time for phonon-assisted tunneling, τ_{d} of reference [2].

The triangular regions in the even rows of octagonal clusters are in one-to-one correspondence with the cells of the rectangular lattice TM-like Billiard Ball Model described above. The triangular regions in the odd rows are a second complete copy of the rectangular cellular array, and are used to compute the new state of the automaton on the odd numbered time steps when the odd partition would be in effect. That is, the updating which would take place during the odd partition of, for example, Fig.1, occurs here in a physically distinct location as well, namely in the odd-numbered rows of octagons. Computations that would occur when the even partition is in effect occur here at even times steps, and only in the even-numbered rows of octagons.

The smaller rectangular areas within the octagonal clusters are “latching sites” which are used, in a manner described below, to prevent undesired double transitions, also known as transparency, when transferring electrons during the two-step updating of the blocks.

The larger rectangular regions, which connect the odd rows and even rows of octagonal blocks, are similarly employed as latching sites during the part of the computational cycle in which results of the update from the previous partition are exported to the corresponding cells of the alternate partition prior to its updating transitions.

3.2 Transistion Table Broadcast

This section describes the illumination schedule, that is, the sequence of external field frequencies, ω(#n.n, #n.n.n.), which are assumed to be both necessary and sufficient stimulus to induce the corresponding transitions when applied for an appropriate interval. The transition frequencies to the transient level have two arguments. The first is the number of nearest neighbor cells of the same polygonal type which are occupied. When operating correctly, different polygonal types will never be simultaneously occupied. The second argument is the number of next nearest neighbor cells (of same type) which are occupied.

As mentioned above, to prevent transparency problems, each transfer of the Figure 5: The geometrical layout of the proposed automaton. Three even rows and two odd rows, each containing two octagons, are shown. electron-like tokens, or bits, is broken into a latched, two-step process. A bar over the frequency denotes the second leg of each two-step process, and we assume that it can be made different from the other frequencies by imposing some static locally asymmetric conditions. The illumination schedule appropriate to implementing the BBM variant of Fig.3 on the structure depicted in Fig. 5 is seen to be given by

1. ω(0, 0) — activates an electron transfer from triangular region to rectangular region, which is the first step of the minority rotation for the case of a single occupied triangular cell in a block

2. ω̄(0, 0) — activates the transfer which completes the minority rotation

3. ω(1, 0) ⊕ ω(1, 1) — induces the first step of the majority rotation except for the single occupation case, which has already been dealt with, and the diagonal occupation case, which is simply to be transformed back into itself

4. ω̄(1, 0) ⊕ ω̄(1, 1) — completes the majority rotation

5. ω_{ex} — first step of “exporting” the results of the updating to the corresponding cells of the alternative partition

6. ω̄_{ex} — completes the process of transferring results of the previous partition’s updating to the next partition

These steps are then repeated, but the frequencies of illumination are those appropriate to the alternate strip, and should be totally disjoint from the range of the frequencies for the previous partition. Presumably such simple periodic variation of energy level spacings, in marked contrast to some other parts of this construct, is not difficult to acheive in real structures. The resulting evolution of the automaton is shown in Fig.6 for a few steps. The black polygons represent those for which the higest valence level localized in the region is occupied. The initial configuration is shown at upper left, and time increases from left to right and top to bottom, starting with the even partition (and therefore occuring on the three even-numbered rows, 0, 2, and 4. In frame 5, the even partition update has just been completed, and in frame 6, the exporting of the results to the octagons computing the odd partition has just begun. In frame 8, the odd partition updating sequence has started.

4 Discussion

Many of the limitations of the construct described above are clear. The tools we have permitted ourselves in the construction are still far removed from the tools which are actually readily available in the phenomenological panoply of condensed matter. To note just one example, we have taken substantial liberty in assuming the existence of generic dependences of energy levels on nearest- and next-nearest-neighbor occupancies. In a real system, of course, one would also need these dependences to produce level shifts of sufficient magnitude and predictability, as well. Attempts to imagine how one might build such an automaton, even from the physical elements on which it is loosely based, quickly reveal other limitations.

Furthermore, no mechanism for error-detection/correction has been included in the above construct; although, we are currently working on extensions in this direction, where we believe the seemingly irrelevant logical-reversibility property of the automaton will prove to be the central issue.

5 Acknowledgments

Thanks to N. Margolus and M. Smith for useful discussions, and to M. Smith for assistance with the figures. Support was provided by the National Science Foundation, grant no. 86180002-IRI.

References

[1] G. Frazier, Cellular Automata Devices, United States Patent 4,769,644 (1988).

[2] K. Obermayer, W. Teich, and G. Mahler, Structural basis of multistationary quantum systems. I. Effective single particle dynamics, PRB 27, 8096 (1988).

[3] Cellular Automata Overview, these proceedings.

[4] N. Margolus, Physics-Like Models of Computation, Physica 10D (1984), 81-95.

[5] N. Margolus, Physics and Computation, Ph.d thesis, MIT (1987).

[6] E. Fredkin and T. Toffoli, Conservative Logic, Int. J. Theor. Phys. 21 (1982), 129-253.

[7] W. Teich, and G. Mahler, Optically controlled multistability in nanostructured semiconductors, Physica Scripta (1988-89).

[8] K. Ismail, D. Antoniadis, and H. Smith, Lateral resonant tunneling in a double-barrier field-effect transistor, Appl. Phys. Lett. 55, (1989), p.589.

[9] K. Obermayer, G. Mahler, H. Haken, Multistable Quantum Systems: Information Processing at Microscopic Levels, PRL 58, 1792 (1987).

[10] G. Mahler, K. Obermayer, Towards the Quantum Computer: Information Processing with Single Electrons, in Computational Systems–Natural and Artificial, ed. Haken, Q295.I586(1987).

[11] M. Sargent, Scully and Lamb, Laser Physics, (1974) QC476.2.S27.

[12] H. Haken, Light, vol.1 Waves, Photons, Atoms 344pp.; vol. 2 Laser Light Dynamics 330pp., QC355.2.H33.

Figure 6: Time evolution of the automaton array. 13