QIP $ \subseteq $ AM(2QCFA)

Abuzer Yakary{\i}lmaz

REVIEW 3 major objections 5 minor 21 references

QIP $ \subseteq $ AM(2QCFA)

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict Believable extension to all of PSPACE; the proof has two under-specified constructions that need a referee's attention. read the letter →

arxiv 2508.21020 v1 pith:7AT376BN submitted 2025-08-28 quant-ph cs.CCcs.FL

Abuzer Yakary{i}lmaz This is my paper

classification quant-phcs.CCcs.FL MSC 68Q1268Q1568Q45

keywords 2QCFAArthur-MerlinproofsystemsquantumfiniteautomatainteractivePSPACEQIPperfectcompletenesssmall-spacecomputation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What'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.

The 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.

The 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.

I 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Theorem 2] 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 5, Fact 1, Eq. (4)] 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 4, 'Decision'] 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.

minor comments (5)

[Corollary 1] 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 2] 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 3.1] 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 4, KNAPSACK-GAME definition] There is a typo in Eq. (2): 'S =∑n i=1 =xi +yi' should read 'S =∑n i=1(xi + yi)'.
[Section 5, Fact 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central protocol is self-contained and relies on external PSPACE-completeness results.

full rationale

The paper's main claim (Corollary 1) follows from a new, self-contained protocol for the PSPACE-complete language KNAPSACK-GAME (Theorem 1), combined with Facts 1 and 2 which are reproduced with proofs in the text rather than merely cited. The PSPACE-completeness of KNAPSACK-GAME and the equality QIP = PSPACE are external results used as benchmarks, not derived from the paper's assumptions. There are no fitted parameters, no quantity is renamed as a prediction, and no uniqueness theorem from the authors' prior work is invoked to force a choice. The only self-citations (to [9,10] for techniques and Facts 1-2, and to [14] for superoperator completion) are not load-bearing because the relevant constructions are either restated or sketched in the paper. Some parts are underspecified: Theorem 2 does not fully spell out the streaming interface between the reducer's configuration history and the KNAPSACK-GAME verifier, and Eq. (4) asserts the common factor D^{-2l} without a detailed derivation of the path norms. These are exposition gaps, not circular reductions, and do not make the derivation equivalent to its inputs. The analysis therefore finds no circular step.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical entities. Its free parameters are limited to construction constants such as D. The most substantive axiom is the rational superoperator embedding lemma imported from [14], and the most substantive domain assumptions are the standard complexity equalities and the PSPACE-completeness of KNAPSACK-GAME.

free parameters (1)

D (common normalization factor for superoperators) = unspecified positive integer
Every superoperator in the protocols uses the same normalization D. The proof requires that such a D exists, but no specific value is given; it is a construction parameter, not fitted to data.

assumptions (5)

standard math Any finite set of rational matrices can be embedded as main operation elements of a rational superoperator with a common normalization D.
Stated in Section 3.1 with a construction idea and reference to [14]; it underpins all superoperator implementations in the protocols.
domain assumption KNAPSACK-GAME is PSPACE-complete under log-space reductions.
Taken from references [18,19,20]; used to reduce every PSPACE language to the game.
domain assumption PSPACE = IP = QIP.
Standard complexity theorems (Shamir; Watrous); used to derive the title inclusion QIP ⊆ AM(2QCFA).
domain assumption Any log-space reduction can be simulated by a linear-space reduction without an output tape.
Used in Corollary 1 and Theorem 2 to combine the KNAPSACK-GAME protocol with linear-space reducers.
domain assumption Quantum mechanics is modeled by superoperators with rational entries describing valid physical evolutions.
The 2QCFA model assumes superoperators satisfy the complete positivity condition; this is the standard model for quantum automata.

how reviews work

0 comments

Cite this review

Pith. "Pith review of QIP $ \subseteq $ AM(2QCFA)." pith.science (2026). https://pith.science/paper/7AT376BN

@misc{pith2026250821020,
  author       = {Pith},
  title        = {Pith review of: QIP $ \subseteq $ AM(2QCFA)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7AT376BN}},
  note         = {Machine review of arXiv:2508.21020}
}

abstract

The class of languages having polynomial-time classical or quantum interactive proof systems ($\mathsf{IP}$ or $\mathsf{QIP}$, respectively) is identical to $\mathsf{PSPACE}$. We show that $\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) is subset of $\mathsf{AM(2QCFA)}$, the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness).

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Complexity theory: Current research

Anne Condon. “Complexity theory: Current research”. Chapter The complexity of space bounded interactive proof systems, pages 147–190. Cambridge University Press. (1993). url: https://dl.acm.org/doi/10.5555/183589.183728

work page arXiv 1993
[2]

Quantum computational complexity

John Watrous. “Quantum computational complexity”. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science. Pages 7174–7201. Springer (2009)

work page 2009
[3]

The knowledge complexity of interactive proof-systems (extended abstract)

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof-systems (extended abstract)”. In STOC’85: Proceedings of the 17th Annual ACM Symposium on Theory of Computing. Pages 291–304. (1985)

work page 1985
[4]

The knowledge complexity of interactive proof systems

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof systems”. SIAM Journal on Computing18, 186–208 (1989)

work page 1989
[5]

Trading group theory for randomness

László Babai. “Trading group theory for randomness”. In STOC’85: Proceedings of the 17th Annual ACM Symposium on Theory of Computing. Pages 421–429. (1985)

work page 1985
[6]

