Quantum Relative Entropy Decay Composition Yields Shallow, Unstructured k-Designs

• URL: http://arxiv.org/abs/2510.08537v2
• Date: Mon, 13 Oct 2025 15:23:25 GMT
• Title: Quantum Relative Entropy Decay Composition Yields Shallow, Unstructured k-Designs
• Authors: Nicholas Laracuente,
• Abstract summary: A major line of questions in quantum information and computing asks how quickly locally random circuits converge to resemble global randomness.<n>It was recently shown that on n qudits, random circuits with slightly structured architectures converge to k-designs in depth O(log n), even on one-dimensional connectivity.<n>We show that a constant number of layers of a parallel random circuit on a family of architectures including one-dimensional brickwork' has O(logn) per-layer multiplicative entropy decay.
• Score: 0.40611352512781856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major line of questions in quantum information and computing asks how quickly locally random circuits converge to resemble global randomness. In particular, approximate k-designs are random unitary ensembles that resemble random circuits up to their first k moments. It was recently shown that on n qudits, random circuits with slightly structured architectures converge to k-designs in depth O(log n), even on one-dimensional connectivity. It has however remained open whether the same shallow depth applies more generally among random circuit architectures and connectivities, or if the structure is truly necessary. We recall the study of exponential relative entropy decay, another topic with a long history in quantum information theory. We show that a constant number of layers of a parallel random circuit on a family of architectures including one-dimensional `brickwork' has O(1/logn) per-layer multiplicative entropy decay. We further show that on general connectivity graphs of bounded degree, randomly placed gates achieve O(1/nlogn)-decay (consistent with logn depth). Both of these results imply that random circuit ensembles with O(polylog(n)) depth achieve approximate k-designs in diamond norm. Hence our results address the question of whether extra structure is truly necessary for sublinear-depth convergence. Furthermore, the relative entropy recombination techniques might be of independent interest.

Related papers

• Emergence of Krylov complexity through quantum walks: An exploration of the quantum origins of complexity [0.0]
  We study the relationship between quantum random walks on graphs and Krylov/spread complexity.<n>We show that the latter's definition naturally emerges through a canonical method of reducing a graph to a chain.<n>We use this identification to construct families of graphs corresponding to special classes of systems with known complexity features.
  arXiv  Detail & Related papers  (2026-02-04T19:00:00Z)
• Entanglement dynamics and Page curves in random permutation circuits [0.0]
  We study the ensembles generated by quantum circuits that randomly permute the computational basis.<n>Our results highlight the implications of classical features on entanglement generation in many-body systems.
  arXiv  Detail & Related papers  (2025-05-09T16:09:48Z)
• On the complexity of sampling from shallow Brownian circuits [0.0]
  We study a constant-time Brownian circuit model which shares many similarities with constant-depth random quantum circuits. We show that the output distributions of Brownian circuits at shallow depths follow a Porter-Thomas distribution, just like in the case of deep circuits. We discover that for these circuits, while the quantum computer typically scores within a constant factor of the expected value, the classical spoofer suffers from an exponentially larger variance.
  arXiv  Detail & Related papers  (2024-11-06T19:00:00Z)
• More global randomness from less random local gates [0.26388783516590225]
  We prove that one-dimensional structured random circuits with non-Haar random local gates can exhibit substantially more global randomness compared to Haar random circuits with the same underlying circuit architecture.<n>Our findings have applications in improving circuit depth bounds for randomized benchmarking and the generation of approximate unitary 2-designs from shallow random circuits.
  arXiv  Detail & Related papers  (2024-10-31T16:51:52Z)
• Quantum complexity and localization in random and time-periodic unitary circuits [0.0]
  We study the growth and saturation of Krylov spread (K-) complexity under random quantum circuits.<n>Our numerical analysis encompasses two classes of random circuits: brick-wall random unitary circuits and Floquet random circuits.
  arXiv  Detail & Related papers  (2024-09-05T16:10:54Z)
• KPZ scaling from the Krylov space [83.88591755871734]
  Recently, a superdiffusion exhibiting the Kardar-Parisi-Zhang scaling in late-time correlators and autocorrelators has been reported. Inspired by these results, we explore the KPZ scaling in correlation functions using their realization in the Krylov operator basis.
  arXiv  Detail & Related papers  (2024-06-04T20:57:59Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
  The OTOC-RE theorem relates the OTOCs summed over a complete base of operators to the second Renyi entropy. We show that the sum over a small set of relevant operators, is enough in order to obtain a very good approximation for the entropy. In turn, this provides with an alternative natural indicator of complexity, i.e. the scaling of the number of relevant operators with time.
  arXiv  Detail & Related papers  (2020-07-31T19:23:26Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

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.