Childs develops quantum algorithms based on walks and simulation, showing how quantum dynamics can produce provable computational advantages and even implement universal quantum computation.
University of MarylandarXiv / ACM STOCarXiv / Physical Review LettersChilds’s research treats quantum evolution as an algorithm-design resource. His collaborative quantum-walk result constructed a black-box problem with an exponential separation from classical computation, providing a different mechanism from familiar Fourier-transform algorithms. His later universality result showed that suitably designed graphs can encode arbitrary quantum computation in a walk. Together, these works explain both why quantum dynamics can be useful and how expressive a simple-looking model can become. Their importance lies in explicit constructions and resource analysis, rather than an assertion that ordinary random walks or every physical system deliver an advantage.
University of MarylandarXiv / ACM STOCarXiv / Physical Review LettersThe work behind the recognition
Work, in context- 2003
A quantum-walk exponential separation
Childs and five coauthors constructed a graph-traversal problem in an oracle model that a continuous-time quantum walk solves exponentially faster than classical algorithms can. The model and input-access assumptions are essential to interpreting this theoretical speedup.
Coauthored theoretical result by Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann and Daniel A. Spielman.
Source-supported recordarXiv / ACM STOC - 2009
Showing quantum walks can be universal
Childs proved that universal quantum computation can be implemented through a walk on a suitably constructed low-degree graph. Quantum gates are encoded through scattering, showing that a constrained dynamical model can still express general quantum computation.
Sole-author universality theorem by Andrew M. Childs.
Source-supported recordarXiv / Physical Review Letters
The evidence map
Both views link each contribution to its sources. Choose a contribution on the map or read them all in the list.
A quantum-walk exponential separation
Exponential algorithmic speedup by quantum walk
Supports: Childs and collaborators; oracle-model separation; preprint 2002, STOC publication 2003.
Published 2003 · Checked 19 Sept 2026Credit & limits: Coauthored theoretical result by Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann and Daniel A. Spielman.
Read the full contribution| Contribution | Evidence & what it supports | Credit & limits |
|---|---|---|
| A quantum-walk exponential separation2003 | Primary paperExponential algorithmic speedup by quantum walk Childs and collaborators; oracle-model separation; preprint 2002, STOC publication 2003. Published 2003 · Checked 19 Sept 2026 | Coauthored theoretical result by Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann and Daniel A. Spielman. |
| Showing quantum walks can be universal2009 | Primary paperUniversal computation by quantum walk Childs authorship and universal construction; 2008 preprint, 2009 journal publication. Published 2009 · Checked 19 Sept 2026 | Sole-author universality theorem by Andrew M. Childs. |
Follow the evidence
3 sourcesPrimary papers, institutional records and attributed announcements. Each source supports the claims linked above.
- University of MarylandInstitutional record
Andrew M. Childs
Current CS/UMIACS professorship, QuICS affiliation and research interests.
Checked 19 Sept 2026 - arXiv / ACM STOCPrimary paper
Exponential algorithmic speedup by quantum walk
Childs and collaborators; oracle-model separation; preprint 2002, STOC publication 2003.
Published 2003 · Checked 19 Sept 2026 - arXiv / Physical Review LettersPrimary paper
Universal computation by quantum walk
Childs authorship and universal construction; 2008 preprint, 2009 journal publication.
Published 2009 · Checked 19 Sept 2026