IoP Colloquium: Harry Buhrman (CWI)
Title: Quantum Computing and Complexity Theory (room C1.110)
Quantum Computing and Complexity Theory
Quantum computers hold great promise as the next generation hardware. They are based on counter-intuitive phenomena from quantum mechanics, like superposition, interference, and entanglement. The basic building block of a quantum computer is a quantum bit or qubit, which unlike a classical bit can be in a quantum superposition (a simultaneous combination) of both 0 and 1. In the 1990s it was demonstrated that, for specific problems, quantum algorithms run on a quantum computer can massively outperform classical computers. The famous quantum algorithm of Peter Shor shows that a quantum computer can factor large numbers and thus breaks most of modern-day cryptography.
Quantum computers appear to have an advantage over the classical computation paradigm. However, it i unclear how large this advantage is. What is the power of a quantum computer and how does it relate to the classical computation paradigm? In this talk I will highlight some of the recent results and ideas relating classical and quantum information processing.