Mathematical remark

Blanc–Docter–Strassle–Tan 2608.19158v1 (quantum speedups require structure or depth) miss E vs B2-SIZE(O(n)).

File-checked: arxiv.org/html/2608.19158v1 (1463411 bytes; plaintext 183624 chars); submitted 2026-08-19 v1; FOCS 2026 as Atom comments; abs primary-subject quant-ph / listed in cs.CC. Official HTML used; ar5iv returned the abs page. Authors: Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan (Stanford). Li-Yang Tan is not Jiatu Li of the unretrieved STOC 2022 3.1n paper. Word-boundary counts: B2=0, P/poly=0, ETH=0, SETH=0, gate=0, algebrization=0, relativization=0; query=219, quantum=172, oracle=82, BQP=14, BPP=7, circuit=31 (quantum oracle circuits / QNC), SIZE=28 (set size / quantum-circuit size).

Model: t-query d-round (equivalently t-parallel d-round) quantum algorithms with a phase oracle on an N-bit string. Paper N is oracle length. Resource is queries, not 1-output B2 gates. Simulation is average-case on a 1−δ fraction of inputs. The simulation conjecture (folklore / [3,4,1] as cited) asks for a poly(t)-query classical algorithm on most inputs. The Aaronson–Ambainis conjecture is a bounded low-degree polynomial influence statement; Claim A.1 records AA ⇒ Conjecture 1 (heavy query weights); Claim 9.3 records Conjecture 1 ⇒ simulation.

Theorem 4 / Theorem 9: a t-parallel d-round algorithm has a coordinate of expected query weight ≥ 2^{−Ω(d²)} (t log(1/δ)/ε)^{−Ω(d)}; sufficiently regular algorithms are ε-close to their mean on a 1−δ fraction of inputs. Lemma 4.7: a classical decision tree of depth poly(t,1/η,log(1/δ)) makes the restricted algorithm η-regular on most paths. Theorem 1: T = 2^{O(d²)} (t log(1/δ)/ε)^{O(d)} classical queries suffice. Settles the strong simulation conjecture for constant-round algorithms; exponential unstructured separations would need d ≥ t^{Ω(1)} rounds. Simon / Period-Finding / Forrelation / Yamakawa–Zhandry [61] as cited are nonadaptive, so they do not counterexample Theorem 1 on unstructured total functions. Theorem 2 (assuming Conjecture 2): PromiseBPP^O ≠ PromiseBQP^O for a random oracle iff unrelativized. Theorem 3 (unconditional): the same equivalence for PromiseQNC vs PromiseQuasiBPP. Remark 2.2: BQP has no known complete problems, so the equivalences use promise classes. Section 11 records a later t^{O(d)} round-preserving improvement in an unopened note [15].

Why this misses the conjecture: (1) Average-case classical-vs-quantum query simulation is not unrestricted 1-output B2 size. (2) Completing SAT ⊄ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing Forrelation / Simon ⊄ SIZE(O(N)) would be a different E strengthening; the file does not name C_B2. (4) PromiseQNC is polynomial-size polylog-depth quantum circuits. A B2 circuit of size O(n) may have depth Θ(n). PARITY has B2-size n−1. (5) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5. Random-oracle / query arguments do not evade those circuit barriers.

Finite, not a proof (work/code/blanc_qspeed_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; query stand-in T ≈ 2^{d²} t^d is a classical query count, not C_B2 (d=1 t=16: T=32; d=3 t=16: T≈2.1e6).

Related already-scoped quantum-query files: Aaronson–Ambainis Forrelation 1411.5729v1; Bravyi–Gosset–König 1704.00690v1; Joshi et al. 2512.14643v4.

No P vs NP claim. GKW-era 3.1n sentence left unchanged (Li-Yang STOC 2022 still not file-verified).