Srinivasan Arunachalam

my picture

I am a Senior Research Scientist at IBM T. J. Watson Research Center.

Prior to this, I was a Postdoctoral Researcher at the Center for Theoretical Physics, MIT.
I received my Ph.D. in 2018 from Centrum Wiskunde & Informatica and QuSoft, Amsterdam, Netherlands, supervised by Ronald de Wolf. Before that I finished my M.Math in Mathematics from University of Waterloo and Institute of Quantum Computing, Canada in 2014, supervised by Michele Mosca.

Research interests

Quantum algorithms, Quantum learning theory, Quantum complexity theory, Analysis of Boolean functions.

Contact information

Email: srinivasan (dot) arunachalam (at) ibm (dot) com

Professional Services

Editor: Quantum
PC member: QCTIP 2020, TQC 2021, STOC 2023, QIP 2024, TQC 2024, ITCS 2025, QIP 2025

Papers

  1. Quantum impurity models: easy at equilibrium, universal in motion
    Srinivasan Arunachalam, Sergey Bravyi, Anirban Chowdhury, Arkopal Dutt, Zhi Li, Alexandru Gheorghiu
    [arXiv]

  2. Optimal Quantum-Classical Separations for Exact Learning
    Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil Mande
    [arXiv]

  3. Learning SYK Hamiltonians
    Anurag Anshu, Srinivasan Arunachalam, Sitan Chen, Yeongwoo Hwang
    [arXiv]

  4. Marton's conjecture in polynomial time
    Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, Aparna Gupte
    [arXiv]

