Papers by Andrew Childs

Preprints

1. Measuring gravitational lensing time delays with quantum information processing
   Zhenning Liu, William DeRocco, Shiming Gu, Emil T. Khabiboulline, Soonwon Choi, Andrew M. Childs, Anson Hook, Alexey V. Gorshkov, and Daniel Gottesman
   • arXiv:2510.07898
   • Coverage in New Scientist
2. Low-depth fermion routing without ancillas
   Nathan Constantinides, Jeffery Yu, Dhruv Devulapalli, Ali Fahimniya, Luke Schaeffer, Andrew M. Childs, Michael J. Gullans, Alexander Schuckert, and Alexey V. Gorshkov
   • arXiv:2510.05099
3. Time independence does not limit information flow. II. The case with ancillas
   T. C. Mooney, Dong Yuan, Adam Ehrenberg, Christopher L. Baldwin, Alexey V. Gorshkov, and Andrew M. Childs
   • arXiv:2505.18254
4. Time independence does not limit information flow. I. The free-particle case
   Dong Yuan, Chao Yin, T. C. Mooney, Christopher L. Baldwin, Andrew M. Childs, and Alexey V. Gorshkov
   • arXiv:2505.18249
5. Quantum routing and entanglement dynamics through bottlenecks
   Dhruv Devulapalli, Chao Yin, Andrew Y. Guo, Eddie Schoute, Andrew M. Childs, Alexey V. Gorshkov, and Andrew Lucas
   • arXiv:2505.16948
6. Translation-invariant quantum algorithms for ordered search are optimal
   Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak, and Luke Schaeffer
   • arXiv:2503.21090
7. Optimal routing protocols for reconfigurable atom arrays
   Nathan Constantinides, Ali Fahimniya, Dhruv Devulapalli, Dolev Bluvstein, Michael J. Gullans, J. V. Porto, Andrew M. Childs, and Alexey V. Gorshkov
   • arXiv:2411.05061
8. Low-depth quantum symmetrization
   Zhenning Liu, Andrew M. Childs, and Daniel Gottesman
   • arXiv:2411.04019
9. Laplace transform based quantum eigenvalue transformation via linear combination of Hamiltonian simulation
   Dong An, Andrew M. Childs, Lin Lin, and Lexing Ying
   • arXiv:2411.04010
   • Presented at QIP 2025 (combined with arXiv:2312.03916)
10. Quantum algorithms for simulating nuclear effective field theories
    James D. Watson, Jacob Bringewatt, Alexander F. Shaw, Andrew M. Childs, Alexey V. Gorshkov, and Zohreh Davoudi
    • arXiv:2312.05344

Publications

1. Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
   Dong An, Andrew M. Childs, and Lin Lin
   • arXiv:2312.03916
   • Presented at QIP 2025 (combined with arXiv:2411.04010)
   • To appear in Communications in Mathematical Physics
2. Efficient preparation of Dicke states
   Jeffery Yu, Sean R. Muleady, Yu-Xin Wang, Nathan Schine, Alexey V. Gorshkov, and Andrew M. Childs
   • arXiv:2411.03428
   • To appear in Physical Review Letters
3. Entanglement accelerates quantum simulation
   Qi Zhao, You Zhou, and Andrew M. Childs
   • arXiv:2406.02379
   • Presented at QIP 2025
   • Nature Physics 21, 1338 (2025)
   • Cover of the August 2025 issue of Nature Physics
4. Quantum divide and conquer
   Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang
   • arXiv:2210.06419
   • Presented at QIP 2023
   • ACM Transactions on Quantum Computing 6, 17 (2025)
5. Efficient and practical Hamiltonian simulation from time-dependent product formulas
   Jan Lukas Bosse, Andrew M. Childs, Charles Derby, Filippo Maria Gambetta, Ashley Montanaro, Raul A. Santos
   • arXiv:2403.08729
   • Nature Communications 16, 2673 (2025)
