6 papers
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…
Asynchronous Quantum Distributed Computing: Causality, Snapshots, and Global Operations
Siddhartha Visveswara Jayanti, Anand Natarajan
We initiate the study of asynchronous quantum distributed systems, focusing on the case of implementing atomic quantum global operations that can be decomposed into a collection of…
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,…
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…