Separating the QIP hierarchy

Asked 8 years, 7 months ago

Viewed 255 times

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

Question:

Can you suggest an introductory book on quantum computation, especially regarding the details of Question 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

Kaveh

16.3k8 gold badges71 silver badges172 bronze badges

asked Dec 27 '10 at 9:11

Zirui Wang

3301 silver badge8 bronze badges

3

$\begingroup$ The answer by Sadeq Dousti in the post What Books Should Everyone Read? is nice. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 27 '10 at 9:17
11

$\begingroup$ 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. 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. $\endgroup$ – Tsuyoshi Ito Dec 27 '10 at 13:54
3

$\begingroup$ 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. $\endgroup$ – Derrick Stolee Dec 27 '10 at 21:52
$\begingroup$ Please use LaTeX for math and read FAQ and [How to ask a good question? ](meta.cstheory.stackexchange.com/questions/300/…). $\endgroup$ – Kaveh Dec 28 '10 at 2:41
2

$\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Dec 29 '10 at 3:10

| show 1 more comment

0 Your Answer

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

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