13
$\begingroup$

According to the Wikipedia (Which quotes this paper https://arxiv.org/abs/1203.5813 by Preskill) the definition of Quantum Supremacy is

Quantum supremacy or quantum advantage is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.

On that same paper, Preskill says that a more feasible approach would be to find Quantum Systems that a quantum computer can simulate in polynomic time while a classical computer can't.

My question is: Would that situation be enough to prove Quantum Supremacy? How do we know no better classical algorithm exist? Maybe there is a efficient way of simulating that system but we don't know it yet. If this is the case, then proving quantum supremacy is more about proving rigorously that a problem is classically hard than about finding that it is quantumly easy, right?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

For all we know, it is extraordinarily hard to prove that a problem which can be solved by a quantum computer is classically hard.

The reason is that this would solve an important and long-standing open problem in complexity theory, namely whether PSPACE is larger than P.

Specifically, any problem which can be solved by a quantum computer in polynomial time can also be solved in polynomial space by a classical computer (the class PSPACE). However, it is not known whether PSPACE is strictly larger than P (the class of problems efficiently solvable on a classical computer). This is a long-standing open question in complexity theory, and thus any hardness result as the ones you talk about would also resolve that question, making it an extremely hard problem.

(In fact, there are tighter upper bounds on BQP, most importantly the class PP, but separating PP from P is even harder.)

This might be a reason for Preskill's careful formulation

Quantum supremacy or quantum advantage is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.

It should however be said that this does not mean that we cannot make any statement about the hardness of certain problems: What we can do is to relate their hardness to the hardness of other problems, for which -- while equally not proven -- there is a lot of accumulated evidence: For instance, it might be known that if problem X is easy, a range of other problems would also be easy, which have long resisted solution.

Thus, while we cannot unconditionally prove hardness of a problem, it is possible to relate it to the hardness of other problems whose hardness, while also unproven, are far better backed up with evidence.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ while technically true, I feel like this is underselling the current understanding of the "quantum supremacy regime". There are a number of problems that have been "proved" to be computationally hard classically but not quantumly, conditionally to some computational complexity assumptions holding. In other words, one can prove that if things such as boson sampling or IQP are in P, then bad things happen in the complexity space. While these results are not technically "proven" in that they rely on unproven assumptions, the same is true for a huge number of results in th complexity theory $\endgroup$
    – glS ♦
    Commented Nov 19, 2018 at 16:55
  • $\begingroup$ see e.g. the discussion in the first paragraph of arxiv.org/abs/1809.07442 $\endgroup$
    – glS ♦
    Commented Nov 19, 2018 at 16:57
  • $\begingroup$ @glS I just aimed to answer the question (or rather show that one cannot expect an affirmative answer). My point was not to sell anything. In any case, to me it is not obvious whether a useless task with a proven classical hardness (relative to some collapse) or a useful task which is plausibly classically hard would be more convincing. $\endgroup$
    – Norbert Schuch
    Commented Nov 19, 2018 at 21:21
  • 1
    $\begingroup$ how convincing "useless" demonstrations of quantum advantage are is a matter for another thread, but what I meant is that the way you write here, what someone not familiar with the topic will read is "there are no proven results", while there are results which rely on "highly likely" assumptions, which makes these results "strongly believed to be true", so much so that these results are commonly taken as essentially proven, with the unproven underlying assumptions considered more of a nitpick than anything else. $\endgroup$
    – glS ♦
    Commented Nov 19, 2018 at 22:24
  • $\begingroup$ @glS Go ahead and write an answer! In any case, I don't have a good intuition how likely or unlikely it is, say, that the polynomial hierarchy collapses to the 3rd level. Also, I don't think that these results are taken as "essentially proven" -- it is merely linking these hardness questions to other questions which are well studied and established. $\endgroup$
    – Norbert Schuch
    Commented Nov 19, 2018 at 22:33
7
$\begingroup$

How do we know no better classical algorithm exist?

We can know thanks to computational complexity theory, which studies the complexity of solving different problems with different computational models. It is in principle possible to prove that no classical algorithm can solve a given problem efficiently. A common way to do it is using reductions, that is, proving that solving a given problem is equivalent to solving another problem. One might thus prove that if it were possible to solve efficiently some kind of problem with a classical computer, it would also be possible to solve efficiently another problem which might be known to be hard.

However, as pointed out in the other answer, this is much easier said than done. A thorough discussion would be out of place here, but the main issue is that there are some big open problems at the core of computational complexity theory which no one has been able to solve yet (most notably the P vs NP problem). While unproven, many of these problems correspond to assumptions which are widely believed to hold (e.g. that P$\neq$NP). Many other results have then been proven conditionally to these assumptions holding. By reflection, these results also do not constitute complete proofs, but they can still be regarded as strong evidence for something to be true.

This is the current situation with quantum supremacy. There are problems which have been "proven" to be impossible to solve/simulate efficiently with a classical device, but for which efficient solutions are possible with a quantum computer, where "proven" here means that is has been shown that if these problems were efficiently solvable classically, then there would be unexpected consequences for some complexity classes. Notable examples are boson sampling and simulating commuting circuits. This post on cstheory.SE gives some other examples of such problems. A recent review on the topic is 1809.07442.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Upvote for the reference to Harrow & Montanaro's paper – it provides a lot of great details relevant to the question. You can find the published version in Nature if you have access. $\endgroup$
    – Greenstick
    Commented Jan 24, 2020 at 22:19

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.