Robin Kothari's homepage

About me

M.Math in Computer Science at the University of Waterloo.
B.Tech in Engineering Physics at the Indian Institute of Technology Bombay.
Research Interests: Quantum algorithms, quantum complexity theory. I'm also interested in classical complexity theory, algorithmic graph theory and computational geometry.
Location: Institute for Quantum Computing, Waterloo.

Contact information

Institute for Quantum Computing
University of Waterloo
200 University Ave. West
Waterloo, Ontario, Canada
N2L 3G1
rkothari⟨at|iqc|dot⟩ca

Papers/Preprints

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

[arXiv:1112.5855]

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.

The quantum query complexity of read-many formulas

[arXiv:1112.0548]

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.

Quantum query complexity of minor-closed graph properties

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

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.

Simulating sparse Hamiltonians with star decompositions

Theory of Quantum Computation, Communication, and Cryptography (TQC 2010)

6519

[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.

Limitations on the simulation of non-sparse Hamiltonians

Quantum Information and Computation

[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.

Dissipation in circuit quantum electrodynamics: lasing and cooling of a low-frequency oscillator

New Journal of Physics

[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'.

Master's thesis

Efficient simulation of Hamiltonians

[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 operator e^{-iHt} with an efficient quantum 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 Hamiltonian 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)}. In terms of the parameter t, these algorithms are essentially optimal due to a no--fast-forwarding theorem. In the second part of this thesis, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, and rule 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 walks cannot be dramatically improved in general. We also show some positive results about simulating structured Hamiltonians efficiently.