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

<p>The only paper I know is <a href="http://www.sciencedirect.com/science/article/pii/S0022000008001165" rel="nofollow">An application of quantum finite automata to interactive proof systems</a> 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} $.</p>

<p>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!</p>

CC BY-SA 3.0
2012-04-02T17:59:10.567Z
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.
Robin Kothari
CC BY-SA 3.0
2012-04-02T19:21:39.600Z
@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!
Abuzer Yakaryilmaz
<cc.complexity-theory><reference-request><quantum-computing><space-bounded><interactive-proofs>
Is there any known nontrivial result on QIP systems having a space-bounded verifier?
Abuzer Yakaryilmaz
# Is there any known nontrivial result on QIP systems having a space-bounded verifier?

(Asked by: username_0 on 2012-04-01)

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](http://www.sciencedirect.com/science/article/pii/S0022000008001165) 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!

**Tags:** cc.complexity-theory, reference-request, quantum-computing, space-bounded, interactive-proofs

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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!  

---

## 0 answers

