Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Peter W. Shor · SIAM Journal on Computing / arXiv · 1997 · quantum-computing · 10.1137/S0097539795293172 · record shor1997-factoring
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. method has no match in the suggested vocabulary: nothing is built or simulated, the work is algorithm construction plus running-time and success-probability analysis for a machine the paper itself says does not exist, so 'algorithm-design' is used. The final claim_relation quote is a contiguous two-sentence span from the abstract, copied unbroken; it is included because the single closing sentence is uninterpretable alone. Replication status 'untested' - the paper reports no implementation and no independent confirmation. Text is an arXiv/SIAM PDF extraction in which mathematical notation is badly mangled (symbols such as the congruence sign are displaced), so quotes were chosen from prose passages where the extraction is clean. 2026-08-15 and 2026-08-17 schema-0.3 passes: 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.

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
precision 10 fields · 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 9 concept tags on this paper, 5 are grounded in a quoted sentence.

quantum algorithm integer factorization discrete logarithm quantum Fourier transform precision quantum computer Church’s thesis physical reasonable A THESIS'S VALUE IS ITS ECONOMY, AND THE ECONOMY IS STATED AS THE REASON: Church's thesis GREATLY SIMPLIFIES THE STUDY OF COMPUTATION, SINCE IT REDUCES THE POTENTIAL FIELD OF STUDY FROM AN INFINITE NUMBER OF POTENTIAL COMPUTING DEVICES TO TURING MACHINES. What is claimed for it first is not its truth but what it lets one stop studying FORMALISING A CLAIM WOULD MAKE IT WEAKER, AND THE MECHANISM IS GIVEN: the thesis IS NOT A MATHEMATICAL THEOREM, and to make it one WOULD REQUIRE A PRECISE MATHEMATICAL DESCRIPTION of a computing device - which WOULD LEAVE OPEN THE POSSIBILITY of some practical device NOT SATISFYING that description, and so WOULD MAKE THE RESULTING THEOREM WEAKER THAN THE ORIGINAL THESIS. A formalism can be escaped in a way an informal claim cannot A CATEGORY IS INTRODUCED EXPLICITLY AS A COMPROMISE BETWEEN TWO UNUSABLE GRAINS: the old distinction is MUCH TOO COARSE, the exact efficiency is TOO PRECISE A QUANTITY TO WORK WITH EASILY, and what the field uses is THE GENERALLY ACCEPTED COMPROMISE BETWEEN COARSENESS AND PRECISION - polynomial versus superpolynomial scaling. The class P is presented as a negotiated grain, not a natural joint THE CLASSIFICATION IS SHOWN TO REQUIRE A FURTHER THESIS BEFORE IT MEANS ANYTHING: FOR THIS CLASSIFICATION TO MAKE SENSE, WE NEED IT TO BE MACHINE-INDEPENDENT - we need to know that polynomial-time computability does not depend on the kind of device used - and that requirement IS a quantitative version of Church's thesis. A definition resting on an unproved claim about the world ONE CLAIM CARRIES THREE NAMES ACROSS THREE LITERATURES, AND ONE OF THEM ONLY PARTLY: the same thesis has been CALLED THE STRONG CHURCH'S THESIS by one group, and MAKES UP HALF OF THE INVARIANCE THESIS of another author. Two vocabularies name it whole, a third contains it as a part - which is a partial overlap between naming systems, not a synonym A READER-FACING SUBSTITUTION IS OFFERED AND JUSTIFIED BY MUTUAL SIMULATION: readers NOT COMFORTABLE WITH Turing machines MAY THINK INSTEAD OF digital computers with linearly growing memory, BECAUSE THESE TWO CLASSES CAN EFFICIENTLY SIMULATE EACH OTHER. One object is licensed to stand in for another, and the licence is an equivalence THE THESIS'S ESCAPE CLAUSES ARE LOCATED IN TWO SPECIFIC WORDS AND NAMED AS SUCH: THERE ARE TWO ESCAPE CLAUSES IN THE ABOVE THESIS - ONE OF THESE IS THE WORD PHYSICAL, and machine models that violate the thesis HAVE BEEN RULED OUT BY SOME REASON FOR WHY THEY ARE NOT PHYSICAL, that is, why they could not be built and made to work. A single underdefined word is doing the excluding AND THE SECOND ESCAPE CLAUSE IS A WORD WHOSE MEANING IS SAID TO BE INCOMPLETELY SPECIFIED: THE OTHER ESCAPE CLAUSE IS THE WORD RESOURCES, THE MEANING OF WHICH IS NOT COMPLETELY SPECIFIED - after which the resources are enumerated for digital computers, and MORE are said to be pertinent to analog computation. The thesis's content varies with a list nobody has closed A NEW RESOURCE IS ADDED TO THE ACCOUNTING AND THE ADDITION IS ARGUED FOR: for quantum computation, IN ADDITION TO SPACE AND TIME, THERE IS ALSO A THIRD POTENTIALLY IMPORTANT RESOURCE, PRECISION - and the argument is that the changes a quantum computer makes CAN CLEARLY NOT BE PERFECTLY ACCURATE but MUST CONTAIN SOME SMALL AMOUNT OF INHERENT IMPRECISION. The bookkeeping is extended because the physics forces a third column WHAT SETS THE LIMIT IS ATTRIBUTED TO MATERIALS RATHER THAN TO PHYSICAL LAW, WITH THE HEDGE STATED: AS FAR AS WE KNOW, what precision is possible IS DICTATED NOT BY FUNDAMENTAL PHYSICAL LAWS BUT BY THE PROPERTIES OF THE MATERIALS AND THE ARCHITECTURE with which the computer is built - and IT IS CURRENTLY NOT CLEAR which architectures will give high precision A MODELLING CHOICE IS DEFENDED AGAINST A TRUE DESCRIPTION, AND THE GROUND IS USEFULNESS: treating precision as a large constant - EVEN THOUGH IT IS ALMOST CERTAIN TO BE CONSTANT FOR ANY GIVEN MACHINE - is compared to treating a digital computer as a finite automaton, of which the verdict is THIS VIEW IS TECHNICALLY CORRECT; HOWEVER, IT IS NOT PARTICULARLY USEFUL. A description can be accurate and the wrong one to adopt A KEY WORD IS FOUND SUBSTITUTED IN ANOTHER AUTHOR'S STATEMENT OF THE SAME THESIS, AND THE SUBSTITUTION IS DIAGNOSED: in one restatement THE WORD PHYSICAL IS REPLACED WITH THE WORD REASONABLE - and IT IS DIFFICULT TO IMAGINE ANY DEFINITION OF REASONABLE IN THIS CONTEXT WHICH DOES NOT MEAN PHYSICALLY REALIZABLE. One word swapped for another in the same claim, and the author argues they must come to the same thing A THESIS IS BELIEVED ON THE STRENGTH OF FAILED REFUTATIONS, AND THE FAILURES ARE THEN SHOWN TO SHARE A PROPERTY: computer scientists became convinced THROUGH THE FAILURE OF ALL PROPOSED COUNTER-EXAMPLES - but MOST OF THESE HAVE BEEN BASED ON THE LAWS OF CLASSICAL MECHANICS, HOWEVER THE UNIVERSE IS IN REALITY QUANTUM MECHANICAL. The induction's instances share exactly the property the new case lacks PRIORITY IS ASSIGNED BY THE EXPLICITNESS OF A QUESTION RATHER THAN BY THE IDEA, AND ONE AUTHOR IS CREDITED FOR WHAT HE DID NOT ASK: one researcher DID NOT ASK whether quantum mechanics conferred extra power AND YET showed enough to make later work possible; another RAISED THE POSSIBILITY, THUS IMPLICITLY ASKING the converse question; and a third WAS THE FIRST TO ASK THIS QUESTION EXPLICITLY factoring quantum algorithm computer integer polynomial logarithms prime factorization quantum order-finding algorithm factoring integers discrete logarithms input size number of steps mathematical-proof

