Srinivasan Arunachalam

my picture

I am a Research Staff Member 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.

Research interests

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

Contact information

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


  1. A rigorous and robust quantum speed-up in supervised machine learning
    Yunchao Liu Srinivasan Arunachalam, Kristan Temme

  2. Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
    Srinivasan Arunachalam, Vojtech Havlicek , Giacomo Nannicini , Kristan Temme, Pawel Wocjan

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

  4. Sample efficient learning of quantum many-body systems
    Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar
    Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS 2020)
    [arXiv] [FOCS 2020 Video]

  5. Quantum statistical query learning
    Srinivasan Arunachalam, Alex B. Grilo , Henry Yuen

  6. 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]

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

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

  9. Quantum hardness of learning shallow classical circuits
    Srinivasan Arunachalam, Alex B. Grilo , Aarthi Sundaram
    Presented at the 19th Conference on Quantum Information Processing (QIP 2020)
    [arXiv] [QIP 2020 Video]

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

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

  12. 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]

  13. 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]

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

  15. 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]

  16. 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]

  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]

  18. 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]

  19. 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]

  20. 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
    [SAT competition] [Journal version]

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

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


    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]