Anand Natarajan

I am an Assistant Professor in EECS and CSAIL at MIT. Prior to starting as a faculty member, I was a postdoc at the Institute for Quantum Information and Matter at Caltech. I obtained my PhD in Physics in 2018 at MIT, under the supervision of Aram Harrow. Office: 32-G624 Email: first name and last initial at mit dot edu “I recognized the professor's characteristic delight at not imparting information.” - Elif Batuman, Either/Or

(Photo credit: Tony Jin)

Research Interests

My research is in theoretical quantum information. I am particularly interested in nonlocality (e.g. Bell inequalities and nonlocal games), quantum complexity theory (especially the power of quantum interactive proof systems), and semidefinite programming hierarchies. My favorite complexity classes are MIP* and QMA(2).

Students and postdocs

Current PhD students: Sunny (Zhiyang) He, Henry Ma, Sujit Rao, Agi Villanyi, Tina Zhang.
Current postdocs: Honghao Fu.

Teaching

“वाच्यतां समयोऽतीतः स्पष्टमग्रे भविष्यति । इति पाठयतां ग्रन्थे काठिन्यं कुत्र विद्यते ॥” - The Kaliviḍambanam of Nīlakaṇṭha Dīkṣitar

• Spring 2023: 6.S895 Quantum Cryptography (with Vinod Vaikuntanathan)

• Fall 2023: 6.1210 (formerly 6.006) Introduction to Algorithms (with Mauricio Karchmer and Nir Shavit).

• Spring 2023: 6.1200 (formerly 6.042) Discrete Mathematics for Computer Science (with Zachary Abel, Brynmor Chapman, and Vinod Vaikuntanathan)

• Fall 2022: 6.2400 Introduction to Quantum Systems Engineering (with Karl Berggren, Ike Chuang, and Kevin O'Brien)

• Spring 2022: 6.845 Quantum Complexity Theory

• Fall 2021: 6.006 Introduction to Algorithms (with Mauricio Karchmer and Julian Shun)

• Spring 2021: 6.006 Introduction to Algorithms (with Mauricio Karchmer and Nir Shavit).

• Fall 2020: 6.S979 Quantum Nonlocality. The official course website is on Canvas. All materials except the video lectures are also available here.

• In the fall of 2017, Aram Harrow and I co-taught a mini-course on SDP Hierarchies and Computational Aspects of Entanglement as part of the trimester on Analysis in Quantum Information Theory at the Institut Henri Poincaré in Paris. Some scribe notes are available here.

Publications and preprints

My papers are available on the arXiv.

• The status of the quantum PCP conjecture (games version)
  With Chinmay Nirkhe.

• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
  With David Cui, Giulio Malavolta, Arthur Mehta, Connor Paddock, Simon Schmidt, Michael Walter, and Tina Zhang.

• The Computational Advantage of MIP* Vanishes in the Presence of Noise
  With Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, and Penghui Yao.

• A Collapsible Polynomial Hierarchy for Promise Problems
  With Chirag Falor and Shu Ge.

• Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
  With Tina Zhang. Presented at FOCS ’23, and at QIP ’24.

• Quantum free games
  With Tina Zhang. Presented at QIP ’23, published in Proc. STOC ’23.

• A distribution testing oracle separation between QMA and QCMA
  With Chinmay Nirkhe. Presented at CCC ’23, and at QIP ’24.

• Quantum Locally Testable Code with Exotic Parameters
  With Andrew Cross, Zhiyang He, Mario Szegedy, and Guanyu Zhu. Presented at QIP ’23.

• Quantum soundness of testing tensor codes
  With Zhengfeng ji, Thomas Vidick, John Wright, and Henry Yuen. Presented at FOCS ’21, published in Discrete Analysis.

• Quantum search-to-decision reductions and the state synthesis problem
  With Sandy Irani, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Presented at QIP ’22, published in Proc. CCC ’22.

• Quantum soundness of the classical low individual degree test
  With Zhengfeng Ji, Thomas Vidick, John Wright, and Henry Yuen.

• MIP* = RE
  With Zhengfeng Ji, Thomas Vidick, John Wright, and Henry Yuen.

• NEEXP ⊆ MIP*
  With John Wright. Talk slides available here. Winner of FOCS 2019 Best Paper award.

• Low-degree testing for quantum states
  With Thomas Vidick. Presented at QIP’18, published in Proc. FOCS’18.

• Algorithms, Bounds, and Strategies for Entangled XOR Games
  With Adam Bene Watts, Aram Harrow, and Gurtej Kanwar. Published in Proc. ITCS’19.

• Two-player entangled games are NP-hard
  With Thomas Vidick. Withdrawn from Proc. CCC’18 due to an error in this cited result. See the erratum notice here. Partially superseded by 2009.12982.

• Tight SoS-degree bounds for approximate Nash equilibria
  With Aram Harrow and Xiaodi Wu. Published in Proc. CCC’16.

• Limitations of semidefinite programs for separable states and entangled games
  With Aram Harrow and Xiaodi Wu. Presented at QIP’17, pubished in Commun. Math. Phys. Vol. 366, No. 2, pp 423-468 (2019).

• Robust self-testing of many-qubit states
  With Thomas Vidick. Presented at QIP’17, published in Proc. STOC’17. See also this blog post by Thomas Vidick for a perspective in terms of approximate representations of groups.

• The Parallel-Repeated Magic Square Game is Rigid
  With Matthew Coudron. Presented at QIP’17.

• An improved semidefinite programming hierarchy for testing entanglement
  With Aram Harrow and Xiaodi Wu. Published in Commun. Math. Phys. Vol. 352, No. 3, pp 881-904 (2017). MATLAB code available on GitHub.

Accessibility

For accessibility information, see here.