Constant-space quantum interactive proofs against multiple provers

• The QIP systems with qfa-verifiers and multiple provers are discussed.
• The 1qfa-verifier QIP systems have complexity of at least context-free languages.
• The same systems have complexity of at most linear exponential time.
• The complexity of expected-polytime 2qfa-verifier QIP systems equals that of NEXP.
• The 2qfa-verifier QIP systems are as powerful as Turing machines.

We present upper and lower bounds of the computational complexity of the two-way communication model of multiple-prover quantum interactive proof systems whose verifiers are limited to measure-many two-way quantum finite automata. We prove that (i) the languages recognized by those multiple-prover systems running in expected polynomial time are exactly the ones in NEXP, the nondeterministic exponential-time complexity class, (ii) if we further require verifiers to be one-way quantum finite automata, then their associated proof systems recognize context-free languages but not beyond languages in NE, the nondeterministic linear exponential-time complexity class, and moreover, (iii) when no time bound is imposed, the proof systems become as powerful as Turing machines. The first two results answer affirmatively an open question, posed by Nishimura and Yamakami [J. Comput. System Sci. 75 (2009) 255–269], of whether multiple-prover quantum interactive proof systems are more powerful than single-prover ones. Our proofs are simple and intuitive, although they heavily rely on an earlier result on multiple-prover classical interactive proof systems of Feige and Shamir [J. Comput. System Sci. 44 (1992) 259–271].