What is recorded here?
Boyer, Brassard, Hoyer and Tapp analyze quantum-search success after a specified number of iterations and give a randomized procedure with order sqrt(N/t) expected query cost when the positive number t of marked items is unknown. A quantum search can fail because it runs too long, not only because it runs too briefly. BBHT derive an explicit success curve, allowing useful stopping points when the number of marked items is known. When that number is unknown, they randomize the iteration count and gradually enlarge its range, checking the observed candidate before continuing. The expected query cost scales with the square root of the ratio of candidates to solutions, under the stated oracle model. Large solution fractions can be handled by ordinary sampling. If no solution exists, a timeout gives a bounded-error absence decision, not an unconditional proof that a solution is impossible. The same 1996 preprint sketches approximate quantum counting but explicitly leaves important details for further work. This entry credits the analysis and unknown-count search procedure, while the underlying search iteration remains Grover's contribution.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The target is the May 1996 preprint. The unknown-count procedure randomizes iteration counts, grows their range and checks observed candidates in the coherent unit-query oracle model. For a positive number t of marked items, its expected cost is O(sqrt(N/t)), not a deterministic deadline for every run. A zero-solution timeout is a bounded-error decision, not an unconditional absence proof. The counting section is a sketch rather than the complete later amplitude-estimation theory. Grover’s underlying iteration and earlier lower-bound work retain separate credit.
Read the original work
- Boyer, Brassard, Hoyer and Tapp, Tight bounds on quantum searching, exact1996arXivv1
- Grover, A fast quantum mechanical algorithm for database search, exact1996arXivv3
- BBHT exactv1 repository identity and complete4author byline
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
BBHT: how to stop quantum search without knowing the solution count
Boyer, Brassard, Hoyer and Tapp analyze quantum-search success after a specified number of iterations and give a randomized procedure with order sqrt(N/t) expected query cost when the positive number t of marked items is unknown.
A quantum search can fail because it runs too long, not only because it runs too briefly. BBHT derive an explicit success curve, allowing useful stopping points when the number of marked items is known. When that number is unknown, they randomize the iteration count and gradually enlarge its range, checking the observed candidate before continuing. The expected query cost scales with the square root of the ratio of candidates to solutions, under the stated oracle model. Large solution fractions can be handled by ordinary sampling. If no solution exists, a timeout gives a bounded-error absence decision, not an unconditional proof that a solution is impossible. The same 1996 preprint sketches approximate quantum counting but explicitly leaves important details for further work. This entry credits the analysis and unknown-count search procedure, while the underlying search iteration remains Grover's contribution.
Scientific scope
The target is the May 1996 preprint. The unknown-count procedure randomizes iteration counts, grows their range and checks observed candidates in the coherent unit-query oracle model. For a positive number t of marked items, its expected cost is O(sqrt(N/t)), not a deterministic deadline for every run. A zero-solution timeout is a bounded-error decision, not an unconditional absence proof. The counting section is a sketch rather than the complete later amplitude-estimation theory. Grover’s underlying iteration and earlier lower-bound work retain separate credit.
People and systems
Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp