Papers by Andrew Childs

Contents


Related links: arXiv, Google Scholar

Preprints

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