<p>To have a list of such problems, you can look at the list of superpolynomial speed improvement at the <a href="http://math.nist.gov/quantum/zoo/" rel="noreferrer">quantum algorithm zoo</a> (QAZ). The list below is based on  this (see <a href="http://math.nist.gov/quantum/zoo/" rel="noreferrer">QAZ</a> 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!)</p>
<h2>Algebraic and Number Theoretic Problems</h2>
<p>If I’m not mistaken, all problems listed before the Abelian hidden subgroup problem are special cases of it.</p>
<ul>
<li>Factorization</li>
<li><a href="https://en.wikipedia.org/wiki/Discrete_logarithm#Algorithms" rel="noreferrer">Discrete logarithm</a></li>
<li><a href="https://en.wikipedia.org/wiki/Pell%27s_equation#Concise_representation_and_faster_algorithms" rel="noreferrer">Pell’s Equation</a>. Factoring reduces to Pell’s equation.</li>
<li>Principal Ideal Ideal problem. Pell’s equation reduces to this problem, which therefore at least as hard as factoring.</li>
<li>Unit Group problem</li>
<li>Class Group problem</li>
<li>Gauß Sums estimation</li>
<li>Matrix Elements of Group Representations</li>
<li>Group Order and Membership</li>
<li>The Abelian <a href="https://en.wikipedia.org/wiki/Hidden_subgroup_problem" rel="noreferrer">hidden subgroup problem</a></li>
<li>Some (but not all) non-Abelian <a href="https://en.wikipedia.org/wiki/Hidden_subgroup_problem" rel="noreferrer">hidden subgroup problems</a></li>
<li>Some (but not all) problems phrased as special cases of the hidden shift problem</li>
<li>Some (but not all) Hidden Nonlinear Structures problems</li>
<li>Exploring some graphs (Welded trees)</li>
<li>Group Isomorphism, for Abelian and some non-Abelian groups</li>
<li>Find some properties of Finite Rings and Ideals</li>
</ul>
<h2>Approximation and Simulation</h2>
<ul>
<li>Quantum simulation. Obviously <span class="math-container">$BQP$</span>-complete</li>
<li>Computing some knot-invariants, including HOMFLY polynomial, of which the Jones polynomial is a special case. Some of them are <span class="math-container">$BQP$</span>-complete</li>
<li>Computing some Three-manifold Invariants. Some of them are <span class="math-container">$BQP$</span>-complete.</li>
<li>Estimating the thermodynamic partition function of some classical systems</li>
<li>Computing Zeta Functions over finite fields</li>
<li>A string rewriting problem is  <span class="math-container">$\mathit{PromiseBQP}$</span>-complete</li>
<li>approximating matrix elements of powers of exponentially large sparse matrices.</li>
</ul>
<h2>Algorithm I don’t really  get.</h2>
<p>These are mainly algorithms where <a href="http://math.nist.gov/quantum/zoo/" rel="noreferrer">QAZ</a> claims a superpolynomial increase, but I don’t get why the original problem is supposed to be out of <span class="math-container">$P$</span>. That said, I’ll bet lots of my money on <a href="http://math.nist.gov/quantum/zoo/" rel="noreferrer">QAZ</a> being right and myself being wrong on that.</p>
<ul>
<li>Pattern matching for large enough (<span class="math-container">$&gt;\log(n)$</span>) patterns</li>
<li>Some linear system problems, in <span class="math-container">$P$</span> but having a <span class="math-container">$\mathrm{polylog}$</span> quantum algorithm if the linear system is given as an oracle.</li>
<li>Computing the Electrical Resistance of a graph,has a <span class="math-container">$\mathrm{polylog}$</span> quantum algorithm if the electric circuit is given as an oracle</li>
<li>Weight Enumerators problem. Something related to code and partition functions, but I don’t understand what it is about.</li>
</ul>
<h2><span class="math-container">$P$</span> problems 1st proved to be in <span class="math-container">$BQP$</span> and then in <span class="math-container">$P$</span></h2>
<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 <span class="math-container">$BQP$</span> but not in <span class="math-container">$P$</span>, but this conjecture is now invalidated.</p>
<ul>
<li>Satisfying more than <span class="math-container">$(\tfrac12-\tfrac{\text{constant}}{D})N$</span> (but less than <span class="math-container">$\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$</span>) constraints of the  Max E3LIN2 problem. As pointed by Juan Berego Vega in the comments : there is now a classical algorithm for <span class="math-container">$(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$</span>, which was motivated by the quantum result. (<a href="https://lucatrevisan.wordpress.com/2015/05/18/how-many-theoreticians-does-it-take-to-approximate-max-3lin/" rel="noreferrer">Blog post on this result</a>, <a href="http://arxiv.org/abs/1505.03424" rel="noreferrer">paper 1</a>, <a href="http://www.csc.kth.se/%7Ejohanh/bounded2.pdf" rel="noreferrer">paper2</a>)</li>
<li><a href="https://en.wikipedia.org/wiki/Recommender_system" rel="noreferrer">Recommendation systems</a> (see <a href="https://www.scottaaronson.com/blog/?p=3880" rel="noreferrer">Scott Aaronson’s blog post</a>  for a more detailed explanation). Recommendation system — à la Netflix/Amazon/etc.— can be seen as completing a sparse <span class="math-container">$m×n$</span> matrix of low rank <span class="math-container">$k$</span> with very incomplete data. Known classical algorithm where polynomial in <span class="math-container">$m$</span>, <span class="math-container">$n$</span> ad <span class="math-container">$k$</span>. If the matrix is given as an oracle, Iordanis Kerenidis an Anupam Prakash found a <span class="math-container">$\mathrm{poly}(k)\mathrm{polylog}(mn)$</span> quantum algorithm finding samples of the unknown elements of the matrix in 2016 (<a href="https://arxiv.org/abs/1603.08675" rel="noreferrer">paper</a>). 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 <a href="https://eccc.weizmann.ac.il/report/2018/128/" rel="noreferrer">here</a> and <a href="https://arxiv.org/abs/1807.04271" rel="noreferrer">here</a>).</li>
</ul>

