Andrew M. Childs

102 papers A* 12A 4Journal 76Unranked 9

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