IQC researchers resolve a longstanding open question about quantum complexity theory.
The University of Waterloo is a world leader in the field of quantum information. Through the coordination of the Institute for Quantum Computing (IQC), researchers work in a variety of areas within the field, ranging from developing the mathematical theory of quantum computing to physical implementations of quantum computing devices.
The David R. Cheriton School of Computer Science is a major component of Waterloo's thrust in the field of quantum computing. Recently, Sarvagya Upadhyay and John Watrous, researchers at SCS and IQC, in collaboration with Rahul Jain (a former member of both SCS and IQC, now at the National University of Singapore) and Zhengfeng Ji (of the Perimeter Institute) have resolved a decade-old problem in the theory of quantum computing by proving the equivalence of two collections of computational problems called QIP and PSPACE.
To explain their result, it is helpful to first summarize some historical developments that preceded the advent of quantum computing. PSPACE (an abbreviation for "polynomial space") designates the collection of all computational problems that can be solved by a computer whose memory usage scales according to some fixed power of the instance size. For example, for problem instances that take n bits to specify, the memory usage of the computer might scale as n3 (if the fixed power is 3).
IP (an abbreviation for "interactive proof") designates the class of all computational problems whose solutions can be "verified", through an interaction with a "prover" agent that answers a series of challenge questions, in time bounded by a fixed power of the instance size. A celebrated result of twenty years ago asserts that IP and PSPACE are in fact two descriptions of the same entity (any problem in PSPACE is in IP and vice versa).
PSPACE and IP are just two of many complexity classes, each of which characterizes a collection of computational problems. Relationships among complexity classes are central to complexity theory, and are among the most important questions in theoretical computer science. (Perhaps the most well-known example is the question whether or not the complexity classes P and NP are equal, but we will not elaborate further on this question here).
About fifteen years ago, a series of breakthrough discoveries were made concerning the computational power of computers that use quantum information: instead of their bits being in well-defined states of 0s and 1s, they exist in "superpositions" of states, and their evolution can undergo interference effects. Due to the exponentially large numbers of combinations of 0s and 1s that can occur in these computations, such computers can be thought of as exponentially large interferometers. One of these results, due to Peter Shor (then at AT&T labs), was that these quantum computers can break essentially all public key cryptosystems used in practice. This caused an explosive growth in worldwide interest in the theory and implementation of quantum computers.
Watrous was one of the first researchers to investigate the quantum analogues of PSPACE and IP, called QPSPACE and QIP. About ten years ago, he showed that PSPACE and QPSPACE are the same, and thus PSPACE, QPSPACE and IP are three different descriptions of the same collection of computational problems. In collaboration with Alexei Kitaev (of the California Institute of Technology), Watrous also showed that QIP has several remarkable properties: for example, quantum information can be used to give an enormous reduction in the number of question/answer rounds required for verification in comparison to classical interactive proofs. But the true relationship between IP and QIP remained a mystery until late July, when Jain, Ji, Upadhyay, and Watrous resolved this question by showing QIP is equivalent to PSPACE (and therefore IP as well).
Their result is based on a polynomial-space algorithm that solves a semidefinite optimization problem that can be associated with the verification process in a quantum interactive proof. The algorithm uses the method of matrix multiplicative weights updates, which has recently found other applications in convex programming (which may be thought of as a generalization of linear programming).
Watrous explains the importance of this result as follows: "It is a fundamental goal of quantum complexity theory to understand the implications of quantum information to computational complexity. In other words, we want to understand the impact of quantum information on the way we classify the inherent difficulty of computational problems. In the case of interactive proof systems, we now have an answer: quantum information actually doesn't have any effect at all on the class of problems they define. This isn't really a limitation of quantum computing so much as a demonstration of the enormous power of PSPACE and interactive verification, it completely subsumes the power of quantum computing."
About IQC: Founded in 2002, the mission of the Institute for Quantum Computing (IQC) is to aggressively explore and advance the application of quantum mechanical systems to a vast array of relevant information processing techniques.
A part of the University of Waterloo, Waterloo Canada, IQC creates a truly unique environment fostering cutting-edge research and collaboration between researchers in the areas of computer, engineering, mathematical and physical sciences.
At the time of this release, IQC has 17 faculty members, 19 postdoctoral fellows and over 65 students and research assistants, as well as a support staff of 12.
The Institute for Quantum Computing acknowledges the support of the Government of Canada through Industry Canada and the Government of Ontario through the Ministry of Research and Innovation.