Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain roots of unity.

Are there any other such problems?


1 Answer 1


To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on this (see QAZ for precise definitions and references. This is another way to say I don’t even pretend to understand many of the problems of this list!)

Algebraic and Number Theoretic Problems

If I’m not mistaken, all problems listed before the Abelian hidden subgroup problem are special cases of it.

  • Factorization
  • Discrete logarithm
  • Pell’s Equation. Factoring reduces to Pell’s equation.
  • Principal Ideal Ideal problem. Pell’s equation reduces to this problem, which therefore at least as hard as factoring.
  • Unit Group problem
  • Class Group problem
  • Gauß Sums estimation
  • Matrix Elements of Group Representations
  • Group Order and Membership
  • The Abelian hidden subgroup problem
  • Some (but not all) non-Abelian hidden subgroup problems
  • Some (but not all) problems phrased as special cases of the hidden shift problem
  • Some (but not all) Hidden Nonlinear Structures problems
  • Exploring some graphs (Welded trees)
  • Group Isomorphism, for Abelian and some non-Abelian groups
  • Find some properties of Finite Rings and Ideals

Approximation and Simulation

  • Quantum simulation. Obviously $BQP$-complete
  • Computing some knot-invariants, including HOMFLY polynomial, of which the Jones polynomial is a special case. Some of them are $BQP$-complete
  • Computing some Three-manifold Invariants. Some of them are $BQP$-complete.
  • Estimating the thermodynamic partition function of some classical systems
  • Computing Zeta Functions over finite fields
  • A string rewriting problem is $\mathit{PromiseBQP}$-complete
  • approximating matrix elements of powers of exponentially large sparse matrices.

Algorithm I don’t really get.

These are mainly algorithms where QAZ claims a superpolynomial increase, but I don’t get why the original problem is supposed to be out of $P$. That said, I’ll bet lots of my money on QAZ being right and myself being wrong on that.

  • Pattern matching for large enough ($>\log(n)$) patterns
  • Some linear system problems, in $P$ but having a $\mathrm{polylog}$ quantum algorithm if the linear system is given as an oracle.
  • Computing the Electrical Resistance of a graph,has a $\mathrm{polylog}$ quantum algorithm if the electric circuit is given as an oracle
  • Weight Enumerators problem. Something related to code and partition functions, but I don’t understand what it is about.

$P$ problems 1st proved to be in $BQP$ and then in $P$

Here are some problems where an efficient quantum algorithm has been published before a classical one. In other words, they were once conjectured to be in $BQP$ but not in $P$, but this conjecture is now invalidated.

  • Satisfying more than $(\tfrac12-\tfrac{\text{constant}}{D})N$ (but less than $\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$) constraints of the Max E3LIN2 problem. As pointed by Juan Berego Vega in the comments : there is now a classical algorithm for $(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$, which was motivated by the quantum result. (Blog post on this result, paper 1, paper2)
  • Recommendation systems (see Scott Aaronson’s blog post for a more detailed explanation). Recommendation system — à la Netflix/Amazon/etc.— can be seen as completing a sparse $m×n$ matrix of low rank $k$ with very incomplete data. Known classical algorithm where polynomial in $m$, $n$ ad $k$. If the matrix is given as an oracle, Iordanis Kerenidis an Anupam Prakash found a $\mathrm{poly}(k)\mathrm{polylog}(mn)$ quantum algorithm finding samples of the unknown elements of the matrix in 2016 (paper). In 2018, while trying to prove this scaling is impossible to reach with a classical machine, Ewin Tang actually found a classical algorithm achieving the same performance under the same conditions (paper available here and here).
  • 2
    $\begingroup$ This is a great answer! One comment: I just noticed that the QAZ entry about the Max E3LIN2 speed-up is not up to date because of recent progress on classical algorithms [1],[2],[3]; I am afraid we do not know if there exists a superpolynomial speed-up for that problem at the time of writing. $\endgroup$ Jul 31, 2015 at 10:34
  • 1
    $\begingroup$ @JuanBermejoVega : I edited the answer to take your comment into account $\endgroup$ Jul 31, 2015 at 11:04
  • 1
    $\begingroup$ In your last bullet-point, $\:$ constrant $\mapsto$ constant $\:$. $\;\;\;\;$ $\endgroup$
    – user6973
    Jul 31, 2015 at 13:12
  • 1
    $\begingroup$ One update: now the Zoo is also up to date on that regard, cf. "However, an efficient classical algorithm achieving an even better approximation ratio (in fact, the approximation ratio saturating the limit set by hardness-of-approximation) was subsequently discovered [260]. Presently, the power of quantum approximate optimization algorithms relative to classical algorithms remains unclear and is an active area of research. " $\endgroup$ Jul 31, 2015 at 17:27
  • 2
    $\begingroup$ FYI (1) I think all claims of "BQP-completeness" are actually, technically PromiseBQP-completeness. I believe it is open whether BQP (not PromiseBQP) has any complete problems, since BQP is a semantic class, and I believe I recall seeing oracles going both ways on this question. (2) I think the thing about linear algebra is b/c "we think" n x n linear systems take $n^\omega$ time, even if the system is given to you as an oracle, and this is exponentially more than the polylog time required to approximate the range on a quantum computer. $\endgroup$ Jul 31, 2018 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.