Complexity
The study of quantum computational complexity is about understanding the fundamental limitations of information processing tasks in nature. How powerful can a quantum computer really be? Which problems are truly hard, and what are the problems we may hope to solve efficiently? How well can quantum transmissions help us to solve communication problems? And, how much can we hope to gain over classical communication?
By understanding such limits, computational complexity offers a guide to crafting new algorithms and communication protocols.
CQT researchers have made central contributions to the field, such as the discovery of QIP = PSPACE.
Latest publications
Latest highlights
- Principal Investigator Rahul Jain awarded University prize
- How quantum physics could make 'The Matrix' more efficient
- CQT welcomes artist-in-residence
- Researchers welcome new proofs of the quantum substate theorem
- Presenting 'The Mechanics', a short film by Karol Jalochowski
- Presenting the CQT Annual Report for 2011
- Ceremony marks creation of International Associated Laboratory by CQT and French partners
- Three insights into the foundations of computer science
- Artur Ekert gives radio listeners the low-down on quantum technologies
- QIP = PSPACE = IP ?
