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

本文研究了基于量子物理过程的量子算法。目标是识别可以重新表述为量子算法的量子过程，并识别可能破坏这些过程的错误类型。主要关注NP-中间问题，即NP中既不是NP-完全也不是P.智力价值的问题。本研究的一个主要焦点是图同构的研究，一个NP-中间问题是复杂性理论中的一个中心问题，一个可能特别适合于解决这个问题的多粒子随机行走过程将被研究，由于多粒子系统的量子动力学通常可以在量子计算机上而不是在经典计算机上有效地模拟，理解多粒子随机行走的性能可能会对这个问题的内在量子算法产生新的见解。（已经被证明是有用的测试critically算法提出解决图同构）将详细研究数值测试的任何粒子量子随机行走算法，并充分表征其复杂性。此外，本论文的一项工作将是通过描述量子计算机可访问的代数图不变量来取得进展。2其他相关的问题和方法也将被研究，包括整数因子分解，离散对数，本文还将研究依赖于生日悖论的经典算法是否可以用来设计新的量子算法。一个补充的研究重点是分析多粒子动力学算法对误差的敏感性，特别关注随着粒子数量的增加误差的缩放，并理解算法所利用的物理过程与实际发生在硬件级别的物理过程之间的联系，并利用这一点来提高量子计算的效率。本研究的目标是扩展量子计算的极限。计算定性的新问题。例如，目前人们不能可靠地测试具有超过几百个顶点的图的同构。然而，量子计算机可以精确地计算这种大小的图上的量子粒子的动力学。如果可以使用这样获得的信息来测试同构，这将是在征服复杂问题方面向前迈出的重要一步。更广泛的影响。拟议的工作将产生广泛的影响，因为它将产生难以计算的问题。更广泛的影响将通过培训具有计算机科学和物理学跨学科经验的研究生和本科生。除了基于网络的研究成果传播外，还将举办跨学科研讨会，以帮助改善计算机科学家和物理学家之间就共同感兴趣的问题进行的沟通。

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.