Skip to Main content
Number of documents


CV - Alex Bredariol Grilo



Since October 2020, I have been a CNRS researcher at LIP6 (CNRS/Sorbonne Université). Previously, I was a post-doc at CWI and QuSoft, a research fellow at the Simons Institute (UC Berkeley) and a PhD student at Université Paris Diderot, where I was affiliated to IRIF. I got my Master's and Bachelor's degree from University of Campinas.


Alex (dot) Bredariol-Grilo (at) lip6 (dot) fr

Research interests

  • Quantum computing
  • Interactive proof systems and PCPs
  • Complexity theory
  • Cryptography


  • CNRS researcher - LIP6 (Sorbonne Université/CNRS) 
    From 10/2020 to present
  • Research Fellow - Simons Institute, UC Berkeley 
    From 01/2020 to 05/2020
  • Lecturer (ATER) - Université Paris Diderot
    From 09/2017 to 04/2018


  • PhD in Computer Science - Université Paris Diderot, France 
    From 09/2014 to 04/2018 
    Title: Quantum proofs, the Local Hamiltonian problem and applications 
    Advisor: Iordanis Kerenidis
  • MSc. in Computer Science - University of Campinas (Unicamp), Brazil 
    From 03/2012 to 04/2014 
    Title: Quantum Computing and Theoretical Computer Science 
    Advisor: Prof. Arnaldo Vieira Moura
  • BSc. in Computer Science - University of Campinas (Unicamp), Brazil
    From 03/2007 to 07/2011

Journal articles2 documents

  • Srinivasan Arunachalam, Alex Grilo, Aarthi Sundaram. Quantum hardness of learning shallow classical circuits. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2021, 50 (3), pp.972-1013. ⟨10.1137/20M1344202⟩. ⟨hal-03043254⟩
  • Alex Grilo, Iordanis Kerenidis, Timo Zijlstra. Learning-with-errors problem is easy with quantum samples. Physical Review A, American Physical Society 2019, 99 (3), ⟨10.1103/PhysRevA.99.032314⟩. ⟨hal-03032826⟩

Conference papers11 documents

  • Dorit Aharonov, Alex Grilo. Two combinatorial MA-complete problems. 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Jan 2021, Online, France. pp.36:1--36:20, ⟨10.4230/LIPIcs.ITCS.2021.36⟩. ⟨hal-03130966⟩
  • Alex Bredariol Grilo, Huijia Lin, Fang Song, Vinod Vaikuntanathan. Oblivious Transfer is in MiniQCrypt. Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Oct 2021, Zagreb, Croatia. pp.531-561, ⟨10.1007/978-3-030-77886-6_18⟩. ⟨hal-03033900⟩
  • Yfke Dulek, Alex Grilo, Stacey Jeffery, Christian Majenz, Christian Schaffner. Secure Multi-party Quantum Computation with a Dishonest Majority. Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2020, Zagreb, Croatia. pp.729-758, ⟨10.1007/978-3-030-45727-3_25⟩. ⟨hal-02968389⟩
  • Anne Broadbent, Alex Bredariol Grilo. QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge. IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Nov 2020, Virtual, United States. ⟨10.1109/FOCS46700.2020.00027⟩. ⟨hal-03123358⟩
  • Gorjan Alagic, Andrew M. Childs, Alex Grilo, Shih-Han Hung. Non-interactive classical verification of quantum computation. Theory of Cryptography - 18th International Conference, TCC 2020, Nov 2020, Durham, United States. pp.153--180, ⟨10.1007/978-3-030-64381-2_6⟩. ⟨hal-03043284⟩
  • Alex Bredariol Grilo. A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Jul 2019, Patras, Greece. pp.28:1--28:13, ⟨10.4230/LIPIcs.ICALP.2019.28⟩. ⟨hal-03033187⟩
  • Alex Grilo, William Slofstra, Henry Yuen. Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Nov 2019, Baltimore, United States. pp.611-635, ⟨10.1109/FOCS.2019.00044⟩. ⟨hal-03032834⟩
  • Dorit Aharonov, Alex Bredariol Grilo. Stoquastic PCP vs. Randomness. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Nov 2019, Baltimore, United States. pp.1000-1023, ⟨10.1109/FOCS.2019.00065⟩. ⟨hal-03032845⟩
  • Andrea Coladangelo, Alex Grilo, Stacey Jeffery, Thomas Vidick. Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources. Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2019, Darmstadt, Germany. pp.247-277, ⟨10.1007/978-3-030-17659-4_9⟩. ⟨hal-03033171⟩
  • Alex Bredariol Grilo, Iordanis Kerenidis, Attila Pereszlényi. Pointer Quantum PCPs and Multi-Prover Games. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, Aug 2016, Kraków, Poland. pp.21:1--21:14, ⟨10.4230/LIPIcs.MFCS.2016.21⟩. ⟨hal-03043224⟩
  • Alex Bredariol Grilo, Iordanis Kerenidis, Jamie Sikora. QMA with Subset State Witnesses. Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Aug 2015, Milan, Italy. pp.163-174, ⟨10.1007/978-3-662-48054-0_14⟩. ⟨hal-03032854⟩

Preprints, Working Papers, ...5 documents

  • Jan Czajkowski, Alex Grilo. On-State Commutativity of Measurements and Joint Distributions of Their Outcomes. 2021. ⟨hal-03123361⟩
  • Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram. Quantum learning algorithms imply circuit lower bounds. 2020. ⟨hal-03040161⟩
  • Alex Bredariol Grilo, Kathrin Hövelmanns, Andreas Hülsing, Christian Majenz. Tight adaptive reprogramming in the QROM. 2020. ⟨hal-02997744⟩
  • Dorit Aharonov, Alex Bredariol Grilo, Yupan Liu. StoqMA vs. MA: the power of error reduction. 2020. ⟨hal-02968357⟩
  • Srinivasan Arunachalam, Alex Grilo, Henry Yuen. Quantum statistical query learning. 2020. ⟨hal-03043275⟩

Theses1 document