{"id":"62a51cb6-8d0b-4286-afc0-a5a1e3a7076d","arxiv_id":"2607.26157","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every deterministic adaptive Z2-linear MBQC computing a non-affine Boolean function produces an inconsistent set of Z2-linear equations — an AvN contextuality argument.","lead":"In adaptive measurement-based quantum computers with linear classical control, any deterministic computation of a non-linear Boolean function forces an algebraic contradiction (an all-versus-nothing paradox) in the quantum resource's behaviour. The paper proves this constructively and uses it to extend cohomological contextuality tests to adaptive protocols.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 5.11 relies on informally defined splicing and repeated-measurement manipulations (Lemma 6.4; §6.4) that the paper itself flags as non-rigorous; these are essential to the induction, so equation (7) is not yet established.","rationale":"I read the paper's central claim as: every deterministic adaptive Z2-linear MBQC computing a non-affine Boolean function yields an AvN paradox in the induced model on MP(BI,Z2), and hence (per the sketched Theorem 7.1) a cohomological witness. The main proof rests on Theorem 5.11, whose induction uses three reduction steps. The paper is unusually candid about the weak spots: Lemma 6.4 is explicitly not proved, and Section 6.4's repeated-measurement conventions are explicitly not fully rigorous. These weaknesses are load-bearing because both are needed to reduce n(p) and apply the induction hypothesis; without them equation (7) is merely asserted for the general case. I found no internal contradiction or obvious counterexample in the worked examples, and the surrounding definitions are detailed enough that the gap appears fillable; this is a conditional-acceptance situation, not a rejection. The reader's weakest assumption identifies the same two under-formalized constructions, so I agree with that assessment. My concrete test asks for the missing formalization, which would either close the gap or expose a hidden edge-case failure. No verdict change is needed: the paper should remain CONDITIONAL until these combinatorial lemmas are made rigorous.","tokens_in":35222,"tokens_out":12980,"duration_ms":119496,"concrete_test":"Formalize the missing constructions in a proof assistant: extend Definition 5.1 with an explicit sequential-composition operation (replace each leaf of an initial protocol by a suffix) and a type MP_rep of protocols with repeated measurement labels; then prove Lemma 6.4 and Lemma 6.8–6.10 from these definitions, checking confluence of the 'first occurrence' reduction and equality of o(p,g) for every global assignment g on B_I. If the lemmas cannot be derived without additional assumptions, or a well-formed edge case violates equation (7), Theorem 5.11 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central identity (7) in Theorem 5.11 is the load-bearing step: from it, Theorem 3.6 follows by summing the four equations of an odd-weight function. The proof of (7) is an induction on n(p) that uses three tree transformations. Step 1 is the splicing lemma (Lemma 6.4), whose proof the authors explicitly replace with 'we believe that the slightly less formal exposition here is more illuminating'. Step 3 (Lemma 6.10) eliminates higher-arity nodes by a convention that allows the same measurement variable to occur twice in one protocol; the paper admits this is 'not fully rigorous' and handles it by asserting equations as definitions. These are not cosmetic gaps: Definition 5.1 only builds protocols by prepending a node to a continuation, so there is no formal operation of 'initial subprotocol q followed by node x', nor any protocol type with repeated variables. The lemmas nevertheless freely decompose trees into p1 followed by x and recombine branches across such decompositions. If any edge case fails — a multiplicative site interleaved between spliced branching nodes, overlapping measurement sets with differing affine shifts, or the 'first occurrence' convention failing to be confluent — the reduction to strictly smaller n(p) collapses and equation (7) is not established. The examples in Section 4 make the intended identities plausible, but plausibility is not proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a constructive proof that any deterministic adaptive Z2-linear MBQC protocol computing a non-affine Boolean function must exhibit an All-versus-Nothing (AvN) algebraic contextuality witness in a flattened scenario of measurement protocols (Theorem 3.6). The proof reduces to establishing equation (4), formalized as Theorem 5.11, via an induction on branching depth that uses three tree transformations: splicing (Lemma 6.4), condensing (Lemma 6.6), and removal of higher-arity nodes (§6.4). The paper further claims cohomological consequences, including a resolution of Raussendorf's open question on extending cohomological witnesses to adaptive protocols (Theorem 7.1 and §7.2).","tokens_in":35670,"tokens_out":2972,"duration_ms":28191,"significance":"If the main theorem holds, it is a substantial advance: it extends the algebraic AvN paradigm from non-adaptive to adaptive MBQC, gives an explicit inductive construction of inconsistent linear equations from any non-linear deterministic Z2-linear computation, and supplies cohomological witnesses in both Čech and group-cohomology frameworks, answering a question raised by Raussendorf. The paper also contains a genuinely useful flattening construction (MP(BI,Z2)) and a worked adaptive example in Section 4 that makes the intended mechanism concrete. The proof is largely machine-checkable in principle, and the authors are commendably explicit about the two places where the current exposition is informal. However, those two gaps are load-bearing, and the cohomological consequence is only sketched.","major_comments":[{"comment":"Lemma 6.4 is the first load-bearing step in the induction for Theorem 5.11, yet it is not proved. The proof is replaced by the statement 'we believe that the slightly less formal exposition here is more illuminating'. The informal splicing construction decomposes a protocol as 'p1, then x, then ...', but Definition 5.1 only allows prepending a node to a continuation; there is no formal operation of 'initial subprotocol followed by node'. Consequently, the existence of q, the preservation of p+v.p = q+v.q, and the asserted rank reduction via Tq(u*) = Tp(u*) + Q(w*) are not established. Since Lemma 6.5 and hence Step 1 of Theorem 5.11 rely directly on Lemma 6.4, equation (7) is not yet proven.","section":"§6.2, Lemma 6.4 (footnote 10)"},{"comment":"The elimination of higher-arity nodes (Lemma 6.9 and Lemma 6.10) depends on a convention for protocols in which the same measurement variable occurs twice. The paper admits: 'Formally, this is not fully rigorous without defining these protocols with repeated measurements and proving a version of Theorem 6.3 decomposing them into branches.' The asserted 'first occurrence' convention is claimed to be confluent, but no proof is given. This is not a cosmetic issue: the reduction to smaller n(p) in Step 3 fails if the convention is not well defined on arbitrary families of overlapping measurement sets arising from repeated applications of Lemma 6.8. Thus the induction in Theorem 5.11 is incomplete.","section":"§6.4, repeated-occurrence conventions (pp. 28–29)"},{"comment":"The proof of the condensing lemma is presented as an informal 'in a bit more detail' construction, not a full verification. In particular, the claim that 'q behaves similarly to p in that, barring them aborting early, the vector giving the measurement settings and the final output bit of both p and q is given by w+Tb' is asserted without a formal induction, and the compatibility argument showing that p and q return the same outcome for every global assignment is sketched rather than proved. Lemma 6.7 and Step 2 of Theorem 5.11 depend on this result, so the gap must be closed.","section":"§6.3, Lemma 6.6"},{"comment":"The paper claims to resolve Raussendorf's open question, but Theorem 7.1 is only given a proof sketch, with the explicit caveat that 'the part of this argument requiring significant elaboration is the verification of the functoriality and naturality properties'. The same is true of the group-cohomological consequences in §7.2. If the open-question resolution is a headline contribution, the cohomological transfer needs either a full proof or an explicit statement that it is a conjecture/outline for future work. As written, the claimed resolution is not fully established in this manuscript.","section":"§7.1, Theorem 7.1 and §7.3"}],"minor_comments":[{"comment":"In the text after Lemma 3.5, 'by Theorem 3.5' should read 'by Lemma 3.5' (the statement is numbered as a Lemma). Also, the reduction from l to 2 input bits silently assumes the inclusion of a two-dimensional subspace is composed with Q correctly; this is likely fine but deserves a short remark.","section":"§3.2, Lemma 3.5"},{"comment":"The definition of MP(BI,Z2) uses 'Theorem 5.1' and 'Theorem 5.9' where the manuscript's own cross-references sometimes call definitions 'Theorems'. This is a consistency issue with the numbering style (Definitions 5.1, 5.2, etc. are referenced as 'Theorem 5.1' in several places).","section":"§5.2, Definition 5.7"},{"comment":"The proof of Lemma 6.2 says 'This follows from Theorem 5.9 by a straightforward case split, for each global assignment g, on whether ...'. This is acceptable but the case split should be written out, since this lemma is used repeatedly in Lemma 6.3 and later in the paper.","section":"§6.1, Lemma 6.2"},{"comment":"The notation in the displayed equation (10) is ambiguous: the branch 's' appears both as a subprotocol and as a variable in the tree, and the reader must infer that 's' is a branch of the prefix. A brief clarification of the notation would help.","section":"§6.4, Lemma 6.8"},{"comment":"The phrase 'along the action of Q' and the use of 'πs(q)+1' in Lemma 6.7 are slightly confusing because q may have a different set of sites than p; the projection should be explained more explicitly.","section":"§7.2"}],"recommendation":"major_revision","confidential_remarks":"The core idea is promising and the main theorem is likely correct, but the manuscript as submitted does not meet the standard for a rigorous proof because two pivotal lemmas in the induction are explicitly informal, and the cohomological application is only sketched. The gaps appear fixable with additional formal work (a rigorous treatment of splicing and of protocols with repeated variables, plus a full proof of the functoriality claims in §7). I would recommend inviting a revision rather than rejecting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nKey takeaway: this is the right result, and it�s not ready. The flattening idea is genuinely new and the inductive construction is explicit. But two load-bearing steps are admitted to be informal, and the cohomological theorem is only sketched. It deserves a serious referee, not a desk rejection, and not publication as-is.\n\nWhat�s new: they turn adaptive Z2-linear MBQC into a non-adaptive scenario MP(BI,Z2) by treating measurement protocols as first-class measurements. This lets them prove that computing a non-affine function forces an inconsistent set of linear equations — an AvN argument — for any deterministic protocol. That strengthens Raussendorf�s strong-contextuality result and is the natural way to extend AvN to adaptivity. The worked examples (PR-box, GHZ, and an adaptive depth-3 case) make the argument concrete, and the reduction to odd-weight functions is clean.\n\nWhat�s soft: Lemma 6.4, the splicing lemma, is asserted without proof. The authors say a formal version would be “notationally heavy” and that they believe informal exposition is “more illuminating.” That is a real gap, because the lemma is what lets them reduce the rank of the adaptivity matrix in Step 1 of the induction. Section 6.4�s repeated-variable conventions are introduced with the admission that they are “not fully rigorous” — repeated occurrences are handled by asserting equations as definitions, with the argument that the first occurrence wins. That may be right, but it needs a proper proof for the protocol grammar of Definition 5.1, which has no repeated variables. The identity (7) in Theorem 5.11 carries the whole paper, and these two spots are load-bearing.\n\nThe cohomological consequences in Section 7 are also sketches, not proofs. Theorem 7.1�s proof sketch explicitly defers the functoriality details. The abstract�s claim to resolve Raussendorf�s open question is therefore ahead of what�s demonstrated.\n\nNone of this looks fatal. The core construction is plausible, the examples support it, and the gaps are patchable. But the preprint should not be taken as the final word. The citation pattern is fine — they build on their own framework, but that�s background, and they cite Raussendorf properly.\n\nSend it to peer review, but with referees who will demand proofs. I�d rather see a longer paper with Lemma 6.4 done properly than a short one with a “we believe.”","headline":"A genuinely new flattening of adaptive MBQC into an AvN scenario, with a plausible but not yet rigorous induction — send to strong referees.","tokens_in":36067,"tokens_out":2994,"would_cite":true,"duration_ms":26095,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P13","81P68"],"pacs":["03.65.Ta","03.67.Lx"],"model":"deepseek-v4-flash","headline":"Adaptive MBQC that deterministically computes a non-affine Boolean function must yield an AvN contextuality paradox.","keywords":["measurement-based quantum computation","adaptivity","contextuality","all-versus-nothing argument","Z2-linear MBQC","cohomological contextuality","strong contextuality","empirical models"],"falsifier":"Enumerate all unary-node protocols with up to four sites and all linear encodings Q with input dimension l = m(p)+2, and directly evaluate the sum in equation (4) over every global assignment of outcomes to the underlying measurements; if any assignment yields a sum of 1 rather than 0, then Theorem 5.11 (and hence Theorem 3.6) is false. More specifically, search for a pair (p, v.p) where the splicing construction of Lemma 6.4 produces a protocol violating the admissibility condition of Definition 5.1 (for example, a node re-measuring a site with a different setting), or find two orders of elim","tokens_in":35161,"feed_emoji":"⚛️","tokens_out":11129,"duration_ms":90072,"temperature":0.7,"pith_summary":"The paper proves that any adaptive measurement-based quantum computation (MBQC) with Z2-linear classical control that deterministically computes a non-affine Boolean function must exploit a quantum resource containing an all-versus-nothing (AvN) paradox: a family of linear equations over Z2 that hold in every run but are jointly inconsistent. This is an algebraic, linear-algebraically checkable form of strong contextuality, strengthening an earlier result that only demonstrated strong contextuality in a non-algebraic sense. The proof is constructive: adaptive protocols are flattened into ordinary measurements on a larger scenario of tree-like protocols, and the inconsistent equations are built inductively from the protocol tree. A corollary resolves a longstanding open question by showing that cohomological witnesses of contextuality extend to adaptive protocols, in both the sheaf-theoretic and group-cohomological frameworks. If correct, the result means the computational advantage of adaptive MBQC is always backed by an explicit linear contradiction.","feed_headline":"Adaptive quantum computing forces an AvN contextuality paradox","feed_subtitle":"A new proof shows feed-forward MBQC that beats parity computers always contains an explicit linear contradiction.","key_machinery":"The central object is the scenario MP(BI,Z2) of Z2-valued measurement protocols on a Bell scenario BI — a multi-site scenario where each context picks at most one measurement per site — whose 'measurements' are adaptive protocol trees with branching nodes (outcome-dependent continuations) and multiplicative nodes (halt-if-outcome-mismatch), including higher-arity parity nodes that measure a set of variables and return only their total parity. The key identity is equation (4): for any empirical model e and any protocol p with post-processing Z and linear encoding Q, the sum over all inputs w of the measurement Q(w).p;Z is 0 in the Z2-linear theory of MP(e,Z2) whenever the input dimension is a","core_discovery":"The central claim (Theorem 3.6) is: if an MBQC on a Bell-type scenario, described by an empirical model e, a base protocol p, and linear pre- and post-processing maps Q and Z, deterministically computes a non-affine function f: Z2^l → Z2^o, then the induced empirical model MP(e,Z2) on the scenario of measurement protocols MP(BI,Z2) has an inconsistent Z2-linear theory — its linear equations entail the contradiction 0 = 1. The proof reduces to the single-output, two-input case of odd-weight Boolean functions, where the sum over all inputs of f(w) equals 1 while the key identity (equation (4)) says that the corresponding sum of protocol measurements Q(w).p;Z vanishes in the Z2-linear theory fo","pith_inferences":["A quantitative refinement of the main theorem is a plausible next step: relating the success probability of a noisy adaptive MBQC to the nonlinearity of the computed function and a contextual-fraction-like measure on the flattened scenario would extend the known non-adaptive inequality to feed-forward protocols.","The explicit AvN witnesses may be usable for self-testing adaptive quantum hardware: certifying not only the resource state but also the feed-forward mechanism, since the paradox constrains the entire conditional measurement structure.","The flattening/co-Kleisli perspective likely generalises beyond Z2 and Bell scenarios to qudit MBQC and arbitrary algebraic contextuality scenarios, potentially producing a comonadic resource theory of adaptive protocols.","Because adaptive AvN arguments can detect contextuality that flat arguments miss, they could provide sharper, hardware-relevant constraints for error detection in adaptive quantum devices, going beyond standard randomised benchmarking."],"forward_implications":["If the theorem is correct, every deterministic adaptive Z2-linear MBQC computing a non-affine function carries an explicit AvN paradox, so contextuality in the adaptive setting is always witnessed by linear algebra rather than only topological invariants.","A corollary settles an open question about cohomological contextuality: non-vanishing cohomological witnesses exist for adaptive protocols, both in the sheaf-cohomological and group-cohomology frameworks, with the sheaf-theoretic witness propagating back to the original scenario.","The constructive proof gives an algorithm to extract the inconsistent linear system directly from the protocol tree, potentially enabling automated paradox generation for adaptive quantum circuits.","The flattening construction establishes that adaptive AvN arguments are strictly more informative than non-adaptive ones: the paper exhibits cases where the underlying scenario has a consistent linear theory even though the protocol scenario is AvN-contextual.","The same flattening technique offers a general bridge for lifting other non-adaptive contextuality tools (for example, measures of contextuality or simulation relations) to adaptive MBQC."],"fun_headline_variants":["Adaptive MBQC: non-affine output forces AvN paradox","Adaptivity in quantum computing always yields algebraic paradox","Quantum computers that adapt must harbor AvN contextuality","Proof: adaptive MBQC contradicts linear equations"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof of the main theorem relies on two combinatorial constructions that the paper itself describes as informal or 'not fully rigorous': the splicing lemma (Lemma 6.4) and the conventions for repeated measurement variables in Section 6.4; if either fails in an edge case — for example with overlapping measurement sets, multiplicative nodes, or output-bit interactions — the key identity (4) that drives the contradiction would not be established.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive MBQC: non-affine output forces AvN paradox","Adaptivity in quantum computing always yields algebraic paradox","Quantum computers that adapt must harbor AvN contextuality","Proof: adaptive MBQC contradicts linear equations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000185,"raw_usage":{"total_tokens":1137,"prompt_tokens":704,"completion_tokens":433,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":448,"completion_tokens_details":{"reasoning_tokens":370}},"tokens_in":448,"tokens_out":433,"duration_ms":4374,"temperature":1.0,"reasoning_tokens":370,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T00:37:48.474592+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all unary-node protocols with up to four sites and all linear encodings Q with input dimension l = m(p)+2, and directly evaluate the sum in equation (4) over every global assignment of outcomes to the underlying measurements; if any assignment yields a sum of 1 rather than 0, then Theorem 5.11 (and hence Theorem 3.6) is false. More specifically, search for a pair (p, v.p) where the splicing construction of Lemma 6.4 produces a protocol violating the admissibility condition of Definition 5.1 (for example, a node re-measuring a site with a different setting), or find two orders of elim","supporting_citations":[],"review_version":1}