Thesis Defense: Luke Schaeffer: Models of Computation Inspired by Near-Term Quantum Devices

Monday, August 5, 2019 - 2:00pm to 3:00pm
Luke Schaeffer
Seminar group: 
Abstract: The race is on to build the first quantum computer, and although there are many groups working towards this goal, their quantum devices have certain architectural properties in common. First, the devices tend to be built on qubits arranged in a 2D grid, with gates between neighboring qubits. Second, we expect that Clifford gates will be an important gate set because of their close connection to stabilizer codes (being both necessary to encode qubits, and easily implemented on encoded logical qubits). Finally, the limited lifespan of qubits (due to various forms of noise) encourages shallow circuits, at least until fault tolerance is achieved. It is important to acknowledge these limitations and incorporate them into our models of computation in order to make the most out of near-term quantum devices. 

In this talk, we will explore the three concepts above, but the focus will be on low-depth quantum circuits. Recent work of Bravyi, Gosset, and König (2018) shows there are problems that can be solved by constant-depth quantum circuits, but not constant-depth classical circuits. Their problem is quite practical to implement, the proof uses no hidden assumptions, and it is a fair comparison of classical vs. quantum circuits---the main downside is that constant-depth classical circuits are extremely weak. We present two follow-up results with the goal of strengthening the classical model. One result constructs a conceptually simpler problem and shows that is hard for AC^0 circuits (constant depth, unbounded fan-in AND/OR gates). The other result proves hardness for even stronger classical models of computation, but under an unusual interactive model of simulation.

Committee Members:  Scott Aaronson, Ryan Williams and Aram Harrow