<p>Background: I'm a CS grad student. I've taken a course on computational complexity.</p>

<p>Question: </p>

<ol>
<li><p>Can you suggest an introductory book on quantum computation, especially regarding the details of Question 2. </p></li>
<li><p>Argue whether it's hard to separate $QIP[i]$ from $QIP[i + 1]$ for $i &lt; 3$. I know $QIP$ collapses to $QIP[3]$. The simple argument is that this question is hard because we still can't separate P from $PSPACE$. Note $P \subseteq BQP = QIP[0]$ and $PSPACE = IP = QIP = QIP[3]$. However on the other hand, I would think separating $QIP[i]$ from $QIP[i + 1]$ is easy, because the difference is obvious. The only thing left to do is to define a language that exploits the difference.</p></li>
</ol>

<p>Remark. To me question 1 is more important than question 2. :p</p>

CC BY-SA 2.5
2010-12-27T09:17:38.237Z
The [answer](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3427#3427) by Sadeq Dousti in the post [What Books Should Everyone Read?](http://cstheory.stackexchange.com/q/3253/1800) is nice.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-27T13:54:07.860Z
Very little is known about the class QIP(2), and identifying QIP(2) compared to QMA, QIP (=PSPACE) or any classical complexity classes is a long-standing open problem in quantum complexity theory stated in [Kitaev and Watrous STOC 2000](http://dx.doi.org/10.1145/335305.335387).  Neither QIP(2)=QMA nor QIP(2)=PSPACE has been ruled out; although either equality is surprising, I would not say that they should be obviously different (even under the assumption AM≠PSPACE or some other widely accepted assumptions) because of the lack of any evidence.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-27T21:52:25.963Z
The difference between levels $\Sigma_P^k$ and $\Sigma_P^{k+1}$ in the polynomial hierarchy is also obvious (including $k = 0$) and there are languages that exploit these differences, but no one has been able to prove their separation.
Derrick Stolee
CC BY-SA 2.5
2010-12-28T02:41:56.387Z
Please use LaTeX for math and read [FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question? ](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).
Kaveh
CC BY-SA 2.5
2010-12-29T03:10:48.883Z
@Kaveh: I do not think that using LaTeX is necessary.  In fact, I find the version before your edit slightly easier to read except for the formatting of the enumerated list.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-29T04:04:07.160Z
@Tsuyoshi: you are right, I misread [the related FAQ item](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/301#301).
Kaveh
<cc.complexity-theory><complexity-classes><quantum-computing><separation>
Separating the QIP hierarchy
Zirui Wang
# Separating the QIP hierarchy

(Asked by: username_0 on 2010-12-27)

Background: I'm a CS grad student. I've taken a course on computational complexity.

Question:

1. Can you suggest an introductory book on quantum computation, especially regarding the details of Question 2.
2. Argue whether it's hard to separate $QIP[i]$ from $QIP[i + 1]$ for $i < 3$. I know $QIP$ collapses to $QIP[3]$. The simple argument is that this question is hard because we still can't separate P from $PSPACE$. Note $P \subseteq BQP = QIP[0]$ and $PSPACE = IP = QIP = QIP[3]$. However on the other hand, I would think separating $QIP[i]$ from $QIP[i + 1]$ is easy, because the difference is obvious. The only thing left to do is to define a language that exploits the difference.

Remark. To me question 1 is more important than question 2. :p

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, separation

> **Comments:**
> **username_1**: The [answer](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3427#3427) by Sadeq Dousti in the post [What Books Should Everyone Read?](http://cstheory.stackexchange.com/q/3253/1800) is nice.  
> **username_2**: Very little is known about the class QIP(2), and identifying QIP(2) compared to QMA, QIP (=PSPACE) or any classical complexity classes is a long-standing open problem in quantum complexity theory stated in [Kitaev and Watrous STOC 2000](http://dx.doi.org/10.1145/335305.335387).  Neither QIP(2)=QMA nor QIP(2)=PSPACE has been ruled out; although either equality is surprising, I would not say that they should be obviously different (even under the assumption AM≠PSPACE or some other widely accepted assumptions) because of the lack of any evidence.  
> **username_3**: The difference between levels $\Sigma_P^k$ and $\Sigma_P^{k+1}$ in the polynomial hierarchy is also obvious (including $k = 0$) and there are languages that exploit these differences, but no one has been able to prove their separation.  
> **username_4**: Please use LaTeX for math and read [FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question? ](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).  
> **username_2**: @username_4: I do not think that using LaTeX is necessary.  In fact, I find the version before your edit slightly easier to read except for the formatting of the enumerated list.  
> **username_4**: @Tsuyoshi: you are right, I misread [the related FAQ item](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/301#301).  

---

## 0 answers

