Pith. sign in

REVIEW 2 major objections 3 minor 9 cited by

Non-Clifford Cost of Random Unitaries

T0 review · 2 major / 3 minor · reviewed 2026-05-22 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quadratic number of non-Clifford gates is both necessary and sufficient to approximate the frame potential of the full unitary group with t-doped Clifford circuits

desk verdict This paper pins down the exact non-Clifford overhead needed for doped Clifford circuits to form approximate k-designs. read the letter →

arxiv 2505.10110 v3 submitted 2025-05-15 quant-ph

Lorenzo Leone , Salvatore F.E. Oliviero , Alioscia Hamma , Jens Eisert , Lennart Bittel This is my paper · ORCID
classification quant-ph
keywords Cliffordcircuitsnon-Cliffordgatesunitaryk-designsframepotentialrandomquantumdopedensembleWeingartenfunctions
checked against Foundation.AbsoluteFloorClosureCost.FunctionalEquation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper examines t-doped Clifford circuits, which are random Clifford circuits with t single-qubit non-Clifford gates added at random spots. It proves that to match the frame potential of truly random unitaries, the doping level t must be on the order of k squared, and this scaling is both required and enough. This tightens the understanding of when these circuits form good approximations to state k-designs. For relative-error approximations to k-designs, t must scale as n times k, and for pseudo-random unitaries, t scales as n. The results emphasize the substantial non-Clifford resources needed to generate random quantum behavior, placing such ensembles outside efficient classical simulation.

What carries the argument

The frame potential of the t-doped Clifford ensemble and the doped-Clifford Weingarten functions used to compute the twirling operator over this ensemble

What would settle it

Exact computation of the frame potential for small fixed k and a range of t values to check whether the unitary-group value is reached only for t of order k squared

Watch

Extended reading notes

Core claim

We establish rigorous convergence bounds towards unitary k-designs for the ensemble of t-doped Clifford circuits. We prove that a quadratic doping level, t = tilde Theta(k^2), is both necessary and sufficient to approximate the frame potential of the full unitary group. This refines existing upper bounds on the convergence towards state k-designs. We derive tight bounds showing that t = tilde Theta(nk) is both necessary and sufficient for relative epsilon-approximate k-designs, and t = tilde Theta(n) for pseudo-random unitaries. We also introduce doped-Clifford Weingarten functions to derive analytic expressions for the twirling operator.

Load-bearing premise

The results depend on the ensemble being formed by randomly interleaving exactly t single-qubit non-Clifford gates within random Clifford circuits

Editorial extensions

If this is right

  • The ensemble approximates the unitary frame potential precisely when t reaches order k squared
  • Refined upper bounds apply to the distance from state k-designs
  • Relative-error k-designs form only when t reaches order n k
  • Pseudo-random unitaries appear once t reaches order n
  • The resulting ensembles lie beyond efficient classical simulation

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same quadratic scaling may govern other randomness measures such as higher moments or spectral gaps
  • Small-system numerics could directly test the necessity claim by computing frame potentials for t below k squared
  • Resource estimates for algorithms that use random unitaries could incorporate this non-Clifford cost
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The manuscript studies the ensemble of t-doped Clifford circuits on n qubits formed by randomly inserting t single-qubit non-Clifford gates into random Clifford circuits. It proves that t = tilde Theta(k^2) is both necessary and sufficient to approximate the k-th frame potential of the full unitary group, refining existing upper bounds on convergence to state k-designs. It further shows that t = tilde Theta(nk) is necessary and sufficient for the ensemble to form a relative-error approximate k-design and that t = tilde Theta(n) is required for pseudo-random unitaries. The paper introduces doped-Clifford Weingarten functions to derive analytic expressions for the twirling operator and establishes their asymptotic behavior.

Significance. If the necessity and sufficiency claims hold, the work delivers tight characterizations of the non-Clifford overhead required to generate approximate random unitaries and designs, with direct implications for circuit complexity and the boundary of classical simulability. The explicit construction and asymptotic analysis of doped-Clifford Weingarten functions constitute a reusable technical tool for moment calculations on hybrid Clifford-non-Clifford ensembles. The combination of representation-theoretic lower bounds with matching upper bounds strengthens the results relative to prior literature that provided only one-sided estimates.

major comments (2)
  1. [§3, Theorem 3.2] §3, Theorem 3.2: The necessity argument that t = Omega(k^2) is required for frame-potential approximation is derived from the support of the moment operators under the random-interleaving construction; the lower bound is tied to this specific placement distribution and would require a separate argument if gate positions were chosen adversarially or fixed in advance.
  2. [§5.2, Eq. (5.8)] §5.2, Eq. (5.8): The sufficiency proof for relative-error k-designs invokes the asymptotic expansion of the doped Weingarten function; an explicit uniform bound on the remainder term is needed when k scales linearly with n to justify the tilde Theta(nk) statement across the full parameter regime claimed.