6. 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, and Andrew M. Childs
   • arXiv:2403.08195
   • PRX Quantum 6, 010341 (2025)
7. Streaming quantum state purification
   Andrew M. Childs, Honghao Fu, Debbie Leung, Zhi Li, Maris Ozols, and Vedang Vyas
   • arXiv:2309.16387
   • Quantum 9, 1603 (2025)
8. Toward a 2D local implementation of quantum LDPC codes
   Noah Berthusen, Dhruv Devulapalli, Eddie Schoute, Andrew M. Childs, Michael J. Gullans, Alexey V. Gorshkov, and Daniel Gottesman
   • arXiv:2404.17676
   • PRX Quantum 6, 010306 (2025)
9. Quantum routing with teleportation
   Dhruv Devulapalli, Eddie Schoute, Aniruddha Bapat, Andrew M. Childs, and Alexey V. Gorshkov
   • arXiv:2204.04185
   • Physical Review Research 6, 033313 (2024)
10. Quantum algorithm for estimating volumes of convex bodies
    Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu
    • arXiv:1908.03903
    • Presented at QIP 2020 (single-track)
    • ACM Transactions on Quantum Computing 4, 20 (2023)
11. Advantages and limitations of quantum routing
    Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, and Eddie Schoute
    • arXiv:2206.01766
    • PRX Quantum 4, 010313 (2023)
12. Hamiltonian simulation with random inputs
    Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs
    • arXiv:2111.04773
    • Presented at QIP 2022
    • Physical Review Letters 129, 270502 (2022)
13. Quantum algorithms and the power of forgetting
    Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani
    • arXiv:2211.12447
    • 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Leibniz International Proceedings in Informatics, vol. 251, pp. 37:1–37:22 (2023)
    • Coverage in Quanta Magazine
14. Quantum simulation of real-space dynamics
    Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang
    • arXiv:2203.17006
    • Quantum 6, 860 (2022)
15. 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, and Alexey V. Gorshkov
    • arXiv:2007.00662
    • Physical Review Research 4, L042016 (2022)
16. Quantum algorithms for sampling log-concave distributions and estimating normalizing constants
    Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang
    • arXiv:2210.06539
    • Advances in Neural Information Processing Systems (NeurIPS 2022) 35, 23205 (2022)
    • Presented at QIP 2023
17. Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
    Aaron W. Young, William J. Eckner, Nathan Schine, Andrew M. Childs, and Adam M. Kaufman
    • arXiv:2202.01204
    • Science 377, 885 (2022)
18. Efficient product formulas for commutators and applications to quantum simulation
    Yu-An Chen, Andrew M. Childs, Mohammad Hafezi, Zhang Jiang, Hwanmun Kim, and Yijia Xu
    • arXiv:2111.12177
    • Physical Review Research 4, 013191 (2022)
19. High-precision quantum algorithms for partial differential equations
    Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander
    • arXiv:2002.07868
    • Quantum 5, 574 (2021)
20. Nearly optimal time-independent reversal of a spin chain
    Aniruddha Bapat, Eddie Schoute, Alexey V. Gorshkov, and Andrew M. Childs
    • arXiv:2003.02843
    • Physical Review Research 4, L012023 (2022)
21. Efficient quantum algorithm for dissipative nonlinear differential equations
    Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, and Andrew M. Childs
    • arXiv:2011.03185
    • Coverage in Quanta Magazine
    • Proceedings of the National Academy of Sciences 118, e2026805118 (2021)
22. Quantum routing with fast reversals
    Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Samuel King, Eddie Schoute, and Hrishee Shastri
    • arXiv:2103.03264
    • Quantum 5, 533 (2021)
23. Quantum query complexity with matrix-vector products
    Andrew M. Childs, Shih-Han Hung, and Tongyang Li
    • arXiv:2102.11349
    • Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Leibniz International Proceedings in Informatics, vol. 198, pp. 55:1–55:19 (2021)
