Adam Bouland

About Me

I am recruiting a postdoc to join my group in Fall'25, please apply to the Bloch fellowship (deadline: Nov 1) and Motwani fellowship (deadline: Dec 1) if interested! I am also recruiting PhD students, please apply to Stanford CS if interested. There is no need to contact me in advance of applying to either position.

I am an Assistant Professor of Computer Science in the CS Theory Group at Stanford. My interests include quantum computation, computational complexity theory, and connections with physics.

Prior to coming to Stanford, I completed my Ph.D. in 2017 at MIT advised by Scott Aaronson, followed by a postdoc at UC Berkeley and the Simons Institute for the Theory of Computing advised by Umesh Vazirani.

Research Group

Alumni

  • Nick Hunter-Jones, postdoc joint with Patrick Hayden, Vedika Khemani, and Xiaoliang Qi 2021-2023, now faculty at UT Austin.
  • Tudor Giurgica-Tiron, PhD 2024 in Applied Physics, now Hartree postdoctoral fellow at QuICS/University of Maryland
  • Victor Shyaka, MS student, Computer Science, 2023-2024.
  • Goli Emami, MS student, Computer Science, 2022-2023.
  • Alex Boulton McKeehan, MS student, Computer Science, 2022-2023.

Teaching

  • CS359D: Quantum Complexity Theory. Winter quarter 2025 [Planned]

  • CS259Q: Quantum Computation. Fall quarter 2024 [Canvas]

  • CS259Q: Quantum Computation. Fall quarter 2023 [Canvas]

  • CS359D: Quantum Complexity Theory. Spring quarter 2023 [Canvas]

  • CS259Q: Quantum Computation. Winter quarter 2023 [Canvas]

  • CS259Q: Quantum Computation. Winter quarter 2022. [Canvas]

Papers

  • On the average-case hardness of BosonSampling. With Ishaun Datta, Bill Fefferman, and Felipe Hernandez (2024). [arXiv]

  • Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary. With Chris Akers, Lijie Chen, Tamara Kohler, Tony Metger, and Umesh Vazirani (2024). [arXiv]

  • On the hardness of learning ground state entanglement of geometrically local Hamiltonians. With Chenyi Zhang and Zixin (Jack) Zhou (2024). [arXiv]

  • The state hidden subgroup problem and an efficient algorithm for locating unentanglement. With Tudor Giurgica-Tiron and John Wright (2024). [arXiv]

  • Efficient unitary designs and pseudorandom unitaries from permutations. With Chi-Fang Chen, Fernando Brandao, Jordan Docter, Patrick Hayden, and Michelle Xu (2024). To appear in Proc. FOCS 2024 (merged with below). [arXiv]

  • Efficient Unitary T-designs from Random Sums. With Chi-Fang Chen, Jordan Docter, Michelle Xu, and Patrick Hayden (2024). To appear in Proc. FOCS 2024 (merged with above). [arXiv]

  • Pseudorandomness from subset states. With Tudor Giurgica-Tiron (2023). [arXiv]

  • Complexity-theoretic foundations of BosonSampling with a linear number of modes. With Daniel Brod, Shaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, and Michal Oszmaniec (2023). Presented as a contributed talk at QIP 2024. [arXiv]

  • Public-key pseudoentanglement and the hardness of learning ground state entanglement structure. With Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh Vazirani, Chenyi Zhang and Zixin Zhou (2023). In Proc. CCC 2024. Presented as a contributed talk at QIP 2024. [arXiv]

  • Quantum Pseudoentanglement [see v2 for recent updates]. With Scott Aaronson, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang and Zixin Zhou (2022). Presented as a contributed talk at QIP 2023. In Proc. ITCS'24. [arXiv, Video of QIP talk]

  • A quantum spectral method for simulating stochastic processes, with applications to Monte Carlo. With Aditi Dandapani and Anupam Prakash (2023). [arXiv]

  • Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling. With Yosheb Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian (2023). Presented as a contributed talk at QIP 2023. In Proc. ICML'23. [arXiv, Video of QIP talk]

  • Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm. With Tudor Giurgica-Tiron (2021). Presented as a contributed talk at QIP 2022. [arXiv, Video of QIP talk]

  • On Certified Randomness from Quantum Advantage Experiments. With Roozbeh Bassirian, Bill Fefferman, Sam Gunn, and Avishay Tal (2021). [arXiv]

  • Noise and the frontier of quantum supremacy. With Bill Fefferman, Zeph Landau and Yunchao Liu (2021). Presented as a contributed talk at QIP 2021. In Proc. FOCS'21. [arXiv, Video of QIP talk]

  • Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality. With Bill Fefferman and Umesh Vazirani (2019). In Proc. ITCS'20. [arXiv, ITCS]

  • Closing gaps of a quantum advantage with short-time Hamiltonian dynamics. With Jonas Haferkamp, Dominik Hangleiter, Bill Fefferman, Jens Eisert, and Juani Bermejo-Vega. Physical Review Letters 125, 250501 (2020). [arXiv, PRL]

  • On the Complexity and Verification of Quantum Random Circuit Sampling. With Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. Nature Physics 15:159-163 (2019). Abstract in Proc. ITCS'2019. Presented as a contributed talk at QIP 2019. [arXiv, Nature physics] Note: a previous version of this paper appeared under the title "Quantum Supremacy and the Complexity of Random Circuit Sampling".

  • Classical Lower Bounds from Quantum Upper Bounds. With Shalev Ben-David, Robin Kothari and Ankit Garg. In Proc. FOCS'18. Presented as a contributed talk at QIP 2018. Presented as an invited talk at TQC 2018. [arXiv, FOCS, Video of QIP talk]

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

  • Complexity Classification of Conjugated Clifford Circuits. With Joseph Fitzismons and Dax Koh. In Proc. CCC'18 (2018) [arXiv, CCC] 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. To appear in SICOMP Special Issue for FOCS'17. [ECCC, arXiv, FOCS] 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]

Surveys and expository writings

  • Prospects and challenges of quantum finance. With Wim van Dam, Hamed Joorati, Iordanis Kerenidis and Anupam Prakash. [arXiv]
  • Establishing Quantum Advantage. XRDS: Crossroads, The ACM Magazine for Students. Volume 23 Issue 1, Fall 2016, Pages 40-44 (2016) [XRDS]

CV (last updated 04-2024): PDF

Service:

  • Program Committee Member for FOCS 2019, QIP 2020, STOC 2023, QIP 2024, ITCS 2025
  • Contact

    172 Gates Computer Science Building
    353 Jane Stanford Way
    Stanford University
    Stanford, CA 94305

    electronic mail: firstinitial lastname at stanford dot edu


    * Original publication by Springer