Algorithm guide · walk
Quantum walk on a 2D torus
Walk a periodic grid with a four-sided Grover coin — two coin qubits, one position register.
Circuit size: 2 coin qubits + nx + ny position qubits
A two-qubit coin · Periodic coordinates · The 1D walk
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
Move coherently on a periodic rectangular grid using a four-direction Grover coin. Track a two-coordinate position and understand how it is encoded as one classical integer.
2. How it works
Two coin bits select +x, −x, +y or −y. Mixing those directions and applying conditional shifts produces multiple paths across the torus. Later paths interfere; a boundary crossing wraps to the opposite edge.
Initialize
Both coordinates and the coin begin at zero.
Mix directions
Apply the four-dimensional Grover coin.
Move
Shift the selected coordinate modulo its axis length.
Read coordinates
Measure position; the coin is not part of the answer.
3. The mathematics, one idea at a time
The circuit may represent C up to an overall sign, which does not change position probabilities.
The low nx position bits encode x; the higher ny bits encode y. This is a torus, so coordinates wrap.
Work this through by hand
4. One step on the smallest offered grid
nx=ny=2 gives a 4×4 torus and six physical wires including the two-bit coin. The UI does not offer one-bit coordinate axes.
Set both axis widths to 2 and Steps=1.
| Stage | Calculation or state | What it means |
|---|---|---|
| Coin probabilities | From |00⟩, four outgoing magnitudes are 1/2 | Each direction has probability 1/4, though their signs need not agree. |
| Neighbors of (0,0) | (1,0), (3,0), (0,1), (0,3) | The negative moves wrap. |
| Node encoding | 1, 3, 4, 12 | Use node=4y+x, not a concatenation of decimal coordinates. |
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 |
|---|---|---|
| 0001 | 25% ideal | (x,y)=(1,0). |
| 0011 | 25% ideal | (3,0). |
| 0100 | 25% ideal | (0,1). |
| 1100 | 25% ideal | (0,3). |
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.
- x qubits (nx)
- 2
- y qubits (ny)
- 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
Split the four-bit position label as yy|xx for this example.
Later even steps allow return to the origin; they do not in general force all probability to be there. Inspect the actual distribution rather than inferring a complete return from parity alone.
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 include the two coin bits when decoding node.
- A periodic grid has no hard wall: moving left from x=0 reaches x=3 here.
8. Check your understanding
What coordinate does label 1001 represent on this grid?
Reveal the reasoning
Split it as y=10₂=2 and x=01₂=1. The coordinate is (1,2), node 9.
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.
- x qubits (nx)
- Default: 2 · Whole number from 2 to 3.
The torus is 2^nx wide.
- y qubits (ny)
- Default: 2 · Whole number from 2 to 3.
The torus is 2^ny tall.
- Steps
- Default: 3 · Whole number from 1 to 8.
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
x lives in the low nx position wires and y in the high ny, so node = y · 2^nx + x. The four coin values select +x, −x, +y, −y. The walk is back on the origin at even step counts and entirely off it at odd ones, so an odd default is the one that shows the spread.
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.
- Grid
- 4 × 4
- Columns/step
- 24
- Most likely node
- (3, 0)
- Peak probability
- 0.4375
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.