⚛️ quantum physics

Lazy Quantum Walks with Native Multiqubit Gates

This paper proposes a quantum half-adder gate method for lazy quantum walks as a benchmark to demonstrate that neutral atom hardware, leveraging native multiqubit Rydberg gates and dynamic qubit rearrangement, can outperform decomposed two-qubit gate implementations within a specific error-tolerance sweet spot for fluid dynamics simulations.

Original authors: Steph Foulds, Viv Kendon

Published 2026-03-17

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Steph Foulds, Viv Kendon

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

The Big Picture: A Quantum Game of "Follow the Leader"

Imagine you are playing a game of "Follow the Leader" on a circular track. In a normal game, you take a step forward or backward based on a coin flip. This is a Classical Random Walk.

Now, imagine a Quantum Walk. Here, the "coin" isn't just heads or tails; it's a magical coin that can be both at the same time. Because of this, the "walker" (the person moving) doesn't just take one path; they take every possible path at once, interfering with each other like ripples in a pond. This allows them to explore the track much faster than a normal person could.

Why do we care?
Scientists think these quantum walks are the secret sauce for simulating fluids (like water flowing or air moving around a wing). To simulate a fluid, you need to model particles that can move left, move right, or just sit still (rest).

The Problem: The "Lazy" Walker

Standard quantum walks are great, but they only allow "move left" or "move right." They don't have a "rest" button. To fix this, the authors propose a "Lazy Quantum Walk."

Think of it like a traffic light:

Green: Go forward.
Red: Go backward.
Yellow: Stop. (This is the "Lazy" part).

To make this "Stop" state work in a quantum computer, you need a more complex coin. Instead of a simple 2-sided coin (Heads/Tails), you need a 4-sided coin (Heads/Tails/Stop/Reverse). This requires the computer to juggle more information at once.

The Hardware: The "Magic Table" vs. The "Assembly Line"

The paper compares two ways to build this quantum computer, using Neutral Atoms (tiny, floating atoms held by laser tweezers) as the platform.

1. The Old Way (Decomposition)

Imagine you want to move a heavy sofa up a flight of stairs.

The Strategy: You break the sofa down into tiny pieces, carry them up one by one, and reassemble them at the top.
In Quantum Terms: You try to build a complex "multi-qubit" gate (a move that affects 3 or 4 atoms at once) by chaining together many simple "two-qubit" gates (moves that only affect 2 atoms).
The Downside: Every time you carry a piece up the stairs, there's a chance you drop it or it gets dusty (errors). The more pieces you have, the more likely the sofa falls apart.

2. The New Way (Native Multiqubit Gates)

The Strategy: You have a magical elevator that can lift the entire sofa in one go.
In Quantum Terms: The neutral atom hardware has a special superpower: it can naturally perform operations on 3, 4, or even more atoms simultaneously without breaking them down first.
The Benefit: Fewer steps mean fewer chances for errors. It's like taking the elevator instead of the stairs.

The Experiment: Testing the Elevator

The authors ran a simulation to see which method works better for these "Lazy" walks. They tested different sizes of tracks (4, 8, and 16 stops) and compared:

The "Stairs" approach: Using only simple 2-atom and 3-atom gates.
The "Elevator" approach: Using native 4-atom gates (which are currently theoretical but very promising).

The Results:

Small Tracks (4 stops): The "Elevator" (4-atom gates) was a clear winner. It kept the simulation accurate for much longer.
The Sweet Spot: They found that adding a 4-atom gate gives you a huge boost in performance. However, adding a 5-atom or 6-atom gate doesn't help much more. It's like upgrading from a bicycle to a car; going from a car to a tank doesn't make you drive that much faster on a normal road.
The "Lazy" Factor: The "Lazy" walks (with the rest state) are harder to run than standard walks, but the native multiqubit gates make them possible on current hardware.

The Conclusion: Why This Matters

