Chinmay Nirkhe

Research Staff Scientist
IBM Quantum, MIT-IBM Watson AI Lab

Hello, I am currently a research staff scientist with IBM Quantum in Cambridge, Massachusetts. Previously, I was a student at Berkeley and Caltech. My research interests are in theoretical computer science centered around quantum information and hardness of approximation. Recently, I've been thinking about the quantum PCP conjecture and the description complexity of quantum states.

Contact Information

• nirkhe@ibm.com | nirkhe@berkeley.edu
• IBM Research, 314 Main St Cambridge, Mass. 02142
• he/him

Select Publications

• NLTS Hamiltonians from good quantum codes
  Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe.
  QIP 2023 (Plenary Talk). CCC 2023 (Invited Talk). STOC 2023.
  [arXiv:2206.13228] [News Article] [Simons Institute Blog Post]
• A distribution testing oracle separation between QMA and QCMA
  Anand Natarajan and Chinmay Nirkhe.
  CCC 2023.
  [arXiv:2210.15380]
• 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]
• 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]
• 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]

CV | All Publications and Talks

Education

• University of California, Berkeley
  Ph.D. Computer Science. 2017 - 2022
  Advisor: Umesh Vazirani
  Thesis: Lower bounds on the complexity of quantum proofs
• California Institute of Technology
  B.S. Mathematics, B.S. Computer Science. 2013 - 2017
  

Teaching

• Berkeley:
  • (Lecturer) CS 294-222: Quantum Interactive Protocols
  • (TA) The Mathematics of Quantum Computation: The 4th Winter School, Hebrew University
  • (TA) CS 294-6: Quantum Computation
  • (TA) CS 170: Efficient Algorithms and Intractable Problems (my course page)
  • (TA) UCSD Trends in Theory 2018 on Quantum Computation
• Caltech:
  • (TA) CS 21: Decidability and Tractability
  • (TA) CS 38: Introduction to Algorithms (lecture notes)
  • (TA) CS 156a: Learning Systems
  • (TA) CS 139: Advanced Algorithms (various notes)

Academic Service