Physics (Internal)

Continuum limits of Quantum Walks

This event is part of the Preliminary Oral Exam.

Examining Committee: Mark Kon, Alex Sushkov, Chris Laumann, Claudio Rebbi

The quantum analog of a random walk is known as the quantum walk. Just as random walks have been used in computer science, quantum walks have been used in many areas of quantum computing. Quantum walks have been shown to match the Grover’s search algorithm speedup over classical oracle search algorithms, to provide exponential speedup compared to any classical algorithms in various graph traversal problems, and more generally to be universal quantum computational primitives.

Two-state quantum walks exist as canonical discretizations of the Dirac equation, as demonstrated originally by Feynman; these walks can be shown rigorously to recapture the Dirac equation in their continuum limit. Since their original use, much work has been done investigating the properties of continuum limits of quantum walks. The goal of my PhD research is to address the question of whether (or not) quantum scattering can be used as a universal quantum computer, and I plan primarily to approach this problem by connecting theorems about quantum walks and their universality to scattering theory via continuum limits.

In this talk I will present results I have obtained about continuum limits of some quantum walks on the integers which are interesting in their own right, and may also give an entrée into the larger question of continuum limits of walks on graphs. In particular I will give an overview of quantum walks and their relationships to the Dirac and Schrodinger equations, motivation for computational universality of scattering theory, and discuss my various results on continuum limits of quantum walks.