24. Quantum exploration algorithms for multi-armed bandits
    Daochen Wang, Xuchen You, Tongyang Li, and Andrew M. Childs
    • arXiv:2007.07049
    • Proceedings of the AAAI Conference on Artificial Intelligence 35 (11), 10102-10110 (2021)
25. Theory of Trotter error with commutator scaling
    Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu
    • arXiv:1912.08854
    • Presented at QIP 2020 (combined with arXiv:1901.00564)
    • Physical Review X 11, 011020 (2021)
26. Non-interactive classical verification of quantum computation
    Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung
    • arXiv:1911.08101
    • Presented at QCrypt 2020
    • Theory of Cryptography Conference (TCC), Lecture Notes in Computer Science 12552, 153–180 (2020)
    • Presented at QIP 2021 (merged with arXiv:1911.07546 by Andrea Coladangelo, Thomas Vidick, and Tina Zhang and arXiv:1912.04769 by Nir Bitansky and Omri Shmueli)
27. Symmetries, graph properties, and quantum speedups
    Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang
    • arXiv:2006.12760 (subsumes arXiv:2001.10520)
    • Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020)
    • Presented at QIP 2021
    • SIAM Journal on Computing 55, FOCS20-368–FOCS20-415 (2024)
28. Signaling and scrambling with strongly long-range interactions
    Andrew Y. Guo, Minh C. Tran, Andrew M. Childs, Alexey V. Gorshkov, and Zhe-Xuan Gong
    • arXiv:1906.02662
    • Physical Review A 102, 010401(R) (2020)
29. Destructive error interference in product-formula lattice simulation
    Minh C. Tran, Su-Kuan Chu, Yuan Su, Andrew M. Childs, and Alexey V. Gorshkov
    • arXiv:1912.11047
    • Physical Review Letters 124, 220502 (2020)
30. Time-dependent Hamiltonian simulation with L¹-norm scaling
    Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe
    • arXiv:1906.07115
    • Quantum 4, 254 (2020)
31. Quantum coupon collector
    Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf
    • arXiv:2002.07688
    • Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics, vol. 158, pp. 10:1–10:17 (2020)
32. Quantum spectral methods for differential equations
    Andrew M. Childs and Jin-Peng Liu
    • arXiv:1901.00961
    • Communications in Mathematical Physics 375, 1427–1457 (2020)
33. Quantum algorithms and lower bounds for convex optimization
    Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu
    • arXiv:1809.01731
    • Presented at QIP 2019 (combined with arXiv:1809.00643 by Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf)
    • Quantum 4, 221 (2020)
34. Faster quantum simulation by randomization
    Andrew M. Childs, Aaron Ostrander, and Yuan Su
    • arXiv:1805.08385
    • Quantum 3, 182 (2019)
35. Nearly optimal lattice simulation by product formulas
    Andrew M. Childs and Yuan Su
    • arXiv:1901.00564
    • Physical Review Letters 123, 050503 (2019)
    • Presented at QIP 2020 (combined with arXiv:1912.08854)
36. Locality and digital quantum simulation of power-law interactions
    Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov
    • arXiv:1808.05225
    • Physical Review X 9, 031006 (2019)
37. Circuit transformations for quantum architectures
    Andrew M. Childs, Eddie Schoute, and Cem M. Unsal
    • arXiv:1902.09102
    • arct software package
    • Proceedings of the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), Leibniz International Proceedings in Informatics, vol. 135, pp. 3:1–3:24 (2019)
38. Toward the first quantum simulation with quantum speedup
    Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su
    • arXiv:1711.10980
    • simcount software package
    • Presented at QIP 2018
    • Proceedings of the National Academy of Sciences 115, 9456–9461 (2018)
    • Coverage in Nature Physics
39. Automated optimization of large quantum circuits with continuous parameters
    Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov
    • arXiv:1710.07345
    • npj Quantum Information 4, 23 (2018)
