EAGER-QIA: Detecting Knottedness with Quantum Computers

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

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.