{"id":"9b3ed686-46a4-4798-9772-36166f0d9a9c","arxiv_id":"2509.08718","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Adaptive quantum computers, mixing quantum circuits with classical parity processing, provably separate from classical shallow circuits on Hadamard list decoding and also prepare standard quantum states more efficiently.","lead":"This preprint formalizes adaptive quantum computers, which hand some computation to an ordinary machine, and proves they can decode corrupted Hadamard codes with shallow circuits that classical shallow circuits cannot. It also gives adaptive methods for preparing common quantum states such as GHZ, W, and Dicke states, with some runs on IBM hardware.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Classical hardness side of the separation rests on two unproved imported theorems (KL08, BC24) applied to a nonstandard analytic rank; if either fails at F_2 or at the exact parameters, Theorems 3.1.2 and 4.5.3 collapse.","rationale":"The paper's strongest concrete claim is Theorem 4.5.3, and both directions are needed: QNC0[+] must decode the Hadamard code (Chapter 4) and NC0[+]/AC0[+] must not (Chapter 3). The quantum direction is argued in detail with an explicit non-local game, GHZ construction, fanout implementation, and depth count; while some steps are compressed, the circuit is concrete enough to be a plausible constructive upper bound. The classical direction, however, is only as secure as the two imported theorems. The reader's weakest-assumption analysis identified the same pair of external results, and the present stress-test found no additional internal inconsistency in the induction of Section 3.5 beyond that dependency. The application to F_2 with degree d+1 and bias p^{-R0} is exactly where subtle hypotheses in additive combinatorics often hide, so this is the right place to require verification. The model-accounting issue around the Majority reduction in Section 4.6.2 is real but secondary: it affects the AC0[+] half of Theorem 4.5.3 and the claimed Majority circuit, not the primary NC0[+] vs QNC0[+] separation or the abstract's central decoding claim. Because the reader already issued a CONDITIONAL verdict and the identified concern is the same one, no verdict adjustment is needed; the paper should be accepted only after the authors confirm the two external theorems apply at the exact parameters used, or supply self-contained proofs for the special cases needed here.","tokens_in":60703,"tokens_out":40024,"duration_ms":688920,"concrete_test":"Independently verify the two imported theorems against the exact objects used in Sections 3.3–3.5: (1) check that [BC24, Theorem 1.8] applies to the analytic rank of Definition 3.3.2, not merely to tensor analytic rank, over F_2, for all degrees d, with κ,R independent of n,k; (2) check that [KL08, Theorem 4] applies to P(y,v)=⟨v,ϕ(y)−ψ(y)⟩ when deg(P)=d+1 over F_2 and bias(P)≥p^{-R0}, with r independent of n,k. Then recompute the constants κ, R0, s, and k0 in Lemma 3.4.2 and Theorem 3.1.2 to confirm they are finite for every ρ,ε∈(0,1). If either theorem is stated only for tensors or requires p>d, re-derive the random-restriction and bias-implies-low-rank steps directly for the paper's rank before relying on Theorem 3.1.2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central separation claim requires the conventional-hardness half: if NC0[+] could decode the Hadamard code, the QNC0[+] construction in Chapter 4 would not separate the classes. The proof of Theorem 3.1.2 is where that half is established, and it leans on two external black boxes. In the pseudorandom case, Lemma 3.4.2 uses Theorem 3.4.1 (Briët–Castro-Silva, Theorem 1.8 of [BC24]) to assert that a high-rank polynomial map of degree d remains high-rank under a σ-biased random restriction with probability 1−ε and rank decay κ=κ(d,σ), with constants independent of n and k. The rank used is not the tensor analytic rank of [BC24] but the paper's Definition 3.3.2, a max over lower-degree maps; the paper argues only that the four properties of Lemma 3.3.4 make the theorem applicable, without reproducing the theorem or its hypotheses. In the structured case, Theorem 3.3.1 (Kaufman–Lovett, Theorem 4 of [KL08]) is applied to P(y,v)=⟨v,ϕ(y)−ψ(y)⟩, whose degree can be d+1 and whose bias is only p^{-R0}; the resulting constant s, and hence the induction threshold k0, depends on the theorem holding at exactly this degree and bias over F_2. If either theorem has a hidden condition—for example, being proved for tensors rather than for this max-over-lower-degree rank, or requiring p>d, or requiring k=O(n)—then the induction in Section 3.5 falls through and the claimed separation has no classical lower bound. The paper provides no proof or derivation of either imported statement, so this is the least secure load-bearing point of the central argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript formalizes a model of adaptive quantum computers (called LAQCC) and studies two tasks. Part I treats decoding: Chapter 3 proves that no NC0[⊕] circuit (equivalently, no constant-degree polynomial map) can decode an arbitrary error-correcting code under biased noise with constant success probability; Chapter 4 gives a constant-depth QNC0[⊕] circuit that decodes a corrupted Hadamard codeword with probability Ω(ε²) and uses this to claim separations between QNC0[⊕] and NC0[⊕]/AC0[⊕]; Chapter 5 gives a quantum algorithm that, given a function close to a degree-2 Reed-Muller codeword, finds a correlated quadratic phase with O_ε(n log n) queries. Part II introduces the LAQCC model, gives constant-depth state-preparation routines for uniform, GHZ, W, and Dicke states, and compares them to non-adaptive alternatives both analytically and on quantum hardware.","tokens_in":61003,"tokens_out":30654,"duration_ms":281499,"significance":"If the central theorems are fully established, the paper provides a natural decoding problem with a provable separation between constant-depth quantum circuits with classical feedback and standard constant-depth circuits, complementing earlier artificial separations such as 2D Hidden Linear Function and Relaxed Parity Halving. The classical hardness theorem is attractively general, applying to every error-correcting code, and the Ω(ε²) decoding probability in Theorem 4.2.1 is derived cleanly from the Fourier amplitude of the corrupted Hadamard word. The Chapter 5 algorithm extends a substantial line of work on algorithmic higher-order Fourier analysis, and the query lower bounds in Section 5.7 are clearly stated. However, several load-bearing steps are either imported theorems whose hypotheses are not verified, a reduction that is explicitly only sketched, or a lemma without proof; these gaps need to be closed before the advertised separations can be considered proven.","major_comments":[{"comment":"The first clause of Theorem 4.5.3 asserts that list decoding the Hadamard code with any constant error parameter δ < 1/2 separates QNC0[⊕] from NC0[⊕]. This is not established by the results proved in the paper. Theorem 3.1.1 bounds the success probability of an NC0[⊕] circuit whose output is the message x, i.e. a map F_2^n → F_2^k; it says nothing about a circuit that outputs a list L(y) of length up to n/4 containing x. Corollary 4.6.2 gives hardness for the list-Hadamard problem only in the regime ε(n) ≤ 1/(log n)^{ω(1)}, which excludes constant ε = 1/2 − δ. Unless a separate lower bound for list decoding at constant δ is supplied, the theorem should be restated as a separation for exact decoding, which is what Theorems 3.1.1 and 4.1.1 actually demonstrate.","section":"Section 4.5, Theorem 4.5.3 (first clause)"},{"comment":"The conversion of the quantum list-decoding circuit into a Majority circuit is explicitly presented as a sketch. In particular, the text does not specify how a probabilistic quantum subroutine C whose output is a classical list obtained by measurement can be used inside an oracle QNC0[⊕] circuit while preserving the claimed success probabilities 1 − O(n^{-1/4}) and 1 − O(n^{-1/8}); it also does not account for the total depth and size of the classical post-processing, including the equality checks between m and every list element and the OR reductions. Since the second part of Theorem 4.5.3 depends on this reduction, the claimed separation from AC0[⊕] is not proven as written. Please provide a complete construction or explicitly mark that separation as conditional on a completed version of this argument.","section":"Section 4.6.2"},{"comment":"The random-restriction theorem is imported from [BC24] and applied to the analytic rank of Definition 3.3.2, with the assertion that the four properties in Lemma 3.3.4 make the theorem applicable. The manuscript does not state the hypotheses of [BC24, Theorem 1.8] nor verify that the present arank_d satisfies them in the regimes used later, in particular over F_2 and with the maximum over lower-degree polynomial maps in the definition. This is load-bearing: the pseudorandom case of Theorem 3.1.2, and hence the conventional-hardness side of the central separation, depends quantitatively on the constants κ(d,σ) and R(d,σ,ε). Please reproduce the imported theorem and its verification, or give a direct proof of the biased-equidistribution lemma.","section":"Section 3.4, Lemma 3.4.2 and Theorem 3.4.1"},{"comment":"Lemma 5.1.6 asserts that a Fourier-mass lower bound on the multiplicative derivatives of f implies that the graph A = {(h, φ(h))} has large additive energy. No proof is given, and this lemma is used later in Section 5.3 (via Proposition 5.3.1) and in Section 5.6 to establish Lemma 5.1.2 and hence Theorem 5.1.1. Since the energy lower bound is the starting point for the Balog-Szemerédi-Gowers step, the proof of the main theorem of Chapter 5 is incomplete as written. Please add a proof or a precise reference that contains the proof.","section":"Section 5.1.1, Lemma 5.1.6"}],"minor_comments":[{"comment":"The upper bound |⟨B3⟩| ≤ exp(−poly(1/γ)) |H0| has the wrong sign: the exponential factor should be exp(poly(1/γ)), since a set size cannot be bounded above by an exponentially small multiple of |H0|. The same notation appears in Equation (5.17) and should be corrected for consistency.","section":"Equation (5.16)"},{"comment":"The notation ε(n) ≤ 1/(log n)^{ω(1)} is ambiguous; it should be clarified, for example as 'ε(n) ≤ (log n)^{-C} for every fixed constant C', so that the intended regime in the theorem is unambiguous.","section":"Theorem 4.5.3"},{"comment":"The size accounting for a conditional phase gate as O(k 2^k) = O(n log n) is unclear. If the Takahashi-Tani OR gate on k inputs has size O(k), the total circuit size would be O(n log n), not O(n² log n); if it uses the 2^k subset parities from the Fourier expansion, the stated size needs justification. Please reconcile the count or state which size bound is actually needed.","section":"Section 4.4, Lemma 4.4.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a thesis-style compilation with a very broad scope. Part II (LAQCC state preparation and hardware experiments) is largely independent of Part I and is not the source of the main correctness concerns. The theoretical Part I contains several attractive ideas, but the advertised list-decoding separation and the quadratic-decoding theorem require the fixes described in the major comments. The reliance on [BC24] and [KL08] as black boxes is acceptable in principle, but the applicability of [BC24] to the nonstandard analytic rank of Definition 3.3.2 should be verified in full; if it is not, the conventional hardness side of the separation would need substantial new work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the QNC0[+] decoder for the Hadamard code, Theorem 4.1.1, is the real deal—explicit, constant-depth, with a clean Fourier argument—and it genuinely separates QNC0[+] from NC0[+] provided the classical side holds. The classical side is Theorem 3.1.2, and that is where I would point a referee.\n\nWhat's new: list-decoding the Hadamard code separating QNC0[+] from NC0[+]/AC0[+], an analytic-rank notion for polynomial maps, a quantum decoder for degree-2 Reed-Muller with O_ε(n log n) queries, and the LAQCC model with state-preparation routines (GHZ, W, Dicke). The quantum circuit is the strongest part; the depth-65 accounting is explicit and the non-local game intuition is helpful.\n\nSoft spots, in proportion. The biggest is that Theorem 3.1.2 leans on two imported theorems—Kaufman–Lovett (bias implies low rank) and Briët–Castro-Silva (random restriction)—applied to the paper's analytic rank, which is a max over lower-degree maps. The BC24 theorem is stated for tensor rank; the paper argues its Lemma 3.3.4 properties make it applicable, but does not reproduce the theorem or verify the hypotheses at F_2 and at the exact degree and bias parameters. This is load-bearing: if either black box has a hidden condition, the classical lower bound falls through and the separation isn't proven. I don't think the theorems fail, but the paper should either prove the needed instances or state them with precise hypotheses.\n\nOther issues are minor: Section 4.6.2 is a sketch, Theorem 5.1.1 doesn't state the success probability, and the hardware chapter has no data. The abstract's 'more powerful than standard computers' overstates—it's a separation in constant-depth, query-limited models, not an unconditional statement.\n\nVerdict: the paper deserves a serious referee. The quantum construction is valuable and the separation is likely correct, but the referee must push on the classical hardness and demand the imported theorems be properly instantiated. I'd cite it for the quantum decoding result and bring it to reading group to discuss the structure-vs-randomness framework.","headline":"A useful paper with a real quantum decoding construction and a classical hardness proof that currently rests on unverified black-box applicability.","tokens_in":61599,"tokens_out":2666,"would_cite":true,"duration_ms":24738,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12","68Q15","94B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive quantum computers—quantum circuits that interact with a classical computer mid-computation—can provably beat standard constant-depth circuits at recovering messages from corrupted Hadamard codes, and can prepare common quantum…","keywords":["adaptive quantum computing","list decoding","Hadamard code","Reed–Muller code","constant-depth quantum circuits","quantum advantage","GHZ state","query complexity"],"falsifier":"Simulate the depth-65 circuit for $n=16$ with noiseless gates and confirm that the distribution of the sum of measurement outcomes matches $(1 - 2d(c,H(x))/n)^2$ from Theorem 4.2.1; if it does not, the GHZ/fanout construction has an accounting error. Alternatively, attempt to construct an NC$^0[\\oplus]$ circuit family that decodes a corrupted Hadamard code with constant success probability at any fixed $\\delta < 1/2$, which would directly refute Theorem 3.1.1.","tokens_in":60433,"feed_emoji":"⚛️","tokens_out":10534,"duration_ms":87649,"temperature":0.7,"pith_summary":"The paper argues that a quantum computer that hands intermediate results to a classical computer—an \"adaptive quantum computer\"—is strictly more powerful than a standard computer for a concrete, practical task: recovering messages from heavily corrupted digital data. It proves that constant-depth quantum circuits with parity gates can list-decode a corrupted Hadamard code with success probability $\\Omega(\\varepsilon^2)$, while no constant-depth classical circuit with parity gates can decode any code with constant success probability. The proof splits the problem into a structured case and a random-like case using a new analytic rank for polynomial maps. The same adaptive approach yields a query-efficient algorithm for decoding degree-2 Reed–Muller codes, and a second formal model (LAQCC) produces constant-depth protocols for preparing uniform superpositions, GHZ, W, and Dicke states, with hardware-backed error analysis showing higher success probabilities than non-adaptive alternatives.","feed_headline":"Constant-depth quantum decoders beat classical ones on corrupted data","feed_subtitle":"Constant-depth quantum circuits recover corrupted Hadamard messages; classical circuits cannot.","key_machinery":"The load-bearing objects are four. First, the analytic rank of polynomial maps—a measure of how far a map is from being uniform modulo lower-degree maps—splits the classical-hardness proof into a pseudorandom high-rank case (controlled by a random-restriction theorem) and a structured low-rank case (controlled by a bias-implies-low-rank theorem). Second, the quantum Fourier-sampling subroutine, a generalization of Bernstein–Vazirani, samples the Fourier spectrum of multiplicative derivatives and drives both the Hadamard decoder and the quadratic decoder. Third, an algorithmic Balog–Szemerédi–Gowers theorem converts spectral concentration into a small-doubling set and then into an approximating matrix $M$, which yields the quadratic correlation. Fourth, in Part II the LAQCC model lets a constant-depth quantum circuit call unbounded-fan-in classical parity and OR computations mid-circuit, enabling a quantum fanout gate and constant-depth GHZ-state correction; this is the mechanism that gives constant-depth decoding and the improved state-preparation circuits.","core_discovery":"The central discovery is a separation: for every constant error parameter $\\delta \\in (0,1/2)$, list decoding the Hadamard code separates QNC$^0[\\oplus]$ from NC$^0[\\oplus]$, and for error rates $1/2-\\varepsilon$ with $\\varepsilon$ between $\\log n/\\sqrt{n}$ and $1/(\\log n)^{\\omega(1)}$, the List-Hadamard problem separates QNC$^0[\\oplus]$ from AC$^0[\\oplus]$. The quantum side is a depth-65 circuit family that implements the Hadamard-decode non-local game: players share GHZ states, apply phase flips controlled by corrupted coordinates, Hadamard-transform, and measure, so the sum of the answers equals the original message with probability $\\Omega(\\varepsilon^2)$. The classical side proves that no NC$^0[\\oplus]$ circuit can decode any code with constant success probability, because such circuits compute constant-degree polynomials and polynomial maps of constant degree cannot invert encoding-plus-noise. For quadratic Reed–Muller codes, a quantum algorithm makes $O_\\varepsilon(n\\log n)$ queries and returns a degree-2 polynomial $g$ with $\\delta(f,g) \\le 1/2 - \\eta$ whenever the input $f$ is within $1/2 - \\varepsilon$ of some degree-2 codeword, improving the classical query complexity by a factor $n$.","pith_inferences":["Editorial: the decoding separation is likely not unique to the Hadamard code; the same GHZ-fanout machinery should decode any code whose codewords are affine functions over $\\mathbb{F}_2$, and the analytic-rank template should adapt whenever an algorithmic inverse theorem for the appropriate Gowers norm is available at the required field size.","Editorial: a near-term experimental check would be to compile the depth-65 Hadamard decoder for $n=16$–$32$ qubits, count the classical parity operations the LAQCC model exposes, and measure whether the success probability tracks $(1 - 2d(c,H(x))/n)^2$ as the noiseless model predicts.","Editorial: the factor-$n$ query reduction suggests that other higher-order Fourier-analytic algorithms—for instance the cubic Goldreich–Levin algorithm—might gain the same speedup by swapping classical Fourier estimation for quantum Fourier sampling, an idea the paper names as future work."],"forward_implications":["For any constant error parameter $\\delta < 1/2$, there is a concrete decoding problem—recovering messages from corrupted Hadamard codewords—where adaptive constant-depth quantum circuits provably outperform constant-depth classical circuits with parity gates.","The same decoding circuit yields a QNC$^0[\\oplus]$ circuit for Majority, extending the known power of constant-depth quantum circuits to threshold functions without unbounded-fan-in majority gates.","For corrupted degree-2 Reed–Muller codewords, the query algorithm improves on the classical approach by a factor $n$, giving a near-quadratic quantum speedup for learning quadratic polynomials in the presence of noise.","The LAQCC model shows that uniform superpositions, GHZ, W, and Dicke states can all be prepared in constant depth when classical parity operations are available mid-circuit, lowering circuit depth for algorithms that use these states as subroutines.","The error analysis indicates that these adaptive routines can have higher success probabilities than non-adaptive constant-depth alternatives under realistic noise, which matters for near-term devices."],"supporting_citations":[{"why":"Supplies the classical list-decoding algorithm and the Fourier-spectrum sampling viewpoint that the quantum Hadamard decoder extends.","marker":"[GL89]"},{"why":"Provides the bias-implies-low-rank theorem used for the structured case in the proof that constant-degree polynomial maps cannot decode.","marker":"[KL08]"},{"why":"Provides the random-restriction theorem showing high-rank polynomial maps remain high-rank under biased restrictions, the pseudorandom half of the classical hardness proof.","marker":"[BC24]"},{"why":"Gives the constant-depth exact OR gate used to implement the phase flips and the Majority-reduction step in the quantum decoder.","marker":"[TT13]"},{"why":"Supplies the poor-man's-cat-state-to-GHZ correction technique that makes the depth-65 decoding circuit constant-depth.","marker":"[Ben+19]"},{"why":"Provides the baseline quantum algorithm for learning degree-$d$ multilinear polynomials and the query lower bounds that Chapter 5 improves and extends to noisy queries.","marker":"[Mon12]"},{"why":"Gives the prior classical list-decoding algorithm for degree-2 Reed–Muller codes that Chapter 5 revisits with improved query complexity.","marker":"[TW14]"},{"why":"Supplies the constant-depth quantum OR/Majority constructions used in the decoding circuit and in the list-pruning step.","marker":"[H ˇS05]"},{"why":"Provides the characteristic-2 variant of the quadratic correlation lemma needed for decoding degree-2 Reed–Muller codes over $\\mathbb{F}_2$.","marker":"[Sam07]"}],"fun_headline_variants":["Quantum constant-depth circuits decode corrupted data faster","Corrupted data decoding: quantum constant-depth wins","Quantum decoders outperform classical in constant depth","Adaptive quantum computers beat classical on decoding","Quantum separation: constant-depth decoding beats classical"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The classical hardness side rests on two imported theorems about polynomial rank—bias implies low rank, and random restrictions preserving high rank—and if either fails at the exact degree, characteristic, and noise parameters used, the separation between quantum and classical constant-depth decoding collapses.","fun_headline_variants_meta":{"raw":{"variants":["Quantum constant-depth circuits decode corrupted data faster","Corrupted data decoding: quantum constant-depth wins","Quantum decoders outperform classical in constant depth","Adaptive quantum computers beat classical on decoding","Quantum separation: constant-depth decoding beats classical"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000919,"raw_usage":{"total_tokens":4020,"prompt_tokens":1096,"completion_tokens":2924,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":712,"completion_tokens_details":{"reasoning_tokens":2857}},"tokens_in":712,"tokens_out":2924,"duration_ms":19661,"temperature":1.0,"reasoning_tokens":2857,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:01:19.056219+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the depth-65 circuit for $n=16$ with noiseless gates and confirm that the distribution of the sum of measurement outcomes matches $(1 - 2d(c,H(x))/n)^2$ from Theorem 4.2.1; if it does not, the GHZ/fanout construction has an accounting error. Alternatively, attempt to construct an NC$^0[\\oplus]$ circuit family that decodes a corrupted Hadamard code with constant success probability at any fixed $\\delta < 1/2$, which would directly refute Theorem 3.1.1.","supporting_citations":[],"review_version":1}