权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: Quantum Optimization, Glassiness and Localization

职业：量子优化、玻璃性和局部化

基本信息

批准号：
1752727
负责人：
Christopher Laumann
金额：
$ 50万
依托单位：
Trustees of Boston University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-08-01 至 2023-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1752727&HistoricalAwards=false
关键词：
CAREER Quantum Optimization Glassiness Localization

项目摘要

The theoretical discovery of quantum search algorithms demonstrated that quantum computers could significantly outperform classical ones. For example, the quantum Grover algorithm can find a marked item in a completely unordered list -- the proverbial needle in a haystack -- provably faster than any classical algorithm. Practical search problems, however, typically have more structure than existing quantum algorithms exploit. It is an outstanding open question exactly where speed ups can be found, and where they will be unachievable. This research aims to address these questions by drawing inspiration from the physics of disordered systems, where there are many known structural mechanisms which produce slow, or 'glassy', dynamics. The project further aims to elucidate the physical consequences of one of the most dramatic quantum mechanisms for slow dynamics: many-body localization (MBL). Although first postulated over 50 years ago, this mechanism has only recently come into sharp theoretical and experimental focus as large-scale isolated quantum systems such as ultracold atoms, ion traps, and superconducting qubit arrays have been built. It is particularly intriguing as localization prevents the emergence of classical behavior. From an quantum algorithmic point of view, the role localization plays is thus unclear. On the one hand, it leads to very slow dynamics and presumably very slow search behavior. On the other hand, one can only hope to achieve quantum mechanical speed ups in systems which do not behave classically! This suggests that one needs localization to obtain such speed ups. Whether this is true and, if so, how to exploit it are crucial open questions.Thus, this CAREER award supports theoretical research and educational activities on two interrelated foci: 1) the computational complexity, typical structure and algorithmic approaches to quantum optimization problems; and, 2) the phenomenology of many-body localization (MBL) and its role in quantum computation and glassy dynamics. Theoretical methods include the cavity method, random matrix theory, large-N and many-body perturbation theory while numerical approaches include quantum Monte Carlo, the density matrix renormalization group and large scale diagonalization. Specifically, the PI proposes to investigate the phase diagram and transitions, geometrization and clustering of the configuration space in quantum satisfiability and related classical constraint satisfaction problems. The PI expects this study to aid the development of heuristic quantum algorithms for approximate optimization and landscape exploration. Many-body localization (MBL) constitutes a fundamental breakdown of quantum statistical mechanics in the presence of quenched disorder and protects quantum coherence out of equilibrium. The project addresses foundational questions about the theory of the delocalization transition and the influence of disorder versus quasiperiodic modulation, dimensionality and the range of interactions on localization. It also seeks to apply these ideas to understanding the behavior of quantum annealing applied to NP-hard optimization problems.This project is jointly funded by the Quantum Information Science (QIS) Program in the Physics Division in the Mathematical and Physical Sciences Directorate, the Condensed Matter and Materials Theory (CMMT) Program in the Division of Materials Research in the Mathematical and Physical Sciences Directorate, and the Algorithmic Foundations (AF) Program in the Computing and Communications Foundations Division in the Computer and Information Science and Engineering Directorate.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

量子搜索算法的理论发现表明，量子计算机可以大大优于经典计算机。例如，量子Grover算法可以在一个完全无序的列表中找到一个标记项--这就像谚语中的大海捞针--可以证明比任何经典算法都要快。然而，实际的搜索问题通常比现有的量子算法具有更多的结构。这是一个悬而未决的问题，究竟在哪里可以找到加速，以及在哪里无法实现。这项研究旨在通过从无序系统的物理学中汲取灵感来解决这些问题，其中有许多已知的结构机制可以产生缓慢或“玻璃化”的动力学。该项目进一步旨在阐明慢动力学最引人注目的量子机制之一的物理后果：多体局域化（MBL）。虽然在50多年前首次提出，但这种机制直到最近才成为理论和实验的焦点，因为已经建立了大规模孤立量子系统，如超冷原子，离子阱和超导量子比特阵列。这是特别有趣的，因为本地化阻止了经典行为的出现。从量子算法的角度来看，局部化所起的作用是不清楚的。一方面，它导致非常缓慢的动态和可能非常缓慢的搜索行为。另一方面，人们只能希望在不具有经典行为的系统中实现量子力学加速！这表明需要本地化来获得这样的加速。因此，CAREER奖支持两个相互关联的领域的理论研究和教育活动：1）量子优化问题的计算复杂性、典型结构和算法方法; 2）多体局域化（MBL）现象学及其在量子计算和玻璃态动力学中的作用。理论方法包括腔方法，随机矩阵理论，大N和多体微扰理论，而数值方法包括量子Monte Carlo，密度矩阵重整化群和大尺度对角化。具体来说，PI建议调查的相图和过渡，几何化和聚类的配置空间中的量子可满足性和相关的经典约束满足问题。PI希望这项研究有助于开发用于近似优化和景观探索的启发式量子算法。多体局域化（MBL）是量子统计力学在猝灭无序下的一个基本崩溃，它保护了量子相干性。该项目解决了关于离域过渡理论的基本问题，以及无序与准周期调制，维度和相互作用范围对本地化的影响。该项目由数学和物理科学理事会物理部的量子信息科学（QIS）计划、数学和物理科学理事会材料研究部的凝聚态物质和材料理论（CMMT）计划、该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。