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将与各种学生组织合作，以确保招募多样化的学员。 在培训阶段，PI将准备一系列关于量子复杂性和拓扑的视频和笔记，免费分发给其他人作为量子劳动力开发资源。三维拓扑通过物质的拓扑相与量子计算相结合，物质是量子凝聚态系统，其物理行为由三维空间中的结拓扑描述。 拓扑量子计算范式提出使用这样的相位作为量子计算机的物理硬件。 尽管节点在这种范式中起着重要作用，但量子计算机还没有比经典计算机更有效地解决节点问题。 从广义上讲，这个项目的目标是雄心勃勃地找到这样的问题。从技术上讲，该项目的目标是使用与相位估计和绝热量子计算相关的量子算法方法来分析Khovanov同调的计算复杂性。 Khovanov同调是将有限维二阶向量空间与每个纽结相关联的不变量。 这个不变量足够强大，可以区分许多不同的节点，但它很难用经典方法计算，因为它的定义需要在指数级大的向量空间中工作。 PI已经展示了如何将结的Khovanov同调编码为线性数量的相互作用量子比特的基态空间，从而似乎克服了其定义中繁琐的经典空间要求。 然而，使用这种编码作为计算Khovanov同调的量子算法的基础，需要推导出这些量子比特系统的非零能级的下限。 PI将通过实验和纯数学方法的结合来实现这一目标，使用大量例子的密集计算机计算来发展猜想，并应用已被充分研究的Khovanov同调代数结构（与量子场论有关，并通过分类的数学过程增强琼斯多项式的结构）该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。