EAGER-QIA: Detecting Knottedness with Quantum Computers

EAGER-QIA：使用量子计算机检测打结情况

• 批准号: 2038020
• 负责人: Eric Samperton
• 金额: $ 14.5万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-09-01 至 2023-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2038020&HistoricalAwards=false
• 关键词: EAGER; QIA; Detecting; Knottedness; Quantum

This project will investigate the extent to which quantum computers might solve problems in topology more efficiently than classical computers. Topology is a branch of mathematics that allows one to quantify the properties of a shape that are independent of small deformations of the shape. As such, it has seen numerous scientific applications in subjects where the global behavior of a large collection of objects is more important than individual behavior, from big data to molecular biology. The discovery of novel quantum algorithms for problems in topology could thus advance computer science and topology, as well as enable other scientists to more effectively apply topology in their work. The PI will train both graduate and undergraduate students to assist with this work, and will initiate new cross-disciplinary collaborations to accelerate progress. In the early stages of the project, the PI will work with various student organizations to ensure a diverse pool of trainees is recruited. In the training stage, the PI will prepare a series of videos and notes on the subject of Quantum Complexity and Topology, to be distributed freely for others to use as quantum workforce development resources.Three-dimensional topology is entwined with quantum computing via topological phases of matter, which are quantum condensed matter systems whose physical behavior is described by the topology of knots in three-dimensional spaces. The topological quantum computation paradigm proposes to use such a phase as the physical hardware for a quantum computer. Despite the essential role of knots in this paradigm, there is no known problem about knots that quantum computers can solve more effectively than a classical computer. Broadly, and ambitiously, the goal of this project is to find such a problem. More technically, this project’s goal is to analyze the computational complexity of Khovanov homology using quantum algorithmic methods related to phase estimation and adiabatic quantum computation. Khovanov homology is an invariant that associates a finite-dimensional bi-graded vector space to every knot. This invariant is powerful enough to distinguish many different knots from one another, but it is hard to compute classically because its definition requires working in an exponentially large vector space. The PI has shown how to encode the Khovanov homology of a knot as the ground state space of a linear number of interacting qubits, thus seemingly overcoming the onerous classical space requirements in its definition. However, using this encoding as the basis of a quantum algorithm for computing Khovanov homology requires the derivation of lower bounds on the nonzero energy levels of these qubit systems. The PI will accomplish this with a combination of experimental and pure mathematical methods, using intensive computer calculations of numerous examples to develop conjectures, and applying the well-studied algebraic structures of Khovanov homology (which are related to quantum field theory and enhance the structures of the Jones polynomial via the mathematical process of categorification) to prove rigorous bounds.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.

该项目将研究量子计算机比古典计算机更有效地解决拓扑问题的程度。拓扑是数学的一个分支，它允许人们量化独立于形状的小变形的形状的性质。因此，它已经看到了大量对象的全球行为比个人行为（从大数据到分子生物学）更重要的主题中看到了许多科学应用。因此，发现拓扑问题的新型量子算法可以推进计算机科学和拓扑，并使其他科学家能够在其工作中更有效地应用拓扑。 PI将培训研究生和本科生以协助这项工作，并将开始新的跨学科合作以加速进步。在该项目的早期阶段，PI将与各种学生组织合作，以确保招募有学员的潜水员。 In the training stage, the PI will prepare a series of videos and notes on the subject of Quantum Complexity and Topology, to be distributed freely for others to use as quantum workforce development resources.Three-dimensional topology is entwined with quantum computing via topological phases of matter, which are quantum condensed matter systems whose physical behavior is described by the topology of knots in three-dimensional spaces.拓扑量子计算范式建议使用量子计算机的物理硬件等阶段。尽管结在此范式中的重要作用，但与经典计算机相比，量子计算机可以更有效地解决的结尚无问题。从广义上讲，这个项目的目标是找到这样的问题。从技术上讲，该项目的目标是使用与相位估计和绝热量子计算有关的量子算法方法分析Khovanov同源性的计算复杂性。 Khovanov同源性是一个不变的，它将有限的双学位矢量空间与每个结相关联。这个不变的功能足以区分许多不同的结，但是很难经典地计算，因为它的定义需要在呈指数级的较大的矢量空间中工作。 PI显示了如何将结的Khovanov同源性编码为线性相互作用的量子数的基态空间，因此似乎在其定义中克服了繁重的经典空间要求。但是，将此编码用作计算Khovanov同源性的量子算法的基础，需要在这些Qubit系统的非零能级上推导下限。 PI将使用实验和纯粹的数学方法的结合，使用众多示例的密集计算计算来发展猜测，并运用Khovanov同源性的良好代数结构（与量子场理论相关并增强jones统计范围的统计过程），以使量统计的统计数据进行数学统计信息，以构成量子的结构）使用基金会的智力优点和更广泛的影响标准，认为通过评估被认为是宝贵的支持。