⚛️ quantum physics

A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications

This paper introduces a novel lackadaisical alternating quantum walk (LAQW) algorithm with reduced circuit depth suitable for NISQ devices, demonstrating its effectiveness as a quantum entropy source for generating reproducible 128-bit cryptographic keys under simulated noise.

Original authors: Natalie Gibson, Niklas Keckman, Andrea Marchesin, Matti Raasakka, Ilkka Tittonen

Published 2026-04-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Natalie Gibson, Niklas Keckman, Andrea Marchesin, Matti Raasakka, Ilkka Tittonen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a secret code that is so complex, even the most powerful supercomputers of today would struggle to crack it. To do this, you need a source of pure, unpredictable chaos.

This paper introduces a new, smarter way to generate that chaos using a Quantum Walk.

Here is the story of how the researchers did it, explained without the heavy math.

1. The Problem: The "Tired" Walker

Think of a quantum walk like a drunk person (the "walker") trying to find their way through a giant city grid (the lattice).

The Old Way (CAQW): In previous methods, this walker was very strict. At every intersection, they had to decide: "Go Left" or "Go Right." They couldn't stay put. To map out a large city, this walker had to take a huge number of steps, and the instructions for the path were incredibly long and complicated.
The Hardware Issue: Today's quantum computers are like "Noisy Intermediate-Scale Quantum" (NISQ) devices. They are like fragile glass houses; if you give them too many instructions (a deep circuit), they get confused, make mistakes, and the result becomes garbage. The old "strict walker" method required too many instructions for current computers to handle reliably.

2. The Solution: The "Lackadaisical" Walker

The authors introduced a new character: the Lackadaisical Alternating Quantum Walk (LAQW).

Imagine the same drunk walker in the city, but this time, they are lazy.

The Magic Trick: At every intersection, this lazy walker has three choices: Go Left, Go Right, or just stand there and take a nap.
Why this helps: Because the walker can stay put, the math behind their movement becomes much simpler. It's like switching from a complex, winding maze to a straight highway.
The Result: The researchers proved that this lazy walker needs 88% fewer instructions (circuit depth) to cover the same ground. This makes it possible to run the algorithm on today's noisy quantum computers without them breaking down.

3. The Application: Making a Secret Key

Why do we want a lazy quantum walker? To make a Secret Key for encryption.

Here is how they turn the walker's nap into a password:

The Setup: You give the walker a secret starting point (like a specific street corner) and a secret "mood" (parameters that decide how likely they are to move or nap).
The Walk: You let the walker run for a while. Because quantum mechanics is chaotic, a tiny change in the starting mood creates a completely different path.
The Snapshot: You take a photo of where the walker ended up. You do this millions of times to build a map of probabilities (a "heat map" of where the walker likes to hang out).
The Translation: This heat map isn't a password yet. The researchers use a clever "translator" (a prime-modulus mapping) to turn those heat map numbers into a long string of 0s and 1s (a bitstring).
The Final Key: They clean up this string to ensure it's perfectly random, resulting in a 128-bit secret key (like the kind used to protect your bank account).

4. The Proof: Does it Work?

The team tested their new "Lazy Walker" against the old "Strict Walker" using a simulator of a real IBM quantum computer.

Speed & Efficiency: The Lazy Walker was significantly faster and required much less "brainpower" from the computer.
Reproducibility: This is the most important part. If you and I both use the exact same secret starting mood, we must get the exact same secret key. The paper shows that even with the "noise" of real quantum hardware, the Lazy Walker produces the same key every time (with a tiny, fixable error rate).
Randomness: They ran the keys through a battery of standard tests (like the NIST tests) to see if they were truly random. The Lazy Walker passed with flying colors, proving the keys are unpredictable and secure.

The Big Picture Analogy

Imagine you are trying to paint a masterpiece using a shaky hand (the noisy quantum computer).

The Old Method: You tried to paint a detailed, complex landscape with a tiny, stiff brush. You had to make thousands of tiny, precise strokes. Your hand shook too much, and the painting came out blurry.
The New Method (LAQW): You switched to a broad, lazy brush that allows for big, sweeping strokes and lets you pause. You still get a beautiful, complex, and unpredictable masterpiece, but your shaky hand can handle the job much better.

In summary: The authors found a way to make quantum computers "lazy" so they can do their job better. This allows us to generate ultra-secure encryption keys on today's imperfect machines, paving the way for future quantum-safe security.

1. Problem Statement

Discrete-time quantum walks (DTQWs), specifically the Controlled Alternating Quantum Walk (CAQW), have been proposed for cryptographic applications (e.g., image encryption, symmetric-key generation) due to their chaotic properties (sensitivity to initial conditions, nonlinearity, and aperiodicity). However, implementing these models on current Noisy Intermediate-Scale Quantum (NISQ) devices faces a critical bottleneck: circuit depth.

The Bottleneck: Existing CAQW implementations on an $n \times n$ lattice over $t$ time steps require a circuit depth scaling as $O(n^2t)$ .
The Consequence: This depth is too high for current hardware, leading to significant noise accumulation and decoherence. Consequently, the output probability distributions become too noisy to be reproducible, rendering them useless for deterministic symmetric-key generation where sender and receiver must generate identical keys from the same initial parameters.
The Constraint: Cryptographic applications using DTQWs often require odd-sized cycle graphs to avoid predictable parity patterns (where walkers are confined to even or odd nodes). However, standard optimization techniques like the Quantum Fourier Transform (QFT) approach, which reduce depth to $O(n^2 + nt)$ , require circulant matrices that cannot be formed on odd-sized graphs using standard qubit encodings.

