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.

  • 1
  • $\begingroup$ 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. $\endgroup$ Apr 1, 2018 at 13:04
  • $\begingroup$ 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. $\endgroup$
    – Aritra
    Apr 1, 2018 at 13:21
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 1, 2018 at 14:11

1 Answer 1


I am only considering the effect of projective measurement and no-cloning.

Consider that a (long) realistical quantum computation would have to involve quantum error correction which only works if the errors are rather limited: Your projective measurement will be rather close (to within 1% or so) to not incorporating errors other than quantum projection noise. This is usually irrelevant because a typical algorithm will not require you to do state tomography but instead distill a binary result into the qubits to be measured in the end. If it would involve state tomography, the (asymptotic) overhead would enter the big-O notation.

There is indeed some overhead from the no-cloning theorem: The (quantum part of the) result of e.g. Shor's algorithm must be read more than once to form the greatest common denominator. Such an overhead obviously depends on the algorithm; in the case of Shor's algorithm, it is small (typically 2 to 3, in detail depending if you are willing to take care of small factors classically, as is simple). A similarly (but not quite as) small overhead occurs if you want to generalize Grover's algorithm to the case where an unknown number of solutions exist.

  • $\begingroup$ indeed I should take into account QEC/mapping but there's no clear winning scheme yet. I can leave that part to the underlying compiler and microarchitecture, but to embed the quantum algorithm in an application, I need to know the full pipeline and the gate complexity (after unrolling it for the expected number of iterations). However, not all quantum algorithms have a distillation that gives a high probability of the solution state, (.e.g. quantum associative memories, quantum pattern matching). $\endgroup$
    – Aritra
    Apr 1, 2018 at 13:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.