Research Group
- Tamara Kohler, postdoc joint with Patrick Hayden.
- Tudor Giurgica-Tiron, 6th year PhD student, Applied Physics.
- Shaun Datta, 5th year PhD student, ICME.
- Zixin (Jack) Zhou, 3rd year PhD student, CS, jointly advised with Aviad Rubinstein.
- Jordan Docter, 2nd year PhD student, CS, jointly advised with Patrick Hayden.
- Chenyi Zhang, 2nd year PhD student, CS, jointly advised with Aaron Sidford.
- Jessica Yeh, 1st year PhD student, Physics, jointly advised with Patrick Hayden.
- Victor Shyaka, MS student, Computer Science.
Alumni
- Nick Hunter-Jones (2021-2023), postdoc joint with Patrick Hayden, Vedika Khemani, and Xiaoliang Qi, now faculty at UT Austin.
- 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 [Planned]
- 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
- 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
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
|
