<p>Regarding the title of the question:</p>
<blockquote>
<p>What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?</p>
</blockquote>
<p>and in particular the statement in the body:</p>
<blockquote>
<p>There is an ever [growing] trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics.</p>
</blockquote>
<p>I'm not aware of any serious scholarly arguments that quantum heuristics can offer an <em>exponential</em> speedup over classical heuristics for NP-complete problems.  I'm not sure of evidence to state an &quot;ever growing trend to believe&quot; that a large number of NP-hard problems can be solved <em>efficiently</em> using quantum heuristics.  There could be Grover-style polynomial speedups, but scholarly opinion even from the mid-90's is that Grover's algorithm is tight in the black-box model; this is the immediate consequence of the <a href="https://arxiv.org/abs/quant-ph/9701001" rel="nofollow noreferrer">BBBV theorem</a>.</p>
<p>Regarding the lack of evidence that BQP<span class="math-container">$\subseteq$</span>NP, from the tone of your question I think you meant to say that there is no evidence that NP<span class="math-container">$\subseteq$</span>BQP.  But, indeed the evidence is that both NP<span class="math-container">$\not\subseteq$</span>BQP and also that BQP<span class="math-container">$\not\subseteq$</span>NP - there may be problems efficiently solvable on a quantum computer that do not even have efficiently verifiable certificates, and we expect BQP to be even weirder than NP insofar as their disjoint union may be non-empty.</p>
<hr />
<p>There appears to be a couple of positions that at first blush or at first reading are mutually incompatible with each other:</p>
<ol>
<li>Quantum Computers and quantum heuristics can solve NP-complete problems, and</li>
<li>Even Grover's algorithm doesn't offer any significant speedup over classical algorithms.</li>
</ol>
<p>With some careful corrections or clarifications these positions, however, may not be entirely inconsistent, and indeed both may be true:</p>
<ol>
<li>Quantum heuristics, even on noisy quantum computers, <em><strong>may offer some asymptotic polynomial-time advantages</strong></em> for NP-complete problems, but</li>
<li>In order for Grover's algorithm to <em><strong>be competitive with various tensor-network approaches</strong></em> and also <em><strong>to run in a fault-tolerant manner</strong></em>, the relevant problem size before quantum wins over classical could be astronomical anyways.</li>
</ol>
<p>The first one point is perhaps often elided over by start-up companies who are financially motivated to generate excitement for their quantum computers.  The second point led recently to a couple of <a href="https://scottaaronson.blog/?p=7143" rel="nofollow noreferrer">massive</a> <a href="https://scottaaronson.blog/?p=7157" rel="nofollow noreferrer">threads</a> on Aaronson's blog.</p>

CC BY-SA 4.0
2023-05-28T18:23:50.840Z
"I'm not aware of any serious scholarly arguments that quantum heuristics can offer an exponential speedup over classical heuristics for NP-complete problems." -- maybe I should be clear here. I did not mean the serious academic community but the startup scene and the industrial point of view (apologies, I know this is not TCS SE related but this is where my questions comes from).
Marion
CC BY-SA 4.0
2023-05-28T18:25:36.593Z
Regarding your comment "Quantum heuristics may offer some polynomial-time advantages for NP-complete problems" where is the evidence for this statement based of? For what (complexity or similar) reason we might be able to have even polynomial speedups with heuristics (e.g. annealing)?
Marion
CC BY-SA 4.0
2023-05-28T18:52:15.300Z
I'd have fun exploring the [Quantum Algorithm Zoo](https://quantumalgorithmzoo.org/).
Mark S
CC BY-SA 4.0
2023-05-28T23:33:00.903Z
Grover's algorithm gives a quadratic speed-up for many NP- complete problems.
Peter Shor 
CC BY-SA 4.0
2023-05-28T14:40:57.207Z
2023-05-29T13:41:21.690Z
2023-05-29T13:41:21.690Z
Mark S
<p>There is an ever going trend to believe that a large number of <strong>NP-Complete</strong> or <strong>NP-Hard</strong> problems can be solved using quantum heuristics.</p>
<p>I have observed, a common trend, to take any sort of combinatorial optimization problems, from continuous Linear Programs and SDPs to Mixed Integer Programs (accross many industrial sectors) and after converting them to Quadratic Unconstrained Binary Optimization (QUBO) problems people do any of:</p>
<ul>
<li>Feed them to tenor networks, to perform for example tensor decomposition, with complexity <span class="math-container">$O(\ell^{2N-1})$</span>, where <span class="math-container">$\ell$</span> is the modal dimension and <span class="math-container">$n$</span> the tensor order. I do not know what the complexity is to solve a generic QUBO instance here.</li>
<li>Feed them to some sort of annealing machine such as a quantum annealer with unknown complexity and empirically not great TTS (time to solution)</li>
<li>Hope for quantum heuristics such as the variational quantum algorithms whose training is proven to be <strong>NP-Hard</strong> <a href="https://arxiv.org/abs/2101.07267" rel="nofollow noreferrer">https://arxiv.org/abs/2101.07267</a></li>
</ul>
<p>Additionally, given lack of evidence that <span class="math-container">$BQP \subseteq NP$</span>, and our complete lack of understanding on where quantum heuristics live, I completely struggle to find a good argument on why one e.g. should hope to be able to solve <strong>NP-Complete</strong> or <strong>NP-Hard</strong> problems more efficiently using quantum heuristics.</p>
<p>Are there any reasonable, computational complexity-based, arguments?</p>

