Robin Kothari

Staff Research Scientist at Google Quantum AI

About me

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 am on the editorial board of the SIAM Journal on Computing (SICOMP) since January 2023.

I have served on the program committees of the following conferences:
STOC 2023
QIP 2022
FOCS 2020
QIP 2020
QIP 2019
TQC 2018
QIP 2017

Contact information

Email address: ⟨robin|robinkothari|com⟩

Follow @RobinKothari on Twitter
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.

1. Exponential quantum speedup in simulating coupled classical oscillators
   Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, and Nathan Wiebe
   [arXiv:2303.13012]
   
   
2. Query-optimal estimation of unitary channels in diamond distance
   Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang
   [arXiv:2302.14066]
   
   
3. 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).
   [arXiv:2210.06419]
   
   
4. Mean estimation when you have the source code; or, quantum Monte Carlo methods
   Robin Kothari and Ryan O'Donnell
   Presented at the Symposium on Discrete Algorithms (SODA 2023).
   Presented at the 26th Annual Conference on Quantum Information Processing (QIP 2023).
   [arXiv:2208.07544]
   
   
5. 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]
   
   
6. 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]
   
   
7. 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).
   Presented at the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022).
   [arXiv:2108.04842] [FOCS 2022]
   
   
8. 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 (2021).
   [arXiv:2102.08348] [FOCS 2021]
   
   
9. 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 24rd 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]
   
   
10. No quantum speedup over gradient descent for non-smooth convex optimization
    Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif
    Presented at the 24rd 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]
    
    
11. 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]
    
    
12. 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]
    
    
13. 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]
    
    
14. 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]
    
    
15. 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).
    [arXiv:1902.03660] [TQC 2019] [TQC 2019 Video]
    
    
16. 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]
    
    
17. Classical lower bounds from quantum upper bounds
    Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari
    Presented at the 21th 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]
    
    
18. 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).
    [arXiv:1801.03922] [FOCS 2018]
    
    
19. The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
    Mark Bun, Robin Kothari, and Justin Thaler
    Presented at the 21th 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]
    
    
20. Separating quantum communication and approximate rank
    Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee
    To be presented at the 21th 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 2016]
    
    
21. 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]
    
    
22. 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]
    
    
23. 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]
    
    
24. Quantum linear systems algorithm 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 ]
    
    
25. 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]
    
    
26. 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]
    
    
27. 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]
    
    
28. 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]
    
    
29. 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]
    
    
30. 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]
    
    
31. 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]
    
    
32. 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]
    
    
33. 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]
    
    
34. 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]
    
    
35. 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]
    
    
36. 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]
    
    
37. 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]
    
    
38. 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]
    
    
39. 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]
    
    
40. 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

• Quantum algorithms for matrix multiplication and product verification
  Robin Kothari and Ashwin Nayak
  In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pp. 1673–1677. Springer New York, 2016.
  [Springer] [Draft PDF]
  
  
  
• Efficient algorithms in quantum query complexity
  Robin Kothari
  PhD thesis (2014)
  [University of Waterloo's Institutional Repository] [PDF]
  

  In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. For the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. We then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. Finally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.

  
  
• Efficient simulation of Hamiltonians
  Robin Kothari
  Master's thesis (2010)
  [University of Waterloo's Institutional Repository] [PDF]
  

  The problem considered in this thesis is the following: We are given a Hamiltonian H and time t, and our goal is to approximately implement the unitary oper$ algorithm. We present an efficient algorithm for simulating sparse Hamiltonians. In terms of the maximum degree d and dimension N of the space on which the $ (d^2(d+log^* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, w$ N)||Ht||)^{1+o(1)}. In terms of the parameter t, these algorithms are essentially optimal due to a no--fast-forwarding theorem. In the second part of this t$ and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, and rule out generic simulations $ not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking ti$ simulations based on discrete-time quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured $