4 papers
Separating QMA from QCMA with a classical oracle
John Bostanci, Jonas Haferkamp, Chinmay Nirkhe +1
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly big…
NLTS Hamiltonians from good quantum codes
Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe
The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of non-trivial complex…
On the hardness of cloning and connections to representation theory
VojtÄch HavlÃÄek, Chinmay Nirkhe
The states accepted by a quantum circuit are known as the witnesses for the quantum circuit's satisfiability. The assumption BQP does not equal QMA implies that no efficient algori…
A distribution testing oracle separation between QMA and QCMA
Anand Natarajan, Chinmay Nirkhe
It is a long-standing open question in quantum complexity theory whether the definition of quantum computation requires quantum witnesses $(\textsf{QMA…