MilestoneTheory & algorithmsConfirmed

Childs shows quantum walks can implement universal quantum computation

Jun 12, 2008

Andrew Childs proves that a quantum walk on a suitably designed graph can implement any quantum computation. Quantum gates are encoded in the graph, where a quantum particle can follow paths in superposition.

Why it matters

The proof connects quantum walks, a tool for algorithms, to the full computational power of the quantum circuit model.

Andrew Childs

See it on the timeline

Related

• A quantum walk gives an exponential speedup for a black-box problem (Sep 24, 2002)