Melvin's digital garden


CREATED: 200908281405 Speaker: Rahul Jain ** Classical interactive proofs

  • abstraction of a problem: membership in a language
  • BPP: allowed to accept with high probability (probabilistic)
  • PSPACE: allowed to use polynomial space
  • prover (all powerful), verifier (probabilistic polynomial time bounded)
  • IP $\approx$ NP + BPP, there is a verifier V with the following properties ** Completeness: If $x \in L$, V accepts with high probability ** Soundess: If $x \notin L$, V rejects with high probability
  • Known results: trivial $IP \subseteq PSPACE$, non trivial $PSPACE \subseteq IP$, $IP = PSPACE$

** Quantum turing machine model

  • QIP: quantum, probabilistic, polynomial time bounded verifier
  • Known results: $QIP \subseteq EXP$, $QIP = QIP(3)$ (3 messages suffice), $QIP(1) \subseteq PSPACE$
  • Recent result: $QIP(2) \subseteq PSPACE$
  • New result: $QIP(3) \subseteq PSPACE$

** Approach to show $QIP(3) \subseteq PSPACE$

  • NC(poly): class of functions having polynomial-space uniform circuits of polynomial depth
  • NC: class of functions having log-space uniform circuits of polylog depth
  • $NC(poly) \subseteq PSPACE$
  • formulate maximum acceptance probability on given input $x$ as the optimum of a semi definite program (using NC(poly) alg)
  • find the optimum (approx) using a NC(poly) algorithm (using NC alg, SDP is exponential in size)

** Details

  • a quantum state is a positive semi definite operator on a Hilbert space
  • setting: experts prediction of the stock market
  • multiplicative weight update algorithm: in log events, the average payoff is close to the payoff of the best expert

Links to this note