497 citations · 1.6k across the 74 of their papers we have counts for
82 papers
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…
Polynomial Hilbert-Schmidt stability of the lamplighter group
Alon Dogon, Thomas Vidick
We establish explicit polynomial bounds on the stability rate and radius of the lamplighter group. This provides the first example of an infinitely presented group with an explicit…
Quantum Interactive Oracle Proofs
Baocheng Sun, Thomas Vidick
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a…
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…
Approximating the quantum value of an LCS game is RE-hard
Aviv Taller, Thomas Vidick
We generalize Håstad's long-code test for projection games and show that it remains complete and sound against entangled provers. Combined with a result of Dong et al. \cite{Dong25…
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…