
Quantum algorithm for multivariate polynomial interpolation
Jianxin Chen, Andrew M. Childs, and ShihHan Hung

Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
Andrew M. Childs, Robin Kothari, and Rolando D. Somma

Quantum algorithm for linear differential equations with exponentially improved dependence on precision
Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang

Efficient simulation of sparse Markovian quantum dynamics
Andrew M. Childs and Tongyang Li

Optimal quantum algorithm for polynomial interpolation
Andrew M. Childs, Wim van Dam, ShihHan Hung, and Igor E. Shparlinski

Optimal state discrimination and unstructured search in nonlinear quantum mechanics
Andrew M. Childs and Joshua Young

Complexity of the XY antiferromagnet at fixed magnetization
Andrew M. Childs, David Gosset, and Zak Webb

Hamiltonian simulation with nearly optimal dependence on all parameters
Dominic W. Berry, Andrew M. Childs, and Robin Kothari

Simulating Hamiltonian dynamics with a truncated Taylor series
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma

Momentum switches
Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, and Zak Webb

Quantum computation of discrete logarithms in semigroups
Andrew M. Childs and Gábor Ivanyos

Spatial search by continuoustime quantum walks on crystal lattices
Andrew M. Childs and Yimin Ge

The BoseHubbard model is QMAcomplete
Andrew M. Childs, David Gosset, and Zak Webb

Exponential improvement in precision for simulating sparse Hamiltonians
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma

The computational power of matchgates and the XY interaction on arbitrary graphs
Daniel J. Brod and Andrew M. Childs

Interpolatability distinguishes LOCC from separable von Neumann measurements
Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols

Constructing elliptic curve isogenies in quantum subexponential time
Andrew M. Childs, David Jao, and Vladimir Soukharev

Product formulas for exponentials of commutators
Andrew M. Childs and Nathan Wiebe

A timeefficient quantum walk for 3distinctness using nested updates
Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez

Easy and hard functions for the Boolean hidden shift problem
Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler

A framework for bounding nonlocality of state discrimination
Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols

Universal computation by multiparticle quantum walk
Andrew M. Childs, David Gosset, and Zak Webb

Levinson’s theorem for graphs II
Andrew M. Childs and David Gosset

Hamiltonian simulation using linear combinations of unitary operations
Andrew M. Childs and Nathan Wiebe

The quantum query complexity of readmany formulas
Andrew M. Childs, Shelby Kimmel, and Robin Kothari

Blackbox Hamiltonian simulation and unitary implementation
Dominic W. Berry and Andrew M. Childs

Levinson’s theorem for graphs
Andrew M. Childs and DJ Strouse

Quantum property testing for boundeddegree graphs
Andris Ambainis, Andrew M. Childs, and YiKai Liu

Quantum query complexity of minorclosed graph properties
Andrew M. Childs and Robin Kothari

Simulating sparse Hamiltonians with star decompositions
Andrew M. Childs and Robin Kothari

Characterization of universal twoqubit Hamiltonians
Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols

Limitations on the simulation of nonsparse Hamiltonians
Andrew M. Childs and Robin Kothari

The quantum query complexity of certification
Andris Ambainis, Andrew M. Childs, François Le Gall, and Seiichiro Tani

Quantum algorithms for algebraic problems
Andrew M. Childs and Wim van Dam

On the relationship between continuous and discretetime quantum walk
Andrew M. Childs

Universal computation by quantum walk
Andrew M. Childs

Optimal quantum adversary lower bounds for ordered search
Andrew M. Childs and Troy Lee

Quantum algorithms for hidden nonlinear structures
Andrew M. Childs, Leonard J. Schulman, and Umesh V. Vazirani

Any ANDOR formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang

Discretequery quantum algorithm for NAND trees
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David YongeMallo

Weak FourierSchur sampling, the hidden subgroup problem, and the quantum collision problem
Andrew M. Childs, Aram W. Harrow, and Pawel Wocjan

Improved quantum algorithms for the ordered search problem via semidefinite programming
Andrew M. Childs, Andrew J. Landahl, and Pablo A. Parrilo

On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
Andrew M. Childs and Pawel Wocjan

Quantum algorithm for a generalized hidden shift problem
Andrew M. Childs and Wim van Dam

Twoway quantum communication channels
Andrew M. Childs, Debbie W. Leung, and H.K. Lo

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

Optimal measurements for the dihedral hidden subgroup
problem
Dave Bacon, Andrew M. Childs, and Wim van Dam

The limitations of nice mutually unbiased bases
Michael Aschbacher, Andrew M. Childs, and Pawel Wocjan

Spatial search and the Dirac equation
Andrew M. Childs and Jeffrey Goldstone

Unified derivations of measurementbased schemes for quantum
computation
Andrew M. Childs, Debbie W. Leung, and Michael A. Nielsen

Quantum algorithms for subset finding
Andrew M. Childs and Jason M. Eisenberg

Lower bounds on the complexity of simulating quantum gates
Andrew M. Childs, Henry L. Haselgrove, and Michael A. Nielsen

Spatial search by quantum walk
Andrew M. Childs and Jeffrey Goldstone

Reversible simulation of bipartite product Hamiltonians
Andrew M. Childs, Debbie W. Leung, and Guifre Vidal

Exponential algorithmic speedup by quantum walk
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman

Asymptotic entanglement capacity of the Ising and anisotropic
Heisenberg interactions
Andrew M. Childs, Debbie W. Leung, Frank Verstraete, and Guifre Vidal

Quantum search by measurement
Andrew M. Childs, Enrico Deotto, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Andrew J. Landahl

Secure assisted quantum computation
Andrew M. Childs

Universal simulation of Hamiltonian dynamics for quantum systems with
finitedimensional state spaces
Michael A. Nielsen, Michael J. Bremner, Jennifer L. Dodd, Andrew M. Childs, and Christopher M. Dawson

Robustness of adiabatic quantum computation
Andrew M. Childs, Edward Farhi, and John Preskill

An example of the difference between quantum and classical random
walks
Andrew M. Childs, Edward Farhi, and Sam Gutmann

Finding cliques by quantum adiabatic evolution
Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann

Realization of quantum process tomography in NMR
Andrew M. Childs, Isaac L. Chuang, and Debbie W. Leung

Universal simulation of Markovian quantum dynamics
Dave Bacon, Andrew M. Childs, Isaac L. Chuang, Julia Kempe, Debbie Leung, and Xinlan Zhou

Universal quantum computation with twolevel trapped ions
Andrew M. Childs and Isaac L. Chuang

Exact sampling from nonattractive distributions using summary states
Andrew M. Childs, Ryan B. Patterson, and David J. C. MacKay

Quantum information and precision measurement
Andrew M. Childs, John Preskill, and Joseph Renes

A model for MeV C_{n} track damage in YIG
Thomas A. Tombrello, Andrew M. Childs, and John W. Hartman

Simulation of keV clusters incident on gold targets
Andrew M. Childs, Mark H. Shapiro, and Thomas A. Tombrello