  The evolution of a quantum lattice gas automaton (LGA) for a single charged
particle is invariant under multiplication of the wave function by a global
phase. Requiring invariance under the corresponding local gauge transformations
determines the rule for minimal coupling to an arbitrary external
electromagnetic field. We develop the Aharonov-Bohm effect in the resulting
model into a constant time algorithm to distinguish a one dimensional periodic
lattice from one with boundaries; any classical deterministic LGA algorithm
distinguishing these two spatial topologies would have expected running time on
the order of the cardinality of the lattice.
