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.
- Will androids dream of quantum sheep?
- Zip software can detect the quantum-classical boundary
- Presenting CQT's Annual Report for 2015
- CQT welcomes alumnus back as National Research Foundation Fellow
- "Breakthrough" research in query complexity
- How quantum entanglement could help us prove things
- Zen and the art of quantum complexity
- Meet a CQTian: Aarthi Sundaram
- Meet a CQTian: Troy Lee
- Game theory result takes CQTian to STOC