About me

my picture

I am interested in (quantum) algorithms and complexity theory.

Past: M.Math and Ph.D. at the David R. Cheriton School of Computer Science and Institute for Quantum Computing at the University of Waterloo.
B.Tech at the Indian Institute of Technology Bombay.

Present: Postdoctoral associate at the Center for Theoretical Physics at MIT.

Future? I'm looking for a permanent position starting around Fall 2017.

Contact information

Center for Theoretical Physics
Massachusetts Institute of Technology
77 Massachusetts Ave, 6-406
Cambridge, MA 02139
USA
⟨rkothari|mit|edu⟩

Publications / preprints

show/hide all abstracts
  1. Randomized query complexity of sabotaged and composed functions
    Shalev Ben-David and Robin Kothari
    To be presented at the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016).
    [arXiv:1605.09071] [ECCC TR16-087]
    We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f o h o g) = Omega(R(f) R(h) R(g)).
    We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f o g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f o g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity.
    Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem for zero-error randomized protocols implies a general lifting theorem for bounded-error protocols.

  2. 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
    To be presented at the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
    [arXiv:1605.01142] [ECCC TR16-072]
    While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We also present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to Göös, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.

  3. 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]
    We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and the author. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from lifting the query separation to communication complexity.

  4. 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)
    [arXiv:1511.02306]
    Harrow, Hassidim, and Lloyd showed that for a suitably specified N x N matrix A and N-dimensional vector b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax=b. If A is sparse and well-conditioned, their algorithm runs in time poly(log N, 1/epsilon), where epsilon is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/epsilon), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on epsilon is prohibitive.

  5. 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 contributed 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]
    We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al., to be shown in a unified manner.

  6. 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]
    The subcube partition model of computation is at least as powerful as decision trees but no separation between these models was known. We show that there exists a function whose deterministic subcube partition complexity is asymptotically smaller than its randomized decision tree complexity, resolving an open problem of Friedgut, Kahn, and Wigderson (2002). Our lower bound is based on the information-theoretic techniques first introduced to lower bound the randomized decision tree complexity of the recursive majority function.
    We also show that the public-coin partition bound, the best known lower bound method for randomized decision tree complexity subsuming other general techniques such as block sensitivity, approximate degree, randomized certificate complexity, and the classical adversary bound, also lower bounds randomized subcube partition complexity. This shows that all these lower bound techniques cannot prove optimal lower bounds for randomized decision tree complexity, which answers an open question of Jain and Klauck (2010) and Jain, Lee, and Vishnoi (2014).

  7. 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]
    We present an algorithm for sparse Hamiltonian simulation that has optimal dependence on all parameters of interest (up to log factors). Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity $d$ at the expense of poor scaling in the allowed error $\epsilon$. In contrast, an approach based on fractional-query simulation provides optimal scaling in $\epsilon$ at the expense of poor scaling in $d$. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm achieves near-linear scaling in $\tau := d \|H\|_{\max} t$ and sublogarithmic scaling in $1/\epsilon$. Our dependence on $\epsilon$ is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on $\tau$.

  8. 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]
    We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal. However, we simplify the algorithm and its analysis by using a method for implementing linear combinations of unitary operations to directly apply the truncated Taylor series.

  9. 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).
    [arXiv:1312.1414] [STOC 2014]
    We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ can be simulated for time $t$ with precision $\epsilon$ using $O(\tau \frac{\log(\tau/\epsilon)}{\log\log(\tau/\epsilon)})$ queries and $O(\tau \frac{\log^2(\tau/\epsilon)}{\log\log(\tau/\epsilon)})$ additional 2-qubit gates, where $\tau = d^2 \|{H}\|_{\max} t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

  10. 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]
    In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al.
    The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered γ2-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.

  11. 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]
    Quantum formulas, defined by Yao [FOCS '93], are the quantum analogs of classical formulas, i.e., classical circuits in which all gates have fanout one. We show that any read-once quantum formula over a gate set that contains all single-qubit gates is equivalent to a read-once classical formula of the same size and depth over an analogous classical gate set. For example, any read-once quantum formula over Toffoli and single-qubit gates is equivalent to a read-once classical formula over Toffoli and NOT gates. We then show that the equivalence does not hold if the read-once restriction is removed. To show the power of quantum formulas without the read-once restriction, we define a new model of computation called the one-qubit model and show that it can compute all boolean functions. This model may also be of independent interest.

  12. 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]
    We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.

  13. 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]
    We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}).

  14. 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]
    We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the O(n^{35/27}) and O(n^{9/7}) learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.

  15. 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).
    [arXiv:1112.5855] [ICALP 2012]
    The quantum query complexity of Boolean matrix multiplication is typically studied as a function of the matrix dimension, n, as well as the number of 1s in the output, ℓ. We prove an upper bound of O~(n sqrt{ℓ}) for all values of ℓ. This is an improvement over previous algorithms for all values of ℓ. On the other hand, we show that for any ε < 1 and any ℓ ≤ εn^2, there is an Omega(n sqrt{ℓ}) lower bound for this problem, showing that our algorithm is essentially tight. We first reduce Boolean matrix multiplication to several instances of graph collision. We then provide an algorithm that takes advantage of the fact that the underlying graph in all of our instances is very dense to find all graph collisions efficiently.

  16. 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]
    The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega~(n^{5/9}) queries. Applications of these results include a Omega~(n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates.

  17. 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]
    We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether a graph is planar, is a forest, or does not contain a path of a given length. We 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}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n^{3/2}) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.

  18. 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]
    We present an efficient algorithm for simulating the time evolution due to a sparse Hamiltonian. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian H acts, this algorithm uses (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, which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero entries have the property that every connected component is a star, and efficiently simulate each of these pieces.

  19. 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]
    The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N x N Hamiltonian H for time t can be simulated using O(||Ht||poly(log N)) operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is 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 time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.

  20. 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]
    Superconducting qubits coupled to electric or nanomechanical resonators display effects previously studied in quantum electrodynamics (QED) as well as extensions thereof. Here, we consider a driven qubit coupled to a low-frequency oscillator and study the influence of dissipation. When the qubit is driven to perform Rabi oscillations, with Rabi frequency in resonance with the oscillator, the latter can be driven far from equilibrium. Blue detuned driving leads to a population inversion in the qubit and lasing behavior of the oscillator ('single-atom laser'). For red detuning, the qubit cools the oscillator. This behavior persists at the symmetry point where the qubit–oscillator coupling is quadratic and decoherence effects are minimized. Here, the system realizes a 'single-atom-two-photon laser'.

Theses / surveys

show/hide all abstracts