No Quantum Leap for Interactive Proofs!
13 October 2009
"This shows that Quantum Interactive Proofs do not have extra power over Classical Interactive Proofs. In other words, 'quantum verification efficiently in time' equates 'classical solution efficiently in space'."
Dr Rahul Jain, Centre for Quantum Technologies and Department of Computer Science
QUANTUM COMPUTING: Dr Rahul Jain, Assistant Professor at the Department of Computer Science and Principal Investigator at the Centre for Quantum Technologies
CONNECTION: Proving that Interactive Proofs equals Quantum Interactive Proofs
While quantum computing is still at its infancy, research in this area had grown in the past years. In fact, this rapidly evolving field is one of the most active research areas of modern science, attracting substantial funding that supports research groups at leading academic institutions, national laboratories and major industrial-research centers. Contributing to the body of knowledge on quantum computing is Dr Rahul Jain from the Centre for Quantum Technologies and Department of Computer Science. Dr Jain worked with researchers Post-Doctoral Fellow Zhengfeng Ji of the Perimeter Institute for Theoretical Physics, Waterloo in Ontario, Canada and PhD student Sarvagya Upadhyay and Assoc. Prof. John Watrous who are both from the Institute for Quantum Computing and School of Computer Science, University of Waterloo, Ontario, Canada.
Together, the researchers solved a question which was left unanswered for 10 years - the relationship between QIP or the quantum analogue of the class of problems having interactive proofs (IP), and PSPACE or the class of all decision problems which can be solved using polynomial space.
They found that QIP is contained in PSPACE, thus proving that QIP=PSPACE=IP. This finding shows that if the verifier is a quantum verifier, there is no extra power to be gained as far as interactive proofs are concerned. One of the main techniques used was fast parallel algorithms for semi definite programmes.
Said Dr Jain: "This shows that Quantum Interactive Proofs do not have extra power over Classical Interactive Proofs. In other words, 'quantum verification efficiently in time' equates 'classical solution efficiently in space'."
An interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties - the verifier and the prover - interact by exchanging messages so as to check whether a given string belongs to a language. The prover is all-powerful in that it has unlimited computational resources while the verifier has bounded computation power. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.
Earlier in 1992, scientists found that the IP was equal to PSPACE. This implied that problems whose proofs can be efficiently verified in time are precisely the problems that can actually be efficiently solved in space.
On the kinds of hard problems which can be solved, Dr Jain cited the example of the travelling salesman case. "Given in a city, a salesman wants to find the shortest way to travel to a few places. There is a distance between every node and one can ask what is the shortest path to cover all the places. In order to calculate the shortest path, this problem is formulated as a graph problem. The graph is taken as an input and encoded into binary strings," he said.
"Say that we want to know whether the shortest path taken by the salesman will be more or less than 100km. Nobody knows how to do it efficiently in time except with the help of the prover. Once the prover has determined for instance that the shortest path is less than 100km, it will exhibit one such short parth to the verifier, who can then efficiently verify what the prover has said," he noted.
Dr Jain is currently appointed as Assistant Professor at the Department of Computer Science and Principal Investigator at the NUS Centre for Quantum Technologies. His research interests spans from information theory, quantum computation, cryptography, communication complexity to computational complexity theory.