Sign outOpen workspaceSign in

Whose claim is the speedup

Every algorithm record here shows a speedup class, and that class is quoted from an outside index rather than derived here. This page says, for each one, whether the paper behind it states the same thing.

58 records carry a speedup class quoted from the Quantum Algorithm Zoo. 18 have been checked against their own primary paper and it states a comparable claim; 9 have been checked and it does not; 31 have not been checked. The last group is the largest, and it is a worklist rather than a verdict.

Checked, and the paper does not state it

Each of these is the narrow claim that a named paper does not contain a named result — not that the class is wrong. The index may have taken it from a source this record does not cite. What was read is printed beside each one, because “the paper does not say it” is only ever as wide as the text somebody opened.

  • Thermal Gibbs state sampling

    David Poulin, Pawel Wocjan · 2009

    The index files it as: Superpolynomial — Preparing Eigenstates and Thermal States

    The paper behind it: Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer

    What was read: abstract of arXiv:0905.2199

  • Estimating Gauss sums over finite fields and rings

    Wim van Dam, Gadiel Seroussi · 2002

    The index files it as: Superpolynomial — Gauss Sums

    The paper behind it: Efficient Quantum Algorithms for Estimating Gauss Sums

    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.

  • Subset finding by quantum walk

    Andrew M. Childs, Jason M. Eisenberg · 2003

    The index files it as: Polynomial — Subset finding

    The paper behind it: Quantum algorithms for subset finding

    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.

  • Quadratically signed weight enumerators

    E. Knill, R. Laflamme · 1999

    The index files it as: Superpolynomial — Weight Enumerators

    The paper behind it: Quantum Computation and Quadratically Signed Weight Enumerators

    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.

  • Double-bracket iterations for diagonalization

    Marek Gluza · 2022

    The index files it as: Unknown — Double-bracket quantum algorithms

    The paper behind it: Double-bracket quantum algorithms for diagonalization

    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.

  • The unit group of a constant-degree number field

    Sean Hallgren · 2005

    The index files it as: Superpolynomial — Unit Group

    The paper behind it: Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field

    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.

  • The class group of a constant-degree number field

    Sean Hallgren · 2005

    The index files it as: Superpolynomial — Class Group

    The paper behind it: Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field

    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.

  • Graph collision on a known graph

    Frederic Magniez, Miklos Santha, Mario Szegedy · 2003

    The index files it as: Polynomial — Graph Collision

    The paper behind it: Quantum Algorithms for the Triangle Problem

    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.

  • The Abelian hidden subgroup problem

    Dan Boneh, Richard J. Lipton · 1995

    The index files it as: Superpolynomial — Abelian Hidden Subgroup

    The paper behind it: Quantum Cryptanalysis of Hidden Linear Functions

    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.

  • Diagonal entries of powers of a sparse symmetric matrix

    Dominik Janzing, Pawel Wocjan · 2006

    The index files it as: Superpolynomial — Matrix Powers

    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.
  • String rewriting derivation counts

    Dominik Janzing, Pawel Wocjan · 2007

    The index files it as: Superpolynomial — String Rewriting

    Given that BQP≠BPP, our result shows that the quantum computer outperforms the classical computer in estimating differences of combinatorial quantities.
  • Zeta function of a curve over a finite field

    Kiran S. Kedlaya · 2004

    The index files it as: Superpolynomial — Zeta Functions

    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.
  • Exponential congruences over a finite field

    Wim van Dam, Igor E. Shparlinski · 2008

    The index files it as: Polynomial — Solving Exponential Congruences

    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.
  • Matrix products over semirings

    François Le Gall, Harumichi Nishimura · 2013

    The index files it as: Polynomial — Matrix Multiplication over Semirings

    In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n^2.687).
  • Viterbi decoding of classical convolutional codes

    Jon R. Grice, David A. Meyer · 2014

    The index files it as: Varies — Decoding

    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.
  • Average-case lattice problem variants by filtering

    Yilei Chen, Qipeng Liu, Mark Zhandry · 2021

    The index files it as: Exponential — Lattice Problems by Filtering

    Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider.
  • Primality proving by quantum order finding

    Alvaro Donis-Vela, Juan Carlos Garcia-Escartin · 2017

    The index files it as: Polynomial — Primality Proving

    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).
  • Pell's equation by computing the regulator

    Sean Hallgren · 2007

    The index files it as: Superpolynomial — Pell's Equation

    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.
  • The principal ideal problem in a real quadratic field

    Sean Hallgren · 2007

    The index files it as: Superpolynomial — Principal Ideal

    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.
  • Matrix elements of irreducible group representations

    Stephen P. Jordan · 2008

    The index files it as: Superpolynomial — Matrix Elements and Multiplicity Coefficients of Group Representations

    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.
  • Sampling the output of a linear-optical network

    Scott Aaronson, Alex Arkhipov · 2010

    The index files it as: Superpolynomial — Probabilistic Sampling

    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.
  • Resource counts for elliptic-curve discrete logarithms

    John Proos, Christof Zalka · 2003

    The index files it as: Various — Quantum Cryptanalysis

    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.
  • Quantum walk speedup of backtracking

    Ashley Montanaro · 2015

    The index files it as: Polynomial — Polynomial Quantum Speedups for Constraint Satisfaction Problems

    We usually think of T as being exponential in n; in this regime this complexity is a near-quadratic speedup over the classical algorithm.
  • Subset-sum by quantum walk over representations

    Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, Alexander Meurer · 2013

    The index files it as: Polynomial — Subset-sum

    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.
  • Effective resistance of an electrical network

    Guoming Wang · 2013

    The index files it as: Exponential — Electrical Resistance

    In particular, their dependence on N is exponentially better than that of known classical algorithms.
  • Semidefinite programming by quantum Gibbs sampling

    Fernando G. S. L. Brandao, Krysta Svore · 2016

    The index files it as: Polynomial (with some exceptions) — Semidefinite Programming

    This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m.
  • Tensor principal component analysis for the spiked tensor model

    M. B. Hastings · 2019

    The index files it as: Polynomial (quartic) — Tensor Principal Component Analysis

    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 asked these papers whether they support the class shown on the record. Listed rather than counted: a page that showed only the finished half of an audit would be a smaller claim pretending to be a whole one.