Andrew M. Childs

According to our database, Andrew M. Childs authored at least 68 papers between 2002 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Efficiently verifiable quantum advantage on near-term analog quantum simulators.

Zhenning Liu, Dhruv Devulapalli, Dominik Hangleiter, Yi-Kai Liu, Alicia J. Kollár, Alexey V. Gorshkov, Andrew M. Childs

CoRR, 2024

2023

Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters.

Dong An, Andrew M. Childs, Lin Lin

CoRR, 2023

Quantum Algorithms and the Power of Forgetting.

Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Quantum simulation of real-space dynamics.

Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, Chenyi Zhang

Quantum, September, 2022

Quantum divide and conquer.

Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, Daochen Wang

CoRR, 2022

Advantages and limitations of quantum routing.

Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Eddie Schoute

CoRR, 2022

Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants.

Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

High-precision quantum algorithms for partial differential equations.

Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander

Quantum, 2021

Quantum routing with fast reversals.

Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Samuel King, Eddie Schoute, Hrishee Shastri

Quantum, 2021

Efficient quantum algorithm for dissipative nonlinear differential equations.

Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, Andrew M. Childs

Proc. Natl. Acad. Sci. USA, 2021

Quantum Query Complexity with Matrix-Vector Products.

Andrew M. Childs, Shih-Han Hung, Tongyang Li

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Quantum Exploration Algorithms for Multi-Armed Bandits.

Daochen Wang, Xuchen You, Tongyang Li, Andrew M. Childs

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

Quantum algorithms and lower bounds for convex optimization.

Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, Xiaodi Wu

Quantum, 2020

Time-dependent Hamiltonian simulation withL1-norm scaling.

Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, Nathan Wiebe

Quantum, 2020

Non-interactive classical verification of quantum computation.

Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, Shih-Han Hung

IACR Cryptol. ePrint Arch., 2020

Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions.

Andrew Y. Guo, Abhinav Deshpande, Su-Kuan Chu, Zachary Eldredge, Przemyslaw Bienias, Dhruv Devulapalli, Yuan Su, Andrew M. Childs, Alexey V. Gorshkov

CoRR, 2020

Can graph properties have exponential quantum speedup?

Andrew M. Childs, Daochen Wang

CoRR, 2020

Quantum Coupon Collector.

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

Symmetries, Graph Properties, and Quantum Speedups.

Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

A Theory of Trotter Error.

Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, Shuchen Zhu

CoRR, 2019

Two-message verification of quantum computation.

Gorjan Alagic, Andrew M. Childs, Shih-Han Hung

CoRR, 2019

Quantum algorithm for estimating volumes of convex bodies.

Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, Xiaodi Wu

CoRR, 2019

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

Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, Nathan Wiebe

CoRR, 2019

Quantum spectral methods for differential equations.

Andrew M. Childs, Jin-Peng Liu

CoRR, 2019

Nearly optimal lattice simulation by product formulas.

Andrew M. Childs, Yuan Su

CoRR, 2019

Circuit Transformations for Quantum Architectures.

Andrew M. Childs, Eddie Schoute, Cem M. Unsal

Proceedings of the 14th Conference on the Theory of Quantum Computation, 2019

2018

Toward the first quantum simulation with quantum speedup.

Andrew M. Childs, Dmitri Maslov, Yun Seong Nam, Neil J. Ross, Yuan Su

Proc. Natl. Acad. Sci. USA, 2018

2017

Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision.

Andrew M. Childs, Robin Kothari, Rolando D. Somma

SIAM J. Comput., 2017

Efficient simulation of sparse Markovian quantum dynamics.

Andrew M. Childs, Tongyang Li

Quantum Inf. Comput., 2017

Automated optimization of large quantum circuits with continuous parameters.

Yun Seong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, Dmitri Maslov

CoRR, 2017

Quantum algorithm for multivariate polynomial interpolation.

Jianxin Chen, Andrew M. Childs, Shih-Han Hung

CoRR, 2017

2016

Complexity of the XY antiferromagnet at fixed magnetization.

Andrew M. Childs, David Gosset, Zak Webb

Quantum Inf. Comput., 2016

Optimal Quantum Algorithm for Polynomial Interpolation.

Andrew M. Childs, Wim van Dam, Shih-Han Hung, Igor E. Shparlinski

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

The Bose-Hubbard Model is QMA-complete.

Andrew M. Childs, David Gosset, Zak Webb

Theory Comput., 2015

