Complete list of publications, preprints, and talks

1. A quantum oracle separation between QMA(2) and QMA
   John Bostanci, Sabee Grewal, Jonas Haferkamp, Andrew Huang, Yeongwoo Hwang, Anand Natarajan, and CN.
   [arXiv:2609.02865]
2. Separating QMA from QCMA with a classical oracle
   John Bostanci, Jonas Haferkamp, CN, and Mark Zhandry.
   STOC 2026 (Best Paper Award).
   [arXiv:2511.09551] [Proceedings Version] [Recorded Lecture] [Quanta Magazine Article] [Scieye Blog Post] [Talks/Slides]
   1. NYU CS Seminar, March 2026.
   2. UCLA Condensed Matter Physics Seminar, March 2026.
   3. Institute for Quantum Information and Matter (Caltech) Seminar, March 2026. (slides)
   4. Quantum Meets online seminar, March 2026.
   5. University of Washington CS Theory Seminar, December 2025.
   6. MIT CS ToC Seminar, November 2025. (recording)
   7. Simons Institute Quantum Pod Seminar, November 2025.
3. On the hardness of cloning and connections to representation theory
   Vojtěch Havlíček and CN.
   [arXiv:2411.11805] [Talks/Slides]
   1. University of Washington AQET Seminar, January 2025. (slides)
4. The status of the quantum PCP conjecture (games version)
   Anand Natarajan and CN.
   [arXiv:2403.13084] [Talks/Slides]
   1. University of Washington Theory Lunch, November 2024.
5. A distribution testing oracle separation between QMA and QCMA
   Anand Natarajan and CN.
   QIP 2024. CCC 2023. Quantum 2023.
   [arXiv:2210.15380] [Proceedings Version] [Journal Version] [Notes] [Talks/Slides]

   A previous version of this paper appeared under the title: 'A classical oracle separation between QMA and QCMA'.

   1. University of Washington CS Seminar, January 2024. (slides)
   2. University of Warwick workshop on quantum complexity theory, July 2023.
   3. Weizmann Institute CS Seminar, May 2023.
   4. Caltech IQIM CS Seminar, February 2023.
   5. IQC Math and CS Seminar, December 2022. (slides).
   6. IBM Quantum s3 Meeting, November 2022. (slides).
   7. Harvard Quantum Information Group Meeting, October 2022.
6. NLTS Hamiltonians from good quantum codes
   Anurag Anshu, Nikolas Breuckmann, and CN.
   QIP 2023 (Long plenary talk). CCC 2023 (Invited Talk). STOC 2023.
   [arXiv:2206.13228] [Proceedings Version] [Quanta Magazine Article] [Simons Institute Blog Post] [Talks/Slides]
   1. Computational Complexity Conference, July 2023.
   2. Weizmann Institute, May 2023.
   3. IAS Theory of Computation and Discrete Mathematics Seminar, March 2023. (slides | video).
   4. Stanford Q-FARM Seminar, March 2023. (slides).
   5. Quantum Information Processing, February 2023. (slides | video).
   6. QLA Meets QIT II Workshop, Chicago, Illinois, USA, November 2022. (slides).
   7. Simons Institute for the Theory of Computuing Quantum Colloquium, October 2022. (slides | video).
   8. INTRIQ Biannual Meeting, Montreal, Quebec, Canada, October 2022 (slides).
   9. Columbia University Seminar, October 2022 (slides).
   10. UT Austin, September 2022.
   11. Kavli Institute for Theoretical Physics, UCSB, September 2022 (video).
   12. CIQC Seminar, UC Berkeley, August 2022.
   13. My PhD dissertation, UC Berkeley, August 2022 (slides).
   14. Stanford University Institute for Theoretical Physics, August 2022.
   15. University of Sydney, July 2022.
   16. IBM Quantum Research Group, July 2022.
7. The parametrized complexity of quantum verification
   Srinivasan Arunachalam, Sergey Bravyi, CN, and Bryan O'Gorman.
   TQC 2022.
   [arXiv:2202.08119] [Proceedings Version] [Talks/Slides]
   1. Theory of Quantum Computation, July 2022. (slides)
   2. University of Maryland QuICS Seminar, June 2022.
   3. IBM Quantum Research Group, September 2021. (slides)
