Low-Depth Random Unitaries without Ancillae

• URL: http://arxiv.org/abs/2609.06528v1
• Date: Sun, 06 Sep 2026 10:48:57 GMT
• Title: Low-Depth Random Unitaries without Ancillae
• Abstract summary: We prove that random unitaries can be generated in optimal depth without ancillae.<n>Our results minimize the space-time costs for a wide range of quantum protocols.
• Score: 2.1517934062472532
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate $k$-designs on $n$ qubits, our circuits achieve a depth of $\widetilde{O} (k) (\log n)^{1/δ}$ on $δ$-dimensional architectures and $\widetilde{O}(k) \log \log n$ with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact $k$-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.

Related papers

• Ultra-Precise Quantum Projective Designs in Constant Depth [8.23817891945353]
  We introduce an explicit sparse commuting circuit ensemble on $n$ qubits that reproduces low-order Haar moments in the stringent relative-error sense.<n>Our results show that precise Haar-like statistics can emerge from sparse commuting dynamics with remarkably low quantum resources.
  arXiv  Detail & Related papers  (2026-09-03T14:38:21Z)
• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Unitary designs in nearly optimal depth [40.28216388589026]
  We construct unitary designs on qubits in circuit depth $O(log k log log n k / varepsilon)$.<n>The depth is exponentially improved over all known results in all three parameters $n$, $k$, $varepsilon$.<n>We also develop a new analytical framework for bounding errors in quantum experiments involving many queries to random unitaries.
  arXiv  Detail & Related papers  (2025-07-08T17:48:33Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
  arXiv  Detail & Related papers  (2025-06-05T18:34:56Z)
• Approximate inverse measurement channel for shallow shadows [0.025206105035672277]
  Classical shadows are a versatile tool to probe many-body quantum systems.<n>We put forward a simple approximate post-processing scheme where the infinite-depth inverse channel is applied to the finite-depth classical shadows.<n>Our work extends the applicability of shallow shadows to large system sizes and general circuit connectivity.
  arXiv  Detail & Related papers  (2024-07-16T15:02:25Z)
• 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)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Quantum coding with low-depth random circuits [2.4201087215689947]
  We use ensembles of low-depth random circuits with local connectivity to generate quantum error-correcting codes. For random stabilizer codes and the erasure channel, we find strong evidence that a depth $O(log N)$ random circuit is necessary. These results indicate that finite-rate quantum codes are practically relevant for near-term devices.
  arXiv  Detail & Related papers  (2020-10-19T18:25:30Z)

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.