Skip to content

Tutorial 02 Quantum Walk

Jump to bottom
Mohammadreza Khellat edited this page Dec 16, 2025 · 1 revision

Tutorial 02: Discrete-Time Quantum Walk

Quantum walk operator for a path graph with 16 nodes ($P_{16}$) using coin and shift operators.

Overview

This tutorial implements quantum walk operators on graphs using coin and shift operators for a path graph with 16 nodes. You'll learn how quantum walks can be used for graph-based algorithms and understand the relationship between classical and quantum random walks.

Location: quantum_walk/
Notebook: quantum_walk_discrete_time_line_16nodes.ipynb
Framework: Classiq
Difficulty: 🟡 Intermediate
Estimated Time: 2-3 hours

Learning Objectives

By completing this tutorial, you will be able to:

  1. Understand quantum walk operators (coin operator $C$ and shift operator $S$)
  2. Implement quantum walks on path graphs
  3. Design diffuser operations for quantum walks
  4. Create edge oracles to check graph connectivity
  5. Recognize applications of quantum walks in graph algorithms

Prerequisites

Required Knowledge

  • Tutorial 00 (QFT): Understanding of quantum Fourier transform concepts

  • Graph Theory:

    • Vertices, edges, and adjacency
    • Path graphs ($P_n$)
    • Graph connectivity

  • Quantum Circuits:

    • Quantum gates and operations
    • Controlled operations
    • Quantum state manipulation

Recommended Background

  • Quantum Algorithms: Familiarity with quantum algorithm design
  • Classiq Framework: Experience with Classiq (helpful but tutorial is self-contained)
  • Random Walks: Understanding of classical random walks (for comparison)

Prior Tutorials

  • Required: Tutorial 00 (Quantum Fourier Transform) or equivalent knowledge
  • Related to: Tutorial 03 (advanced quantum operations)

Theory

Quantum Walks

Quantum walks are quantum analogs of classical random walks:

  • Classical Random Walk: Probabilistic movement on a graph
  • Quantum Walk: Quantum superposition allows exploring multiple paths simultaneously
  • Applications: Graph search, optimization, simulation

Discrete-Time Quantum Walk

The quantum walk operator $W$ is composed of two operators:

  1. Coin Operator ($C$): Determines the direction of movement
  2. Shift Operator ($S$): Moves the walker along edges

The full walk operator is: $W = S \cdot C$

Implementation Details

Coin Operator ($C$)

The diffuser part of the $C$ operator is deployed using zero_diffuzer(x: QNum). For the full $C$:

  • Control the operation using the first register
  • Iterate through all vertices
  • Implemented in W_iteration(i: int, vertices: QNum, adjacent_vertices: QNum)

Shift Operator ($S$)

The shift operator requires:

  • Edge Oracle: Check if two vertices are connected using edge_oracle(res: Output[QBit], vertices: QNum, adjacent_vertices: QNum)
  • Bit-wise Swap: Apply swap on all connected vertices in S_operator(vertices: QNum, adjacent_vertices: QNum)

Path Graph $P_{16}$

  • Structure: Linear graph with 16 nodes connected in a path
  • Properties: Each node (except endpoints) has degree 2
  • Quantum Walk: Demonstrates quantum walk behavior on this simple structure

Implementation

High-Level Approach

The implementation consists of several key components:

  1. Zero Diffuser: Core component of the coin operator
  2. W Iteration: Applies the coin operator with proper controls
  3. Edge Oracle: Checks connectivity between vertices
  4. S Operator: Implements the shift operation
  5. Main Walk: Combines coin and shift operators

Key Functions

  • zero_diffuzer(x: QNum) - Diffuser for coin operator
  • W_iteration(i: int, vertices: QNum, adjacent_vertices: QNum) - Full coin operator
  • edge_oracle(res: Output[QBit], vertices: QNum, adjacent_vertices: QNum) - Connectivity check
  • S_operator(vertices: QNum, adjacent_vertices: QNum) - Shift operator

Software Architecture

The notebook uses Classiq to:

  • Define quantum functions for walk operators
  • Synthesize optimized quantum circuits
  • Execute and analyze quantum walk behavior

Software Requirements

The following Python packages are required:

  • numpy - Numerical operations
  • classiq - Quantum circuit design and synthesis

Installation:

All packages are included in the top-level requirements.txt. If you have set up the base environment as described in the main README, no additional installation is needed.

# If not already installed
pip install numpy classiq

Running the Tutorial

Step 1: Navigate to the Tutorial Directory

cd quantum_walk

Step 2: Open the Notebook

jupyter notebook quantum_walk_discrete_time_line_16nodes.ipynb

Or in JupyterLab:

jupyter lab quantum_walk_discrete_time_line_16nodes.ipynb

Step 3: Execute the Notebook

  1. Review the theory - Understand quantum walk operators
  2. Examine the implementation - See how coin and shift operators work
  3. Run the quantum walk - Execute on $P_{16}$
  4. Analyze results - Observe quantum walk behavior

Step 4: Experiment (Optional)

  • Try different graph structures
  • Modify the coin operator
  • Experiment with different initial states
  • Compare with classical random walks

Expected Results

Outputs

  1. Quantum Walk Implementation:

    • Working coin and shift operators
    • Quantum walk on $P_{16}$ path graph
    • Measurement results showing walk behavior

  2. Understanding:

    • How quantum walks differ from classical random walks
    • Coin and shift operator design
    • Applications in graph algorithms

Key Takeaways

  • Quantum walks enable efficient graph exploration
  • Coin and shift operators are fundamental components
  • Quantum walks can provide speedups over classical approaches
  • Classiq simplifies complex quantum algorithm design

Troubleshooting

Issue: Classiq Import Errors

Solution:

  • Ensure Classiq is installed: pip install classiq
  • Check Classiq version compatibility
  • Some features may require API authentication

Issue: Understanding the Operators

Solution:

  • Review Tutorial 00 (QFT) for foundational concepts
  • Study the theory section carefully
  • Refer to quantum walk papers in 6.B/ directory
  • See Academic Resources

Issue: Circuit Complexity

Solution:

  • Start with smaller graphs for understanding
  • Review the implementation step by step
  • Check Classiq documentation for optimization options

Issue: Results Interpretation

Solution:

  • Compare with classical random walk behavior
  • Review quantum walk literature
  • Understand measurement statistics

Further Reading

Related Papers

See the 6.B/ directory for related papers:

  • (J. Watrous-1998) - Quantum simulations of classical random walks and undirected graph connectivity
  • (X. Qiang et al.-2024) - Review on Quantum Walk Computing Theory, Implementation, and Application

Related Tutorials

  • Tutorial 00 - Quantum Fourier Transform: Foundational concepts used here
  • Tutorial 03 - Non-Unitary Computing: Advanced quantum operations
  • Tutorial 05 - Coupled Harmonic Oscillators: More complex quantum algorithms

External Resources

Advanced Examples

  • See 6.B/advanced design/quantum_walk_circle_example.py for additional examples

Contributors

  • Mohammadreza Khellat - Primary author and maintainer

For questions or contributions, see the Contributing Guide.

Summary

This tutorial demonstrates quantum walks on graphs. You've learned:

✅ How to implement coin and shift operators
✅ How to design quantum walks on path graphs
✅ How to use edge oracles for connectivity
✅ Applications of quantum walks in graph algorithms

Next Steps:

  • Explore quantum walks on different graph structures
  • Try Tutorial 03 for advanced non-unitary operations
  • Review quantum walk papers in 6.B/ directory
  • Experiment with different coin operators

Return to: Tutorial Catalog | Home

Clone this wiki locally