Algorithm guide · oracle
Grover search
Amplify any set of marked basis states to near-certainty in O(√(N/M)) oracle calls.
Circuit size: n = 2..7 qubits (uses MCX)
Amplitudes and squared magnitudes · A phase oracle · Uniform superposition
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
Find one of M marked items among N=2ⁿ possibilities using an oracle that recognizes marked states. The task is to produce one marked item, not read an entire database in one measurement.
2. How it works
The oracle flips the marked amplitudes’ signs. Diffusion reflects every amplitude about their average. These two reflections rotate the state toward the marked subspace. Too many rounds rotate it away again.
Prepare
H on each search wire gives amplitude 1/√N to every basis string.
Mark
A phase oracle multiplies marked branches by −1.
Diffuse
Apply D=2|s⟩⟨s|−I, then repeat the oracle/diffusion pair the selected number of times.
Measure
Read a search string and check whether it is marked.
3. The mathematics, one idea at a time
ā is the mean amplitude after the oracle. This reflection changes amplitudes, not probabilities directly.
θ is the starting angle toward the marked subspace and k is the number of full Grover rounds. This explains both amplification and overshooting.
Work this through by hand
4. Search four items for 11
n=2 is the supported minimum. One mark among four makes a particularly transparent exact example.
Use two search qubits and enter marked state 11. The generator chooses one round.
| Stage | Calculation or state | What it means |
|---|---|---|
| Initial amplitudes: 00,01,10,11 | (1/2, 1/2, 1/2, 1/2) | Each initial probability is 1/4. |
| After oracle | (1/2, 1/2, 1/2, −1/2); mean=1/4 | Only the marked amplitude changes sign. |
| After diffusion | (0,0,0,1) | For an unmarked branch: 2(1/4)−1/2=0. For 11: 2(1/4)+1/2=1. |
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 |
|---|---|---|
| 11 | 100% ideal for this example | The marked item. |
| 00,01,10 | 0% ideal for this example | Unmarked items cancel. |
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.
- Search space qubits (n)
- 2
- Marked states
- 11
- 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 c1c0; the last character is c0. The marked input string uses the corresponding search-bit convention.
The 100% result is special to this size and marked fraction. In general ordinary Grover is probabilistic.
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
- More iterations do not always mean more success.
- An oracle query hides implementation cost. The teaching oracle is built from known selected marks; this is not a free search through externally stored data.
8. Check your understanding
What happens after a second full round in this example?
Reveal the reasoning
θ=π/6, so success is sin²(5π/6)=1/4. The first round was already optimal.
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.
- Search space qubits (n)
- Default: 3 · Whole number from 2 to 7.
- Marked states
- Default: 101 · Comma-separated 3-character marks (up to 32). Use 0 and 1 only. The rightmost character is q0.
Each mark is one basis state. A state can be marked only once.
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.
- Oracle queries
- 2
- Classical queries
- 7
- Speedup
- 3.5×
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.