This paper is essentially a roadmap for building better quantum computers.

It tells hardware engineers: "Don't just keep trying to make your 2-atom gates perfect. Instead, focus on building reliable 4-atom gates. That is the 'sweet spot' where you get the most bang for your buck."

If we can master these 4-atom "magic elevators," we can run complex simulations of fluids and weather patterns on quantum computers much sooner than we thought. It turns a theoretical "what if" into a practical "how to."

Summary in One Sentence

The paper proves that using a quantum computer's ability to move four atoms at once (instead of breaking the job down into smaller, error-prone steps) is the key to successfully simulating fluids and other complex physics problems.

1. Problem Statement

Quantum walks (QWs) are the quantum analogues of classical random walks and serve as the foundation for several quantum algorithms, including those for fluid dynamics simulation (e.g., lattice Boltzmann methods). However, standard QWs lack a "rest state" (zero velocity), which is essential for modeling fluid particles at rest. To address this, Lazy Quantum Walks (LQWs) are required, which introduce a self-loop on the graph, effectively increasing the dimensionality of the coin state.

While LQWs are theoretically useful, they have not yet been experimentally implemented. Implementing them efficiently on near-term quantum hardware is challenging because:

Gate Depth: Efficiently encoding LQWs on a ring graph requires multiqubit gates (acting on 3 or more qubits) to perform the shift operation.
Hardware Limitations: Most current quantum processors (e.g., superconducting, trapped ions) are limited to native two-qubit gates. Implementing multiqubit operations requires decomposing them into sequences of two-qubit gates, which increases circuit depth and accumulates significant error.
Benchmarking Gap: There is a need for a robust benchmark to compare the performance of native multiqubit gates (available on neutral atom platforms) against decomposed gate sequences.

2. Methodology

The authors propose using Lazy Quantum Walks as a benchmark algorithm to evaluate neutral atom quantum processors, which feature dynamically reconfigurable qubit arrays and native multiqubit gates (via Rydberg states).

A. Algorithmic Model

Encoding: The walk is performed on a $2^n$ $2^{n}$ -node ring. Position is encoded in $n$ $n$ qubits, and the coin state is encoded in 1 or 2 qubits.
- 1q-coin: Standard walk (clockwise/anticlockwise).
- 2q-coin (Lazy): Includes a "rest" state. The shift operator $S$ $S$ acts on $n+2$ $n + 2$ qubits.
  - $|x, 00\rangle \to |x, 00\rangle$ (Rest)
  - $|x, 01\rangle \to |x-1, 01\rangle$ (Anticlockwise)
  - $|x, 10\rangle \to |x, 10\rangle$ (Rest)
  - $|x, 11\rangle \to |x+1, 11\rangle$ (Clockwise)
Circuit Implementation: The authors utilize the Quantum Half-Adder gate method to implement the shift operator. This requires Controlled-NOT gates ( $C_kX$ ) where $k$ is the number of control qubits. For an $n$ -node ring with a 2q-coin, gates of rank up to $n+2$ are required.

B. Hardware and Error Modeling

The study simulates a programmable array of Cesium (Cs) atoms using a detailed error model based on two-photon adiabatic rapid passage (ARP) for Rydberg gates.

Native Gates: The model includes effective matrices for:
- $CZ$ (2-qubit)
- $CCZ$ (3-qubit)
- $C_3Z$ (4-qubit, theoretical but not yet experimentally realized).
Error Sources: The simulation accounts for:
- Gate Fidelity: Imperfect unitary operations (modeled via non-unitary effective matrices).
- SPAM: State preparation and measurement errors (including population leakage).
- Passive Noise: $T_1$ (relaxation) and $T_2$ (dephasing) decay during gate execution and qubit movement.
- Atom Loss: Random loss of atoms during transport or readout.
Comparison Strategy: The authors compare two approaches:
1. Native Multiqubit Implementation: Using native gates up to rank 3 ($CZ, CCZ$) or rank 4 ( $C_3Z$ ).
2. Decomposed Implementation: Decomposing higher-rank gates into sequences of lower-rank native gates (e.g., decomposing $C_4X$ into $CCX$ and $C_3X$ ).

