1
$\begingroup$

Is there any paper or piece of code showing, on a REAL quantum computer, that a specific real world problem (possibly related to computer science, machine learning or finance and possibly NOT related to cryptography) is solved more efficiently than a classical computer ? In general, I'd be happy with any problem where a Quantum Computer can bring value, which does not need to be necessarily speedup. In fact, for me it's enough if the quantum version is better under any point of view (stability, robustness, energy consumption, model expressiveness ...) as long as this superiority is somehow showed and documented true actual comparisons and experiments.

All the resources I looked at never make any comparison with the classical version and often claim quantum computing is powerful just showing it can solve a specific problem, without telling much about the classical counterpart.

Improve this question
$\endgroup$
7
  • $\begingroup$ Yes! Arguably the most famous is Shor's algorithm, which can find the prime factors of an integer in polynomial time on a quantum computer. The most efficient known classical algorithm runs in exponential time. $\endgroup$
    – T.H
    Jul 8, 2022 at 14:12
  • $\begingroup$ related: quantumcomputing.stackexchange.com/q/135/55, quantumcomputing.stackexchange.com/q/2444/55 $\endgroup$
    – glS ♦
    Jul 8, 2022 at 14:26
  • $\begingroup$ Sorry, I forgot I wanted to explicitly exclude cryptography from the question. I'm mainly looking for something (real world) related to ML, optimization, databases or finance. $\endgroup$
    – mpro
    Jul 8, 2022 at 14:28
  • $\begingroup$ @glS I read both those threads before posting, unfortunately they don't contain what I'm looking for. I'm seeking some paper or piece of code with actual results on real hardware were it's crystal clear which value the quantum approach adds wrt the classical version. I'm not looking for proofs or (only) theoretical result. $\endgroup$
    – mpro
    Jul 8, 2022 at 14:31
  • 1
    $\begingroup$ Which quantum computer? Theoretical, definitely yes. As for real-world existing quantum computer, they say that DWave computer is better than classical in problem it solves, but DWave is not an algoritmic computer. $\endgroup$
    – kludg
    Jul 8, 2022 at 14:36

2 Answers 2

Reset to default
2
$\begingroup$

You probably did not look good enough. Every fundamental quantum algorithm is always presented and compared to a classical counterpart. There is simply no well-known quantum algorithm that was ever given without complexity analysis.

Currently, most of the QC field is theoretical and not realizable in practice. But there are many useful and valuable experiments that are routinely performed on real quantum devices.

If we leave out cryptography and Shor's algorithm which has exponential speedup over classical factoring methods, there are:

  1. Grover's search with quadratic speedup. It can be executed on a real quantum computer. Two working logical qubits are enough to experimentally demonstrate that Grover can find a preimage of a function in one query! Whereas classical search would take from 1 to 4 queries. You can run it yourself on a cloud. I'm not attaching any references because it is basic textbook stuff. The code that you can run is here.
  2. Adiabatic quantum search with quadratic speedup. Similar to Grover search but with adiabatic computation. Complexity analysis is, of course, included.
  3. Quantum teleportation. In network communication, they teleport quantum information. This has been done many times. Some scientists even managed to teleport quantum information to a space satellite. This is important for quantum internet and communication.
  4. Quantum chemistry. Small molecule systems are routinely solved on actual quantum hardware. So far, no practical advantages over classical methods. But this is a question of time. We'll get there someday.
  5. Optimization with D-Wave quantum annealers. The practical advantage over classical solvers is not clear so far. But I'm sure in several years we will get there too. In 2021 they demonstrated the quantum advantage over path-integrated MC.
  6. You can create time crystals. See here. For some reason, physics people are really excited about it. If you or I don't understand why it is important, it doesn't mean it has no value.
  7. Quantum optics for optimization. Coherent Ising machines were experimentally tested and the speedup was experimentally observed.
  8. Finally, machine learning... IBM has done some work and proved a quantum advantage in quantum kernel methods.

