Information for

Quantum complexity

A model of quantum teleportationWhereas algorithms focus on what a quantum computer can achieve, the study of complexity examines how well they can (or cannot) achieve these tasks and by counting the resources needed. Quantum complexity examines the concept of difficulty — the “hardness” of certain problems to solve. In 2009, John Watrous and collaborators achieved a major breakthrough when they resolved a decade-old complexity problem by proving the equivalence of two collections of computational problems called QIP and PSPACE.

Contributions that have shaped the field have also been made by faculty at the Institute for Quantum Computing including Andrew Childs, Richard Cleve, Michele Mosca and Ashwin Nayak.

John Watrous - QIP and PSPACE