Academy K

Quantum Walk on a Graph

HardConceptualquantum walkgraph algorithmsspeedup

Related module: Search and amplitude amplification

Problem statement

A discrete-time quantum walk on a graph uses a coin operator and shift operator.

  1. Define the coin and shift operators for a walk on a line.
  2. How does quantum walk spreading differ from classical random walk?
  3. What algorithmic speedups can quantum walks provide?

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.