<np-hardness><optimization><quantum-computing><time-complexity>
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
Marion
# What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

(Asked by: username_0 on 2023-05-28)

There is an ever going trend to believe that a large number of **NP-Complete** or **NP-Hard** problems can be solved using quantum heuristics.

I have observed, a common trend, to take any sort of combinatorial optimization problems, from continuous Linear Programs and SDPs to Mixed Integer Programs (accross many industrial sectors) and after converting them to Quadratic Unconstrained Binary Optimization (QUBO) problems people do any of:

* Feed them to tenor networks, to perform for example tensor decomposition, with complexity $O(\ell^{2N-1})$, where $\ell$ is the modal dimension and $n$ the tensor order. I do not know what the complexity is to solve a generic QUBO instance here.
* Feed them to some sort of annealing machine such as a quantum annealer with unknown complexity and empirically not great TTS (time to solution)
* Hope for quantum heuristics such as the variational quantum algorithms whose training is proven to be **NP-Hard** <https://arxiv.org/abs/2101.07267>

Additionally, given lack of evidence that $BQP \subseteq NP$, and our complete lack of understanding on where quantum heuristics live, I completely struggle to find a good argument on why one e.g. should hope to be able to solve **NP-Complete** or **NP-Hard** problems more efficiently using quantum heuristics.

Are there any reasonable, computational complexity-based, arguments?

**Tags:** np-hardness, optimization, quantum-computing, time-complexity


---

## 1 answers

### Answer by username_1 on 2023-05-28. Score: 4 | Accepted answer

Regarding the title of the question:

> What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

and in particular the statement in the body:

> There is an ever [growing] trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics.

I'm not aware of any serious scholarly arguments that quantum heuristics can offer an *exponential* speedup over classical heuristics for NP-complete problems. I'm not sure of evidence to state an "ever growing trend to believe" that a large number of NP-hard problems can be solved *efficiently* using quantum heuristics. There could be Grover-style polynomial speedups, but scholarly opinion even from the mid-90's is that Grover's algorithm is tight in the black-box model; this is the immediate consequence of the [BBBV theorem](https://arxiv.org/abs/quant-ph/9701001).

Regarding the lack of evidence that BQP$\subseteq$NP, from the tone of your question I think you meant to say that there is no evidence that NP$\subseteq$BQP. But, indeed the evidence is that both NP$\not\subseteq$BQP and also that BQP$\not\subseteq$NP - there may be problems efficiently solvable on a quantum computer that do not even have efficiently verifiable certificates, and we expect BQP to be even weirder than NP insofar as their disjoint union may be non-empty.

---

There appears to be a couple of positions that at first blush or at first reading are mutually incompatible with each other:

1. Quantum Computers and quantum heuristics can solve NP-complete problems, and
2. Even Grover's algorithm doesn't offer any significant speedup over classical algorithms.

With some careful corrections or clarifications these positions, however, may not be entirely inconsistent, and indeed both may be true:

1. Quantum heuristics, even on noisy quantum computers, ***may offer some asymptotic polynomial-time advantages*** for NP-complete problems, but
2. In order for Grover's algorithm to ***be competitive with various tensor-network approaches*** and also ***to run in a fault-tolerant manner***, the relevant problem size before quantum wins over classical could be astronomical anyways.

The first one point is perhaps often elided over by start-up companies who are financially motivated to generate excitement for their quantum computers. The second point led recently to a couple of [massive](https://scottaaronson.blog/?p=7143) [threads](https://scottaaronson.blog/?p=7157) on Aaronson's blog.

> **Comments:**
> **username_0**: "I'm not aware of any serious scholarly arguments that quantum heuristics can offer an exponential speedup over classical heuristics for NP-complete problems." -- maybe I should be clear here. I did not mean the serious academic community but the startup scene and the industrial point of view (apologies, I know this is not TCS SE related but this is where my questions comes from).  
> **username_0**: Regarding your comment "Quantum heuristics may offer some polynomial-time advantages for NP-complete problems" where is the evidence for this statement based of? For what (complexity or similar) reason we might be able to have even polynomial speedups with heuristics (e.g. annealing)?  
> **username_1**: I'd have fun exploring the [Quantum Algorithm Zoo](https://quantumalgorithmzoo.org/).  
> **username_2**: Grover's algorithm gives a quadratic speed-up for many NP- complete problems.  

---

