About

Andrew M. Childs is a Professor in the Department of Computer Science and the Institute for Advanced Computer Studies at the University of Maryland. He is also a Fellow at the Joint Center for Quantum Information and Computer Science (QuICS) and serves as the Director of the NSF Quantum Leap Challenge Institute for Robust Quantum Simulation. His research focuses on understanding the power of quantum systems to process information, with particular interests in quantum algorithms. This includes areas such as quantum simulation, quantum query complexity, quantum walks, and quantum algorithms for algebraic problems. Professor Childs is actively involved in teaching courses related to quantum information processing and the design and analysis of computer algorithms. He also contributes to the academic community through service roles such as program committee memberships and editorial board positions.

Research topics

• Quantum mechanics
• Applied mathematics
• Mathematics
• Physics

Selected publications

• Future of quantum computing

  Quantum Machine Intelligence · 2026-01-20

  articleOpen access
  PublisherOA PDFDOI

• Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation

  SIAM Journal on Computing · 2026-03-17

  article
  PublisherDOI

• Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

  ACM Transactions on Quantum Computing · 2026-03-12 · 1 citations

  articleOpen access

  Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses \(\lceil \log _{2}{n}\rceil\) queries for a list of length n . Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of \(\log _{2}{n}\) for exact quantum algorithms is only known to lie between \((\ln {2})/\pi \approx 0.221\) and \(4/\log _{2}{605} \approx 0.433\) . We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any bounded-error, k -query quantum algorithm for ordered search can be implemented by a k -query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses \(5 \log _{7265}{n} \approx 0.390 \log _{2}{n}\) quantum queries.

  PublisherDOI

• Time Independence Does Not Limit Information Flow. II. The Case with Ancillas

  ArXiv.org · 2025-05-23

  preprintOpen accessSenior author

  While the impact of locality restrictions on quantum dynamics and algorithmic complexity has been well studied in the general case of time-dependent Hamiltonians, the capabilities of time-independent protocols are less well understood. Using clock constructions, we show that the light cone for time-independent Hamiltonians, as captured by Lieb-Robinson bounds, is the same as that for time-dependent systems when local ancillas are allowed. More specifically, we develop time-independent protocols for approximate quantum state transfer with the same run-times as their corresponding time-dependent protocols. Given any piecewise-continuous Hamiltonian, our construction gives a time-independent Hamiltonian that implements its dynamics in the same time, up to error $\varepsilon$, at the cost of introducing a number of local ancilla qubits for each data qubit that is polylogarithmic in the number of qubits, the norm of the Hamiltonian and its derivative (if it exists), the run time, and $1/\varepsilon$. We apply this construction to state transfer for systems with power-law-decaying interactions and one-dimensional nearest-neighbor systems with disordered interaction strengths. In both cases, this gives time-independent protocols with the same optimal light-cone-saturating run-times as their time-dependent counterparts.

  PublisherOA PDFDOI

• Streaming quantum state purification

  Quantum · 2025-01-21 · 8 citations

  articleOpen access1st authorCorresponding

  Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.

  PublisherOA PDFDOI

• Quantum Algorithm for Linear Non-unitary Dynamics with Near-Optimal Dependence on All Parameters

  Communications in Mathematical Physics · 2025-12-08 · 5 citations

  articleOpen access

  Abstract We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.

  PublisherOA PDFDOI

• Entanglement accelerates quantum simulation

  Nature Physics · 2025-07-14 · 12 citations

  articleSenior authorCorresponding
  PublisherDOI

