QnTM: Physically-inspired Quantum Algorithms for NP-intermediate Problems

点击翻译按钮获取中文摘要

This proposal investigates quantum algorithms based on quantum physical processes.The goalis to identify quantum processes that can be reformulated to serve as quantum algorithms,and toidentify the types of errors that can disrupt these processes.The main focus is on NP-intermediateproblems,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 randomwalk process that may be particularly well-suited to solve this problem will be investigated.Sincethe quantum dynamics of many-particle systems can often be e .ciently simulated on quantumcomputers but not on classical computers,understanding the performance of the many-particlerandom walk may yield new insight into inherently quantum algorithms for this problem.Speci .cgraphs known as strongly regular graphs (already shown to be useful to test critically algorithmsproposed for solving graph isomorphism)will be investigated in detail numerically to test themany-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 areaccessible 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 whetherclassical algorithms that depend on the birthday paradox can be used to devise new quantumalgorithms.A complementary research thrust is to analyze the sensitivity of the multi-particle dynamicalalgorithms 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 physicalprocesses that actually occur at the hardware level and use this to improve the e .ciency of quantumcomputations.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 afew hundred vertices.A quantum computer could,however,accurately compute the dynamics ofquantum particles on graphs of this size.If it is possible to use the information so obtained to testisomorphism,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 yieldinto hard computational problems.Further broad impact will be through the training of graduateand undergraduate students with substantial interdisciplinary experience with both computer sci-ence and physics.In addition to web-based dissemination of research results,an interdisciplinaryworkshop will be held that will help improve communication between computer scientists andphysicists working on problems of common interest.