POST/PRE LLM

  1. Learning Random Quantum Circuits and the Emergence of Pseudorandomness
    Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha
    [arXiv]

  2. Quantum Query Complexity Beyond the Worst Case
    Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani
    [arXiv]

  3. Separating quantum circuits from classical LLMs
    Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi, Rik Sengupta
    [arXiv]

  4. No low-degree tests for quantum states
    Omar Alrabiah, Srinivasan Arunachalam, Sabee Grewal, John Wright
    [arXiv]

  5. Optimal Stabilizer Testing and Learning with Limited Quantum Memory
    Srinivasan Arunachalam, Louis Schatzki
    [arXiv]

  6. Tomography of quantum states with bounded extent
    Srinivasan Arunachalam, Arkopal Dutt
    [arXiv]

  7. Learning stabilizer structure of quantum states
    Srinivasan Arunachalam, Arkopal Dutt
    [arXiv]
    Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026)

  8. Learning depth-3 circuits via quantum agnostic boosting
    Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael de Oliveira
    Presented at the 29th Annual Conference on Quantum Information Processing (QIP 2026)
    [arXiv]
    Proceedings of the 39th Conference on Learning Theory (COLT 2026) — [COLT 2026]

  9. An algorithmic Polynomial Freiman-Ruzsa theorem
    (subsumes the paper below)
    Srinivasan Arunachalam, Jop Briet, Davi Castro Silva, Arkopal Dutt, Tom Gur
    Presented at the 29th Annual Conference on Quantum Information Processing (QIP 2026)
    [arXiv]
    Expanded 2026 preprint (incorporates earlier PFR preprints)

  10. Classical and Quantum Polynomial Freiman-Ruzsa Algorithms
    Srinivasan Arunachalam, Davi Castro Silva, Arkopal Dutt, Tom Gur
    Proceedings of the 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
    [arXiv]
    [ITCS 2026]

  11. Polynomial-time tolerant testing stabilizer states
    Srinivasan Arunachalam, Arkopal Dutt
    Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    Presented at the 29th Annual Conference on Quantum Information Processing (QIP 2026)
    [arXiv]

  12. A note on polynomial-time tolerant testing stabilizer states
    Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt
    Incorporated into the expanded version of the STOC 2025 paper above.
    [arXiv]

  13. Generalized Inner Product Estimation with Limited Quantum Communication
    Srinivasan Arunachalam, Louis Schatzki
    Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS 2025)
    Talk at Theory of Quantum computation, Communication & Cryptography (TQC 2025)
    [arXiv]
    [STACS 2025]

  14. Testing and learning structured quantum Hamiltonians
    Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez
    Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    Talk at Theory of Quantum computation, Communication & Cryptography (TQC 2025)
    [arXiv]

  15. One Clean Qubit Suffices for Quantum Communication Advantage
    Srinivasan Arunachalam, Uma Girish, Noam Lifshitz
    Talk at Theory of Quantum computation, Communication & Cryptography (TQC 2024)
    [arXiv]

  16. Quantum computing for high-energy physics
    White paper with IBM, CERN and DESY
    Physical Review X
    [arXiv]

  17. A survey on the complexity of learning quantum states
    Srinivasan Arunachalam, Anurag Anshu
    Nature Reviews Physics
    [arXiv]

  18. On the role of entanglement and statistics in learning
    Srinivasan Arunachalam, Vojtech Havlicek, Louis Schatzki
    Proceedings of Neural Information Processing Systems (NeurIPS 2023)
    Talk at Theory of Quantum computation, Communication & Cryptography (TQC 2024)
    [arXiv]

  19. Learning low-degree quantum objects
    Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, Carlos Palazuelos
    Proceedings of International Colloquium on Automata, Languages & Programming (ICALP 2024)
    Talk at Theory of Quantum computation, Communication & Cryptography (TQC 2024)
    Mathematische Annalen
    [arXiv]

  20. Trade-offs between entanglement and communication
    Srinivasan Arunachalam, Uma Girish
    Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024)
    Proceedings of Conference on Computational Complexity (CCC 2023)
    [arXiv]

  21. A note on the partition bound for one-way classical communication complexity
    Srinivasan Arunachalam, João F. Doriguello, Rahul Jain
    Updated September 2026
    [arXiv]

  22. Optimal algorithms for learning quantum phase states
    Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, Ted Yoder
    Presented at the 24th Conference on Quantum Information Processing (QIP 2023)
    Proceedings of Theory of Quantum computation, Communication & Cryptography (TQC 2023)
    [arXiv]

  23. The parametrized complexity of quantum verification
    Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, Bryan O'Gorman
    Proceedings of Theory of Quantum computation, Communication & Cryptography (TQC 2022)
    [arXiv]

  24. On the Gaussian surface area of spectrahedra
    Srinivasan Arunachalam, Oded Regev, Penghui Yao
    GAFA Seminar Notes
    [arXiv]

  25. Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
    Srinivasan Arunachalam, João F Doriguello
    ACM Transactions on Computation Theory
    [arXiv]

  26. Positive spectrahedra: Invariance principles and Pseudorandom generators
    Srinivasan Arunachalam, Penghui Yao
    Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
    [arXiv]

  27. Private learning implies quantum stability
    Srinivasan Arunachalam, Yihui Quek, John Smolin
    Spotlight talk at Conference on Neural Information Processing Systems (NeurIPS 2021)
    [arXiv] [NeurIPS 2021]

  28. Quantum learning algorithms imply circuit lower bounds
    Srinivasan Arunachalam, Alex B. Grilo , Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
    Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS 2021)
    Presented at the 24th Conference on Quantum Information Processing (QIP 2021)
    [arXiv]

  29. A rigorous and robust quantum speed-up in supervised machine learning
    Yunchao Liu, Srinivasan Arunachalam, Kristan Temme
    Nature Physics 2021
    [arXiv] [Nature Physics 2021]
    See [Quanta] [MarketTechPost] [Phys.org] [Silicon Republic] [IBM blogpost] for coverage of our work

  30. Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
    Srinivasan Arunachalam, Vojtech Havlicek , Giacomo Nannicini , Kristan Temme, Pawel Wocjan
    Proceedings of IEEE Quantum Week 2021 (Best Paper Award)
    [arXiv]

  31. Communication memento: Memoryless communication complexity
    Srinivasan Arunachalam, Supartha Podder
    Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
    [arXiv]

  32. Sample efficient learning of quantum many-body systems
    Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar
    Nature Physics 2021
    Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS 2020)
    Presented at the 24th Conference on Quantum Information Processing (QIP 2021)
    [arXiv] [Nature Physics 2021] [FOCS 2020 Video]
    See [News & Views] [IBM blogpost] for coverage of our work

  33. Quantum statistical query learning
    Srinivasan Arunachalam, Alex B. Grilo , Henry Yuen
    [arXiv]

  34. Quantum Coupon Collector
    Srinivasan Arunachalam, Alexander Belovs, Andrew Childs, Robin Kothari, Ansis Rosmansis, Ronald de Wolf
    Proceedings of Theory of Quantum computation, Communication & Cryptography (TQC 2020)
    [arXiv] [TQC 2020]

  35. Quantum Boosting
    Srinivasan Arunachalam, Reevu Maity
    Proceedings of th 37th International Conference on Machine Learning (ICML 2020)
    [arXiv] [ICML 2020]

  36. The asymptotic induced matching number of hypergraphs: Balanced types
    Srinivasan Arunachalam, Peter Vrana, Jeroen Zuiddam
    Electronic Journal of Combinatorics 27(3), 2020
    [arXiv] [EJC]

  37. Quantum hardness of learning shallow classical circuits
    Srinivasan Arunachalam, Alex B. Grilo , Aarthi Sundaram
    SIAM Journal on Computing 50(3) (2021)
    Presented at the 19th Conference on Quantum Information Processing (QIP 2020)
    [arXiv] [SICOMP] [QIP 2020 Video]

  38. Two new results about quantum exact learning
    Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Ronald de Wolf
    In Quantum 5, 587
    Proceedings of 46th International Colloquium on Automata, Languages & Programming (ICALP 2019)
    [arXiv] [Quantum] [ICALP 2019]

  39. Improved bounds on Fourier entropy and Min-entropy
    Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký , Nitin Saurabh , Ronald de Wolf
    ACM Transactions on Computation Theory (TOCT)
    Proceedings of 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020)
    [arXiv] [TOCT] [STACS 2020]

  40. Optimizing quantum optimization algorithms via faster quantum gradient computation
    András Gilyén, Srinivasan Arunachalam, Nathan Wiebe
    Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
    [arXiv] [SODA 2019]

  41. Quantum query algorithms are completely bounded forms
    Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos
    SIAM Journal on Computing 48(3), 903-925 (2019)
    Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
    Presented at the 19th Conference on Quantum Information Processing (QIP 2019)
    [arXiv] [ITCS 2018] [SICOMP] [QIP 2019 video]

  42. A survey of quantum learning theory
    Srinivasan Arunachalam, Ronald de Wolf
    Computational Complexity Column, ACM SIGACT News, Vol. 48, June 2017.
    [arXiv] [SIGACT Column]

  43. Optimal quantum sample complexity of learning algorithms
    Srinivasan Arunachalam, Ronald de Wolf
    Journal of Machine Learning Research (JMLR) 19(71), 1-36 (2018).
    Proceedings of 32nd Conference on Computational Complexity (CCC 2017)
    Presented at the 20th Conference on Quantum Information Processing (QIP 2017)
    [arXiv] [JMLR] [CCC 2017] [QIP 2017 Video]

  44. Optimizing the Number of Gates in Quantum Search
    Srinivasan Arunachalam, Ronald de Wolf
    Quantum Information & Computation, Vol. 17, 2017
    [arXiv] [Quantum Information & Computation Vol. 17]

  45. Quantum hedging in two-round prover-verifier interactions
    Srinivasan Arunachalam, Abel Molina, Vincent Russo
    Proceedings of Theory of Quantum computation, Communication and Cryptography (TQC 2017)
    [arXiv] [TQC 2017]

  46. On the robustness of bucket brigade quantum RAM
    Srinivasan Arunachalam,Vlad Gheorghiu, Tomas Jochym-O’Connor, Michele Mosca, Priyaa Varshini Srinivasan
    Presented at Asian Quantum information science (AQIS), 2015
    Proceedings of Theory of Quantum computation, Communication and Cryptography (TQC 2015)
    New Journal of Physics, Vol. 17, 2015
    [arXiv] [TQC 2015] [New Journal of Physics: Article|Video abstract]

  47. Is absolute separability determined by the partial transpose?
    Srinivasan Arunachalam, Nathaniel Johnston, Vincent Russo
    Quantum Information & Computation, Vol. 15, 2015
    [arXiv] [Quantum Information & Computation Vol. 15]

Some older projects

Hard satisfiable 3-SAT instances via auto-correlation
Srinivasan Arunachalam, Ilias Kotsireas
Journal on Satisfiability, Boolean Modeling & Computation, Vol. 10, 2016
Proceedings of SAT Competition 2014
[Journal version]

Evaluation of Riemann Zeta function on the Line Re(s) = 1 and Odd Arguments
Srinivasan Arunachalam
[arXiv]

A Substitution to Bernoulli Numbers in easier computation of ζ(2k)
Srinivasan Arunachalam
[arXiv]

Thesis

Quantum Speed-ups for Boolean Satisfiability and Derivative-Free Optimization.
Srinivasan Arunachalam
Master's thesis (2014), University of Waterloo
[PDF]

Quantum algorithms and learning theory.
Srinivasan Arunachalam
PhD thesis (2018), University of Amsterdam
[PDF]

External links: [Google Scholar] [arXiv]