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. Our algorithm is based on an 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 consider a model of quantum walk in which many walkers move and interact on a graph. Building on a previous single-walker universality result, we show that multi-particle quantum walk can also perform universal quantum computation, but with a graph of only polynomial size.
We establish a precise connection between the two main models of quantum walk, one operating in continuous time and the other in discrete time. Using this connection, it develops a radically new way of simulating quantum dynamics, showing for the first time that Hamiltonian evolution for time t can be simulated in a number of computational steps that is strictly linear in t.
We develop an approach to universal quantum computing based on scattering theory and thereby establish the universality of quantum walk on a sparse, unweighted graph.
We dramatically generalize the algorithm of Farhi, Goldstone, and Gutmann for evaluating balanced binary AND-OR trees, giving a nearly-optimal algorithm for evaluating any read-once Boolean formula.
We develop a new approach to quantum algorithms for the non-abelian hidden subgroup problem based on optimal measurements for distinguishing quantum states. This approach gives the first efficient quantum algorithm for the HSP in certain non-abelian groups, such as the Heisenberg group.
We show that a quantum walk can find a marked vertex of a d-dimensional grid quadratically faster than any classical method, provided d > 4 (or with logarithmic overhead in d = 4). This work anticipated a quantum walk-based framework for search on graphs, a major tool for quantum query algorithms.
We construct an example of a black-box problem that can be solved in polynomial time using a quantum walk, but that requires exponentially many queries to solve using a classical computer. This is a rare example of exponential quantum speedup that is not based on the Fourier transform. We also develop general tools for Hamiltonian simulation.