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?

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


Your Answer

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

Browse other questions tagged or ask your own question.