8. Quantum search-to-decision and the state synthesis problem
   Sandy Irani, Anand Natarajan, CN, Sujit Rao, and Henry Yuen.
   QIP 2022. CCC 2022.
   [arXiv:2111.02999] [Proceedings Version] [Talks/Slides]
   1. Computational Complexity Conference, July 2022. (slides)
   2. University of Maryland QuICS Seminar, June 2022. (slides)
   3. UC Berkeley Theory Lunch Seminar, April 2022.
   4. Quantum Information Processing 2022, March 2022.
   5. UT Austin Scott Aaronson Group Meeting, December 2021. (slides)
9. Circuit lower bounds for low-energy states of quantum code Hamiltonians
   Anurag Anshu and CN.
   ITCS 2022. QIP 2021. Theory of Computing 2022.
   [arXiv:2011.02044] [Proceedings Version] [Talks/Slides]
   1. Innovations in Theoretical Computer Science, February 2022. (video)
   2. Simons Institute for the Theory of Computing, Quantum Wave in Computing Reunion Workshop, July 2021. (video)
   3. Stanford Patrick Hayden's Group Quantum Seminar, July 2021.
   4. Caltech Thomas Vidick's group Quantum Seminar, March 2021.
   5. Quantum Information Processing 2021, February 2021. (slides | video)
   6. Quantum Code Design and Architectures Seminar, November 2020. (video)
   7. University of Texas, Austin and MIT Joint Quantum Seminar, December 2020. (slides | video)
10. Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
    Thom Bohdanowicz, Elizabeth Crosson, CN, and Henry Yuen.
    STOC 2019. QIP 2019. QEC 2019 (Invited talk).
    [arXiv:1811.00277] [Proceedings Version] [Talks/Slides]
    1. Symposium on the Theory of Computing, June 2019. (slides | poster)
    2. University of Waterloo IQC Seminar, April 2019. (slides)
    3. UC Berkeley Theory Lunch, February 2019.
    4. Berkeley Quantum Information & Computation Center Seminar, December 2018. (slides)
11. On the complexity and verification of random circuit sampling
    Adam Bouland, Bill Fefferman, CN, and Umesh Vazirani.
    Nature Physics 2018. ITCS 2019. QIP 2019.
    [arXiv:1803.04402] [Journal Version] [News Article] [Notes] [Talks/Slides]

    A previous version of this paper appeared under the title: 'Quantum Supremacy and the Complexity of Random Circuit Sampling'.

    1. Indian Symposium on Quantum Information and Technology (ISQIT) Pune, India, December 2019. (slides)
    2. University of Toronto Computer Science / Quantum Information Seminar, March 2019. (slides | video)
    3. Poster at Innovations in Theoretical Computer Science (ITCS) 2019 San Diego, Calif. (poster)
    4. IIT Kanpur Computer Science Seminar, December 2018. (slides)
    5. Simons Institute Industry Day Lightning Talks, May 2018
    6. UC Berkeley Visit Days, March 2018. (slides)
12. Approximate low-weight check codes and circuit lower bounds for noisy ground states
    CN, Umesh Vazirani, and Henry Yuen.
    ICALP 2018. TQC 2018.
    [arXiv:1802.07419] [Proceedings Version] [Talks/Slides]
    1. Theory of Quantum Computing, July 2018. (slides)
    2. Stanford Institute for Theoretical Physics Seminar, May 2018. (slides)
    3. Caltech IQIM, February 2018.

Other Talks

1. Why is quantum mechanics so hard to describe?: A computational lens on the problem at Harvey Mudd College Mathematical Connections Seminar. March 2026. (slides)
2. Finding lessons in quantum oracles at UT Austin Theory Seminar. March 2025. (slides)
3. "Quantum Codes in Quantum Complexity" at Simons Institute Error Correcting Codes Bootcamp. January 2024. (slides | video)
4. Making the leap to Quantum PCPs
   1. "Mathematical [...] Challenges in Quantum Computing" workshop at IPAM UCLA. November 2023. (video)
   2. "Frontiers of near-term quantum computing" workshop at Chalmers University of Technology. August 2023.
   3. "Locality and Complexity in Quantum Thermal Equilibrium" workshop at Harvard University. August 2023.
   4. Simons Institute Summer Cluster 2023. July 2023. (slides | video)

PhD Thesis: PDF

Short Notes

1. The W₁ state is the unique ground-state of a local Hamiltonian.
2. Brandao-Harrow limitation beyond 2-local Hamiltonians. With Anurag Anshu.

Thesis