Quantum Walks

Table of Contents

1. Introduction
2. Classical Random Walks Overview
3. Motivation for Quantum Walks
4. What Are Quantum Walks?
5. Discrete-Time vs Continuous-Time Quantum Walks
6. Mathematical Framework
7. Coined Quantum Walks
8. Quantum Coin Operators
9. Shift (Step) Operators
10. Unitary Evolution in Quantum Walks
11. Hilbert Space Structure
12. Evolution Operator Formulation
13. Example: Walk on a Line
14. Probability Distribution Differences
15. Speedup in Quantum Walks
16. Continuous-Time Quantum Walks
17. Hamiltonian Formulation
18. Adjacency and Laplacian Matrices
19. Graph Traversal via Quantum Walks
20. Search Algorithms with Quantum Walks
21. Quantum Walks on Graphs (Hypercube, Cycles)
22. Spatial Search with Quantum Walks
23. Quantum Walks and Element Distinctness
24. Quantum Walk-Based Algorithms
25. Conclusion

1. Introduction

Quantum walks are the quantum counterparts of classical random walks. They form the basis of several powerful quantum algorithms, including search, graph traversal, and simulation techniques.

2. Classical Random Walks Overview

A classical random walk is a stochastic process where a particle moves randomly between connected nodes (e.g., steps on a line or graph). The resulting probability distribution spreads diffusively over time.

3. Motivation for Quantum Walks

Quantum walks exploit quantum superposition and interference, enabling:

• Faster spread than classical walks
• Quantum algorithmic speedups
• Structured exploration of graph-based problems

4. What Are Quantum Walks?

Quantum walks involve the evolution of quantum states over a graph or lattice, governed by unitary (reversible) dynamics, rather than probabilistic rules.

5. Discrete-Time vs Continuous-Time Quantum Walks

• Discrete-Time (DTQW): Evolves in steps using coin and shift operations
• Continuous-Time (CTQW): Evolves continuously under a Hamiltonian derived from the graph

6. Mathematical Framework

Quantum walks are modeled over a Hilbert space formed by:

• Position space (node or vertex)
• Coin space (direction of movement)

For DTQW: \( \mathcal{H} = \mathcal{H}_C \otimes \mathcal{H}_P \)

7. Coined Quantum Walks

In DTQW, each step involves:

1. Applying a coin operator (Hadamard or Grover coin)
2. Conditional shift based on coin outcome

\[
U = S \cdot (C \otimes I)
\]

8. Quantum Coin Operators

Typical coin operators:

• Hadamard Coin:
  \[
  H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \ 1 & -1 \end{bmatrix}
  \]
• Grover Coin:
  \[
  G = \frac{2}{d}J – I
  \]
  for \( d \)-dimensional coin space

9. Shift (Step) Operators

Conditional shifts move the walker left or right:

\[
S|c\rangle|x\rangle = |c\rangle|x + (-1)^c\rangle
\]

Moves depend on the coin state.

10. Unitary Evolution in Quantum Walks

The full evolution operator:

\[
U = S (C \otimes I)
\]

Repeated application gives:

\[
|\psi(t)\rangle = U^t |\psi(0)\rangle
\]

11. Hilbert Space Structure

• Position register: encodes the node or lattice site
• Coin register: encodes direction/move choice
• Total system lives in \( \mathbb{C}^{d} \otimes \mathbb{C}^{n} \)

12. Evolution Operator Formulation

For each step, apply:

1. Coin toss: \( C \)
2. Conditional movement: \( S \)

Overall evolution remains unitary and reversible.

13. Example: Walk on a Line

Starting at \( x=0 \), coin = \( |0\rangle \), after \( t \) steps:

• The position distribution exhibits ballistic spread
• Peaks appear due to quantum interference

14. Probability Distribution Differences

• Classical walk: Gaussian spread, standard deviation \( \sigma \sim \sqrt{t} \)
• Quantum walk: Faster spread, \( \sigma \sim t \)

This difference leads to speedups in various algorithms.

15. Speedup in Quantum Walks

Quantum walks achieve:

• \( \mathcal{O}(\sqrt{N}) \) spatial search vs \( \mathcal{O}(N) \) classical
• Exponential speedup in some decision problems (e.g., element distinctness)

16. Continuous-Time Quantum Walks

CTQW evolves using Schrödinger-like equation:

\[
i \frac{d}{dt}|\psi(t)\rangle = H |\psi(t)\rangle
\]

where \( H \) is the graph Hamiltonian.

17. Hamiltonian Formulation

For graph \( G \) with adjacency matrix \( A \), use:

\[
H = \gamma A
\]

or

\[
H = \gamma L
\]

where \( L \) is the Laplacian, \( \gamma \) is a rate constant.

18. Adjacency and Laplacian Matrices

• Adjacency Matrix \( A \): \( A_{ij} = 1 \) if edge exists
• Laplacian Matrix \( L = D – A \): \( D \) is the degree matrix

These govern the quantum walk’s evolution.

19. Graph Traversal via Quantum Walks

Quantum walks can traverse:

• Grids
• Hypercubes
• Cycles
• Arbitrary graphs with proper Hamiltonian encoding

20. Search Algorithms with Quantum Walks

Using walks on graphs, one can perform search:

• Mark a target node
• Evolve under walk dynamics
• Measure to detect presence

21. Quantum Walks on Graphs (Hypercube, Cycles)

• Hypercube: Search in \( \mathcal{O}(\sqrt{N}) \)
• Cycles: Periodic behavior useful in structured problems

22. Spatial Search with Quantum Walks

Find a marked node using walk dynamics:

• Use reflection or potential wells
• Measure after optimal evolution time

23. Quantum Walks and Element Distinctness

Ambainis’ algorithm uses quantum walks on the Johnson graph to solve the element distinctness problem in:

\[
\mathcal{O}(N^{2/3})
\]

compared to \( \mathcal{O}(N) \) classically.

24. Quantum Walk-Based Algorithms

• Search on graphs
• NAND tree evaluation
• Element distinctness
• Learning graph frameworks
• Quantum PageRank models

25. Conclusion

Quantum walks provide a unifying framework for exploring the power of quantum algorithms in both discrete and continuous domains. They form the basis for search, graph algorithms, and simulations that outperform classical counterparts, opening new directions in quantum algorithm design and quantum information processing.