Anirban Narayan Chowdhury

We present algorithms to evaluate partition functions of quantum Hamiltonians using mixed-state quantum computation, specifically the DQC1 model of computation which requires only one pure qubit. Our algorithm provides an additive-error estimate to the normalized partition function in time that is polynomial in the number of qubits, for a large class of Hamiltonians. This implies that a variant of the partition function problem, that was previously shown to be hard for the complexity class DQC1 by Brandao, is in fact DQC1-complete. Our algorithm is based on approximations of the exponential operator as linear combinations of unitaries, which are related to block-encoding of Hamiltonians or Hamiltonian evolutions. We then extend our results to give an algorithm that estimates the partition function within a desired relative error. Towards this end, we develop a procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.

Flow models are a cornerstone of modern machine learning. They are generative models that progressively transform probability distributions according to learned dynamics. Specifically, they learn a continuous-time Markov process that efficiently maps samples from a simple source distribution into samples from a complex target distribution. We show that these models are naturally related to the Schrödinger equation, for an unusual Hamiltonian on continuous variables. Moreover, we prove that the dynamics generated by this Hamiltonian can be efficiently simulated on a quantum computer. Together, these results give a quantum algorithm for preparing coherent encodings (a.k.a., qsamples) for a vast family of probability distributions—namely, those expressible by flow models—by reducing the task to an existing classical learning problem, plus Hamiltonian simulation. For statistical problems defined by flow models, such as mean estimation and property testing, this enables the use of quantum algorithms tailored to qsamples, which may offer advantages over classical algorithms based only on samples from a flow model. More broadly, these results reveal a close connection between state-of-the-art machine learning models, such as flow matching and diffusion models, and one of the main expected capabilities of quantum computers: simulating quantum dynamics.