Papers by Andrew Childs

Contents


Related links: arXiv, Google Scholar

Preprints

  1. Advantages and limitations of quantum routing
    Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, and Eddie Schoute
  2. Quantum routing with teleportation
    Dhruv Devulapalli, Eddie Schoute, Aniruddha Bapat, Andrew M. Childs, and Alexey V. Gorshkov
  3. Quantum simulation of real-space dynamics
    Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang
  4. 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
  5. Hamiltonian simulation with random inputs
    Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs
  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 algorithm for estimating volumes of convex bodies
    Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu

Publications

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