EAGER-QIA: Detecting Knottedness with Quantum Computers

Purdue University, West Lafayette IN

Investigators

Abstract

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.