How scalable are quantum computers when measurement operations are considered?

Question

From a high-level point of view, given a quantum program, typically the last few operations are measurements.

In most cases, in order to extract a useful answer, it is necessary to run multiple times to reach a point where it is possible to estimate the probability distribution of the output q-bits with some level of statistical significance.

Even when ignoring noise, if the number of q-bits of the output increases, the number of required runs will increase too. In particular, for some output probability distributions it is likely that the number of required samples can be very high to obtain some sensible statistical power.

While increasing the number of q-bits seems to indicate an exponential growth, the number of measurements required (each run taking x nanoseconds) seem to limit how will quantum computation do scale.

Is this argument sensible or there is some critical concept that I am missing?

Answer 1

Some near-term quantum algorithms rely on getting lucky with the measurements, and in fact these algorithms will not scale efficiently to large sizes. But most quantum algorithms don't have this problem; it is required that the amount luck needed [i.e. retries] scales only polynomially with the problem size.

For example, Shor's algorithm fails if the quantum part outputs 0. But the chance of 0 becomes smaller and smaller as N (the number to factor) becomes larger. Shor's algorithm also fails if the base B you pick randomly has a k such that to B^k = -1 (mod N), but AFAIK the chance of that happening stays constant as N increases so you don't expect to have to pick too many Bs.

In other words, yes you have identified a problem that quantum algorithms do in fact have to avoid. This is the difference between BQP and PostBQP.