User:Shitikanth/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

Quantum interactive proof system for Quantum Circuit Distinguishability

We say that a language L belongs to QIP(m,c,s) if there is a quantum interactive proof system with at most m messages such that

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

The complexity class QIP is defined as QIP(poly,⅔,⅓). The constants ⅔ and ⅓ in the definition of QIP are arbitrary, as the errors in the proof system can be reduced by parallel repetition (as long as the completeness and soundness parameters have at least an inverse polynomial gap).

Quantum circuit distinguishability

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,

1. QIP protocols with two-sided error to QIP protocols with perfect completeness:

   QIP(m,c,s) ⊆ QIP(m+2,1,(c-s)²)

2. Parallelization of QIP protocols with perfect completeness:

   QIP(m,1,1-ξ) ⊆ QIP(3,1,1-ξ²/4m²)

Proof of (1)

Suppose L has a m message QIP protocol with completeness c and soundeness s.

First of all, notice that we may modify our protocol (by a adding bias depending on the input x) such that the verifier accepts all x∈L with probability exactly c. Call this modified protocol P.

Consider the following (m+2) message QIP protocol-

1. The verifier and prover run the protocol P, except the verifier does not measure the output register at the end.
2. The verifier prepares a fresh qubit B in state $|0\rangle$ and copies the output register onto B using a CNOT gate.
3. The verifier keeps the output qubit but sends the rest of his qubits to the prover.
4. Receive B back from the prover and apply the

Analysis: Let the global state at the end of step 1 be $\alpha _{0}|0\rangle |\psi _{0}\rangle +\alpha _{1}|1\rangle |\psi _{1}\rangle .$ (The first qubit represents the output register of the verifier.)

Then, the state after step 3 is $\alpha _{0}|0\rangle |0\rangle |\psi _{0}\rangle +\alpha _{1}|1\rangle |1\rangle |\psi _{1}\rangle .$ (The prover has access to all but the output register.)

Suppose that the prover now applies some unitary U to his part of the state. Then, the state after step 4 is $\alpha _{0}|0\rangle U(|0\rangle |\psi _{0}\rangle )+\alpha _{1}|1\rangle U(|1\rangle |\psi _{1}\rangle ).$

Note that $x\in L\Rightarrow \alpha _{1}^{2}=c$ and $x\notin L\Rightarrow \alpha _{1}^{2}<s.$

Proof of (2)

Let m>3. (The result is trivial for m ≤ 3.) Let k = (m+1)/2. Let the unitaries applied by the prover and the verifier be $P_{1},\dots ,P_{k}$ and $V_{1},\dots ,V_{k}$ respectively.

The following 3 message protocol simulates the original m message protocol.

1. The prover sends registers $\mathbf {V} _{1},\dots ,\mathbf {V} _{k}$ and $\mathbf {M} _{1},\dots ,\mathbf {V} _{k}$ that are supposed to contain the state of the verifier and message registers in the original protocol just before the k'th round of messages.
2. Pick $r\in \{1,\dots ,k-1\}$. Run the following test to verify that the states given by the prover are consistent with the verifier's action during round r.
3. Prepare two registers $\mathbf {B} ,\mathbf {B} '$ in state ${\frac {1}{\sqrt {2}}}{\Big (}|0\rangle |0\rangle +|1\rangle |1\rangle {\Big )}.$ Apply $V_{r}$ to $\mathbf {V} _{r},\mathbf {M} _{r}$, and swap $\mathbf {V} _{r}$ and $\mathbf {V} _{r+1}$ controlled on $\mathbf {B}$.
4. Send the registers $\mathbf {M} _{r},\mathbf {M} _{r+1},\mathbf {B} '$ and integer r to the prover.

Parallel approximation of QIP(3) protocols

File:QIP (3) circuit.jpg

Circuit Representing QMAM 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\notin 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/ε2]
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 δ-approximation of $P(\Psi )$.

Simulation by bounded-depth Boolean circuits

The final step is to show that the algorithm described above can be simulated using boolean circuits with at most polynomial depth. The result QIP⊆PSPACE follows since it is known that NC(poly)=PSPACE [NC(poly) is the class of languages accepted by such circuits]. We omit the details.

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.)

References

• John Watrous. PSPACE has constant-round quantum interactive proof systems. Foundations of Computer Science, 1999. 40th Annual Symposium on , vol., no., pp.112,119, 1999.
• Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 608–617, 2000.
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP = PSPACE. In Proceedings of the 42nd ACM Symposium on Theory of computing . ACM, New York, 2010, pp. 573-582. [1]
• Xiaodi Wu. Equilibrium value method for the proof of QIP= PSPACE. arXiv preprint arXiv:1004.0264, 2010. [2]
• Complexity Zoo: QIP,QIP(2), QMIP, [3], MIP*

Category:Probabilistic complexity classes Category:Quantum complexity theory