Whose claim is the speedup
Every algorithm record's speedup class is checked against that record's own primary paper.
58 records state a speedup class. 18 have been checked against their primary paper and match, 9 do not, and 31 are not yet checked.
Checked, and the paper does not state it
Each row is the narrow claim that a specific paper does not contain a specific result, not that the class itself is wrong.
What was read
abstract of arXiv:0905.2199
What was read
the full text of arXiv:quant-ph/0207131 — abstract, sections 1 through 8 and the conclusion. Section 5 raises the classical question and answers it with a reduction rather than a bound: "Although we are not able to prove that this is hard, we can give the following reduction, which indicates that a classical polynomial time algorithm is unlikely." Section 8 then leaves it open: "For the results of this article it remains therefore an important open question if Gauss sum estimation is hard classically, even under the assumption that factoring and discrete logarithms are easy." No classical running time is stated anywhere in the text.
What was read
the full text of arXiv:quant-ph/0311038 — abstract, section I (introduction), section II (algorithm), section III (analysis), section IV (applications), section V (open problems), the note added and the references. The word "classical" does not appear in the body text. Every comparison the paper makes is against quantum query lower bounds — the Ω(√N) bound for L = 1 and the Ω(N^(2/3)) bound for element distinctness — rather than against the cost of a classical algorithm.
What was read
the full text of arXiv:quant-ph/9909094 — abstract, sections I through V and appendix A. The paper's claim is a polynomial-equivalence and BQP-completeness result, not a speedup: an oracle for the sign problem makes classical probabilistic computation as powerful as quantum computation. No statement anywhere compares a quantum algorithm's cost with a classical algorithm's cost for a shared task.
What was read
arXiv:2206.11772 as retrieved — the abstract, the full introduction, sections 1.1 to 1.3, sections 1.6 and 1.7 where the query recursion is derived, part of section 2.2, Proposition 5 in section 3, section 4 on open questions, and fragments of the appendices. Every comparison in that text is against other quantum approaches — brute-force variational circuit optimization and quantum phase estimation — and the classical Lanczos algorithm appears only as context for a different paper's quantum adaptation, never as a baseline for this algorithm's cost. Section 2's numerical examples, section 5 and most of the appendix proofs were not retrieved and were not read.
What was read
the full text of doi:10.1145/1060590.1060660 as published on the author's page — abstract and sections 1 through 6, acknowledgments and references, all ten pages. The paper compares itself with classical work only structurally, not by cost: it observes that factoring reduces to Pell's equation, which is a special case of computing the unit group, while a reduction in the other direction is not known and appears more difficult, and that the best classical algorithm for either the unit group or the class group solves both at once. No classical running time is stated anywhere, in L-notation or otherwise, unlike the companion Pell paper which does state one.
What was read
the full text of doi:10.1145/1060590.1060660 as published on the author's page — abstract and sections 1 through 6, acknowledgments and references, all ten pages. The only comparison with classical work is structural: that the best classical algorithm for either the unit group or the class group solves both simultaneously, whereas the quantum algorithms here are layered, the class group one calling the previous two. No classical running time is stated anywhere.
What was read
the abstract of arXiv:quant-ph/0310134 and its section 4.2 (Graph Collision Problem), where Theorem 3 and its proof state the graph collision bound. The abstract reports only the triangle bounds Õ(n^(10/7)) and Õ(n^(13/10)) and does not mention graph collision at all; neither it nor section 4.2 states a classical query cost for graph collision, and neither compares the Õ(n^(2/3)) bound against one. The word classical occurs six times in the body of the paper and twice more in its bibliography, never in section 4.2; the nearest it comes to this problem is the remark opening section 4.1 that the algorithm of Ambainis is somewhat similar to the brand of classical algorithms, where a database is used, which states no cost.
What was read
the full text of Boneh and Lipton's 14-page CRYPTO '95 extended abstract, read as a PDF from the first author's Stanford page: abstract, section 1 (Introduction), section 2 (Main Results), section 3 (Applications), the lemmas and proofs of sections 4 through 8, and section 9 (Conclusions and Open Problems). It claims random quantum polynomial time for its own two theorems and for the general discrete logarithm problem and factoring, and names no classical running time, query count or lower bound to compare those against. Searching the extracted text for 'classical', 'exponential', 'lower bound', 'superpolynomial', 'speedup' and 'faster' returns 'classical' only in the abstract's closing sentence about junk bits, and 'lower bound' only in a lemma bounding a sum of roots of unity and in a counting step inside the proof of Theorem 1.
Checked, and the paper states it
The source's own words, not a paraphrase.
Our results show that quantum computation outperforms classical computation in estimating the diagonal entries (provided that BQP≠BPP). But one has to be very careful on which scale this result remains true.
Given that BQP≠BPP, our result shows that the quantum computer outperforms the classical computer in estimating differences of combinatorial quantities.
For g fixed, the approach introduced by Schoof [22] ... gives an algorithm which is polynomial in log(q) but exponential in g ... imitating Dwork's proof ... yields an algorithm which is polynomial in p, g and logp(q), as observed by Lauder and Wan [15]. However, a single algorithm for computing P(t) in time polynomial both in g and log(q) remains elusive.
While still superpolynomial in log q, this quantum algorithm is significantly faster than the best known classical algorithm, which has time complexity q^{9/8}(log q)^{O(1)}. Thus it gives an example of a natural problem where quantum algorithms provide about a cubic speed-up over classical ones.
In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n^2.687).
We present a quantum Viterbi algorithm (QVA) with better than classical performance under certain conditions. … The quantum speedup is possible because the performance of the QVA depends on the fanout (number of possible transitions from any given state in the hidden Markov model) which is in general much less than Q.
Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider.
Its complexity is essentially quadratic in the asymptotic limit, which is more efficient than classical tests that prove primality with certainty, which are usually restricted to integers of a particular form, or require a number of operations of the order of the sixth power of the number of bits (AKS test).
The best algorithm for factoring integers has expected time L(1/3,b) for some constant b [LL93]. Assuming the GRH, the best algorithms for Pell's equation and the principal ideal problem have expected time L(1/2,b′), for some constant b′, so there is a sub-exponential gap between the best known classical algorithms.
Assuming the GRH, the best algorithms for Pell's equation and the principal ideal problem have expected time L(1/2,b′), for some constant b′, so there is a sub-exponential gap between the best known classical algorithms.
These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.
in the classical case, the aij's are nonnegative real numbers—which means that we can approximate Per(A) in probabilistic polynomial time, by using the celebrated algorithm of Jerrum, Sinclair, and Vigoda [30]. In the quantum case, by contrast, the aij's are complex numbers. And it is not hard to show that, given a general matrix A ∈ Cn×n, even approximating Per(A) to within a constant factor is #P-complete.
The classical complexity of this problem seems to depend strongly on the underlying group… for discrete logarithms over elliptic curves, nothing better than "generic" algorithms are known… e.g. the Pollard ρ algorithm [3], have truly exponential complexity.
We usually think of T as being exponential in n; in this regime this complexity is a near-quadratic speedup over the classical algorithm.
We introduce the first subset-sum algorithm that beats 2^{n/4}. Specifically, we introduce a quantum algorithm that, under reasonable assumptions, uses at most 2^{(0.241…+o(1))n} qubit operations to solve a subset-sum problem.
In particular, their dependence on N is exponentially better than that of known classical algorithms.
This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m.
The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space.
Not checked against the primary source
Nobody has checked these records' papers against the class shown yet, so they are listed rather than counted.