Zoe Holmes

Generalization bounds are a critical tool to assess the training data requirements of Quantum Machine Learning (QML). In this work, we prove the first out-of-distribution generalization guarantees in QML, where we require a trained model to perform well even on testing data drawn from a distribution different from the training data distribution. Namely, we establish out-of-distribution generalization for the task of learning an unknown unitary using a quantum neural network and for a broad class of training and testing distributions. In particular, we show that one can learn the action of a unitary on entangled states using only product state training data. Since product states can be prepared using only single-qubit gates, this advances the near-term prospects of QML for learning quantum dynamics, and further opens up new methods for both the classical and quantum compilation of quantum circuits. Based on these insights, we propose a QML-based algorithm for simulating quantum dynamics on near-term quantum hardware and rigorously prove its resource-efficiency in terms of qubit and training data requirements. We also demonstrate the viability of this algorithm through numerical experiments, both in classical simulations and on quantum hardware. Finally, we embed this algorithm in a broader framework for using QML methods for quantum dynamical simulation on NISQ devices.

We reveal the power of Grover’s algorithm from thermodynamic and geometric perspectives by showing that it is a product formula approximation of imaginary-time evolution (ITE), a Riemannian gradient flow on the special unitary group. This viewpoint uncovers three key insights. First, we show that the ITE dynamics trace the shortest path between the initial and the solution states in complex projective space. Second, we prove that the geodesic length of ITE determines the query complexity of Grover’s algorithm. This complexity notably aligns with the known optimal scaling for unstructured search. Lastly, utilizing the geodesic structure of ITE, we construct a quantum signal processing formulation for ITE without post-selection, and derive a new set of angles for the fixed-point search. These results collectively establish a deeper understanding of Grover's algorithm and suggest a potential role for thermodynamics and geometry in quantum algorithm design.

Quantum Signal Processing (QSP), a framework for implementing matrix-valued polynomials, is a fundamental primitive in various quantum algorithms. Despite its versatility, a potentially underappreciated challenge is that all systematic protocols for implementing QSP rely on post-selection. This can impose prohibitive costs for tasks when amplitude amplification cannot sufficiently improve the success probability. For example, in the context of ground-state preparation, this occurs when using a too poor initial state. In this work, we introduce a new formula for implementing QSP transformations of Hermitian matrices, which requires neither auxiliary qubits nor post-selection. Rather, using approximation to the exact unitary synthesis, we leverage the theory of the double-bracket quantum algorithms to provide a new quantum algorithm for QSP, termed Double-Bracket QSP (DB-QSP). The algorithm requires the energy and energetic variance of the state to be measured at each step and has a recursive structure, which leads to circuit depths that can grow super exponentially with the degree of the polynomial. With these strengths and caveats in mind, DB-QSP should be viewed as complementing the established QSP toolkit. In particular, DB-QSP can deterministically implement low-degree polynomials to "warm start" QSP methods involving post-selection.

A central challenge in quantum many-body physics is to understand how operators evolve in time. Key phenomena like operator growth, transport, and scrambling are most naturally framed in the Heisenberg picture, but classical approaches (e.g., tensor networks or Pauli propagation) run into limits set by entanglement or magic. In the first paper of this joint submission, we develop a general Heisenberg-picture simulation framework for quantum computers based on vectorization and transfer-matrix ideas. This lets us represent time-evolved Heisenberg operators as quantum states in a structure-preserving way, so a wide range of Heisenberg-native tasks can be recast as standard state-based procedures. As a result, we obtain new quantum algorithms for computing many operator diagnostics, including Pauli statistics, OTOCs, superoperator moments, two-point correlators, and operator entanglement/stabilizer entanglement measures. In the second paper, we target the problem of learning many correlators simultaneously. We introduce “shadows of Heisenberg operators,” obtained via randomized measurements with local or global Clifford schemes, enabling simultaneous estimation of broad families of OTOCs or two-point correlators from shared data. We also prove information-theoretic lower bounds for multi-OTOC estimation across different learning models, yielding exponential separations that formalize when and why the vectorized approach provides genuine measurement-efficiency advantages.

In the quest for quantum advantage, a central question is under what conditions can classical algorithms achieve a performance comparable to quantum algorithms--a concept known as dequantization. Random Fourier features (RFFs) have demonstrated potential for dequantizing certain quantum neural networks (QNNs) applied to regression tasks, but their applicability to other learning problems and architectures remains unexplored. In this work, we derive bounds on the true risk gap between classical RFF models and quantum models for regression and classification tasks with both QNN and quantum kernel architectures. Furthermore, we provide sufficient conditions under which this gap is small and thus the quantum system can be dequantized via the RFF method. We support our findings with numerical experiments that illustrate the practical dequantization of existing quantum kernel-based methods. Our findings not only broaden the applicability of RFF-dequantization but also enhance the understanding of potential quantum advantages in practical machine-learning tasks.

Analyzing the impact of noise is of fundamental importance to understand the advantages provided by quantum systems. While the classical simulability of noisy discrete-variable systems is increasingly well understood, noisy bosonic circuits are more challenging to simulate and analyze. Here, we address this gap by introducing the displacement propagation algorithm, a continuous-variable analogue of Pauli propagation for simulating noisy bosonic circuits. By exploring the interplay of noise and quantum resources, we identify several computational phase transitions, revealing regimes where even modest noise levels render bosonic circuits efficiently classically simulable. In particular, our analysis reveals a surprising phenomenon: computational resources usually associated with bosonic quantum advantage, namely non-Gaussianity and symplectic coherence, can make the system easier to classically simulate in presence of noise.

Variational quantum algorithms are limited in practice by the barren plateau (BP) problem, where cost function gradients vanish exponentially with system size. We show that Quantum Signal Processing (QSP) provides a structured variational ansatz that is provably BP-free in a region around the all-zero initialization, for a broad class of observables with eigenvalues bounded away from zero. The BP-free region is an ellipsoid in parameter space characterized precisely via the connection to symmetric QSP and the energy landscape results of Wang, Dong, and Lin (arXiv:2110.04993v2). Contrary to the conjecture of Cerezo et al. (arXiv:2312.09121v2) that BP-free cost functions are classically simulable, we show that the cost functions of general QSP ansatze are classically hard. Finally, we show that the optimization over QSP phases can be reduced to a convex quadratic program over Chebyshev coefficients, solvable classically using measurements on unparametrized quantum circuits. These results establish QSP as a theoretically principled variational ansatz that is simultaneously trainable, classically hard, and efficiently optimizable, opening near-term applications in quantum simulation and sensing.