291 citations · 380 across the 13 of their papers we have counts for
13 papers
A quantum oracle separation between QMA(2) and QMA
John Bostanci, Sabee Grewal, Jonas Haferkamp +4
We find a quantum oracle relative to which . As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every , any $(ε,…
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…
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…
The status of the quantum PCP conjecture (games version)
Anand Natarajan, Chinmay Nirkhe
In classical complexity theory, the two definitions of probabilistically checkable proofs -- the constraint satisfaction and the nonlocal games version -- are computationally equal…
NLTS Hamiltonians from classical LTCs
Zhiyang He, Chinmay Nirkhe
We provide a completely self-contained construction of a family of NLTS Hamiltonians [Freedman and Hastings, 2014] based on ideas from [Anshu, Breuckmann, and Nirkhe, 2022], [Cross…
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…
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…
The Parameterized Complexity of Quantum Verification
Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe +1
We initiate the study of parameterized complexity of problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem o…
Quantum search-to-decision reductions and the state synthesis problem
Sandy Irani, Anand Natarajan, Chinmay Nirkhe +2
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the $\textit{de…
Circuit lower bounds for low-energy states of quantum code Hamiltonians
Anurag Anshu, Chinmay Nirkhe
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower b…
Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe +1
We study approximate quantum low-density parity-check (QLDPC) codes, which are approximate quantum error-correcting codes specified as the ground space of a frustration-free local…
Quantum Supremacy and the Complexity of Random Circuit Sampling
Adam Bouland, Bill Fefferman, Chinmay Nirkhe +1
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A l…
Approximate low-weight check codes and circuit lower bounds for noisy ground states
Chinmay Nirkhe, Umesh Vazirani, Henry Yuen
The No Low-Energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation 2014), which asserts the existence of local Hamiltonians whose low…