4
$\begingroup$

Many popular QC algorithms are probabilistic in nature, like Grover's, Shor's, QAOA ..etc

For some of these we have formulas that give probabilities of success (like for Grover's and Shor's), and for others that are harder to analyze we estimate these probabilities by testing the algorithm on various problem samples (like for QAOA).

Is there a general framework that we use to compare the performance of either type of probabilistic algorithms against deterministic algorithms to ensure a fair comparison?

Improve this question
$\endgroup$
2
  • $\begingroup$ Wall-clock time? $\endgroup$
    – Cuhrazatee
    Jul 25, 2022 at 0:48
  • $\begingroup$ Do you mean something other than asymptotic computational complexity, or the asymptotic scaling of oracle calls? $\endgroup$
    – Mark Spinelli
    Jul 27, 2022 at 3:28

0

Reset to default

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.

Browse other questions tagged or ask your own question.