phenomenon · claim-type · cross-domain-transfer · mechanism · claim-relation · replication-status · limitation — grounded in the full text| phenomenon | unstructured database search— “Let there be a unique state, say Sv, that satisfies the condition C(SV) = 1, whereas for all other states S, C(S) = 0 (assume that for any state S, the condition C(S) can be evaluated in unit time), The problem is to identify the state SV.” | |
| claim-type | method— “This paper presents an O (~~ step algorithm for the above problem.” | |
| method — evidence | — “First, it is proved that the system is a valid quantum mechanical system (theorems 1 & 2) and, second, that it converges to the desired state (theorems 3, 4 & 5)” | |
| mechanism | 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— “Each iteration of this loop increases the amplitude in the desired state” [UNVERIFIED AGAINST THE STAGED TEXT] | mechanisms[0] |
| mechanism | THE PROBLEM'S WHOLE COST MODEL RESTS ON ONE STIPULATION ABOUT VERIFICATION, STATED IN A SINGLE SENTENCE: ONCE AN ITEM IS EXAMINED, IT IS POSSIBLE TO TELL WHETHER OR NOT IT SATISFIES THE CONDITION IN ONE STEP. 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— “Once an item is examined, it is possible to tell whether or not it satisfies the condition in one step.” | mechanisms[1] |
| mechanism | 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— “Quantum mechanical computers were proposed in the early 1980’s [Benioff80] and 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.” | mechanisms[2] |
| mechanism | 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— “The description of quantum mechanical computers was formalized in the late 80’s and early 90’s [Deutsch85][BB92] [BV93] [Yao93] and they were shown to be more powerful than classical computers on various specialized problems.” | mechanisms[3] |
| mechanism | 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— “There is a matching lower bound on how fast the desired item can be identified. [BBBV94] show in their paper that in order to identify the desired element, without any information about the structure of the database” | mechanisms[4] |
| builds-on | classical probabilistic algorithms— “Just like classical probabilistic algorithms, quantum mechanical algorithms work with a probability distribution over various states.” [UNVERIFIED AGAINST THE STAGED TEXT] | claim_relations[0] |
| builds-on | [BBBV94] (the Omega(sqrt(N)) quantum query lower bound)— “[BBBV94] show in their paper that in order to identify the desired element, without any information about the structure of the database, a quantum mechanical system will need at least Cl ( ~~ steps.” | claim_relations[1] |
| evidence status | classical probabilistic algorithms — quote-not-in-current-staged-text— “Just like classical probabilistic algorithms, quantum mechanical algorithms work with a probability distribution over various states.” [UNVERIFIED AGAINST THE STAGED TEXT] | claim_relations[0] |
| evidence status note | classical probabilistic algorithms — 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.— “Just like classical probabilistic algorithms, quantum mechanical algorithms work with a probability distribution over various states.” [UNVERIFIED AGAINST THE STAGED TEXT] | claim_relations[0] |
| not machine-vouched | classical probabilistic algorithms — 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.— “Just like classical probabilistic algorithms, quantum mechanical algorithms work with a probability distribution over various states.” [UNVERIFIED AGAINST THE STAGED TEXT] | claim_relations[0] |
| evidence status note | [BBBV94] (the Omega(sqrt(N)) quantum query lower bound) — 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] |
| for which use | limitation — any expectation of further speedup: THERE IS A MATCHING LOWER BOUND ON HOW FAST THE DESIRED ITEM CAN BE IDENTIFIED | limitations[0] |
| for which use | limitation — 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] |
| for which use | limitation — 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] |
| for which use | limitation — 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 Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[3] |
| evidence status | mechanism — quote-not-in-current-staged-text Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[0] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[0] |
| not machine-vouched | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[0] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[1] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[2] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[3] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[4] |
| replication | untested | |
| evidence status note | claim-type — 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. | |
| limitation | the quadratic speedup is optimal - a matching lower bound limits how fast the item can be found Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[0] |
| limitation | The algorithm exploits no structure in the problem or database. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[1] |
| limitation | The algorithm as presented assumes exactly one state satisfies the condition; the multiple-solution case needs modification. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[2] |
| limitation | The O(sqrt(N)) speedup falls short of what would be needed to give polynomial-time algorithms for NP-complete problems. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[3] |
finding · quantity · variable · definition · key-term — grounded in the full text| finding | The algorithm is significantly faster than any classical algorithm can be. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.findings[0] |
| not machine-vouched | finding — 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.findings[0] |
| quantity | O(√N) steps — quantum search time to find the marked item (quadratic speedup) Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.quantities[0] |
| not machine-vouched | quantity — 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[0] |
| quantity | N/2 — classical lower bound: names any classical algorithm must examine on average Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.quantities[1] |
| not machine-vouched | quantity — 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[1] |
| quantity | ≥ 1/2 — success probability of the final measurement Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.quantities[2] |
| not machine-vouched | quantity — 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.quantities[2] |
| variable | N (independent) Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.variables[0] |
| evidence status note | variable — 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. | content_tags.variables[0] |
| not machine-vouched | variable — 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[0] |
| variable | number of steps (dependent) Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.variables[1] |
| evidence status note | variable — 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. | content_tags.variables[1] |
| not machine-vouched | variable — 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.variables[1] |
| definition | unsorted database Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.definitions[0] |
| evidence status note | definition — 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. | content_tags.definitions[0] |
| not machine-vouched | definition — 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[0] |
| definition | amplitude Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.definitions[1] |
| evidence status note | definition — 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. | content_tags.definitions[1] |
| not machine-vouched | definition — 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] |
| key-terms | quantum, amplitude, superposition, unitary, algorithm, database, probability, states, phase |
| mean μ | as written: average of Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.statistics[0] |
| not machine-vouched | mean — 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. | content_tags.statistics[0] |
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.
Tag layer © the Meta-Tagging Project, CC BY 4.0. The paper text is © its authors/publisher
and is linked, not reproduced. Excerpts shown are short quotations for identification and verification.
· back to index
· concepts · authors
· עברית
© 2026 Shir Sivroni · ORCID 0009-0000-2597-2824