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.

Recently, a quantum algorithm called Decoded Quantum Interferometry (DQI) was introduced that achieves an apparent exponential speedup for Optimal Polynomial Intersection (OPI) problem, which has previously been studied in the contexts of cryptography and error correcting codes. However, this left open the question of how many logical gates and logical qubits would be needed to solve a classically intractable instance of OPI. Here, we develop optimized implementations of DQI which greatly reduce its resource requirements. We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal asymptotic speedup: solving instances with classical hardness $O(2^N)$ requires only $\widetilde{O}(N)$ quantum gates, matching the theoretical lower bound. To realize this, we overcome the primary bottleneck of reversible Reed-Solomon decoding by introducing novel quantum circuits for the Extended Euclidean Algorithm (EEA) that reduce the leading-order space complexity to the theoretical minimum of $2nb$ qubits. These improvements are broadly applicable, including to Shor's algorithm for the discrete logarithm. We analyze OPI over binary extension fields $\GF(2^b)$, assess hardness against new classical attacks, and identify resilient instances. Our resource estimates show that classically intractable OPI instances (requiring $>10^{23}$ classical trials) can be solved with approximately 5.72 million Toffoli gates. This is roughly $1000$ times fewer gates than required for factoring RSA-2048 and, remarkably, is also less than the leading interactive protocol for computational proof of quantumness, positioning DQI as a compelling candidate for practical, verifiable quantum advantage.

We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of SU(n), where n>=2 is constant. For dimension N and error eps, the number of quantum gates in our circuits is polynomial in log(N) and log(1/eps). Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of SU(n) in the Hilbert space of n quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.

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.