David A. Meyer,
``From gauge transformations to topology computation in quantum lattice gas automata'',
Journal of Physics A: Mathematical and General 34 (2001) 6981-6986;
quant-ph/0105087.

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.

PlainTeX (8 pages): PostScript (1156K), PDF (153K).