Grover speedup is provably optimal but quadratic. The oracle compilation cost is the critical variable: a naive oracle implementing the function as a circuit costs O(N) gates, completely eliminating the speedup. Only structured oracles with O(poly(n)) gate cost preserve the advantage.

• Quadratic speedup offset by large constant factors in fault-tolerant implementation
• Oracle compilation cost not included — real oracles may require O(N) gates, eliminating speedup
• 119k physical qubits for 4-qubit search; scaling to useful N requires millions of qubits
• Grover is provably optimal but constant-factor overhead may delay practical advantage to N>10^6

Provably optimal quadratic speedup, but the QRAM assumption for data loading is critical. Without efficient QRAM, the speedup may be negated by data-access overhead.

Problem 15 · Quantum Database Search

Overview

Unstructured database search underpins many cryptographic attacks and combinatorial problems. Grover's algorithm delivers a quadratic speedup over classical exhaustive search by amplifying probability amplitudes for marked items. This problem now includes a canonical Grover workflow in Q# plus classical query-complexity baselines and analysis plots for cross-checking scaling behavior.

Directory Layout

15_database_search/
├── estimates/                       # JSON artifacts from classical / quantum workflows
├── instances/                       # Dataset sizes and marked item distributions (small/medium/large)
├── plots/                           # Generated figures from analyze.py
├── python/
│   ├── classical_baseline.py        # Exhaustive search complexity and success probability estimates
│   └── analyze.py                   # Visualization of query budgets and scaling behavior
└── qsharp/
    ├── qsharp.json            # Modern QDK project file
    ├── Program.qs                   # Canonical Grover implementation
    └── GroverEstimation.qs          # Resource-estimation variant

Quick Start

cd problems/15_database_search

# Classical baseline (writes estimates/classical_baseline.json)
python python/classical_baseline.py

# Visualize query complexity vs. dataset size
python python/analyze.py

# Quantum workflow (uses modern QDK  qsharp Python package)
python -c "import qsharp; qsharp.init(project_root='qsharp'); print('Build OK')"
python tooling/run_all_qsharp.py  # runs via qsharp Python package

Validation Highlights

• Canonical Grover implementation details and demonstrations are documented in `docs/GROVER_IMPLEMENTATION_SUMMARY.md`.
• Reported simulator success rates include:
• 93% for 16-item single-target search,
• 71% for 32-item multi-target search,
• 100% for 4096-item benchmark case.
• Classical-vs-quantum query scaling artifacts are generated in `plots/` and `estimates/classical_baseline.json`.

Objective Maturity Gate

• **Current gate**: **Stage C complete** (canonical Grover workflow implemented with simulator-backed validation and scaling analysis artifacts).
• **Next gate target**: **Stage D** (advantage evidence package hardening with backend-specific uncertainty methodology and deployment assumptions).

Stage C evidence references for this problem:

• Executable Grover workflow in `qsharp/Program.qs` and estimator variant in `qsharp/GroverEstimation.qs`.
• Simulator validation and empirical success-rate results in `docs/GROVER_IMPLEMENTATION_SUMMARY.md`.
• Classical comparison artifacts in `python/classical_baseline.py`, `estimates/classical_baseline.json`, and `plots/`.
• Circuit construction and control assumptions documented in the implementation summary and problem-local Q# sources.

DiVincenzo Readiness (Stage C/D Overlay)

| Criterion | Status | Evidence / Notes |

|---|---|---|

| Scalable qubit system | partial | Simulator-backed scaling evidence spans small to large instances; hardware resource-estimation evidence is not yet complete. |

| Initialization | met | Initial-state preparation for canonical Grover flow is explicit in qsharp/Program.qs and validated in simulator runs. |

| Coherence vs gate time | not-yet | Backend-calibrated coherence-vs-depth evidence is not yet included; current validation is simulator-centric. |

| Universal gate set | met | Canonical Grover oracle/diffuser workflow is implemented in Q# with documented circuit assumptions. |

| Qubit-specific measurement | partial | Measurement and success-rate validation are documented in simulator studies; hardware readout characterization is pending. |

Advantage Claim Contract

• **Claim category (current)**: `projected`.
• **Problem class and regime**: Unstructured search with configurable dataset size and marked-item fractions.
• **Fair baseline**: Classical exhaustive-search query model in `python/classical_baseline.py`.
• **Quantum resource scaling claim**: Grover scaling O(sqrt(N)) versus classical O(N) with simulator-backed behavior; hardware-specific performance still pending.
• **Data-loading and I/O assumptions**: Oracle construction cost and data-oracle assumptions must be included with future claims.
• **Noise/error model assumptions**: Current evidence is simulator-centric; backend-calibrated noise models remain pending.
• **Confidence/uncertainty method**: Simulator trials reported in implementation summary; backend shot-based confidence intervals remain a Stage D hardening task.
• **Residual risks**: Oracle synthesis and transpilation overhead can erode practical speedup for near-term sizes.

Stage D Hardening Package

• Stage D evidence file: `STAGE_D_ADVANTAGE_EVIDENCE.md`.
• This package defines the Stage D uncertainty/fairness hardening work needed before any promotion to a demonstrated claim category.