AF: Small: Adiabatic Quantum Optimization, NP-Completeness and Anderson Localization

AF：小：绝热量子优化、NP 完备性和安德森定位

• 批准号: 1017244
• 负责人: Boris Altshuler
• 金额: $ 43.73万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017244&HistoricalAwards=false
• 关键词: AF; Small; Adiabatic; Quantum; Optimization

The main objective of the project is to study the fundamental limits and possible modifications of the Adiabatic Quantum Optimization approach to the NP-complete computational problems. PI plans to use the connection of the Adiabatic Quantum Optimization with the theory of Anderson Localization, more precisely its recent extension to the Many-Body problems of Condensed Matter Physics and Statistical Mechanics. By applying techniques used in the Quantum Physics of Complex Systems, PI plans to analyze in details the distribution of small spectral gaps and their effect on the efficiency of the Adiabatic Quantum algorithms for various problems. The connection with the localization implies that the loss of the adiabaticity due to the existence of the exponentially small gaps is likely and the difficulty is fundamental. However, a better understanding of the adiabatic evolution of the complex quantum models, which arise in connection with NP-complete problems, may help to design a modified quantum algorithm that has advantages over known classical algorithms. For example, PI will study possibilities to design quantum algorithms that have advantages over classical heuristics or approximation algorithms, where a local minimum with energy close enough to the global minimum is an acceptable solution. The research under this award is on the edge of Computer Science, Quantum Physics of Complex Systems and Mathematical Physics.

该项目的主要目标是研究绝热量子优化方法对 NP 完全计算问题的基本限制和可能的修改。 PI 计划利用绝热量子优化与安德森局域化理论的联系，更准确地说是其最近对凝聚态物理和统计力学多体问题的扩展。 通过应用复杂系统量子物理中使用的技术，PI 计划详细分析小光谱间隙的分布及其对各种问题的绝热量子算法效率的影响。 与局域化的联系意味着由于指数级小间隙的存在而导致绝热性的损失是可能的，并且困难是根本性的。 然而，更好地理解与 NP 完全问题相关的复杂量子模型的绝热演化，可能有助于设计一种比已知经典算法更具优势的改进量子算法。 例如，PI 将研究设计量子算法的可能性，该算法比经典启发式或近似算法具有优势，其中能量足够接近全局最小值的局部最小值是可接受的解决方案。 该奖项的研究处于计算机科学、复杂系统量子物理和数学物理的边缘。