4
$\begingroup$

I have essentially developed a Quantum Support Vector Machine to classify some data I have successfully. I wanted to know if it is possible to quantify the speed-up and time difference between this algorithm and a classical Support Vector Machine doing the exact same task. Also is it possible to somewhat estimate how this speed-up will be for larger datasets and scaling?

Thanks a lot!

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ user1271772 has a good answer below. Another thing you can try is to see how well your Quantum SVM does compared to other classical methods when using the exact same amount data. Currently there is no way to estimate how this speed-up will be for larger datasets and scaling except in very contrived situations. It is an ongoing topic of research. For a brief summary of the current state of the art, I would recommend one of my previous answers to a very similar question: quantumcomputing.stackexchange.com/a/15998/14597 $\endgroup$
    – sheesymcdeezy
    Mar 25, 2021 at 20:35
  • $\begingroup$ note also that for such a comparison to be fair, you would need to also take into account the time required to load the classical data into the quantum state, as that is presumably what the qSVM algorithm works on. I'm not aware of any good way to do this (unless, of course, the data was already stored in a quantum state, but then the comparison with the classical case is arguably unfair) $\endgroup$
    – glS ♦
    Mar 27, 2021 at 11:24

1 Answer 1

Reset to default
2
$\begingroup$

The paper published in Science: "Defining and Detecting Quantum Speed-up" tells you to measure quantum speed-up with the following formula (... ready for it?!):

$$\tag{1} \textrm{speed-up} = \frac{Q}{C}, $$

where $Q$ is the runtime on a quantum computer, and $C$ is the runtime on a classical computer. Believe it or not, this is Eq. 1 in that paper.

In reality it's much more complicated than that that, because different classical hardware will have a different $C$ value.

"Also is it possible to somewhat estimate how this speed-up will be for larger datasets and scaling?"

Without knowing the specific details of your algorithm, which might provide some insight into how the scaling can be measured, you would have to do experiments on larger and larger inputs and empirically guess the asymptotic scaling based on that (which is hard to do properly right now because quantum devices are limited in the number of qubits they offer).

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ The formula should be the other way around right? $\dfrac{C}{Q}$. $\endgroup$
    – KAJ226
    Mar 26, 2021 at 1:18
  • $\begingroup$ @KAJ226 exactly the same information information is contained in that! Assumimg there's quantum "speed-up", Q should be faster and therefore it makes sense to look at it as a percentage of the classical runtime which is bigger (multiply by 100 if you want). $\endgroup$
    – user1271772
    Mar 26, 2021 at 1:24

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.