40. Quantum algorithm for multivariate polynomial interpolation
    Jianxin Chen, Andrew M. Childs, and Shih-Han Hung
    • arXiv:1701.03990
    • Proceedings of the Royal Society A 474, 20170480 (2018)
41. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
    Andrew M. Childs, Robin Kothari, and Rolando D. Somma
    • arXiv:1511.02306
    • Presented at QIP 2016
    • SIAM Journal on Computing 46, 1920–1950 (2017)
42. Quantum algorithm for linear differential equations with exponentially improved dependence on precision
    Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang
    • arXiv:1701.03684
    • Communications in Mathematical Physics 356, 1057–1081 (2017)
43. Efficient simulation of sparse Markovian quantum dynamics
    Andrew M. Childs and Tongyang Li
    • arXiv:1611.05543
    • Quantum Information and Computation 17, 901–947 (2017)
44. Optimal quantum algorithm for polynomial interpolation
    Andrew M. Childs, Wim van Dam, Shih-Han Hung, and Igor E. Shparlinski
    • arXiv:1509.09271
    • Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp. 16:1–16:13 (2016)
45. Optimal state discrimination and unstructured search in nonlinear quantum mechanics
    Andrew M. Childs and Joshua Young
    • arXiv:1507.06334
    • Physical Review A 93, 022314 (2016)
46. Complexity of the XY antiferromagnet at fixed magnetization
    Andrew M. Childs, David Gosset, and Zak Webb
    • arXiv:1503.07083
    • Quantum Information and Computation 16, 1–18 (2016)
47. Hamiltonian simulation with nearly optimal dependence on all parameters
    Dominic W. Berry, Andrew M. Childs, and Robin Kothari
    • arXiv:1501.01715
    • Presented at QIP 2015
    • Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS 2015), pp. 792–809 (2015)
48. Simulating Hamiltonian dynamics with a truncated Taylor series
    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
    • arXiv:1412.4687
    • Physical Review Letters 114, 090502 (2015)
49. Momentum switches
    Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, and Zak Webb
    • arXiv:1406.4510
    • Quantum Information and Computation 15, 601–621 (2015)
50. Quantum computation of discrete logarithms in semigroups
    Andrew M. Childs and Gábor Ivanyos
    • arXiv:1310.6238
    • Journal of Mathematical Cryptology 8, 405–416 (2014)
51. Spatial search by continuous-time quantum walks on crystal lattices
    Andrew M. Childs and Yimin Ge
    • arXiv:1403.2676
    • Physical Review A 89, 052337 (2014)
52. The Bose-Hubbard model is QMA-complete
    Andrew M. Childs, David Gosset, and Zak Webb
    • arXiv:1311.3297
    • Presented at QIP 2014
    • Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), pp. 308–319 (2014)
    • Theory of Computing 11, 491–602 (2015)
53. Exponential improvement in precision for simulating sparse Hamiltonians
    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
    • arXiv:1312.1414
    • Presented at QIP 2014
    • Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), pp. 283–292 (2014)
    • Forum of Mathematics, Sigma 5, e8 (2017)
54. The computational power of matchgates and the XY interaction on arbitrary graphs
    Daniel J. Brod and Andrew M. Childs
    • arXiv:1308.1463
    • Quantum Information and Computation 14, 901–916 (2014)
55. Interpolatability distinguishes LOCC from separable von Neumann measurements
    Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols
    • arXiv:1306.5992
    • Journal of Mathematical Physics 54, 112204 (2013)
56. Constructing elliptic curve isogenies in quantum subexponential time
    Andrew M. Childs, David Jao, and Vladimir Soukharev
    • arXiv:1012.4019
    • Presented at QIP 2011
    • Journal of Mathematical Cryptology 8, 1–29 (2014)
57. Product formulas for exponentials of commutators
    Andrew M. Childs and Nathan Wiebe
    • arXiv:1211.4945
    • Journal of Mathematical Physics 54, 062202 (2013)
