Research Group
- Tamara Kohler, postdoc joint with Patrick Hayden.
- Shaun Datta, 6th year PhD student, ICME.
- Zixin (Jack) Zhou, 4th year PhD student, CS, jointly advised with Aviad Rubinstein.
- Jordan Docter, 3rd year PhD student, CS, jointly advised with Patrick Hayden.
- Chenyi Zhang, 3rd year PhD student, CS, jointly advised with Aaron Sidford.
- Jessica Yeh, 2nd year PhD student, Physics, jointly advised with Patrick Hayden.
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). To appear as a contributed talk at QIP 2025. [arXiv]
- The state hidden subgroup problem and an efficient algorithm for locating unentanglement. With Tudor Giurgica-Tiron and John Wright (2024). To appear as a short plenary talk at QIP 2025. [arXiv]
- Efficient unitary designs and pseudorandom unitaries from permutations. With Chi-Fang Chen, Fernando Brandao, Jordan Docter, Patrick Hayden, and Michelle Xu (2024). In Proc. FOCS 2024, and to appear as a contributed talk at QIP 2025 (merged with below). [arXiv]
- Efficient Unitary T-designs from Random Sums. With Chi-Fang Chen, Jordan Docter, Michelle Xu, and Patrick Hayden (2024). In Proc. FOCS 2024, and to appear as a contributed talk at QIP 2025 (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 11-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
|
