Alternative models for quantum computation/
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/99307 |
| _version_ | 1811095998376706048 |
|---|---|
| author | Lin, Cedric Yen-Yu |
| author2 | Edward H. Farhi. |
| author_facet | Edward H. Farhi. Lin, Cedric Yen-Yu |
| author_sort | Lin, Cedric Yen-Yu |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2015. |
| first_indexed | 2024-09-23T16:36:43Z |
| format | Thesis |
| id | mit-1721.1/99307 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:36:43Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/993072019-09-13T03:05:38Z Alternative models for quantum computation/ Lin, Cedric Yen-Yu Edward H. Farhi. Massachusetts Institute of Technology. Department of Physics. Massachusetts Institute of Technology. Department of Physics. Physics. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2015. Cataloged from PDF version of thesis. Includes bibliographical references (pages 165-181). We propose and study two new computational models for quantum computation, and infer new insights about the circumstances that give quantum computers an advantage over classical ones. The bomb query complexity model is a variation on the query complexity model, inspired by the Elitzur-Vaidman bomb tester. In this model after each query to the black box the result is measured, and the algorithm fails if the measurement gives a 1. We show that the bomb query complexity is asymptotically the square of the usual quantum query complexity. We then show a general method of converting certain classical algorithms to bomb query algorithms, which then give improved quantum algorithms. We apply this general method to graph problems, giving improved quantum query algorithms for single-source shortest paths and maximum bipartite matching. Normalizer circuits are a class of restricted quantum circuits defined on Hilbert spaces associated with Abelian groups. These circuits generalize the Clifford group, and are composed of gates implementing quantum Fourier transforms, automorphisms, and quadratic phases. We show that these circuits can be simulated efficiently on a classical computer even on infinite Abelian groups (the finite case is known [1, 21), as long as the group is decomposed into primitive subgroups. This result gives a generalization of the Gottesman-Knill theorem to infinite groups. However, if the underlying group is not decomposed (the group is a black box group) then normalizer circuits include many well known quantum algorithms, including Shor's factoring algorithm. There is therefore a large difference in computational power between normalizer circuits over explicitly decomposed versus black box groups. In fact, we show that a version of the problem of decomposing Abelian groups is complete for the complexity class associated with normalizer circuits over black box groups: any such normalizer circuit can be simulated classically given the ability to decompose Abelian groups. by Cedric Yen-Yu Lin. Ph. D. 2015-10-14T15:04:43Z 2015-10-14T15:04:43Z 2015 2015 Thesis http://hdl.handle.net/1721.1/99307 922937094 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 181 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Physics. Lin, Cedric Yen-Yu Alternative models for quantum computation/ |
| title | Alternative models for quantum computation/ |
| title_full | Alternative models for quantum computation/ |
| title_fullStr | Alternative models for quantum computation/ |
| title_full_unstemmed | Alternative models for quantum computation/ |
| title_short | Alternative models for quantum computation/ |
| title_sort | alternative models for quantum computation |
| topic | Physics. |
| url | http://hdl.handle.net/1721.1/99307 |
| work_keys_str_mv | AT lincedricyenyu alternativemodelsforquantumcomputation |