2. Methodology: The Lackadaisical Alternating Quantum Walk (LAQW)

The authors propose a novel algorithm, the Lackadaisical Alternating Quantum Walk (LAQW), designed to overcome the depth limitations of CAQW while maintaining compatibility with odd-sized lattices and chaotic dynamics.

Core Innovation: Self-Loops and QFT

Lackadaisical Mechanism: The LAQW introduces self-loops to every node of the graph. This allows the "walker" to stay in place with a certain probability, fundamentally altering the dynamics.
Circuit Optimization: By adding a second coin qubit, the shift operator is redefined to allow the walker to move left, right, or stay. This modification ensures the shift matrices ( $P_0$ and $P_1$ ) become circulant, even on odd-sized lattices (when mapped to even-sized Hilbert spaces).
QFT-Based Implementation: Because the matrices are now circulant, the authors can utilize the Quantum Fourier Transform (QFT) approach. This allows the shift operations to be diagonalized, reducing the circuit depth scaling from $O(n^2t)$ to $O(n^2 + nt)$ .

Symmetric-Key Generation Scheme

The paper outlines a full pipeline for generating reproducible cryptographic keys:

Initialization: Parameters include initial position $(x, y)$ , coin angles ( $\alpha, \theta_0, \theta_1$ ), time steps $t$ , and a binary key string $K$ .
Measurement & Sampling: The LAQW is executed for $S \approx 10^6$ shots to approximate the probability distribution.
Post-Processing (Bitstring Generation):
- Interval Rounding: Measured counts are rounded to integer intervals to ensure reproducibility across trials despite minor statistical fluctuations.
- Prime-Modulus Mapping: Rounded counts are mapped to byte values using a deterministic prime-modulus scheme. This disrupts the underlying structure of the probability distribution to ensure a near-uniform byte distribution, avoiding the non-uniformity seen in simple modulo-256 operations.
Entropy Estimation & Extraction:
- Min-Entropy: The conservative min-entropy is estimated using the Clopper-Pearson method on the maximum observed probability.
- Leftover Hash Lemma (LHL): A deterministic weighted bit extraction scheme is applied to the raw bitstring. The extraction weight is based on the initial coin state parameter $\alpha$ , ensuring the final key length is within the theoretical security bound ( $m \le K_{raw} - 2\log_2(1/\epsilon)$ ).

3. Key Contributions

Algorithmic Improvement: Introduction of the LAQW model, which achieves a significant circuit depth reduction ( $O(n^2 + nt)$ vs. $O(n^2t)$ ) compared to CAQW, making it viable for NISQ devices.
Reproducible Key Generation: A complete framework for generating 128-bit symmetric keys from quantum walks, including a novel prime-modulus mapping and weighted extraction method to handle quantum noise and statistical fluctuations.
Empirical Validation: Comprehensive evaluation using IBM's FakeTorino backend (simulating real hardware noise) and noiseless simulators, demonstrating that the scheme produces reproducible keys despite noise.

4. Results

The authors conducted extensive simulations and comparisons between LAQW and CAQW:

Circuit Depth Reduction:
- On a GenericBackendV2 (all-to-all connectivity) and FakeTorino (heavy-hex topology), the LAQW achieved an average circuit depth reduction of ~88% compared to CAQW.
- For an $8 \times 8$ lattice with $t=20$ , LAQW depth was ~550 gates vs. ~5064 for CAQW.
Parameter Sensitivity (Chaos):
- LAQW showed higher sensitivity to small changes in coin parameters ( $\theta_0, \theta_1, \alpha$ ) compared to CAQW (average Hellinger distance increases of 30.12%, 29.63%, and 18.98% respectively).
- CAQW was more sensitive to changes in time steps $t$ , but LAQW's overall sensitivity to coin parameters is advantageous for key generation.
Statistical Randomness (NIST Tests):
- Raw Bitstrings: LAQW raw bitstrings passed 5/6 NIST tests (failing only the Runs test, indicating slight oscillatory tendencies). CAQW failed the Block Frequency test.
- Extracted Keys: After post-processing, the 128-bit keys generated by LAQW passed all 6 NIST tests (Frequency, Block Frequency, Runs, Longest Run, Spectral, Cumulative Sums), confirming high-quality randomness.
Reproducibility:
- Across 100 trials with identical initial parameters, the normalized Hamming distance for the final 128-bit keys was 0.0003 (effectively zero).
- Even under realistic noise (FakeTorino), the key reproducibility remained high (average Hamming distance 0.0002), with only one instance of a 2-bit deviation.
Entropy: LAQW yielded a higher average min-entropy ( $h_{min} \approx 2.78$ bits/block) compared to CAQW ( $h_{min} \approx 1.95$ bits/block), allowing for more extractable uniform bits.

5. Significance

This paper addresses a critical gap in quantum cryptography: the transition from theoretical quantum walk models to practical, NISQ-compatible implementations.

Feasibility: By reducing circuit depth by ~88%, the LAQW makes quantum walk-based encryption feasible on current and near-term hardware, where deep circuits previously resulted in unusable noise.
Security: The scheme demonstrates that quantum walks can serve as robust entropy sources. The high sensitivity to initial parameters ensures that a brute-force attack is infeasible (a 1% parameter error yields an uncorrelated key), while the deterministic extraction ensures legitimate users can reproduce the key.
Future Applications: The methodology provides a blueprint for using quantum walks in symmetric-key generation, image encryption, and hash functions, moving beyond theoretical proposals to hardware-realizable protocols.

In conclusion, the LAQW model represents a significant step forward in making chaos-based quantum cryptography a reality for the NISQ era, balancing computational efficiency with cryptographic robustness.