Natarajan, Anand and Vidick, Thomas
(2015)
*Constant-Soundness Interactive Proofs for Local Hamiltonians.*
.
(Submitted)
http://resolver.caltech.edu/CaltechAUTHORS:20160318-160143988

PDF
- Submitted Version
See Usage Policy. 335Kb |

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160318-160143988

## Abstract

We give a quantum multiprover interactive proof system for the local Hamiltonian problem in which there is a constant number of provers, questions are classical of length polynomial in the number of qubits, and answers are of constant length. The main novelty of our protocol is that the gap between completeness and soundness is directly proportional to the promise gap on the (normalized) ground state energy of the Hamiltonian. This result can be interpreted as a concrete step towards a quantum PCP theorem giving entangled-prover interactive proof systems for QMA-complete problems. The key ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld, where the function f : {0,1}^n → {0,1} is replaced by a pair of functions X,Z : {0,1}^n → Obs_d(C), the set of d-dimensional Hermitian matrices that square to identity. The test enforces that (i) each function is exactly linear, X(a)X(b) = X(a+b) and Z(a)Z(b) = Z(a+b), and (ii) the two functions are approximately complementary, X(a)Z(b) ≈ (−1)^(a⋅b)Z(b)X(a).

Item Type: | Report or Paper (Discussion Paper) | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||

ORCID: |
| ||||||||||

Additional Information: | AN was supported by the ARO grant Contract Number W911NF-12-0486. Parts of this work was completed while the second author was visiting the Institute for Quantum Information and Matter (IQIM) at Caltech, and both authors acknowledge funding provided by the IQIM, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). | ||||||||||

Group: | IQIM, Institute for Quantum Information and Matter | ||||||||||

Funders: |
| ||||||||||

Record Number: | CaltechAUTHORS:20160318-160143988 | ||||||||||

Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20160318-160143988 | ||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||

ID Code: | 65495 | ||||||||||

Collection: | CaltechAUTHORS | ||||||||||

Deposited By: | Tony Diaz | ||||||||||

Deposited On: | 18 Mar 2016 23:18 | ||||||||||

Last Modified: | 18 Mar 2016 23:18 |

Repository Staff Only: item control page