minor comments (3)
  1. [Abstract] Abstract: The tilde Theta notation is used without a short definition or reference; adding one sentence would improve accessibility for readers outside the immediate subfield.
  2. [§2.1] §2.1: The frame potential is defined via the integral over the unitary group, but the normalization constant is not restated in the doped-ensemble section; repeating it would aid comparison.
  3. [Figure 3] Figure 3 caption: The values of n and k used for the numerical curves are not listed; including them would make the figure self-contained.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and constructive feedback on our manuscript. We address each of the major comments below and have incorporated revisions to strengthen the presentation and rigor of our results.

read point-by-point responses

  1. Referee: [§3, Theorem 3.2] §3, Theorem 3.2: The necessity argument that t = Omega(k^2) is required for frame-potential approximation is derived from the support of the moment operators under the random-interleaving construction; the lower bound is tied to this specific placement distribution and would require a separate argument if gate positions were chosen adversarially or fixed in advance.

    Authors: We appreciate the referee's careful analysis of our necessity argument in Theorem 3.2. Indeed, the lower bound is established for the ensemble where the t non-Clifford gates are randomly interleaved within the Clifford circuit. This random placement is an integral part of the t-doped Clifford circuit model studied in the paper. Our results characterize the non-Clifford cost for this natural random ensemble. While a different placement strategy might yield different bounds, our focus is on the random-interleaving construction as defined. To address this point, we will add a clarifying remark in Section 3 specifying that the necessity holds under random gate placement. revision: yes

  2. Referee: [§5.2, Eq. (5.8)] §5.2, Eq. (5.8): The sufficiency proof for relative-error k-designs invokes the asymptotic expansion of the doped Weingarten function; an explicit uniform bound on the remainder term is needed when k scales linearly with n to justify the tilde Theta(nk) statement across the full parameter regime claimed.

    Authors: We thank the referee for highlighting this aspect of the proof in Section 5.2. The asymptotic expansion of the doped-Clifford Weingarten function is used to derive the convergence bounds. To ensure the result holds uniformly when k grows linearly with n, we will derive and include an explicit bound on the remainder term in the expansion. This bound can be obtained by carefully estimating the contributions from higher moments using the representation-theoretic properties of the Weingarten functions. We will update the manuscript to include this uniform error bound, thereby justifying the tilde Theta(nk) scaling in the full regime. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivations self-contained

full rationale

The paper establishes necessity and sufficiency of quadratic and linear doping levels through explicit computation of frame potentials, moment operators, and newly defined doped-Clifford Weingarten functions with stated asymptotic expansions. These steps rely on representation-theoretic lower bounds and direct analysis of the random-interleaving ensemble rather than any fitted parameter renamed as a prediction, self-referential definition, or load-bearing self-citation chain. The central claims on convergence to k-designs and pseudo-random unitaries remain independent of prior author results and are supported by the paper's own explicit constructions.

Assumptions & free parameters 0 free parameters · 1 assumptions · 1 invented entities

The central claims rest on standard quantum-information axioms about the unitary group and Haar measure together with the newly introduced doped-Clifford Weingarten functions; no numerical free parameters are fitted to data.

assumptions (1)
  • standard math Properties of the unitary group and its Haar measure define the target k-design moments.
    The frame potential and relative-error design definitions are taken directly from the standard Haar-random unitary ensemble.
invented entities (1)
  • doped-Clifford Weingarten functions
    purpose: Analytic computation of the twirling operator over the t-doped Clifford ensemble.
    New functions introduced to obtain closed-form expressions for averages over the mixed Clifford-plus-non-Clifford ensemble.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Non-Clifford Cost of Random Unitaries." pith.science (2026). https://pith.science/paper/2505.10110

@misc{pith2026250510110,
  author       = {Pith},
  title        = {Pith review of: Non-Clifford Cost of Random Unitaries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2505.10110}},
  note         = {Machine review of arXiv:2505.10110}
}
abstract

