Complete List of Publications and Talks

The status of the quantum PCP conjecture (games version)
Anand Natarajan and Chinmay Nirkhe.
[arXiv:2403.13084]
A distribution testing oracle separation between QMA and QCMA
Anand Natarajan and Chinmay Nirkhe.
QIP 2024. CCC 2023. Quantum 2023.
[arXiv:2210.15380] [Proceedings 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.
NLTS Hamiltonians from good quantum codes
Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe.
QIP 2023 (Plenary Talk). CCC 2023 (Invited Talk).
[arXiv:2206.13228] [News Article] [Simons Institute Blog Post] [Proceedings Version] [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.
The parametrized complexity of quantum verification
Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, 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)
Quantum search-to-decision and the state synthesis problem
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, 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)
Circuit lower bounds for low-energy states of quantum code Hamiltonians
Anurag Anshu and Chinmay Nirkhe.
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)
Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
Thom Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, 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)
On the complexity and verification of random circuit sampling
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, 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)
Approximate low-weight check codes and circuit lower bounds for noisy ground states
Chinmay Nirkhe, 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

"Quantum Codes in Quantum Complexity" at Simons Institute Error Correcting Codes Bootcamp. January 2024. (slides | video)
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)

Short Notes

Brandao-Harrow limitation beyond 2-local Hamiltonians? with Anurag Anshu.