Publications

Selected research papers (see also a complete list on the arXiv)

  • Quantum Pseudoentanglement with A. Bouland, S. Ghosh, U. Vazirani, Z. Zhou.
    Accepted talk at Conference on Quantum Information Processing (QIP 2023), [arXiv]
  • Noise and the frontier of quantum supremacy with A. Bouland, Z. Landau, Y. Liu.
    To appear in Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS 2021)
    Accepted talk at Conference on Quantum Information Processing (QIP 2021), [arXiv]
  • Eliminating intermediate measurements in space-bounded quantum computation with Z. Remscrim
    In Proceedings of ACM Symposium on Theory of Computing (STOC 2021)
    Accepted talk at Conference on Quantum Information Processing (QIP 2021), See also coverage of this work in [Quanta magazine] [arXiv]
  • The importance of the spectral gap in estimating ground-state energies with A. Deshpande, A.V. Gorshkov
    Accepted talk at Conference on Quantum Information Processing (QIP 2021), In Proceedings of Innovations in Theoretical Computer Science (ITCS 2022)[arXiv]
  • Closing gaps of a quantum advantage with short-time Hamiltonian dynamics with J. Haferkamp, D. Hangleiter, A. Bouland, J. Eisert, J. Bermejo-Vega
    In Physical Review Letters 125, 250501, 2020 [journal, arXiv]
  • Efficient classical simulation of noisy random quantum circuits in one dimension with K. Noh, L. Jiang
    In Quantum [journal, arXiv]
  • Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality with A. Bouland, U. Vazirani
    In Proceedings of Innovations in Theoretical Computer Science (ITCS 2020), See also coverage of this work in [Quanta magazine][arXiv]
  • “Quantum Supremacy” and the Complexity of Random Circuit Sampling with A. Bouland, C. Nirkhe, U. Vazirani
    In Nature Physics (Article, November 2018) (See also the press release from UC Berkeley)
    Accepted talk at QIP 2019 in Boulder, Colorado.
    In Proceedings of Innovations in Theoretical Computer Science (ITCS 2019) [Nature Physics, arXiv]
  • Dynamical phase transitions in sampling complexity with A. Deshpande, M.C. Tran, M. Foss-Feig, A.V. Gorshkov
    In Physical Review Letters 121, 030501, 2018 [pdf, arXiv]
  • Exact Sampling Hardness of Ising Spin Models with M. Foss-Feig, A.V. Gorshkov
    In Physical Review A, vol. 96, no. 3, 2017 [pdf, arXiv]
  • Space-Efficient Error Reduction for Unitary Quantum Computations  with H. Kobayashi, C. Lin, T. Morimae, and H. Nishimura
    Accepted talk at Asian Quantum Information Science Conference (AQIS 2016). In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP 2016) [pdf, arXiv]
  • A Complete Characterization of Unitary Quantum Space with C. Lin
    Accepted talk at Conference on Quantum Information Processing (QIP 2017). In Proceedings of Innovations in Theoretical Computer Science (ITCS 2018) [pdf, arXiv]
  • Computational Security of Quantum Encryption with G. Alagic, A. Broadbent, T. Gagliardoni, C. Schaffner, and M. St. Jules
    Accepted talk at International Conference on Quantum Cryptography (QCrypt 2016).
    In Proceedings of International Conference on Information Theoretic Security (ICITS 2016) [pdf, arXiv]
  • Quantum vs Classical Proofs and Subset Verification with S. Kimmel
    In Proceedings of Mathematical Foundations of Computer Science (MFCS 2018) [pdf, arXiv]
  • On The Power of Quantum Fourier Sampling with C. Umans
    In Proceedings of Theory of Quantum Computation, Communication, and Cryptography (TQC 2016)   [pdf, arXiv]
  • On Beating the Hybrid Argument with R. Shaltiel, C. Umans and E.Viola
    In Theory of Computing Journal, 9(26):809-843, 2013. [ToC]
    In Proceedings of Innovations in Theoretical Computer Science (ITCS 2012) [ECCC, Conference abstract]
  • Pseudorandom Generators and the BQP vs PH Problem with C. Umans
    Accepted to Conference on Quantum Information Processing (QIP 2011) as a featured talk [pdf, arXiv]
  • The Power of Unentanglement with S. Aaronson, S. Beigi, A. Drucker, P. Shor
    In Theory of Computing Journal, 5(1):1-42, 2009. [ToC]
    In Proceedings of IEEE Conference on Computational Complexity 2008 [Conference abstract,arXiv]

Expository writings

  • Toward noise-robust quantum advantage, Invited piece, Nature Physics [Nature Physics]
  • The coming of the quantum age, Invited blog post (with F. Chong) [ACM SIGARCH blog]
  • On experimentally relevant quantum speedups, Invited perspective piece [Quantum journal]