4
$\begingroup$

I'm interested in learning about cases where a quantum computer could be used to perform tasks with only a constant (albeit large) factor of improvement in execution speed over classical computers. For example, in a talk about this paper it was mentioned that a photonic quantum computer might be able to evaluate functions of the form $$ f(x, y) = \exp \left(\frac{(x - y)^2}{\sigma^2} \right) $$

at a rate on the order of terahertz frequency ($\sim 10^{-12}$ seconds), which might give a significant procedural advantage compared to evaluating such a function classically on a PC at a rate that's presumably less than gigahertz ($\sim 10^{-9}$ seconds). So while the quantum evaluation isn't asymptotically faster it might still be a useful as specialized hardware to compute a very specific, broadly useful function (similar to how GPU's and TPU's are employed).

Are there any other interesting examples of the possibility to use a quantum computer to do an otherwise classically efficient task? Also I'm not so worried about QEC overhead and classical pre/post-processing overhead but the "clock rates" for executing gates and performing measurement on the quantum hardware are relevant.

Improve this question
$\endgroup$
6
  • $\begingroup$ Are you interested in only a constant speedup, or also speedups of problems that are already efficient (i.e. in $P$ or $BPP$) but just have better scaling on quantum computers? If the latter, (Grover's search algortihm)[en.wikipedia.org/wiki/Grover%27s_algorithm] is generally seen as having a quadratic speedup over classical search methods, which might interest you. $\endgroup$
    – JSdJ
    Commented Apr 20, 2021 at 19:33
  • 1
    $\begingroup$ Ah, no I'm more looking for applications where the asymptotic complexity looks identical on classical and quantum devices regardless of classical complexity class. Informally, applications that make a complexity theorist ask "why would you ever run that on quantum hardware?" but for which there's a practical reason to answer in the affirmative. $\endgroup$
    – forky40
    Commented Apr 20, 2021 at 19:53
  • 1
    $\begingroup$ check - although Grovers is also not a speedup in terms of complexity classes, but just gives a quadratic speedup. Nevertheless, very interesting question, although one which I'm not able to properly answer. Although it feels that the fact that classical computing is $\sim 70$ years ahead, plus the setback of the (very likely) necessity of quantum error correction which, loosely speaking, introduces a polynomial overhead, might diminish any of these types of advantages. $\endgroup$
    – JSdJ
    Commented Apr 20, 2021 at 20:44
  • $\begingroup$ Yes I agree that QEC will probably ruin anything that starts out as a constant advantage. But I'm hoping there are still fun specializations to think about for the idealized case. $\endgroup$
    – forky40
    Commented Apr 20, 2021 at 21:03
  • 1
    $\begingroup$ one problem with this is that constant speed-ups will strongly depend on the implementation details. I don't think it makes must sense to say that "an algorithm" has a constant speed-up compared to classical counterparts, because that will be affected by things such as the experimental architecture with which you actually implement the algorithm, how to implement the individual "elementary gates" it uses etc $\endgroup$
    – glS ♦
    Commented Apr 21, 2021 at 10:18

1 Answer 1

Reset to default
4
$\begingroup$

This is not possible. If you're not using a quantum algorithm, but just the quantum hardware, then the thing is hardly a quantum computer, you're just talking about a faster architecture for classical computing. Which is of course interesting, but not quantum. And furthermore classical computing architectures have been researched for decades to the tune of tens of billions of dollars. It is difficult to come up with something better.

Also, keep in mind that existing quantum hardware is rather slow - the clock rate of Google and IBM's devices is on the order of MHz, whereas classical hardware routinely runs at GHz speed.

Now, of course you could use dedicated hardware that is only good for some specific functions, and is not Turing-complete. That is known as an analog computer, and they are sometimes useful. But again, if that is not running a quantum algorithm it is hardly quantum hardware. Remember that "classical" chips are still made of atoms and have electrons going around them.

Improve this answer
$\endgroup$

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.