Vishnu Iyer

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.

The field of quantum learning theory has advanced rapidly in recent years, at the intersection of quantum information science, statistical learning, and computational complexity. A key task in this area is quantum process tomography, which seeks to learn unitary transformations of quantum states efficiently. Efficient process tomography would be highly valuable: for instance, learning an unknown natural process could enable its efficient implementation and simulation on a quantum computer. However, learning arbitrary unitary operators is generally prohibitively expensive, with several sample- and time-complexity lower bounds showing the task is intractable. Thus, work typically focuses on more structured classes of operators when computational efficiency is desired. Two especially important such classes are bosonic and fermionic Gaussian unitaries. These operators have compact parametrizations, rich algebraic structure, and enough expressiveness to capture many relevant physical processes. As a result, they are ubiquitous in quantum information theory. In this work, we advance the learning theory of bosonic and fermionic unitaries in two ways: (1) We give the first time-efficient algorithm to learn bosonic Gaussian unitaries. The complexity of the algorithm scales polynomially in the number of modes, a total photon number bound (which is critical in defining an energy-constrained distance measure), and a squeezing parameter which captures how much the operator increases the mean energy of a vacuum state. (2) We give a first-of-its-kind algorithm to learn fermionic unitaries prepared with at most t non-Gaussian gates. Our algorithm scales polynomially in the number of modes and exponentially in t, and we argue that this scaling is optimal up to polynomial factors. Both algorithms produce an output whose distance to the input unitary is small in the worst-case (diamond) distance. Our results are organized into two separate manuscripts: one is arXiv:2504.11318 (Mildly-Interacting Fermionic Unitaries are Efficiently Learnable), and the other will be released on arXiv within a month (Efficient Learning of Bosonic Gaussian Unitary Channels).

We show that any pseudoentangled state ensemble with a gap of t bits of entropy requires Ω(t) non-Clifford gates to prepare. This bound is tight up to polylogarithmic factors if linear-time quantum-secure pseudorandom functions exist. Our result follows from a polynomial-time algorithm to estimate the entanglement entropy of a quantum state across any cut of qubits. When run on an n-qubit state that is stabilized by at least 2^n−t Pauli operators, our algorithm produces an estimate that is within an additive factor of t/2 bits of the true entanglement entropy.