QIP = PSPACE

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