DJ Strouse

Project Title: A Levinson’s Theorem for Scattering on Graphs
Advisor:Professor Andrew Childs (Institute for Quantum Computing & University of Waterloo)
Timeline: May 2010 to present

For Grandma*:
    Beginning in the early 20th century, a series of experimental discoveries indicated to physicists that the behavior of tiny objects, like atoms and electrons, is very different from the behavior of everyday objects, such as cars and baseballs. The theory of quantum mechanics that was built to explain these observations allows tiny objects to, in a sense, exist in many places at once (you can read far more about this in Brian Greene’s ‘Fabric of the Cosmos’ or another popular science book on quantum mechanics). Decades later in the 1980s, researchers realized that they could exploit the strange features of quantum mechanics to build “quantum computers” that operated in very different ways from computers currently in use. The usefulness of a quantum computer, however, hinged on the ability of researchers to figure out to exploit the strange features of quantum mechanics to solve interesting computational problems faster than any “classical computer” could. The first such “quantum algorithm” was developed in the 1990s and caused an explosion of research to find more of them.
    During my first years as an undergraduate, I became deeply fascinated with the physical limits of computation and wanted to understand how the laws of physics constrain information processing. After attending a two-week summer school on quantum computing at the Institute for Quantum Computing in Waterloo, Ontario, Canada during summer 2009, I returned during summer 2010 to work with Professor Andrew Childs on a mathematical theorem that we felt might help us or other researchers design new quantum algorithms. Roughly speaking, the theorem relates the number of ways that an atom can “trap” a particle to the behavior of particles that bump into the atom but are not trapped. In other words, by simply assaulting an atom with a series of projectiles, we can understand something about its internal structure without ever getting up close and looking at it. Think of it as a very strange form of echolocation for physicists.
    I gave a lecture on our project (video and slides below) and we also published a research article in the Journal of Mathematical Physics.

For Einstein:
    While quantum computers do possess unique computational capabilities, this potential will remain untapped unless researchers design algorithms that exploit quantum effects to efficiently solve problems of interest to society. During the first half of summer 2010, I spent six weeks at the Institute for Quantum Computing working with Professor Andrew Childs on a mathematical theorem that we felt might aid the design of new quantum algorithms. In particular, we sought the discrete analog of the continuous Levinson’s theorem relating the number of bound states of a potential to the winding of the phase shift of the scattering states. In the discrete case, a potential can be represented as a directed, weighted graph and the scattering trajectories by semi-infinite lines of nodes (“tails”) attached to that graph. The discrete case is not a simple translation of the continuous case, as the discrete case introduces new types of bound states (we called them “confined bound states”) not found in the continuous case, among other complexities. Thus, we sought both the correct statement of the theorem as well as a proof for it. We hope this will enable us to better understand the scattering on graphs paradigm for quantum computing (shown to be universal in Childs 2009).
    Over the summer, we were able to establish a statement and proof for the simple case of attaching one semi-infinite “tail” to the graph, and I gave a colloquium at IQC on our findings (links to video and slides below), and we published a paper in the Journal of Mathematical Physics.
    We have since worked a bit on the generalization of the theorem to the multi-tail case and made enough progress that I am reasonably confident that we or someone else could finish the proof with a few weeks of careful thought. However, we have currently set this project aside to work on other things.

Colloquium video: available for download here
Colloquium slides: available for download here
Paper: arxiv, journal, pdf

*”You do not really understand something unless you can explain it to your grandmother.” – Albert Einstein