12 citations · 22 across the 7 of their papers we have counts for
8 papers
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…
Succinct arguments for QMA from standard assumptions via compiled nonlocal games
Tony Metger, Anand Natarajan, Tina Zhang
We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work o…
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
David Cui, Giulio Malavolta, Arthur Mehta +5
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work…
Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
Anand Natarajan, Tina Zhang
We present a step towards the goal of producing a general cryptographic 'compilation' procedure which can translate any entangled nonlocal game into a single-prover interactive pro…
Quantum free games
Anand Natarajan, Tina Zhang
The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC'14). There are two complexity classes that can…
Classical proofs of quantum knowledge
Thomas Vidick, Tina Zhang
We define the notion of a proof of knowledge in the setting where the verifier is classical, but the prover is quantum, and where the witness that the prover holds is in general a…
Non-interactive zero-knowledge arguments for QMA, with preprocessing
Andrea Coladangelo, Thomas Vidick, Tina Zhang
We initiate the study of non-interactive zero-knowledge (NIZK) arguments for languages in QMA. Our first main result is the following: if Learning With Errors (LWE) is hard for qua…
Classical zero-knowledge arguments for quantum computations
Thomas Vidick, Tina Zhang
We show that every language in QMA admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowle…