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

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

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.