Strong random unitaries and fast scrambling

• URL: http://arxiv.org/abs/2509.26310v1
• Date: Tue, 30 Sep 2025 14:23:46 GMT
• Title: Strong random unitaries and fast scrambling
• Authors: Thomas Schuster, Fermi Ma, Alex Lombardi, Fernando Brandao, Hsin-Yuan Huang,
• Abstract summary: We show that strong unitary designs can form in circuit depth $O(log2 n)$ in circuits composed of independent two-qubit Haar-random gates.<n>Our results provide an operational proof of the fast scrambling conjecture from black hole physics.
• Score: 37.03163411089211
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $O(\log n)$ for systems of $n$ qubits. We further show that strong unitary designs can form in circuit depth $O(\log^2 n)$ in circuits composed of independent two-qubit Haar-random gates, and that strong PRUs can form in circuit depth $\text{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.

Related papers

• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Random Unitaries in Constant (Quantum) Time [0.8516351290711953]
  We show that unitary designs and PRUs can be efficiently constructed in several well-studied models of quantum computation.<n>Results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought.
  arXiv  Detail & Related papers  (2025-08-15T14:04:49Z)
• Unconditional Pseudorandomness against Shallow Quantum Circuits [13.400821866479635]
  We establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes.<n>Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries.
  arXiv  Detail & Related papers  (2025-07-24T20:33:26Z)
• How to Construct Random Unitaries [2.8237889121096034]
  We prove that PRUs exist, assuming that any quantum-secure one-way function exists.<n>We prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer.
  arXiv  Detail & Related papers  (2024-10-14T03:07:36Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem.<n>We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions.<n>We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Random unitaries in extremely low depth [0.8680580889074451]
  We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $log n$ depth.<n>In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $textpoly(log n)$ depth, and in all-to-all-connected circuits in $textpoly(log log n)$ depth.
  arXiv  Detail & Related papers  (2024-07-10T15:27:48Z)
• Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
  Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. Two different notions of derandomisation have emerged: $t-designs are random unitaries that reproduce the first $t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.
  arXiv  Detail & Related papers  (2024-04-19T06:13:02Z)
• Pseudorandom unitaries with non-adaptive security [43.15464425520681]
  We present a PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions.
  arXiv  Detail & Related papers  (2024-02-22T18:56:37Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(nt^{5+o(1)}\ ight)$ [0.0]
  We show that random quantum circuits generate approximate unitary $t$-designs in depth $O(nt5+o(1))$. Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group.
  arXiv  Detail & Related papers  (2022-03-30T18:02:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.