1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 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

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.