Grover search and its black-box lower bound
Research context
postgraduate concept · established · As of 2026-10-10
For an unstructured search over N alternatives with a coherent marking oracle and one marked item, amplitude amplification uses O(sqrt(N)) oracle queries for bounded success probability.
Key knowledge
For an unstructured search over N alternatives with a coherent marking oracle and one marked item, amplitude amplification uses O(sqrt(N)) oracle queries for bounded success probability. A matching order lower bound holds in this black-box quantum query setting. The gain is quadratic against classical unstructured query search, not an exponential speedup for every search problem; oracle construction and verification may dominate actual runtime.
Conditions and scope
- The standard one-solution promise, coherent oracle access and counted resource are explicit.
- Known multiple solutions change the rotation angle; finding all matches requires further work.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: Quantum circuits, Grover query/amplitude analysis, Shor order-finding resource discussion; §IV BQP/resource/oracle model, §V QMA promises and 2-local Hamiltonian Theorem 8; historical survey. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-grover-query-speedup
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference