497 citations · 1.6k across the 74 of their papers we have counts for
70 papers · 1 filter
Achieving perfect completeness for one- and two-message quantum proof systems
Yupan Liu, Thomas Vidick
While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether perfect completeness is…
Derandomised tensor product gap amplification for quantum Hamiltonians
Thiago Bergamaschi, Tony Metger, Thomas Vidick +1
The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low-energy Hamiltonians even when the gap between "high" and "low" energy is large (constant…
PRS Length Expansion
Romi Levy, Thomas Vidick
One of the most fundamental results in classical cryptography is that the existence of Pseudo-Random Generators (PRG) that expands bits of randomness to bits that are pse…
Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
Irit Dinur, Ting-Chun Lin, Thomas Vidick
We introduce a high-dimensional cubical complex, for any dimension t>0, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the…
Efficiently stable presentations from error-correcting codes
Michael Chapman, Thomas Vidick, Henry Yuen
We introduce a notion of \emph{efficient stability} for finite presentations of groups. Informally, a finite presentation using generators and relations is \emph{stable} if…
Computational Entanglement Theory
Rotem Arnon, Zvika Brakerski, Thomas Vidick
We initiate a rigorous study of computational entanglement theory, inspired by the emerging usefulness of ideas from quantum information theory in computational complexity. We defi…