PSPACE has constant-round quantum interactive proof systems

John Watrous. “PSPACE has constant-round quantum interactive proof systems”. In FOCS’99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Pages 112–119. (1999)

work page 1999
[7]

Finite state verifiers I: The power of interac- tion

Cynthia Dwork and Larry Stockmeyer. “Finite state verifiers I: The power of interac- tion”. Journal of the ACM39, 800–828 (1992)

work page 1992
[8]

Space-bounded probabilistic game automata

Anne Condon. “Space-bounded probabilistic game automata”. Journal of the ACM 38, 472–494 (1991)

work page 1991

Show all 21 references

[9]

Public-qubits versus private-coins

Abuzer Yakaryılmaz. “Public-qubits versus private-coins”. Electron. Colloquium Comput. Complex.TR12-130 (2012). url: https://eccc.weizmann.ac.il/report/ 2012/130

2012
[10]

Public qubits versus private coins

Abuzer Yakaryılmaz. “Public qubits versus private coins”. In The Proceedings of Workshop on Quantum and Classical Complexity. Pages 45–60. (2013). Univeristy of Latvia Press. url: https://users.utu.fi/mikhirve/workshop/Proceedings.pdf

2013
[11]

Automata: From mathematics to appli- cations

Andris Ambainis and Abuzer Yakaryılmaz. “Automata: From mathematics to appli- cations”. Technical Report 1507.01988. arXiv (2015). url: http://arxiv.org/abs/ 1507.01988

2015 arXiv
[12]

Automata and quantum computing

Andris Ambainis and Abuzer Yakaryılmaz. “Automata and quantum computing”. In Jean-Éric Pin, editor, Handbook of Automata Theory. Pages 1457–1493. European Mathematical Society Publishing House, Zürich, Switzerland, (2021)

2021
[13]

Two–way finite automata with quantum and classical states

Andris Ambainis and John Watrous. “Two–way finite automata with quantum and classical states”. Theoretical Computer Science287, 299–311 (2002). 14

2002
[14]

Unbounded-error quantum computation with small space bounds

Abuzer Yakaryılmaz and A. C. Cem Say. “Unbounded-error quantum computation with small space bounds”. Information and Computation279, 873–892 (2011)

2011
[15]

Magic coins are useful for small-space quantum machines

A. C. Cem Say and Abuzer Yakaryılmaz. “Magic coins are useful for small-space quantum machines”. Quantum Inf. Comput.17, 1027–1043 (2017)

2017
[16]

Quantum complexity theory

Ethan Bernstein and Umesh Vazirani. “Quantum complexity theory”. SIAM Journal on Computing 26, 1411–1473 (1997)

1997
[17]

On the complexity of simulating space-bounded quantum computa- tions

John Watrous. “On the complexity of simulating space-bounded quantum computa- tions”. Computational Complexity12, 48–84 (2003)

2003
[18]

The complexity of membership problems for circuits over sets of integers

Stephen D. Travers. “The complexity of membership problems for circuits over sets of integers”. Theor. Comput. Sci.369, 211–229 (2006)

2006
[19]

Reachability in two-clock timed automata is PSPACE-complete

John Fearnley and Marcin Jurdziński. “Reachability in two-clock timed automata is PSPACE-complete”. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latv...

2013
[20]

Reachability in two-clock timed automata is PSPACE-complete

John Fearnley and Marcin Jurdziński. “Reachability in two-clock timed automata is PSPACE-complete”. Inf. Comput.243, 26–36 (2015)

2015
[21]

Succinctness of two-way probabilistic and quantum finite automata

Abuzer Yakaryılmaz and A. C. Cem Say. “Succinctness of two-way probabilistic and quantum finite automata”. Discrete Mathematics and Theoretical Computer Science 12, 19–40 (2010). 15

2010

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

Complexity theory: Current research

Anne Condon. “Complexity theory: Current research”. Chapter The complexity of space bounded interactive proof systems, pages 147–190. Cambridge University Press. (1993). url: https://dl.acm.org/doi/10.5555/183589.183728

work page arXiv 1993

[2] [2]

Quantum computational complexity

John Watrous. “Quantum computational complexity”. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science. Pages 7174–7201. Springer (2009)

work page 2009

[3] [3]

The knowledge complexity of interactive proof-systems (extended abstract)

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof-systems (extended abstract)”. In STOC’85: Proceedings of the 17th Annual ACM Symposium on Theory of Computing. Pages 291–304. (1985)

work page 1985

[4] [4]

The knowledge complexity of interactive proof systems

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof systems”. SIAM Journal on Computing18, 186–208 (1989)

work page 1989

[5] [5]

Trading group theory for randomness

László Babai. “Trading group theory for randomness”. In STOC’85: Proceedings of the 17th Annual ACM Symposium on Theory of Computing. Pages 421–429. (1985)

work page 1985

[6] [6]

PSPACE has constant-round quantum interactive proof systems

John Watrous. “PSPACE has constant-round quantum interactive proof systems”. In FOCS’99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Pages 112–119. (1999)

work page 1999

[7] [7]

Finite state verifiers I: The power of interac- tion

Cynthia Dwork and Larry Stockmeyer. “Finite state verifiers I: The power of interac- tion”. Journal of the ACM39, 800–828 (1992)

work page 1992

[8] [8]

Space-bounded probabilistic game automata

Anne Condon. “Space-bounded probabilistic game automata”. Journal of the ACM 38, 472–494 (1991)

work page 1991