• Low-depth fermion routing without ancillas

  ArXiv.org · 2025-10-06

  preprintOpen access

  Routing is the task of permuting qubits in such a way that quantum operations can be parallelized maximally, given constraints on the hardware geometry. When simulating fermions in the Jordan-Wigner encoding with qubits, a one-dimensional nearest-neighbor-connected geometry is effectively imposed on the system, independently of the underlying hardware, which means that naively, an $O(N)$ depth routing overhead is incurred. Recently, Maskara et al. [arXiv:2509.08898] demonstrated that this routing overhead can be reduced to $O(\log N)$ by decomposing general fermion routing into $O(\log N)$ interleave permutations of depth $O(1)$, using $Θ(N)$ ancillary qubits and employing measurements and feedforward. Here, we exhibit an alternative construction that achieves the same asymptotic performance. We also generalize the result in two ways. Firstly, we show that fermion routing can be performed in depth $O(\log^2 N)$ \emph{without} ancillas, measurements, or feedforward. Secondly, we construct efficient mappings with $O(\log^2 N)$ depth between all product-preserving ternary tree fermionic encodings, thereby showing that fermion routing in any such encoding can be done efficiently. While these results assume all-to-all connectivity, they also imply upper bounds for fermion routing in devices with limited connectivity by multiplying the fermion routing depth by the worst-case qubit routing depth.

  PublisherOA PDFDOI

• Toward a 2D Local Implementation of Quantum Low-Density Parity-Check Codes

  PRX Quantum · 2025-01-09 · 25 citations

  articleOpen access

  Geometric locality is an important theoretical and practical factor for quantum low-density parity-check (qLDPC) codes that affects code performance and ease of physical realization. For device architectures restricted to two-dimensional (2D) local gates, naively implementing the high-rate codes suitable for low-overhead fault-tolerant quantum computing incurs prohibitive overhead. In this work, we present an error-correction protocol built on a bilayer architecture that aims to reduce operational overheads when restricted to 2D local gates by measuring some generators less frequently than others. We investigate the family of bivariate-bicycle qLDPC codes and show that they are well suited for a parallel syndrome-measurement scheme using fast routing with local operations and classical communication (LOCC). Through circuit-level simulations, we find that in some parameter regimes, bivariate-bicycle codes implemented with this protocol have logical error rates comparable to the surface code while using fewer physical qubits.

  PublisherDOI

• Quantum Divide and Conquer

  ACM Transactions on Quantum Computing · 2025-03-17 · 3 citations

  articleOpen access1st authorCorresponding

  The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size n into smaller subproblems (say, a copies of size \(n/b\) each), along with some auxiliary work of cost \(C^{\mathrm{aux}}(n)\) , to give a recurrence relation \(\begin{equation*} C(n) \le a \, C(n/b) + C^{\mathrm{aux}}(n) \end{equation*}\) for the classical complexity \(C(n)\) . We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation \(\begin{equation*} C_Q(n) \le \sqrt {a} \, C_Q(n/b) + O(C^{\mathrm{aux}}_Q(n)) \end{equation*}\) that characterizes the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing the regular language \(\Sigma ^* 2 0^* 2 \Sigma ^*\) over the alphabet \(\Sigma = \lbrace 0,1,2\rbrace\) ; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.

  PublisherDOI

Recent grants

• QLCI-CI: NSF Quantum Leap Challenge Institute for Robust Quantum Simulation

  NSF · $27.5M · 2021–2027

• CCF: AF: Small: Simulating Hamiltonian dynamics: Algorithms and applications

  NSF · $500k · 2015–2018

• AF: Small: Toward Applications and Verification of Early Quantum Computers

  NSF · $508k · 2018–2022

Frequent coauthors

• Alexey V. Gorshkov

  62 shared

• Yuan Su

  Zhejiang University

  41 shared

• Robin Kothari

  37 shared

• Aniruddha Bapat

  The University of Tokyo

  33 shared

• Minh C. Tran

  31 shared

• Eddie Schoute

  27 shared

• Debbie Leung

  25 shared

• Tongyang Li

  25 shared

Labs

• CLIP LabPI

Education

• Ph.D., Physics

  Massachusetts Institute of Technology

  2004

• B.S., Physics

  California Institute of Technology

  2000

Awards & honors

• 2024 UMD Kirwan Faculty Research and Scholarship Prize
• 2014 Fellow Canadian Institute for Advanced Research