Algorithm guide · walk
Hypercube walk search
Find a marked vertex with the Shenvi–Kempe–Whaley coin — no ancilla, no controlled Hadamard.
Circuit size: log2(d) coin + d position qubits — 6 at d = 4, 11 at d = 8
Hypercube walk · Marked-state phase changes · Marginal position 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
Amplify a marked hypercube vertex by changing the coin operation at that vertex. This is a search walk, so its initialization and oracle differ from the corner-start transport example.
2. How it works
Start uniformly across vertices and directions. A localized coin perturbation breaks that stationary pattern. Repeated mixing and shifting creates constructive interference near the marked vertex.
Uniform graph state
Superpose all coin and position wires.
Perturb the marked coin
Apply the reflection about the uniform-coin state at the selected vertex.
Mix and shift
Apply the ordinary Grover coin and hypercube shift.
Stop and measure
Choose a step count, read a vertex and test whether it is marked.
3. The mathematics, one idea at a time
m is the marked vertex. At m this becomes −I on the coin; elsewhere it remains C0.
Success sums probabilities over all coin directions at the marked position. It is not the probability of one complete coin-plus-position basis string.
Work this through by hand
4. Smallest supported search: d=4
Two coin plus four position wires: six qubits. d=2 is intentionally unavailable because it does not amplify the position distribution in this construction.
Choose d=4, marked vertex 0110 and four steps. A one-step warm-up remains uniform; four steps show the first useful amplification in this example.
| Stage | Calculation or state | What it means |
|---|---|---|
| Before walking | P(m)=1/16=6.25% | All 16 vertices start equally likely. |
| Local change | The marked vertex uses −I instead of C0 | This introduces relative signs that later shifts can recombine. |
| After four steps | P(m)=25/64=39.0625% | This is 6.25 times the initial marked probability, not certainty. |
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 |
|---|---|---|
| 0110 | 39.0625% ideal | Successful search result. |
| All other vertices together | 60.9375% ideal | A failed attempt; their individual probabilities need not agree. |
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 = 4
- Marked vertex
- 0110
- Steps
- 4
- 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 the four-bit position string. Check 0110 explicitly; do not include the two coin wires.
The Classical bits histogram estimates success from repeated attempts. The chosen step count matters; more steps are not a universal improvement.
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
- Transport from one corner and search from a uniform graph state are different experiments.
- Do not report 100% search success because the marked vertex is the largest histogram bar.
8. Check your understanding
How many marked outcomes do you expect on average in 640 ideal shots?
Reveal the reasoning
640×25/64=250. Actual finite samples fluctuate around that value.
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 = 4 (16 vertices, 6 qubits. Peaks at step 4.); d = 8 (256 vertices, 11 qubits. Needs many more steps to peak.).
d = 2 is excluded because amplification there is impossible, not merely weak: the position marginal of the d = 2 search is exactly uniform at every step, for every marked vertex.
- Marked vertex
- Default: 0110 · 4 bits (0 or 1); leftmost character is the highest-numbered qubit.
Bit j is position wire j, LSB first (Grover's marks read the other way, q0 last). The default 0110 is vertex 6.
- Steps
- Default: 4 · Whole number from 1 to 8.
Defaults to the measured peak of the d = 4 walk. P(marked) below is always the value at the step count currently selected, not the best over a range.
Implementation notes
The perturbed coin factors as (C₀ ⊗ I)(I − 2|s,m⟩⟨s,m|), so one multi-controlled phase flip across every wire does the whole oracle. d = 2 is deliberately not offered: there the hypercube is a 4-cycle, the walk starts maximally mixed over positions, and P(x) stays pinned to 1/4 at every step whatever the oracle marks — nothing to amplify. At d = 4 the walk peaks at four steps with P(marked) = 25/64, six times uniform; d = 8 climbs more slowly and is still rising at the step cap.
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
- 25
- P(marked)
- 0.390625
- Most likely vertex
- 6
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.