Interactive proofs with quantum finite automata

• We study quantum interactive proof (QIP) systems whose verifiers are quantum finite automata.
• QIP systems with classical provers are compared with those with quantum provers.
• We demonstrate that public QIP systems with qfa-verifiers remain powerful.
• Many interactions between a prover and a verifier are more powerful than a single interaction.

Following an early work of Dwork and Stockmeyer on interactive proof systems whose verifiers are two-way probabilistic finite automata, the authors initiated in 2004 a study on the computational power of quantum interactive proof systems whose verifiers are particularly limited to quantum finite automata. As a follow-up to the authors' early journal publication [J. Comput. System Sci., vol. 75, pp. 255–269, 2009], we further investigate the quantum nature of interactions between provers and verifiers by studying how various restrictions on quantum interactive proof systems affect the language recognition power of the proof systems. In particular, we examine three intriguing restrictions that (i) provers always behave in a classical fashion, (ii) verifiers always reveal to provers the information on their next moves, and (iii) the number of interactions between provers and verifiers is bounded.