Andrew M. Childs

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 46

Top Topics

Quantum Computation

Top Venues

Quantum Inf. Comput.

Publications

Zhenning Liu, Dhruv Devulapalli, Dominik Hangleiter, Yi-Kai Liu, Alicia J. Kollár, Alexey V. Gorshkov, Andrew M. Childs
Efficiently verifiable quantum advantage on near-term analog quantum simulators. CoRR (2024)
Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani
Quantum Algorithms and the Power of Forgetting. ITCS (2023)
Dong An, Andrew M. Childs, Lin Lin
Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters. CoRR (2023)
Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants. NeurIPS (2022)
Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, Chenyi Zhang
Quantum simulation of real-space dynamics. CoRR (2022)
Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, Chenyi Zhang
Quantum simulation of real-space dynamics. Quantum 6 (2022)
Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, Daochen Wang
Quantum divide and conquer. CoRR (2022)
Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Eddie Schoute
Advantages and limitations of quantum routing. CoRR (2022)
Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani
Quantum algorithms and the power of forgetting. CoRR (2022)
Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants. CoRR (2022)
Andrew M. Childs, Shih-Han Hung, Tongyang Li
Quantum Query Complexity with Matrix-Vector Products. ICALP (2021)
Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, Andrew M. Childs
Efficient quantum algorithm for dissipative nonlinear differential equations. Proc. Natl. Acad. Sci. USA 118 (35) (2021)
Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Samuel King, Eddie Schoute, Hrishee Shastri
Quantum routing with fast reversals. CoRR (2021)
Daochen Wang, Xuchen You, Tongyang Li, Andrew M. Childs
Quantum Exploration Algorithms for Multi-Armed Bandits. AAAI (2021)
Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Samuel King, Eddie Schoute, Hrishee Shastri
Quantum routing with fast reversals. Quantum 5 (2021)
Andrew M. Childs, Shih-Han Hung, Tongyang Li
Quantum query complexity with matrix-vector products. CoRR (2021)
Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander
High-precision quantum algorithms for partial differential equations. Quantum 5 (2021)
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, Xiaodi Wu
Quantum algorithms and lower bounds for convex optimization. Quantum 4 (2020)
Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
Symmetries, graph properties, and quantum speedups. CoRR (2020)
Andrew M. Childs, Daochen Wang
Can graph properties have exponential quantum speedup? CoRR (2020)
Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander
High-precision quantum algorithms for partial differential equations. CoRR (2020)
Andrew Y. Guo, Abhinav Deshpande, Su-Kuan Chu, Zachary Eldredge, Przemyslaw Bienias, Dhruv Devulapalli, Yuan Su, Andrew M. Childs, Alexey V. Gorshkov
Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions. CoRR (2020)
Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, Nathan Wiebe
Time-dependent Hamiltonian simulation withL1-norm scaling. Quantum 4 (2020)
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
Quantum Coupon Collector. CoRR (2020)
Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, Andrew M. Childs
Efficient quantum algorithm for dissipative nonlinear differential equations. CoRR (2020)
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
Quantum Coupon Collector. TQC (2020)
Daochen Wang, Xuchen You, Tongyang Li, Andrew M. Childs
Quantum exploration algorithms for multi-armed bandits. CoRR (2020)
Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
Symmetries, Graph Properties, and Quantum Speedups. FOCS (2020)
Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, Shih-Han Hung
Non-interactive classical verification of quantum computation. IACR Cryptol. ePrint Arch. 2020 (2020)
Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, Shih-Han Hung
Non-interactive Classical Verification of Quantum Computation. TCC (3) (2020)
Andrew M. Childs, Eddie Schoute, Cem M. Unsal
Circuit Transformations for Quantum Architectures. TQC (2019)
Andrew M. Childs, Jin-Peng Liu
Quantum spectral methods for differential equations. CoRR (2019)
Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, Shuchen Zhu
A Theory of Trotter Error. CoRR (2019)
Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, Xiaodi Wu
Quantum algorithm for estimating volumes of convex bodies. CoRR (2019)
Andrew M. Childs, Yuan Su
Nearly optimal lattice simulation by product formulas. CoRR (2019)
Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, Nathan Wiebe
Time-dependent Hamiltonian simulation with $L^1$-norm scaling. CoRR (2019)
Gorjan Alagic, Andrew M. Childs, Shih-Han Hung
Two-message verification of quantum computation. CoRR (2019)
Andrew M. Childs, Eddie Schoute, Cem M. Unsal
Circuit Transformations for Quantum Architectures. CoRR (2019)
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, Xiaodi Wu
Quantum algorithms and lower bounds for convex optimization. CoRR (2018)
Andrew M. Childs, Dmitri Maslov, Yun Seong Nam, Neil J. Ross, Yuan Su
Toward the first quantum simulation with quantum speedup. Proc. Natl. Acad. Sci. USA 115 (38) (2018)
Jianxin Chen, Andrew M. Childs, Shih-Han Hung
Quantum algorithm for multivariate polynomial interpolation. CoRR (2017)
Yun Seong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, Dmitri Maslov
Automated optimization of large quantum circuits with continuous parameters. CoRR (2017)
Andrew M. Childs, Tongyang Li
Efficient simulation of sparse Markovian quantum dynamics. Quantum Inf. Comput. 17 (11&12) (2017)
Andrew M. Childs, Robin Kothari, Rolando D. Somma
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision. SIAM J. Comput. 46 (6) (2017)
Andrew M. Childs, David Gosset, Zak Webb
Complexity of the XY antiferromagnet at fixed magnetization. Quantum Inf. Comput. 16 (1&2) (2016)
Andrew M. Childs, Wim van Dam, Shih-Han Hung, Igor E. Shparlinski
Optimal Quantum Algorithm for Polynomial Interpolation. ICALP (2016)
Andrew M. Childs, Wim van Dam, Shih-Han Hung, Igor E. Shparlinski
Optimal quantum algorithm for polynomial interpolation. CoRR (2015)
Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb
Momentum switches. Quantum Inf. Comput. 15 (7&8) (2015)
Andrew M. Childs, David Gosset, Zak Webb
The Bose-Hubbard Model is QMA-complete. Theory Comput. 11 (2015)
Dominic W. Berry, Andrew M. Childs, Robin Kothari
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. FOCS (2015)
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma
Exponential improvement in precision for simulating sparse Hamiltonians. STOC (2014)
Andrew M. Childs, David Jao, Vladimir Soukharev
Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8 (1) (2014)
Andrew M. Childs, David Gosset, Zak Webb
The Bose-Hubbard Model is QMA-complete. ICALP (1) (2014)
Daniel J. Brod, Andrew M. Childs
The computational power of matchgates and the XY interaction on arbitrary graphs. Quantum Inf. Comput. 14 (11-12) (2014)
Andrew M. Childs, Gábor Ivanyos
Quantum computation of discrete logarithms in semigroups. J. Math. Cryptol. 8 (4) (2014)
Andrew M. Childs, David Gosset, Zak Webb
The Bose-Hubbard model is QMA-complete. CoRR (2013)
Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler
Easy and hard functions for the Boolean hidden shift problem CoRR (2013)
Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates CoRR (2013)
Andrew M. Childs, Gábor Ivanyos
Quantum computation of discrete logarithms in semigroups. CoRR (2013)
Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler
Easy and Hard Functions for the Boolean Hidden Shift Problem. TQC (2013)
Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
Time-Efficient Quantum Walks for 3-Distinctness. ICALP (1) (2013)
Andrew M. Childs, Robin Kothari
Quantum Query Complexity of Minor-Closed Graph Properties. SIAM J. Comput. 41 (6) (2012)
Andrew M. Childs, Shelby Kimmel, Robin Kothari
The Quantum Query Complexity of Read-Many Formulas. ESA (2012)
Andrew M. Childs, Nathan Wiebe
Hamiltonian simulation using linear combinations of unitary operations. Quantum Inf. Comput. 12 (11-12) (2012)
Dominic W. Berry, Andrew M. Childs
Black-box hamiltonian simulation and unitary implementation. Quantum Inf. Comput. 12 (1-2) (2012)
Andris Ambainis, Andrew M. Childs, Yi-Kai Liu
Quantum Property Testing for Bounded-Degree Graphs. APPROX-RANDOM (2011)
Andrew M. Childs, Shelby Kimmel, Robin Kothari
The quantum query complexity of read-many formulas CoRR (2011)
Andrew M. Childs, Debbie W. Leung, Laura Mancinska, Maris Ozols
Characterization of universal two-qubit Hamiltonians. Quantum Inf. Comput. 11 (1&2) (2011)
Andrew M. Childs, Robin Kothari
Quantum query complexity of minor-closed graph properties. STACS (2011)
Andrew M. Childs, Robin Kothari
Quantum query complexity of minor-closed graph properties CoRR (2010)
Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang
on a Quantum Computer. SIAM J. Comput. 39 (6) (2010)
Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani
The quantum query complexity of certification. Quantum Inf. Comput. 10 (3&4) (2010)
Andrew M. Childs, Robin Kothari
Limitations on the simulation of non-sparse Hamiltonians. Quantum Inf. Comput. 10 (7&8) (2010)
Andrew M. Childs, Robin Kothari
Simulating Sparse Hamiltonians with Star Decompositions. TQC (2010)
Andris Ambainis, Andrew M. Childs, Yi-Kai Liu
Quantum property testing for bounded-degree graphs CoRR (2010)
Andrew M. Childs, David Jao, Vladimir Soukharev
Constructing elliptic curve isogenies in quantum subexponential time CoRR (2010)
Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani
The quantum query complexity of certification CoRR (2009)
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David L. Yonge-Mallo
Discrete-Query Quantum Algorithm for NAND Trees. Theory Comput. 5 (1) (2009)
Andrew M. Childs, Troy Lee
Optimal Quantum Adversary Lower Bounds for Ordered Search. ICALP (1) (2008)
Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang
on a Quantum Computer. FOCS (2007)
Andrew M. Childs, Aram W. Harrow, Pawel Wocjan
Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem. STACS (2007)
Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani
Quantum Algorithms for Hidden Nonlinear Structures. FOCS (2007)
Andrew M. Childs, Wim van Dam
Quantum algorithm for a generalized hidden shift problem. SODA (2007)
Andrew M. Childs, Pawel Wocjan
On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems. Quantum Inf. Comput. 7 (5) (2007)
Dave Bacon, Andrew M. Childs, Wim van Dam
Optimal measurements for the dihedral hidden subgroup problem. Chic. J. Theor. Comput. Sci. 2006 (2006)
Andrew M. Childs, Jason M. Eisenberg
Quantum algorithms for subset finding. Quantum Inf. Comput. 5 (7) (2005)
Dave Bacon, Andrew M. Childs, Wim van Dam
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. FOCS (2005)
Andrew M. Childs
Secure assisted quantum computation. Quantum Inf. Comput. 5 (6) (2005)
Andrew M. Childs, Debbie W. Leung, Guifre Vidal
Reversible Simulation of Bipartite Product Hamiltonians. IEEE Trans. Inf. Theory 50 (6) (2004)
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman
Exponential algorithmic speedup by a quantum walk. STOC (2003)
Andrew M. Childs, Debbie W. Leung, Frank Verstraete, Guifre Vidal
Asymptotic entanglement capacity of the ising and anisotropic Heisenberg interactions. Quantum Inf. Comput. 3 (2) (2003)
Andrew M. Childs, Edward Farhi, Sam Gutmann
An Example of the Difference Between Quantum and Classical Random Walks. Quantum Inf. Process. 1 (1-2) (2002)
Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, Sam Gutmann
Finding cliques by quantum adiabatic evolution. Quantum Inf. Comput. 2 (3) (2002)