Posted

Liang Mao, Laura Cui, Thomas Schuster, Hsin-Yuan Huang (Oct 10 2025).
Abstract: Random unitaries sampled from the Haar measure serve as fundamental models for generic quantum many-body dynamics. Under standard cryptographic assumptions, recent works have constructed polynomial-size quantum circuits that are computationally indistinguishable from Haar-random unitaries, establishing the concept of pseudorandom unitaries (PRUs). While PRUs have found broad implications in many-body physics, they fail to capture the energy conservation that governs physical systems. In this work, we investigate the computational complexity of generating PRUs that conserve energy under a fixed and known Hamiltonian HH. We provide an efficient construction of energy-conserving PRUs when HH is local and commuting with random coefficients. Conversely, we prove that for certain translationally invariant one-dimensional HH, there exists an efficient quantum algorithm that can distinguish truly random energy-conserving unitaries from any polynomial-size quantum circuit. This establishes that energy-conserving PRUs cannot exist for these Hamiltonians. Furthermore, we prove that determining whether energy-conserving PRUs exist for a given family of one-dimensional local Hamiltonians is an undecidable problem. Our results reveal an unexpected computational barrier that fundamentally separates the generation of generic random unitaries from those obeying the basic physical constraint of energy conservation.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!