Anand Natarajan

Massachusetts Institute of Technology — United States

Computer Science · Physical Sciences

9h-index412citations25works0.02yr avg
OpenAlex↗Google Scholar↗Lab page↗

Accepting Students?

No reports yet. Know if this professor is taking students?

Research Topics

Quantum Computing Algorithms and Architecture(17), Quantum Mechanics and Applications(10), Complexity and Algorithms in Graphs(10), Quantum Information and Cryptography(9), Computability, Logic, AI Algorithms(8)

Publications25 total

The Computational Advantage of MIP* Vanishes in the Presence of Noise
Journal of the ACM·2025Open Access
Classical Commitments to Quantum States
arXiv (Cornell University)·2024Open Access
Quantum soundness of testing tensor codes
2022· 6 cited
Quantum soundness of testing tensor codes
arXiv (Cornell University)·2021· 1 citedOpen Access
Quantum Search-To-Decision Reductions and the State Synthesis Problem
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)·2021· 7 citedOpen Access
MIP* = RE
Communications of the ACM·2021· 139 citedOpen Access
Quantum soundness of the classical low individual degree test
arXiv (Cornell University)·2020· 12 citedOpen Access
Quantum blackjack: Advantages offered by quantum strategies in communication-limited games
Physical review. A/Physical review, A·2020· 9 citedOpen Access
MIP*=RE
arXiv (Cornell University)·2020· 8 citedOpen Access
NEEXP is Contained in MIP
2019· 22 cited
NEEXP in MIP*
arXiv (Cornell University)·2019· 3 citedOpen Access
NEEXP in MIP.
arXiv (Cornell University)·2019· 8 citedOpen Access
Limitations of Semidefinite Programs for Separable States and Entangled Games
Communications in Mathematical Physics·2019· 14 citedOpen Access
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA
2018· 40 citedOpen Access
Low-degree testing for quantum states
arXiv (Cornell University)·2018· 3 citedOpen Access
Algorithms, Bounds, and Strategies for Entangled XOR Games
arXiv (Cornell University)·2018· 3 citedOpen Access
Verifying quantum proofs with entangled games
DSpace@MIT (Massachusetts Institute of Technology)·2018Open Access
Retracted: Two-Player Entangled Games are NP-Hard
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)·2018Open Access
Two-player entangled games are NP-hard
arXiv (Cornell University)·2017· 6 citedOpen Access
A quantum linearity test for robustly verifying entanglement
2017· 51 citedOpen Access
page 1 of 2Next →

Frequent Co-authors

Thomas Vidick(12), John C. Wright(8), Henry Yuen(6), Zhengfeng Ji(5), Aram W. Harrow(5), Xiaodi Wu(3), Matthew Coudron(1), Joseph X. Lin(1), J. A. Formaggio(1), Sandy Irani(1), Chinmay Nirkhe(1), Sujit Rao(1), Adam Bene Watts(1), Gurtej Kanwar(1), Yangjing Dong(1), Honghao Fu(1), Minglong Qin(1), Hongfei Xu(1), Penghui Yao(1), Sam Gunn(1)