13
$\begingroup$

Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier?

The only paper I know is An application of quantum finite automata to interactive proof systems by Nishimura and Yamakami, in which a restricted 2QFA (two-way quantum finite automaton) model is used as a verifier and the following result is given: $ \mathsf{QIP(2qfa,polytime)} \subseteq \mathsf{NP} $.

The motivation: I am preparing a paper containing some new results on space-bounded QIP systems and I want to be sure not missing any related known result!

$\endgroup$
  • 3
    $\begingroup$ Do you know what happens when you restrict an IP system to have a space-bounded verifier? That might be a good place to start. $\endgroup$ – Robin Kothari Apr 2 '12 at 17:59
  • $\begingroup$ @Robin: Yes, I am aware many of the classical results. In fact, I am preparing a paper containing some new results on space-bounded QIP systems and I want to be sure not missing any related known result! $\endgroup$ – Abuzer Yakaryilmaz Apr 2 '12 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.