Adam Bouland

About Me

I am a postdoctoral scholar at UC Berkeley working with Umesh Vazirani. I recently completed my Ph.D. 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.


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

  • Trading Inverses for an Irrep in the Solovay-Kitaev Theorem. With Maris Ozols. (2017) [arXiv]

  • Quantum Advantage from Conjugated Clifford Circuits. With Joseph Fitzismons and Dax Koh. (2017) [arXiv]

  • 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]

  • 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 11-2017): PDF


617 Soda Hall
UC Berkeley
Berkeley, CA 94709

electronic mail: firstname at csail dot mit dot edu

* Original publication by Springer