User:Diffeomorphicvoodoo/sandbox/QIP (complexity)

In computational complexity theory, the class QIP (which stands for Quantum Interactive Polynomial time) is the set of decision problems that are solvable by a quantum interactive proof system. Quantum interactive proof systems were first introduced by John Watrous in 1999 as a quantum computing analogue of (classical) interactive proof systems. Quantum interactive proof systems are the same as classical interactive proof systems, except that the verifier is a polynomial-time quantum computer which exchanges quantum messages with the prover.

Definition

We say that a language L belongs to QIP if there is a quantum interactive proof system such that

(Completeness) if x ∈ L, the prover has a strategy to convince the verifier with probability ≥ ⅔.
(Soundness) if x ∉ L, irrespective of what the prover does, the verifier would not accept with probability ≥ ⅓.

The constants ⅔ and ⅓ in the definition of QIP are arbitrary, as the errors in the proof system can be reduced by parallel repetition.

As an example, consider the problem of distinguishing quantum circuits. Suppose that the verifier is given the description of two quantum circuits C₁ and C₂ with the guarantee that they are either close or quite far in the metric induced by the completely bounded trace norm. That is, either $\|C_{1}-C_{2}\|_{cb}\geq 2/3$ or $\|C_{1}-C_{2}\|_{cb}<1/3$ and the verifier wants to check which is the case.

Given one of two quantum states $\rho _{1}$ or $\rho _{1}$ (with probability half each), the maximum probability of guessing correctly amongst them is given by ${\frac {1}{2}}+{\frac {1}{2}}\|\rho _{1}-\rho _{2}\|$ .

If $\|C_{1}-C_{2}\|_{cb}\geq 2/3$ , the prover can prepare a state $\rho$ such that $\|(C_{1}\otimes I)(\rho )-(C_{2}\otimes I)(\rho )\|\geq 2/3$ , so that it can distinguish between the two cases with probability 5/6. On the other hand, if $\|C_{1}-C_{2}\|_{cb}<1/3$ , no matter what state $\rho$ the prover prepares, $\|(C_{1}\otimes I)(\rho )-(C_{2}\otimes I)(\rho )\|<1/3$ . Therefore, the prover can not make the verifier accept with probability more than 2/3.

Proof of QIP = PSPACE

QIP = QIP(3)

The proof proceeds in two steps,

QIP protocols with two-sided error to QIP protocols with perfect completeness:
QIP(m,c,s) ⊆ QIP(m+2,1,(c-s)²)
Parallelization of QIP protocols with perfect completeness:
QIP(m,1,1-ξ) ⊆ QIP(3,1,1-ξ²/4m²)

Parallel approximation of QIP(3) protocol

Suppose we have a 3-round QIP protocol for a language L with completeness ¹⁵/₁₆ and soundness ¹/₁₆.

Fixing the strategy of the verifier, the maximum probability of acceptance that the prover may achieve is $\max _{\omega ,\tau }F(\Phi _{1}(\tau ),\Phi _{2}(\omega ))$ .

Therefore, if $x\in L$ , then $\max _{\omega ,\tau }F(\Phi _{1}(\tau ),\Phi _{2}(\omega ))\geq {15}/{16}$ and if $x\notin L$ , then $\max _{\omega ,\tau }F(\Phi _{1}(\tau ),\Phi _{2}(\omega ))\leq {1}/{16}$ .

Using Fuchs-van de Graaf inequalities, if $x\in L$ , $\min _{\omega ,\tau }\|\Phi _{1}(\tau )-\Phi _{2}(\omega )\|\leq 2{\sqrt {1-15/16}}=1/2$ and if $x\in L$ , then $\min _{\omega ,\tau }\|\Phi _{1}(\tau )-\Phi _{2}(\omega )\|\geq 2(1-1/4)=3/2$ .

We now show that it is possible to approximate $\min _{\omega ,\tau }\|\Phi _{1}(\tau )-\Phi _{2}(\omega )\|$ to an accuracy of $\delta =1/2$ in polynomial space. Define $\Psi \in T({\mathcal {M}}\otimes {\mathcal {K}},{\mathcal {V}})$ as $\Psi (\theta )=\Phi _{1}({\text{Tr}}_{\mathcal {M}}\,\theta )-\Phi _{2}({\text{Tr}}_{\mathcal {K}}\,\theta )$ . Then, $\min _{\omega ,\tau }\|\Phi _{1}(\tau )-\Phi _{2}(\omega )\|=\min _{\theta }\|\Psi (\theta )\|=\min _{\theta }\max _{0\leq \Pi \leq \mathbb {I} }\langle \Pi ,\Psi (\theta )\rangle =\min _{\theta }\max _{0\leq \Pi \leq \mathbb {I} }\langle \Psi ^{\ast }(\Pi ),\theta \rangle .$

