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

QnTM：针对 NP 中间问题的物理启发量子算法

• 批准号: 0523680
• 负责人: ROBERT JOYNT
• 金额: $ 30万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-15 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0523680&HistoricalAwards=false
• 关键词: QnTM; Physically; inspired; Quantum; Algorithms

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.

该方案研究基于量子物理过程的量子算法。目标是识别可以被重新表述为量子算法的量子过程，并识别可能扰乱这些过程的错误的类型。主要关注NP中介问题，即NP中既不是NP完全的问题，也不是P中的问题。本研究的一个主要重点是研究图的同构，一个NP中间问题，是复杂性理论中的一个中心问题。我们将研究一种特别适合于解决这一问题的多粒子随机游走过程。由于多粒子系统的量子动力学通常可以在量子计算机上模拟，而不是在经典计算机上，了解多粒子随机游走的性能可能会使我们对这一问题的内在量子算法有新的见解。我们将详细地研究被称为强正则图的特殊图(已被证明有助于测试提出的用于解决图同构的关键算法)，以测试任意粒子量子随机游走算法，并充分刻画其复杂性。此外，本文还对多粒子随机游走算法进行了研究我们将通过刻画量子计算机可访问的代数图形不变量来取得进展。还将研究其他相关问题和方法，包括整数因式分解、离散对数和在格子中定义短向量。还将研究依赖于生日悖论的经典算法是否可以设计新的量子算法。作为补充的研究重点是分析多粒子动态算法对误差的敏感性，特别是随着粒子数量的增加误差的比例，了解算法使用的物理过程与实际发生在硬件级别的物理过程之间的联系，并利用此来提高量子计算的效率。本研究的目的是将计算的范围扩展到定性的新问题。例如，目前人们不能可靠地测试具有数百个以上顶点的图的同构。然而，量子计算机可以准确地计算这种尺寸的图上的量子粒子的动力学。如果可以使用所获得的信息来验证同态，这将是在克服复杂问题方面迈出的重要一步。更广泛的影响。拟议的工作将产生广泛的影响，因为它将产生对困难计算问题的洞察。更广泛的影响将通过培训在计算机科学和物理方面具有丰富跨学科经验的研究生和本科生来实现。除了以网络为基础的研究成果的传播之外，还将举办一个跨学科的研讨会，以帮助加强计算机科学家和从事共同感兴趣问题的物理学家之间的交流。