Papers by Andrew Childs

Contents


Related links: arXiv, Google Scholar

Preprints

  1. 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
  2. Hamiltonian simulation with random inputs
    Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs
  3. 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
  4. Quantum algorithm for estimating volumes of convex bodies
    Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu

Publications

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