5 papers
Secure Multi-party Quantum Computation with a Dishonest Majority
Yfke Dulek, Alex B. Grilo, Stacey Jeffery +2
The cryptographic task of secure multi-party (classical) computation has received a lot of attention in the last decades. Even in the extreme case where a computation is performed…
Perfect zero knowledge for quantum multiprover interactive proofs
Alex B. Grilo, William Slofstra, Henry Yuen
In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs - notions that are central pillars of complexity theo…
Quantum hardness of learning shallow classical circuits
Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram
In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. I…
Stoquastic PCP vs. Randomness
Dorit Aharonov, Alex B. Grilo
The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quant…
Pointer Quantum PCPs and Multi-Prover Games
Alex B. Grilo, Iordanis Kerenidis, Attila Pereszlényi
The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial…