This proposal investigates quantum algorithms based on quantum physical processes.The goal is to identify quantum processes that can be reformulated to serve as quantum algorithms,and to identify the types of errors that can disrupt these processes.The main focus is on NP-intermediate problems,which are problems in NP that are neither NP-complete nor in P. Intellectual Merit .One main focus of this research is the study of graph isomorphism,an NP- intermediate problem that is a central problem in complexity theory.A many-particle random walk process that may be particularly well-suited to solve this problem will be investigated.Since the quantum dynamics of many-particle systems can often be e .ciently simulated on quantum computers but not on classical computers,understanding the performance of the many-particle random walk may yield new insight into inherently quantum algorithms for this problem.Speci .c graphs known as strongly regular graphs (already shown to be useful to test critically algorithms proposed for solving graph isomorphism)will be investigated in detail numerically to test the many-particle quantum random walk algorithm,and fully characterize its complexity.In addition, an e .ort will be made to make progress by characterizing the algebraic graph invariants that are accessible to quantum computers. Other related problems and methods will also be investigated,including integer factorization, the discrete logarithm,and .nding short vectors in lattices.It will also be investigated whether classical algorithms that depend on the birthday paradox can be used to devise new quantum algorithms. A complementary research thrust is to analyze the sensitivity of the multi-particle dynamical algorithms to errors,focusing speci .cally on the scaling of errors as the number of particles increases, and to understand the connection of the physical processes utilized by the algorithms to the physical processes that actually occur at the hardware level and use this to improve the e .ciency of quantum computations. The goal of this research is to extend the limits of computation to qualitatively new problems. For example,at present one cannot reliably test for the isomorphism of graphs with more than a few hundred vertices.A quantum computer could,however,accurately compute the dynamics of quantum particles on graphs of this size.If it is possible to use the information so obtained to test isomorphism,this would be a signi .cant step forward in conquering complex problems. Broader Impacts .The proposed work will have broad impact because of the insight it will yield into hard computational problems.Further broad impact will be through the training of graduate and undergraduate students with substantial interdisciplinary experience with both computer sci- ence and physics.In addition to web-based dissemination of research results,an interdisciplinary workshop will be held that will help improve communication between computer scientists and physicists working on problems of common interest.
