Quantum speedups in query complexity
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/113996 |
| _version_ | 1826194252497944576 |
|---|---|
| author | Ben David, Shalev |
| author2 | Scott J. Aaronson. |
| author_facet | Scott J. Aaronson. Ben David, Shalev |
| author_sort | Ben David, Shalev |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017. |
| first_indexed | 2024-09-23T09:53:14Z |
| format | Thesis |
| id | mit-1721.1/113996 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:53:14Z |
| publishDate | 2018 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1139962019-04-12T23:17:24Z Quantum speedups in query complexity Ben David, Shalev Scott J. 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, 2017. Cataloged from PDF version of thesis. Includes bibliographical references (pages 135-141). In this thesis, we study randomized and quantum algorithms in the query complexity model. We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting. We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm. In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications. We also study lower bound techniques for randomized algorithms. We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions. This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications. In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity. Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set. We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity. Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup. by Shalev Ben-David. Ph. D. 2018-03-02T22:22:14Z 2018-03-02T22:22:14Z 2017 2017 Thesis http://hdl.handle.net/1721.1/113996 1023803724 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 141 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Ben David, Shalev Quantum speedups in query complexity |
| title | Quantum speedups in query complexity |
| title_full | Quantum speedups in query complexity |
| title_fullStr | Quantum speedups in query complexity |
| title_full_unstemmed | Quantum speedups in query complexity |
| title_short | Quantum speedups in query complexity |
| title_sort | quantum speedups in query complexity |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/113996 |
| work_keys_str_mv | AT bendavidshalev quantumspeedupsinquerycomplexity |