Papers by Andrew Childs

Contents


Related links: arXiv, Google Scholar

Preprints

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