A Fast Quantum Mechanical Algorithm for Database Search

Lov K. Grover · STOC / arXiv · 1996 · quantum-computing · 10.1145/237814.237866 · record grover1996-search
tag layer · index · concepts · authors · עברית

Where this record's text came from. faceted 2026-08 by reading the locally held text (pdftext); every evidence string verified as an exact substring of that text before merging. The pdftext extraction is heavily OCR-damaged: two-column text is interleaved sentence-by-sentence, and mathematical notation is destroyed (sqrt(N) appears variously as 'O ( JN)', 'O ( fi)', 'O (~~', 'Q ( J7i7is'; the success probability 1/2 is lost entirely from 'the final state is SV with a probability of at least ~.'). Every quote above was substring-verified against the file, so the mangling is faithful, not mine — but it means the evidence for claim type reads as gibberish where the complexity bound should be. method: no suggested vocabulary term fits a paper that constructs an algorithm and proves five theorems about it with no implementation or experiment, so I used 'algorithm-design-and-proof'. A fourth self-stated limitation exists — the closing note that noise and error correction remain open ('design of error still remains an unsolved problem.') — but the surrounding sentence is so scrambled by the column interleaving that no coherent verbatim sentence can be lifted, so I left it out rather than quote a fragment whose referent is unrecoverable. Claim relations: only the [BBBV94] lower-bound relation is stated as an explicit relation to named prior work; the mentions of [Shor94], [Simon93], [DJ92], [MVV87] and [VV86] are background or future-work citations, and the [Shor94] passages are additionally too garbled to quote, so per the rule I did not infer relations from them. 2026-08-17 schema-0.3 pass: every quote verified as an exact substring of the staged text and anchored at merge time; concept terms verified present; every edge endpoint an existing node. Update, 15 September 2026: EXCEPTION, measured with the merge gate's own predicate (Paper.locate): 11 quote(s) on this record are not found as one exact string in the current staged text - claim_relations[0].evidence, content_tags.definitions[0].evidence, content_tags.definitions[1].evidence, content_tags.findings[0].evidence, content_tags.quantities[0].evidence, content_tags.quantities[1].evidence, content_tags.quantities[2].evidence, content_tags.statistics[0].evidence, content_tags.variables[0].evidence, content_tags.variables[1].evidence, mechanisms[0].evidence. The sentence above does not hold for them as written. Where a row records why - the quote is grounded in another copy of the paper, joins two passages with an ellipsis, or differs from the staged text by extraction noise - that note stays on the row.

6 quotes on this page were cut from a different copy of this article. This project holds two extractions of this paper: the plain text every other quote here is anchored in, and the publisher’s own HTML edition, which we are not licensed to republish. They are verbatim in the second and cannot be found in the first — not because the tagging is wrong, but because the extraction damaged the passage: a page number dropped into the middle of a number, a formula moved out of its sentence, a ligature where two letters belong. The record names the copy for each one. The quote is the paper’s; the extraction is not.

How to read this page. The article itself is not reproduced here — this paper is not cleared for redistribution, so what follows is the tag layer alone. The evidence sentences are withheld with the article. The table at the foot lists every tag the record carries; each row names the facet it belongs to, and the whose words column says whether the tag records the paper's own wording or the tagger's sentence about the paper. Every tag links to each other paper in the corpus carrying it. The machine-readable edition of the same thing is the TEI file beside this one, where the tags live in standOff, and the article is at its publisher via the link below. When we have changed our mind. Some entries in the table begin with a word in capitals and the reason for it. EVIDENCE CORRECTED — the finding still stands, but we had quoted the wrong sentence from the paper, and the quotation has been replaced with the right one. RETRACTED — the entry itself was wrong; it stays on the page, marked, with the reason, rather than being deleted. WITHDRAWN AND REPLACED — the entry was wrong, and a corrected version of it appears in the entries below. Each mark carries its own reason, in brackets, because the reasons differ from one entry to the next. An entry we have WITHDRAWN is removed from this page and kept in the record, with its reason. A line reading Audit and a date is a later re-reading of the entry against its whole sentence: DOUBTFUL means it was kept, and the reason says what is loose about it. Quotation marks inside the tagger's sentence. Where a tag is the tagger's own sentence, a phrase in quotation marks inside it is borrowed from the paper — the tagger's wording around it is not. The paper's own sentence is the evidence quote for that row; on this page it is withheld with the article, and the article is at its publisher. Nothing inside quotation marks anywhere on this page is ours: if it is quoted, it is the paper's. Whose words a concept carries. A concept entry records a term the paper itself uses, so the term, the sense given for it, and its evidence are the paper's own words, quoted where the paper fixes them. This is the opposite of a sense entry in the tag table, which is the tagger's sentence about how the paper uses a term. Where a concept entry could not be grounded in the paper's words, the entry says so on its own row.

Other fields define these differently the same word, defined another way in another discipline
algorithm 5 fields

Tags on this paper

Every tag the record carries, each linking to every other paper in the corpus that carries it. A tag appears here whether or not its words occur in the article — the spans below are only the ones a sentence in this paper licenses. Of the 4 concept tags on this paper, none is grounded in a quoted sentence.

quantum algorithm quantum search amplitude amplification quadratic speedup amplitude amplification: begin in an equal superposition over all N items, then repeatedly increase the amplitude of the target state so that after about sqrt(N) iterations a measurement finds it with high probability THE PROBLEM'S WHOLE COST MODEL RESTS ON ONE STIPULATION ABOUT VERIFICATION, STATED IN A SINGLE SENTENCE: Quotation withheld Checking is free and finding is expensive - and the separation between the two is what makes `search` a measurable quantity at all. The stipulation is not defended; it defines the object A RESULT IS CALLED IMPORTANT AND UNSURPRISING IN THE SAME BREATH, WITH THE REASON DRAWN FROM PHYSICS RATHER THAN FROM COMPUTATION: quantum mechanical computers were shown to be at least as powerful as classical computers - AN IMPORTANT BUT NOT SURPRISING RESULT, SINCE CLASSICAL COMPUTERS, AT THE DEEPEST LEVEL, ULTIMATELY FOLLOW THE LAWS OF QUANTUM MECHANICS. The surprisingness of a theorem is assessed by an argument from what the machines are made of A FORMALISATION IS DATED, ATTRIBUTED, AND ITS SUPERIORITY CLAIM IS SCOPED IN THE SAME SENTENCE: THE DESCRIPTION OF QUANTUM MECHANICAL COMPUTERS WAS FORMALIZED IN THE LATE 80s AND EARLY 90s and they were shown to be more powerful than classical computers ON VARIOUS SPECIALIZED PROBLEMS. The word `formalized` is given a date and four citations, and the advantage is restricted to a class of problems rather than asserted in general OPTIMALITY IS CLAIMED BY CITING SOMEONE ELSE'S LOWER BOUND, AND THE BOUND'S OWN CONDITION IS QUOTED WITH IT: THERE IS A MATCHING LOWER BOUND on how fast the desired item can be identified - another paper shows what is needed IN ORDER TO IDENTIFY THE DESIRED ELEMENT, WITHOUT ANY INFORMATION ABOUT THE STRUCTURE OF THE DATABASE. The optimality claim carries its own condition - an absence of structure - and the condition travels with the claim in the same sentence rather than being left to a reader quantum amplitude superposition unitary algorithm database probability states phase unsorted database N number of steps mean average of mathematical-proof

Method, as described: algorithm-design-and-proof

Legend

relation to other work	`claim_relations`	how this paper stands to another: agrees, contradicts, extends, qualifies
claim type	`claim_type`	the shape of the claim: existence, mechanism, method, critique, prediction, null
limitation	`limitations`	what the paper says its evidence cannot support
mechanism	`mechanisms`	how the reported effect is said to come about
method	`method`	how the paper produced its evidence
phenomenon	`phenomenon`	the effect or regularity under study

The paper

The full text is not reproduced here. This article is not cleared for redistribution, so the page carries the tag layer only. Its evidence sentences are withheld; the grounding status remains with each tag, and the article itself is at https://doi.org/10.1145/237814.237866. The reading view exists for the papers whose licence permits it.

Every tag on this page

claim_relations 1 · claim_type 1 · limitations 4 · mechanisms 4 · method 1 · phenomenon 1

This record holds no relations between concepts, controls or senses of a term. A layer is empty when the tagger recorded nothing in it — which is not the same as the paper having nothing to record.

facet	tag	field	conf.	whose words
claim_type	method Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: THE FORMULA IS GARBLED IN THE EXTRACTED TEXT: 'O (~~' stands for the paper's O(√N), so the bracket it opens never closes in this copy; the rest of the sentence is quoted as printed.	`claim_type`		the paper's words
phenomenon	unstructured database search Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`phenomenon`		the paper's words
method	mathematical-proof Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: mathematical-proof	`method`		the paper's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: THE STAGED TEXT OF THIS PAPER IS A TWO-COLUMN SCRAMBLE (damage shape 5), which has no detector: every token in a reordered sentence is a real word. This span was verified BY READING that it is continuous English, after a token test had reduced 140 sentences to 55 and reading reduced 55 to 4. Neighbouring text is interleaved and must not be quoted without the same check. also in: THE PROBLEM'S WHOLE COST MODEL RESTS ON ONE STIPULATION ABOUT VERIFICATION, STATED IN A SINGLE SENTENCE: Quotation withheld Checking is free and finding is expensive - and the separation between the two is what makes `search` a measurable quantity at all. The stipulation is not defended; it defines the object	`mechanisms[1]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: THE STAGED TEXT OF THIS PAPER IS A TWO-COLUMN SCRAMBLE (damage shape 5), which has no detector: every token in a reordered sentence is a real word. This span was verified BY READING that it is continuous English, after a token test had reduced 140 sentences to 55 and reading reduced 55 to 4. Neighbouring text is interleaved and must not be quoted without the same check. also in: A RESULT IS CALLED IMPORTANT AND UNSURPRISING IN THE SAME BREATH, WITH THE REASON DRAWN FROM PHYSICS RATHER THAN FROM COMPUTATION: quantum mechanical computers were shown to be at least as powerful as classical computers - AN IMPORTANT BUT NOT SURPRISING RESULT, SINCE CLASSICAL COMPUTERS, AT THE DEEPEST LEVEL, ULTIMATELY FOLLOW THE LAWS OF QUANTUM MECHANICS. The surprisingness of a theorem is assessed by an argument from what the machines are made of	`mechanisms[2]`	0.85	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: THE STAGED TEXT OF THIS PAPER IS A TWO-COLUMN SCRAMBLE (damage shape 5), which has no detector: every token in a reordered sentence is a real word. This span was verified BY READING that it is continuous English, after a token test had reduced 140 sentences to 55 and reading reduced 55 to 4. Neighbouring text is interleaved and must not be quoted without the same check. also in: A FORMALISATION IS DATED, ATTRIBUTED, AND ITS SUPERIORITY CLAIM IS SCOPED IN THE SAME SENTENCE: THE DESCRIPTION OF QUANTUM MECHANICAL COMPUTERS WAS FORMALIZED IN THE LATE 80s AND EARLY 90s and they were shown to be more powerful than classical computers ON VARIOUS SPECIALIZED PROBLEMS. The word `formalized` is given a date and four citations, and the advantage is restricted to a class of problems rather than asserted in general	`mechanisms[3]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: THE STAGED TEXT OF THIS PAPER IS A TWO-COLUMN SCRAMBLE (damage shape 5), which has no detector: every token in a reordered sentence is a real word. This span was verified BY READING that it is continuous English, after a token test had reduced 140 sentences to 55 and reading reduced 55 to 4. Neighbouring text is interleaved and must not be quoted without the same check. also in: OPTIMALITY IS CLAIMED BY CITING SOMEONE ELSE'S LOWER BOUND, AND THE BOUND'S OWN CONDITION IS QUOTED WITH IT: THERE IS A MATCHING LOWER BOUND on how fast the desired item can be identified - another paper shows what is needed IN ORDER TO IDENTIFY THE DESIRED ELEMENT, WITHOUT ANY INFORMATION ABOUT THE STRUCTURE OF THE DATABASE. The optimality claim carries its own condition - an absence of structure - and the condition travels with the claim in the same sentence rather than being left to a reader	`mechanisms[4]`	0.85	the tagger's words
limitations	the quadratic speedup is optimal - a matching lower bound limits how fast the item can be found Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: any expectation of further speedup: THERE IS A MATCHING LOWER BOUND ON HOW FAST THE DESIRED ITEM CAN BE IDENTIFIED	`limitations[0]`		the tagger's words
limitations	The algorithm exploits no structure in the problem or database. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the generality claim, and note our staged text is damaged here: THE ALGORITHM THIS PAPER DOES NOT USE ANY IMOWLEDGE OF PROBLEM [OCR for 'knowledge'] - no problem structure is exploited	`limitations[1]`		the tagger's words
limitations	The algorithm as presented assumes exactly one state satisfies the condition; the multiple-solution case needs modification. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the single-solution presentation: the algorithm as given assumes exactly one state satisfies the condition, and the multiple-solution case needs separate treatment	`limitations[2]`		the tagger's words
limitations	The O(sqrt(N)) speedup falls short of what would be needed to give polynomial-time algorithms for NP-complete problems. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the strongest reading of the speedup: IF IT WERE POSSIBLE TO REDUCE THE NUMBER OF STEPS TO A FINITE POWER OF O(log N) (INSTEAD OF O(sqrt N) AS IN THIS PAPER), FOR NP-COMPLETE PROBLEMS IT WOULD YIELD A POLYNOMIAL TIME ALGORITHM - and it does not	`limitations[3]`		the tagger's words
claim_relations	builds-on → [BBBV94] (the Omega(sqrt(N)) quantum query lower bound) Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: THE FORMULA IS GARBLED IN THE EXTRACTED TEXT: 'Cl ( ~~' stands for the paper's Ω(√N), so the bracket it opens never closes in this copy; the rest of the sentence is quoted as printed.	`claim_relations[1]`		the tagger's words

Interpretive choices

Tags that could not be placed in the text:

mechanisms[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
this quote's status: quote-not-in-current-staged-text · about this quote: tagged against an earlier extraction of this paper; the staged file has since changed. The claim may still be sound - the QUOTE is unanchorable. Not deleted, not repaired, not verified. · NOT MACHINE-VOUCHED: not-in-our-copy - The quote is in the original page we fetched for this paper ('fulltext.html'), but not in the text we tag against, which was extracted differently. Checked with ligatures, hyphens, spacing and punctuation set aside. This body carries 1 intra-word spaces.
claim_relations[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
this quote's status: quote-not-in-current-staged-text · about this quote: tagged against an earlier extraction of this paper; the staged file has since changed. The claim may still be sound - the QUOTE is unanchorable. Not deleted, not repaired, not verified., 2026-08-15: the quote IS present, verbatim once whitespace is normalised, in the web page we fetched. The staged text this flag refers to is a lossier extraction of the same paper, so the tag is UNVERIFIED AGAINST THE FILE THE VERIFIER READS rather than unverifiable. Re-staging would move every offset and hash on the record and is a staging decision, not a tagging one. · NOT MACHINE-VOUCHED: not-in-our-copy - The quote is in the original page we fetched for this paper ('fulltext.html'), but not in the text we tag against, which was extracted differently. Checked with ligatures, hyphens, spacing and punctuation set aside. This body carries 1 intra-word spaces.
content_tags.quantities[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: restored-notation - The quote comes from the web page we fetched for this paper, which drops the symbol: it reads 'can be obtained in only steps', with a stray 'O N(' a sentence later. The square brackets in '[O(√N)]' mark the symbol as supplied by us, as scholarly quotation does. The text we tag against, a different copy of the paper, does not contain this sentence.
content_tags.quantities[1] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: restored-notation - The quote gives the paper's fraction, 'a minimum of N/2 names'. The web page we fetched prints it as 'a minimum of N ---- 2 names', and the text we tag against, a different copy of the paper, does not contain this sentence.
content_tags.quantities[2] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: restored-notation - The quote gives the paper's fraction, 'at least 1/2'. The web page we fetched prints it as 'at least 1 --- 2', and the text we tag against, a different copy of the paper, words the sentence differently and prints the fraction as 'at least ~. 2'.
content_tags.findings[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: not-in-our-copy - The quote is in the original web page we fetched for this paper, but not in the text we tag against, which was extracted differently. Checked with ligatures, hyphens, spacing and punctuation set aside.
content_tags.variables[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
this quote's status: quote-not-in-current-staged-text · about this quote: marked quote-not-in-current-staged-text - today's merge gate would REFUSE this quote: Paper.locate() does not find it in the current staged text. · NOT MACHINE-VOUCHED: not-in-our-copy - The quote is in the original page we fetched for this paper ('fulltext.html'), but not in the text we tag against, which was extracted differently. Checked with ligatures, hyphens, spacing and punctuation set aside. This body carries 1 intra-word spaces.
content_tags.variables[1] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
this quote's status: quote-not-in-current-staged-text · about this quote: marked quote-not-in-current-staged-text - today's merge gate would REFUSE this quote: Paper.locate() does not find it in the current staged text. · NOT MACHINE-VOUCHED: restored-notation - The same sentence as another tag on this paper: the web page we fetched prints it without the symbol ('can be obtained in only steps'), and '[O(√N)]' in square brackets is supplied by us. The text we tag against, a different copy of the paper, does not contain this sentence.
content_tags.definitions[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
this quote's status: quote-not-in-current-staged-text · about this quote: marked quote-not-in-current-staged-text - today's merge gate would REFUSE this quote: Paper.locate() does not find it in the current staged text. · NOT MACHINE-VOUCHED: not-in-our-copy - The quote is in the original page we fetched for this paper ('fulltext.html'), but not in the text we tag against, which was extracted differently. Checked with ligatures, hyphens, spacing and punctuation set aside. This body carries 1 intra-word spaces.
content_tags.definitions[1] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
this quote's status: quote-not-in-current-staged-text · about this quote: marked quote-not-in-current-staged-text - today's merge gate would REFUSE this quote: Paper.locate() does not find it in the current staged text. · NOT MACHINE-VOUCHED: not-in-our-copy - The quote is in the original page we fetched for this paper ('fulltext.html'), but not in the text we tag against, which was extracted differently. Checked with ligatures, hyphens, spacing and punctuation set aside. This body carries 1 intra-word spaces.
content_tags.statistics[0] — quotation withheld — the page has already reproduced as much of this paper as the rights budget allows
NOT MACHINE-VOUCHED: restored-notation - The quote puts the fraction N/2 back where the paper has it. The web page we fetched prints the fraction on a line of its own, which lands it after 'seen': 'It is easily seen N ---- 2 that this algorithm will need to look at an average of items'. The text we tag against, a different copy of the paper, has a damaged, differently worded version of the sentence without the fraction.

What was deliberately not tagged, and why, is recorded per paper by the tagger. Where a paper has no such record, this page says so rather than implying that nothing was declined.