Algorithm family
Grover search
Unstructured search of N=2^n items with a single marked state: the optimal iteration count grows as (pi/4)sqrt(N) and the success probability at that count approaches certainty. The registry's reference run measures success probability across n = 2..6.
Assumptions and execution semantics
The registry implementation draws shots from Grover's ANALYTIC success probability -- it is a modelled result, not a circuit execution, and every run records that. Circuit depth and gate counts are formula-derived for the standard construction. One marked state (all-ones); no noise model.
Implementations
| Engine | Method | Backend | Abstraction level | Semantics |
|---|---|---|---|---|
| ketqat-runner | shot-based | analytic success-probability model | algorithmic (no gate-level compilation) | MODELLED Modelled — values follow from an analytic formula, no circuit was executed shots are Bernoulli draws from sin^2((2k+1) asin(2^{-n/2})) at the exact optimal k; ketqat-sdk#228 fixed k at n=2 |
Problem and sizes
- Instance types
- marked-state-search
- Size axis
- qubit_count (n; N = 2^n items)
- Sizes measured
- n = 2n = 3n = 4n = 5n = 6
- Parameters
- marked_state, shots, seed
Suites and runs
Quality and resources across size
One row per measured point; every row traces to its run. Semantics per the implementation table — nothing here mixes modelled and simulated values in one aggregate.
| n | Success probability | Depth | Gates (2q) | Runtime (s) | Run |
|---|---|---|---|---|---|
| 2 | 1.000000 | 3 | 6 (1) | 0.0000 | grover-search-reference |
| 3 | 0.940918 | 5 | 15 (4) | 0.0000 | grover-search-reference |
| 4 | 0.952881 | 7 | 28 (9) | 0.0000 | grover-search-reference |
| 5 | 0.999756 | 9 | 45 (16) | 0.0000 | grover-search-reference |
| 6 | 0.997803 | 13 | 78 (30) | 0.0000 | grover-search-reference |
These points come from one reference sweep. One entrant is not a comparison; this table shows scaling, it ranks nothing.
References
- Grover, A fast quantum mechanical algorithm for database search — arXiv:quant-ph/9605043
- Boyer, Brassard, Hoyer, Tapp, Tight bounds on quantum searching — arXiv:quant-ph/9605034
Next action
Add a gate-level simulated implementation so the modelled curve can be checked against an executed circuit, and record conversion loss between the two abstraction levels.