Recent years have enjoyed a strong interest in exploring properties and applications of random quantum circuits. In this work, we explore the ensemble of $t$-doped Clifford circuits on $n$ qubits, consisting of Clifford circuits interspersed with $t$ single-qubit non-Clifford gates. We establish rigorous convergence bounds towards unitary $k$-designs, revealing the intrinsic cost in terms of non-Clifford resources in various flavors. First, we analyze the $k$-th order frame potential, which quantifies how well the ensemble of doped Clifford circuits is spread within the unitary group. We prove that a quadratic doping level, $t = \tilde{\Theta}(k^2)$, is both necessary and sufficient to approximate the frame potential of the full unitary group. As a consequence, we refine existing upper bounds on the convergence of the ensemble towards state $k$-designs. Second, we derive tight bounds on the convergence of $t$-doped Clifford circuits towards relative-error $k$-designs, showing that $t = \tilde{\Theta}(nk)$ is both necessary and sufficient for the ensemble to form a relative $\varepsilon$-approximate $k$-design. Similarly, $t = \tilde{\Theta}(n)$ is required to generate pseudo-random unitaries. All these results highlight that generating random unitaries is extremely costly in terms of non-Clifford resources, and that such ensembles fundamentally lie beyond the classical simulability barrier. Additionally, we introduce doped-Clifford Weingarten functions to derive analytic expressions for the twirling operator over the ensemble of random doped Clifford circuits, and we establish their asymptotic behavior in relevant regimes.

Figures

Figures reproduced from arXiv: 2505.10110 by the authors.

