1
$\begingroup$

I am new to the field and I am very confused about the status of things right now. Sorry, but this confusion also spills into the framing of my questions.

First, a more CS-style question.

As far as I understand historically since the invention of Shor's factoring algorithm or around that time the confidence that quantum computers will be able to outperform classical in some tasks has grown. However, there is still very little or no rigorous evidence for that. I've found this account in the QuantaMagazine of the result on the oracle separation between BQP and BPP. The significance of this result is not clear to me, but the very fact that it's relatively new seems to be quite telling.

At the same time I'm constantly bumping into different papers that claim to de-quantize some important class of problems, say here for quantum machine learning and here for quantum simulations. I do not know whether these results are universally accepted but at least there seems to be no apparent reason why they could not be true in principle. So my first concrete question is

Is there an accessible review somewhere that explains the current status of the affairs?

Next, a more sociological one.

If my impression is correct, and the theoretical advantage of classical algorithms over quantum is not really established, how should I think about the large investments going into the quantum computing industry right now?

I understand that this is not a very scientific question, but perhaps there are scientifically motivated answers? For example although Grover's algorithm does not provide an exponential speed-up it still increases performance and maybe this is enough for some practical purposes? Or perhaps one expects that although some types of problems may formally be polynomial-time for both classical and quantum computers, the real-life performance may still be much more favorable in the quantum case?

Related to the last question, are there any applications that are expected to be possible on the near-term quantum computers, say 10 to 20 years? Is there a good review of such prospects?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ the confusion is understandable, but please note that the stackexchange format prefers questions to be laser-focused. As it currently stands, this is too broad. Feel free to edit the question to specialise it on a single point. You can ask the other questions separately on different posts $\endgroup$
    – glS ♦
    Apr 15, 2021 at 10:26
  • $\begingroup$ Oracle separation between BQP and BPP is proved by Bernstein and Vazirani in 1997. Quanta Magazine article talks about Oracle separation between BQP and PH (the polynomial hierarchy) $\endgroup$
    – Egretta.Thula
    Apr 15, 2021 at 15:04
  • 1
    $\begingroup$ Does this answer your question? What exactly makes quantum computers faster than classical computers? $\endgroup$
    – user1271772
    Apr 15, 2021 at 17:55

0

Reset to default