Supervisor: Jacob Sherson

Presently universal, scalable classical computers (Turing machines) are ubiquitous. Using super computers it is possible to model complicated physical systems like the distribution of matter in the universe and the time development of intricate quantum mechanical systems. The Church-Turing Thesis states that any physical system can be simulated using a classical computer. In contrast the Extended Church-Turing thesis states that all physical systems can be simulated efficiently using a classical computer. It is believed to be false in light of the difficulty simulating quantum sytems, but it has yet to be disproven. “Efficiently” means that simulation time scales as some polynomial of the number of particles being simulated.

If a quantum experiment could be devised, which is known to involve a classically hard problem, and where experimental runtime grows more slowly than classical simulation time for larger and larger particle numbers, “Quantum Supremacy” would be achieved and the ECTT would be disproven. This would conclusively prove that there are indeed problems which classical computers cannot solve efficiently further motivating the quest to construct universal scalable quantum computers.

This kollokvium will explain such a candidate experiment for achieving quantum supremacy - “Boson Sampling”.