Chinmay Nirkhe

According to our database, Chinmay Nirkhe authored at least 14 papers between 2018 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

Separating QMA from QCMA with a Classical Oracle.

John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, Mark Zhandry

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

2024

A distribution testing oracle separation between QMA and QCMA.

Anand Natarajan, Chinmay Nirkhe

Quantum, 2024

On the hardness of cloning and connections to representation theory.

Vojtech Havlícek, Chinmay Nirkhe

CoRR, 2024

The status of the quantum PCP conjecture (games version).

Anand Natarajan, Chinmay Nirkhe

CoRR, 2024

2023

NLTS Hamiltonians from Good Quantum Codes.

Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Distribution Testing Oracle Separating QMA and QCMA.

Anand Natarajan, Chinmay Nirkhe

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Lower bounds on the complexity of quantum proofs

Chinmay Nirkhe

PhD thesis, 2022

The Parameterized Complexity of Quantum Verification.

Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, Bryan O'Gorman

CoRR, 2022

The Parametrized Complexity of Quantum Verification.

Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, Bryan O'Gorman

Proceedings of the 17th Conference on the Theory of Quantum Computation, 2022

Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians.

Anurag Anshu, Chinmay Nirkhe

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Quantum Search-To-Decision Reductions and the State Synthesis Problem.

Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen

Proceedings of the 37th Computational Complexity Conference, 2022

2019

Good approximate quantum LDPC codes from spacetime circuit Hamiltonians.

Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, Henry Yuen

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

"Quantum Supremacy" and the Complexity of Random Circuit Sampling.

Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States.

Chinmay Nirkhe, Umesh V. Vazirani, Henry Yuen

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018