A landmark paper co-authored by IQC faculty member John Watrous and doctoral student Sarvagya Upadhyay has earned the prestigious Best Paper Award at the Symposium on Theory of Computing (STOC).
The paper, entitled QIP = PSPACE, was chosen from a field of 279 submissions and 79 finalists as having made the most significant contribution to theoretical computer science over the past year.
The paper earned the prize last week at the STOC conference in Cambridge, MA, for having provided a solution to a long-standing open problem. Another paper, "An improved LP-based approximation for steiner tree" by Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß and Laura Sanità, share top honours.
The paper by Watrous and team 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.
Watrous and collaborators Zhengeng Ji (Perimeter Institute), Sarvagya Upadhyay (IQC and David R. Cheriton School of Computer Science) and Rahul Jain (National University of Singapore) demonstrated that QIP is equivalent to PSPACE.
To understand the importance of their result, it is helpful to summarize some historical developments that pre-date quantum computing:
PSPACE (“polynomial space”) is 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. IP (“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 20 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).
Watrous was among the first researchers to investigate the quantum analogue of IP, namely QIP. Although he and his collaborators uncovered several interesting properties of QIP, its true relationship to PSPACE remained a mystery until Jain, Ji, Upadhyay and Watrous demonstrated their equivalence last summer.
Explained Watrous: “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 doesn’t actually have any effect at all on the class of problems they define.”
Congratulations to Watrous and his team for this breakthrough and the well-deserved recognition.
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, Ont., 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, 22 postdoctoral fellows and over 55 students and research assistants, as well as a support staff of 18.
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.