Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.08434

Random unitaries from Hamiltonian dynamics

Cui, Laura, Thomas Schuster, Mao, Liang, Hsin-Yuan Huang, Fernando G. S. L. Brandão

Published Oct 9, 2025• 0 citations
arXivHTMLPDF

Abstract

The nature of randomness and complexity growth in systems governed by unitary dynamics is a fundamental question in quantum many-body physics. This problem has motivated the study of models such as local random circuits and their convergence to Haar-random unitaries in the long-time limit. However, these models do not correspond to any family of physical time-independent Hamiltonians. In this work, we address this gap by studying the indistinguishability of time-independent Hamiltonian dynamics from truly random unitaries. On one hand, we establish a no-go result showing that for any ensemble of constant-local Hamiltonians and any evolution times, the resulting time-evolution unitary can be efficiently distinguished from Haar-random and fails to form a $2$-design or a pseudorandom unitary (PRU). On the other hand, we prove that this limitation can be overcome by increasing the locality slightly: there exist ensembles of random polylog-local Hamiltonians in one-dimension such that under constant evolution time, the resulting time-evolution unitary is indistinguishable from Haar-random, i.e. it forms both a unitary $k$-design and a PRU. Moreover, these Hamiltonians can be efficiently simulated under standard cryptographic assumptions.

DOI
10.48550/arxiv.2510.08434

Related papers

Random unitaries that conserve energy

Mao, Liang, Lei Cui, Schuster, Thomas +1 more

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 $H$. We provide an efficient construction of energy-conserving PRUs when $H$ is local and commuting with random coefficients. Conversely, we prove that for certain translationally invariant one-dimensional $H$, 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.

arXiv:2510.08448•Oct 9, 2025•0 citations

Random Unitaries in Constant (Quantum) Time

Ben Foxman, Natalie Parham, Francisca Vasconcelos +1 more

Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

Unitary designs from perturbed time evolutions of a chaotic Hamiltonian

Zhongyi Yang, Biao Wu

Unitary designs provide efficient substitutes for Haar-random unitaries in quantum information processing, randomized measurements, and many-body quantum dynamics. We propose a protocol based on time evolutions of a single chaotic Hamiltonian interleaved with unitary perturbations to generate unitary designs. We derive the frame potential of the resulting ensemble in terms of those of the intermediate ensemble. The intermediate ensemble need not itself be Haar random or exhibit Haar-level frame potentials, provided that its trace moments and frame-potential growth are sufficiently suppressed. The nontrivial Pauli set and the Clifford ensemble are simple examples, whereas ensembles whose cardinality does not grow with the Hilbert-space dimension generally fail. We further establish a frame-potential correspondence between multi-Hamiltonian temporal protocols and one-Hamiltonian protocols interleaved with repeated fixed trace-suppressed perturbations, showing that two perturbations suffice to recover Haar-level frame potentials. For local Hamiltonians, we derive a lower bound on the space--depth control resource, while more generally we establish a universal finite-window bound that constrains the required temporal sampling range. Together, these results identify complementary spatial and temporal resource requirements for perturbation-assisted randomness generation.

quant-pharXiv:2607.24851•Jul 28, 2026•0 citations

How to Construct Random Unitaries

Fermi Ma, Hsin-Yuan Huang

The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.

arXiv:2410.10116•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•19 citations

On the pseudorandomness of simple quantum processes

Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba

Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture. Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed $t$, we give an efficiently samplable family $\{ν_n\}_n$ of distributions on one- and two-qubit gates such that, after $T=O_t(n^2\log^2 n)$ independent steps, the resulting $n$-qubit ensemble is an approximate unitary $t$-design with negligible error $\exp(-Ω(\log^2 n))$, yet an efficient quantum algorithm distinguishes it from random using only $O_t(\log^2 n)$ queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations. Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.

quant-pharXiv:2610.02100•Oct 2, 2026•0 citations

Time-periodic dynamics generates pseudo-random unitaries

Tom Farshi, Daniele Toniolo, Carlos E. González-Guillén +2 more

