Quantum Algorithms Based on Physical Processes
Abstract
One promising avenue for the invention of new quantum algorithms is to focus on those that mimic physical processes. Our aim in this project is to identify physical quantum processes that can be reformulated to serve as quantum algorithms, with a particular focus on problems that are of intermediate difficulty in classical computation, including graph isomorphism, which is the problem of determining whether two graphs are related by a relabeling of the vertices. These problems are likely to be in the same class of problem difficulty as factoring, which has proven to be amenable to attack by quantum computers. In this project we are investigating how the dynamical evolutions of different systems of interacting and noninteracting quantum particles can be exploited to attack the graph isomorphism problem. We have shown that seemingly minor changes in the algorithm can significantly affect its effectiveness in distinguishing nonisomorphic graphs, and we have also identified some restrictions on the power of the method when the number of particles in the walk is much less than the number of vertices.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 02, 2013
- Accession Number
- ADA608050
Entities
People
- Eric Bach
- Mark Friesen
- Robert Joynt
- Susan Coppersmith
Organizations
- University of Wisconsin–Madison