Algorithm guide · oracle
Quantum counting
Estimate how many states an oracle marks using phase estimation on Grover's iterate.
Circuit size: 2–4 search + 2–4 counting qubits
Grover’s rotation angle · Phase estimation · Binary integers
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
Estimate the number M of marked states among N=2ⁿ possibilities. Instead of amplifying and returning a marked item, measure the phase of Grover’s rotation and turn it into a count.
2. How it works
The same marked fraction that controls Grover’s rotation also controls its eigenphases. A counting register acts like a phase ruler. Two mirrored phase peaks describe the same marked fraction.
Prepare registers
Superpose the search and counting registers.
Controlled powers
Counting bit j controls 2ʲ Grover iterations.
Inverse QFT
Interference converts the accumulated phase into a t-bit integer y.
Decode
Compute N sin²(πy/2ᵗ), allowing for finite phase precision.
3. The mathematics, one idea at a time
Both rotations encode the same count because squaring sine removes the sign.
y is the measured counting integer. It is not M itself. Increasing t refines the phase grid while increasing controlled-oracle cost.
Work this through by hand
4. Count two marked states among four
Two search and two counting qubits: the supported minimum of each register. Two marks make the phase exactly representable.
Mark 10 and 11. Although you know M while building this teaching oracle, the estimation circuit obtains it through phase interference.
| Stage | Calculation or state | What it means |
|---|---|---|
| Fraction | M/N=2/4=1/2 ⇒ θ=π/4 | The Grover eigenphases are 1/4 and 3/4. |
| Counting bins | 2ᵗ=4 ⇒ y=1 or 3 | Binary labels are 01 and 11. |
| Decode either | 4 sin²(π/4)=4 sin²(3π/4)=2 | The two different peaks represent the same answer. |
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 | Estimated count 2. |
| 11 | 50% ideal | Estimated count 2 from the mirrored phase. |
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 qubits (n)
- 2
- Counting qubits (t)
- 2
- Marked states
- 10,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 only c1c0 from the counting register, not the search wires.
For other fractions, y may spread across bins and the decoded estimate need not be an integer. Do not assume rounding one shot always gives the true M.
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 result 11 means y=3, not three marked items.
- Paired peaks are expected physics, not duplicate or conflicting counts.
8. Check your understanding
If N=4 and y=0 with t=2, what does the decoder return?
Reveal the reasoning
It returns 0. In a finite-precision experiment this may be a low-probability estimation error; it does not by itself prove the oracle has no marks.
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 qubits (n)
- Default: 3 · Whole number from 2 to 4.
- Counting qubits (t)
- Default: 3 · Whole number from 2 to 4.
Phase precision uses 2^t bins and 2^t − 1 controlled oracle queries. The estimate is approximate unless the phase lies exactly on a bin.
- Marked states
- Default: 101 · Comma-separated 3-character marks (up to 16). _ means either bit. The rightmost character is q0.
Mark one or more disjoint states. Each _ matches either 0 or 1; overlapping patterns and a fully marked search space are rejected.
Implementation notes
This example uses the gallery's default configuration. Check Run details for the settings used in your execution.
Marks are written q2…q0, last character q0, like Grover's. Counting wires q3–q5 measure into c0–c2. Read the Classical bits histogram as c2…c0. Paired phase peaks describe the same count. More counting qubits improve precision but increase circuit depth. This example supports at least one marked and one unmarked state.
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
- 7
- Phase bins
- 8
- Configured marks
- 1 of 8
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.