1 citations · 1 across the 5 of their papers we have counts for
6 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 $(ε,…
Rounding Almost Commuting Hamiltonians
Islam Faisal, Anand Natarajan, Alexander Poremba
Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics, exhibiting rich quantum structure while remaining more tractable…
A Relativizing MIP for BQP
Scott Aaronson, Anand Natarajan, Avishay Tal +1
Complexity class containments involving interactive proof classes are famously nonrelativizing: although , Fortnow and Sipser showed that that there…
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…
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
David Cui, Giulio Malavolta, Arthur Mehta +5
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work…
The Computational Advantage of MIP* Vanishes in the Presence of Noise
Yangjing Dong, Honghao Fu, Anand Natarajan +3
Quantum multiprover interactive proof systems with entanglement MIP* are much more powerful than its classical counterpart MIP (Babai et al. '91, Ji et al. '20): while MIP = NEXP,…