How much does local and time-periodic dynamics resemble a random unitary? In the present work we address this question by using the Clifford formalism from quantum computation. We analyse a Floquet model with disorder, characterised by a family of local, time-periodic, random quantum circuits in one spatial dimension. We observe that the evolution operator enjoys an extra symmetry at times that are a half-integer multiple of the period. With this we prove that after the scrambling time, namely when any initial perturbation has propagated throughout the system, the evolution operator cannot be distinguished from a (Haar) random unitary when all qubits are measured with Pauli operators. This indistinguishability decreases as time goes on, which is in high contrast to the more studied case of (time-dependent) random circuits. We also prove that the evolution of Pauli operators displays a form of ergodicity. These results require the dimension of the local subsystem to be large. In the opposite regime our system displays a novel form of localisation, which can be characterised in terms of one-sided walls.

•Jul 7, 2020•0 citations
The nature of randomness and complexity growth in systems governed by unitary dynamics is a fundamental question in quantum many-body physics. This problem has motivated the study of models such as local random circuits and their convergence to Haar-random unitaries in the long-time limit. However, these models do not correspond to any family of physical time-independent Hamiltonians. In this work, we address this gap by studying the indistinguishability of time-independent Hamiltonian dynamics from truly random unitaries. On one hand, we establish a no-go result showing that for any ensemble of constant-local Hamiltonians and any evolution times, the resulting time-evolution unitary can be efficiently distinguished from Haar-random and fails to form a 222-design or a pseudorandom unitary (PRU). On the other hand, we prove that this limitation can be overcome by increasing the locality slightly: there exist ensembles of random polylog-local Hamiltonians in one-dimension such that under constant evolution time, the resulting time-evolution unitary is indistinguishable from Haar-random, i.e. it forms both a unitary kkk-design and a PRU. Moreover, these Hamiltonians can be efficiently simulated under standard cryptographic assumptions.
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 HHH. We provide an efficient construction of energy-conserving PRUs when HHH is local and commuting with random coefficients. Conversely, we prove that for certain translationally invariant one-dimensional HHH, 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.
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.
Unitary designs provide efficient substitutes for Haar-random unitaries in quantum information processing, randomized measurements, and many-body quantum dynamics. We propose a protocol based on time evolutions of a single chaotic Hamiltonian interleaved with unitary perturbations to generate unitary designs. We derive the frame potential of the resulting ensemble in terms of those of the intermediate ensemble. The intermediate ensemble need not itself be Haar random or exhibit Haar-level frame potentials, provided that its trace moments and frame-potential growth are sufficiently suppressed. The nontrivial Pauli set and the Clifford ensemble are simple examples, whereas ensembles whose cardinality does not grow with the Hilbert-space dimension generally fail. We further establish a frame-potential correspondence between multi-Hamiltonian temporal protocols and one-Hamiltonian protocols interleaved with repeated fixed trace-suppressed perturbations, showing that two perturbations suffice to recover Haar-level frame potentials. For local Hamiltonians, we derive a lower bound on the space--depth control resource, while more generally we establish a universal finite-window bound that constrains the required temporal sampling range. Together, these results identify complementary spatial and temporal resource requirements for perturbation-assisted randomness generation.
The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary UUU, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary UUU and its inverse U†U^\daggerU†. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.
Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture. Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed ttt, we give an efficiently samplable family {νn}n\{ν_n\}_n{νn​}n​ of distributions on one- and two-qubit gates such that, after T=Ot(n2log⁡2n)T=O_t(n^2\log^2 n)T=Ot​(n2log2n) independent steps, the resulting nnn-qubit ensemble is an approximate unitary ttt-design with negligible error exp⁡(−Ω(log⁡2n))\exp(-Ω(\log^2 n))exp(−Ω(log2n)), yet an efficient quantum algorithm distinguishes it from random using only Ot(log⁡2n)O_t(\log^2 n)Ot​(log2n) queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations. Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.
How much does local and time-periodic dynamics resemble a random unitary? In the present work we address this question by using the Clifford formalism from quantum computation. We analyse a Floquet model with disorder, characterised by a family of local, time-periodic, random quantum circuits in one spatial dimension. We observe that the evolution operator enjoys an extra symmetry at times that are a half-integer multiple of the period. With this we prove that after the scrambling time, namely when any initial perturbation has propagated throughout the system, the evolution operator cannot be distinguished from a (Haar) random unitary when all qubits are measured with Pauli operators. This indistinguishability decreases as time goes on, which is in high contrast to the more studied case of (time-dependent) random circuits. We also prove that the evolution of Pauli operators displays a form of ergodicity. These results require the dimension of the local subsystem to be large. In the opposite regime our system displays a novel form of localisation, which can be characterised in terms of one-sided walls.