Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma

arXiv:1312.1414; Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), pp. 283–292 (2014)

Presented at QIP 2014 as a contributed talk (speaker: Robin Kothari)

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.

Andrew M. Childs, David Gosset, and Zak Webb

arXiv:1205.3782; Science

Presented at QIP 2013 as a contributed talk (speaker: David Gosset)

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.

Andrew M. Childs

arXiv:0810.0312; Communications in Mathematical Physics

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

Andrew M. Childs

arXiv:0806.1972; Physical Review Letters

Presented at QIP 2009 as an invited talk

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.

Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang

quant-ph/0703015; Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pp. 363–372 (2007); SIAM Journal on Computing

Presented at QIP 2008 as an invited talk (speaker: Andris Ambainis)

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.

Dave Bacon, Andrew M. Childs, and Wim van Dam

quant-ph/0504083; Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pp. 469–478 (2005)

Presented at QIP 2006 as a contributed talk (speaker: Wim van Dam)

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.

Andrew M. Childs and Jeffrey Goldstone

quant-ph/0306054; Physical Review A

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.

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman

quant-ph/0209131; Proceedings of the 35th ACM Symposium on Theory of Computing, pp. 59–68 (2003)

Presented at QIP 2003 as an invited talk (speaker: Edward Farhi)

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.