1 citations · 1 across the 5 of their papers we have counts for
8 papers · 1 filter
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…
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…