Stephen Jordan

We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that depends logarithmically in both the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast forward the evolution of the quantum harmonic oscillator, which significantly improves over prior art. We apply this Hermite transform to give examples of provable quantum query advantage in property testing and learning. In particular, we show how to efficiently test the property of being close to a low-degree in the Hermite basis when inputs are sampled from the Gaussian distribution, and how to solve a Gaussian analogue of the Goldreich-Levin learning task efficiently. We also comment on other potential uses of this transform to simulating time dynamics of quantum systems in the continuum.

We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a signed Pauli Hamiltonian $H$ and any degree-$\ell$ polynomial $\calP$, HDQI prepares a purification of the density matrix $$\rho_\calP(H) = \calP^2(H)/\Tr[\calP^2(H)]$$ by solving a combination of 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 $\calP(x)$ to approximate $\exp(-\beta x/2)$ yields Gibbs states at inverse temperature $\beta$; other choices of $\calP$ prepare approximate ground states, microcanonical ensembles, and other spectral filters. The decoding problem inherits structural properties of $H$; in particular, 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 a class of nearly commuting Pauli Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. We show that 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 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 code Hamiltonians with quantum defects, HDQI provably prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical preprocessing. These results position HDQI as a versatile new algorithmic primitive, connecting quantum state preparation to classical decoding.

In 1998, Knill and Laflamme proposed that exponential speedups over classical computers could still be possible even if one can only initialize a single qubit into a pure state, with the rest of the qubits in the maximally mixed state. The complexity class thus defined is called DQC1. We show that approximating the Turaev-Viro invariant of a 3-manifold specified as a mapping torus is a complete problem for DQC1. We also use the language of Topological Quantum Field Theories (or TQFTs) to outline the mathematical underpinnings of the relationship between approximating the Jones polynomial of the plat and trace closures, and approximating the Turaev-Viro invariant of Heegaard splittings and mapping tori.