We describe a Matrix multiplicative weights update algorithm for approximating $P(\Psi )=\min _{\theta }\max _{0\leq \Pi \leq \mathbb {I} }\langle \Psi ^{\ast }(\Pi ),\theta \rangle .$ We look at $\theta$ as a mixture of experts. Since $\Psi$ is a difference of two-quantum channels, $-\mathbb {I} \leq \Psi ^{\ast }(\Pi )\leq \mathbb {I}$ . We take the loss matrix for round t to be $M(t)=(\mathbb {I} +\Psi ^{\ast }(\Pi (t)))/2$ where $\Pi (t)$ is the projector onto the positive eigenspace of $\Psi (\rho (t))$ .

Algorithm

Let ε ← δ/8  and T ← ceil[ln N/ε²]
Let λ ← 0
for i = 1 to n
 W(1) ← I
 Φ(1) ← Tr(W(1)) = n.
 for t = 1 to T
  ρ(t) = W(t)/Φ(t)
  Follow expert's advice according to ρ(t) 
  Observe the loss matrix for day t, M(t)
  λ ← λ +〈ρ(t),M(t)〉
  W(t+1) ← exp(-ε Sum[M(i), {i,1,t}])
  Φ(t+1) = Tr(W(t+1))
Return 2λ/T-1

For any $\varepsilon \leq 1/2$ and for any $v\in \mathbb {C} ^{n}$ , $(1-\varepsilon )\lambda \leq \sum _{t=1}^{T}v^{\ast }M(t)v+{\frac {\ln n}{\varepsilon }}$ .

For $\varepsilon \in [0,1/2],$ $1/(1-\varepsilon )\leq 1+2\varepsilon$ . Therefore, $\lambda /T\leq {\frac {1}{T}}\sum _{t=1}^{T}v^{\ast }M(t)v+2\varepsilon +{\frac {\ln n}{\varepsilon (1-\varepsilon )T}}\leq \sum _{t=1}^{T}v^{\ast }M(t)v+\delta /2$ .

Let $({\hat {\rho }},{\hat {\Pi }})$ attain the min-max value $P(\Psi )=\langle \Psi ({\hat {\rho }}),{\hat {\Pi }}\rangle$ . Then, for any t, $\langle {\hat {\rho }},M(t)\rangle =(1+\langle {\hat {\rho }},\Psi ^{\ast }(\Pi (t))\rangle )/2=(1+\langle \Psi ({\hat {\rho }}),\Pi (t)\rangle )/2\leq (1+P(\Psi ))/2.$ Therefore, $\lambda /T\leq {\frac {1}{T}}\sum _{t=1}^{T}\langle {\hat {\rho }}+\delta /2\leq (1+P(\Psi )+\delta )/2$ .

On the other hand, $\lambda /T={\frac {1}{T}}\sum _{t=1}^{T}\langle \rho (t),M(t)\rangle ={\Big (}1+{\frac {1}{T}}\sum _{t=1}^{T}\langle \rho (t),\Psi ^{\ast }(\Pi (t))\rangle {\Big )}/2={\Big (}1+{\frac {1}{T}}\sum _{t=1}^{T}\langle \Psi (\rho (t)),\Pi (t)\rangle {\Big )}/2\geq (1+P(\Psi ))/2$ .

Therefore, (2λ/T-1) is a &delta-approximation of $P(\Psi )$ .

Variants

QMIP

Quantum Multi-prover Interactive Proofs are motivated by the study of Multi-prover Interactive Proofs. The verifier is a polynomial-time quantum computer which exchanges quantum messages with the prover. As in MIP, the provers are not allowed to communicate after the protocol starts, but they may be entangled. In 2012, Reichardt, Unger and Vazirani established that QMIP=MIP*, showing that all the power of Quantum Multi-prover Interactive Proof systems comes from the ability of the provers to share entanglement.

MIP*

In MIP* protocols, the verifier, and the messages between the prover and the verifier are completely classical. However, as in QMIP, the provers may share an arbitrary amount of entanglement. Since the provers may use the additional resource of entanglement to both convince or to fool the verifier, it is not a priori obvious how MIP* relates to MIP. However, in 2012, Ito and Vidick showed a multi-prover protocol for NEXP sound against entangled provers, showing that NEXP=MIP⊆MIP*. There is no known upper bound to MIP*. (It is not even known whether or not MIP* protocols can solve undecidable problems.)