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 Wiskune & 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.
Quantum algorithms, Quantum learning theory, Quantum complexity theory, Analysis of Boolean functions.
Email: srinivasan (dot) arunachalam (at) ibm (dot) com
Editor: Quantum PC member: QCTIP 2020, TQC 2021, STOC 2023, QIP 2024, TQC 2024, ITCS 2025, QIP 2025
Learning stabilizer structure of quantum states Srinivasan Arunachalam, Arkopal Dutt [arXiv]
Efficiently learning depth-3 circuits via quantum agnostic boosting Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael Oliveira [arXiv]
Algorithmizing polynomial Freiman-Ruzsa Theorems Srinivasan Arunachalam, Davi Castro Silva, Arkopal Dutt, Tom Gur [arXiv]
Distributed 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]
Testing and learning structured 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]
Polynomial-time tolerant testing stabilizer states Srinivasan Arunachalam, Arkopal Dutt Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025) [arXiv]
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]
Quantum computing for high-energy physics White paper with IBM, CERN and DESY Physical Review X [arXiv]
A survey on the complexity of learning quantum states Srinivasan Arunachalam, Anurag Anshu Nature Reviews Physics [arXiv]
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]
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]
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]
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]
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]
On the Gaussian surface area of spectrahedra Srinivasan Arunachalam, Oded Regev, Penghui Yao GAFA Seminar Notes [arXiv]
Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case Srinivasan Arunachalam, João F Doriguello ACM Transactions on Computation Theory [arXiv]
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]
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]
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]
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
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]
Communication memento: Memoryless communication complexity Srinivasan Arunachalam, Supartha Podder Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) [arXiv]
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
Quantum statistical query learning Srinivasan Arunachalam, Alex B. Grilo , Henry Yuen [arXiv]
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]
Quantum Boosting Srinivasan Arunachalam, Reevu Maity Proceedings of th 37th International Conference on Machine Learning (ICML 2020) [arXiv] [ICML 2020]
The asymptotic induced matching number of hypergraphs: Balanced types Srinivasan Arunachalam, Peter Vrana, Jeroen Zuiddam Electronic Journal of Combinatorics 27(3), 2020 [arXiv] [EJC]
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]
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]
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]
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]
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]
A survey of quantum learning theory Srinivasan Arunachalam, Ronald de Wolf Computational Complexity Column, ACM SIGACT News, Vol. 48, June 2017. [arXiv] [SIGACT Column]
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]
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]
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]
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]
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]
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 [SAT competition] [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]
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]