Momentum switches.

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

Quantum Inf. Comput., 2015

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters.

Dominic W. Berry, Andrew M. Childs, Robin Kothari

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

The computational power of matchgates and the XY interaction on arbitrary graphs.

Daniel J. Brod, Andrew M. Childs

Quantum Inf. Comput., 2014

Constructing elliptic curve isogenies in quantum subexponential time.

Andrew M. Childs, David Jao, Vladimir Soukharev

J. Math. Cryptol., 2014

Quantum computation of discrete logarithms in semigroups.

Andrew M. Childs, Gábor Ivanyos

J. Math. Cryptol., 2014

Exponential improvement in precision for simulating sparse Hamiltonians.

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

Proceedings of the Symposium on Theory of Computing, 2014

2013

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

Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez

CoRR, 2013

Easy and Hard Functions for the Boolean Hidden Shift Problem.

Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler

Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Time-Efficient Quantum Walks for 3-Distinctness.

Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Quantum Query Complexity of Minor-Closed Graph Properties.

Andrew M. Childs, Robin Kothari

SIAM J. Comput., 2012

Hamiltonian simulation using linear combinations of unitary operations.

Andrew M. Childs, Nathan Wiebe

Quantum Inf. Comput., 2012

Black-box hamiltonian simulation and unitary implementation.

Dominic W. Berry, Andrew M. Childs

Quantum Inf. Comput., 2012

The Quantum Query Complexity of Read-Many Formulas.

Andrew M. Childs, Shelby Kimmel, Robin Kothari

Proceedings of the Algorithms - ESA 2012, 2012

2011

Characterization of universal two-qubit Hamiltonians.

Andrew M. Childs, Debbie W. Leung, Laura Mancinska, Maris Ozols

Quantum Inf. Comput., 2011

Quantum Property Testing for Bounded-Degree Graphs.

Andris Ambainis, Andrew M. Childs, Yi-Kai Liu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Any AND-OR Formula of Size N Can Be Evaluated in Time N^1/2+o(1) on a Quantum Computer.

Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang

SIAM J. Comput., 2010

Limitations on the simulation of non-sparse Hamiltonians.

Andrew M. Childs, Robin Kothari

Quantum Inf. Comput., 2010

The quantum query complexity of certification.

Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani

Quantum Inf. Comput., 2010

Simulating Sparse Hamiltonians with Star Decompositions.

Andrew M. Childs, Robin Kothari

Proceedings of the Theory of Quantum Computation, Communication, and Cryptography, 2010

2009

Discrete-Query Quantum Algorithm for NAND Trees.

Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David L. Yonge-Mallo

Theory Comput., 2009

2008

Optimal Quantum Adversary Lower Bounds for Ordered Search.

Andrew M. Childs, Troy Lee

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems.

Andrew M. Childs, Pawel Wocjan

Quantum Inf. Comput., 2007

Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem.

Andrew M. Childs, Aram W. Harrow, Pawel Wocjan

Proceedings of the STACS 2007, 2007

Quantum algorithm for a generalized hidden shift problem.

Andrew M. Childs, Wim van Dam

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Quantum Algorithms for Hidden Nonlinear Structures.

Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Optimal measurements for the dihedral hidden subgroup problem.

Dave Bacon, Andrew M. Childs, Wim van Dam

Chic. J. Theor. Comput. Sci., 2006

2005

Quantum algorithms for subset finding.

Andrew M. Childs, Jason M. Eisenberg

Quantum Inf. Comput., 2005

Secure assisted quantum computation.

Andrew M. Childs

Quantum Inf. Comput., 2005

From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups.

Dave Bacon, Andrew M. Childs, Wim van Dam

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Reversible Simulation of Bipartite Product Hamiltonians.

Andrew M. Childs, Debbie W. Leung, Guifre Vidal

IEEE Trans. Inf. Theory, 2004

2003

Asymptotic entanglement capacity of the ising and anisotropic Heisenberg interactions.

Andrew M. Childs, Debbie W. Leung, Frank Verstraete, Guifre Vidal

Quantum Inf. Comput., 2003

Exponential algorithmic speedup by a quantum walk.

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

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

An Example of the Difference Between Quantum and Classical Random Walks.

Andrew M. Childs, Edward Farhi, Sam Gutmann

Quantum Inf. Process., 2002

Finding cliques by quantum adiabatic evolution.

Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Quantum Inf. Comput., 2002