-2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

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 threads on Aaronson's blog.

$\endgroup$
4
  • $\begingroup$ "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). $\endgroup$
    – Marion
    May 28, 2023 at 18:23
  • $\begingroup$ 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)? $\endgroup$
    – Marion
    May 28, 2023 at 18:25
  • $\begingroup$ I'd have fun exploring the Quantum Algorithm Zoo. $\endgroup$
    – Mark S
    May 28, 2023 at 18:52
  • 4
    $\begingroup$ Grover's algorithm gives a quadratic speed-up for many NP- complete problems. $\endgroup$ May 28, 2023 at 23:33

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.