Short description: The aim of this project is to study some of the primary areas in quantum complexity theory that have developed well over the last couple of years including Interactive Proofs, Zero Knowledge Proofs. Quantum Games like Non-Local games and Quantum Zero-Sum games have also found attention in recent research and their study sometimes is instrumental in arriving at some Structural Complexity results like understanding power of some complexity classes.

Details: We will present background on some specific questions that we wish to investigate further.

1. For multi-prover Quantum Interactive Proofs setting the current knowledge is . is a class of languages recognized by simple protocols in which verifier sends one message each to the two provers (who do not communicate with each other), gets back single bit answers, and uses the questions and the XOR of the answered bits to decide on acceptance/rejection of the input. When provers are entangled in protocols, the resulting class is referred to as . For this class the current knowledge is . The containment was shown in Wehner [W06]. The containment was shown by Cleve, Gavinsky, J [CGJ08] (where they extended and used a result on Transversal XOR Games due to Linden, Popescu, Short, Winter [LPSW06]) exhibiting connection between studying Non-local games and natural complexity classes.
2. Zero-Knowledge proofs are Interactive Proofs in which if the input x is in L, then the verifier "learns nothing more" than the validity of the statement. The fact that the verifier learns nothing more is shown by exhibiting an efficient (polynomial time) machine called the "simulator" which, when x is in L, can reproduce the transcript of interaction between the prover and the (possibly cheating) verifier. When the protocol is classical and the transcript of the simulator is required to be statistically indistinguishable from the actual transcript then resulting class is referred to as Statistical Zero-Knowledge or SZK. When the protocol could be quantum and the simulator is required to also simulate possibly cheating quantum verifiers then the resulting class is referred to as QSZK. Apriory it is not clear whether SZK is contained in QSZK or not. However, it was shown by Watrous [W06], using interesting quantum rewinding technique that . It was also shown earlier by Watrous [W02] that any language in QSZK has a three message protocol with the single message from verifier being classical public coins. However it was shown by Gatis, J, Kolla, Reichardt [GJKR06] that if a language L has a three message Zero-Knowledge protocol with the first two messages being classical and exponentially small soundness error then L is in class BQP, that is L has an efficient quantum deciding machine.

Progress:

1. In recent paper titled "QIP = PSPACE" as above, we have settled a long standing open question in this area and have shown that Quantum Interactive Proofs possess exactly the same power as Classical Interactive Proofs. The holy grail in this area has been found! This work further asserts the robustness of the complexity class PSPACE ( = IP). This work is a natural successor of the previous work titled "Two-message quantum interactive proofs are in PSPACE" in which we showed that two-message Quantum Interactive Proofs possess no extra power over Classical Interactive Proofs. This was already a significant step forward towards settling the main question since three-message Quantum Interactive Proofs capture the entire power of QIP. In a related work which can be considered first in this series of work titled, "Parallel approximation of non-interactive zero-sum quantum games", we had shown that QRG(1), which is the class of problems having a single message Two-Competing Provers Quantum Protocol is contained in PSPACE. The main technique used in all of the above work is to present fast parallel algorithms for different classes of semi-definite programs and this helps to obtain containment of respective classes inside PSPACE. In the last work as mentioned, we considered the quantum analogue of the well studied zero-games in Game Theory and presented a fast parallel algorithm to get an approximate value of the Nash-Equilibrium of such games.
2. Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit [Blu81]. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4 [Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than $1/\sqrt{2}$ [Kit03]. Closing this gap has been one of the important open questions in quantum cryptography. In the paper titled "Optimal quantum strong coin flipping" as above, we resolve this question by presenting a quantum strong coin flipping protocol with cheating probability arbitrarily close to $1/\sqrt{2}$. More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2+\epsilon$ in order to achieve a strong coin flipping protocol with cheating probability $1/\sqrt{2}+O(\epsilon)$. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon [Moc07].
3. In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their instances. They gave a strong negative answer by showing that distinguishing between instances having zero or one witnesses is as hard as recognizing NP, under randomized reductions. We consider the same question in the quantum setting in the paper titled "On the power of unique quantum witness", and investigate the possibility of reducing quantum witnesses in the context of the complexity class QMA, the quantum analogue of NP. The natural way to quantify the number of quantum witnesses is the dimension of the witness subspace W in some appropriate Hilbert space H. We present an efficient deterministic procedure that reduces any problem where the dimension d of W is bounded by a polynomial to a problem with a unique quantum witness. The main idea of our reduction is to consider the Alternating subspace of the d-th tensor power of H. Indeed, the intersection of this subspace with the d-th tensor power of W is one-dimensional, and therefore can play the role of the unique quantum witness.

Publications

References

Back