Verifying quantum proofs with entangled games
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2018.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/119110 |
| _version_ | 1811076460411092992 |
|---|---|
| author | Natarajan, Anand Venkat |
| author2 | Aram W. Harrow. |
| author_facet | Aram W. Harrow. Natarajan, Anand Venkat |
| author_sort | Natarajan, Anand Venkat |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2018. |
| first_indexed | 2024-09-23T10:22:31Z |
| format | Thesis |
| id | mit-1721.1/119110 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:22:31Z |
| publishDate | 2018 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1191102019-04-12T23:04:35Z Verifying quantum proofs with entangled games Natarajan, Anand Venkat Aram W. Harrow. 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, 2018. Cataloged from PDF version of thesis. Includes bibliographical references (pages 197-205). A team of students has been given a challenging physics exam: find the ground energy of a complicated, n-spin system. Even if they succeed, how can the examiners be sure that their answer is correct without physically measuring all n spins of the ground state, or worse, having to read a description of the 2n components of its wavefunction? The main result of this thesis is a protocol such that, if the examiners are allowed to separately interrogate multiple students, they can be confident that the students possess the n-spin ground state as well as learn its energy to high precision, after exchanging just O(log(n)) bits of classical communication with the students! The protocol and its analysis combine classical computer science techniques for efficiently checking proofs with Bell inequalities. Stated more formally, the main result of this thesis is a multi-prover interactive proof protocol, in which a classical verifier exchanging only O(log(n)) bits of classical communication with 7 untrusted, entangled provers can certify that they share between them an encoding of an n-qubit quantum state Ib), and estimate its energy under a local Hamiltonian H to high (1/ poly(n)) precision. As a consequence, we show that, under poly-time randomized reductions, it is QMA-hard to estimate the entangled value of a nonlocal game up to constant error, proving the quantum entangled games PCP conjecture of Fitzsimons and Vidick. Our main technical innovations are two constructions of robust self-tests for entanglement: two-player nonlocal games where to succeed with probability E-close to 1, the players must share a state that is [delta] = poly([epsilon])-close in trace distance to n EPR pairs. These tests are robust in that [delta] is independent of the number n of EPR pairs being tested. Our techniques draw heavily on the original, "algebraic" proof of the PCP theorem in classical complexity theory, and in particular, each of our robust self-tests is based on a classical locally-testable error correcting code: the first on the Hadamard code and the associated linearity test of Blum, Luby, and Rubinfeld, and the second on Reed-Muller code and the associated low-degree test of Raz and Safra. Supported by NSF Grant CCF-1629809 ARO Contract Number W911NF-12-0486 NSF CAREER Grant CCF-1452616 by Anand Venkat Natarajan. Ph. D. 2018-11-15T16:36:59Z 2018-11-15T16:36:59Z 2018 2018 Thesis http://hdl.handle.net/1721.1/119110 1059577038 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 205 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Physics. Natarajan, Anand Venkat Verifying quantum proofs with entangled games |
| title | Verifying quantum proofs with entangled games |
| title_full | Verifying quantum proofs with entangled games |
| title_fullStr | Verifying quantum proofs with entangled games |
| title_full_unstemmed | Verifying quantum proofs with entangled games |
| title_short | Verifying quantum proofs with entangled games |
| title_sort | verifying quantum proofs with entangled games |
| topic | Physics. |
| url | http://hdl.handle.net/1721.1/119110 |
| work_keys_str_mv | AT natarajananandvenkat verifyingquantumproofswithentangledgames |