All reports by Author Alex Bredariol Grilo:

__
TR20-043
| 29th March 2020
__

Dorit Aharonov, Alex Bredariol Grilo#### A combinatorial MA-complete problem

Revisions: 2

__
TR19-086
| 7th June 2019
__

Alex Bredariol Grilo, William Slofstra, Henry Yuen#### Perfect zero knowledge for quantum multiprover interactive proofs

__
TR19-041
| 7th March 2019
__

Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram#### Quantum hardness of learning shallow classical circuits

__
TR19-010
| 21st January 2019
__

Dorit Aharonov, Alex Bredariol Grilo#### Stoquastic PCP vs. Randomness

Dorit Aharonov, Alex Bredariol Grilo

Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>>

Alex Bredariol 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 theory,

quantum information and cryptography. In particular, we study the relationship between the

complexity class MIP$^*$ , the set of languages decidable by multiprover interactive ...
more >>>

Srinivasan Arunachalam, Alex Bredariol 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. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>

Dorit Aharonov, Alex Bredariol 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 quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>