Selected papers by Andrew Childs

Exponential improvement in precision for simulating sparse Hamiltonians
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.
Universal computation by multi-particle quantum walk
Andrew M. Childs, David Gosset, and Zak Webb
arXiv:1205.3782; Science 339, 791–794 (2013)
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.
On the relationship between continuous- and discrete-time quantum walk
Andrew M. Childs
arXiv:0810.0312; Communications in Mathematical Physics 294, 581–603 (2010)
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.
Universal computation by quantum walk
Andrew M. Childs
arXiv:0806.1972; Physical Review Letters 102, 180501 (2009)
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.
Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer
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 39, 2513–2530 (2010)
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.
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
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.
Spatial search by quantum walk
Andrew M. Childs and Jeffrey Goldstone
quant-ph/0306054; Physical Review A 70, 022314 (2004)
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.
Exponential algorithmic speedup by quantum walk
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.