Algorithm guide · walk
Quantum walk on a hypercube
Walk the d-dimensional hypercube from one corner and watch the amplitude gather on the opposite one.
Circuit size: log2(d) coin qubits + d position qubits — 3, 6 or 11 in total
Bit-string vertices · Uniform coin states · Conditional bit flips
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
Walk on the d-dimensional hypercube, whose 2ᵈ vertices are d-bit strings. Each edge flips exactly one coordinate bit. Study coherent transport from the all-zero corner.
2. How it works
A coin chooses which coordinate to flip, rather than whether to add or subtract an integer. The Grover coin mixes directions. Starting at one corner allows nonuniform transport; a uniformly occupied graph would stay uniform under this unperturbed walk.
Prepare corner
Position starts at 0ᵈ; coin starts uniform over d directions.
Mix
Apply the d-dimensional Grover coin.
Shift along an edge
For coin j, flip position bit j.
Repeat and observe
Measure the position distribution and compare opposite corners.
3. The mathematics, one idea at a time
e_j is the bit string with only bit j equal to 1. Each move changes Hamming weight by one.
There are log2(d) coin wires for the offered power-of-two dimensions.
Work this through by hand
4. The square: d=2, one step
One coin plus two position wires: three qubits, the smallest supported hypercube.
Choose dimension 2 and one step. Position starts at 00.
| Stage | Calculation or state | What it means |
|---|---|---|
| Uniform coin | (|0⟩+|1⟩)/√2 | For d=2 the Grover coin is X and preserves this uniform state. |
| Shift | (|0,01⟩+|1,10⟩)/√2 | Each branch flips a different coordinate. |
| Position probabilities | P(01)=P(10)=1/2 | Both are adjacent vertices of the square. |
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 | One coordinate flipped. |
| 10 | 50% ideal | The other coordinate flipped. |
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.
- Dimension (d)
- d = 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
Read a d-bit position, excluding coin wires.
For d=4 at four steps, the opposite corner has probability 9/16. That larger case is a transport example, not a guarantee of perfect transfer for all dimensions.
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
- A dimension d hypercube has 2ᵈ vertices, not d vertices.
- Position 11 and integer position 2 are different concepts; use bit-string coordinates for graph edges.
8. Check your understanding
For the d=2 example, where is the walker after two steps?
Reveal the reasoning
At 11 with certainty ideally: X swaps the coin directions so each path flips the other coordinate on its second move.
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.
- Dimension (d)
- Default: 4 · Choices for the current settings: d = 2 (The square: 1 coin + 2 position qubits, 4 vertices.); d = 4 (2 coin + 4 position qubits, 16 vertices.); d = 8 (3 coin + 8 position qubits, 256 vertices.).
Powers of two only: the coin register names one edge per basis state, and a non-power-of-two dimension would leave coin states pointing nowhere — a different walk, not this one.
- Steps
- Default: 4 · 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
Starts at vertex 0 with a uniform coin. Starting from the uniform superposition over all vertices instead would be an exact fixed point of this walk — the Grover coin fixes the uniform coin state and the shift permutes a uniform position register onto itself, so the distribution would sit on 1/2^d forever. From a corner, d = 4 puts 9/16 on the antipodal vertex after four steps. d = 8 is 11 qubits, past the 10-qubit step-history limit, so the composer will not record per-step states for it.
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.
- Vertices
- 16
- Columns/step
- 20
- Most likely vertex
- 15
- Peak probability
- 0.5625
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.