Quantum computers offer the potential to exponentially speed up the solution of certain classically hard computational problems. It is already known, for example, that quantum computers can efficiently factor numbers (something modern computers cannot do), and this fact implies that quantum computers can break the majority of cryptographic systems which protect our nation's cyber-infrastructure. The quantum factoring algorithm is the main motivation behind current research into actually building a quantum computer. In this grant, the investigator proposes a new approach to efficiently solving a computational problem--the graph isomorphism problem--which might also admit an exponential speedup over the best classical algorithm for the problem. The graph isomorphism problem is to tell whether two given graphs (a collection of vertices with edges connecting them) can be made to look identical to each other by permuting the different vertices. The approach taken here is different from that taken by the majority of the quantum algorithms community and centers on a novel class of quantum random walks, those in which the walkers carry topological quantum numbers. This approach follows from a series of failed proposals to graph isomorphism based on random walks by hard-core bosons or fermions and is motivated by the form in which these proposals fail. Finding an efficient quantum algorithm for the graph isomorphism problem would be potentially transformative and would provide a major new justification for building a large quantum computer. The approach chosen by the PI also introduces a novel quantum algorithm technique--quantum random walks by anyons--which has the potential to be useful a primitive outside of the graph isomorphism problem. Finally, the award will be used to support the training of graduate students who work on the boundary between computer science and physics, and thus strengthen connections across this interdisciplinary divide.
Normal 0 false false false EN-US X-NONE X-NONE Research: In the first two years the PI of the grant was Dave Bacon. Bacon worked initially with a grad student to study the spectral properties of quantum walks with anyons. Followup numerical investigations were performed by Bacon and an undergrad student. This was applied to the search for new graph isomorphism algorithms in work by Bacon and two undergraduate students. An important tool in working with anyons was the concept of adiabatically moving a quasiparticle. Bacon went on to investigate applications of this tool with Steve Flammia, who was at the time a postdoc at the Perimeter Institute, along with another UW grad student. In the second year, a new grad student joined the group and worked on state preparation methods for solving graph isomorphism. He also worked on the Weisfeiler-Lehman algorithm, its variants and a possible quantum analogue. This work led to a collaboration with Aram Harrow which found quantum speedups for oracle problems that involve group theory and are inspired by graph isomorphism. In examining the practical side of the resulting quantum algorithms, the grad student also worked on 2-d quantum architectures. Harrow also (together with collaborators from Bristol) worked on highly connected quantum architectures. The following year Dave Bacon left UW and Aram Harrow became PI of the grant. The grad student's work on graph isomorphism led him to work on the problem of group isomorphism. Part of this also involved the PI and grad student working with REU students on empirical evaluation of algorithms for group and graph isomorphism. Two more grad students joined the project and began work on a different application of random walks to quantum computing. They were seeking to understand the performance of quantum Monte Carlo algorithms (which are classical random-walk-based algorithms for simulating quantum systems) as applied to adiabatic quantum algorithms. This work also involved two REU students, one of whom performed numerical experiments on the k-extendable approximation to the set of separable states. Finally in the last half year of the grant, Harrow moved to MIT, and Paul Beame became PI while Harrow remained a co-PI. For more than a year, the grad students were jointly supervised by Beame and/or Harrow. Two grad students remained at UW but have moved to MIT as long-term visitors, while another grad student on the project made plans to transfer to MIT in Fall 2013. During this time the UW grad student further improved his group isomorphism work. Beame, together with two collaborators, worked on determining whether quantum algorithms (particularly those involving random walks) are more efficient with respect to time-space tradeoffs than classical algorithms for exactly computing certain statistical measures such a frequency moments over sliding windows on data. The UW/MIT grad student also worked on algorithms for the group extension equivalence problem. Results: Our work produced the new paradigm of adiabatic one-way quantum computing, which encompasses adiabatic gate teleportation and the quantum transistor. This has been published in Physics Review X, Physics Review A, and Physics Review Letters. Our architecture work led to general-purpose speedups and the first polylog-depth 2-d implementation of Shor's algorithm. It has been published in the Proceedings of TQC and the Proceedings of the Royal Society. Our group isomorphism work developed the first polynomial speedup of the problem in 40 years. The work on group extension equivalence also developed several new exponential quantum speedups for natural problems (based on computational assumptions). The results have been published on the arxiv, presented at conferences, mentioned on the two of the PI's Quantum Pontiff blog, and published in major journals. Impacts: The project involved several undergraduate and graduate students in research with mentoring of graduate students provided by the PIs and mentoring of undergraduates provided by both the PIs and the graduate students on the project, which also provided the graduate students with important experience in guiding others. The project team also supervised a local high school student in a project concerning adiabatic quantum computing. Several undergraduate and graduate students were trained in cutting-edge research. These include major portions of the doctorial research of multiple graduate students who have received their Masters degree, PhD candidacy, and PhD degree. A major new computational model was developed for quantum computing (adiabatic gates), which is likely to have widespread application. For example, followup work has already obtained preliminary results in applying them to constructing new quantum error-correcting codes. The deterministic collision-detection techniques used for group isomorphism are likely to be a widely useful algorithmic primitive.
