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!

Improve this question
$\endgroup$
2
  • 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, 2012 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, 2012 at 19:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.