Papers by Andrew Childs

Contents


Related links: arXiv, Google Scholar

Preprints

  1. 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
  2. Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
    Dong An, Andrew M. Childs, and Lin Lin
  3. Streaming quantum state purification
    Andrew M. Childs, Honghao Fu, Debbie Leung, Zhi Li, Maris Ozols, and Vedang Vyas
  4. Quantum divide and conquer
    Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang
  5. Quantum routing with teleportation
    Dhruv Devulapalli, Eddie Schoute, Aniruddha Bapat, Andrew M. Childs, and Alexey V. Gorshkov

Publications

  1. Quantum algorithm for estimating volumes of convex bodies
    Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu
  2. Advantages and limitations of quantum routing
    Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, and Eddie Schoute
  3. Hamiltonian simulation with random inputs
    Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs
  4. Quantum algorithms and the power of forgetting
    Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani
  5. Quantum simulation of real-space dynamics
    Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang
  6. 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
  7. Quantum algorithms for sampling log-concave distributions and estimating normalizing constants
    Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang
  8. 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
  9. 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
  10. High-precision quantum algorithms for partial differential equations
    Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander
  11. Nearly optimal time-independent reversal of a spin chain
    Aniruddha Bapat, Eddie Schoute, Alexey V. Gorshkov, and Andrew M. Childs
  12. 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
  13. Quantum routing with fast reversals
    Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, Samuel King, Eddie Schoute, and Hrishee Shastri
  14. Quantum query complexity with matrix-vector products
    Andrew M. Childs, Shih-Han Hung, and Tongyang Li
  15. Quantum exploration algorithms for multi-armed bandits
    Daochen Wang, Xuchen You, Tongyang Li, and Andrew M. Childs
  16. Theory of Trotter error with commutator scaling
    Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu
  17. Non-interactive classical verification of quantum computation
    Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung
  18. Symmetries, graph properties, and quantum speedups
    Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang
  19. Signaling and scrambling with strongly long-range interactions
    Andrew Y. Guo, Minh C. Tran, Andrew M. Childs, Alexey V. Gorshkov, and Zhe-Xuan Gong
  20. Destructive error interference in product-formula lattice simulation
    Minh C. Tran, Su-Kuan Chu, Yuan Su, Andrew M. Childs, and Alexey V. Gorshkov
  21. Time-dependent Hamiltonian simulation with L1-norm scaling
    Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe
  22. Quantum coupon collector
    Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf
  23. Quantum spectral methods for differential equations
    Andrew M. Childs and Jin-Peng Liu
  24. Quantum algorithms and lower bounds for convex optimization
    Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu
  25. Faster quantum simulation by randomization
    Andrew M. Childs, Aaron Ostrander, and Yuan Su
  26. Nearly optimal lattice simulation by product formulas
    Andrew M. Childs and Yuan Su
  27. 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
  28. Circuit transformations for quantum architectures
    Andrew M. Childs, Eddie Schoute, and Cem M. Unsal
  29. Toward the first quantum simulation with quantum speedup
    Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su
  30. Automated optimization of large quantum circuits with continuous parameters
    Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov
  31. Quantum algorithm for multivariate polynomial interpolation
    Jianxin Chen, Andrew M. Childs, and Shih-Han Hung
  32. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
    Andrew M. Childs, Robin Kothari, and Rolando D. Somma
  33. Quantum algorithm for linear differential equations with exponentially improved dependence on precision
    Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang
  34. Efficient simulation of sparse Markovian quantum dynamics
    Andrew M. Childs and Tongyang Li
  35. Optimal quantum algorithm for polynomial interpolation
    Andrew M. Childs, Wim van Dam, Shih-Han Hung, and Igor E. Shparlinski
  36. Optimal state discrimination and unstructured search in nonlinear quantum mechanics
    Andrew M. Childs and Joshua Young
  37. Complexity of the XY antiferromagnet at fixed magnetization
    Andrew M. Childs, David Gosset, and Zak Webb
  38. Hamiltonian simulation with nearly optimal dependence on all parameters
    Dominic W. Berry, Andrew M. Childs, and Robin Kothari
  39. Simulating Hamiltonian dynamics with a truncated Taylor series
    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
  40. Momentum switches
    Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, and Zak Webb
  41. Quantum computation of discrete logarithms in semigroups
    Andrew M. Childs and Gábor Ivanyos
  42. Spatial search by continuous-time quantum walks on crystal lattices
    Andrew M. Childs and Yimin Ge
  43. The Bose-Hubbard model is QMA-complete
    Andrew M. Childs, David Gosset, and Zak Webb
  44. Exponential improvement in precision for simulating sparse Hamiltonians
    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
  45. The computational power of matchgates and the XY interaction on arbitrary graphs
    Daniel J. Brod and Andrew M. Childs
  46. Interpolatability distinguishes LOCC from separable von Neumann measurements
    Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols
  47. Constructing elliptic curve isogenies in quantum subexponential time
    Andrew M. Childs, David Jao, and Vladimir Soukharev
  48. Product formulas for exponentials of commutators
    Andrew M. Childs and Nathan Wiebe
  49. A time-efficient quantum walk for 3-distinctness using nested updates
    Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
  50. Easy and hard functions for the Boolean hidden shift problem
    Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler
  51. A framework for bounding nonlocality of state discrimination
    Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols
  52. Universal computation by multi-particle quantum walk
    Andrew M. Childs, David Gosset, and Zak Webb
  53. Levinson’s theorem for graphs II
    Andrew M. Childs and David Gosset
  54. Hamiltonian simulation using linear combinations of unitary operations
    Andrew M. Childs and Nathan Wiebe
  55. The quantum query complexity of read-many formulas
    Andrew M. Childs, Shelby Kimmel, and Robin Kothari
  56. Black-box Hamiltonian simulation and unitary implementation
    Dominic W. Berry and Andrew M. Childs
  57. Levinson’s theorem for graphs
    Andrew M. Childs and DJ Strouse
  58. Quantum property testing for bounded-degree graphs
    Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu
  59. Quantum query complexity of minor-closed graph properties
    Andrew M. Childs and Robin Kothari
  60. Simulating sparse Hamiltonians with star decompositions
    Andrew M. Childs and Robin Kothari
  61. Characterization of universal two-qubit Hamiltonians
    Andrew M. Childs, Debbie Leung, Laura Mancinska, and Maris Ozols
  62. Limitations on the simulation of non-sparse Hamiltonians
    Andrew M. Childs and Robin Kothari
  63. The quantum query complexity of certification
    Andris Ambainis, Andrew M. Childs, François Le Gall, and Seiichiro Tani
  64. On the relationship between continuous- and discrete-time quantum walk
    Andrew M. Childs
  65. Discrete-query quantum algorithm for NAND trees
    Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
  66. Universal computation by quantum walk
    Andrew M. Childs
  67. Quantum algorithms for algebraic problems
    Andrew M. Childs and Wim van Dam
  68. Optimal quantum adversary lower bounds for ordered search
    Andrew M. Childs and Troy Lee
  69. Quantum algorithms for hidden nonlinear structures
    Andrew M. Childs, Leonard J. Schulman, and Umesh V. Vazirani
  70. Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer
    Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang
  71. Improved quantum algorithms for the ordered search problem via semidefinite programming
    Andrew M. Childs, Andrew J. Landahl, and Pablo A. Parrilo
  72. On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
    Andrew M. Childs and Pawel Wocjan
  73. Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
    Andrew M. Childs, Aram W. Harrow, and Pawel Wocjan
  74. Quantum algorithm for a generalized hidden shift problem
    Andrew M. Childs and Wim van Dam
  75. The limitations of nice mutually unbiased bases
    Michael Aschbacher, Andrew M. Childs, and Pawel Wocjan
  76. Optimal measurements for the dihedral hidden subgroup problem
    Dave Bacon, Andrew M. Childs, and Wim van Dam
  77. Two-way quantum communication channels
    Andrew M. Childs, Debbie W. Leung, and H.-K. Lo
  78. Quantum algorithms for subset finding
    Andrew M. Childs and Jason M. Eisenberg
  79. 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
  80. Secure assisted quantum computation
    Andrew M. Childs
  81. Unified derivations of measurement-based schemes for quantum computation
    Andrew M. Childs, Debbie W. Leung, and Michael A. Nielsen
  82. Spatial search and the Dirac equation
    Andrew M. Childs and Jeffrey Goldstone
  83. Spatial search by quantum walk
    Andrew M. Childs and Jeffrey Goldstone
  84. Reversible simulation of bipartite product Hamiltonians
    Andrew M. Childs, Debbie W. Leung, and Guifre Vidal
  85. Lower bounds on the complexity of simulating quantum gates
    Andrew M. Childs, Henry L. Haselgrove, and Michael A. Nielsen
  86. Exponential algorithmic speedup by quantum walk
    Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman
  87. Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions
    Andrew M. Childs, Debbie W. Leung, Frank Verstraete, and Guifre Vidal
  88. Quantum search by measurement
    Andrew M. Childs, Enrico Deotto, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Andrew J. Landahl
  89. 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
  90. An example of the difference between quantum and classical random walks
    Andrew M. Childs, Edward Farhi, and Sam Gutmann
  91. Finding cliques by quantum adiabatic evolution
    Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
  92. Robustness of adiabatic quantum computation
    Andrew M. Childs, Edward Farhi, and John Preskill
  93. Universal simulation of Markovian quantum dynamics
    Dave Bacon, Andrew M. Childs, Isaac L. Chuang, Julia Kempe, Debbie Leung, and Xinlan Zhou
  94. Realization of quantum process tomography in NMR
    Andrew M. Childs, Isaac L. Chuang, and Debbie W. Leung
  95. Exact sampling from non-attractive distributions using summary states
    Andrew M. Childs, Ryan B. Patterson, and David J. C. MacKay
  96. Universal quantum computation with two-level trapped ions
    Andrew M. Childs and Isaac L. Chuang
  97. Quantum information and precision measurement
    Andrew M. Childs, John Preskill, and Joseph Renes
  98. A model for MeV Cn track damage in YIG
    Thomas A. Tombrello, Andrew M. Childs, and John W. Hartman
  99. Simulation of keV clusters incident on gold targets
    Andrew M. Childs, Mark H. Shapiro, and Thomas A. Tombrello

Commentary

  1. Quantum computing: Quantum advantage deferred
    Andrew M. Childs
  2. Andrew M. Childs

Thesis