Teaching
- 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]
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.
- Alex Boulton McKeehan, Master's student, CS, 2022-2023.
Alumni
- Nick Hunter-Jones (2021-2023), postdoc joint with Patrick Hayden, Vedika Khemani, and Xiaoliang Qi, now faculty at UT Austin.
- Goli Emami, Master's student, CS, 2022-2023.
Papers
- Efficient Unitary T-designs from Random Sums. With Chi-Fang Chen, Jordan Docter, Michelle Xu, and Patrick Hayden (2024). [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). To appear 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). To appear 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. To appear 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 06-2023): 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
|