58. A time-efficient quantum walk for 3-distinctness using nested updates
    Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
    • arXiv:1302.7316
    • Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013), Lecture Notes in Computer Science 7965, 105–122 (2013) (merged with arXiv:1302.3143 by Aleksandrs Belovs)
    • Presented at QIP 2014, combined with arXiv:1210.1199 by Stacey Jeffery, Robin Kothari, and Frédéric Magniez
59. Easy and hard functions for the Boolean hidden shift problem
    Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler
    • arXiv:1304.4642
    • Proceedings of the 8th Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics 22, 50–79 (2013)
60. A framework for bounding nonlocality of state discrimination
    Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols
    • arXiv:1206.5822
    • Communications in Mathematical Physics 323, 1121–1153 (2013)
61. Universal computation by multi-particle quantum walk
    Andrew M. Childs, David Gosset, and Zak Webb
    • arXiv:1205.3782
    • Presented at QIP 2013
    • Science 339, 791–794 (2013)
62. Levinson’s theorem for graphs II
    Andrew M. Childs and David Gosset
    • arXiv:1203.6557
    • Journal of Mathematical Physics 53, 102207 (2012)
63. Hamiltonian simulation using linear combinations of unitary operations
    Andrew M. Childs and Nathan Wiebe
    • arXiv:1202.5822
    • Quantum Information and Computation 12, 901–924 (2012)
64. The quantum query complexity of read-many formulas
    Andrew M. Childs, Shelby Kimmel, and Robin Kothari
    • arXiv:1112.0548
    • Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012), Lecture Notes in Computer Science 7501, pp. 337–348 (2012)
65. Black-box Hamiltonian simulation and unitary implementation
    Dominic W. Berry and Andrew M. Childs
    • arXiv:0910.4157
    • Presented at QIP 2010
    • Quantum Information and Computation 12, 29–62 (2012)
66. Levinson’s theorem for graphs
    Andrew M. Childs and DJ Strouse
    • arXiv:1103.5077
    • Journal of Mathematical Physics 52, 082102 (2011)
67. Quantum property testing for bounded-degree graphs
    Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu
    • arXiv:1012.3174
    • Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM 2011), Lecture Notes in Computer Science 6845, pp. 365–376 (2011)
68. Quantum query complexity of minor-closed graph properties
    Andrew M. Childs and Robin Kothari
    • arXiv:1011.1443
    • Presented at QIP 2011
    • Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics 9, pp. 661–672 (2011)
    • SIAM Journal on Computing 41, 1426–1450 (2012)
69. Simulating sparse Hamiltonians with star decompositions
    Andrew M. Childs and Robin Kothari
    • arXiv:1003.3683
    • Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), Lecture Notes in Computer Science 6519, pp. 94–103 (2011)
70. Characterization of universal two-qubit Hamiltonians
    Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols
    • arXiv:1004.1645
    • Quantum Information and Computation 11, 19–39 (2011)
71. Limitations on the simulation of non-sparse Hamiltonians
    Andrew M. Childs and Robin Kothari
    • arXiv:0908.4398
    • Quantum Information and Computation 10, 669–684 (2010)
72. The quantum query complexity of certification
    Andris Ambainis, Andrew M. Childs, François Le Gall, and Seiichiro Tani
    • arXiv:0903.1291
    • Quantum Information and Computation 10, 181–188 (2010)
73. On the relationship between continuous- and discrete-time quantum walk
    Andrew M. Childs
    • arXiv:0810.0312
    • Communications in Mathematical Physics 294, 581–603 (2010)
74. Discrete-query quantum algorithm for NAND trees
    Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
    • quant-ph/0702160
    • Theory of Computing 5, 119–123 (2009)
75. Universal computation by quantum walk
    Andrew M. Childs
    • arXiv:0806.1972
    • Presented at QIP 2009 as an invited talk
    • Physical Review Letters 102, 180501 (2009)
