Hsin-Yuan Huang

Haar-random unitaries are fundamental mathematical tools for understanding quantum many-body dynamics, yet they fail to obey basic physical constraints imposed by Hamiltonians. In this work, we explore how to reconcile random unitary models with physical constraints imposed by Hamiltonians, addressing the central question: Can we efficiently generate random unitaries while obeying Hamiltonian constraints? First, we consider the role of energy conservation in the setting where the Hamiltonian $H$ is completely known. There, we show that energy-conserving pseudorandom unitaries (PRUs) exist for random local commuting Hamiltonians, assuming quantum-secure one-way functions exist. However, we also prove that energy-conserving PRUs do not exist for some local translation-invariant Hamiltonians, even in one-dimensional systems. Furthermore, we show that determining whether energy-conserving PRUs exist for a family of Hamiltonians is undecidable. Second, we consider Hamiltonian time dynamics itself when there is incomplete knowledge of $H$. In this setting, we prove that random unitaries $e^{-iHt}$ generated from any ensemble of constant-local Hamiltonians $H$ cannot form approximate unitary designs or PRUs. This barrier vanishes when we relax locality: we construct an ensemble of polylog-local Hamiltonians $H$ that generates short-time dynamics which form both a unitary design and a PRU. Our results reveal fundamental computational barriers emerging from energy conservation constraints, highlighting the tension between common models of ergodicity and the structure of physical dynamics.

We prove that recognizing the phase of matter of an unknown quantum state is quantum computationally hard. More specifically, we show that the worst-case runtime of any phase recognition algorithm must grow exponentially in the correlation length $\xi$ of the state. This exponential growth renders the problem practically infeasible even for moderate constant values of the correlation length $\xi$, and leads to super-polynomial quantum computational time in the system size $n$ whenever $\xi = \omega(\log n)$. Our results apply to a substantial portion of all known phases of matter, including symmetry-breaking phases and symmetry-protected topological phases for any discrete on-site symmetry group in any spatial dimension. To establish this hardness, we extend the study of pseudorandom unitaries to quantum systems with symmetries. We prove that symmetric pseudorandom unitaries exist under standard cryptographic conjectures, and can be constructed in extremely low circuit depths for any discrete on-site group. We also provide extensions of our results to systems with translation invariance and purely classical phases of matter. A key technical limitation is that the locality of the parent Hamiltonian of the states we consider is linear in $\xi$; removing this constraint remains an important open question.

Understanding how fast physical systems can resemble Haar-random unitaries is a fundamental question in physics. Many experiments of interest in quantum gravity and many-body physics, including the butterfly effect in quantum information scrambling and the Hayden-Preskill thought experiment, involve queries to a random unitary~$U$ alongside its inverse~$U^\dagger$, conjugate~$U^*$, and transpose~$U^T$. However, conventional notions of approximate unitary designs and pseudorandom unitaries (PRUs) fail to capture these experiments. In this work, we introduce and construct strong unitary designs and strong PRUs that remain robust under all such queries. Our constructions achieve the optimal circuit depth of $\mathcal{O}(\log n)$ for systems of $n$ qubits. We further show that strong unitary designs can form in circuit depth $\mathcal{O}(\log^2 n)$ in circuits composed of independent two-qubit Haar-random gates, and that strong PRUs can form in circuit depth $\poly(\log n)$ in circuits with no ancilla qubits. Our results provide an operational proof of the fast scrambling conjecture from black hole physics: every observable feature of the fastest scrambling quantum systems reproduces Haar-random behavior at logarithmic times.

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.

Abstract Machine learning (ML) provides the potential to solve challenging quantum many-body problems in physics and chemistry. Yet, this prospect has not been fully justified. In this work, we establish rigorous results to understand the power of classical ML and the potential for quantum advantage in an important example application: predicting outcomes of quantum mechanical processes. We prove that for achieving a small average prediction error, one can always design a classical ML model whose sample complexity is comparable to the best quantum ML model (up to a small polynomial factor). Regarding computational complexity, we show that the class of problems that can be solved by efficient classical ML models with access to sampled data is strictly larger than BPP. Hence, classical ML models may be able to solve some challenging quantum problems after training from data obtained in physical experiments. As a concrete example, we prove that a simple, classical ML model can efficiently learn to predict ground state representations that approximate expectation values of local observables up to a small, constant error. This holds for any smooth family of gapped local Hamiltonians in a finite spatial dimension.

Abstract We consider simulating quantum systems on digital quantum computers. We show that the performance of quantum simulation can be improved by simultaneously exploiting the commutativity of Hamiltonian, the sparsity of interactions, and the prior knowledge of initial state. We achieve this using Trotterization for a class of correlated electrons that encompasses various physical systems, including the plane-wave-basis electronic structure and the Fermi-Hubbard model. We estimate the simulation error by taking the transition amplitude of nested commutators of Hamiltonian terms within the $\eta$-electron manifold. We develop multiple techniques for bounding the transition amplitude and the expectation of general fermionic operators, which may be of independent interest. We show that it suffices to use $\cO{\frac{n^{5/3}}{\eta^{2/3}}+n^{4/3}\eta^{2/3}}$ gates to simulate electronic structure in the plane-wave basis with $n$ spin orbitals and $\eta$ electrons up to a negligible factor, improving the best previous result in second quantization while outperforming the first-quantized simulation when $\eta=\Om{\sqrt{n}}$. We also obtain an improvement for simulating the Fermi-Hubbard model. We construct concrete examples for which our bounds are almost saturated, giving a nearly tight Trotterization of correlated electrons.