CC BY-SA 3.0
2015-07-31T10:34:22.290Z
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](https://lucatrevisan.wordpress.com/2015/05/18/how-many-theoreticians-does-it-take-to-approximate-max-3lin/)],[[2](http://eccc.hpi-web.de/report/2015/082/)],[[3](http://www.scottaaronson.com/blog/?p=2284#comments)]; I am afraid we do not know if there exists a superpolynomial speed-up for that problem at the time of writing.
Juan Bermejo Vega
CC BY-SA 3.0
2015-07-31T10:38:18.173Z
@JuanBermejoVega : I think you should forward this comment to the zoo keeper (Stephen Jordan, his email is on top of the QAZ page).
Frédéric Grosshans
CC BY-SA 3.0
2015-07-31T11:04:21.350Z
@JuanBermejoVega : I edited the answer to take your comment into account
Frédéric Grosshans
CC BY-SA 3.0
2015-07-31T17:27:31.057Z
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. "
Juan Bermejo Vega
CC BY-SA 3.0
2015-08-20T04:42:57.323Z
How does 'Factoring reduces to Pell’s equation'?
Turbo
CC BY-SA 3.0
2016-11-25T23:40:26.880Z
@Turbo See http://mathoverflow.net/q/70913/4780 for the link between Pell equation and factorisation
Frédéric Grosshans
CC BY-SA 4.0
2018-07-31T22:58:39.340Z
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.
Joshua Grochow
CC BY-SA 4.0
2018-08-02T10:56:02.677Z
@JoshuaGrochow : (1) I’m a poor physicist, struggling with complexity classes, and I have problem to  make sense of this part : most “BQP completeness” claims go through a polynomial simulation of universal quantum circuits, thus solving any BQP problem in polynomial time. I guess I am missing something crucial. Do you have any ref which could help me? (2) Indeed, this fits with my understanding of the HHL algorithm (which I’ve understood since 2015)
Frédéric Grosshans
CC BY-SA 4.0
2015-07-29T14:54:31.503Z
2018-07-30T13:06:30.720Z
2020-06-17T09:38:08.363Z
Frédéric Grosshans
<p>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.</p>

<p>Are there any other such problems?</p>

<cc.complexity-theory><complexity-classes><quantum-computing>
Problems in BQP but conjectured to be outside P
Minkov
# Problems in BQP but conjectured to be outside P

(Asked by: username_0 on 2015-04-14)

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?

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing


---

## 1 answers

### Answer by username_1 on 2015-07-29. Score: 25 | Accepted answer

To have a list of such problems, you can look at the list of superpolynomial speed improvement at the [quantum algorithm zoo](http://math.nist.gov/quantum/zoo/) (QAZ). The list below is based on this (see [QAZ](http://math.nist.gov/quantum/zoo/) 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](https://en.wikipedia.org/wiki/Discrete_logarithm#Algorithms)
* [Pell’s Equation](https://en.wikipedia.org/wiki/Pell%27s_equation#Concise_representation_and_faster_algorithms). 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](https://en.wikipedia.org/wiki/Hidden_subgroup_problem)
* Some (but not all) non-Abelian [hidden subgroup problems](https://en.wikipedia.org/wiki/Hidden_subgroup_problem)
* 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](http://math.nist.gov/quantum/zoo/) 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](http://math.nist.gov/quantum/zoo/) 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](https://lucatrevisan.wordpress.com/2015/05/18/how-many-theoreticians-does-it-take-to-approximate-max-3lin/), [paper 1](http://arxiv.org/abs/1505.03424), [paper2](http://www.csc.kth.se/%7Ejohanh/bounded2.pdf))
* [Recommendation systems](https://en.wikipedia.org/wiki/Recommender_system) (see [Scott Aaronson’s blog post](https://www.scottaaronson.com/blog/?p=3880) 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](https://arxiv.org/abs/1603.08675)). 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](https://eccc.weizmann.ac.il/report/2018/128/) and [here](https://arxiv.org/abs/1807.04271)).

> **Comments:**
> **username_2**: 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](https://lucatrevisan.wordpress.com/2015/05/18/how-many-theoreticians-does-it-take-to-approximate-max-3lin/)],[[2](http://eccc.hpi-web.de/report/2015/082/)],[[3](http://www.scottaaronson.com/blog/?p=2284#comments)]; I am afraid we do not know if there exists a superpolynomial speed-up for that problem at the time of writing.  
> **username_1**: @JuanBermejoVega : I think you should forward this comment to the zoo keeper (Stephen Jordan, his email is on top of the QAZ page).  
> **username_1**: @JuanBermejoVega : I edited the answer to take your comment into account  
> **username_2**: 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. "  
> **username_3**: How does 'Factoring reduces to Pell’s equation'?  
> **username_1**: @username_3 See http://mathoverflow.net/q/70913/4780 for the link between Pell equation and factorisation  
> **username_4**: 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.  
> **username_1**: @JoshuaGrochow : (1) I’m a poor physicist, struggling with complexity classes, and I have problem to  make sense of this part : most “BQP completeness” claims go through a polynomial simulation of universal quantum circuits, thus solving any BQP problem in polynomial time. I guess I am missing something crucial. Do you have any ref which could help me? (2) Indeed, this fits with my understanding of the HHL algorithm (which I’ve understood since 2015)  

---

