Algorithms
Quantum Walk
The quantum analog of a classical random walk, used as the basis for several search and optimization algorithms.
Definition
A quantum walk is the quantum mechanical counterpart to a classical random walk — a process of moving step-by-step through a graph or network — but exploiting superposition and interference to spread probability differently than classical randomness allows.
In depth
A quantum walk is the quantum counterpart of a random walk. A classical walker takes a random step at each tick, and after t steps is typically about the square root of t away from the start. A quantum walker is in a superposition of positions, and the amplitudes for different paths interfere. For a walk on a line with a Hadamard coin, the probability spreads outward linearly with time instead of with the square root, so the walker covers distance quadratically faster, with probability peaks near the edges.
There are two main versions. A discrete-time quantum walk uses an extra coin qubit that sets the direction, with alternating steps of flipping the coin and moving the walker according to it. A continuous-time quantum walk skips the coin, and the state evolves under a Hamiltonian built from the graph's adjacency matrix. Both can be used as algorithmic frameworks. Quantum walks give an exponential speedup on a specific problem of traversing glued binary trees, quadratic speedups for searching and element distinctness, and, as shown by Childs in 2009, universal quantum computation, so any quantum circuit can be rewritten as a walk.
Quantum walks have been demonstrated in many platforms. Experiments have used photons in waveguide arrays and fibers, trapped ions, neutral atoms in optical lattices, nuclear magnetic resonance, and superconducting qubits, including a two-dimensional walk of two interacting particles on a 12-qubit device in 2019. They are also used as models for energy transport, and some proposals link them to graph isomorphism and ranking algorithms, though practical advantages in those areas are unproven.
Technical Definition
Quantum walks come in discrete-time and continuous-time variants, and have been shown to provide quadratic or, in some structured cases, exponential speedups over classical random walks for specific graph traversal and search problems.
Visual Explanation: An Analogy
Think of a classical random walk like a single confused tourist randomly picking a direction at every intersection, whereas a quantum walk is more like that tourist existing in superposition across multiple paths simultaneously, with interference between the paths shaping where they're more or less likely to end up.
Key facts
| Item | Detail |
|---|---|
| Spreading | Distance grows linearly with time, versus the square root for classical random walks |
| Versions | Discrete-time (with a coin) and continuous-time (Hamiltonian-based) |
| Exponential speedup | Glued trees problem (Childs et al., 2003) |
| Quadratic speedups | Spatial search and element distinctness |
| Universality | Quantum walks can simulate any quantum circuit (Childs, 2009) |
Where the idea comes from
Aharonov, Davidovich, and Zagury introduced discrete quantum walks in 1993, Farhi and Gutmann introduced continuous-time walks in 1998, and the algorithmic uses developed through the 2000s.
Real-World Use Cases
- The basis for quantum walk search algorithms, an alternative to Grover's Algorithm for certain structured search problems
- Used in some proposed approaches to the graph isomorphism problem
How it differs from related ideas
- A classical random walk spreads diffusively, and a quantum walk spreads ballistically.
- Discrete-time quantum walks need a coin space, and continuous-time ones do not.
- Quantum walks are a framework for algorithms, and Grover search can be viewed as a quantum walk.
Frequently asked questions
What is a quantum walk?
A quantum version of a random walk in which a walker moves in superposition and its paths interfere, so it spreads faster than a classical walker.
What are quantum walks used for?
Search, graph problems, element distinctness, a proven exponential speedup on a glued-trees problem, and as a universal model of quantum computation.
Have quantum walks been built in the lab?
Yes, on photons, ions, atoms, and superconducting qubits.
Related Terms
Keep exploring
- Algorithm: Quantum Walk Algorithms
- Algorithm: Quantum Walk Approaches to Graph Isomorphism
- Algorithm: Quantum PageRank
- Algorithm: Grover's Algorithm
- Hardware: IBM Heron (r1, r2, and r3)