Computation in models inspired by near-term quantum devices

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019Cataloged from PDF version of thesis.Includes bibliographical references (pages 199-208).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 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 thesis, we will explore the three concepts above. First, we see a cellular automaton with a demanding universality property, to illustrate that computation in the grid is possible even under extreme circumstances. Second, we present a classification of subsets of the Clifford gates, furthering our understanding of this important quantum gate set. Finally, recent work of Bravyi, Gosset, and König (2018) shows, unconditionally, that there are problems that can be solved by constant-depth quantum circuits, but not constant-depth classical circuits. We present two follow-up results above low-depth quantum circuits with the goal of strengthening the classical hardness. One result extends the separation AC⁰ circuits (constant depth, unbounded fan-in AND/OR gates), and arguably simplifies the Bravyi et al. problem. The other result proves hardness beyond AC⁰ (specifically to [cross in a circle symbol]L) for the task of interactively simulating certain constant-depth quantum circuits.by Luke Schaeffer.Ph. D.Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Scienc