Three complexity classification questions at the quantum/classical boundary
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/124062 |
| _version_ | 1826192455384432640 |
|---|---|
| author | Grier, Daniel. |
| author2 | Scott Aaronson. |
| author_facet | Scott Aaronson. Grier, Daniel. |
| author_sort | Grier, Daniel. |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019 |
| first_indexed | 2024-09-23T09:14:06Z |
| format | Thesis |
| id | mit-1721.1/124062 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:14:06Z |
| publishDate | 2020 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1240622020-03-10T03:29:55Z Three complexity classification questions at the quantum/classical boundary Grier, Daniel. 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 177-183). A central promise of quantum computers is their ability to solve some problems dramatically more efficiently than their classical counterparts. Thus, to understand feasible computation in our physical world, we must turn to quantum rather than classical complexity theory. That said, classical complexity theory has a long and successful history of developing tools and techniques to analyze the power of various computing models. Can we use classical complexity theory to aid our understanding of the quantum world? As it turns out, the answer is yes. There is actually a very fruitful connection between quantum and classical complexity theory, each field informing the other. We will add to this perspective through the lens of classification--attempts to categorize all variations of the object of study as thoroughly and completely as possible. First, we will show that every regular language has quantum query complexity [theta](1), [theta]~([square root]n), or [theta](n). Combining quantum query complexity with these fundamental classical languages not only reveals new structure in these languages, but also leads to a generalization of Grover's famous quantum search algorithm. Second, we will discuss the complexity of computing the permanent over various matrix groups. In particular, this will show that computing the permanent of a unitary matrix is #P-hard. The theorem statement is classical, and yet, the proof is almost entirely the result of exploiting well-known theorems in quantum linear optics. Finally, we give a complete classification of Clifford operations over qubits. Although the Clifford operations are classically simulable, they also exhibit distinct quantum behavior, making them a particularly interesting gate set at the quantum/classical boundary. by Daniel Grier. Ph. D. Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2020-03-09T18:51:41Z 2020-03-09T18:51:41Z 2019 2019 Thesis https://hdl.handle.net/1721.1/124062 1142101782 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 183 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Grier, Daniel. Three complexity classification questions at the quantum/classical boundary |
| title | Three complexity classification questions at the quantum/classical boundary |
| title_full | Three complexity classification questions at the quantum/classical boundary |
| title_fullStr | Three complexity classification questions at the quantum/classical boundary |
| title_full_unstemmed | Three complexity classification questions at the quantum/classical boundary |
| title_short | Three complexity classification questions at the quantum/classical boundary |
| title_sort | three complexity classification questions at the quantum classical boundary |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/124062 |
| work_keys_str_mv | AT grierdaniel threecomplexityclassificationquestionsatthequantumclassicalboundary |