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 - Reinstate Monica, Mithrandir24601, Discrete lizard, ItamarG3 Apr 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.

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

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 '18 at 13:33

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