Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Date:

Thursday

January

2018

Colloquia

Time: 11:15-12:30

Location: Edna and K.B. Weissman Building of Physical Sciences

Lecturer: Scott Aaronson

Organizer: Faculty of Physics

Contact: hadar.lappin@weizmann.ac.il

Details: UT Austin

Abstract: In the near future, there will likely be special-purpose quantum computers with ... Read more In the near future, there will likely be special-purpose quantum computers with 50 or so high-quality qubits and controllable nearest-neighbor couplings. In this talk, I'll discuss general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for *some* task, motivated by the goal of overturning the Extended Church-Turing Thesis (which says that all physical systems can be efficiently simulated by classical computers) as confidently as possible. Based on joint work with Lijie Chen, https://arxiv.org/abs/1612.05903

Close abstract