Adam Bouland

About Me

I am a postdoctoral researcher at UC Berkeley working with Umesh Vazirani. I completed my Ph.D. in 2017 in the Theory of Computation Group at MIT working with Scott Aaronson. My interests include quantum computation, computational complexity theory, and connections with physics.

Prior to MIT, I completed Part III at Cambridge as well as a Master's under the supervision of Anuj Dawar on a Marshall Scholarship. Prior to that, I completed my undergraduate degree at Yale in Computer Science/Mathematics and Physics.


  • Quantum Supremacy and the Complexity of Random Circuit Sampling. With Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. (2018) [arXiv]

  • Classical Lower Bounds from Quantum Upper Bounds. With Shalev Ben-David, Robin Kothari and Ankit Garg. Presented as a contributed talk at QIP 2018. To be presented as an invited talk at TQC 2018 (In prep.) [Video of QIP talk]

  • Trading Inverses for an Irrep in the Solovay-Kitaev Theorem. With Maris Ozols. To appear in Proc. TQC'18. (2018) [arXiv]

  • Complexity Classification of Conjugated Clifford Circuits. With Joseph Fitzismons and Dax Koh. To appear in Proc. CCC'18 (2018) [arXiv] Note: a previous version of this paper appeared under the title "Quantum Advantage from Conjugated Clifford Circuits".

  • The Computational Complexity of Ball Permutations. With Scott Aaronson, Greg Kuperberg, and Saeed Mehraban. In Proc. STOC 2017. [arXiv, STOC]

  • On the Power of Statistical Zero Knowledge. With Lijie Chen, Dhiraj Holden, Justin Thaler and Prashant Nalini Vasudevan. In Proc. FOCS 2017. [ECCC, arXiv] Note: a previous version of this paper appeared under the title "On SZK and PP".

  • Rescuing Complementarity With Little Drama. With Ning Bao, Aidan Chatwin-Davies, Jason Pollack and Henry Yuen. Journal of High Energy Physics (JHEP) 2016:26 (2016). [arXiv, JHEP]

  • On the complexity of probabilistic trials for hidden satisfiability problems. With Itai Arad, Daniel Grier, Miklos Santha, Aarthi Sundaram and Shengyu Zhang. In Proc. MFCS '16. [arXiv, MFCS, PDF]

  • Complexity classification of two-qubit commuting hamiltonians. With Laura Mančinska and Xue Zhang. In Proc. CCC '16. Presented as a contributed talk at QIP 2016. [arXiv, CCC, ECCC, PDF, Video of QIP Talk]

  • Grover search and the no-signaling principle. With Ning Bao and Stephen Jordan. Physical Review Letters 117, 120501 (2016) [PRL, arXiv]

  • The space "just above" BQP. With Scott Aaronson, Joseph Fitzsimons and Mitchell Lee. In Proc. ITCS '16. [arXiv, ITCS, ECCC, PDF]

  • Generation of Universal Linear Optics by Any Beamsplitter. With Scott Aaronson. Physical Review A 89, 062316 (2014). Editor's suggestion. Presented as a contributed talk at QIP 2015. [PRA, arXiv, ECCC, PDF, Video of QIP Talk]

  • Psi-Epistemic Theories: The Role of Symmetry. With Scott Aaronson, Lynn Chua and George Lowther. Physical Review A 88, 032111 (2013). Editor's suggestion. [PRA, arXiv]

  • On Tractable Parameterizations of Graph Isomorphism. With Anuj Dawar and Eryk Kopczyński. In D.M. Thilikos and G.J. Woeginger (Eds.): IPEC 2012, LNCS 7535, pp. 218-230, Springer 2012. [PDF*, LNCS].

  • Caching and Interpolated Likelihoods: Accelerating Cosmological Monte Carlo Markov Chains. With Richard Easther and Katherine Rosenfeld. Journal of Cosmology and Astroparticle Physics 2011. [arXiv, JCAP]

Other writings

  • Establishing Quantum Advantage. XRDS: Crossroads, The ACM Magazine for Students . Volume 23 Issue 1, Fall 2016, Pages 40-44 (2016) [XRDS]

CV (last updated 05-2018): PDF


617 Soda Hall
UC Berkeley
Berkeley, CA 94709

electronic mail: firstname at csail dot mit dot edu

* Original publication by Springer