76. Quantum algorithms for algebraic problems
    Andrew M. Childs and Wim van Dam
    • arXiv:0812.0380
    • Reviews of Modern Physics 82, 1–52 (2010)
77. Optimal quantum adversary lower bounds for ordered search
    Andrew M. Childs and Troy Lee
    • arXiv:0708.3396
    • Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Lecture Notes in Computer Science 5125, pp. 869–880 (2008)
78. Quantum algorithms for hidden nonlinear structures
    Andrew M. Childs, Leonard J. Schulman, and Umesh V. Vazirani
    • arXiv:0705.2784
    • Presented at QIP 2007 as an invited talk
    • Proceedings of the 48th IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 395–404 (2007)
79. 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 W. Reichardt, Robert Špalek, and Shengyu Zhang
    • quant-ph/0703015
    • Presented at QIP 2008 as an invited talk (speaker: Andris Ambainis)
    • Proceedings of the 48th IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 363–372 (2007)
    • SIAM Journal on Computing 39, 2513–2530 (2010)
80. Improved quantum algorithms for the ordered search problem via semidefinite programming
    Andrew M. Childs, Andrew J. Landahl, and Pablo A. Parrilo
    • quant-ph/0608161
    • Physical Review A 75, 032335 (2007)
81. On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
    Andrew M. Childs and Pawel Wocjan
    • quant-ph/0510185
    • Quantum Information and Computation 7, 504–521 (2007)
82. Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
    Andrew M. Childs, Aram W. Harrow, and Pawel Wocjan
    • quant-ph/0609110
    • Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007), Lecture Notes in Computer Science 4393, pp. 598–609 (2007)
83. Quantum algorithm for a generalized hidden shift problem
    Andrew M. Childs and Wim van Dam
    • quant-ph/0507190
    • Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 1225–1234 (2007)
84. The limitations of nice mutually unbiased bases
    Michael Aschbacher, Andrew M. Childs, and Pawel Wocjan
    • quant-ph/0412066
    • Journal of Algebraic Combinatorics 25, 111–123 (2007)
85. Optimal measurements for the dihedral hidden subgroup problem
    Dave Bacon, Andrew M. Childs, and Wim van Dam
    • quant-ph/0501044
    • Presented at QIP 2005 as an invited talk
    • Chicago Journal of Theoretical Computer Science (2006), article 2
86. Two-way quantum communication channels
    Andrew M. Childs, Debbie W. Leung, and H.-K. Lo
    • quant-ph/0506039
    • International Journal of Quantum Information 4, 63–83 (2006)
87. Quantum algorithms for subset finding
    Andrew M. Childs and Jason M. Eisenberg
    • quant-ph/0311038
    • Quantum Information and Computation 5, 593–604 (2005)
88. 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
    • quant-ph/0504083
    • Presented at QIP 2006
    • Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 469–478 (2005)
89. Secure assisted quantum computation
    Andrew M. Childs
    • quant-ph/0111046
    • Quantum Information and Computation 5, 456–466 (2005)
90. Unified derivations of measurement-based schemes for quantum computation
    Andrew M. Childs, Debbie W. Leung, and Michael A. Nielsen
    • quant-ph/0404132
    • Physical Review A 71, 032318 (2005)
91. Spatial search and the Dirac equation
    Andrew M. Childs and Jeffrey Goldstone
    • quant-ph/0405120
    • Physical Review A 70, 042312 (2004)
92. Spatial search by quantum walk
    Andrew M. Childs and Jeffrey Goldstone
    • quant-ph/0306054
    • Physical Review A 70, 022314 (2004)
93. Reversible simulation of bipartite product Hamiltonians
    Andrew M. Childs, Debbie W. Leung, and Guifre Vidal
    • quant-ph/0303097
    • IEEE Transactions on Information Theory 50, 1189–1197 (2004)
