Classical simulation complexity of restricted models of quantum computation
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2019
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/122164 |
| _version_ | 1826193547929321472 |
|---|---|
| author | Koh, Dax Enshan. |
| author2 | Peter W. Shor. |
| author_facet | Peter W. Shor. Koh, Dax Enshan. |
| author_sort | Koh, Dax Enshan. |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2019 |
| first_indexed | 2024-09-23T09:40:51Z |
| format | Thesis |
| id | mit-1721.1/122164 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:40:51Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1221642019-11-22T03:36:57Z Classical simulation complexity of restricted models of quantum computation Koh, Dax Enshan. Peter W. Shor. Massachusetts Institute of Technology. Department of Mathematics. Massachusetts Institute of Technology. Department of Mathematics Mathematics. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2019 Cataloged from PDF version of thesis. Includes bibliographical references (pages 355-372). Restricted models of quantum computation are mathematical models which describe quantum computers that have limited access to certain resources. Well-known examples of such models include the boson sampling model, extended Clifford circuits, and instantaneous quantum polynomial-time circuits. While unlikely to be universal for quantum computation, several of these models appear to be able to outperform classical computers at certain computational tasks, such as sampling from certain probability distributions. Understanding which of these models are capable of performing such tasks and characterizing the classical simulation complexity of these models--i.e. how hard it is to simulate these models on a classical computer--are some of the central questions we address in this thesis. Our first contribution is a classification of various extended Clifford circuits according to their classical simulation complexity. Among these circuits are the conjugated Clifford circuits, which we prove cannot be efficiently classically simulated up to multiplicative or additive error, under certain plausible conjectures in computational complexity theory. Our second contribution is an estimate of the number of qubits needed in various restricted quantum computation models in order for them to be able to demonstrate quantum computational supremacy. Our estimate is obtained by fine-graining existing hardness results for these restricted models. Our third contribution is a new alternative proof of the Gottesman-Knill theorem, which states that Clifford circuits can be efficiently simulated by a classical computer. Our proof uses the sum-over-paths technique and establishes a correspondence between quantum circuits and a class of exponential sums. Our final contribution is a theorem characterizing the operations that can be efficiently simulated using a particular rebit simulator. An application of this result is a generalization of the Gottesman-Knill theorem that allows for the efficient classical simulation of certain nonlinear operations. "Funding support from the National Science Scholarship awarded by the Agency for Science, Technology and Research (A*STAR), Singapore, as well as the Enabling Practical-scale Quantum Computing (EPiQC) Expedition, an NSF expedition in computing"--Page 6. by Dax Enshan Koh. Ph. D. Ph.D. Massachusetts Institute of Technology, Department of Mathematics 2019-09-16T22:33:45Z 2019-09-16T22:33:45Z 2019 2019 Thesis https://hdl.handle.net/1721.1/122164 1117775048 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 372 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Koh, Dax Enshan. Classical simulation complexity of restricted models of quantum computation |
| title | Classical simulation complexity of restricted models of quantum computation |
| title_full | Classical simulation complexity of restricted models of quantum computation |
| title_fullStr | Classical simulation complexity of restricted models of quantum computation |
| title_full_unstemmed | Classical simulation complexity of restricted models of quantum computation |
| title_short | Classical simulation complexity of restricted models of quantum computation |
| title_sort | classical simulation complexity of restricted models of quantum computation |
| topic | Mathematics. |
| url | https://hdl.handle.net/1721.1/122164 |
| work_keys_str_mv | AT kohdaxenshan classicalsimulationcomplexityofrestrictedmodelsofquantumcomputation |