Classical vs Quantum Random Walks
A classical random walk on a graph spreads as . A quantum walk evolves unitarily and spreads as β a quadratic speedup in spreading rate.
This speedup translates to algorithmic advantages for search, element distinctness, and other graph problems.
Discrete-Time Quantum Walks
A discrete-time quantum walk uses coin and position registers:
The coin operator determines direction, and the shift operator moves the walker:
The walk step alternates coin operations and shifts.
Continuous-Time Quantum Walks
A CTQW evolves according to the adjacency matrix :
The time evolution is . For the adjacency matrix:
where and are eigenvalues and eigenvectors.
Spatial Search on Graphs
Spatial search uses quantum walks to find a marked vertex:
- Prepare uniform superposition
- Phase flip the marked vertex
- Apply one step of quantum walk
- Repeat times
For the complete graph, this matches Grover's query complexity.
Quantum Walk on the Line
For a CTQW on a line, the probability distribution at time is:
where is the th Bessel function. The walker spreads linearly: , compared to for classical walks.
Graph Properties from Walks
Quantum walks can reveal:
- Gap detection: spectral gap determines mixing time
- Element distinctness: queries on Johnson graph
- Triangle finding: queries
- Graph isomorphism: polynomial speedups for certain classes
Python: Quantum Walk Simulation
import numpy as np
import scipy.linalg
def quantum_walk_line(steps=50):
N = 2 * steps + 1
center = steps
A = np.zeros((N, N), dtype=complex)
for i in range(N-1):
A[i, i+1] = 1
A[i+1, i] = 1
t = steps / 2.0
U = scipy.linalg.expm(-1j * A * t)
psi0 = np.zeros(N, dtype=complex)
psi0[center] = 1.0
psi_t = U @ psi0
probs = np.abs(psi_t)**2
positions = np.arange(N) - center
mean_sq = np.sum(positions**2 * probs)
print(f"Spread <x^2> = {mean_sq:.2f}")
return positions, probs
positions, probs = quantum_walk_line(50)
Quantum Walk Complexity
The hitting time of quantum walks:
| Graph | Classical | Quantum |
|---|---|---|
| Complete (KN) | O(N) | O(sqrtN) |
| Hypercube (Qn) | O(n 2^n) | O(n) |
| Johnson (J(N,k)) | O(N) | O(N^2/3) |
| Grid (sqrtN times sqrtN) | O(N log N) | O(N) |
Continuous-Time vs Discrete-Time
| Aspect | Discrete-Time | Continuous-Time |
|---|---|---|
| Coin space | Explicit | Implicit |
| Time evolution | W = S cdot C | U(t) = e^-iHt |
| Graph representation | Adjacency + coin | Hamiltonian |
| Applications | Spatial search | Graph algorithms |
Summary
This topic covers the fundamental concepts and applications in quantum computing. Understanding these concepts is essential for advancing in the field and applying quantum techniques to real-world problems. The mathematical framework provides the foundation for analyzing quantum algorithms and hardware implementations.
Key takeaways include the importance of quantum coherence, the role of entanglement as a resource, and the tradeoffs between different quantum computing architectures. As the field progresses from NISQ to fault-tolerant devices, these foundational concepts will continue to underpin new developments and applications.
Further study should include hands-on implementation using quantum programming frameworks, analysis of recent research papers, and exploration of the connections between quantum computing and other fields such as machine learning, optimization, and simulation.