6 papers
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…
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{Dong2…
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…
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…
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…