Quantum Walks: A Tool for Benchmarking Quantum Computers

As part of my undergraduate thesis, I've been exploring how quantum walks can be used to benchmark real quantum hardware. In this post, I'll explain what quantum walks are and why they're useful for evaluating quantum computers.

What is a Quantum Walk?

A quantum walk is the quantum mechanical analog of a classical random walk. While a classical random walk involves a particle moving randomly left or right with equal probability, a quantum walk exploits superposition and interference to spread across multiple positions simultaneously.

This fundamental difference leads to a quadratically faster spreading compared to classical walks — a property known as quantum speedup.

Why Use Quantum Walks for Benchmarking?

Quantum walks are excellent benchmarks because they are sensitive to errors in quantum hardware. The interference patterns that emerge depend critically on the coherence and gate fidelity of the quantum processor. Any noise or decoherence will distort the expected probability distribution.

This makes them ideal for comparing different quantum computers — in my case, IBM's ibm_brisbane, ibm_kyoto, and ibm_sherbrooke.

Types of Quantum Walks

There are two main types of quantum walks:

Discrete-time quantum walks use a "coin" operator (typically a Hadamard gate) to determine the direction of movement, followed by a conditional shift operator. This is analogous to flipping a coin in a classical random walk.

Continuous-time quantum walks evolve according to a Hamiltonian, typically derived from the adjacency matrix of a graph. The evolution is implemented using Trotter decomposition on real hardware.

Key Metrics for Benchmarking

In my thesis, I track several metrics to evaluate quantum computer performance:

Spread variance measures how far the quantum walker spreads from its initial position. Higher variance indicates better quantum behavior.

Position entropy quantifies the uniformity of the probability distribution across positions.

Quantum advantage compares the quantum walk's spreading to what a classical random walk would achieve.

Optimizing for Real Hardware

Real quantum computers have constraints — limited connectivity between qubits, varying error rates, and specific topologies. Part of my work involves optimizing quantum walk circuits for specific IBM hardware using techniques like:

Topology-aware transpilation maps logical qubits to physical qubits in a way that minimizes the need for SWAP gates.

Circuit depth minimization reduces the number of sequential operations, decreasing exposure to decoherence.

Error mitigation applies post-processing techniques to reduce the impact of noise on results.

What's Next?

In upcoming posts, I'll share specific results from running quantum walks on IBM hardware, including comparisons between different processors and analysis of how circuit optimization affects benchmark results.

If you're interested in quantum computing or have questions about quantum walks, feel free to reach out!