# 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.

• – Discrete lizard Apr 1 '18 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. – Discrete lizard Apr 1 '18 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. – Aritra Apr 1 '18 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? – Niel de Beaudrap Apr 1 '18 at 14:11