Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
This work addresses the computational power of interactive proof systems with limited quantum resources, offering incremental theoretical insights into quantum automata models.
The paper investigates the power of Quantum Arthur-Merlin proof systems with verifiers modeled by semi-quantum two-way finite automata (2QCFA), showing they are more powerful than classical probabilistic automata (2PFA) in polynomial expected time and can recognize languages like an NP-complete one using only quantum pure states.
In this paper we explore the power of AM for the case that verifiers are {\em two-way finite automata with quantum and classical states} (2QCFA)--introduced by Ambainis and Watrous in 2002--and the communications are classical. It is of interest to consider AM with such "semi-quantum" verifiers because they use only limited quantum resources. Our main result is that such Quantum Arthur-Merlin proof systems (QAM(2QCFA)) with polynomial expected running time are more powerful than in the case verifiers are two-way probabilistic finite automata (AM(2PFA)) with polynomial expected running time. Moreover, we prove that there is a language which can be recognized by an exponential expected running time QAM(2QCFA), but can not be recognized by any AM(2PFA), and that the NP-complete language $L_{knapsack}$ can also be recognized by a QAM(2QCFA) working only on quantum pure states using unitary operators.