Algorithm guide · walk
Quantum walk on a cycle
Walk a ring of N = 2^n nodes with a Hadamard coin and watch it spread ballistically.
Circuit size: 1 coin qubit + n = 2..5 position qubits
Hadamard coin · Position registers · Amplitudes add before probabilities
Review quantum fundamentals →Notation used in this lesson
- |ψ⟩ and ⟨ψ|
- A state vector (ket) and its conjugate transpose (bra). ⟨a|b⟩ is their inner product.
- α, β and i
- α and β are complex amplitudes; i²=−1. A probability is the squared magnitude |α|².
- XOR, · and ⊗
- XOR adds bits modulo two. In s·x, multiply corresponding bits and XOR them. ⊗ combines registers or operations on different wires.
- U†, Σ and Tr
- U† is the adjoint (inverse for a unitary). Σ sums terms. Tr is the matrix trace, the sum of diagonal entries.
- Probability, shots and angles
- Ideal probabilities describe the model; measured shot frequencies fluctuate. Angles inside trigonometric expressions are in radians unless explicitly labeled turns.
1. The problem
Evolve a quantum walker on a cycle of N=2ⁿ nodes. Observe how a coherent coin and conditional movement create a position distribution different from a classical random walk.
2. How it works
The coin is a qubit, not a measured coin toss. Each step splits and mixes amplitudes, then moves the corresponding branches clockwise or anticlockwise. Paths can later meet and interfere.
Initialize
Position starts at zero and coin at |0⟩.
Coin
Apply H to the coin.
Shift
Coin 0 increments the position; coin 1 decrements it modulo N.
Repeat and measure
Repeat coherent steps, then measure position while summing over the unobserved coin.
3. The mathematics, one idea at a time
S is the conditional shift. H is not followed by coin measurement.
At a fixed coin and position, path amplitudes add before squaring. Distinct unmeasured coin states contribute probabilities.
Work this through by hand
4. One step on a four-node cycle
n=2 position wires plus one coin is the supported minimum; use one step for the first calculation.
Set Position qubits=2 and Steps=1.
| Stage | Calculation or state | What it means |
|---|---|---|
| Start | |coin,position⟩=|0,00⟩ | There is one occupied node. |
| After H | (|0,00⟩+|1,00⟩)/√2 | The two directions are coherent. |
| After shift | (|0,01⟩+|1,11⟩)/√2 | Increment reaches node 1; decrement wraps to node 3. |
Expected outcomes for this example
These are ideal predictions for the stated configuration, not a result already measured by your browser. Rows describing alternative modes or combined events are labeled explicitly.
| Outcome or event | Ideal probability | Interpretation |
|---|---|---|
| 01 | 50% ideal | Position 1. |
| 11 | 50% ideal | Position 3, the −1 neighbor modulo four. |
5. Load the worked example in Composer
The worked example can use smaller or simpler inputs than the gallery defaults. The button below loads the exact circuit used in this lesson.
- Position qubits (n)
- 2
- Steps
- 1
- Save any current circuit you want to keep, then open the worked example. Loading it does not execute a paid hardware job.
- Trace the preparation, main operations and measurements against the worked table. Check the gate editor for controls, targets and angles.
- Start with an ideal noiseless simulator compatible with the circuit. Mid-circuit measurement, reset and feed-forward require support from the chosen backend.
- Inspect the live preview. For a recorded experiment, open Execute, set the available backend options and shots, and Run. Sign in when prompted to retain it in My Jobs.
- Read the output as described below before changing one setting and repeating. The guide describes the original example; edits can change the answer.
6. Read the output correctly
Classical bits contains position only; coin q0 is not part of the displayed integer.
This first step also resembles a classical walk. Increase steps to study interference. A small cycle wraps quickly, so infinite-line spreading rules do not describe every later step.
A bit label is a register value; its bar height is a probability or count. For S shots and observed count k, the sampled frequency is k/S. A typical sampling scale for probability p is √[p(1−p)/S]; this is not a strict error bound. Finite samples do not have to match the ideal percentages exactly.
7. Common mistakes & limits
- Do not measure the coin after every step if you want the same coherent walk.
- The unmeasured coin must be marginalized, not read as an extra most-significant position bit.
8. Check your understanding
What are the possible positions after two steps on this four-cycle?
Reveal the reasoning
Only even positions 0 and 2. In this initial-state example each has probability 1/2 after summing over the coin.
9. Further study
The lesson’s register mappings, supported inputs and loadable example follow Quantket’s implemented circuit. A reference may use different wire names, bit order or resource conventions.
Gallery reference: defaults, definitions & implementation notes
Inputs & default settings
These are the gallery defaults. The worked example above may override them. Configure the card to change the inputs before loading its editable circuit.
- Position qubits (n)
- Default: 4 · Whole number from 2 to 5.
The cycle has N = 2^n nodes. The shift is a modular increment/decrement ladder, so the whole ring is addressed by n wires.
- Steps
- Default: 8 · Whole number from 1 to 10.
One step is a coin flip followed by a coin-conditioned shift. The circuit grows linearly in steps — the Columns/step fact says by how much, read off the generator itself.
Implementation notes
The coin starts in |0⟩, which is what makes the distribution lopsided — a classical walk would pile a binomial bell curve on the origin instead, and spread as √steps rather than linearly. Keep 2 × steps below N or the two arms wrap around the ring and interfere with themselves; at n = 4 the shape is intact through 8 steps.
Default example: predictions & circuit facts
These values describe the unedited default setup. They are predictions and circuit properties, not measured results from your saved execution.
- Nodes
- 16
- Columns/step
- 14
- Most likely node
- 4
- Peak probability
- 0.414063
Read your saved result
Check the submitted circuit, measured register and execution settings in Run details. Exact results give computed probabilities; sampled results show frequencies from the recorded shots. Edited circuits and noise can change the expected outcome. The algorithm label records the circuit's origin; it does not certify an edited circuit or a measured result.