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.

closed as unclear what you're asking by Norbert Schuch, MEE was the missing bracket, Mithrandir24601♦, Discrete lizard, ItamarG3Apr 2 '18 at 8:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• – 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