{"id":"c581d224-6aa1-4934-b994-e67902a56313","arxiv_id":"2607.00507","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Exact classical recognition of the Kochen–Specker promise problem needs χ(G) states while a QFA needs only ξ(G), giving an exponential memory separation that disappears under bounded confusability.","lead":"This paper defines a simple memory task built from contextuality graphs and shows quantum automata need O(n) memory where exact classical automata need exponentially more. A small allowed error rate makes the classical cost collapse to O(n), revealing a sharp boundary tied to perfect exclusivity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Zero-error separation is sound; the claimed 'sharp phase transition' at ε_s > 1/(4χ) is unsupported — the O(n) fingerprinting construction only works for a fixed constant soundness error, not for the subconstant errors just above that threshold.","rationale":"The reader's weakest_assumption targets the PFA-to-ontological mapping, but this mapping is not an assumption—it is an exact reformulation of the PFA's linear acceptance probability; the N≥χ lower bound is therefore airtight for the stated model. The reader's concern about the 'sharp phase transition' is, however, well-founded and is the most load-bearing issue. The zero-error exponential separation is correct and should stand, but the paper's abstract and conclusion overstate the phase-transition result: the O(n) fingerprinting construction only applies for a fixed constant soundness error, not for the exponentially small threshold derived from Theorem 3. This does not overturn the main memory-advantage claim, so a conditional acceptance remains appropriate, but the overclaim should be corrected. Our read therefore does not change the reader's verdict.","tokens_in":14975,"tokens_out":21899,"duration_ms":156131,"concrete_test":"Compute the state complexity of the expander-fingerprinting PFA for a target soundness error ε_s = 1/(4χ(Ω_n)) ≈ 2^{-c n} (the claimed threshold). From the error bound (S27), determine the required walk length k: need (ρ+λ_2)^k ≤ ε_s, so k = Θ(n). Substitute into N_expander = m d^k 2^{k+1} (Eq. S26). For a concrete instance, e.g., n=128, plot N_expander vs n; it will scale as 2^{Ω(n)}, not O(n). This verifies that the O(n) collapse is not achieved at the stated threshold, and that the phase-transition claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central zero-error separation (classical N≥χ vs QFA d=ξ) is mathematically sound. The PFA lower bound in the Supplement is rigorous: it follows directly from the linearity of acceptance probabilities (Eq. S1-S4) without needing any extra 'ontological' assumption—the PFA's internal states are literally the ontic states. The QFA construction is also correct. However, the paper's advertised 'sharp algorithmic phase transition' is overclaimed. Theorem 3 gives a lower bound N≥χ only when ε_s ≤ (1−ε_c)^2/(4χ); for Boolean graphs this threshold is exponentially small (≈2^{-Ω(n)}). The expander-fingerprinting construction in the Supplement achieves N=O(n) only when the walk length k is a constant independent of n, which makes the soundness error a fixed constant (ρ+λ_2)^k. To reach ε_s just above the claimed threshold—an exponentially small value—k must grow linearly in n, yielding N_expander = m d^k 2^{k+1} = 2^{Ω(n)}, not O(n). Thus the statement that 'once the acceptable soundness error exceeds this threshold ... reducing the classical state complexity from 2^{Ω(n)} to O(n)' (main text after Eq. 4) does not hold at that threshold. The paper demonstrates a collapse for constant confusability, and a lower bound for zero/exponentially-small error, but it does not establish a sharp phase transition at 1/(4χ). This is a concrete, load-bearing overclaim in the abstract and conclusion.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a promise problem (KSP) on an exclusivity graph G: the input is a length-2 string over the vertex alphabet, promised to be either two identical symbols or two adjacent (mutually exclusive) symbols. The main formal claims are: (i) any probabilistic finite automaton solving KSP with zero soundness error needs N ≥ χ(G) states (Theorem 1); (ii) there exists a measure-once QFA solving KSP with dimension d = ξ(G) via Householder reflections (Theorem 2); (iii) for Boolean orthogonality graphs this gives an exponential classical-vs-quantum memory gap (2^{Ω(n)} vs O(n)); and (iv) there is a \"sharp algorithmic phase transition\": once soundness error exceeds about 1/(4χ), the classical state complexity collapses to O(n) using expander-based fingerprinting. The zero-error separation is mathematically sound, but the phase-transition claim is not supported by the provided proofs.","tokens_in":15316,"tokens_out":13936,"duration_ms":137117,"significance":"If appropriately revised, this is a valuable contribution. The zero-error lower bound for PFAs is rigorous and self-contained (Supplement Eqs. S1–S6), the Householder QFA construction is explicit and correct, and the exponential gap for Boolean orthogonality graphs is a strong, unconditional separation. The bounds are derived independently, with no parameter fitting, and the main proofs are reproducible. However, the advertised sharp phase transition and the \"requires d=ξ(G)\" language both go beyond what is proved. These overstatements are load-bearing for the abstract and conclusions, but they are fixable without changing the core zero-error result.","major_comments":[{"comment":"The paper claims a 'sharp phase transition' at ε_s > 1/(4χ): classical memory collapses from 2^{Ω(n)} to O(n). This is not established. The expander protocol has N = m d^k 2^{k+1} and error ≤ (ρ+λ_2)^k; N = O(n) requires k and d to be constants, making the soundness error a fixed constant independent of n. To drive ε_s down to the subconstant threshold 1/(4χ) ≈ 2^{-Ω(n)}, k must grow as Ω(n), giving N = 2^{Ω(n)}. Moreover, Theorem 3 itself gives N ≥ (1−ε_c)^2/(4ε_s) in this regime, which is also exponential for ε_s just above 1/(4χ). The paper therefore proves a constant-error upper bound and a small-error lower bound, but not a phase transition at the stated threshold. This claim appears in the abstract and conclusion and must be substantially weakened or removed.","section":"§5, Eq. (4); Supplement, Eqs. (S25)–(S27)"},{"comment":"The abstract states that a QFA 'requires' a memory of dimension d = ξ(G), but Theorem 2 proves only that there exists a QFA solving KSP in dimension ξ(G). A general measure-once QFA is not restricted to Hermitian Householder reflections. If U_v is not Hermitian, the zero-error condition |⟨ψ0|U_v U_u|ψ0⟩|² = 0 is not equivalent to orthogonality of |u_u⟩ = U_u|ψ0⟩ and |v_v⟩ = U_v|ψ0⟩. Thus the exact quantum memory requirement ξ(G) is not proved. The statement should be changed to 'can be solved with d = ξ(G)', and the abstract should not claim that the QFA requires this dimension unless a matching lower bound is supplied.","section":"Abstract; Theorem 2"}],"minor_comments":[{"comment":"The n-dimensional construction shows ξ(Ω_n) ≤ n, but the equality ξ(Ω_n) = n is asserted without a lower-bound proof or reference. Since the exponential separation only needs the upper bound d = O(n), the authors should either cite a proof of the orthogonal rank or state the result as an upper bound.","section":"Supplement, Boolean-orthogonality graphs"},{"comment":"The statement that the worst-case entropic quantum state complexity is log ξ(G) is asserted without derivation, and the subsequent CPTP-map expectation is explicitly speculative. These should be marked as conjectures, not as proved results.","section":"Supplement, Entropic Memory Cost"}],"recommendation":"major_revision","confidential_remarks":"The core zero-error result is sound and publishable. The main risk is the phase-transition overclaim, which is exactly the kind of strong statement that other referees will challenge. I would ask the author to align the abstract and conclusion with the proven statements: a constant-soundness-error collapse to O(n), and a lower bound for exponentially small errors, but no sharp transition at 1/(4χ)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core zero-error separation is real and worth taking seriously. The PFA lower bound N ≥ χ(G) is rigorous in the Supplement: it follows directly from linearity and non-negativity of acceptance probabilities, with the internal states functioning as a complete independent set cover. The QFA construction using Householder reflections is also correct, and the Boolean orthogonality graph instantiation gives a clean exponential gap (N = 2^{Ω(n)} vs d = O(n)). That part holds up.\n\nThe soft spots are in the framing and the bounded-error claims. First, the abstract says the QFA “requires a memory of dimension d = ξ(G)”; Theorem 2 only proves existence of a QFA in that dimension. Minor wording, but it should be fixed. Second, and more seriously, the “sharp algorithmic phase transition” is not established. Theorem 3 gives a lower bound N ≥ χ only for ε_s ≤ (1−ε_c)^2/(4χ); for Boolean graphs this threshold is exponentially small. The expander-fingerprinting PFA achieves N = O(n) only when the walk length k is constant, which gives constant soundness error. To get ε_s just above that exponentially small threshold, k must grow with n, and the state count becomes 2^{Ω(n)}, not O(n). So the claim that exceeding 1/(4χ) collapses the exponential cost to linear is unsupported. The paper demonstrates a collapse for constant confusability and a lower bound for zero or exponentially small error, but no phase transition at the stated threshold. This overclaim appears in the abstract and conclusion and should be removed or substantially qualified.\n\nOn novelty: the χ vs ξ memory gap is closely related to existing memory-cost results (Kleinmann et al., Ref. [50], and Trandafir et al., Ref. [51]) and to quantum-coloring separations. The paper should compare directly with those rather than only mentioning them as future work. The “representational contextuality” label is fine, but it is mostly a re-description of known graph-theoretic gaps. What does seem new is the formal-language framing and the bounded-error analysis, even if the phase transition is overstated.\n\nThe example data (the Waegell–Aravind graph coloring) would benefit from a reproducible script or at least a clearer method section. That is minor.\n\nOverall: the central zero-error theorem is sound, the QFA construction is elegant, and the paper deserves serious refereeing. But it needs major revision to fix the phase-transition overclaim and to situate itself honestly against the prior memory-cost literature. I would send it to peer review, with a clear request to revise the abstract and conclusion and to add a direct comparison with Refs. [50,51].","headline":"The zero-error χ vs ξ memory separation is defensible, but the advertised 'sharp phase transition' is not proven — the paper overclaims in the abstract and conclusion.","tokens_in":15858,"tokens_out":1875,"would_cite":true,"duration_ms":19962,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For any exclusivity graph G, the paper claims a two-symbol promise problem that any sound classical finite automaton solves with at least χ(G) memory states is solved by a measure-once quantum finite automaton with only ξ(G) dimensions; on","keywords":["contextuality","exclusivity graphs","chromatic number","orthogonal rank","quantum finite automata","state complexity","promise problems","memory advantage"],"falsifier":"Exhibit a classical probabilistic finite automaton that solves the paper's promise problem on a graph with χ(G)>ξ(G) using fewer than χ(G) states while keeping soundness error zero and completeness error below one—for example, fewer than 7 states on the 18-vertex graph join described in the paper, or o(2^{Ω(n)}) states on the Boolean orthogonality graphs. Alternatively, show that the same promise language is solved by a quantum automaton in dimension less than ξ(G), which would break the claimed tightness of the upper bound.","tokens_in":14799,"feed_emoji":"⚛️","tokens_out":7781,"duration_ms":70411,"temperature":0.7,"pith_summary":"The paper tries to establish that quantum contextuality—specifically the impossibility of coloring an exclusivity graph with few colors—can be turned into an unconditional memory advantage for a very simple language task. It defines a promise problem whose inputs are pairs of measurement outcomes: either the same outcome or two mutually exclusive outcomes. Any classical finite automaton that never mistakes a mutually exclusive pair for a valid pair must use at least as many internal states as the graph's chromatic number, whereas a quantum finite automaton needs only the dimension of the graph's simplest orthogonal representation. For a family of n-bit Boolean orthogonality graphs this becomes 2^{Ω(n)} classical states versus O(n) quantum dimensions. The paper also shows that if the classical machine is allowed a small probability of confusing exclusive events, the exponential penalty disappears above a sharp threshold, and it interprets the χ>ξ gap as a distinct resource it calls representational contextuality.","feed_headline":"Contextuality gives quantum automata an exponential memory edge","feed_subtitle":"A two-symbol promise task costs classical automata 2^Ω(n) states but quantum ones O(n) dimensions—until soundness error crosses a threshold.","key_machinery":"The load-bearing objects are the exclusivity graph G (vertices are outcomes, edges are mutually exclusive pairs), its chromatic number χ(G) (the minimum independent-set cover, hence the minimum number of ontic states a sound classical model needs), and its orthogonal rank ξ(G) (the minimum dimension of a quantum representation with orthogonal projectors on edges). The promise problem converts these into automata: zero soundness error is exactly physical exclusivity, classical machines are analyzed through the identity P(accept uv)=Σ_λ μ_u(λ)ξ_v(λ), and the QFA solution uses Householder reflections U_v that map the initial state to |v⟩, so that adjacent vertices become orthogonal.","core_discovery":"The central claim is a computational translation of the gap between chromatic number and orthogonal rank. For an exclusivity graph G=(V,E), the paper's promise problem asks an automaton to accept strings vv and reject strings uv where (u,v)∈E. A classical probabilistic finite automaton with zero soundness error must have at least χ(G) states: rejecting every adjacent pair forces the support of each preparation to be an independent set, and covering all vertices by such sets is exactly a coloring. A measure-once quantum finite automaton encodes each vertex as a unit vector in an orthogonal representation and uses Householder reflections to route the initial state, requiring only ξ(G) dimensio","pith_inferences":["If the automaton-to-ontological-model mapping is sound, representational contextuality gives a direct operational reading of the chromatic-number/orthogonal-rank gap as the extra number of distinct classical states a simulator must keep, independent of any inequality violation; one could search for other graph parameters, such as vector or quantum chromatic numbers, that yield analogous single-sho","The two-symbol restriction suggests the same graph-theoretic gap may appear in communication-complexity or zero-error signalling tasks where the message is a single outcome pair; testing the 60-vertex graph on a two-qubit platform would be a direct experimental check of the predicted d=4 vs N=6 separation.","The threshold phenomenon echoes the fragility of logical contextuality under unsharp measurements, giving a quantitative algorithmic counterpart that could be extended to sequential or temporal contextuality, where memory bounds may grow with input length rather than saturating at length two.","A natural extension is to replace rank-1 orthogonal representations with higher-rank projectors or nonexact representations, which would interpolate between the χ and ξ bounds and might yield partial quantum advantages at intermediate soundness errors."],"forward_implications":["The advantage is structural, not an artifact of long inputs: the input length is exactly two symbols, so no accumulation of unitary rotations contributes.","On Boolean orthogonality graphs the separation is exponential: 2^{Ω(n)} classical states vs O(n) quantum dimensions, and the exponential alphabet size does not force a classical controller overhead because transition unitaries are synthesized by O(n)-sized circuits.","Representational contextuality sits strictly between state-independent and state-dependent contextuality; it is present in graphs with χ>ξ even when statistical state-independent violations are impossible, and it suffices for state-dependent contextuality.","Permitting classical soundness error above the threshold (1−ϵ_c)^2/(4χ(G)) makes the exponential gap vanish—a random-walk fingerprinting automaton on an expander graph solves the same promise problem with O(n) states—while erasure-dominated noise, which only raises completeness error, leaves the exponential advantage intact.","A 60-vertex Kochen-Specker graph already realizes the gap χ−ξ=2 at ξ=4, so the advantage can be probed with a single 4-level qudit; depolarizing and coherent noise thresholds are O(1) and independent of graph size."],"fun_headline_variants":["Exponential memory edge for quantum automata from contextuality","Contextuality yields exponential quantum memory advantage in automata","Quantum automata get exponential memory savings via contextuality","Contextuality gap: quantum O(n) memory beats classical 2^Ω(n)","With contextuality, quantum automata need exponentially fewer states"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that a classical automaton's internal states can be treated as ontic states in an ontological model, so that 'never accepts adjacent outcomes' forces the support of every outcome to be an independent set; if a classical machine were allowed a non-ontological encoding that exploits temporal correlations or external memory, the N≥χ(G) bound would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Exponential memory edge for quantum automata from contextuality","Contextuality yields exponential quantum memory advantage in automata","Quantum automata get exponential memory savings via contextuality","Contextuality gap: quantum O(n) memory beats classical 2^Ω(n)","With contextuality, quantum automata need exponentially fewer states"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001009,"raw_usage":{"total_tokens":4076,"prompt_tokens":696,"completion_tokens":3380,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":440,"completion_tokens_details":{"reasoning_tokens":3296}},"tokens_in":440,"tokens_out":3380,"duration_ms":24373,"temperature":1.0,"reasoning_tokens":3296,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T09:16:16.997612+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a classical probabilistic finite automaton that solves the paper's promise problem on a graph with χ(G)>ξ(G) using fewer than χ(G) states while keeping soundness error zero and completeness error below one—for example, fewer than 7 states on the 18-vertex graph join described in the paper, or o(2^{Ω(n)}) states on the Boolean orthogonality graphs. Alternatively, show that the same promise language is solved by a quantum automaton in dimension less than ξ(G), which would break the claimed tightness of the upper bound.","supporting_citations":[],"review_version":2}