Computation in models inspired by near-term quantum devices
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/124088 |
| _version_ | 1826213483978424320 |
|---|---|
| author | Schaeffer, Luke(Luke Robert) |
| author2 | Scott Aaronson. |
| author_facet | Scott Aaronson. Schaeffer, Luke(Luke Robert) |
| author_sort | Schaeffer, Luke(Luke Robert) |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019 |
| first_indexed | 2024-09-23T15:49:56Z |
| format | Thesis |
| id | mit-1721.1/124088 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:49:56Z |
| publishDate | 2020 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1240882020-03-10T03:03:22Z Computation in models inspired by near-term quantum devices Schaeffer, Luke(Luke Robert) Scott Aaronson. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019 Cataloged 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 Science 2020-03-09T18:52:57Z 2020-03-09T18:52:57Z 2019 2019 Thesis https://hdl.handle.net/1721.1/124088 1142631128 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 208 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Schaeffer, Luke(Luke Robert) Computation in models inspired by near-term quantum devices |
| title | Computation in models inspired by near-term quantum devices |
| title_full | Computation in models inspired by near-term quantum devices |
| title_fullStr | Computation in models inspired by near-term quantum devices |
| title_full_unstemmed | Computation in models inspired by near-term quantum devices |
| title_short | Computation in models inspired by near-term quantum devices |
| title_sort | computation in models inspired by near term quantum devices |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/124088 |
| work_keys_str_mv | AT schaefferlukelukerobert computationinmodelsinspiredbyneartermquantumdevices |