This document serves as a summary of the research activities and outcomes of the Long Program, “Mathematical and Computational Challenges in Quantum Computing”.

This program was held at the Institute of Pure and Applied Mathematics (IPAM) from September 11 to December 15, 2023. The program embraced the grand challenge in quantum information science: harness the weirdness of quantum mechanics to yield a computational advantage. Shor’s algorithm, featured by the Green Family Lecture Series during the program, provides an early and (still) striking example of such an advantage. Practical applications of quantum computers also face several major challenges: they can require high ingenuity in preparing, manipulating and reading classical data, and existing quantum devices are prone to high error rates. This program employed deep tools from mathematics, inspired by physical realities, to find algorithmic solutions to challenging applications.

Quantum information science is a multi-disciplinary challenge with broad applications to computing, communication, security, and quantum sensing tasks. According to Scott Aaronson, quantum computation must pass the very high bar of providing provable quantum advantages with a relatively small number of qubits on a noisy device in order to demonstrate its near-term usefulness. The rapid advancement in quantum computing presents unparalleled opportunities for the scientific community. However, fully harnessing the potential of quantum computers to achieve quantum advantage over classical computers is a significant challenge. While it may be tempting to think that exponential quantum speedups can be achieved by using n qubits to encode 2ⁿ bits of classical information, the reality is more subtle, since the quantum algorithm must interact with classical processing systems. Therefore, we need to not only design efficient quantum algorithms using a relatively small number of quantum gates, but also thoughtfully consider input-output models, and the specific requirements of quantum algorithms.

We may dissect the overall quantum cost into three main categories: input, output, and running costs. A quantum algorithm starts with a standard state, which is then transformed by a unitary matrix to prepare the input state. The input cost is the quantum gate complexity required to implement this unitary matrix. The output cost relates to the quantum measurement process, which is performed on one or several qubits often at the end of the algorithm. The output cost is given by the number of repetitions necessary to reach a target precision. The running cost refers to the expense incurred in executing the quantum algorithm a single time. A comprehensive “end-to-end” analysis of quantum advantage requires considering input, output, and running costs.

Assessing the performance of quantum algorithms and identifying potential quantum advantages raises considerable challenges. Rigorous proof of asymptotic quantum advantage over the best-possible classical algorithm, ideally superpolynomial, is a gold standard; however, such proofs are difficult to establish and may be currently beyond reach. An alternative is to compare against the best-known classical algorithm; however, such quantum advantages may vanish under classical algorithmic advances. Empirical assessment of quantum algorithms is a natural strategy in absence of rigorous proofs; however, this may suggest advantages that are not sustainable as problem instances grow in size or complexity.  Moreover, as quantum information science (QIS) is an exemplar interdisciplinary field, methodologies or metrics for performance assessment may be highly domain sensitive. For example, quantum complexity theory seeks to provide insight into the power and limitations of quantum computing from a worst-case asymptotic perspective; however, such a notion may not be appropriate for computing quantities to a practical precision, such as chemical accuracy, for a specific molecule.

Research in quantum computation has to reflect and embrace the challenges imposed by the limitations of existing quantum devices. For example, fault tolerance and quantum error correction are omnipresent in quantum information theory and quantum computation. Over the past fifty years, classical computer gates have observed significant improvements resulting in miniscule errors per gate. In contrast, physical quantum gates are subject to broader sources of error stemming from their quantum-mechanical nature. Errors present a critical challenge for Noisy Intermediate-Scale Quantum (NISQ) devices. However, just as there exist classical error correction codes, which, for example, enable us to smoothly communicate over cell phones, there are quantum analogues called quantum error-correction (QEC) codes that are known to be able to correct errors in quantum computation. Developing and engineering robust and scalable QEC is a paramount challenge for quantum computing.

Nearly optimal QEC rests on deep mathematical insights. Quantum computation also draws inspiration from interactions with other fields. For example, recent theoretical findings suggest that quantum field theory and gravity rely on surprising properties of quantum entanglement and codes. Fundamental problems from condensed matter theory and quantum chemistry present challenges that quantum computation seems well suited to address. Quantum computation has had a profound impact on computational complexity theory, with many previously studied models of computation exhibiting unexpected connections to quantum mechanics. A particularly striking example enabled a recent breakthrough disproving a longstanding conjecture in operator algebras (Connes’ embedding problem) through non-local games and entanglement.

Read the full report.