About me
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.
Service: I'm on the program committee of QIP 2017.


Contact information
Center for Theoretical Physics
Massachusetts Institute of Technology
77 Massachusetts Ave, 6406
Cambridge, MA 02139
USA
⟨rkotharimitedu⟩
Publications / preprints
show/hide all abstracts
Separating quantum communication and approximate rank
Anurag Anshu, Shalev BenDavid, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee
[arXiv:1611.05754]
One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate gamma_2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unboundedround model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank.
In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H=F_G. Our main technical result is a lower bound on the quantum communication complexity of F_G in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of F_G by relating it to the Boolean circuit size of the starting function F. 
Randomized query complexity of sabotaged and composed functions
Shalev BenDavid and Robin Kothari
Presented at the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016).
[arXiv:1605.09071] [ECCC TR16087]
We study the composition question for boundederror 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 zeroerror randomized protocols implies a general lifting theorem for boundederror protocols. 
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev BenDavid, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Presented at the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
[arXiv:1605.01142] [ECCC TR16072] [FOCS 2016]
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 superquadratic 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, BenDavid, 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.

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 TR15195] [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 onesided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, BenDavid, 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.

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 Ndimensional 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 wellconditioned, 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.

Separations in query complexity using cheat sheets
Scott Aaronson, Shalev BenDavid, and Robin Kothari
Presented at the 19th Conference on Quantum Information Processing (QIP 2016) as a plenary talk (speaker: Shalev BenDavid)
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pp. 863–876 (2016).
[arXiv:1511.01937] [ECCC TR15175] [STOC 2016]
We show a power 2.5 separation between boundederror 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.

Separating decision tree complexity from subcube partition complexity
Robin Kothari, David RacicotDesloges, 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 informationtheoretic techniques first introduced to lower bound the randomized decision tree complexity of the recursive majority function.
We also show that the publiccoin 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). 
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 nearoptimal 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 fractionalquery 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 nearlinear 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$.

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.

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 2qubit 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 timevarying 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 fractionalquery 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.

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 Nbit 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 inputdependent 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. 
Dequantizing Readonce 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 readonce quantum formula over a gate set that contains all singlequbit gates is equivalent to a readonce classical formula of the same size and depth over an analogous classical gate set. For example, any readonce quantum formula over Toffoli and singlequbit gates is equivalent to a readonce classical formula over Toffoli and NOT gates. We then show that the equivalence does not hold if the readonce restriction is removed. To show the power of quantum formulas without the readonce restriction, we define a new model of computation called the onequbit model and show that it can compute all boolean functions. This model may also be of independent interest.

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 nbit 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 onequery 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.

A TimeEfficient Quantum Walk for 3Distinctness 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 3Distinctness 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}).

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 ACMSIAM 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.
 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]
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 readmany 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 readonce formula with n blackbox input bits is Theta(sqrt(n)). However, the corresponding problem for readmany formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal readonce 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 linearsize 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 constantdepth 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^{2epsilon}) gates.
 Quantum query complexity of minorclosed 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: AbstractSlidesVideo] [SIAM Journal on Computing]
We study the quantum query complexity of minorclosed 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 minorclosed propertiesthose that cannot be characterized by a finite set of forbidden subgraphshave quantum query complexity \Theta(n^{3/2}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minorclosed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minorclosed 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 subgraphfinding problems.
 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 nonzero entries have the property that every connected component is a star, and efficiently simulate each of these pieces.
 Limitations on the simulation of nonsparse 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(Htpoly(log N)) operations, which is essentially optimal due to a nofastforwarding theorem. Here, we consider nonsparse Hamiltonians and show significant limitations on their simulation. We generalize the nofastforwarding 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 discretetime quantum walk cannot be dramatically improved in general. On the positive side, we show that some nonsparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.
 Dissipation in circuit quantum electrodynamics: lasing and cooling of a lowfrequency 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 lowfrequency 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 ('singleatom 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 'singleatomtwophoton laser'.
Theses / surveys
show/hide all abstracts Quantum algorithms for matrix multiplication and product verification
Robin Kothari and Ashwin Nayak
In MingYang 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 graphproperty 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 Nbit 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_2norm 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 outputsensitive 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 minorclosed graph properties and show that most minorclosed propertiesthose that cannot be characterized by a finite set of forbidden subgraphshave 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 minorclosed 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 subgraphfinding 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 nofastforwarding theorem. In the second part of this t$ and show significant limitations on their simulation. We generalize the nofastforwarding 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 discretetime quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured $