REVIEW 3 major objections 5 minor 2 cited by
No-go theorems for sublinear-depth group designs
T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read For any group with an invariant state, sublinear-depth circuits cannot be approximate k-designs.
desk verdict A genuinely useful no-go framework, but the gate-count Theorem 2 rests on a cited, unproved basis of quadratic symmetries that needs to be fixed before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the (projectively) $G$-invariant state $|\Psi\rangle\in H^{\otimes k}$, satisfying $G^{\otimes k}|\Psi\rangle = e^{i\theta_U}|\Psi\rangle$. Its role is to supply a time-reversal in the experiment: conjugating a perturbation $V$ by a sampled unitary $U$ becomes $(UVU^\dagger)\otimes \mathbb{1}^{\otimes(k-1)}$ acting on $|\Psi\rangle$, so all effects of $U$ on the perturbation localize in a lightcone. The distinguishing POVM projects onto $|\Psi\rangle\langle\Psi|_{1,L}$ on the lightcone factor; shallow circuits return the shallow outcome with probability one, Haar unitaries only with the small probability computed by the theorem. For the gate-count version, the machinery is the commutator graph of the Pauli strings in the generating set: vertices are Pauli strings, edges connect $P$ and $Q$ if some generator $H$ satisfies $[H,P]\propto Q$, and the connected components of this graph classify the quadratic symmetries $Q_{j,\kappa}=(d\sqrt{|C_\kappa|})^{-1}\sum_{S\in C_\kappa} S\otimes (L_j S)$ used in the Haar-average calculation. The translation from distinguishability to distance is the standard bound $\|\phi_E-\phi_F\|_\diamond \ge 4(p_{\mathrm{succ}}(\rho,\Pi)-1/2)$, which turns a single-shot success probability into the diamond-norm separation.
What would settle it
Check the completeness of the $Q_{j,\kappa}$ basis directly: for a small Pauli-compatible group (e.g., matchgates on $n=4$ or $5$ qubits), compute the space of operators commuting with $U^{\otimes 2}$ for all $U$ in the group and compare its dimension and orthonormal basis with the span of the $Q_{j,\kappa}$ built from commutator-graph components; a mismatch, or a nonzero $\mathrm{Tr}[Q_{j,\kappa} P^{\otimes 2}]$ for a Pauli $P$ outside component $C_\kappa$ with $L_j=1$, would falsify the Haar-average step of Theorem 2.
Extended reading notes
Core claim
The central claim is that a projectively $G$-invariant state is a resource allowing a two-outcome measurement to tell a shallow circuit ensemble apart from the Haar ensemble, and that this distinguishability translates into a quantitative lower bound on the diamond distance between the corresponding k-th moment channels. For $k=2$ the bound is $\|\phi_L^{(2)}-\phi_G^{(2)}\|_\diamond \ge 2 - \frac{2 d_L}{d^2}\mathrm{Tr}[\phi_G^{(2)}(V\otimes V^\dagger) S_L]$, where $V$ is a local perturbation, $H_L$ is the lightcone factor containing the support of $UVU^\dagger$, and $S_L$ swaps the two copies of $H_L$; for a group with an invariant state the measurement succeeds with probability one when the circuit is shallow and with a calculable small probability when the unitary is Haar-random. Evaluating the Haar average for matchgates gives $\|\cdot\|_\diamond \gtrsim 3/2$ below depth $n/2$; for orthogonal and symplectic groups the same calculation gives $\gtrsim 3/2$ below depth $n-1$; and for the Clifford group a similar eight-copy experiment, using a known lemma about Clifford tensor powers, rules out sublinear-depth 8-designs. A second theorem replaces geometric lightcones with lightcones in the commutator graph of Pauli strings: after $N$ gates generated by a set $S$, an operator can only have spread to the $N$-neighborhood of its starting Pauli in that graph, while the Haar average spreads it over the whole connected component, yielding $\|\phi_{E_N^S}^{(2)}-\phi_{\mu_G}^{(2)}\|_\diamond \ge 2 - 2|N_{N,S}(P)|/|N_S(P)|$.
Load-bearing premise
The load-bearing premise is that the quadratic symmetries of any Pauli-compatible group are exactly those built from connected components of its commutator graph, a classification cited from earlier work rather than re-derived here, so the gate-count no-go theorem collapses if that spectral decomposition is wrong.
Editorial extensions
If this is right
- Any approximate matchgate 2-design requires circuit depth at least $n/2$, and any 2-local matchgate ensemble requires at least $n^2/2$ gates; the exact matchgate Haar measure can be implemented in depth $3n$ with $2n^2-n$ gates, giving a constant separation.
- Any ensemble of 2-local orthogonal or symplectic gates requires depth at least $n-1$ to form an approximate 2-design; real Clifford circuits achieve linear depth, so the orthogonal bound is tight up to constants, while the symplectic construction question remains open.
- No ensemble of 2-local Clifford circuits of depth below $n-1$ can form an approximate Clifford 8-design.
- On a D-dimensional lattice with local gates, any approximate group design of the type considered requires depth scaling at least as $\Omega(n^{1/D})$.
- For most of the groups considered, a constant-depth measurement distinguishes the shallow ensemble from the Haar ensemble with probability bounded away from $1/2$ in a single shot, so the failure is operationally visible, not just a norm bound.
- For any group with an invariant state, sublinear-depth local circuits cannot approximate Haar k-designs.
Reading between the lines
- The authors leave open whether G-designs can be formed from circuits outside G; shallow outside-G constructions may circumvent these bounds, and testing that possibility is a natural next step.
- Because the invariant-state argument at $k=2$ settles all higher moments, the Clifford case is curious: no invariant state appears until eight copies, so approximate Clifford designs at intermediate $k=4,\ldots,7$ may or may not admit shallow constructions.
- The efficiently preparable single-shot experiments could be turned into practical property testers for whether an implemented random-circuit ensemble is too shallow to serve as a group design on real hardware.
- The lattice generalization suggests a simple geometric heuristic: on higher-dimensional chips the minimal design depth grows as $n^{1/D}$, so shallow-design tricks that work in one dimension do not transfer directly to two- or three-dimensional layouts.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves no-go theorems for approximate k-designs over subgroups of the unitary group that possess an invariant state in a tensor power of the Hilbert space. Theorem 1 gives a lightcone-based lower bound on the diamond distance between the second-moment channel of any depth-L local-gate ensemble from such a group and the Haar channel; the bound is then evaluated for matchgates, orthogonal, symplectic, mixed-unitary, and Pauli-compatible groups, yielding linear-depth lower bounds and an Ω(n^{1/D}) bound on D-dimensional lattices. Theorem 2 replaces geometric lightcones with lightcones on the commutator graph of a Pauli-compatible generating set, giving gate-count lower bounds, including a quadratic gate-count separation for matchgate 2-designs and a no-go for sublinear-gate-count nonlocal matchgate circuits. The paper also claims a Clifford 8-design lower bound using a reduction of the 8th moment to a two-copy mixed-unitary problem. The main text is clear, and the lightcone argument in Theorem 1 is elegant; however, the proof of Theorem 2 relies on a cited, non-reproduced characterization of quadratic symmetries, and the Clifford application has a representation mismatch that must be resolved.
Significance. If the missing ingredients are supplied, the paper makes a substantial contribution. The lightcone argument in Theorem 1 is parameter-free, transparent, and yields concrete, tight-up-to-constants separations for matchgates, orthogonal, and symplectic groups, with implications for classical shadows and randomized benchmarking over those groups. The single-shot distinguishability statement is a nice strengthening. Theorem 2 addresses the more difficult regime of nonlocal gates, and the claimed quadratic gate-count separation for matchgates is a strong and falsifiable result. The paper contains no fitted parameters and the central derivation is performed in the manuscript rather than imported. The main risk is that the gate-count results rely on a completeness claim for a quadratic-symmetry basis that is imported from two self-authored preprints and not proved; if that basis is incomplete, Theorem 2 and Corollaries 6–8 do not follow as stated.
major comments (3)
- [Appendix B, Eq. (B32)] The decisive ingredient of Theorem 2 is the claim that the operators Q_{j,κ} ∝ Σ_{S∈Cκ} S⊗(L_j S), built from connected components of the commutator graph, form a complete orthonormal basis of the quadratic commutant {O : [U^{⊗2}, O]=0 for all U∈G}. This is not proved in the manuscript; it is imported from Refs. [45,47], which are preprints sharing authors with the present paper. The subsequent trace evaluation from Eq. (B27) to Eq. (B31) additionally assumes that each component C_κ is invariant under the adjoint action of the full group G, not merely the generating set S, and that Tr[Q_{j,κ} P^{⊗2}] vanishes unless L_j=I and P∈C_κ. Neither fact is established here. Completeness is not a triviality: for Pauli-compatible groups that do not preserve a bilinear form, the displayed family does not obviously generate the full quadratic commutant, so the restriction to bilinear-form-preserving groups must be doing essential work that is never made explicit. Since Eq. (12) and Corollaries 6–8 all rest on this lemma, the proof should either be included in full, or the theorem should be restated with this basis as an explicit hypothesis.
- [Appendix B, Eqs. (B29)–(B31)] Even granting the Q_{j,κ} basis, the normalization chain in the proof of Theorem 2 is not verifiable as written. After substituting the normalized operators Q_{j,κ} = (1/(d sqrt|C_κ|)) Σ_S S⊗(L_j S) into Eq. (B28), the factors of d and |C_κ| must cancel in a specific way to produce the final coefficient 2|N_{N,S}(P)|/|N_S(P)| in Eq. (B31). The displayed derivation skips the necessary orthogonality and trace evaluations, and the constants do not transparently cancel. Because Eq. (12) is the quantitative output of Theorem 2, this chain needs a complete, line-by-line derivation rather than an assertion.
- [Appendix C4] The proof of Corollary 4 (Clifford 8-designs) is not self-contained and, as written, contains a representation mismatch. The text says that after using Lemma 4 one applies C⊗C to (V⊗1)|Φ⟩ and that the Bell state is Clifford-invariant; however, |Φ⟩ is invariant under C⊗C* for every unitary C, not under C⊗C for general unitaries (which requires C C^T = I). The displayed calculation in Eq. (C13) indeed uses (U⊗U*), not (U⊗U). The reduction from the 8th moment to this two-copy mixed-unitary action via Lemma 4 must be written out explicitly, including the role of the isometries V1 and V2. As it stands, Corollary 4 does not follow from the stated equations. Lemma 4 is also imported from Ref. [59] without a statement or proof.
minor comments (5)
- [Definition 3] The definition of the commutator graph should state whether a commuting pair (H,P with [H,P]=0) produces an edge or a self-loop; the later arguments assume that only nontrivial commutators create edges.
- [Appendix B, Eq. (B7)] The projective phase e^{iθ_U} is dropped from the vector equalities in the proof of Lemma 1. This is harmless because the subsequent expressions are rank-one projectors, but the text should say so explicitly, since Appendix A only establishes exact invariance of the associated bilinear form.
- [Appendix C2] The statement of Corollary 7 would benefit from an explicit connection between the diameter n^2 of the standard matchgate commutator graph and the threshold N = n^2/2; as written, the reader must infer the factor 1/2 from the diameter calculation.
- [Appendix C4] In Eq. (C13), the approximation symbol hides the use of the fact that the Clifford group is a unitary 2-design; the replacement of the Clifford average by the unitary average should be stated and quantified before this equation.
- [Appendix C5] There is a typo: 'determine wether' should be 'determine whether'. Also, the notation d^{-2}_L would be clearer as d_L^{-2}.
Circularity Check
No circularity: the no-go results are derived in-paper from a channel-discrimination argument; the cited commutant basis is a mathematical dependency, not a by-construction reduction.
full rationale
The central derivation is self-contained: Theorem 1 constructs a POVM from a G-invariant state, uses the operational bound Eq. (2) to convert the success probability of the discrimination experiment into a diamond-distance lower bound, and then evaluates the Haar average term Tr[phi_G^{(2)}(V⊗V†)S_L] by direct calculation or Weingarten calculus. Corollaries 1, 2, 3, 5, and 6 follow by evaluating this bound for specific groups and perturbations; none of these steps fits a parameter to data and then renames it as a prediction, and no target quantity is defined in terms of the quantity being bounded. The gate-count bound (Theorem 2, Eq. 12) expands the Haar average in the Q_{j,κ} basis imported from Refs [45,47]. Although those references share authors with this paper, the basis is a parameter-free characterization of the quadratic commutant of Pauli-compatible groups, with stated assumptions that do not include the no-go conclusions; it is not an ansatz fitted to the target results, and the operator-space lightcone argument supplies independent content. The Clifford k=8 result imports Lemma 4 from Ref [59], an external source. These are ordinary theorem dependencies and do not make the derivation circular. The proof of the Q-basis is not reproduced in this paper, which is a completeness or correctness caveat, but it is not circularity.
Assumptions & free parameters
assumptions (5)
- standard math Weingarten calculus formulas for Haar integration over O(d) and Sp(d)
- standard math The Clifford group forms a unitary 3-design, allowing replacement of Clifford averages by unitary Haar averages in second-moment calculations
- domain assumption Quadratic symmetries of a Pauli-compatible group are spanned by operators Q_{j,κ} over connected components of the commutator graph (Eq. B32)
- domain assumption There exist isometries V1, V2 with U = V1 U^{⊗7} V2 for every n-qubit Clifford U
- standard math Frobenius-Schur indicator trichotomy and additivity over irreducible components
Cite this review
Pith. "Pith review of No-go theorems for sublinear-depth group designs." pith.science (2026). https://pith.science/paper/5CC4VMCR
@misc{pith2026250616005,
author = {Pith},
title = {Pith review of: No-go theorems for sublinear-depth group designs},
year = {2026},
howpublished = {\url{https://pith.science/paper/5CC4VMCR}},
note = {Machine review of arXiv:2506.16005}
}
abstract
Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group $G$ possessing an invariant state $G^{\otimes k} \lvert\Psi\rangle= \lvert\Psi\rangle$, a lower bound on the diamond distance between the $k$\textsuperscript{th} moment operator of any ensemble of elements of $G$, and that of the Haar measure over $G$. We then use this bound to prove that for many groups of interest, no subset of $G$ consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate $k$-design over $G$. More generally, on a $D$-dimensional lattice, our results imply that such group designs require depths scaling at least as $n^{1/D}$. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from $k$-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth $8$-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over $G$ using any circuit comprised of a sublinear number of gates generated by Pauli strings.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 2 Pith papers
-
Apparent Universal Behavior in Second Moments of Random Quantum Circuits
Most random circuit geometries form approximate 2-designs in O(log n) depth with explicit constants; bridge/lollipop graphs need Ω(n²) gates, and 10-20 layers suffice for 50-qubit near-random circuits.
-
Ambient unitaries don't enable shallow group designs
Even with arbitrary ambient unitaries and ancillas, sublinear-depth nearest-neighbour circuits remain far from approximate 2-designs over the matchgate, orthogonal, and symplectic groups and from a Clifford 4-design.
Reference graph
Works this paper leans on
- [59]
-
[1]
We show in Appendix A that a matchgate-invariant state ex- ists fork= 2
Matchgate group For our first example, we consider then-qubit match- gate (or free-fermion) groupSpin(2n), which we recall to be generated by nearest-neighbor (on a one-dimensional ar- ray)XXgates and single-qubitZgates [32, 33, 45]. We show in Appendix A that a matchgate-invariant state ex- ists fork= 2. Applying Theorem 1 withV=X n/2 and L=n/2−1leads to...
-
[2]
Orthogonal group For our next example, we consider the orthogonal group, O(d) ={U∈U(d) :U TU=1}.(5) As described in the Introduction, the non-existence of sublinear-depth approximate orthogonal 2-designs consist- ing of local orthogonal unitaries has already been sketched in Ref. [25]. As the Bell state|Φ⟩= 2 −n/2P i|ii⟩is an orthogonal-invariant state in...
-
[3]
Here, the state (1⊗Ω|Φ⟩), where|Φ⟩is the Bell state, is aG-invariant state inH⊗2
Unitary symplectic group The situation is very similar for the (unitary) symplectic group, which we recall to be defined by the condition SP(d/2) ={U∈U(d) :U TΩU= Ω},(7) for a fixed antisymmetric non-degenerate bilinear form which we will take to beiY 13 [35, 41]. Here, the state (1⊗Ω|Φ⟩), where|Φ⟩is the Bell state, is aG-invariant state inH⊗2. Thus, we a...
-
[4]
Clifford group We next come to the important case of then-qubit Clif- ford group [34]. This is our first example of a group for which there is no invariant state atk= 2, ruling out the application of Theorem 1. Indeed, the Clifford group is well-known to form a unitary 3-design [15], so the ex- istence of logarithmic-depth approximate unitary designs imme...
-
[5]
Here for the first time we have an invariant state atk= 1
Mixed-unitary group We next studymixed-unitarycircuits [37], which consist of elements of the formU⊗U ∗, whereUis ann-qubit unitary. Here for the first time we have an invariant state atk= 1. Indeed, note that the Bell state|Φ⟩across the firstandsecondregistersofnqubitsismanifestlyinvariant. By a routine application of our procedure we find Corollary 5.An...
-
[6]
non-local matchgate cir- cuits
Pauli-compatible groups As our last example of Theorem 1 we consider the class ofPauli-compatiblegroups, defined as follows. LetP n be the set ofn-qubit Pauli strings. Definition 2(Pauli-compatible).A groupG⊆U(H)on H= (C 2)⊗n is called Pauli-compatible if both •its elements are of the form Q jeiθjPj withθ j real scalars andPj∈S⊆P n, and •theG-invariant op...
-
[7]
Huang, R
H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measure- ments, Nature Physics16, 1050 (2020)
2020
Show all 80 references
-
[8]
Knill, D
E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland, Randomized benchmarking of quan- tum gates, Physical Review A77, 012307 (2008)
2008
-
[9]
Elben, S
A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The ran- domized measurement toolbox, Nature Review Physics 10.1038/s42254-022-00535-2 (2022)
2022 doi
-
[10]
A. Zhao, N. C. Rubin, and A. Miyake, Fermionic partial tomography via classical shadows, Physical Review Letters 127, 110504 (2021)
2021
-
[11]
K. Wan, W. J. Huggins, J. Lee, and R. Babbush, Match- gate shadows for fermionic quantum simulation, Commu- nications in Mathematical Physics404, 629 (2023)
2023
-
[12]
M. West, A. A. Mele, M. Larocca, and M. Cerezo, Real classical shadows, arXiv preprint arXiv:2410.23481 (2024)
2024 arXiv
-
[13]
Arute, K
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R.Collins, W.Courtney, A.Dunsworth, E.Farhi, B.Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. H...
2019
- [14]
-
[15]
Van Kirk, J
K. Van Kirk, J. Cotler, H.-Y. Huang, and M. D. Lukin, Hardware-efficient learning of quantum many-body states, arXiv preprint arXiv:2212.06084 (2022)
2022 arXiv
-
[16]
M. P. Fisher, V. Khemani, A. Nahum, and S. Vijay, Ran- dom quantum circuits, Annual Review of Condensed Mat- ter Physics14, 335 (2023)
2023
-
[17]
A.Nahum, J.Ruhman, S.Vijay,andJ.Haah,Quantumen- tanglement growth under random unitary dynamics, Phys- ical Review X7, 031016 (2017)
2017
-
[18]
Nahum, S
A. Nahum, S. Vijay, and J. Haah, Operator spreading in random unitary circuits, Physical Review X8, 021014 (2018)
2018
-
[19]
Hayden and J
P. Hayden and J. Preskill, Black holes as mirrors: quantum information in random subsystems, Journal of High Energy Physics9, 120 (2007)
2007
-
[20]
Y.SekinoandL.Susskind,Fastscramblers,JournalofHigh Energy Physics2008, 065 (2008)
2008
-
[21]
A. A. Mele, Introduction to haar measure tools in quan- tum information: A beginner’s tutorial, Quantum8, 1340 (2024)
2024
-
[22]
A. W. Harrow and R. A. Low, Random quantum circuits are approximate 2-designs, Communications in Mathemat- ical Physics291, 257 (2009)
2009
-
[23]
F. G. Brandao, A. W. Harrow, and M. Horodecki, Lo- cal random quantum circuits are approximate polynomial- designs, Communications in Mathematical Physics346, 397 (2016)
2016
-
[24]
Hunter-Jones, Unitary designs from statistical me- chanics in random quantum circuits, arXiv preprint arXiv:1905.12053 (2019)
N. Hunter-Jones, Unitary designs from statistical me- chanics in random quantum circuits, arXiv preprint arXiv:1905.12053 (2019). 9
2019 arXiv
-
[25]
M. Liu, J. Liu, Y. Alexeev, and L. Jiang, Estimating the randomness of quantum circuit ensembles up to 50 qubits, npj Quantum Information8, 137 (2022)
2022
-
[26]
W. W. Ho and S. Choi, Exact emergent quantum state designs from quantum chaotic dynamics, Physical Review Letters128, 060601 (2022)
2022
-
[27]
C.-F. Chen, J. Docter, M. Xu, A. Bouland, and P. Hay- den, Efficient unitary t-designs from random sums, arXiv preprint arXiv:2402.09335 (2024)
2024 arXiv
-
[28]
Metger, A
T. Metger, A. Poremba, M. Sinha, and H. Yuen, Simple constructions of linear-depth t-designs and pseudorandom unitaries, arXiv preprint arXiv:2404.12647 (2024)
2024 arXiv
-
[29]
J. Haah, Y. Liu, and X. Tan, Efficient approximate uni- tary designs from random pauli rotations, arXiv preprint arXiv:2402.05239 (2024)
2024
-
[30]
C.-F. Chen, J. Haah, J. Haferkamp, Y. Liu, T. Metger, and X. Tan, Incompressibility and spectral gaps of random circuits, arXiv preprint arXiv:2406.07478 (2024)
2024 arXiv
-
[31]
Schuster, J
T. Schuster, J. Haferkamp, and H.-Y. Huang, Ran- dom unitaries in extremely low depth, arXiv preprint arXiv:2407.07754 (2024)
2024 arXiv
-
[32]
G. H. Low, Classical shadows of fermions with parti- cle number symmetry, arXiv preprint arXiv:2208.08964 (2022)
2022 arXiv
-
[33]
M. L. Goh, M. Larocca, L. Cincio, M. Cerezo, and F. Sauvage, Lie-algebraic classical simulations for quantum computing, arXiv preprint arXiv:2308.01432 (2023)
2023
-
[34]
Miller, Z
A. Miller, Z. Holmes, Ö. Salehi, R. Chakraborty, A. Nykä- nen, Z.Zimborás, A.Glos,andG.García-Pérez,Simulation of fermionic circuits using majorana propagation, arXiv preprint arXiv:2503.18939 (2025)
2025
-
[35]
Hashagen, S
A. Hashagen, S. Flammia, D. Gross, and J. Wallman, Real randomized benchmarking, Quantum2, 85 (2018)
2018
-
[36]
Marvian, Restrictions on realizable unitary operations imposed by symmetry and locality, Nature Physics18, 283 (2022)
I. Marvian, Restrictions on realizable unitary operations imposed by symmetry and locality, Nature Physics18, 283 (2022)
2022
-
[37]
S. N. Hearth, M. O. Flynn, A. Chandran, and C. R. Lau- mann, Unitary k-designs from random number-conserving quantum circuits, Physical Review X15, 021022 (2025)
2025
-
[38]
Knill, Fermionic linear optics and matchgates, arXiv preprint arXiv:quant-ph/0108033 (2001)
E. Knill, Fermionic linear optics and matchgates, arXiv preprint arXiv:quant-ph/0108033 (2001)
2001 arXiv
-
[39]
Jozsa and A
R. Jozsa and A. Miyake, Matchgates and classical simula- tion of quantum circuits, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences464, 3089 (2008)
2008
- [40]
-
[41]
García-Martín, P
D. García-Martín, P. Braccia, and M. Cerezo, Architec- tures and random properties of symplectic quantum cir- cuits, arXiv preprint arXiv:2405.10264 (2024)
2024
-
[42]
D.GrinkoandM.Ozols,Linearprogrammingwithunitary- equivariant constraints, arXiv preprint arXiv:2207.05713 (2022)
2022 arXiv
- [43]
- [44]
-
[45]
Braccia, N
P. Braccia, N. L. Diaz, M. Larocca, M. Cerezo, and D. García-Martín, Optimal Haar random fermionic linear optics circuits, arXiv preprint arXiv:2505.24212 (2025)
2025 arXiv
- [46]
- [47]
-
[48]
M. A. Nielsen and I. L. Chuang,Quantum Computation and Quantum Information(Cambridge University Press, Cambridge, 2000)
2000
-
[49]
Benenti and G
G. Benenti and G. Strini, Computing the distance be- tween quantum channels: usefulness of the Fano represen- tation, Journal of Physics B: Atomic, Molecular and Opti- cal Physics43, 215508 (2010)
2010
-
[50]
D. Maslov, Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures, Physical Review A—Atomic, Molecular, and Optical Physics76, 052310 (2007)
2007
-
[51]
N. L. Diaz, D. García-Martín, S. Kazi, M. Larocca, and M. Cerezo, Showcasing a barren plateau theory beyond the dynamical lie algebra, arXiv preprint arXiv:2310.11505 (2023)
2023 arXiv
-
[52]
H. Zhu, R. Kueng, M. Grassl, and D. Gross, The clif- ford group fails gracefully to be a unitary 4-design, arXiv preprint arXiv:1609.08172 (2016)
2016 arXiv
-
[53]
M. West, N. Dowling, A. Southwell, M. Sevior, M. Usman, K. Modi, and T. Quella, A graph-theoretic approach to chaos and complexity in quantum systems, arXiv preprint arXiv:2502.16404 (2025)
2025
-
[54]
R. King, K. Wan, and J. McClean, Exponential learning advantages with conjugate states and minimal quantum memory, arXiv preprint arXiv:2403.03469 (2024)
2024 arXiv
-
[55]
Haah, Short remarks on shallow unitary circuits, arXiv preprint arXiv:2504.14005 (2025)
J. Haah, Short remarks on shallow unitary circuits, arXiv preprint arXiv:2504.14005 (2025)
2025
-
[56]
Webb, The clifford group forms a unitary 3-design, Quantum Information and Computation16, 1379 (2016)
Z. Webb, The clifford group forms a unitary 3-design, Quantum Information and Computation16, 1379 (2016)
2016
-
[57]
Bertoni, J
C. Bertoni, J. Haferkamp, M. Hinsche, M. Ioannou, J. Eis- ert, and H. Pashayan, Shallow shadows: Expectation esti- mation using low-depth random Clifford circuits, Physical Review Letters133, 020602 (2024)
2024
- [58]
-
[60]
Montanaro and R
A. Montanaro and R. de Wolf, A survey of quantum prop- erty testing, arXiv preprint arXiv:1310.2035 (2013)
2013 arXiv
-
[61]
Fulton and J
W. Fulton and J. Harris,Representation Theory: A First Course(Springer, 1991)
1991
-
[62]
Wiersema, E
R. Wiersema, E. Kökcü, A. F. Kemper, and B. N. Bakalov, Classification of dynamical lie algebras of 2-local spin sys- tems on linear, circular and fully connected topologies, npj Quantum Information10, 110 (2024)
2024
-
[63]
Collins and P
B. Collins and P. Śniady, Integration with respect to the haar measure on unitary, orthogonal and symplectic group, Communications in Mathematical Physics264, 773 (2006)
2006
-
[64]
Collins and S
B. Collins and S. Matsumoto, On some properties of or- thogonal weingarten functions, Journal of Mathematical Physics50(2009)
2009
-
[65]
Montealegre-Mora and D
F. Montealegre-Mora and D. Gross, Duality theory for clifford tensor powers, arXiv preprint arXiv:2208.01688 (2022)
2022
-
[66]
Zee,Group theory in a nutshell for physicists, Vol
A. Zee,Group theory in a nutshell for physicists, Vol. 17 (Princeton University Press, 2016). Appendix A: Invariant states and preserved bilinear forms Theorems 1 and 2 of our results apply specifically to the case where there is an invariant state|Ψ⟩∈H⊗2. In this brief append...
2016
-
[67]
Prepare a stateρ∈L(H⊗k⊗H anc),
-
[68]
Exposeρto black-box process that with probabilityλappliesU ⊗k withU∼Eand with1−λappliesU ⊗k with U∼F,
-
[69]
Implement a POVMΠ ={ΠE,ΠF},
-
[70]
So, one guessesEwith probabilityp(ΠE|U∼X) = Tr[ρ X ΠE], whereρX = (ϕ(k) X ⊗I anc)(ρ)
Upon measuringΠX for someX∈{E,F}, guess thatρwas evolved byU∼X. So, one guessesEwith probabilityp(ΠE|U∼X) = Tr[ρ X ΠE], whereρX = (ϕ(k) X ⊗I anc)(ρ). The probability of success in Algorithm 1 is psucc(ρ,Π) =p(U∼E)p(Π E|U∼E) +p(U∼F)p(Π F|U∼F) =λp(Π E|U∼E) + (1−λ)p(Π F|U∼F).(B1)...
-
[71]
projectivelyG-invariant
Bounding circuit depth We begin by focusing on ensembles over quantum circuits with restricted depth. LetEL be an arbitrary ensemble of depth-Lcircuits inG⊆U(H). By this we mean we consider circuits withLtime-steps, where each gate takes a single time-step, and gates acting on...
-
[72]
Consider any ensembleES N over elements of the formU= QN ℓ=1 exp(iθℓHℓ), where the generators are Paulis{Hℓ}ℓ⊂S⊂g
Bounding gate count Before coming to the proof of Theorem 2, we establish some notation. Consider any ensembleES N over elements of the formU= QN ℓ=1 exp(iθℓHℓ), where the generators are Paulis{Hℓ}ℓ⊂S⊂g. Here,gdenotes the Lie algebra associated 16 FIG. 4. A connected component...
-
[73]
(9) by evaluating Eq
Pauli-compatible groups In this section we derive Eq. (9) by evaluating Eq. (3) in the case of a Pauli-compatible group generated by a set Sof Pauli strings. We can evaluate the expectation value in Eq. (3) using the basis of quadratic symmetries provided in the proof of Theor...
-
[74]
Matchgate group Having established in the Appendix A the existence of a matchgate-invariant bilinear form, we are in a position to apply Theorem 1, and therefore wish to evaluate the right hand side of the bound Eq. (3). Let us take the local perturbation to be a PauliXgate on...
-
[75]
Note that from Eq
The orthogonal and symplectic groups In this section we apply Theorem 1 to the the orthogonal and symplectic groups, O(d) ={U∈U(d) :U TΩOU= Ω O}andSP(d/2) ={U∈U(d) :U TΩSPU= Ω SP},(C9) 21 where we takeΩ O =1 ⊗2 andΩ SP =1⊗iY 1 [35, 41]. Note that from Eq. (C9) both the orthogo...
-
[76]
Interestingly, and in contrast to the other groups we consider, we are here able to rule out sublinear-depth approximate designs only atk⩾8
Clifford group Next we turn to the important case of the Clifford group. Interestingly, and in contrast to the other groups we consider, we are here able to rule out sublinear-depth approximate designs only atk⩾8. The core technical result that we will need is Lemma 4(Corollar...
-
[77]
real”, “complex
Mixed-unitary To finish, we consider the case of mixed-unitary circuits, which we recall to consist of elements of the formU⊗U∗, whereUisann-qubitunitary. Wehaveaninvariantstate|Φ⟩∈H, theBellstateacrossthefirstandsecondgroupingsofn qubits, which is manifestly mixed-unitary-inv...
-
[78]
Complex:χV is not real-valued;Vdoes not have anyG-invariant non-degenerate bilinear forms
-
[79]
Real:V=V 0⊗R C,V 0 a representation overR;Vhas aG-invariant symmetric nondegenerate bilinear form
-
[80]
HereχV = Tr◦RV :G→Cis thecharacterofV, i.e., the trace of the representing elementsR V :G→L(V)
Quaternionic:χV is real, butVis not;Vhas aG-invariant antisymmetric nondegenerate bilinear form. HereχV = Tr◦RV :G→Cis thecharacterofV, i.e., the trace of the representing elementsR V :G→L(V). In fact, it is not too hard to see explicitly that for an irreducible representation...
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.