EAGER-QIA: Detecting Knottedness with Quantum Computers

这个项目将调查量子计算机可能在多大程度上比经典计算机更有效地解决拓扑学问题。拓扑学是数学的一个分支，它允许人们量化形状的属性，这些属性独立于形状的小变形。因此，它在从大数据到分子生物学的大量对象的全局行为比个人行为更重要的学科中看到了许多科学应用。拓扑学中新的量子算法的发现可以促进计算机科学和拓扑学的发展，并使其他科学家能够更有效地将拓扑学应用到他们的工作中。PI将培训研究生和本科生协助这项工作，并将启动新的跨学科合作以加快进展。在该项目的早期阶段，PI将与各种学生组织合作，以确保招募到不同的受训者。在培训阶段，PI将准备一系列关于量子复杂性和拓扑学主题的视频和笔记，供其他人免费分发作为量子劳动力发展资源。三维拓扑通过物质的拓扑相与量子计算缠绕在一起，物质的拓扑相是量子凝聚态物质系统，其物理行为通过三维空间中的节点拓扑来描述。拓扑量子计算范式建议使用这样的阶段作为量子计算机的物理硬件。尽管结在这一范式中扮演着重要的角色，但关于结的已知问题，量子计算机可以比经典计算机更有效地解决。广泛而雄心勃勃的这个项目的目标就是找到这样一个问题。更严格地说，这个项目的目标是使用与相位估计和绝热量子计算相关的量子算法方法来分析Khovanov同调的计算复杂性。Khovanov同调是一个不变量，它将有限维二次向量空间与每个纽结联系在一起。这个不变量足够强大，足以区分许多不同的结，但它很难进行经典计算，因为它的定义需要在指数级大的向量空间中工作。PI已经展示了如何将纽结的Khovanov同调编码为线性数量的相互作用量子比特的基态空间，从而似乎克服了其定义中繁琐的经典空间要求。然而，使用这种编码作为计算Khovanov同调的量子算法的基础，需要推导出这些量子比特系统的非零能级的下界。PI将通过实验和纯数学方法的结合来实现这一点，使用大量例子的密集计算机计算来开发猜想，并应用Khovanov同调的精心研究的代数结构(与量子场论相关，并通过分类的数学过程增强Jones多项式的结构)来证明严格的界限。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.