5 citations · 8 across the 13 of their papers we have counts for
5 papers · 1 filter
How to Classically Verify a Quantum Cat without Killing It
Yael Tauman Kalai, Dakshita Khurana, Justin Raizes
Existing protocols for classical verification of quantum computation (CVQC) consume the prover's witness state, requiring a new witness state for each invocation. Because QMA witne…
Compiling Any into a (Succinct) Classical Interactive Argument
Andrew Huang, Yael Tauman Kalai
We present a generic compiler that converts any protocol into a succinct interactive argument where the communication and the verifier are classical, and where p…
Parallel Repetition for Post-Quantum Arguments
Andrew Huang, Yael Tauman Kalai
In this work, we show that parallel repetition of public-coin interactive arguments reduces the soundness error at an exponential rate even in the post-quantum setting. Moreover, w…
Quantum Advantage from Any Non-Local Game
Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan +1
We show a general method of compiling any -prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guar…
Constructive Post-Quantum Reductions
Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai
Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interac…