{"id":"fba649a8-6aa7-4786-b183-7c7f23a40a23","arxiv_id":"2608.13491","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every fixed k and error tolerance, strong approximate unitary k-designs are constructed in optimal Theta(log n) depth on the n system qubits using random perfect-matching layers.","lead":"Random quantum circuits built from random perfect matchings are shown to mimic true randomness even for queries to the inverse, transpose, and conjugate of the unitary, in optimal logarithmic depth and without extra qubits. This resolves an open part of the strong fast-scrambling question in quantum information.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The construction's strong-design guarantee rests on imported Proposition 1, which equates mixed-sign two-query comb error with Pauli-transition TVD; this reduction is not proved here and is essential to the log-depth shell.","rationale":"The reader identified Proposition 1 as the weakest assumption, and I agree. The paper's own contribution, the uniform Pauli mixing bound for the perfect-matching ensemble, is written out in full: the support-chain reduction, the grand coupling, the growth/persistence/contraction lemmas, and the constant bookkeeping in Theorem 1 are internally consistent. I found no fitted parameters and no circular reasoning. The remaining steps use imported results (weak gluing, strong gluing, 1D strong designs), but these are standard in the area and are cited precisely; the reduction in Proposition 1 is the one place where the novel Pauli-mixing result is converted into the operational strong-design guarantee. If that conversion is not exactly as stated, Theorem 2's shell and hence Theorem 3's optimal-depth claim do not follow. The concrete check of re-deriving Prop 1 or computing Phi_E for n=4 would settle whether the concern lands; absent that, CONDITIONAL is the right verdict. My recommendation is UNCHANGED: the reader's conditional assessment already reflects this dependence.","tokens_in":45084,"tokens_out":22335,"duration_ms":210521,"concrete_test":"Re-derive Proposition 1 from the comb definition in Eq. (4) and Appendix A.1.1, and isolate the step where the mixed-sign two-query output state is expressed solely through the Pauli transition distribution p_E(·|P). As a supplementary check, compute the second-moment channel Phi_E^{(1,1)} of the n=4 perfect-matching ensemble in the Pauli basis: if any off-diagonal matrix element (not determined by the p_E(Q|P) marginals) is nonzero, or if the optimal two-query comb advantage from an SDP exceeds max_P TVD(p_E(·|P), pi) by more than a numerical tolerance, the reduction in Proposition 1 fails for this ensemble and the shell construction loses its mixed-sign guarantee.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is Proposition 1 (Section II.D, Eq. (6)), imported from Ref. [1]: for an ensemble invariant under conjugation, transposition, and random single-qubit Pauli rotations at input and output, robustness against every fixed-word adaptive two-query comb with one query from {U,U^T} and one from {U^*,U^†} is claimed to equal max_P TVD(p_E(·|P), pi). The paper verifies these symmetries for the perfect-matching ensemble and proves the worst-case TVD bound (Theorem 1), but it does not prove the reduction. If a two-query comb with quantum memory can exploit second-moment information not captured by the Pauli transition distribution (e.g., off-diagonal coherence of the mixed-moment channel Phi_E^{(1,1)} in the Pauli basis), then the perfect-matching shell's mixed-sign error could exceed the TVD. Because Theorem 2 uses exactly this equality to build the strong 2-design shell, and Theorem 3 sandwiches the k-design with two such shells, a failure of Proposition 1 would invalidate the Theta(log n) strong k-design claim. The paper's Section VI discloses LLM-assisted gap-filling without identifying which gaps were filled; this imported reduction is a natural candidate. No internal inconsistency in the Markov-chain proof of Theorem 1 was found; the concern is the unproved bridge from Pauli mixing to quantum comb indistinguishability.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs strong approximate unitary k-designs on n physical qubits with all-to-all circuit depth Θ(log n), resolving the unitary-design part of the strong fast-scrambling question left open in Ref. [1]. The new ingredient is the perfect-matching ensemble: each layer pairs the qubits by a uniformly random perfect matching and applies independent Haar-random two-qubit gates. The main technical result, Theorem 1, proves that after T = O(log(n/η)) layers every nonidentity Pauli string has its induced Pauli transition distribution within total variation distance η of the Haar-uniform distribution. The proof reduces the Pauli chain to a support Markov chain, then analyzes it with a monotone grand coupling combining growth, persistence, and geometric contraction estimates. Theorem 2 composes this ensemble with an independent weak relative-error 2-design to obtain a logarithmic-depth strong 2-design shell, and Theorem 3 sandwiches two brickwork layers of local strong k-designs between two such shells via an imported strong gluing lemma, yielding depth C(1 + k log^7(2k)) log(nk/ε). The result is stated for even n, fixed query words, measurable error in full trace norm, and all-to-all connectivity, and it matches the known Ω(log n) light-cone lower bound.","tokens_in":45265,"tokens_out":20333,"duration_ms":193678,"significance":"If the result is correct, it is a substantial advance: it achieves the optimal Θ(log n) depth for strong unitary designs using only the system qubits, removing the extra logarithmic factor and the ancilla overhead of the previous construction. The support-chain reduction and the grand-coupling argument for worst-case Pauli inputs are genuine technical contributions, and the derivation is parameter-free in the sense that the constants are explicit rather than fitted. I found no internal inconsistency in the Markov-chain proof of Theorem 1: the growth, persistence, and contraction lemmas are internally coherent, and the error budgeting in the final coalescence argument checks out. The numerical simulations support the logarithmic mixing claim, though they do not substitute for the proof. The main caveat is that the bridge from Pauli mixing to quantum comb indistinguishability, Proposition 1, is imported from an unpublished preprint and is not proved here; the final Θ(log n) claim is conditional on that reduction. This is a correctness-risk concern, not a circularity: I saw no place where the paper assumes the target result.","major_comments":[{"comment":"The strong 2-design shell and hence the final Θ(log n) claim rest on the imported equality between mixed-sign two-query comb error and worst-case total variation distance of the Pauli transition distribution. The manuscript verifies the required symmetries for the perfect-matching ensemble but does not prove the reduction itself, and Eq. (6) is stated without a derivation. Since a two-query comb with quantum memory could in principle exploit off-diagonal matrix elements of the mixed-moment channel Φ_E^{(1,1)} in the Pauli basis, the equality is not self-evident; a failure of this reduction would invalidate Theorem 2 and Theorem 3. Please include a self-contained proof of Proposition 1 (or of the precise form needed here), or replace the reference to the unpublished preprint [1] with a published version containing the proof, and state explicitly which hypotheses of Ref. [1] are being imported. A concrete way to close the gap would be to show that under the stated symmetries Φ_E^{(1,1)} is completely determined by its diagonal Pauli matrix elements.","section":"Section II.D, Proposition 1 and Eq. (6)"},{"comment":"The disclosure states that GPT-5.6 Pro was used to help fill gaps in the full proof of Pauli mixing, but it does not identify which gaps were filled. Because Theorem 1 is the central new technical contribution and its proof is where the paper's main novelty lies, the absence of a precise account of which steps were machine-generated makes it difficult to verify the provenance and completeness of the proof. Please list the specific gaps that were filled, state how each was subsequently verified by the human authors, and attach any additional derivations needed; alternatively, clearly mark the affected steps in the appendix.","section":"Section VI (AI Disclosure)"}],"minor_comments":[{"comment":"The paper uses two normalizations of the measurable error, the full trace norm in Eq. (4) and the half trace distance in Proposition 1, with the conversion stated only in Appendix A.3; a one-line reminder at the point of Eq. (4) would prevent misreading of later constants.","section":"Section II.A, after Eq. (4)"},{"comment":"The displayed definition of h_* is ambiguous: it can be read either as 800 ln(4) · (1+log(21/20))/log(21/20) or as 800 ln(4(1+log(21/20))/log(21/20)); since the two choices differ by more than a constant factor, please add brackets and state explicitly that the chosen value is an absolute constant.","section":"Appendix A.2.3, Corollary 1"},{"comment":"The middle and right subpanels of panels (b) and (c) appear to be identical; if this is intentional, label them accordingly, and otherwise replace the duplicate figure.","section":"Figure 4"},{"comment":"The abstract says arbitrary fixed design order while Theorem 3 requires k ≥ 2; please state the k = 1 case explicitly or qualify the abstract.","section":"Abstract and Theorem 3"},{"comment":"The main theorems depend on two arXiv preprints, Refs. [1] and [32]; please update to published versions if available and, at minimum, cite the specific theorem and lemma numbers in those preprints that provide the imported statements.","section":"References [1] and [32]"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong candidate if the load-bearing Proposition 1 is either proved in the manuscript or backed by a published refereed source; both Ref. [1] and Ref. [32] are unpublished preprints as of this report. Given the Section VI disclosure that an LLM filled gaps in the proof of Pauli mixing, I would advise the editor to require a clear identification of the LLM-filled steps and an independent proof of Proposition 1 before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the paper that probably settles the unitary-design half of the strong fast-scrambling conjecture. For fixed k and error, it gives strong approximate unitary k-designs in Theta(log n) all-to-all depth using only the n system qubits, matching the light-cone lower bound. The hard new part is a worst-case Pauli-mixing bound for the perfect-matching ensemble, proved by reducing the second moment to a support Markov chain and then using a monotone grand coupling. I read the appendix fairly carefully; the chain reduction, the growth/persistence/contraction lemmas, the error budgeting, and the final assembly are detailed and internally consistent. No fitted parameters, no circularity. This is real technical work and the main result deserves to be in the literature.\n\nTwo soft spots, in different sizes. First, the genuinely load-bearing bridge is Proposition 1, imported from Ref [1], which equates robustness against mixed-sign two-query combs with worst-case Pauli-transition TVD for symmetric ensembles. The paper verifies the symmetries for the perfect-matching ensemble but does not prove the reduction. Ref [1] is itself a recent preprint, so the claim chains trust. The stress-test worry about off-diagonal coherence in the (1,1) moment channel is a legitimate thing to check, but it is not a demonstrated flaw: the symmetries are exactly the ones used in Ref [1]'s reduction, and I found no internal contradiction. Still, a referee should ask the authors to either prove Proposition 1 in the appendix or quote a version that is itself published or independently verified.\n\nSecond, Section VI says GPT-5.6 Pro was used 'to help fill gaps in the full proof of Pauli mixing' but does not say which gaps. Given that the core new proof lives in the appendix, this is a real transparency problem. It does not make me doubt the math by itself, but it makes independent verification of those specific steps necessary. The authors should be required to identify the LLM-assisted steps and confirm that a human has checked them in detail.\n\nMinor: the construction is for even n only, and the stated limitations (no controlled queries, no adaptive orientation choice) are honestly listed, so that is scope, not a flaw.\n\nWho should read it: anyone working on random circuits, scrambling, OTOC protocols, or design theory. I would bring it to our reading group and I would cite it if the details survive refereeing. It deserves a serious referee.","headline":"Strong unitary designs in optimal Theta(log n) depth on the system qubits, with a genuinely new worst-case Pauli-mixing proof for perfect-matching circuits; the core looks right, but the result leans on an imported reduction and an undisclosed LLM-gap-filling step that referees should probe.","tokens_in":45894,"tokens_out":4092,"would_cite":true,"duration_ms":34865,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"For any fixed design order and error tolerance, strong approximate unitary designs can be generated in optimal $\\Theta(\\log n)$ all-to-all circuit depth using only the $n$ physical qubits.","keywords":["strong unitary designs","perfect-matching ensemble","Pauli mixing","Markov chain coupling","logarithmic depth circuits","measurable error","quantum scrambling","random circuits"],"falsifier":"Take the depth-$T$ perfect-matching ensemble with $T=\\lceil C_{\\mathrm{mix}}\\log(n/\\eta)\\rceil$ for, say, $n=128$ and $\\eta=0.1$, and compute the optimal distinguishing advantage of a two-query comb that queries one of $\\{U,U^T\\}$ and one of $\\{U^*,U^\\dagger\\}$; compare it against $\\max_P \\mathrm{TVD}(p_{\\mathcal{E}_{\\mathrm{PM}}^{(T)}}(\\cdot|P),\\pi)$. The theorem predicts they agree to within the claimed measurable-error bound, so any experiment or exact simulation exhibiting a strictly larger advantage, or a support chain that fails to coalesce within the predicted time except with probability larger than $\\eta$, would refute it.","tokens_in":44825,"feed_emoji":"⚛️","tokens_out":8812,"duration_ms":81325,"temperature":0.7,"pith_summary":"Unitary designs are finite-moment stand-ins for Haar-random unitaries, and strong designs must be indistinguishable from Haar even when an experiment may query $U$, $U^T$, $U^*$, and $U^\\dagger$ separately with adaptive quantum memory. This paper establishes that, for every fixed design order $k$ and every fixed measurable-error tolerance, strong approximate unitary $k$-designs exist in $\\Theta(\\log n)$ all-to-all circuit depth using only the original $n$ physical qubits, matching the $\\Omega(\\log n)$ light-cone lower bound. The new ingredient is a worst-case Pauli-mixing theorem for the perfect-matching ensemble: after $O(\\log(n/\\eta))$ layers of uniformly random perfect matchings with independent Haar-random two-qubit gates, every nonidentity Pauli operator evolves to a distribution $\\eta$-close in total variation to the Haar-uniform Pauli distribution. That bound controls the mixed forward/reverse two-query sector; composing it with a logarithmic-depth weak relative-error 2-design and strong gluing yields the full strong $k$-design. If true, closed-system dynamics reaching this strong form of scrambling at the earliest possible depth scale would follow, with implications for out-of-time-order correlator growth and black-hole-style information recovery.","feed_headline":"Strong quantum designs reach optimal logarithmic depth","feed_subtitle":"Random perfect-matching layers scramble every Pauli operator to near-Haar-uniform in O(log n) layers, matching the light-cone bound.","key_machinery":"The central object is the perfect-matching ensemble: each layer samples a uniformly random perfect matching of the qubits and applies independent Haar-random two-qubit gates to every matched pair. The analysis reduces operator spreading to a classical Markov chain on nonempty Pauli supports, because after one layer the local $X,Y,Z$ labels are forgotten and each active edge contributes one or two qubits to the new support with probabilities $2/5$ and $3/5$. A monotone grand coupling over the shared matching randomness shows that all singleton chains grow to half density in $O(\\log n)$ layers, stay dense with probability $1-e^{-\\Omega(n)}$, and then contract their gap to the full-support chain geometrically, yielding uniform Pauli mixing in $O(\\log(n/\\eta))$ layers. This gives the mixed-sign security, and the gluing machinery promotes it to a full strong $k$-design in measurable error.","core_discovery":"Theorem 3 states that there are universal constants $c_0,A,C,\\xi_0$ such that for even $n$, $k\\ge 2$, $0<\\varepsilon\\le 1/2$, and $\\log(nk/\\varepsilon)\\le c_0 n$, there is an all-to-all circuit ensemble on the $n$ physical qubits that is a strong $\\varepsilon$-approximate unitary $k$-design in measurable error with depth $d\\le C(1+k\\log^7(2k))\\log(nk/\\varepsilon)$. For fixed $k$ and fixed $\\varepsilon<1/4$ the upper bound is $O(\\log n)$, and a light-cone argument gives $\\Omega(\\log n)$, so the depth is optimal $\\Theta(\\log n)$. The circuit is a two-layer brickwork of local strong $k$-designs realized by one-dimensional random circuits, sandwiched between two global strong 2-design shells; each shell is the composition of a perfect-matching ensemble with an independent weak relative-error 2-design. The perfect-matching part alone controls all mixed-sign two-query experiments, the weak-design part controls the same-sign sector, and strong gluing promotes the combination to arbitrary order $k$.","pith_inferences":["The support-chain proof uses only the randomness of pairing and the local edge-update probabilities, so the same two-phase growth-and-contraction argument is a plausible template for other connectivity graphs such as sparse expanders or small-world networks; checking whether the gap-contraction factor stays below $1$ there would test the transfer.","The composition with a weak relative-error 2-design may be an artifact of the proof route; the paper explicitly asks whether the perfect-matching ensemble alone already forms a strong 2-design in logarithmic depth, and a direct higher-moment analysis could both answer this and improve the $k$-dependence.","Small-scale numerical simulation of the support Markov chain should show the coalescence time of singletons and the full-support chain at approximately $C_{\\mathrm{mix}}\\log(n/\\eta)$; agreement would give independent evidence for the claimed constants, while a visible gap would point to a constant that needs revisiting.","If the Pauli-mixing bound can be lifted to higher moments rather than only the second moment, the same architecture might yield strong designs with a milder order-dependence than the gluing-based factor $1+k\\log^7(2k)$."],"forward_implications":["For fixed $k$ and fixed target error, strong approximate unitary $k$-designs can be produced in $O(\\log n)$ depth on the system qubits alone, saturating the $\\Omega(\\log n)$ lower bound and resolving the system-only strong fast-scrambling question for unitary designs.","Out-of-time-order-correlator growth, and the scrambling behavior behind echo protocols and Hayden-Preskill-type decoding, can occur at logarithmic time within an all-to-all architecture that uses no auxiliary qubits.","The depth factor for higher orders is $d = O((1 + k \\log^7(2k))\\log(nk/\\varepsilon))$, giving explicit (non-optimized) dependence on $k$ and $\\varepsilon$.","The guarantee is information-theoretic and covers fixed-word adaptive combs with arbitrary quantum memory; it does not by itself cover controlled queries, adaptive choice of query orientation, noisy oracles, or physical implementation.","The construction is not computationally secure: the question of system-only strong pseudorandom unitaries in logarithmic depth remains open."],"supporting_citations":[{"why":"Supplies the mixed-query-to-Pauli-TVD reduction, the one-dimensional local strong $k$-design lemma, and the logarithmic lower bound that the construction saturates.","marker":"[1]"},{"why":"Supplies the strong gluing lemma and the same-sign/mixed-sign composition lemma used to assemble the shells into a strong $k$-design.","marker":"[32]"},{"why":"Supplies the logarithmic-depth weak relative-error 2-designs, with weak gluing, that control the same-sign query sector.","marker":"[33]"},{"why":"Introduces the measurable-error notion in which all final strong-design guarantees are stated.","marker":"[36]"},{"why":"Provides the grand-coupling and coupling-inequality methods used to prove uniform Pauli mixing for the perfect-matching ensemble.","marker":"[34]"},{"why":"Supplies the one-dimensional random-circuit result realizing the local strong $k$-design bricks in near-linear depth on their support.","marker":"[38]"},{"why":"Provides the quantum-comb formalism used to define fixed-word adaptive experiments with mixed queries.","marker":"[29]"}],"fun_headline_variants":["Strong unitary designs hit optimal O(log n) depth","Log-depth strong designs from random perfect matchings","Near-Haar scrambling in optimal log depth","Strong designs in logarithmic depth, no ancillas","Perfect-matching layers yield strong designs in O(log n)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument inherits an imported reduction: for an ensemble invariant under conjugation, transposition, and random single-qubit Pauli rotations, robustness against all mixed-sign two-query combs is exactly the worst-case total-variation distance between the induced Pauli transition distribution and the Haar-uniform Pauli distribution; if some fixed-word adaptive comb could distinguish better than that Pauli statistic, the logarithmic-depth strong-2-design shell and hence the $\\Theta(\\log n)$ strong-$k$-design claim would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Strong unitary designs hit optimal O(log n) depth","Log-depth strong designs from random perfect matchings","Near-Haar scrambling in optimal log depth","Strong designs in logarithmic depth, no ancillas","Perfect-matching layers yield strong designs in O(log n)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000804,"raw_usage":{"total_tokens":3572,"prompt_tokens":1022,"completion_tokens":2550,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":2477}},"tokens_in":638,"tokens_out":2550,"duration_ms":41519,"temperature":1.0,"reasoning_tokens":2477,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:53:42.005996+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the depth-$T$ perfect-matching ensemble with $T=\\lceil C_{\\mathrm{mix}}\\log(n/\\eta)\\rceil$ for, say, $n=128$ and $\\eta=0.1$, and compute the optimal distinguishing advantage of a two-query comb that queries one of $\\{U,U^T\\}$ and one of $\\{U^*,U^\\dagger\\}$; compare it against $\\max_P \\mathrm{TVD}(p_{\\mathcal{E}_{\\mathrm{PM}}^{(T)}}(\\cdot|P),\\pi)$. The theorem predicts they agree to within the claimed measurable-error bound, so any experiment or exact simulation exhibiting a strictly larger advantage, or a support chain that fails to coalesce within the predicted time except with probability larger than $\\eta$, would refute it.","supporting_citations":[{"cited_title":"Scrambling Dynamics and Out-of-Time-Ordered Correlators in Quantum Many-Body Systems , volume=","cited_arxiv_id":null,"evidence_quote":"Supplies the one-dimensional random-circuit result realizing the local strong $k$-design bricks in near-linear depth on their support."}],"review_version":1}