{"id":"146e0709-0724-4270-9976-b7a5b93f93e8","arxiv_id":"2607.20919","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Constant-depth brickwork random unitary circuits and random Pauli rotations on n qubits have constant spectral gap, independent of n and uniform over all unitary representations.","lead":"This paper proves that several natural random walks on the unitary group of n qubits, including the brickwork random unitary circuit, have spectral gaps bounded below by constants that do not shrink as the number of qubits grows. If correct, it resolves a long-standing question about how quickly random constant-depth circuits converge to uniform (Haar) randomness.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unshipped Sp(6;F2) computation in Prop 2.2 is the load-bearing risk; Eq. (4.10) has a repairable constant typo.","rationale":"The reader's weakest assumption correctly identifies the computer-assisted Prop 2.2 as the load-bearing step. My independent reading of the proof chain confirms that Theorems 2.7, 2.14, and 4.1 all reduce to this 3/10 bound; the rest of the argument is a sequence of standard lemmas (Knabe, detectability lemma, triangle comparison) with careful constants. I found one additional defect, an inconsistent constant in Eq. (4.10), but it is a typo: the equality to 1 - 1/2^5 is exactly what one gets from the 1 - 1/16 bound of Thm 3.16. Thus the proof is repairable in place. The lack of shipped code for Prop 2.2 is a genuine reproducibility concern, but the step-by-step procedure and independent character-table checks make the computation auditable; releasing the code would fully settle it. I do not see grounds to move the reader's ACCEPT verdict.","tokens_in":23468,"tokens_out":38530,"duration_ms":298891,"concrete_test":"Implement Steps i-viii for G = Sp(6;F2) in GAP or Magma using exact rational arithmetic, and verify: (1) the eigenspectrum of Pi(rho_reg|H1,2) + Pi(rho_reg|H2,3) is exactly {0, 6/10, 8/10, 9/10, 1, 11/10, 12/10, 14/10, 2}; (2) for every one of the 30 irreps, the largest non-trivial eigenvalue of (Pi(rho|H1,2)+Pi(rho|H2,3))/2 is at most 7/10. In the same pass, recompute Eq. (4.10) with the two candidate constants 1/24 and 1/16 to confirm that only 1/16 makes the displayed equality to 1 - 1/2^5 valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The entire chain from the Clifford brickwork gap (Thm 2.14) to the brickwork unitary gap (Thm 4.1) rests on the computer-assisted bound in Prop 2.2: for the two embeddings of Sp(4;F2) in Sp(6;F2), the essential norm of (Pi(H1,2)+Pi(H2,3))/2 is at most 7/10. The manuscript describes the Julia implementation step-by-step and independently verifies the GAP character table via class-algebra constants, but the code itself is not reproduced. A bug in the enumeration, class algebra, character-table matching, or eigenvalue routine would invalidate Theorems 1.3(3)-(4). The 10 relevant irreps are identified by character multiplicities, and the final spectral data are claimed rational; the decisive unshipped artifact is the exact factorization of the characteristic polynomials in Step viii. A secondary, easily repaired issue: in Eq. (4.10), the paper writes 1 - 1/24 + 2/2^6 = 1 - 1/2^5; the equality is false unless the first term is 1 - 1/16, the bound actually supplied by Thm 3.16. With 1/16 the subsequent constant chase is consistent, so this is a typo rather than a structural flaw.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves constant lower bounds on the spectral gap of several random walks on SU(2^n) and on Clifford groups, uniform over all finite-dimensional unitary representations. The main results are Theorem 1.3: the random Pauli rotation on SU(2^n) has gap > 2^{-4}, the random Pauli Clifford rotation on Cl(n) has gap > 2^{-3}, the brickwork random unitary circuit on SU(2^n) has gap > 2^{-53}, and the brickwork random Clifford circuit on Cl(n) has gap > 2^{-7}. The proofs combine Knabe/Caputo-type local-to-global arguments, the detectability lemma, a computer-assisted exact character computation for Sp(6;F_2) in Proposition 2.2, and an eigenvalue analysis of a t=4 tensor representation for random Pauli rotations. A consequence noted in the paper is that a brickwork random unitary circuit of depth O(nt + log 1/epsilon) forms an approximate unitary t-design with relative error epsilon.","tokens_in":23719,"tokens_out":16584,"duration_ms":135407,"significance":"If correct, these results are a significant advance: they give the first spectral gap bounds for efficient random walks on SU(2^n) that are independent of n and of the representation, improving on previous bounds that decayed as 1/polylog(t) or worse. The constants are explicit and the arguments use exact rational arithmetic, with no fitted parameters. The computer-assisted part of the proof is described in enough procedural detail that an independent implementation is feasible, and the manuscript verifies the downloaded character table through independent class-algebra checks. The proof strategy, using Clifford walks as an intermediate step and then boosting to the full unitary group, is original and well matched to the problem.","major_comments":[{"comment":"The constant 3/10 bound for the two embeddings of Sp(4;F_2) in Sp(6;F_2) is the load-bearing input for Theorems 2.14 and 4.1, and hence for the brickwork Clifford and brickwork unitary gap claims in Theorem 1.3(3)-(4). The manuscript describes the Julia computation step-by-step and verifies the character table, but it does not include the code, the exact characteristic polynomials, or the resulting eigenvalue data. Since the paper presents this as a proof rather than as numerical evidence, the computation should be made independently checkable by shipping the code or the exact intermediate data (for example, as ancillary files). Without that, a referee or reader cannot verify Proposition 2.2 from the manuscript alone.","section":"Section 2.1, Proposition 2.2"},{"comment":"The proof of Proposition 2.2 states that for each of the five concrete representations, the roots of the relevant characteristic polynomial 'turn out to be all rational', and that the eigenspectrum of the regular representation is {0, 6/10, 8/10, 9/10, 1, 11/10, 12/10, 14/10, 2}. These data are the actual content of the finite computation, but they are not reported. Please list the characteristic polynomials, the rational roots, or the code that produces them; this would make the verification independent of rerunning the full enumeration.","section":"Section 2.1, Step viii"}],"minor_comments":[{"comment":"The calculations of ||Pi_xi Omega||^2 and ||Pi_xi Gamma(Omega)||^2 are summarized with 'after some algebra'. The class algebra multiplication function is given, and the trace table is provided, but the intermediate algebra is not shown. For a published proof, it would be helpful to include a derivation or a short supplementary notebook so that the reader does not have to reconstruct the trace evaluation.","section":"Section 3, equations (3.45)-(3.46)"},{"comment":"The identity 1 - 1/2^4 + 2/2^6 = 1 - 1/2^5 is correct as written, since 1/2^4 = 2/2^5 and 2/2^6 = 1/2^5, so the expression equals 1 - 1/2^5. No typo is present here.","section":"Equation (4.10)"},{"comment":"The description says 'Select any element' when building conjugacy classes. It would be clearer to specify that the selection is deterministic or that the choice does not affect the subsequent calculation; the surrounding algorithm already makes this clear, but a one-sentence clarification would help.","section":"Section 2.1, Step ii"},{"comment":"In the reference [WWT+], the author list contains a stray comma before 'and Rachel Abbott'; please correct this small formatting issue.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The mathematical content is strong and the main claims are well supported by the written arguments, with the exception of the computer-assisted Proposition 2.2, which is described but not shipped. I recommend requesting the code or exact data as a condition of publication. This is not a matter of mathematical correctness so much as of verifiability: the paper explicitly presents the calculation as a proof, so the proof artifacts should be available. The manuscript also makes appropriate use of external lemmas with independent sources, so I see no circularity concern. If the authors provide the requested computational artifacts, I would expect the paper to be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is the first constant lower bound on the spectral gap for the two walks named in the title, uniform over all finite-dimensional unitary representations and independent of n. It resolves a question that previously had only polylog or vanishing bounds, and it converts the result into an O(nt + log 1/epsilon) depth for approximate t-designs under relative error. The result is real.\n\nThe architecture is clean: prove a constant gap for brickwork Clifford circuits using a Knabe-type boost from a three-qubit local gap, derive the random Pauli rotation gap from a Kac-walk comparison, then combine via the detectability lemma and a Clifford-brickwork separator to get the brickwork unitary gap. The local three-qubit Clifford gap rests on a computer-assisted exact computation over Sp(6;F2). This is the right tool, and they handle it honestly: exact rational arithmetic, independent verification of the GAP character table via class-algebra constants, and a step-by-step description of the Julia implementation. The 3/10 seed bound is the load-bearing piece; the unshipped code is the one thing I would want before signing off. It is auditable, but the factorization in Step viii is the kind of step where a coding error would invalidate everything downstream. That is a moderate reservation, not a fatal one.\n\nTwo smaller points. Equation (4.10) as written has an arithmetic typo: 1 - 1/24 + 2/2^6 is not 1 - 1/2^5; with the correct 1/16 from Theorem 3.16 it works, so this is cosmetic. The 'after some algebra' in (3.45)-(3.46) is compressed, but the S4 class algebra multiplication rule is given and Mathematica code supplied, so a motivated reader can reproduce it in minutes.\n\nThe citation pattern is clean. The self-citations to [CHH+25] and [HLT25] are for lemmas with independent sources, and the constants are derived, not fitted. The Aldous-type conjecture in 3.48 is explicit and separate from the theorems.\n\nVerdict: this deserves a serious referee. I would send it out, and I would specifically ask the referee to reproduce or at least independently re-implement the Sp(6;F2) calculation. With that piece verified, the paper is a solid accept.","headline":"First constant spectral gap for random Pauli rotations and brickwork random unitary circuits, with a clean proof that leans on one auditable computer-assisted calculation.","tokens_in":24264,"tokens_out":2521,"would_cite":true,"duration_ms":21458,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B15","81P45"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"Random Pauli rotations and brickwork random unitary circuits are proven to have constant spectral gaps, independent of n and uniform over all representations.","keywords":["spectral gap","random unitary circuits","brickwork circuits","unitary t-designs","Clifford group","Pauli rotations","Kac's random walk","Knabe method"],"falsifier":"Recompute the spectrum of $(\\Pi(\\rho|H_{1,2}) + \\Pi(\\rho|H_{2,3}))/2$ in the regular representation of $\\mathrm{Sp}(6;\\mathbb{F}_2)$ with exact arithmetic, independently of the paper's implementation; if any eigenvalue exceeds $7/10$ (equivalently $1-3/10$), the seed of the proof fails. A softer check: numerically diagonalize the depth-2 brickwork walk in the $t=2$ tensor representation for a few modest $n$ and compare the gap with $2^{-53}$.","tokens_in":23238,"feed_emoji":"🎲","tokens_out":18758,"duration_ms":148887,"temperature":0.7,"pith_summary":"This paper tries to establish that several basic random quantum processes mix at a speed that does not depend on the number of qubits. For the random walk that picks a Pauli operator and a random angle, and for the brickwork random unitary circuit (one layer of random two-qubit gates), it proves explicit constant lower bounds on the spectral gap: $\\Delta(\\nu_{\\mathrm{RPR}}, \\mathrm{SU}(2^n)) > 2^{-4}$ and $\\Delta(\\nu_{\\mathrm{BRUC}}, \\mathrm{SU}(2^n)) > 2^{-53}$, with $2^{-3}$ and $2^{-7}$ for the Clifford variants. The bounds are uniform over every finite-dimensional unitary representation, so in particular the walks converge at a constant rate in the tensor representations that define unitary $t$-designs. This matters because previous gaps for efficiently implementable walks all decayed with the representation or with $n$; a constant gap means shallow circuits can be guaranteed to approximate Haar-random unitaries. The paper's route is a local-to-global gap argument whose seed is a computer-assisted calculation on a finite symplectic group.","feed_headline":"Random circuits keep a constant mixing rate on any number of qubits","feed_subtitle":"Mixing no longer slows as qubits grow; shallow brickwork circuits give approximate unitary t-designs.","key_machinery":"The central quantity is the spectral gap of a random walk's averaging operator: one minus the largest eigenvalue on nontrivial representations, and a constant gap means every step shrinks the distance to Haar or uniform Clifford measure by a fixed fraction. The principal engine is the Knabe local-to-global method, which boosts a gap proven for a small block to a gap on the whole chain: the three-qubit seed (Proposition 2.2) gives a $3/5$ local gap for pairs of neighbouring two-qubit Clifford projectors, leading to an $O(1/n)$ gap for the averaged nearest-neighbour Clifford walk; the detectability lemma (Lemma 1.16, via simplified quantum-union-bound proofs) then converts averaged walks into sequential depth-2 brickwork walks with a constant gap. The seed is a computer-assisted exact calculation on the finite symplectic group $\\mathrm{Sp}(6;\\mathbb{F}_2)$, which describes the three-qubit Clifford group modulo its normal Pauli subgroup, showing that the averaged two-qubit Clifford projectors have essential norm at most $7/10$. Independently, the Random Pauli Rotation gap uses the single-qubit constant $\\Delta_\\Theta = 5/4$ inherited from Kac's walk on $\\mathrm{SO}(3)$, boosted to $n$ qubits by counting anticommuting Pauli pairs. The brickwork unitary circuit bound splices the Clifford and Pauli-rotation gaps through the same detectability-lemma conversion.","core_discovery":"The central claim is Theorem 1.3: the spectral gap of each of the four walks is bounded below by a constant depending only on the walk, not on $n$ or the representation. Concretely, $\\Delta(\\nu_{\\mathrm{RPR}}, \\mathrm{SU}(2^n)) > 2^{-4}$, $\\Delta(\\nu_{\\mathrm{RPCR}}, \\mathrm{Cl}(n)) > 2^{-3}$, $\\Delta(\\nu_{\\mathrm{BRUC}}, \\mathrm{SU}(2^n)) > 2^{-53}$, and $\\Delta(\\nu_{\\mathrm{BRCC}}, \\mathrm{Cl}(n)) > 2^{-7}$ for every $n$ and every finite-dimensional unitary representation. The discovery is not just that these gaps are positive, but that they stay bounded away from zero as $n$ grows; in prior work the best lower bounds for efficiently implementable walks decayed like $1/\\mathrm{polylog}(t)$ in the tensor representations relevant to designs. A constant gap means that after $k$ steps the essential norm of the moment operator is at most $(1-\\Delta)^k$, so the walk reaches any fixed accuracy in a number of steps independent of the system size. The proof obtains the two Clifford gaps first via the Knabe local-to-global boost from a $3/10$ local gap, then uses the Pauli-rotation gap to lift the Clifford result to the full unitary group, closing with the detectability-lemma conversion between averaged and convolutional circuit ensembles.","pith_inferences":["The constants $2^{-53}$ and $2^{-7}$ are built from deliberately loose choices ($m=2^{10}$ and comfortable roundings), so the true gaps are probably orders of magnitude larger; diagonalizing the $t=2$ moment operator for modest $n$ would likely reveal a far better brickwork constant.","The proof's architecture—computer-certified local gap on a Clifford quotient, then lifting to the full unitary group—appears portable to other constant-degree circuit geometries, with the final constants depending on the interaction graph rather than on $n$.","A concrete test of tightness in the Pauli-rotation walk is the $t=4$ tensor representation: Conjecture 3.48 predicts the exact gap $2n(2n-3)/(8(4^n-1))$ for $n\\ge 3$, so computing the largest nontrivial eigenvalue there would confirm or refute the conjectured bottleneck."],"forward_implications":["A brickwork random unitary circuit of depth $O(nt + \\log(1/\\epsilon))$ is an approximate unitary $t$-design with relative error $\\epsilon$, via the standard gap-to-design conversion; the depth is linear in $t$ and $n$ and logarithmic in the desired accuracy.","The Random Pauli Rotation walk reaches essential-norm accuracy $\\epsilon$ in $O(\\log(1/\\epsilon))$ steps for any representation, so its mixing time does not grow with the number of qubits.","The brickwork Clifford circuit mixes on $\\mathrm{Cl}(n)$ at a constant rate, giving a constant-depth approximation to the uniform Clifford distribution; previously no efficiently implementable Clifford or unitary walk was known to have a constant spectral gap.","High-order tensor representations $U^{\\otimes t} \\otimes \\bar{U}^{\\otimes t}$ mix at the same constant rate for all $t$, so the design-relevant moments do not experience a $t$-dependent slowdown."],"supporting_citations":[{"why":"Knabe's local-to-global gap bound is the main tool that turns the three-qubit $3/10$ local gap into a gap on the whole chain in Theorem 2.7.","marker":"[Kna88]"},{"why":"Caputo's triangle method for Kac's walk is adapted in Lemma 3.4 to boost a single-qubit rotation gap to an $n$-qubit Random Pauli Rotation gap.","marker":"[Cap08]"},{"why":"Introduces the Random Pauli Rotation measure and supplies the single-qubit gap $\\Delta_\\Theta = 5/4$ (its Corollary 4.2) that Theorem 3.16 quotes.","marker":"[HLT25]"},{"why":"Source of the simplified detectability lemma and quantum union bound stated as Lemma 1.16, used to convert between averaged and sequential circuit ensembles.","marker":"[AAV16, OV22]"},{"why":"Supplies the compiled form of the detectability-lemma conversion used in Section 4, along with the prior polylogarithmic gap bound that this paper improves to a constant.","marker":"[CHH+25]"},{"why":"Identifies the Clifford group modulo Pauli operators with the symplectic group $\\mathrm{Sp}(2n;\\mathbb{F}_2)$, reducing the seed calculation to the finite group $\\mathrm{Sp}(6;\\mathbb{F}_2)$.","marker":"[Haa17]"}],"fun_headline_variants":["Constant spectral gap: random circuits mix uniformly on any n","Random circuits keep mixing rate constant as qubits grow","Spectral gap fixed: brickwork circuits mix independent of size","No size slowdown: random unitary circuits have constant gap"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the computer-assisted calculation of Proposition 2.2—that the averaged two-qubit Clifford subgroups inside the three-qubit Clifford group mod its Pauli center have a $3/10$ spectral gap—is correct, because that one number seeds every later gap bound in the paper.","fun_headline_variants_meta":{"raw":{"variants":["Constant spectral gap: random circuits mix uniformly on any n","Random circuits keep mixing rate constant as qubits grow","Spectral gap fixed: brickwork circuits mix independent of size","No size slowdown: random unitary circuits have constant gap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000627,"raw_usage":{"total_tokens":2956,"prompt_tokens":1056,"completion_tokens":1900,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":1834}},"tokens_in":672,"tokens_out":1900,"duration_ms":12514,"temperature":1.0,"reasoning_tokens":1834,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:32:28.862238+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the spectrum of $(\\Pi(\\rho|H_{1,2}) + \\Pi(\\rho|H_{2,3}))/2$ in the regular representation of $\\mathrm{Sp}(6;\\mathbb{F}_2)$ with exact arithmetic, independently of the paper's implementation; if any eigenvalue exceeds $7/10$ (equivalently $1-3/10$), the seed of the proof fails. A softer check: numerically diagonalize the depth-2 brickwork walk in the $t=2$ tensor representation for a few modest $n$ and compare the gap with $2^{-53}$.","supporting_citations":[],"review_version":2}