1

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Zirui Wang
  • 551
  • 2
  • 9

0 Answers0