497 citations · 1.6k across the 74 of their papers we have counts for
5 papers · 1 filter
A parallel repetition theorem for entangled projection games
Irit Dinur, David Steurer, Thomas Vidick
We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game of entangled value 1-eps <…
The Quantum PCP Conjecture
Dorit Aharonov, Itai Arad, Thomas Vidick
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computation…
A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
Zeph Landau, Umesh Vazirani, Thomas Vidick
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states…
Robust Randomness Amplifiers: Upper and Lower Bounds
Matthew Coudron, Thomas Vidick, Henry Yuen
A recent sequence of works, initially motivated by the study of the nonlocal properties of entanglement, demonstrate that a source of information-theoretically certified randomness…
Three-player entangled XOR games are NP-hard to approximate
Thomas Vidick
We show that for any eps>0 the problem of finding a factor (2-eps) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approxim…