These are things off the top of my head. I'm sure there is plenty of quantum stuff that is currently running on the near-term hardware.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your answer. I had a look at some of the resources you shared with me (only those related to computer science, optimization or finance, I'm not interested in physics) and even if they include the complexity analysis, they don't report practical comparisons with the classical case. What I'm desperately looking for is a table or a plot showing how the quantum version on REAL hw performs on some use case vs the same use case solved by a classical computer or, if the use case is an intractable problem for a classical supercomputer, at least the performances of the quantum version. $\endgroup$
    – mpro
    Jul 11, 2022 at 11:23
  • $\begingroup$ Ok, you look for benchmarking results then. First, D-Wave paper has the section on it. They are the only company that can somewhat compete with classical hardware. Second, Grover algo, you can ran it yourseld and compare amount of queries. Third, producing benchmarking results doesn't makse sense now, it is too early. To produce benchmarking results you need to have hardware and practical performance will depend on that. But computing science and quantum computing are not about tools. So in essence, it almost doesn't matter which current tool stack runs faster. $\endgroup$
    – MonteNero
    Jul 11, 2022 at 17:22
  • $\begingroup$ Thanks again for your answer. Perhaps I'm not seeing the big picture. I thought that, when doing research in companies about Quantum Computing, one was supposed to show why the quantum version is supposed to be better (speedup, better accuracy, capable of solving intractable problems, etc.), producing some result I guess. If benchmarking doesn't make sense now, where should one aim at when doing this kind of research ? Also why do companies like IBM and Microsoft claim they already own a quantum computer ? $\endgroup$
    – mpro
    Jul 12, 2022 at 7:12
  • $\begingroup$ To show theoretical usefulness of some novel algorithm you show complexity analysis. This is valid for quantum and classical computing. For example, basic classical binary search on an ordered array has complexity log(n). This alone is enough to convince the majority of people with rudimentary knowledge of computing that this search algorithm must not be that bad. And there is no need for Alice and Bob to benchmark linear search vs binary search. $\endgroup$
    – MonteNero
    Jul 12, 2022 at 7:35
  • $\begingroup$ Companies are not universities. When you claim something is better, you must also show it works in practice. Often researchers claim a specific algorithm can expose a Nx speedup using quantum, FPGAs, GPUs and so on, but in practice when you try to measure the actual performances on an heterogeneous system you end up realizing you didn't consider many factors. For instance, latencies coming from bringing back data from the quantum computer to the classical computer, time taken to encode and load the data to the quantum computer and so on. Theory is often not enough $\endgroup$
    – mpro
    Jul 12, 2022 at 8:18
0
$\begingroup$

D-wave has been used to solve multiple optimization problems already, see examples here: https://www.dwavesys.com/solutions-and-products/manufacturing-logistics/ The only issue with this as an answer is that D-Wave's devices are arguably not real Quantum Computers, but they are hardly classical computers either so I think this still applies.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ is there any comparative analysis as to what is the advantage/value of solving said optimisation problems with D-wave rather than with regular computers? $\endgroup$
    – glS ♦
    Jul 8, 2022 at 16:25
  • $\begingroup$ What do you mean? D-wave is not a cheap resource to use, so companies like VW and others likely needed to compare that to use of comparable supercomputers for the jobs they were pursuing. I think the comment on your question you posted above @gIS is actually pretty valuable, better than mine: quantumcomputing.stackexchange.com/q/135/55 Outside of that, comparing computing power between D-Wave and traditional computers with CPUs and GPUs is a futile task, the question only asked if some problems can be solved with quantum computers faster, which is true, as per the D-wave case studies. $\endgroup$
    – Sam_QC
    Jul 8, 2022 at 16:47
  • 2
    $\begingroup$ well, thing is, "they likely needed to compare ..." might very well be wishful thinking. I might not be too up to speed with what's been done with D-Wave devices, but I've still never read nor heard about any case where they were used to solve some problem and there was a convincing reason to believe that the results they got with the device could not have been obtained with similar or better performances with classical devices. Not to mention the, to my knowledge, total lack of evidence that annealing provides scaling advantages efficiency-wise $\endgroup$
    – glS ♦
    Jul 8, 2022 at 17:47
  • $\begingroup$ @Sam_QC Can you elaborate a little more the following sentence "D-Wave's devices are arguably not real Quantum Computers, but they are hardly classical computers either" (please consider I'm a CS student, then my quantum knowledge is limited to the quantum computing and I have no knowledge of quantum hardware) ? $\endgroup$
    – mpro
    Jul 8, 2022 at 18:34
  • $\begingroup$ D-wave makes quantum annealing processors, which are different from almost every other major QC company. There are some good videos D-wave themselves have made on YT that explain the differences. People just argue that they are not really quantum computers because they are not universal, which is valid, the only problems they are really designed to solve are optimization problems. That is also why nobody is freaking out that D-wave's Advantage machine has 5000 qubits, they are fundamentally different from traditional qubits like in IBM or Quantinuum devices. $\endgroup$
    – Sam_QC
    Jul 8, 2022 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.