Andrew M. Childs

According to our database1, Andrew M. Childs authored at least 51 papers between 2002 and 2020.

Collaborative distances:
  • Dijkstra number2 of five.
  • Erdős number3 of two.



In proceedings 
PhD thesis 





Can graph properties have exponential quantum speedup?
CoRR, 2020

A Theory of Trotter Error.
CoRR, 2019

Two-message verification of quantum computation.
CoRR, 2019

Quantum algorithm for estimating volumes of convex bodies.
CoRR, 2019

Time-dependent Hamiltonian simulation with $L^1$-norm scaling.
CoRR, 2019

Quantum spectral methods for differential equations.
CoRR, 2019

Nearly optimal lattice simulation by product formulas.
CoRR, 2019

Circuit Transformations for Quantum Architectures.
Proceedings of the 14th Conference on the Theory of Quantum Computation, 2019

Toward the first quantum simulation with quantum speedup.
Proc. Natl. Acad. Sci. U.S.A., 2018

Quantum algorithms and lower bounds for convex optimization.
CoRR, 2018

Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision.
SIAM J. Comput., 2017

Efficient simulation of sparse Markovian quantum dynamics.
Quantum Information & Computation, 2017

Automated optimization of large quantum circuits with continuous parameters.
CoRR, 2017

Quantum algorithm for multivariate polynomial interpolation.
CoRR, 2017

Complexity of the XY antiferromagnet at fixed magnetization.
Quantum Information & Computation, 2016

Optimal Quantum Algorithm for Polynomial Interpolation.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

The Bose-Hubbard Model is QMA-complete.
Theory of Computing, 2015

Momentum switches.
Quantum Information & Computation, 2015

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

The computational power of matchgates and the XY interaction on arbitrary graphs.
Quantum Information & Computation, 2014

Constructing elliptic curve isogenies in quantum subexponential time.
J. Mathematical Cryptology, 2014

Quantum computation of discrete logarithms in semigroups.
J. Mathematical Cryptology, 2014

Exponential improvement in precision for simulating sparse Hamiltonians.
Proceedings of the Symposium on Theory of Computing, 2014

A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
CoRR, 2013

Easy and Hard Functions for the Boolean Hidden Shift Problem.
Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Time-Efficient Quantum Walks for 3-Distinctness.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Quantum Query Complexity of Minor-Closed Graph Properties.
SIAM J. Comput., 2012

Hamiltonian simulation using linear combinations of unitary operations.
Quantum Information & Computation, 2012

Black-box hamiltonian simulation and unitary implementation.
Quantum Information & Computation, 2012

The Quantum Query Complexity of Read-Many Formulas.
Proceedings of the Algorithms - ESA 2012, 2012

Characterization of universal two-qubit Hamiltonians.
Quantum Information & Computation, 2011

Quantum Property Testing for Bounded-Degree Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Any AND-OR Formula of Size N Can Be Evaluated in Time N1/2+o(1) on a Quantum Computer.
SIAM J. Comput., 2010

Limitations on the simulation of non-sparse Hamiltonians.
Quantum Information & Computation, 2010

The quantum query complexity of certification.
Quantum Information & Computation, 2010

Simulating Sparse Hamiltonians with Star Decompositions.
Proceedings of the Theory of Quantum Computation, Communication, and Cryptography, 2010

Discrete-Query Quantum Algorithm for NAND Trees.
Theory of Computing, 2009

Optimal Quantum Adversary Lower Bounds for Ordered Search.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems.
Quantum Information & Computation, 2007

Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem.
Proceedings of the STACS 2007, 2007

Quantum algorithm for a generalized hidden shift problem.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Quantum Algorithms for Hidden Nonlinear Structures.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Optimal measurements for the dihedral hidden subgroup problem.
Chicago J. Theor. Comput. Sci., 2006

Quantum algorithms for subset finding.
Quantum Information & Computation, 2005

Secure assisted quantum computation.
Quantum Information & Computation, 2005

From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Reversible Simulation of Bipartite Product Hamiltonians.
IEEE Trans. Information Theory, 2004

Asymptotic entanglement capacity of the ising and anisotropic Heisenberg interactions.
Quantum Information & Computation, 2003

Exponential algorithmic speedup by a quantum walk.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

An Example of the Difference Between Quantum and Classical Random Walks.
Quantum Information Processing, 2002

Finding cliques by quantum adiabatic evolution.
Quantum Information & Computation, 2002