Universal computation by multi-particle quantum walk

Abstract

A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. Here we consider a generalization of quantum walk to systems with more than one walker. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. Multi-particle quantum walk includes a broad class of interacting many-body systems such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions. We show that multi-particle quantum walk is capable of universal quantum computation. Since it is also possible to efficiently simulate a multi-particle quantum walk of the type we consider using a universal quantum computer, this model exactly captures the power of quantum computation. In principle our construction could be used as an architecture for building a scalable quantum computer with no need for time-dependent control.

References in corpus (12)

• Universal computation by quantum walk
• Quantum walks of correlated particles
• Exponential algorithmic speedup by quantum walk
• Quantum Walk in Position Space with Single Optically Trapped Atoms
• Realization of quantum walks with negligible decoherence in waveguide lattices
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Quantum Walk on a Line with Two Entangled Particles
• Two-particle states in the Hubbard model
• Quantum random walk of two photons in separable and entangled state
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Levinson's theorem for graphs II

Cited by in corpus (4)

• Controlling and reversing the transition from classical diffusive to quantum ballistic transport in a quantum walk by driving the coin
• Formal languages analysed by quantum walks
• The expressive power of quantum walks in terms of language acceptance
• Quantum Google Algorithm: Construction and Application to Complex Networks