IQIM Postdoctoral and Graduate Student Seminar
Note: IQIM seminar will be held in the Ginsburg seminar room.
Abstract: Which problems can quantum computers solve faster than classical ones, and what structure enables this? Decoded Quantum Interferometry (DQI) [1] offers one answer: a quantum algorithm that reduces classical optimization to classical decoding, so that an efficient decoding algorithm turns into an efficient quantum algorithm for optimization. In this talk I will explain how the ideas behind DQI generalize to preparing thermal states and approximate ground states of quantum Hamiltonians. This result extends the recently developed Hamiltonian DQI [2] to the general noncommuting setting [3].
Our approach splits the hardness of general quantum Hamiltonians into two separate sources. One source is redundancies: products of terms in the Hamiltonian that multiply to the identity. These form a classical code. The other is anticommutation, which survives even in a "redundancy-free" relaxation of the Hamiltonian, with the same anticommutation graph but no redundancies. We show that preparing the Gibbs state of a general Hamiltonian reduces to classically decoding its redundancies and preparing the thermofield double of its redundancy-free relaxation.
Redundancy-free Hamiltonians turn out to have interesting physical properties of their own. Thermal states stay tractable down to quadratically lower temperatures than for general Hamiltonians. In this regime the partition function is efficiently computable, correlations decay rapidly, and the mutual information obeys a stronger area law, yet the states are still generically entangled. At lower temperatures, anticommutation alone suffices to produce frustration, glassy hysteresis, and complexity-theoretic hardness: approximating the partition function becomes NP-hard, and the ground-state problem is QMA-complete.
Joint work with Matthew B. Hastings
[1] Optimization by decoded quantum interferometry, Nature 646, 831–836 (2025).
[2] Hamiltonian decoded quantum interferometry, arXiv:2510.07913 (2025).
[3] On the complexity of redundancy-free quantum Hamiltonians, arXiv:2610.03697 (2026).
Lunch will be provided on the lawn north of Bridge, following the talk.