94. Lower bounds on the complexity of simulating quantum gates
    Andrew M. Childs, Henry L. Haselgrove, and Michael A. Nielsen
    • quant-ph/0307190
    • Physical Review A 68, 052311 (2003)
95. Exponential algorithmic speedup by quantum walk
    Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman
    • quant-ph/0209131
    • Presented at QIP 2003 as an invited talk (speaker: Edward Farhi)
    • Proceedings of the 35th ACM Symposium on Theory of Computing (STOC 2003), pp. 59–68 (2003)
96. Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions
    Andrew M. Childs, Debbie W. Leung, Frank Verstraete, and Guifre Vidal
    • quant-ph/0207052
    • Quantum Information and Computation 3, 97–105 (2003)
97. Quantum search by measurement
    Andrew M. Childs, Enrico Deotto, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Andrew J. Landahl
    • quant-ph/0204013
    • Physical Review A 66, 032314 (2002)
98. Universal simulation of Hamiltonian dynamics for quantum systems with finite-dimensional state spaces
    Michael A. Nielsen, Michael J. Bremner, Jennifer L. Dodd, Andrew M. Childs, and Christopher M. Dawson
    • quant-ph/0109064
    • Physical Review A 66, 022317 (2002)
99. An example of the difference between quantum and classical random walks
    Andrew M. Childs, Edward Farhi, and Sam Gutmann
    • quant-ph/0103020
    • Quantum Information Processing 1, 35–43 (2002)
100. Finding cliques by quantum adiabatic evolution
     Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
     • quant-ph/0012104
     • Quantum Information and Computation 2, 181–191 (2002)
101. Robustness of adiabatic quantum computation
     Andrew M. Childs, Edward Farhi, and John Preskill
     • quant-ph/0108048
     • Physical Review A 65, 012322 (2001)
102. Universal simulation of Markovian quantum dynamics
     Dave Bacon, Andrew M. Childs, Isaac L. Chuang, Julia Kempe, Debbie Leung, and Xinlan Zhou
     • quant-ph/0008070
     • Physical Review A 64, 062302 (2001)
103. Realization of quantum process tomography in NMR
     Andrew M. Childs, Isaac L. Chuang, and Debbie W. Leung
     • quant-ph/0012032
     • Physical Review A 64, 012314 (2001)
104. Exact sampling from non-attractive distributions using summary states
     Andrew M. Childs, Ryan B. Patterson, and David J. C. MacKay
     • cond-mat/0005132 [pictures and animations]
     • Physical Review E 63, 036113 (2001)
105. Universal quantum computation with two-level trapped ions
     Andrew M. Childs and Isaac L. Chuang
     • quant-ph/0008065
     • Physical Review A 63, 012306 (2001)
106. Quantum information and precision measurement
     Andrew M. Childs, John Preskill, and Joseph Renes
     • quant-ph/9904021
     • Journal of Modern Optics 47, 155–176 (2000)
107. A model for MeV C_n track damage in YIG
     Thomas A. Tombrello, Andrew M. Childs, and John W. Hartman
     • Nuclear Instruments and Methods B 145, 429–433 (1998)
108. Simulation of keV clusters incident on gold targets
     Andrew M. Childs, Mark H. Shapiro, and Thomas A. Tombrello
     • Nuclear Instruments and Methods B 143, 298–305 (1998)

Commentary

1. Future of quantum computing
   Scott Aaronson, Andrew M. Childs, Edward Farhi, Aram W. Harrow, and Barry C. Sanders
   • arXiv:2506.19232
2. Quantum computing: Quantum advantage deferred
   Andrew M. Childs
   • Nature Physics 13, 1148 (2017)
3. Quantum algorithms: Equation solving by simulation
   Andrew M. Childs
   • Nature Physics 5, 861 (2009)

Thesis

• Quantum information processing in continuous time
  Andrew M. Childs
  Ph.D. thesis, Massachusetts Institute of Technology, 2004