BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We show that the n-round parallel repetition of the Magic Square game of Mermin and Peres is rigid, in the sense that for any entangled strategy succeeding with probability 1−ε, the players' shared state is O(poly(nε))-close to 2n EPR pairs under a local isometry. Furthermore, we show that, under local isometry, the players' measurements in said entangled strategy must be O(poly(nε)) close to the "ideal" strategy when acting on the shared state.
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 $\Xlin, \Zlin:\{0,1\}^n\to \text{Obs}_d(\C)$, the set of d-dimensional Hermitian matrices that square to identity. The test enforces that (i) each function is exactly linear, $\Xlin(a)\Xlin(b)=\Xlin(a+b)$ and $\Zlin(a) \Zlin(b)=\Zlin(a+b)$, and (ii) the two functions are approximately complementary, $\Xlin(a)\Zlin(b)\approx (-1)^{a\cdot b} \Zlin(b)\Xlin(a)$.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.