Collaborative Research: Quantum Monte Carlo Algorithms and Quantum Circuit Complexity

University Of New Mexico, Albuquerque NM

Investigators

Abstract

EIA-0218563 Christopher D. Moore University of New Mexico Collaborative Research: Quantum Mote Carlo Algorithms and Complexity This collaborative project with the University of Connecticut is exploring both new quantum algorithmic techniques and tools for proving impossibility results for quantum computation. Specifically, the focus is on quantum Monte Carlo algorithms, which try to solve problems by doing a random walk in the space of possible solutions. In addition, fundamental limits on the power of quantum computation, developing impossibility results for quantum circuits is being explored and proving that simple generalizations of Shor's factoring algorithm will not work for the Graph Isomorphism problem, which along with Factoring is a likely candidate for a quantum algorithm. Specifically, quantum walks (unitary analogues of stochastic processes) on various combinatorial structures by employing both Fourier analysis for groups and new tools suited for less symmetric Spaces is being studied. Cases where quantum walks explore the space more quickly than their classical counterparts, and other cases where they become localized and mix more slowly than a classical walk are being explored. In addition Fourier analysis to develop lower bounds for shallow quantum circuits and information-theoretic bounds on the process of sampling from the quantum Fourier transform are being studied. In particular, the quantum Fourier transform over non-Abelian groups, and hidden subgroup and hidden subspace problems for such groups is being investigated. This is closely related to Graph Isomorphism, and explore tractable special cases while showing it is hard for a Shor-type algorithm in general.