Robert Huang: Quantum advantage in learning and sensing

Quantum technology has the potential to revolutionize how we learn about the physical world. Quantum AI agents with access to the full suite of quantum technology—quantum sensors, quantum memory, and quantum computers—can achieve significant advantages over classical AI agents using conventional technologies. This talk examines our current understanding of these quantum advantages, which has primarily focused on learning many-body quantum systems, exploring both the remarkable capabilities (https://arxiv.org/abs/2112.00778) and fundamental limitations (https://arxiv.org/abs/2407.07754) of quantum agents. To broaden the impact of quantum AI agents, we must extend these capabilities to classical sensing and learning tasks. Specifically, I will present our recent work (https://arxiv.org/abs/2501.07625) developing a quantum computing-enhanced protocol for a fundamental sensing problem: detecting oscillating classical fields. In the strong field and large bandwidth regime, our approach achieves a substantial beyond-quadratic advantage in sensing time. This research illuminates the potential for quantum AI to enhance our learning and sensing capabilities in the classical world.

This talk includes joint work with Michael Broughton, Jarrod McClean, Jordan Cotler, Sitan Chen, Jerry Li, Thomas Schuster, Jonas Haferkamp, Richard Allen, Francisco Machado, Isaac Chuang, and Soonwon Choi.

Laura Mančinska: Quantum reductions for nonlocal games

Gap-preserving reductions are central to classical complexity theory, but their quantum counterparts—especially in the context of multiprover interactive proofs with entangled provers—pose new challenges. In this talk I will discuss a framework for such reductions in the MIP* setting and use it to show that the gapped promise problem for independent set games is MIP*-complete. These games, with constant question size, can be undecidable in the quantum case yet polynomial-time solvable classically. A key technical tool is a new stability theorem that converts almost projective measurements into exact ones.

This talk is baed on a joint work with Pieter Spaas, Taro Spirig, and Matthijs Vernooij.

Anand Natarajan: Succinct arguments for QMA from standard assumptions, without quantum PCPs

In this talk, I will explain how to construct succinct classical interactive arguments for QMA, using only standard cryptographic assumptions (implied by LWE). Our approach builds on Kalai, Lombardi, Vaikuntanathan’s “compiler” to convert a two-prover interactive proof in the MIP* model into a one-prover interactive argument, and achieves succinctness by combining ideas from the MIP* literature with post-quantum succinct arguments of knowledge. Perhaps unexpectedly, our construction does not yield any form of quantum PCP—neither a “Hamiltonian” PCP nor a “games” PCP—in contrast to the situation in the classical world, where PCPs appear to be inherent to succinct arguments for NP.

Based on joint work with Tony Metger and Tina Zhang (2404.19754)

Michael Walter: Nonlocal Games Without Locality: Trading Space for Polynomial Time

Nonlocal games are a foundational tool in quantum computing, but they traditionally require two or more physically separated players. A recent line of work, initiated by Kalai et al. (STOC'23), explores how these games can be played with a single player -- by using quantum cryptography. In this talk, I will introduce this line of research and its motivations, and discuss how by replacing physical separation with computational efficiency, one can force a single device to obey the same rules and ultimate limits that quantum theory imposes in the original nonlocal setting. This provides new insights into quantum complexity and opens the door to powerful new protocols for self-testing and verifying quantum computations.