Speakers
Description
We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm utilizing coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a Pauli Hamiltonian $H$ and any degree-$\ell$ polynomial $\mathcal{P}$, HDQI prepares a purification of $\rho_{\mathcal{P}}(H) = \mathcal{P}^2(H)/\operatorname{Tr}[\mathcal{P}^2(H)]$ by solving two tasks: decoding $\ell$ errors on a classical code defined by $H$, and preparing a pilot state that encodes the anti-commutation structure of $H$. Choosing $\mathcal{P}(x)$ to approximate $\exp(-\beta x/2)$ yields Gibbs states at inverse temperature $\beta$; other choices of $\mathcal{P}$ prepare approximate ground states, microcanonical ensembles, and other spectral filters.
The decoding problem inherits structural properties of $H$, e.g. local Hamiltonians map to LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for Pauli Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size.
HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians—including the toric code, color code, and Haah's cubic code—but we also develop a matching efficient classical algorithm for this task, thereby delineating the boundary of efficient classical simulation. For a non-commuting semiclassical spin glass and commuting stabilizer Hamiltonians with quantum defects, HDQI provably efficiently prepares Gibbs states up to a constant inverse-temperature. These results position HDQI as a versatile new algorithmic primitive and the first extension of Regev’s reduction to non-abelian groups.
| Topic | Hybrid quantum-classical approaches for learning and optimization |
|---|