# How to compare a quantum algorithm with its classical version? [closed]

The Quantum Algorithm Zoo includes a host of algorithms for which Quantum Computing offers speedups (exponential, polynomial, etc). However, those speedups are based on asymptotic computational complexity (Big-O complexity).

For a realistic implementation on a quantum computer (or even a simulator), the algorithm might require other add-ons to get a satisfiable result. For e.g., for multiple quantum state tomography trials, or probabilistic cloning. I am not considering an ideal quantum computer, thus, overheads of physical to logical qubit mapping for Quantum Error Correction; overheads of nearest neighbour mapping; or experimental environmental errors are not considered. I am only considering the effect of projective measurement and no-cloning.

How can I compare a quantum algorithm taking into account such factors? The overheads might be polynomial, linear, or even constant, so asymptotically it will outperform the corresponding classical algorithm. But, asymptotically means, for a large enough problem size. I am interested in determining if that cross-over point (quantum supremacy problem size) is realistic for my case.

The specific algorithm I am currently working with is an improvement of Grover's search as proposed by Biham et. al, where the initial amplitude distribution is not uniform, and there are multiple solutions.

• Apr 1, 2018 at 13:02
• I think that beyond the answers already given to the two questions I linked, you're not going to get much more than 'It depends'. Still, someone might prove me wrong by posting an answer here that is dissimilar to the answers in the linked questions. Apr 1, 2018 at 13:04
• The question is indeed similar, but I am pretty convinced that at least in near-term, we need to take into account the constants (so the answers to the question leads to this question). How can we have realistic estimates of the constants from different overheads I mentioned. Apr 1, 2018 at 13:21
• When you write "multiple quantum state tomography trials, or probabilistic cloning", I'm not sure what you mean. I know (or think that I know) what quantum state tomography is, and I know what probabilistic cloning is, but I don't know in what way these would be important for quantum algorithms in a way that we would need to consider the "overhead" they introduce. Could you expand a little on this point? Apr 1, 2018 at 14:11