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

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ The answer by Sadeq Dousti in the post What Books Should Everyone Read? is nice. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 27, 2010 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, 2010 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, 2010 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, 2010 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, 2010 at 3:10

0

Reset to default

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.