Algorithm guide · oracle
Fixed-point Grover search
Find marked states with a guaranteed high success rate even when their exact fraction is unknown.
Circuit size: n = 2..4 search qubits
Ordinary Grover · Probability bounds · Phase rotations
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 marked states when only a trustworthy lower bound λ_min on their initial fraction is known. Choose an allowed failure probability ε and guarantee high final ideal success for fractions at least that bound.
2. How it works
Ordinary Grover always uses π reflections and can overshoot badly when the fraction is misestimated. This construction changes the reflection phases from round to round. A designed polynomial keeps final failure small over an interval of fractions.
Set the promise
Choose λ_min no greater than the actual marked fraction and choose ε.
Synthesize phases
The generator chooses an odd polynomial length and paired oracle/reflection angles.
Apply the sequence
Run the variable-phase rounds, then measure and check a marked data string.
3. The mathematics, one idea at a time
This is a final ideal guarantee under a valid lower bound, not exact certainty.
T_L is the Chebyshev polynomial, defined by T_L(cos u)=cos(Lu). The generator chooses odd L so the promised interval lies inside the bounded region. Noninteger T_(1/L) is evaluated through cosh/arcosh on arguments above one.
Work this through by hand
4. Four items, one marked state
n=2 is the supported minimum; the phase sequence can still be deeper than ordinary Grover.
Choose mark 11, minimum marked fraction 0.25 and target failure 0.1. Here the actual fraction equals the lower bound.
| Stage | Calculation or state | What it means |
|---|---|---|
| Count the example | N=4, M=1 ⇒ λ=1/4 | The chosen lower bound is valid. |
| Translate the bound | 1−ε=0.9 | The final ideal chance of a marked result must be at least 90%. |
| Inspect configuration | Review phase rounds and ideal success in the dialog | That calculated value can exceed 90%; it need not equal 100%. |
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 | At least 90% in the ideal promised case | Successful marked outcome. |
| Other strings together | At most 10% in the ideal promised case | Allowed failure probability. |
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
- Minimum marked fraction
- 0.25
- Target failure probability
- 0.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
Add counts of all marked labels, then divide by total shots. This estimates success; finite samples can lie below the ideal bound by chance.
For a deterministic numerical prediction of this specific configuration, use the dialog’s ideal success value; the 90% above is a guarantee, not the exact histogram.
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
- The guarantee fails if λ_min is larger than the true fraction.
- Fixed-point does not mean every intermediate partial sequence improves monotonically, and it does not mean deterministic search.
8. Check your understanding
What if you set λ_min=0.5 when only one of four states is marked?
Reveal the reasoning
The promised condition λ≥λ_min is false. The stated success bound no longer applies.
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
Choose marked states, a conservative minimum marked fraction, and an acceptable failure rate. Open the variable-phase circuit in Composer.
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 4.
- Marked states
- Default: 101 · Comma-separated 3-character marks (up to 8). Use 0 and 1 only. The rightmost character is q0.
Select complete, distinct basis states. The simulator uses them to check the lower-bound guarantee.
- Minimum marked fraction
- Default: 0.05 · A probability from 0 to 1 inclusive.
A conservative lower bound on the fraction of marked states. It must not exceed the actual fraction selected above.
- Target failure probability
- Default: 0.1 · A probability from 0 to 1 inclusive.
The ideal success guarantee is at least 1 minus this value when the lower bound holds. A smaller value needs a deeper circuit.
Implementation notes
Ordinary Grover uses the same π phase flip each round and needs the marked fraction to choose when to stop. This Yoder–Low–Chuang circuit changes the oracle and reflection phases each round. If the actual marked fraction is at least the selected lower bound, ideal success is at least 1 minus the chosen failure rate. That is a bound, not exact 100% success or a claim that every intermediate round improves. The deterministic card instead tunes an ancilla using the exact marked fraction.
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.
- Actual marked fraction
- 1/8
- Phase rounds
- 4
- Success guarantee
- ≥90% (ideal)
- Ideal success here
- 91.65%
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.