{"id":"e72ac07b-7e9a-4834-b5a6-f359b09cec00","arxiv_id":"2508.21020","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"PSPACE, hence QIP, is contained in the class of languages verifiable by Arthur-Merlin proof systems whose verifier is a two-way automaton with a constant-size quantum memory.","lead":"A theoretical computer scientist proves that PSPACE, which equals the class QIP of languages with quantum interactive proofs, can be verified by an extremely weak machine: a two-way finite automaton with a constant-size quantum memory and rational transition amplitudes. The result shows that constant-memory quantum verifiers with public coins can check every problem decidable in polynomial space.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof's key probability claims are consistent, though several constructions are underspecified.","rationale":"The reader identified the norm-product property behind Eq. (4) as the weakest assumption. I do not see this as a real defect: the protocol is designed so that the product of the unscaled main operation elements is exactly the displayed vector, with no path-dependent extra factor. The equal amplitude factor N_$=D^{-l} follows from the fact that every main operation element is (1/D) times a fixed rational matrix and the total number of read symbols l is the same for every branch. The soundness bound then follows from the integer nature of S-T: every losing universal choice gives rejection at least D^{-2l}, and every accepting branch gives acceptance exactly (1/16)^n D^{-2l}. The remaining concern in Theorem 2, about feeding the two-way verifier V2 with a streaming u, is an implementation detail: V2's protocol is one-way within each pass and can be restarted by requesting a fresh configuration history from the prover. The proof would be stronger if this were spelled out, but I found no reason to believe the construction fails. I therefore do not share the reader's conditional concern as a load-bearing objection, though CONDITIONAL is a reasonable editorial stance given the exposition gaps.","tokens_in":10915,"tokens_out":52832,"duration_ms":558292,"concrete_test":"Re-derive Eq. (4) and the N_$ claim by writing the exact 4x4 matrices for the encoding, subtraction/halving, and decision operations in Theorem 1, and verify by induction that their product (without the 1/D factors) applied to the initial state equals (1, S-T, 0, (1/4)^n) for every sequence of verifier/prover choices. Also write out the finite-state control of the combined verifier in Theorem 2 for a concrete linear-space transducer and simulate one nonmember input; if the transition table is finite and V2's restarts are emulated by re-requesting the configuration history, the composition goes through.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After working through the protocol, I could not identify a load-bearing flaw. The apparent norm-product issue behind Eq. (4) and the equality N_$=(1/D)^l is resolvable: the unscaled product of the main operation elements in Theorem 1 maps the initial vector to (1, S-T, 0, (1/4)^n), and in Fact 1 a valid history maps to (1,0,0,0), so the common factor D^{-l} is correct even though intermediate states are not unit-norm. The ratio argument for nonmembers is sound: every branch of a losing universal choice contributes at least D^{-2l} to rejection, while total acceptance is at most 2^n(1/16)^n D^{-2l}, yielding the claimed 8^n ratio. The streaming composition in Theorem 2 is not written out, but V2's protocol is one-way within each pass and can be rerun by requesting a fresh configuration history; V1's deterministic checks fix the output string. This is an exposition gap, not a demonstrated contradiction.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims that PSPACE (and hence QIP, since QIP = PSPACE) is contained in AM(2QCFA), the class of languages recognized by Arthur–Merlin proof systems whose verifier is a two-way finite automaton with quantum and classical states. The main technical vehicle is a 2QCFA protocol for the PSPACE-complete language KNAPSACK-GAME with perfect completeness and exponential expected time (Theorem 1). The paper then proves two facts showing that any language recognized by a linear-space DTM (Fact 1) or NTM (Fact 2) can be verified by a 2QCFA with perfect completeness in double-exponential expected time, and uses these to prove that any language linear-space reducible to KNAPSACK-GAME is verifiable (Theorem 2). Corollary 1 concludes that every PSPACE language is in AM1(2QCFA). The presentation is compact, with several constructions only sketched.","tokens_in":11118,"tokens_out":40000,"duration_ms":400024,"significance":"If correct, the result is significant: it considerably extends the known power of constant-space quantum verifiers in Arthur–Merlin systems, moving from NP, ASPACE(n), and an NEXP-complete problem to all of PSPACE. The proof is self-contained in the sense that the key probabilistic accounting is explicit, there are no fitted parameters, and the protocols use rational transition amplitudes. The claimed 8^n rejection-to-acceptance ratio in the KNAPSACK-GAME protocol is coherent. However, the manuscript currently omits several load-bearing implementation details, so the significance is only conditional until those constructions are supplied.","major_comments":[{"comment":"The composition of V1 and V2 is not actually a 2QCFA as defined in Section 2. V1 and V2 are each described as having their own input tape and head, while the combined verifier V has only the original input tape containing w. The text says V2 is 'fed' the output u symbol by symbol, but it does not specify how V2's input end-markers, head movements, and restart behavior are simulated when u is streamed from a simulated reduction. Since V2's protocol in Theorem 1 is one-way on each pass, a streaming simulation is plausible, but it must be spelled out at the level of δc, δr, δq. This is load-bearing for Corollary 1.","section":"Theorem 2"},{"comment":"The equality (1/D)^{2l} in Eq. (4) and the analogous rejection bound in Eq. (5) require that the product of the unscaled main operation elements along any path that reaches the decision point maps the initial state to a vector of norm exactly 1 (for Eq. (4)) or norm at least 1 (for Eq. (5)). The proof never establishes this product-norm property. An explicit induction is needed: after each @@@@ block the continue branch maps the unscaled state to (1,next(c_i),0,0), the final block maps it to (1,0,0,0), and the encoding/comparison matrices have the required norms. Without this, the probability accounting in Fact 1 is unsupported.","section":"Section 5, Fact 1, Eq. (4)"},{"comment":"The statement that non-members 'are rejected with probability at least 8/(8+1) > 0.888' is not literally the per-iteration rejection probability. Early termination by auxiliary outcomes and the continue branch at the right end-marker mean a single iteration may make no decision. What is actually shown is the ratio of rejection to acceptance conditional on a decision. The infinite-loop protocol therefore requires a separate argument that the first decision made over repeated iterations is accept with probability at most 1/(1+8^n). This is standard, but it should be stated explicitly, especially because the prover's strategy can adapt across iterations.","section":"Section 4, 'Decision'"}],"minor_comments":[{"comment":"The remark that 'any log-space reduction can be exactly simulated by a linear-space reducer without using any extra work tape' is asserted without proof. A two-sentence justification would help: the work tape is O(log n), the input fits on the single tape, and the output can be streamed rather than stored.","section":"Corollary 1"},{"comment":"The formal definition of a 2QCFA has quantum operations applied only in reading states based on the input tape symbol. In Fact 1 the verifier apparently applies quantum operations while scanning prover-supplied configuration symbols. Please clarify how this is implemented with the communication channel (e.g., by using communication symbols to enter dedicated reading states while the input head is stationary).","section":"Section 2"},{"comment":"The completion procedure that produces the auxiliary operation elements is only referenced to [14]. A short outline of how the columns are made orthonormal and how D is chosen for all superoperators would improve self-containedness.","section":"Section 3.1"},{"comment":"There is a typo in Eq. (2): 'S =∑n i=1 =xi +yi' should read 'S =∑n i=1(xi + yi)'.","section":"Section 4, KNAPSACK-GAME definition"},{"comment":"Fact 2 is proved in only a short paragraph. Since it is not needed for the main theorem, either move it to a remark or supply the missing transition-choice details.","section":"Section 5, Fact 2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a believable, significant step — PSPACE, hence QIP, in AM1(2QCFA) — and I don't see a load-bearing flaw. The paper deserves a serious referee, but it also needs a second pass on exposition.\n\nWhat's new: the author's earlier work gave AM1(2QCFA) protocols for NP, ASPACE(n), and a NEXP-complete language. This paper adds the KNAPSACK-GAME protocol (Section 4) and the reduction-simulation trick (Theorem 2) to cover all of PSPACE. The probability accounting is coherent: for each universal branch, a surviving iteration accepts with probability (1/16)^n; on non-members at least one branch has S != T, giving an 8^n reject-to-accept ratio. Perfect completeness is preserved because the honest prover never triggers a reject. The rational-valued superoperators keep things constructive.\n\nThe soft spots are exactly where the reader pointed. The norm-product property behind Eq. (4) is asserted but not proven; the stress-test note makes a good case that the unscaled product does map the initial state to the right vector, so the D^{-l} factor is correct. Still, the paper should show this explicitly instead of relying on 'cumulative normalization factor.' More serious is the streaming composition in Theorem 2. V2 is a two-way automaton, but the reduction output u is produced online while V1 reads the configuration history. The paper doesn't explain how V2's head movements and restarts are simulated with constant memory when the input is not on a tape. This might be a straightforward fix — the reduction's output is deterministic and can be replayed — but as written it's a real gap.\n\nThe technique sections lean heavily on the author's earlier papers [9,10,14]. That's not self-citation inflation here; the model and the earlier Facts are the rightful basis. Still, a referee should ask for the omitted superoperator details in an appendix.\n\nI come out more optimistic than the formal reader: I don't think the core claim is broken. I would accept this for peer review and would also bring it to a reading group, because the proof strategy is interesting and the gaps are instructive.","headline":"Believable extension to all of PSPACE; the proof has two under-specified constructions that need a referee's attention.","tokens_in":11664,"tokens_out":3015,"would_cite":true,"duration_ms":30204,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q15","68Q45"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that PSPACE, and therefore QIP, lies in AM(2QCFA): every PSPACE language can be verified with perfect completeness by a two-way finite automaton with quantum and classical states that talks classically to a prover.","keywords":["2QCFA","Arthur-Merlin proof systems","quantum finite automata","interactive proof systems","PSPACE","QIP","perfect completeness","small-space computation"],"falsifier":"Enumerate all branches of the KNAPSACK-GAME protocol on a small non-member instance (say n=1) and compute the exact total rejection probability; any value below 8/9 would falsify Theorem 1. Equivalently, for the linear-space simulation, build a valid configuration history and compute the unnormalized norm of the main-element product; if it is not exactly (1/D)^{2l}, the claimed soundness bound collapses.","tokens_in":10775,"feed_emoji":"⚛️","tokens_out":5083,"duration_ms":50790,"temperature":0.7,"pith_summary":"The paper aims to show that a very small verifier—a two-way finite automaton with a handful of quantum states and classical control, communicating classically with a prover—can verify any language in PSPACE. Because PSPACE equals QIP, this also places quantum interactive proof systems inside the Arthur-Merlin class with such automaton verifiers. The protocol accepts all members with probability 1, uses only rational quantum transition values, and terminates in double-exponential expected time. The proof works by giving a perfect-completeness protocol for the PSPACE-complete language KNAPSACK-GAME and then simulating arbitrary log-space reductions to it.","feed_headline":"4-state quantum automaton verifies every PSPACE language","feed_subtitle":"Arthur-Merlin proofs with constant-memory quantum verifiers reach PSPACE in double-exponential time.","key_machinery":"The carrying object is a superoperator-based 2QCFA whose quantum register has only four states. Each symbol is processed by a rational-valued superoperator with one or two 'main' operational elements plus auxiliary elements; observing an auxiliary outcome kills the current iteration, so the useful computation stays in a single pure state along surviving branches. Binary and m-ary numbers are encoded into amplitudes by simple 2x2 matrices A0=(1 0;0 2) and A1=(1 0;1 2), which lets the automaton compare configuration values and accumulated sums by subtraction. The KNAPSACK-GAME protocol uses fair coin flips to pick universal choices and reads the prover's existential choices from the communicat","core_discovery":"The central claim is Theorem 1 plus Corollary 1: the PSPACE-complete language KNAPSACK-GAME has a 2QCFA verifier with perfect completeness, and therefore every PSPACE language does. The verifier runs an endless loop of passes over the input; in each pass it encodes the chosen universal values into quantum amplitudes, lets the prover choose the existential values, and at the right end-marker accepts or rejects based on whether the accumulated values sum to S. Any wrong branch either vanishes or is overwhelmed by rejection probability at least 8/9, and honest members are never rejected, so acceptance happens with probability 1. A streaming simulation of the log-space reduction then feeds the r","pith_inferences":["The double-exponential runtime is an artifact of the automaton's constant memory; a natural next target is to see whether the same encoding tricks can be amortized to single-exponential or even polynomial time for specific PSPACE-complete problems.","The result suggests a trade-off: a constant-size quantum register plus the ability to restart a pass gives the power of polynomial-space verification, whereas any classical probabilistic constant-space verifier stays inside P; the difference likely comes from the way amplitudes can store a whole configuration's value in a single component.","If one replaced the honest prover model in Fact 2 by a probabilistic prover, the same mismatch-rejection argument may yield a direct proof that AM1(2QCFA) contains languages beyond PSPACE, perhaps climbing toward the NEXP-complete language already known to be in the class.","The streaming composition in Theorem 2 implies that any PSPACE-complete problem with a linear-space many-one reduction to KNAPSACK-GAME inherits the protocol; identifying natural problems that reduce more directly could make the automaton's runtime practical."],"forward_implications":["Every language in PSPACE has a constant-memory quantum verifier in an Arthur-Merlin setting with perfect completeness, so AM1(2QCFA) contains PSPACE and, since QIP = PSPACE, QIP as well.","The protocol is public-coin style (the provers see the verifier's measurements), yet it achieves what private-coin two-way probabilistic automata cannot: verification beyond P, including languages outside P.","Because the same framework already contains an NEXP-complete problem, these small-space quantum verifiers can verify languages that polynomial-time classical proof systems cannot be known to handle.","The verification uses rational transition amplitudes only, so the full protocol can in principle be implemented exactly on a physical device without arbitrary real-valued constants.","Member strings are accepted with probability exactly 1, so no error is ever introduced for positive instances; non-members are rejected with probability at least 9/10."],"supporting_citations":[{"why":"Supplies the Fact 1 protocol for verifying linear-space DTMs with a 2QCFA, which the paper reuses for the PSPACE simulation.","marker":"[10]"},{"why":"Introduced the AM1(2QCFA) model and the techniques that the paper says it follows for the PSPACE result.","marker":"[9]"},{"why":"Defines 2QCFAs, the verifier model whose power the paper is extending.","marker":"[13]"},{"why":"Provides the method for embedding rational matrices into superoperators, which carries the normalization through the protocols.","marker":"[14]"},{"why":"Gives KNAPSACK-GAME and its PSPACE-completeness under log-space reductions, the language used in Theorem 1.","marker":"[18]"},{"why":"Shows PSPACE has constant-round quantum interactive proofs, so QIP = PSPACE and the corollary follows.","marker":"[6]"},{"why":"Establishes the limits of AM systems with two-way probabilistic automaton verifiers that the paper contrasts with 2QCFA verifiers.","marker":"[7]"},{"why":"Shows space-bounded probabilistic game automata are weaker, providing the comparison baseline for the classical constant-space case.","marker":"[8]"}],"fun_headline_variants":["PSPACE verified by two-way quantum finite automata","Quantum automata with classical communication check PSPACE","Tiny quantum verifiers handle all PSPACE languages","Arthur-Merlin with 2QCFA achieves PSPACE","Constant-memory quantum verifiers reach PSPACE"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The rejection analysis assumes that the accumulated unnormalized amplitude along every survival path ends with exactly the same norm (1/D)^{2l}, meaning no unwanted amplitude is lost or gained inside the main 'useful' computation.","fun_headline_variants_meta":{"raw":{"variants":["PSPACE verified by two-way quantum finite automata","Quantum automata with classical communication check PSPACE","Tiny quantum verifiers handle all PSPACE languages","Arthur-Merlin with 2QCFA achieves PSPACE","Constant-memory quantum verifiers reach PSPACE"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00029,"raw_usage":{"total_tokens":1485,"prompt_tokens":648,"completion_tokens":837,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":392,"completion_tokens_details":{"reasoning_tokens":769}},"tokens_in":392,"tokens_out":837,"duration_ms":8774,"temperature":1.0,"reasoning_tokens":769,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:41:13.911429+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all branches of the KNAPSACK-GAME protocol on a small non-member instance (say n=1) and compute the exact total rejection probability; any value below 8/9 would falsify Theorem 1. Equivalently, for the linear-space simulation, build a valid configuration history and compute the unnormalized norm of the main-element product; if it is not exactly (1/D)^{2l}, the claimed soundness bound collapses.","supporting_citations":[{"cited_title":"Public qubits versus private coins","cited_arxiv_id":null,"evidence_quote":"Supplies the Fact 1 protocol for verifying linear-space DTMs with a 2QCFA, which the paper reuses for the PSPACE simulation."},{"cited_title":"Public-qubits versus private-coins","cited_arxiv_id":null,"evidence_quote":"Introduced the AM1(2QCFA) model and the techniques that the paper says it follows for the PSPACE result."},{"cited_title":"Two–way finite automata with quantum and classical states","cited_arxiv_id":null,"evidence_quote":"Defines 2QCFAs, the verifier model whose power the paper is extending."},{"cited_title":"Unbounded-error quantum computation with small space bounds","cited_arxiv_id":null,"evidence_quote":"Provides the method for embedding rational matrices into superoperators, which carries the normalization through the protocols."},{"cited_title":"The complexity of membership problems for circuits over sets of integers","cited_arxiv_id":null,"evidence_quote":"Gives KNAPSACK-GAME and its PSPACE-completeness under log-space reductions, the language used in Theorem 1."},{"cited_title":"PSPACE has constant-round quantum interactive proof systems","cited_arxiv_id":null,"evidence_quote":"Shows PSPACE has constant-round quantum interactive proofs, so QIP = PSPACE and the corollary follows."},{"cited_title":"Finite state verifiers I: The power of interac- tion","cited_arxiv_id":null,"evidence_quote":"Establishes the limits of AM systems with two-way probabilistic automaton verifiers that the paper contrasts with 2QCFA verifiers."},{"cited_title":"Space-bounded probabilistic game automata","cited_arxiv_id":null,"evidence_quote":"Shows space-bounded probabilistic game automata are weaker, providing the comparison baseline for the classical constant-space case."}],"review_version":1}