A Caltech Library Service

Constant-Soundness Interactive Proofs for Local Hamiltonians

Natarajan, Anand and Vidick, Thomas (2015) Constant-Soundness Interactive Proofs for Local Hamiltonians. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
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:UNSPECIFIED, Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-12-0486
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Record Number:CaltechAUTHORS:20160318-160143988
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65495
Deposited By: Tony Diaz
Deposited On:18 Mar 2016 23:18
Last Modified:04 Jun 2020 10:14

Repository Staff Only: item control page