Quantum computation with identical bosons
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/113995 |
| _version_ | 1811083814371328000 |
|---|---|
| author | Arkhipov, Alex (Aleksandr) |
| author2 | Scott Aaronson. |
| author_facet | Scott Aaronson. Arkhipov, Alex (Aleksandr) |
| author_sort | Arkhipov, Alex (Aleksandr) |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017. |
| first_indexed | 2024-09-23T12:39:46Z |
| format | Thesis |
| id | mit-1721.1/113995 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:39:46Z |
| publishDate | 2018 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1139952019-04-12T17:39:27Z Quantum computation with identical bosons Arkhipov, Alex (Aleksandr) 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, 2017. Cataloged from PDF version of thesis. Includes bibliographical references (pages 103-106). We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system. We explore the challenges in building devices that implement this model and in certifying their correctness. In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1]. We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span. This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world. Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation. We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAMPLING. An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH. We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through. We then discuss experimental implementations of BOSONSAMPLING. The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows. We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one. Finally, we look at the challenge of certifying a BOSONSAMPLING device. We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently. Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution. Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification. We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts. by Aleksandr Arkhipov. Ph. D. 2018-03-02T22:22:12Z 2018-03-02T22:22:12Z 2017 2017 Thesis http://hdl.handle.net/1721.1/113995 1023803120 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 106 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Arkhipov, Alex (Aleksandr) Quantum computation with identical bosons |
| title | Quantum computation with identical bosons |
| title_full | Quantum computation with identical bosons |
| title_fullStr | Quantum computation with identical bosons |
| title_full_unstemmed | Quantum computation with identical bosons |
| title_short | Quantum computation with identical bosons |
| title_sort | quantum computation with identical bosons |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/113995 |
| work_keys_str_mv | AT arkhipovalexaleksandr quantumcomputationwithidenticalbosons |