Method, as described: algorithm-design

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
concept edge	`concept_edges`	an asserted relation between two concepts, with the sentence asserting it
concept	`concepts`	an idea the paper works with, quoted where the paper uses it
content tag	`content_tags`	a finding, definition, quantity, statistic or variable named in the paper
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
sense	`senses`	a distinct use of a term, quoted where the paper fixes it
transfer	`transfers`	a method or concept carried in from another field
unrecordable relation	`unhoused_relations`	a relation the paper asserts that this vocabulary cannot express, with the reason

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.1137/S0097539795293172. The reading view exists for the papers whose licence permits it.

Every tag on this page

claim_relations 7 · claim_type 1 · concept_edges 1 · concepts 5 · content_tags 8 · limitations 7 · mechanisms 14 · method 1 · phenomenon 1 · senses 2 · transfers 1 · unhoused_relations 1

Relations on this page carry a quotation for the claim. Where a relation was separately evidenced — and so tested against the vocabulary for its type — the row says so; none of 1 relation here carry that mark. The rest are the tagger’s reading of the sentence quoted beside them.

This record holds no controls. 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.	`claim_type`		the paper's words
phenomenon	prime factorization and discrete logarithms on a quantum computer 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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: A THESIS'S VALUE IS ITS ECONOMY, AND THE ECONOMY IS STATED AS THE REASON: Church's thesis GREATLY SIMPLIFIES THE STUDY OF COMPUTATION, SINCE IT REDUCES THE POTENTIAL FIELD OF STUDY FROM AN INFINITE NUMBER OF POTENTIAL COMPUTING DEVICES TO TURING MACHINES. What is claimed for it first is not its truth but what it lets one stop studying	`mechanisms[0]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: FORMALISING A CLAIM WOULD MAKE IT WEAKER, AND THE MECHANISM IS GIVEN: the thesis IS NOT A MATHEMATICAL THEOREM, and to make it one WOULD REQUIRE A PRECISE MATHEMATICAL DESCRIPTION of a computing device - which WOULD LEAVE OPEN THE POSSIBILITY of some practical device NOT SATISFYING that description, and so WOULD MAKE THE RESULTING THEOREM WEAKER THAN THE ORIGINAL THESIS. A formalism can be escaped in a way an informal claim cannot	`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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: A CATEGORY IS INTRODUCED EXPLICITLY AS A COMPROMISE BETWEEN TWO UNUSABLE GRAINS: the old distinction is MUCH TOO COARSE, the exact efficiency is TOO PRECISE A QUANTITY TO WORK WITH EASILY, and what the field uses is THE GENERALLY ACCEPTED COMPROMISE BETWEEN COARSENESS AND PRECISION - polynomial versus superpolynomial scaling. The class P is presented as a negotiated grain, not a natural joint	`mechanisms[2]`	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: RE-SLICED: the first cut ended "...quantitative version of Church", stopping INSIDE THE NAME. The cut-word guard did not catch it because the next character is a curly apostrophe, not a letter - so `Church` + `’s` reads as a clean word boundary to the check. A span must not end inside a person's name either, and no guard currently tests that. PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: `PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b` matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: THE CLASSIFICATION IS SHOWN TO REQUIRE A FURTHER THESIS BEFORE IT MEANS ANYTHING: FOR THIS CLASSIFICATION TO MAKE SENSE, WE NEED IT TO BE MACHINE-INDEPENDENT - we need to know that polynomial-time computability does not depend on the kind of device used - and that requirement IS a quantitative version of Church's thesis. A definition resting on an unproved claim about the world	`mechanisms[3]`	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: EXTENDED BACKWARDS: the first cut began "which Vergis et al. [1986] have called..." and never named the thesis it was about. A tag asserting that one claim carries three names has to contain the claim. Overlaps the span of the preceding mechanism, which is allowed and normal. PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: ONE CLAIM CARRIES THREE NAMES ACROSS THREE LITERATURES, AND ONE OF THEM ONLY PARTLY: the same thesis has been CALLED THE STRONG CHURCH'S THESIS by one group, and MAKES UP HALF OF THE INVARIANCE THESIS of another author. Two vocabularies name it whole, a third contains it as a part - which is a partial overlap between naming systems, not a synonym	`mechanisms[4]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: A READER-FACING SUBSTITUTION IS OFFERED AND JUSTIFIED BY MUTUAL SIMULATION: readers NOT COMFORTABLE WITH Turing machines MAY THINK INSTEAD OF digital computers with linearly growing memory, BECAUSE THESE TWO CLASSES CAN EFFICIENTLY SIMULATE EACH OTHER. One object is licensed to stand in for another, and the licence is an equivalence	`mechanisms[5]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: THE THESIS'S ESCAPE CLAUSES ARE LOCATED IN TWO SPECIFIC WORDS AND NAMED AS SUCH: THERE ARE TWO ESCAPE CLAUSES IN THE ABOVE THESIS - ONE OF THESE IS THE WORD PHYSICAL, and machine models that violate the thesis HAVE BEEN RULED OUT BY SOME REASON FOR WHY THEY ARE NOT PHYSICAL, that is, why they could not be built and made to work. A single underdefined word is doing the excluding	`mechanisms[6]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: AND THE SECOND ESCAPE CLAUSE IS A WORD WHOSE MEANING IS SAID TO BE INCOMPLETELY SPECIFIED: THE OTHER ESCAPE CLAUSE IS THE WORD RESOURCES, THE MEANING OF WHICH IS NOT COMPLETELY SPECIFIED - after which the resources are enumerated for digital computers, and MORE are said to be pertinent to analog computation. The thesis's content varies with a list nobody has closed	`mechanisms[7]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: A NEW RESOURCE IS ADDED TO THE ACCOUNTING AND THE ADDITION IS ARGUED FOR: for quantum computation, IN ADDITION TO SPACE AND TIME, THERE IS ALSO A THIRD POTENTIALLY IMPORTANT RESOURCE, PRECISION - and the argument is that the changes a quantum computer makes CAN CLEARLY NOT BE PERFECTLY ACCURATE but MUST CONTAIN SOME SMALL AMOUNT OF INHERENT IMPRECISION. The bookkeeping is extended because the physics forces a third column	`mechanisms[8]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: WHAT SETS THE LIMIT IS ATTRIBUTED TO MATERIALS RATHER THAN TO PHYSICAL LAW, WITH THE HEDGE STATED: AS FAR AS WE KNOW, what precision is possible IS DICTATED NOT BY FUNDAMENTAL PHYSICAL LAWS BUT BY THE PROPERTIES OF THE MATERIALS AND THE ARCHITECTURE with which the computer is built - and IT IS CURRENTLY NOT CLEAR which architectures will give high precision	`mechanisms[9]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: A MODELLING CHOICE IS DEFENDED AGAINST A TRUE DESCRIPTION, AND THE GROUND IS USEFULNESS: treating precision as a large constant - EVEN THOUGH IT IS ALMOST CERTAIN TO BE CONSTANT FOR ANY GIVEN MACHINE - is compared to treating a digital computer as a finite automaton, of which the verdict is THIS VIEW IS TECHNICALLY CORRECT; HOWEVER, IT IS NOT PARTICULARLY USEFUL. A description can be accurate and the wrong one to adopt	`mechanisms[10]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: A KEY WORD IS FOUND SUBSTITUTED IN ANOTHER AUTHOR'S STATEMENT OF THE SAME THESIS, AND THE SUBSTITUTION IS DIAGNOSED: in one restatement THE WORD PHYSICAL IS REPLACED WITH THE WORD REASONABLE - and IT IS DIFFICULT TO IMAGINE ANY DEFINITION OF REASONABLE IN THIS CONTEXT WHICH DOES NOT MEAN PHYSICALLY REALIZABLE. One word swapped for another in the same claim, and the author argues they must come to the same thing	`mechanisms[11]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: A THESIS IS BELIEVED ON THE STRENGTH OF FAILED REFUTATIONS, AND THE FAILURES ARE THEN SHOWN TO SHARE A PROPERTY: computer scientists became convinced THROUGH THE FAILURE OF ALL PROPOSED COUNTER-EXAMPLES - but MOST OF THESE HAVE BEEN BASED ON THE LAWS OF CLASSICAL MECHANICS, HOWEVER THE UNIVERSE IS IN REALITY QUANTUM MECHANICAL. The induction's instances share exactly the property the new case lacks	`mechanisms[12]`	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: PROVENANCE: this record belongs to the priming sub-corpus, which is the other terminal's lane, and these mechanisms were written by the project. No two hands were on the record - it carried no mechanisms before these, and the project confirmed on 2026-08-17 that the project is auditing rather than tagging. Kept rather than retracted on his instruction (17:22): retracting verified work over a bookkeeping flag would leave a retraction reason that misdescribes the row. Recorded here so a reader learns it from the corpus. The flag on this record is a FALSE POSITIVE of the ownership rule, not a judgement about the paper: 'PRIMING_SUBJECT = \bprim(e\|es\|ed\|ing)\b' matched “PRIME factorization” in the title. It carries no priming fields and it is number theory. Released by name on 2026-08-17 17:22 via MANUAL_RELEASED in an internal tool, together with greentao2004-primes and culpepper2020 - which the same rule caught on “the PRIMES” and on a pun about a subscription service. also in: PRIORITY IS ASSIGNED BY THE EXPLICITNESS OF A QUESTION RATHER THAN BY THE IDEA, AND ONE AUTHOR IS CREDITED FOR WHAT HE DID NOT ASK: one researcher DID NOT ASK whether quantum mechanics conferred extra power AND YET showed enough to make later work possible; another RAISED THE POSSIBILITY, THUS IMPLICITLY ASKING the converse question; and a third WAS THE FIRST TO ASK THIS QUESTION EXPLICITLY	`mechanisms[13]`	0.95	the tagger's words
limitations	the quantum algorithms are randomized, allowing a small probability of error Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[0]`		the tagger's words
limitations	No quantum computer exists that could run the algorithms. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[1]`		the tagger's words
limitations	Decoherence and precision obstacles grow with machine size, so machines large enough for interesting computations may face fundamental difficulties. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[2]`		the tagger's words
limitations	The analysis of the discrete-log algorithm only establishes the residue of r for primes larger than 18, requiring extra work for small prime powers. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[3]`		the tagger's words
limitations	The proved efficiency bounds are loose; an actual implementation could do considerably better than the paper's analysis shows. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[4]`		the tagger's words
limitations	The problems solved are of narrow intrinsic value, mattering mainly because cryptography assumed they were hard. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[5]`		the tagger's words
limitations	Making the thesis provable would make it weaker, and the paper says so: 'Quotation withheld' The informal statement is unprovable and the formal one is about a smaller class of machines. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`limitations[6]`	0.95	the tagger's words
transfers	reducing integer factorization to order/period-finding (a number-theory reduction), then solving it on a quantum computer via the quantum Fourier transform Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`transfers[0]`		the tagger's words
concepts	precision Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: precision	`concepts[4]`	0.95	the paper's words
concepts	quantum computer Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: quantum computer	`concepts[5]`	0.95	the paper's words
concepts	Church’s thesis Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: Church’s thesis	`concepts[6]`	0.95	the paper's words
concepts	physical Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: physical	`concepts[7]`	0.9	the paper's words
concepts	reasonable Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: reasonable	`concepts[8]`	0.9	the paper's words
unhoused_relations	Church’s thesis → a mathematical theorem Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. THREE PAPERS, THREE DIFFERENT VERDICTS ON WHETHER A FORMALISM CAN BE SHOWN TO CAPTURE THE INFORMAL NOTION IT REPLACES - and no type in the vocabulary can express a disagreement about what KIND OF CLAIM something is. This paper says the identification CANNOT BE MADE A THEOREM WITHOUT WEAKENING IT: a precise mathematical description of a computing device would leave open the possibility of a practical device that did not satisfy it, so the theorem would be weaker than the thesis it replaced. turing1936-computable-numbers argues it instead, enumerating three kinds of argument; tkacik2016-information-living reports a theorem that did make a vague notion precise. 'same-as' and 'distinct-from' are both false here: the three are not making one claim or two, they are ruling differently on whether the identification is the sort of thing a proof can settle. All eight edge types assert that a relation holds between two concepts. Recorded per record, each row quoting only its own paper; the cross-paper half is this paraphrase, checkable by opening the other two., and the third case for an earlier note of ours - which by the rule that one is an observation and three make a proposal is the point at which the gap should be put to Shir.	`unhoused_relations[0]`	0.95	the tagger's words
senses	Quantitative Church’s thesis - AS THE PAPER READS IT, WITH ITS TWO LOOSE WORDS NAMED: 'There are TWO ESCAPE CLAUSES in the above thesis. One of these is the word "physical" ... The other escape clause ... is the word "resources," the meaning of which is NOT COMPLETELY SPECIFIED.' What the thesis asserts depends on which senses are supplied for those two words Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[0]`	0.95	the tagger's words
senses	efficiently computable - EXPLICITLY A COMPROMISE, NOT A DISCOVERY: 'The generally accepted compromise between coarseness and precision' between a computable/non-computable split that is 'much too coarse' and exact efficiency that is 'too precise a quantity to work with easily' - realised as the polynomial vs superpolynomial scaling line Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[1]`	0.95	the tagger's words
claim_relations	builds-on → the number-theoretic reduction of factoring to order-finding (Miller 1976) Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[0]`		the tagger's words
claim_relations	builds-on → computability theory (Church, Turing, Post 1936) Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[1]`		the tagger's words
claim_relations	builds-on → Simon [1994] Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[2]`		the tagger's words
claim_relations	builds-on → Miller [1976] randomised reduction of factoring to order-finding Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[3]`		the tagger's words
claim_relations	builds-on → Coppersmith [1994] and Deutsch [see Ekert and Jozsa 1995] construction of the quantum Fourier transform Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[4]`		the tagger's words
claim_relations	extends → Deutsch and Jozsa [1992] and Berthiaume and Brassard [1992a, 1992b] Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[5]`		the tagger's words
claim_relations	contradicts → the quantitative (strong) Church's thesis, that any physical computing device can be simulated by a Turing machine with at most polynomial overhead Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. differs in: THE AXIS IS WHETHER QUANTUM MECHANICS IS TAKEN INTO ACCOUNT. 'A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most A POLYNOMIAL FACTOR. This may not be true when quantum mechanics is taken into cons[IDERATION].' The thesis is not shown false - it is shown to have a physical precondition nobody had needed to state, and the polynomial factor is what fails. A 'contradicts' alone records a dispute with a computing thesis and drops the fact that the dispute is ABOUT WHICH PHYSICS THE MACHINE OBEYS.	`claim_relations[6]`		the tagger's words
concept_edges	physical —same-as→ reasonable Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. strength of the relation: 0.8 · note: TWO PUBLISHED STATEMENTS OF ONE THESIS DIFFER IN ONE WORD, AND THE PAPER ARGUES THEY MUST MEAN THE SAME: in van Emde Boas [1990] '…is replaced with the word "reasonable." It is difficult…' A terminological argument inside a mathematics paper, about the load-bearing word of the thesis being tested. Audit 2026-09-28: DOUBTFUL - read against its full span and kept, but the span says 'physical' was REPLACED by 'reasonable' in one statement of the thesis; same-as is loose. also in: physical · reasonable	`concept_edges[1]`	0.9	the tagger's words
content_tags	polynomial — quantum running time for factoring / discrete log (vs believed super-polynomial classically) Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.quantities[0]`		the tagger's words
content_tags	Efficient randomized algorithms for factoring and discrete logarithms are given for a hypothetical quantum computer, taking a number of steps polynomial in the input size. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.findings[0]`		the tagger's words
content_tags	The quantitative Church thesis may not be true when quantum mechanics is taken into consideration. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.findings[1]`		the tagger's words
content_tags	input size Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: input size	`content_tags.variables[0]`		the tagger's words
content_tags	number of steps Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: number of steps	`content_tags.variables[1]`		the tagger's words
content_tags	quantum order-finding algorithm Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: quantum order-finding algorithm	`content_tags.definitions[1]`		the tagger's words
content_tags	factoring integers Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: factoring integers	`content_tags.definitions[2]`		the tagger's words
content_tags	discrete logarithms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: discrete logarithms	`content_tags.definitions[3]`		the tagger's words

Interpretive choices

Tags that could not be placed in the text:

none — every tag was located in the text

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.