Quantum Walks and Cellular Automata for Quantum Information Processing

Quantum field theories underlie our deepest theories of nature, including the standard model of particle physics and its extensions. These theories unite quantum mechanics and special relativity, and have been very successful in understanding fundamental physics. However, they have many mathematical challenges and open questions that make them hard to solve in closed form, and they can also be very difficult to simulate with computers. This proposed research explores an intriguing relationship between quantum walks and relativistic quantum equations (like the Dirac equation), which suggests that quantum field theories may arise as low-energy limits of models called quantum cellular automata, giving a different approach to deriving quantum field theories. This relationship raises many very interesting questions. This project will provide topics for Ph.D. research for graduate students, and play a role in developing the research community, and courses in quantum information processing, at USC. The PI will develop educational materials for undergraduates and a master's degree program in Quantum Information Science which aims to serve the growing number of companies working on quantum computers. Quantum walks are quantum-mechanical analogues of classical random walks. In random walks, particles move in discrete steps along the edges of graphs, choosing randomly which edge to take at each step. Quantum walks have a similar mathematical description, but instead of moving randomly they can make superpositions of different moves, with each step being a unitary transformation. This difference leads to dramatically different behavior than random walks, with interference effects, wave-like propagation and a rich array of other quantum phenomena. Quantum walks have connections to quantum algorithms, such as search and element distinctness; they also form models for fundamental physical systems. Quantum cellular automata are a natural many-body generalization of quantum walks, where the vertices of the graph become localized quantum systems, evolving in discrete time steps by interacting locally with neighboring sites. This project will explore several aspects of quantum walks and quantum cellular automata: as discrete models of relativistic quantum wave functions and quantum field theories; potential applications to simulations on quantum computers (which can simulate quantum walks and quantum cellular automata efficiently); how continuous symmetries such as rotational symmetry and Lorentz invariance can arise as a limit of a discrete theory; the tension between local evolution, Fermi statistics, and positive energies; and multiparticle quantum walks as an alternative model of quantum computation. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.