{'fraction_non_alphanumeric': 0.04809555688664952, 'fraction_numerical': 0.020823790564109792, 'mean_word_length': 4.141666666666667, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum mechanics of lattice gas automata. II. Boundary conditions and other inhomogeneities

We continue our analysis of the physics of quantum lattice gas automata (QLGA). Previous work has been restricted to periodic or infinite lattices; simulation of more realistic physical situations requires finite sizes and non-periodic boundary conditions. Furthermore, envisioning a QLGA as a nanoscale computer architecture motivates consideration of inhomogeneities in the `substrate'; this translates into inhomogeneities in the local evolution rules. Concentrating on the one particle sector of the model, we determine the various boundary conditions and rule inhomogeneities which are consistent with unitary global evolution. We analyze the reflection of plane waves from boundaries, simulate wave packet refraction across inhomogeneities, and conclude by discussing the extension of these results to multiple particles.


Introduction
Shor's discovery of a polynomial time quantum algorithm for factoring [1] stimulated a surge of interest in quantum computation (see the extensive bibliographies of [2]). Most work has concentrated on serial algorithms-sequences of unitary, few qubit* operationsthe quantum version of serial Boolean logic [4]. Single quantum logic gates have been realized experimentally in ion traps [5] and quantum electrodynamics cavities [6], and short sequences of such unitary operations have recently been implemented with NMR [7]. All of these systems, as well as proposed solid state architectures such as arrays of quantum dots [8], exist physically in d > 0 spatial dimensions and therefore naturally evolve in parallel. Imposing a single gate operation restricts the rest of the qubits to be invariant, i.e., they must evolve by the identity operator; at the opposite extreme all the qubits would evolve according to the same, local (few qubit) operation during a single timestep. A quantum computer evolving according to such a homogeneous, local, unitary rule would have the quantum version of the massively parallel architecture possessed, for example, by Margolus' CAM machines [9].
The simplest algorithms which would run on such an architecture are quantum cellular automata (QCA) [10] or quantum lattice gas automata (QLGA) [11]. Even in d = 1 spatial dimensions QCA are capable of universal computation [12], and the existence of the universal reversible billiard ball computer [13] implies that QLGA are also, at least in d ≥ 2 spatial dimensions. Just as classical LGA are most effectively deployed to simulate physical systems such as fluid flow [14], however, QLGA most naturally simulate quantum physical systems [11,15,16]: with the simplest homogeneous evolution rule, one particle QLGA simulate the constant potential Dirac [11] or Schrödinger [17] equation, depending on the relative scaling of the lattice spacing and timestep.
An earlier paper [15] initiated a project to analyze which physical processes QLGA can simulate effectively. In that paper and in this one we concentrate on the most general model for a single quantum particle with speed no more than 1 in lattice units, moving on a lattice in one dimension. The amplitudes for the particle to be (left, right) moving at a lattice point x ∈ L are combined into a two component complex vector ψ(t, x) := ψ −1 (t, x), ψ +1 (t, x) which evolves as ψ(t + 1, x) = w −1 ψ(t, x − 1) + w 0 ψ(t, x) + w +1 ψ(t, x + 1). (1.1) Here the weights w i ∈ M 2 (C) are 2 × 2 complex matrices constrained by the requirement * A qubit [3] is a quantum system whose state is a vector in a two dimensional Hilbert space, e.g., a spin-1 2 particle fixed in space.
that the global evolution matrix be unitary. We showed in [11] that the most general parity invariant solution, up to unitary equivalence and an overall phase, is given by w −1 = cos ρ 0 i sin θ 0 cos θ w +1 = cos ρ cos θ 0 i sin θ 0 Describing the evolution by (1.1)-(1.3) assumes that the system is homogeneous in space and that the lattice L is isomorphic either to the integers Z or to a periodic quotient thereof, say Z N . To simulate physical systems [18] more generally, the model should be extended to allow for finite size and non-periodic boundary conditions. Furthermore, envisioning a QLGA as a nanoscale quantum computer architecture [19,20,2] motivates consideration of inhomogeneities in the 'substrate', possibly as a step towards implementing logical gates [4] and away from simply simulating quantum physical systems. In [15] we showed how to introduce an inhomogeneous potential in the model; the purpose of this paper is to investigate more general inhomogeneities in the evolution rule, including boundary conditions.
In Section 2 we consider the simplest possible modification of the evolution rule (1.1) for a boundary at x = 0, say, setting w −1 there to 0 and allowing the weight w 0 to differ from the constant w 0 of the rest of the lattice. The resulting Type I boundary condition suggests the form for a corresponding Type I inhomogeneity where the global evolution matrix (1.2) is changed by replacing one of the w 0 blocks with a different matrix w 0 , and allowing the weights w i to differ on either side of the antidiagonal through it. In Section 3 we show that such an inhomogeneous rule is unitary provided θ is the same for all the weights.
There is a dual inhomogeneity across which ρ is constant but θ may differ; we describe this Type II inhomogeneity in Section 4 and find the corresponding boundary condition. In Section 5 we observe that the Type I and II inhomogeneities can occur together, changing both ρ and θ. The corresponding Type III boundary condition has an extra degree of freedom, justifying distinct classification.
In Section 6 we show how to find the eigenfunctions of U in the presence of these boundaries. In each case the result is a linear combination of left and right moving plane waves with the same frequency. On a finite lattice with two boundaries, the spectrum of U is discrete. In Section 7 we investigate the discrete spectra for pairs of each type of boundary condition, determining how they depend on the boundary parameters and what the consequences are for the eigenfunctions.
Simulations of wave packets on lattices with boundary conditions and in the presence of inhomogeneities confirms that the physical consequences of these inhomogeneous evolution rules are as expected. We show some results in Section 8.
We conclude in Section 9 with a summary and a discussion of the extension of this work to the multiple particle sector of the Hilbert space.

Type I boundary conditions
If our system is neither infinite nor periodic, we must model it on a bounded lattice, e.g., Since there is no lattice point to the left of 0, it is clear that the evolution rule (1.1) must be adjusted there (as it must also be at the right boundary). Making the minimal change in the model, let us suppose that the global evolution matrix takes the form where the w i are given by (1.3). Thus a left moving particle at x = 1 has the same amplitudes (given by w +1 ) to advect to x = 0 and scatter to the left or right, and a right moving particle at x = 0 has the same amplitudes (given by w −1 ) to advect to x = 1 and scatter to the left or right, as each would were there no boundary. (The analogous form for the evolution rule at a right boundary is obtained by a parity transformation.) The only differences we allow for this Type I boundary condition are in the amplitudes for the evolution of a left moving particle at x = 0 and for the scattering of a right moving particle at x = 0 which remains there during the advection step; these are given by w 0 .
The unitarity conditions U U † = I = U † U impose the following constraints on w 0 : The normalization condition (2.2a) requires for some arbitrary phase angle υ ∈ R. Combining (2.4)-(2.7), we find which satisfies all the constraints (2.2) and (2.3).
The Type I boundary condition defined by (2.1) and (2.8) gives the same amplitudes as (1.3) for the scattering of a right moving particle at x = 0 which remains there; only the amplitudes for the scattering of a left moving particle at x = 0 differ from the no boundary situation. The latter depend on a single real parameter υ characterizing the boundary. Notice also that these amplitudes do not vanish in the decoupled case ρ = 0 (whence w 0 = 0). That is, w 0 = 0 is required to define unitary boundary conditions even when the particle has speed 1 everywhere else in the lattice.

Type I inhomogeneities
The boundary weight w 0 defined by (2.8) has the same form as the weight w 0 defined in (1.3), except that the factor of sin ρ in the first column is replaced by e iυ . Thus we can interpret the evolution rule defined by (2.1) and (2.8) as describing a system where the coupling constant ρ satisfies cos ρ = 0 at and to the left of x = 0. This would make w −1 = 0 = w +1 , so there would be no advection to the left of x = 0. This suggests that the w 0 we found in Section 2 may be a special case of an inhomogeneity in the coupling constant ρ. So let us consider a Type I evolution rule inhomogeneity of the form: where the w i =: w i (ρ, θ) are defined by (1.3) and w ′ i := w i (ρ ′ , θ ′ ). Now the unitarity conditions impose constraints on the relation between the w i and the w ′ i as well as on the inhomogeneity matrix w 0 : is automatically satisfied but, again assuming that cos ρ = 0 = cos ρ ′ , (3.3a) requires sin(θ − θ ′ ) = 0, so we set θ ′ ≡ θ. Using the form (2.4) for w 0 , we observe that the constraints (3.2d) and (3.3d) are the same as (2.2b) and (2.3b), so the y i must satisfy (2.5) and (2.6). Constraint (3.2b) requires that which also satisfies the remaining (normalization) constraints in (3.2) and (3.3).
The arbitrary phase degree of freedom in the Type I boundary condition is not present in (3.5), but as anticipated, this Type I inhomogeneity describes a change in the coupling constant ρ, the mass θ being held fixed across the inhomogeneity. The locus of the inhomogeneity is quite precise: a left moving particle from x = 0 obeys the 'primed' rules, while a right moving particle obeys the 'unprimed' ones.

Type II inhomogeneities and boundary conditions
The form (3.1) of the Type I inhomogeneity partitions the evolution matrix U into two pieces across an antidiagonal through the w 0 block (inside the block the partition runs between the two columns). We might also consider an inhomogeneity which partitions U across an antidiagonal through a pair of w −1 and w +1 blocks. Such a Type II evolution rule inhomogeneity has the form: The unitarity conditions U U † = I = U † U impose even more constraints in this more complicated situation: Suppose the inhomogeneity matrices have the most general forms: Then, assuming cos ρ = 0, constraint (4.2c) requires z 2 = 0 = z 4 . Similarly, assuming cos ρ ′ = 0, constraint (4.2d) requires x 1 = 0 = x 3 . Thus the inhomogeneity matrices have the same advection/scattering interpretation as in the homogeneous situation.
Now constraints (4.3c) and (4.3d) imply that ) and respectively. Imposing the normalization constraint (4.2a) we find that Then imposing the normalization constraint (4.3a) implies cos 2 ρ = cos 2 ρ ′ , so we set ρ ′ ≡ ρ. Combining (4.4), (4.5) and (4.7) gives Similarly, imposing the normalization constraint (4.2e) we find that Combining (4.4), (4.6) and (4.9) gives which also satisfies the last normalization constraint (4.3e). The two remaining constraints (4.2b) and (4.3b) require only that χ ≡ −ζ (mod 2π), which can thence be set to 0 by a unitary transformation. Thus (4.8) and (4.10) become Just as the Type I inhomogeneity described by (3.1) and (3.5) specializes to a Type I boundary condition described by (2.1) and (2.8) when cos ρ ′ = 0 so that there is no advection to the left of x = 0, the Type II inhomogeneity described by (4.1) and (4.11) specializes to a boundary condition when cos θ ′ = 0. In this situation, when a left moving particle at x = 1 advects to x = 0 it scatters to the right, while a right moving particle at x = 0 which remains at x = 0 also scatters to the right-a particle initially at x > 0 or at x = 0 and right moving has no amplitude to be at x < 0 or at x = 0 and left moving at any subsequent timestep. This is a special case of the Type II boundary condition which we expect to be characterized by nontrivial phases, just as is the Type I boundary condition. The 'primed' parameters satisfy ρ ′ ≡ ρ and cos θ ′ = 0, so generalizing the Type II inhomogeneity by multiplicative phases suggests where is a generalization of (4.10). Then the unitarity conditions impose constraints on the phase angles χ 1 , χ 2 , υ and ζ via (4.2) and (4.3). Constraint (4.2c) is automatically satisfied, while (4.3d) requires χ 1 ≡ χ 2 =: χ (mod 2π). This means that the normalization constraints are necessarily satisfied so the only remaining constraints are (4.2b) and (4.3b). These are satisfied provided υ ≡ χ + ζ (mod 2π). Finally, up to unitary equivalence we may set χ = 0, so the most general Type II boundary condition is defined by: where w ′ i = w i (ρ, 0). Just as does the Type I boundary condition, the Type II boundary condition has one phase degree of freedom.

Type III boundary conditions
The two types of inhomogeneities we have found reflect the ρ ←→ θ duality evident in the dispersion relation (6.2) discussed in [15]: The Type I inhomogeneity has constant θ and discontinuity in ρ while the Type II inhomogeneity has constant ρ and discontinuity in θ. Suppose we wish to change both ρ and θ. This is clearly possible using a Type I inhomogeneity to change ρ followed by a Type II inhomogeneity to change θ, provided the discontinuities are sufficiently far apart that the constraints (3.2), (3.2), (4.2) and (4.3) do not overlap. In fact, the discontinuities can be adjacent: it is straightforward to verify that the evolution matrix is unitary for w −1 = w −1 (ρ, θ) and w +1 = w +1 (ρ, θ ′ ) as in (4.11) and w 0 = w 0 (ρ ′ , θ ′ , ρ). The evolution matrix (5.1) describes a system in which the parameters ρ ′ and θ ′ change to ρ and θ across the inhomogeneity.
As expected, in addition to θ ′ there are two phase angle degrees of freedom: υ and ζ.

Plane waves near a boundary
The global evolution matrices (2.1), (4.14) and (5.2) describe unitary evolution of a single particle in the presence of a boundary of Type I, II, or III, respectively. Away from the boundary the local evolution is still given by (1.1) and (1.3), so the one particle plane waves ψ (k,ǫ) (x) = ψ (k,ǫ) (0)e ikx (6.1) we found in [15] still evolve, locally, by multiplication by e −iǫω at each time step, where ω satisfies the dispersion relation cos ω = cos k cos θ cos ρ + sin θ sin ρ (6.2) and ǫ ∈ {±1}. In fact, any linear combination evolves locally by phase multiplication as both k and −k satisfy (6.2) with the same frequency ω.
Consider the Type I boundary condition at x = 0 and suppose there is an eigenfunction ψ (ω) (x) of the form (6.3), which should be interpreted as a linear combination of incident and reflected plane waves with relative amplitude A, just as in the situation of scattering off a potential step considered in [21]. Then The linear combination (6.3) is well defined for x < 0 and for any A ∈ C, so subtracting (6.5) from (6.4) gives Using (1.3), (2.8) and (6.3) in (6.6) we find where ψ (k,ǫ) (0) := i sin ρ cos θ − ie −ik cos ρ sin θ sin ρ sin θ + e ik cos ρ cos θ − e −iǫω (6.8) is the (unnormalized) eigenvector of D(k) in [15]. That is, with A given by (6.7), the linear combination (6.3) is an eigenfunction satisfying the Type I boundary condition.
To find the eigenfunctions for the Type III boundary condition, we still suppose they satisfy (6.9), but not (6.10). Since w −1 is the same as for the Type II boundary, (6.11) still implies (6.12). Now applying (5.2) to the eigenfunction ψ (ω) (x) at x = 0 gives which comprises a pair of linear equations for ψ (ω) −1 (0) and A. These equations can be solved to give the eigenfunctions for the Type III boundary conditions, although we will not need the explicit solution here.

Plane waves on finite lattices
With only one boundary, e.g., L = N as we were considering implicitly in the previous section, the wave number can take any value in the interval −π < k ≤ π and the frequency/energy spectrum is continuous with range θ − ρ ≤ |ω| ≤ π − (θ + ρ) (assuming 0 ≤ ρ ≤ θ ≤ π/2) determined by the dispersion relation (6.2). On finite lattices, however, the spectra are discrete and are determined by the two boundary conditions. Consider the case of two Type I boundary conditions on a lattice of cardinality N . The weights in the boundary condition at x = N − 1 are the parity transforms of those in (6.6): This gives a second constraint on A: which must be consistent with (6.7). To see how this determines the discrete spectrum, let υ = 0 = ρ. Then (6.7) becomes A = −e −2ik e ik cos θ − e −iǫω + sin θ e −ik cos θ − e −iǫω + sin θ (7.2) and (7.1) becomes Setting the right hand sides of (7.2) and (7.3) to be equal and using the dispersion relation (6.2) to eliminate ω, we find, after some algebra, e −2i(N−2)k (sin θ − i sin k cos θ) = sin θ + i sin k cos θ. (7.4) Supposing k to be real, the right hand side of (7.4) is the complex conjugate of the parenthesized expression on the left hand side, which implies that tan (N − 2)k + sin k cot θ = 0.
The left hand side of (7.5) has poles at k = (n + 1/2)π/(N − 2), n ∈ Z, between each pair of which there must be a root of the equation. Thus (7.5) has N − 1 roots in the interval 0 ≤ k ≤ π, giving N −1 distinct values for eigenfrequencies in the range θ−ρ ≤ ω ≤ π−θ−ρ (assuming 0 ≤ ρ ≤ θ ≤ π/2). But U is a 2N × 2N matrix so it must have 2N eigenvalues e −iω . Figures 1 and 2 show the results of computing the eigenvalues of U numerically for N = 16: the eigenfrequencies are plotted as functions of the Type I boundary parameter υ, set to the same value at each boundary. Notice that while most of the eigenfrequencies lie in the expected intervals, there are four which, over parts of the range of υ, do not.
of k, the left hand side of (7.4) becomes arbitrarily small. So, if there were such a k which caused the right hand side of (7.4) to vanish, it would provide an additional root. Solving we find e ik = − tan θ ± sec θ.
The negative root in (7.6) makes the norm |e −ik | ≤ 1 for 0 ≤ θ ≤ π/2; furthermore, it satisfies the dispersion relation (6.2) with ω = 0. Thus in the N → ∞ limit, 1 is an eigenvalue of U with multiplicity two. For finite N these extra eigenfrequencies split, finely, and are only very close to 0. As we see in Figures 1 and 2, as υ changes away from 0, the splitting increases and the eigenfrequencies move into the range associated with real wave numbers. An analogous discussion explains the pair of eigenfrequencies near π at υ = π. The eigenfunctions having these eigenfrequencies corresponding to wave numbers with nonzero imaginary part are, of course, not plane waves; rather, each describes the state of a 'low' energy particle which is 'trapped' at the boundaries, with exponentially decreasing amplitude to be in the interior of the lattice.
the Type II boundary parameter ζ, set to the same value at each boundary. As in the Type I boundary situation, most of the eigenfrequencies lie in the ranges corresponding to real wave numbers, although near ζ = π there are four which do not, and which are explained by an analysis similar to that of the preceding paragraph.
Finally, consider the case of two Type III boundary conditions, again with equal parameter values. In this case there is a non-phase parameter which can be adjusted, namely θ ′ . Figure 5 shows the eigenfrequencies of U as a function of θ ′ for the rule defined by ρ = 0, θ = π/4, with boundary parameters υ = 0 = ζ. To separate the eigenvalues we have computed them for a lattice of size only N = 4. Figure 6 is similar, but the rule parameters are now ρ = π/4, θ = π/3. In this case N = 8 and the two eigenfrequencies near 0 are only finely split over the whole parameter range. Notice that in each case there are actually six eigenvalues corresponding to imaginary wave numbers. Examination of the eigenfunctions shows that the two with eigenfrequencies near 0 have amplitudes concentrated in the states |1, −1 and |N − 2, +1 , while the four with eigenfrequencies closer to ±π have amplitudes concentrated at x = 0 and x = N − 1.
Let us first consider the reflection of such a wave packet from the possible boundaries. Figure 7 shows the evolution of the wave packet with parameters ρ = 0 and θ = π/4 in the presence of Type I boundary conditions with υ = 0. Reflection from Type II and Type III boundaries is extremely similar: in each case the significant dispersion of the wave packet at the time of interaction with the wall results in a sequence of reflected (smaller) wave packets.
As we learned in [15], a 'massless' wave packet disperses more slowly than a massive one. In Figure 8 we show the results of a simulation of this case: ρ = π/4 = θ and the boundaries are both of Type II with ζ = 0. Reflection from Type I and Type III boundaries is again similar: in each case the wave packet reflects cleanly and suffers little more dispersion than if the boundary had not been there. Now let us consider the effect of rule inhomogenities on wave packet evolution. Figure 9 shows the results of a simulation in which there is a Type I inhomogeneity at x = 31: the rule parameter θ is constant at π/4 while ρ is 0 to the left, and π/4 to the right, of the inhomogeneity. There is both reflection and transmission of the wave packet at the inhomogeneity: the reflected wave disperses rapidly which causes an interaction with the left boundary similar to that shown in Figure 7 while the transmitted wave packet has little dispersion and evolves much as the wave packet in Figure 8. x t x |ψ| 2 Figure 9. Evolution of the same wave packet as in the previous figures with rule parameters θ = π/4 everywhere and ρ = 0 to the left and ρ = π/4 to the right of a Type I inhomogeneity at x = 31. Both boundaries are of Type I with υ = 0.
(figure available from author ) Figure 10. Evolution of the same wave packet as in the previous figures with rule parameters ρ = π/4 everywhere and θ = π/4 to the left and θ = π/3 to the right of a Type II inhomogeneity at x = 32. Both boundaries are of Type II with ζ = 0.
Next, let us consider the effect of a Type II inhomogeneity which changes the value of θ from π/4 to the left of x = 32 to π/3 to the right. Figure 10 show the results of a simulation with ρ = π/4 everywhere and Type II boundary conditions. To the left of the inhomogeneity the rule is 'massless'; this is evident in the negligible dispersion of the wave packet and its reflection off the inhomogeneity and then off the left boundary. With higher probability, however, the particle is transmitted through the inhomogeneity. The transmitted wave packet evolves according to a 'massive' rule and begins to disperse slowly so that reflection off the right boundary creates a small trailing wave packet.
Recall from Section 5 that the Type I and Type II inhomogeneities can be adjacent with evolution matrix of the form (5.1). Figure 11 shows the results of a simulation of this situation: to the left of the inhomogeneity ρ = 0, θ = π/4 and to the right ρ = π/4, θ = π/3. The boundary conditions are of Type III with θ ′ = 0 = υ = ζ. There is the same concentration of probability at the inhomogeneity that occurs with the Type I inhomogeneity shown in Figure 9, together with less transmission and more dispersion to the right than with the Type II inhomogeneity shown in Figure 10.
Finally, recall the ρ ←→ θ duality displayed by the dispersion relation (6.2). Figure 12 shows the results of a simulation in the presence of a Type III inhomogeneity constructed to convert the rule parameters ρ = π/3, θ = π/4 on the left to the dual pair ρ = π/4, θ = π/3 on the right. The reflected and transmitted wave packets have more even probabilities than in Figure 11 and evolve with the opposite group velocities. There is some asymmetry, most evident at the end of the simulation upon reflection from the boundaries; it is due to the asymmetry of the combined Type I/Type II inhomogeneity as well as of the initial condition.

Discussion
We have found dual inhomogeneities consistent with unitary global evolution of the general one particle rule (1.1)-(1.3): Type I implements a change in ρ while Type II implements a change in θ; adjacent Type I/Type II inhomogeneities implement changes in both ρ and θ. Each of these three possibilities has a corresponding boundary condition characterized by additional parameters. Despite this apparent variety of possibilities, the unitarity constraint is quite restrictive: besides the phase implementation of an inhomogeneous potential [17,15] and some degenerate cases, these are the only possible local inhomogeneities up to unitary equivalence.
A natural question to ask is how these rule inhomogeneities extend to the complete multiparticle rule set. Even the homogeneous rules for the general one dimensional QLGA whose one particle subspace we have been investigating are quite complicated as there are effectively two, three and four particle interactions. In [11], however, we found the only particle preserving generalization of the rules (1.1)-(1.3) with ρ = 0 (i.e., with particles of unit speed). In this case no more than two particles can advect simultaneously to a given lattice site, whereupon they scatter in opposite directions with amplitude e iφ , φ ∈ R. In fact, the global evolution remains unitary if the constant phase angle φ considered in x t x |ψ| 2 Figure 11. Evolution of the same wave packet as in the previous figures with rule parameters ρ = 0, θ = π/4 to the left and ρ = π/4, θ = π/3 to the right of a combined Type I/Type II inhomogeneity at x = {31, 32}. Both boundaries are of Type III with θ = 0 = υ = ζ.
(figure available from author ) Figure 12. Evolution of the same wave packet as in the previous figures with dual rule parameters ρ = π/3, θ = π/4 to the left and ρ = π/4, θ = π/3 to the right of a combined Type I/Type II inhomogeneity at x = {31, 32}. Both boundaries are of Type III with θ = 0 = υ = ζ. [22,11,17,21] becomes any function of the lattice sites φ(x). That is, the two particle scattering amplitude can be any inhomogeneous function on the lattice, independently of the one particle 'scattering' amplitudes-and this independent inhomogeneity extends to the values of φ(x) at the boundaries. (Notice that even in the Type I and Type III boundary conditions where w 0 = 0, and hence a particle scattering off the boundary can have speed 0, no more than two particles can advect to the same lattice site.) The question of determining which boundary conditions are consistent with integrability of the model, via the Bethe ansatz [23,24] as we began studying in [21] or by generalization of the Yang-Baxter equation [24] as has been used in closely related models [25], is of fundamental interest.
For the purposes of quantum computation with QLGA, we conclude by noting that we have explicitly formulated the possible local inhomogeneities in the one dimensional unit speed model. Extending these multiparticle results to multiple speeds and higher dimensions seems likely to be algebraically more complicated but conceptually similar-single particle single speed models with inhomogeneities have been constructed in two dimensions [26,27,17]. More interesting is the question of how to exploit such inhomogeneities to effect specific quantum computational tasks more efficiently than by simply implementing a quantum version of reversible billiard computing [13,20] using a homogeneous rule. The most natural use of QLGA may be to simulate other quantum physical systems; designing an inhomogeneous QLGA to be an efficient universal quantum computer may consequently be difficult. A reasonable intermediate goal would be to solve specific problems particularly well suited to this architecture. Although neither implements a quantum algorithm, Squier and Steiglitz' particle model for parallel arithmetic [28] and Benjamin and Johnson's recent proposal for an inhomogeneous nanoscale cellular automaton adder [29] may provide useful points of departure.