Figure 1
Figure 1. FIG. 1. Pictorial representation of [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We prove that a quadratic doping level, t = tilde Theta(k^2), is both necessary and sufficient to approximate the frame potential of the full unitary group... t = tilde Theta(nk) ... relative epsilon-approximate k-design.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    doped-Clifford Weingarten functions... asymptotic behavior

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 9 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. High-rate qLDPC processors

    quant-ph 2026-07 conditional novelty 8.0 of 10

    Non-abelian "mitten" qLDPC codes achieve 20% encoding rate with distances 10-24 on 150-975 qubits, and simulations indicate fault-tolerant processors sustaining ~10^10 logical operations at 0.1% physical error rate.

  2. A journey through Flatland: What does the antiflatness of a spectrum teach us?

    quant-ph 2026-05 unverdicted novelty 7.0 of 10

    Introduces antiflatness of entanglement spectra, antiflat majorization based on Rényi entropy spread, and unifies measures via escort distributions while connecting capacity of entanglement to quantum Fisher information.

  3. Non-stabilizerness and U(1) symmetry in chaotic many-body quantum systems

    quant-ph 2026-03 unverdicted novelty 7.0 of 10

    Exact results show U(1) symmetry substantially suppresses non-stabilizerness in random states, with different leading scaling from entanglement near zero charge density.

  4. Certifying localizable quantum properties with constant sample complexity

    quant-ph 2025-09 unverdicted novelty 7.0 of 10

    A new framework certifies global quantum properties including multipartite entanglement, circuit complexity, and quantum magic on small subsystems with constant sample complexity via local Pauli measurements.

  5. Demonstrating an unconditional separation between quantum and classical information resources

    quant-ph 2025-09 unverdicted novelty 7.0 of 10

    Demonstrates a task solvable with 12 qubits but requiring 62-382 classical bits of memory, yielding unconditional quantum information supremacy on a trapped-ion processor.

  6. Operational interpretation of the Stabilizer Entropy

    quant-ph 2025-07 unverdicted novelty 7.0 of 10

    The stabilizer Rényi entropy governs the exponential rate at which Clifford orbits become indistinguishable from Haar-random states and sets the optimal distinguishability from stabilizer states in property testing.

  7. Magic-protected entanglement and Clifford-irreducible structure in magic state space

    quant-ph 2026-07 conditional novelty 6.0 of 10

    Quantum states are classified by how much bipartite entanglement survives optimal simplification by classically easy Clifford operations, yielding a split into weakly protected T-magic and strongly protected W-magic regimes.

  8. Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks

    quant-ph 2025-12 conditional novelty 6.0 of 10

    Real stabilizer states follow a new "orthogonal Clifford Porter–Thomas" overlap distribution, reached by shallow real-Clifford circuits in log depth; one imaginary state recovers unitary-Clifford statistics, polylog m...

  9. Quantum Complexity and Chaos in Many-Qudit Doped Clifford Circuits

    quant-ph 2025-06 conditional novelty 6.0 of 10

    For odd-prime qudit doped Clifford circuits, magic saturates at a universal value above a doping rate q_c(d), while OTOC-based chaos requires about twice that rate.

Reference graph

Works this paper leans on

109 extracted references · 109 canonical work pages · cited by 9 Pith papers

  1. [1]

    [73], the same bound hold for the Haar random ensemble

    Moreover, as also noted in Ref. [73], the same bound hold for the Haar random ensemble. Moreover we have that 7|P| 2 d ≤ 1 16 for every k ≥ 1 thanks to the hypothesis of the lemma. Therefore, we finally have X Ω̸∈Sk (∆Ω,Ω)t ≤ (|P| − k!) 15 16 t (104) 24 Now we established the key lemmas to show the convergence of doped random circuit in multiple flavours....

    work page

  2. [2]

    Note that the condition n ≥ f(k, t/2) ensures n ≥ 3 2(k2 − 3k + 26 + log 16

    Hence, a sufficient condition for applying Theorem 16 in this case is n ≥ 3 2(k2 − 3k + 26 + log 16 15). Note that the condition n ≥ f(k, t/2) ensures n ≥ 3 2(k2 − 3k + 26 + log 16

    work page

  3. [3]

    Y i U ⊗k i (⃗ αi) #† Ψ(k) Cl

    for any t, k ≥ 1. Applying Theorem 16, we can expressP Ω(∆t)Ω,Ω =P Ω(∆Ω,Ω)t ± 7|P| 4 d t∥∆∥t−1 ∞ . Now, applying Lemma 17 and Corollary 2, we have X Ω (∆t)Ω ≥ (|P| − k!) 2√π 3e2 √ k t − 7|P|4 d t∥∆∥t−1 ∞ . (110) To derive a nontrivial lower bound we require that 7|P| 4 d t∥∆∥t−1 ∞ ≤ 1 2(|P| − k!) 2√π 3e2√ k t . A sufficient condition to ensure it is given...

    work page

  4. [4]

    Ambainis and A

    A. Ambainis and A. Smith, Small pseudo-random families of matrices: Derandomizing approximate quantum encryption, in Proc. RANDOM’04, Lecture Notes in Computer Science , Vol. 3122 (Springer, 2004) pp. 249– 260

    work page 2004

  5. [5]

    Hayden, D

    P. Hayden, D. Leung, P. W. Shor, and A. Winter, Randomizing quantum states: Constructions and appli- cations, Commun. Math. Phys. 250, 371 (2004)

    work page 2004

  6. [6]

    Kretschmer, Quantum pseudorandomness and classical complexity, in TQC 2021, Vol

    W. Kretschmer, Quantum pseudorandomness and classical complexity, in TQC 2021, Vol. 197 (2021) pp. 2:1–2:20

    work page 2021

  7. [7]

    Morimae and T

    T. Morimae and T. Yamakawa, Quantum commitments and signatures without one-way functions, in CRYPTO 2022 (2022) pp. 269–295

    work page 2022

  8. [8]

    Ananth, L

    P. Ananth, L. Qian, and H. Yuen, Cryptography from pseudorandom quantum states, in CRYPTO 2022 (2022) pp. 208–236

    work page 2022

Show all 109 references
  1. [9]

    P. Sen, Random measurement bases, quantum state distinction and applications to the hidden subgroup problem, in 21st Annual IEEE Conference on Computational Complexity (CCC’06) (2006) pp. 14–287

    2006

  2. [10]

    F. G. S. L. Brand˜ ao and M. Horodecki, Exponential quantum speed-ups are generic, Quant. Inf. Comp.13, 901 (2013)

    2013

  3. [11]

    Boixo, S

    S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near-term devices, Nature Phys. 14, 595 (2018)

    2018

  4. [12]

    Arute et al

    F. Arute et al. , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019)

    2019

  5. [13]

    Bouland, B

    A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling, Nature Phys. 15, 159 (2019)

    2019

  6. [14]

    Kueng, H

    R. Kueng, H. Rauhut, and U. Terstiege, Low rank matrix recovery from rank one measurements, Appl. Comput. Harmon. Anal. 42, 88 (2017)

    2017

  7. [15]

    Kimmel and Y

    S. Kimmel and Y. Liu, Phase retrieval using unitary 2-designs, in2017 International Conference on Sampling Theory and Applications (SampTA) (2017) pp. 345–349

    2017

  8. [16]

    Kueng, H

    R. Kueng, H. Zhu, and D. Gross, Distinguishing quantum states using Clifford orbits (2016), arXiv:1609.08595

    2016 arXiv

  9. [17]

    Oszmaniec et al., Random bosonic states for robust quantum metrology, Phys

    M. Oszmaniec et al., Random bosonic states for robust quantum metrology, Phys. Rev. X 6, 041044 (2016)

    2016

  10. [18]

    Eisert, D

    J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Quantum certification and benchmarking, Nature Rev. Phys. 2, 382–390 (2020)

    2020

  11. [19]

    Dankert, R

    C. Dankert, R. Cleve, J. Emerson, and E. Livine, Exact and approximate unitary 2-designs and their application to fidelity estimation, Phys. Rev. A 80, 012304 (2009)

    2009

  12. [20]

    Magesan, J

    E. Magesan, J. M. Gambetta, and J. Emerson, Scalable and robust randomized benchmarking of quantum processes, Phys. Rev. Lett. 106, 180504 (2011)

    2011

  13. [21]

    Magni, A

    B. Magni, A. Christopoulos, A. D. Luca, and X. Turkeshi, Anticoncentration in Clifford circuits and beyond: From random tensor networks to pseudo-magic states (2025), arXiv:2502.20455. 33

    2025

  14. [22]

    Devetak, The private classical capacity and quantum capacity of a quantum channel, IEEE Trans

    I. Devetak, The private classical capacity and quantum capacity of a quantum channel, IEEE Trans. Inf. Th. 51, 44 (2005)

    2005

  15. [23]

    Devetak and A

    I. Devetak and A. Winter, Relating quantum privacy and quantum coherence: An operational approach, Phys. Rev. Lett. 93, 080501 (2004)

    2004

  16. [24]

    Groisman, S

    B. Groisman, S. Popescu, and A. Winter, Quantum, classical, and total amount of correlations in a quantum state, Phys. Rev. A 72, 032317 (2005)

    2005

  17. [25]

    Abeyesinghe et al., The mother of all protocols: Restructuring quantum information’s family tree, Proc

    A. Abeyesinghe et al., The mother of all protocols: Restructuring quantum information’s family tree, Proc. R. Soc. A 465, 2537 (2009)

    2009

  18. [26]

    Dupuis et al., One-shot decoupling, Commun

    F. Dupuis et al., One-shot decoupling, Commun. Math. Phys. 328, 251 (2014)

    2014

  19. [27]

    Szehr et al., Decoupling with unitary approximate two-designs, New J

    O. Szehr et al., Decoupling with unitary approximate two-designs, New J. Phys. 15, 053022 (2013)

    2013

  20. [28]

    Horodecki, J

    M. Horodecki, J. Oppenheim, and A. Winter, Partial quantum information, Nature 436, 673–676 (2005)

    2005

  21. [29]

    Horodecki, J

    M. Horodecki, J. Oppenheim, and A. Winter, Quantum state merging and negative information, Comm. Math. Phys. 269, 107–136 (2006)

    2006

  22. [30]

    Nakata, E

    Y. Nakata, E. Wakakuwa, and H. Yamasaki, One-shot quantum error correction of classical and quantum information, Phys. Rev. A 104, 012408 (2021)

    2021

  23. [31]

    Wakakuwa and Y

    E. Wakakuwa and Y. Nakata, One-shot triple-resource trade-off in quantum channel coding, IEEE Trans. Inf. Th. 69, 2400 (2023)

    2023

  24. [32]

    Popescu, A

    S. Popescu, A. J. Short, and A. Winter, Entanglement and the foundations of statistical mechanics, Nature Phys. 2, 754 (2006)

    2006

  25. [33]

    Linden, S

    N. Linden, S. Popescu, A. J. Short, and A. Winter, Quantum mechanical evolution towards thermal equi- librium, Phys. Rev. E 79, 061103 (2009)

    2009

  26. [34]

    del Rio et al., Relative thermalization, Phys

    L. del Rio et al., Relative thermalization, Phys. Rev. E 94, 022104 (2016)

    2016

  27. [35]

    Kaneko et al

    K. Kaneko et al. , Characterizing complexity of many-body quantum dynamics by higher-order eigenstate thermalization, Phys. Rev. A 101, 042126 (2020)

    2020

  28. [36]

    Gogolin and J

    C. Gogolin and J. Eisert, Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems, Rep. Prog. Phys. 79, 56001 (2016)

    2016

  29. [37]

    Ippoliti and W

    M. Ippoliti and W. W. Ho, Solvable model of deep thermalization with distinct design times, Quantum 6, 886 (2022)

    2022

  30. [38]

    Hayden and J

    P. Hayden and J. Preskill, Black holes as mirrors: Quantum information in random subsystems, J. High En. Phys. 2007, 120 (2007)

    2007

  31. [39]

    Nakata et al., Black holes as clouded mirrors: the Hayden-Preskill protocol with symmetry, Quantum 7, 928 (2023)

    Y. Nakata et al., Black holes as clouded mirrors: the Hayden-Preskill protocol with symmetry, Quantum 7, 928 (2023)

    2023

  32. [40]

    Onorati, O

    E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert, Mixing properties of stochastic quantum Hamiltonians, Commun. Math. Phys. 355, 905 (2017)

    2017

  33. [41]

    Nakata, Y

    Y. Nakata, Y. Takeuchi, M. Kliesch, and A. Darmawan, On computational complexity of unitary and state design properties (2024), arXiv:2410.23353

    2024

  34. [42]

    S. F. E. Oliviero, L. Leone, S. Lloyd, and A. Hamma, Unscrambling quantum information with Clifford decoders, Phys. Rev. Lett. 132, 080402 (2024)

    2024

  35. [43]

    Leone, S

    L. Leone, S. F. E. Oliviero, S. Lloyd, and A. Hamma, Learning efficient decoders for quasichaotic quantum scramblers, Phys. Rev. A 109, 022429 (2024)

    2024

  36. [44]

    Sekino and L

    Y. Sekino and L. Susskind, Fast scramblers, J. High En. Phys. 2008, 065 (2008)

    2008

  37. [45]

    Lashkari, D

    N. Lashkari, D. Stanford, M. Hastings, T. Osborne, and P. Hayden, Towards the fast scrambling conjecture, J. High En. Phys. 2013, 22 (2013)

    2013

  38. [46]

    Maldacena, S

    J. Maldacena, S. H. Shenker, and D. Stanford, A bound on chaos, J. High En. Phys. 2016, 106 (2016)

    2016

  39. [47]

    D. A. Roberts and B. Yoshida, Chaos and complexity by design, J. High En. Phys. 2017, 121 (2017)

    2017

  40. [48]

    J. S. Cotler et al., Emergent quantum state designs from individual many-body wave functions, PRX Quan- tum 4, 010311 (2023)

    2023

  41. [49]

    D. K. Mark et al., Maximum entropy principle in deep thermalization and in Hilbert-space ergodicity, Phys. Rev. X 14, 041051 (2024)

    2024

  42. [50]

    Pilatowsky-Cameo et al., Hilbert-space ergodicity in driven quantum systems: Obstructions and designs, Phys

    S. Pilatowsky-Cameo et al., Hilbert-space ergodicity in driven quantum systems: Obstructions and designs, Phys. Rev. X 14, 041059 (2024)

    2024

  43. [51]

    Munson, N

    A. Munson, N. B. T. Kothakonda, J. Haferkamp, N. Yunger Halpern, J. Eisert, and P. Faist, Complexity- Constrained Quantum Thermodynamics, PRX Quantum 6, 010346 (2025)

    2025

  44. [52]

    Emerson, Y

    J. Emerson, Y. S. Weinstein, M. Saraceno, S. Lloyd, and D. G. Cory, Pseudo-random unitary operators for Quant. Inf. Proc., Science 302, 2098 (2003)

  45. [53]

    Gross, K

    D. Gross, K. Audenaert, and J. Eisert, Evenly distributed unitaries: On the structure of unitary designs, J. Math. Phys. 48, 052104 (2007)

    2007

  46. [54]

    Haferkamp, F

    J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, and I. Roth, Efficient unitary designs with a system-size independent number of non-Clifford gates, Commun. Math. Phys. 397, 995 (2023)

    2023

  47. [55]

    F. G. S. L. Brand˜ ao, A. W. Harrow, and M. Horodecki, Local random quantum circuits are approximate polynomial-designs, Comm. Math. Phys. 346, 397 (2016)

    2016

  48. [56]

    A. W. Harrow and R. A. Low, Random quantum circuits are approximate 2-designs, Comm. Math. Phys. 291, 302 (2009). 34

    2009

  49. [57]

    A. W. Harrow and S. Mehraban, Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates, Comm. Math. Phys. 401, 1531–1626 (2023)

    2023

  50. [58]

    LaRacuente and F

    N. LaRacuente and F. Leditzky, Approximate unitary k-designs from shallow, low-communication circuits (2024), arXiv:2407.07876

    2024

  51. [59]

    Ji, Y.-K

    Z. Ji, Y.-K. Liu, and F. Song, Pseudorandom quantum states, in Advances in Cryptology – CRYPTO 2018 (Springer International Publishing, 2018) p. 126–152

    2018

  52. [60]

    Metger, A

    T. Metger, A. Poremba, M. Sinha, and H. Yuen, Pseudorandom unitaries with non-adaptive security (2024), arXiv:2402.14803

    2024

  53. [61]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth (2025), arXiv:2407.07754

    2025

  54. [62]

    Ma and H.-Y

    F. Ma and H.-Y. Huang, How to construct random unitaries (2024), arXiv:2410.10116

    2024

  55. [63]

    T. Haug, K. Bharti, and D. E. Koh, Pseudorandom unitaries are neither real nor sparse nor noise-robust (2024), arXiv:2306.11677

    2024

  56. [64]

    Eastin and E

    B. Eastin and E. Knill, Restrictions on transversal encoded quantum gate sets, Phys. Rev. Lett. 102, 110502 (2009)

    2009

  57. [65]

    Gottesman, Stabilizer codes and quantum error correction, Ph.D

    D. Gottesman, Stabilizer codes and quantum error correction, Ph.D. thesis, California Institute of Technology (1997)

    1997

  58. [66]

    Webb, The Clifford group forms a unitary 3-design, QIC 16, 1379 (2016)

    Z. Webb, The Clifford group forms a unitary 3-design, QIC 16, 1379 (2016)

    2016

  59. [67]

    Zhu, Multiqubit Clifford groups are unitary 3-designs, Phys

    H. Zhu, Multiqubit Clifford groups are unitary 3-designs, Phys. Rev. A 96, 062336 (2017)

    2017

  60. [68]

    A. J. Scott, Optimizing quantum process tomography with unitary 2-designs, J. Phys. A 41, 055308 (2008)

    2008

  61. [69]

    I. Roth, R. Kueng, S. Kimmel, Y.-K. Liu, D. Gross, J. Eisert, and M. Kliesch, Recovering quantum gates from few average gate fidelities, Phys. Rev. Lett. 121, 170502 (2018)

    2018

  62. [70]

    J. J. Wallman and S. T. Flammia, Randomized benchmarking with confidence, New J. Phys. 16, 103032 (2014)

    2014

  63. [71]

    J. J. Wallman, Randomized benchmarking with gate-dependent noise, Quantum 2, 47 (2018)

    2018

  64. [72]

    H. Zhu, R. Kueng, M. Grassl, and D. Gross, The Clifford group fails gracefully to be a unitary 4-design (2016), arXiv:1609.08172

    2016 arXiv

  65. [73]

    Deshpande, B

    A. Deshpande, B. Fefferman, S. Ghosh, M. Gullans, and D. Hangleiter, Peaked quantum advantage using error correction (2025), arXiv:2510.05262 [quant-ph]

    2025

  66. [74]

    Zhang, S

    Y. Zhang, S. Vijay, Y. Gu, and Y. Bao, Designs from magic-augmented clifford circuits (2025), arXiv:2507.02828 [quant-ph]

    2025

  67. [75]

    Bittel, J

    L. Bittel, J. Eisert, L. Leone, A. A. Mele, and S. F. E. Oliviero, A complete theory of the Clifford commutant (2025), arXiv:2504.12263

    2025

  68. [76]

    Haferkamp, Random quantum circuits are approximate unitary t-designs in depth O(nt5+o(1)), Quantum 6, 795 (2022)

    J. Haferkamp, Random quantum circuits are approximate unitary t-designs in depth O(nt5+o(1)), Quantum 6, 795 (2022)

    2022

  69. [77]

    S.-K. Jian, G. Bentsen, and B. Swingle, Linear growth of circuit complexity from Brownian dynamics (2022), arXiv:2206.14205

    2022

  70. [78]

    Haferkamp, P

    J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, and N. Yunger Halpern, Linear growth of quantum circuit complexity, Nat. Phys. 18, 528 (2022)

    2022

  71. [79]

    Kitaev, Hidden correlations in the Hawking radiation and thermal noise, in Talk given at the Fundamental Physics Prize Symposium , Vol

    A. Kitaev, Hidden correlations in the Hawking radiation and thermal noise, in Talk given at the Fundamental Physics Prize Symposium , Vol. 10 (2014)

    2014

  72. [80]

    Leone, S

    L. Leone, S. F. E. Oliviero, Y. Zhou, and A. Hamma, Quantum chaos is quantum, Quantum 5, 453 (2021)

    2021

  73. [81]

    S. F. E. Oliviero, L. Leone, and A. Hamma, Transitions in entanglement complexity in random quantum circuits by measurements, Phys. Lett. A 418, 127721 (2021)

    2021

  74. [82]

    Bhatia, Matrix analysis , Vol

    R. Bhatia, Matrix analysis , Vol. 169 (Springer New York, 1997)

    1997

  75. [83]

    Cotler, N

    J. Cotler, N. Hunter-Jones, J. Liu, and B. Yoshida, Chaos, complexity, and random matrices, J. High En. Phys. 2017, 48 (2017)

    2017

  76. [84]

    Liu, Spectral form factors and late time quantum chaos, Phys

    J. Liu, Spectral form factors and late time quantum chaos, Phys. Rev. D 98, 086026 (2018)

    2018

  77. [85]

    Leone, S

    L. Leone, S. F. E. Oliviero, and A. Hamma, Isospectral twirling and quantum chaos, Entropy 23, 1073 (2021)

    2021

  78. [86]

    S. F. E. Oliviero, L. Leone, F. Caravelli, and A. Hamma, Random matrix theory of the isospectral twirling, SciPost Phys. 10, 76 (2021)

    2021

  79. [87]

    Gharibyan, M

    H. Gharibyan, M. Hanada, S. H. Shenker, and M. Tezuka, Onset of random matrix behavior in scrambling systems, J. High En. Phys. 2018, 124 (2018)

    2018

  80. [88]

    Winer and B

    M. Winer and B. Swingle, Reappearance of thermalization dynamics in the late-time spectral form factor (2023), arXiv:2307.14415

    2023

  81. [89]

    J. P. Keating and N. C. Snaith, Random matrix theory and ζ(1/2+it), Comm. Math. Phys. 214, 57 (2000)

    2000

  82. [90]

    Imry, Active transmission channels and universal conductance fluctuations, Eur

    Y. Imry, Active transmission channels and universal conductance fluctuations, Eur. Phys. Lett.1, 249 (1986)

    1986

  83. [91]

    Bravyi and D

    S. Bravyi and D. Gosset, Improved Classical simulation of quantum circuits dominated by Clifford gates, Phys. Rev. Lett. 116, 250501 (2016)

    2016

  84. [92]

    A. Gu, S. F. Oliviero, and L. Leone, Magic-induced computational separation in entanglement theory, PRX Quantum 6, 020324 (2025)

    2025

  85. [93]

    Ji, Y.-K

    Z. Ji, Y.-K. Liu, and F. Song, Pseudorandom quantum states, in Advances in Cryptology – CRYPTO 2018, Lecture Notes in Computer Science, edited by H. Shacham and A. Boldyreva (Springer International 35 Publishing, Cham, 2018) pp. 126–152

    2018

  86. [94]

    Grewal, V

    S. Grewal, V. Iyer, W. Kretschmer, and D. Liang, Efficient learning of quantum states prepared with few non-Clifford gates (2023), arXiv:2305.13409

    2023

  87. [95]

    Skinner, J

    B. Skinner, J. Ruhman, and A. Nahum, Measurement-induced phase transitions in the dynamics of entan- glement, Phys. Rev. X 9, 031009 (2019)

    2019

  88. [96]

    A. F. Mello, A. Santini, G. Lami, J. De Nardis, and M. Collura, Clifford dressed time-dependent variational principle, Phys. Rev. Lett. 134, 150403 (2025)

    2025

  89. [97]

    Weingarten, Asymptotic behavior of group integrals in the limit of infinite rank, J

    D. Weingarten, Asymptotic behavior of group integrals in the limit of infinite rank, J. Math. Phys. 19, 999 (1978)

    1978

  90. [98]

    Z.-W. Liu, S. Lloyd, E. Zhu, and H. Zhu, Entanglement, quantum randomness, and complexity beyond scrambling, J. High En. Phys. 2018, 41 (2018)

    2018

  91. [99]

    R. A. Low, Pseudo-randomness and learning in quantum computation (2010), arXiv:1006.5227 [quant-ph]

    2010 arXiv

  92. [100]

    Oszmaniec, A

    M. Oszmaniec, A. Sawicki, and M. Horodecki, Epsilon-nets, unitary designs and random quantum circuits, IEEE Trans. Inf. Th. 68, 989 (2022)

    2022

  93. [101]

    G. Lami, T. Haug, and J. De Nardis, Quantum state designs with Clifford-enhanced matrix product states, PRX Quantum 6, 010345 (2025)

    2025

  94. [102]

    Gross, S

    D. Gross, S. Nezami, and M. Walter, Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations, Comm. Math. Phys. 385, 1325–1393 (2021)

    2021

  95. [103]

    M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information (Cambridge University Press, 2000)

    2000

  96. [104]

    Baker, Lie groups, in Matrix groups (Springer, London, England, UK, 2002) pp

    A. Baker, Lie groups, in Matrix groups (Springer, London, England, UK, 2002) pp. 181–209

    2002

  97. [105]

    Grewal, V

    S. Grewal, V. Iyer, W. Kretschmer, and D. Liang, Pseudoentanglement ain’t cheap (2024), arXiv:2404.00126 [quant-ph]

    2024

  98. [106]

    Leone, S

    L. Leone, S. F. E. Oliviero, S. Lloyd, and A. Hamma, Learning efficient decoders for quasi-chaotic quantum scramblers (2022), arXiv:2212.11338

    2022

  99. [107]

    S. J. Szarek, Nets of Grassmann manifold and orthogonal groups, in Proceedings of Research Workshop on Banach Space Theory (University of Iowa Press, Iowa City, Iowa, 1982) pp. 169–185

    1982

  100. [108]

    H. Zhao, L. Lewis, I. Kannan, Y. Quek, H.-Y. Huang, and M. C. Caro, Learning Quantum States and Unitaries of Bounded Gate Complexity, PRX Quantum 5, 040306 (2024)

    2024

  101. [109]

    Leone, Clifford Group and beyond: Theory and Applications in Quantum Information , Ph.D

    L. Leone, Clifford Group and beyond: Theory and Applications in Quantum Information , Ph.D. thesis, University of Massachusetts Boston (2023)

    2023

Pith tools

Reviewed May 22, 2026 · model on record in the stance chip above.