3. Key Contributions

Proposal of LQWs as a Benchmark: The paper identifies Lazy Quantum Walks as a specific, practical benchmark for neutral atom hardware, highlighting the necessity of multiqubit gates for fluid simulation applications.
Detailed Error Modeling: The authors provide a comprehensive simulation framework incorporating realistic parameters for neutral atom systems, including specific effective matrices for 2-, 3-, and 4-qubit Rydberg gates, atom loss, and transport delays.
Identification of the "Sweet Spot": The study quantitatively determines the optimal native gate rank. It demonstrates that while moving from 2-qubit to 3-qubit gates offers massive gains, and 3-qubit to 4-qubit offers significant gains, the marginal utility diminishes for gates of rank 5 or higher.
Performance Prediction: The paper predicts the final state fidelities for LQWs on 4, 8, and 16-node rings under current and projected hardware capabilities.

4. Results

The simulations were performed for 21 steps on rings of varying sizes ( $N=4, 8, 16$ ) using both 1q-coin and 2q-coin encodings.

Near-Term Performance (Max Rank 3):
- With current estimated fidelities ( $F_{CZ} \approx 0.9981$ , $F_{CCZ} \approx 0.9954$ ), a 2q-coin LQW on a 4-node ring achieves a final state fidelity $f > 0.99$ for 2 steps and $f > 0.90$ for 14 steps.
- For larger rings (8 or 16 nodes) or more coin qubits, fidelity drops rapidly below the 0.99 threshold, limiting the feasible walk length.
- Gate errors are the dominant source of fidelity loss; atom loss at readout contributes minor "wobbles" in the fidelity curve.
Impact of Native 4-Qubit Gates (Rank 4):
- Introducing a native $C_3Z$ gate ( $F \approx 0.9850$ ) significantly improves performance.
- For a 2q-coin LQW on a 4-node ring, the number of steps maintaining $f > 0.99$ increases from 2 to 5 steps.
- The number of steps maintaining $f > 0.90$ increases from 14 to 21 steps (the full simulation length).
- This improvement is roughly equivalent to improving 2-qubit and 3-qubit gate fidelities to $\approx 99.99\%$ and $99.79\%$ respectively, which is a more difficult engineering challenge than implementing a native 4-qubit gate.
Decomposition vs. Native Gates:
- Decomposing a 4-qubit gate into 3-qubit gates results in a significant fidelity penalty due to the accumulation of errors in the longer circuit.
- The "sweet spot" is identified at max rank = 4. Increasing the native gate rank beyond 4 (e.g., to 5 or 6) yields only marginal gains in composite fidelity compared to the complexity and error rates of implementing such high-rank gates.

5. Significance and Conclusion

The paper concludes that native multiqubit gates (specifically up to rank 4) and mid-circuit qubit rearrangement are critical for the near-term implementation of useful quantum algorithms like fluid simulations on neutral atom hardware.

Feasibility: It is feasible to run meaningful Lazy Quantum Walks on 4-node rings with current or slightly improved neutral atom hardware, provided native 3- and 4-qubit gates are utilized.
Hardware Roadmap: The results suggest that quantum hardware developers should prioritize the implementation of native 4-qubit gates ( $C_3Z$ ) over simply trying to perfect 2-qubit gates or attempting to build 5+ qubit gates, as the latter offers diminishing returns.
Application: This work bridges the gap between theoretical quantum fluid dynamics and experimental realization, providing a clear path for neutral atom processors to demonstrate quantum advantage in simulation tasks.

The authors recommend experimentalists attempt a 4-node ring LQW to validate these theoretical predictions and suggest future work on non-linear fluid simulations and 2D lattice walks.