Staff Research Scientist at Google Quantum AI

About me

my picture

I am a theoretical computer scientist and my primary area of research is quantum algorithms and complexity theory.

Area of research
I have worked extensively on quantum algorithms for simulating the dynamics of physical systems, perhaps the most promising application of quantum computers. I have also worked on quantum algorithms for linear algebraic, graph theoretic, combinatorial, and machine learning problems. I also work on algorithms and lower bounds in (quantum and classical) query complexity, and related areas like communication complexity and circuit complexity.

Past positions and education
I was a Principal Researcher at Microsoft Quantum in Redmond, WA. I was a postdoctoral associate at the Center for Theoretical Physics at MIT. I received an M.Math and Ph.D. at the David R. Cheriton School of Computer Science and Institute for Quantum Computing at the University of Waterloo. I received a B.Tech at the Indian Institute of Technology Bombay.

Service

I have served on the following committees and editorial boards:

I have served on the program committees of the following conferences:

Former interns

Contact information

Email address: ⟨robin|robinkothari|com⟩


Follow @RobinKothari on bluesky
ArXiv profile
Google Scholar profile

Talks

A YouTube playlist of some talks I've given.

Publications / preprints


All my publications are available on the arXiv. Authors are listed in alphabetical order for most of the papers below, which is standard in mathematics and theoretical computer science. Papers marked with © use contribution order, which is standard in physics and applied areas of computer science. Papers marked with ® list authors in reverse alphabetical order.

  1. Exponential quantum speedup for 𝔽3n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
    Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, and Kewen Wu
    [arXiv:2609.40321]

  2. Quantum circuit compilation with constant overhead
    ® Chenyi Zhang, Xinyu Tan, Robin Kothari, David Gosset, and Craig Gidney
    [arXiv:2609.39092]

  3. An Optimal Quantum Linear Systems Algorithm
    Carlos Bravo-Prieto, Aram W. Harrow, and Robin Kothari
    [arXiv:2609.35660]

  4. Randomized query complexity can beat certificate complexity
    Shalev Ben-David and Robin Kothari
    [arXiv:2609.15063]

  5. Rational degree is polynomially related to degree
    Robin Kothari, Matt Kovacs-Deak, Daochen Wang, and Rain Zimin Yang
    To be presented at the 67th Annual Symposium on Foundations of Computer Science (FOCS 2026).
    [arXiv:2601.08727]

  6. A simplified version of the quantum OTOC(2) problem
    © Robbie King, Robin Kothari, Ryan Babbush, Sergio Boixo, Kostyantyn Kechedzhi, Thomas E. O'Brien, and Vadim Smelyanskiy
    [arXiv:2510.19751]

  7. No exponential quantum speedup for SIS∞ anymore
    Robin Kothari, Ryan O'Donnell, and Kewen Wu
    Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), pp. 101–105 (2026).
    [arXiv:2510.07515] [STOC 2026]

  8. Multi-qubit Toffoli with exponentially fewer T gates
    David Gosset, Robin Kothari, and Chenyi Zhang
    Presented at the 29th Annual Conference on Quantum Information Processing (QIP 2026) as a long plenary talk.
    [arXiv:2510.07223]

  9. On the Rational Degree of Boolean Functions and Applications
    Vishnu Iyer, Siddhartha Jain, Robin Kothari, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, and Michael Whitmeyer
    [arXiv:2310.08004]

  10. Uniformity testing when you have the source code
    Clément L. Canonne, Robin Kothari, and Ryan O'Donnell
    20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025), Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 7:1–7:20 (2025).
    [arXiv:2411.04972] [TQC 2025]

  11. Quantum state preparation with optimal T-count
    David Gosset, Robin Kothari, and Kewen Wu
    Presented at the 28th Annual Conference on Quantum Information Processing (QIP 2025).
    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pp. 3378–3406 (2026).
    Quantum 10, 2168 (2026).
    [arXiv:2411.04790] [SODA 2026] [Quantum]

  12. Shadow Hamiltonian Simulation
    © Rolando D. Somma, Robbie King, Robin Kothari, Thomas O'Brien, and Ryan Babbush
    Nature Communications 16, 2690 (2025).
    [arXiv:2407.21775] [Nature Communications]

  13. Quartic quantum speedups for planted inference
    © Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, and Ryan Babbush
    Presented at the 28th Annual Conference on Quantum Information Processing (QIP 2025).
    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pp. 905 – 913.
    Physical Review X 15, 021077 (2025).
    [arXiv:2406.19378] [SODA 2025] [Physical Review X]

  14. Triply efficient shadow tomography
    © Robbie King, David Gosset, Robin Kothari, and Ryan Babbush
    Presented at the 28th Annual Conference on Quantum Information Processing (QIP 2025).
    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pp. 914 – 946.
    PRX Quantum 6, 010336 (2025).
    [arXiv:2404.19211] [SODA 2025] [PRX Quantum]

  15. Exponential quantum speedup in simulating coupled classical oscillators
    Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, and Nathan Wiebe
    Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024) as a short plenary talk.
    Proceedings of the 64th Symposium on Foundations of Computer Science (FOCS 2023), pp. 405 – 414 (2023).
    Physical Review X 13 041041 (2023).
    [arXiv:2303.13012] [FOCS 2023] [Physical Review X]

  16. Query-optimal estimation of unitary channels in diamond distance
    Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang
    Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024).
    Proceedings of the 64th Symposium on Foundations of Computer Science (FOCS 2023), pp. 363 – 390 (2023).
    [arXiv:2302.14066] [FOCS 2023]

  17. Quantum divide and conquer
    Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang
    Presented at the 26th Annual Conference on Quantum Information Processing (QIP 2023).
    ACM Transactions on Quantum Computing 6(2), pp. 17:1 – 17:26 (June 2025).
    [arXiv:2210.06419] [ACM ToQC]

  18. Mean estimation when you have the source code; or, quantum Monte Carlo methods
    Robin Kothari and Ryan O'Donnell
    Presented at the 26th Annual Conference on Quantum Information Processing (QIP 2023).
    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pp. 1186 – 1215 (2023).
    [arXiv:2208.07544] [SODA 2023] [QIP 2023 Video]

  19. Quantum Algorithms for Reinforcement Learning with a Generative Model
    © Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, and Martin Roetteler
    Proceedings of the 38th International Conference on Machine Learning (ICML 2021), PMLR 139:10916-10926, 2021.
    [arXiv:2112.08451] [ICML 2021]

  20. Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
    Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif
    Presented at the 25th Annual Conference on Quantum Information Processing (QIP 2022).
    Presented as a spotlight talk at the thirty-fifth Conference on Neural Information Processing Systems (NeurIPS 2021).
    Advances in Neural Information Processing Systems 34, pp. 29874 – 29884 (2021).
    [arXiv:2112.01118] [NeurIPS 2021]

  21. Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
    Jeongwan Haah, Robin Kothari, and Ewin Tang
    Presented at the 25th Annual Conference on Quantum Information Processing (QIP 2022).
    Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), pp. 135 – 146 (2022).
    Journal version published as Learning quantum Hamiltonians from high-temperature Gibbs states and real-time evolutions.
    Nature Physics 20, 1027–1031 (2024).
    [arXiv:2108.04842] [FOCS 2022] [Nature Physics]

  22. Unambiguous DNFs and Alon-Saks-Seymour
    Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari
    Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), pp. 116 – 124 (2022).
    SIAM Journal on Computing, pp. FOCS21-157–FOCS21-173 (2023).
    [arXiv:2102.08348] [FOCS 2021] [SIAM Journal on Computing]

  23. Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
    Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal
    Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021) as a short plenary talk.
    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pp. 1330 – 1342 (2021).
    [arXiv:2010.12629] [STOC 2021]

    This work subsumes the following older preprint by a subset of the authors:
    Quantum Implications of Huang's Sensitivity Theorem
    Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal
    [arXiv:2004.13231]

  24. No quantum speedup over gradient descent for non-smooth convex optimization
    Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif
    Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021).
    12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Leibniz International Proceedings in Informatics (LIPIcs) 185, pp. 53:1 – 53:20 (2021).
    [arXiv:2010.01801] [ITCS 2021]

  25. When Is Amplification Necessary for Composition in Randomized Query Complexity?
    Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson
    Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), Leibniz International Proceedings in Informatics (LIPIcs) 176, pp. 28:1 – 28:16 (2020).
    [arXiv:2006.10957] [RANDOM 2020]

  26. Quantum Coupon Collector
    Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf
    15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 158, pp. 10:1 – 10:17 (2020).
    [arXiv:2002.07688] [TQC 2020]

  27. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
    Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler
    Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020).
    35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 169, pp. 7:1 – 7:47 (2020).
    [arXiv:1904.08914] [QIP 2020 Video] [CCC 2020]

  28. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
    Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal
    Presented at the 22nd Annual Conference on Quantum Information Processing (QIP 2019).
    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), pp. 515–526 (2019).
    [arXiv:1906.08890] [STOC 2019]

  29. Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
    Shalev Ben-David and Robin Kothari
    14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Leibniz International Proceedings in Informatics (LIPIcs) 135, pp. 2:1–2:23 (2019).
    [arXiv:1902.03660] [TQC 2019] [TQC 2019 Video]

  30. Quantum algorithms and approximating polynomials for composed functions with shared inputs
    Mark Bun, Robin Kothari, and Justin Thaler
    Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 662–678 (2019).
    Quantum 5, 543 (2021).
    [arXiv:1809.02254] [SODA 2019] [Quantum]

  31. Classical lower bounds from quantum upper bounds
    Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari
    Presented at the 21st Annual Conference on Quantum Information Processing (QIP 2018).
    Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS 2018), pp. 339–349 (2018).
    [arXiv:1807.06256] [FOCS 2018]

  32. Quantum algorithm for simulating real time evolution of lattice Hamiltonians
    Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low
    Presented at the 22nd Annual Conference on Quantum Information Processing (QIP 2019) as a plenary talk (speaker: Jeongwan Haah).
    Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS 2018), pp. 350–360 (2018).
    SIAM Journal on Computing, 52(6), pp. FOCS18-250 – FOCS18-284 (2023).
    [arXiv:1801.03922] [FOCS 2018] [SIAM Journal on Computing]

  33. The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
    Mark Bun, Robin Kothari, and Justin Thaler
    Presented at the 21st Annual Conference on Quantum Information Processing (QIP 2018) as a plenary talk (speaker: Robin Kothari).
    Proceedings of the 50th ACM Symposium on Theory of Computing (STOC 2018), pp. 297–310 (2018).
    Theory of Computing , Volume 16(10), pp. 1-71, 2020.
    [arXiv:1710.09079] [ECCC TR17-169] [STOC 2018] [Theory of Computing] [QIP 2018 Video]

  34. Separating quantum communication and approximate rank
    Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee
    Presented at the 21st Annual Conference on Quantum Information Processing (QIP 2018).
    32nd Conference on Computational Complexity (CCC 2017), Leibniz International Proceedings in Informatics (LIPIcs) 79, pp. 24:1–24:33 (2017).
    [arXiv:1611.05754] [CCC 2017]

  35. Randomized query complexity of sabotaged and composed functions
    Shalev Ben-David and Robin Kothari
    43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs) 55, 60:1–60:14 (2016).
    Theory of Computing, Volume 14(5), pp. 1-27, 2018.
    [arXiv:1605.09071] [ECCC TR16-087] [ICALP 2016] [Theory of Computing]

  36. Separations in communication complexity using cheat sheets and information complexity
    Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
    Presented at the 20th Conference on Quantum Information Processing (QIP 2017).
    Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 555–564 (2016).
    [arXiv:1605.01142] [ECCC TR16-072] [FOCS 2016]

  37. Nearly optimal separations between communication (or query) complexity and partitions
    Andris Ambainis, Martins Kokainis, and Robin Kothari
    31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (LIPIcs) 50, pp. 4:1–4:14 (2016).
    [arXiv:1512.01210]+[arXiv:1512.00661] [ECCC TR15-195] [CCC 2016]

  38. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
    Andrew M. Childs, Robin Kothari, and Rolando D. Somma
    Presented at the 19th Conference on Quantum Information Processing (QIP 2016) as a contributed talk (speaker: Robin Kothari)
    SIAM Journal on Computing, 46(6), 1920–1950 (2017).
    [arXiv:1511.02306] [SIAM Journal on Computing] [Video from a talk at QuICS] [QIP 2016 Video: Part 1 Part 2 ]

  39. Separations in query complexity using cheat sheets
    Scott Aaronson, Shalev Ben-David, and Robin Kothari
    Presented at the 19th Conference on Quantum Information Processing (QIP 2016) as a plenary talk (speaker: Shalev Ben-David)
    Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pp. 863–876 (2016).
    [arXiv:1511.01937] [ECCC TR15-175] [STOC 2016]

  40. Separating decision tree complexity from subcube partition complexity
    Robin Kothari, David Racicot-Desloges, and Miklos Santha
    Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs) 40, pp. 915–930 (2015).
    [arXiv:1504.01339] [RANDOM 2015]

  41. Hamiltonian simulation with nearly optimal dependence on all parameters
    Dominic W. Berry, Andrew M. Childs, and Robin Kothari
    Presented at the 18th Conference on Quantum Information Processing (QIP 2015) as a contributed talk (speaker: Dominic Berry)
    Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pp. 792–809 (2015).
    [arXiv:1501.01715] [FOCS 2015]

  42. Simulating Hamiltonian dynamics with a truncated Taylor series
    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
    Physical Review Letters 114, 090502 (2015)
    [arXiv:1412.4687] [PRL]

  43. Exponential improvement in precision for simulating sparse Hamiltonians
    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
    Presented at the 17th Workshop on Quantum Information Processing (QIP 2014) as a contributed talk (speaker: Robin Kothari)
    Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pp. 283–292 (2014).
    Forum of Mathematics, Sigma 5, e8 (2017).
    [arXiv:1312.1414] [STOC 2014] [Forum of Mathematics, Sigma]

  44. An optimal quantum algorithm for the oracle identification problem
    Robin Kothari
    Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), Leibniz International Proceedings in Informatics 25, pp. 482–493 (2014).
    [arXiv:1311.7685] [STACS 2014]

  45. Dequantizing Read-once Quantum Formulas
    Alessandro Cosentino, Robin Kothari, and Adam Paetznick
    8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics (LIPIcs) 22, pp. 80–92 (2013).
    [arXiv:1304.5164] [TQC 2013]

  46. Easy and hard functions for the Boolean hidden shift problem
    Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler
    8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics (LIPIcs) 22, pp. 50–79 (2013).
    [arXiv:1304.4642] [TQC 2013]

  47. A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
    Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
    [arXiv:1302.7316]
    Merged with arXiv:1302.3143 by Aleksandrs Belovs for ICALP 2013.
    Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013), Lecture Notes in Computer Science 7965, pp. 105–122 (2013).
    [ICALP 2013]

  48. Nested quantum walks with quantum data structures
    Stacey Jeffery, Robin Kothari, and Frédéric Magniez
    Presented at the 17th Workshop on Quantum Information Processing (QIP 2014) as a contributed talk, combined with the above paper (arXiv:1302.7316). (speaker: Stacey Jeffery)
    Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1474–1485 (2013).
    [arXiv:1210.1199] [SODA 2013]

  49. Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
    Stacey Jeffery, Robin Kothari, and Frédéric Magniez
    Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Lecture Notes in Computer Science 7391, pp. 522–532 (2012).
    Algorithmica, 76:1, pp. 1–16 (2016).
    [arXiv:1112.5855] [ICALP 2012] [Algorithmica]

  50. The quantum query complexity of read-many formulas
    Andrew M. Childs, Shelby Kimmel, and Robin Kothari
    Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012), Lecture Notes in Computer Science 7501, pp. 337–348 (2012).
    [arXiv:1112.0548] [ESA 2012]

  51. Quantum query complexity of minor-closed graph properties
    Andrew M. Childs and Robin Kothari
    Presented at the 14th Workshop on Quantum Information Processing (QIP 2011) as a contributed talk (speaker: Robin Kothari)
    Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics 9, pp. 661–672 (2011).
    SIAM Journal on Computing, 41(6), 1426–1450 (2012).
    [arXiv:1011.1443] [STACS 2011] [QIP 2011: Abstract|Slides|Video] [SIAM Journal on Computing]

  52. Simulating sparse Hamiltonians with star decompositions
    Andrew M. Childs and Robin Kothari
    Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), Lecture Notes in Computer Science 6519, pp. 94–103 (2011).
    [arXiv:1003.3683] [TQC 2010]

  53. Limitations on the simulation of non-sparse Hamiltonians
    Andrew M. Childs and Robin Kothari
    Quantum Information and Computation 10, 669–684 (2010).
    [arXiv:0908.4398] [Quantum Information and Computation]

  54. Dissipation in circuit quantum electrodynamics: lasing and cooling of a low-frequency oscillator
    © Julian Hauss, Arkady Fedorov, Stephan André, Valentina Brosco, Carsten Hutter, Robin Kothari, Sunil Yeshwanth, Alexander Shnirman, and Gerd Schön
    New Journal of Physics 10 095018 (2008).
    [arXiv:0806.1298] [New Journal of Physics]

Theses / surveys