Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

Abstract

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.

26 pages, 5 figures, some references have been added, and comments are welcome

References in corpus (3)

• Unbounded-error quantum computation with small space bounds
• Interactive Proofs with Quantum Finite Automata
• Turing-equivalent automata using a fixed-size quantum memory

Cited by in corpus (7)

• On the state complexity of semi-quantum finite automata
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Potential of quantum finite automata with exact acceptance
• Quantum finite automata: survey, status and research directions
• Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
• Time-space tradeoffs for two-way finite automata
• Promise problems solved by quantum and classical finite automata