Quantum proof systems and entanglement theory
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/50594 |
| _version_ | 1811093525110980608 |
|---|---|
| author | Abolfathe Beikidezfuli, Salman |
| author2 | Peter W. Shor. |
| author_facet | Peter W. Shor. Abolfathe Beikidezfuli, Salman |
| author_sort | Abolfathe Beikidezfuli, Salman |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009. |
| first_indexed | 2024-09-23T15:46:30Z |
| format | Thesis |
| id | mit-1721.1/50594 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:46:30Z |
| publishDate | 2010 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/505942019-04-12T23:33:55Z Quantum proof systems and entanglement theory Abolfathe Beikidezfuli, Salman Peter W. Shor. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009. Includes bibliographical references (p. 99-106). Quantum complexity theory is important from the point of view of not only theory of computation but also quantum information theory. In particular, quantum multi-prover interactive proof systems are defined based on complexity theory notions, while their characterization can be formulated using LOCC operations. On the other hand, the main resource in quantum information theory is entanglement, which can be considered as a monotonic decreasing quantity under LOCC maps. Indeed, any result in quantum proof systems can be translated to entanglement theory, and vice versa. In this thesis I mostly focus on quantum Merlin-Arthur games as a proof system in quantum complexity theory. I present a new complete problem for the complexity class QMA. I also show that computing both the Holevo capacity and the minimum output entropy of quantum channels are NP-hard. Then I move to the multiple-Merlin-Arthur games and show that assuming some additivity conjecture for entanglement of formation, we can amplify the gap in QMA(2) protocols. Based on the same assumption, I show that the QMA(k)-hierarchy collapses to QMA(2). I also prove that QMAlog(2), which is defined the same as QMA(2) except that the size of witnesses is logarithmic, with the gap n-(3+e) contains NP. Finally, motivated by the previous results, I show that the positive partial transpose test gives no bound on the trace distance of a given bipartite state from the set of separable states. by Salman Abolfathe Beikidezfuli. Ph.D. 2010-01-07T20:58:17Z 2010-01-07T20:58:17Z 2009 2009 Thesis http://hdl.handle.net/1721.1/50594 465219430 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 106 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Abolfathe Beikidezfuli, Salman Quantum proof systems and entanglement theory |
| title | Quantum proof systems and entanglement theory |
| title_full | Quantum proof systems and entanglement theory |
| title_fullStr | Quantum proof systems and entanglement theory |
| title_full_unstemmed | Quantum proof systems and entanglement theory |
| title_short | Quantum proof systems and entanglement theory |
| title_sort | quantum proof systems and entanglement theory |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/50594 |
| work_keys_str_mv | AT abolfathebeikidezfulisalman quantumproofsystemsandentanglementtheory |