Is the common Computer Science usage of 'ignoring constants' useful when comparing classical computing with quantum computing?

Question

Daniel Sank mentioned in a comment, responding to (my) opinion that the constant speed-up of $10^8$ on a problem admitting a polynomial time algorithm is meager, that

Complexity theory is way too obsessed with infinite size scaling limits. What matters in real life is how fast you get the answer to your problem.

In Computer Science, it is common to ignore constants in algorithms, and all in all, this has turned out to work rather well. (I mean, there are good and practical algorithms. I hope you will grant me (theoretical) algorithms researchers have had a rather large hand in this!)

But, I do understand that this is a slightly different situation as now we are:

1. Not comparing two algorithms running on the same computer, but two (slightly) different algorithms on two very different computers.
2. We now are working with quantum computers, for which perhaps traditional perfomance measurements may be insufficient.

In particular, the methods of algorithm analysis are merely methods. I think radically new computing methods calls for a critical review of our current performance evaluation methods!

So, my question is:

When comparing the performance of algorithms on a quantum computer versus algorithms on a classical computer, is the practice of 'ignoring' constants a good practice?

Answer 1

The common Computer Science usage of 'ignoring constants' is only useful where the differences in performance of various kinds of hardware architecture or software can be ignored with a little bit of massaging. But even in classical computation, it is important to be aware of the impact of architecture (caching behaviour, hard disk usage) if you want to solve difficult problems, or large problems.

The practise of ignoring constants isn't a practise which is motivated (in the sense of being continually affirmed) from an implementation point of view. It is driven mostly by an interest in an approach to the study of algorithms which is well-behaved under composition and admits simple characterisations, in a manner close to pure mathematics. The speed-up theorems for Turing Machines meant that any sensible definition couldn't attempt to pin down the complexity of problems too precisely in order to arrive at a sensible theory; and besides, in the struggle to find good algorithms for difficult problems, the constant factors weren't the mathematically interesting part...

This more abstract approach to the study of algorithms was and is largely fruitful. But now we are confronted with a situation where we have two models of computation, where

• One is in an advanced state of technological maturity (classical computation); and
• One is in a very immature state, but is attempting to realise a theoretical model which can lead to significant asymptotic improvements (quantum computation).

In this case, we can ask whether it even makes sense to consider the asymptotic benefit, with or without careful accounting of the constant factors. Because of the extra effort which may be required to perform scalable quantum computing, not only scalar factors but polynomial "speedups" in theoretical performance may be washed out once all of the overhead in realising a quantum algorithm is taken into account.

In these early days, there may also be significant differences in performance to different approaches to quantum architecture. This could make the choice of architecture as important (if not more important) to how well an algorithm performs than asymptotic analysis — just as it would matter a lot to you whether you do your conventional computation on a von Neumann machine or a highly distributed network with significant latencies.

The actually important thing for practical computation is — and has always been — not just algorithms, but implementations of algorithms: an algorithm realised in a certain way, on a certain architecture. The common practise of asymptotic analysis which ignores constant factors allows us to pay attention to the systematic, mathematical reasons for differences in the performance of algorithms, and is practically motivated on those occasions when the architectural differences are not so large as to dominate the practical performance.

With respect to quantum technologies, we are not in that happy situation where we can safely gloss over constant factors in any practical context. But perhaps one day we will be able to do so. This is the long game of quantum information technologies — until now, nearly the only game that academic computer scientists have ever played, as far as quantum information technology is concerned. Anticipating that day when quantum technology finds its footing, it will be good for us to continue pursuing asymptotic analysis, as one line of investigation in the performance of quantum algorithms.

Answer 2

First, there are no scaling analyses of quantum devices like we have for algorithms on CMOS hardware. So talking about $O\left(f\left[N\right]\right)$ is flawed. Second, given the lack of theoretical backing, we have to do scaling analyses with experiments. However, the currently accessible problem sizes ($N$) are rather limited. As such, we do not even know if we are in the asymptotic limit ("the true behavior of the device").

Therefore, neglecting prefactors (i.e. constant factors) might be premature. Purists will argue that only an improvement in the scaling ("change in slope") is true speedup. I agree, however, if your quantum device scales as well as the best classical algorithms yet has a $10^{10}$ prefactor, I would call it useful for applications.

Unfortunately, the current state of the art is D-Wave scaling as good as the best algorithms, but with only a $\approx300$ factor advantage over code run on a single core. Moreover, this is a synthetic benchmark problem and not an application of interest. Far from disruptive... See https://arxiv.org/abs/1711.01368 for more information.

Answer 3

You can't ignore the constant factors when comparing quantum computation to classical computation. They're too large.

For example, here is an image from some slides I presented last year:

The things along the bottom are magic state factories. They have a footprint of 150K physical qubits. Since the AND gate uses 150K qubits for 0.6 milliseconds, we surmise that the spacetime volume of a quantum AND gate is on the order of 90 qubit seconds.

One of my coworkers' goals is to use 1 cpu per 100 qubits when performing error correction. So we might say that 90 qubit seconds requires 0.9 cpu seconds of work. We've made the quantum constructions several times more efficient since the above image was made, so let's call it 0.1 cpu seconds instead.

(There are many assumptions that go into these estimates. What kind of architecture, error rates, etc. I'm only trying to convey an order of magnitude idea.)

It takes 63 AND gates to perform a 64 bit addition. 63*0.1 cpu seconds ~= 6 cpu seconds. Quantumly, a 64 bit addition costs more than a CPU second. Classically, a 64 bit addition costs less than a CPU nanosecond. There's easily a constant factor difference of 10 billion here. If you compare against a parallel classical machine, such as a GPU, the numbers get even worse. You can't ignore constant factors with that many digits.

For example, consider Grover's algorithm, which allows us to search for a satisfying input to a function in sqrt(N) evaluations of the function instead of N evaluations. Add in the constant factor of 10 billion, and solve for where the quantum computer starts to require fewer evaluations:

$$\begin{align} N &> 10^{10} \sqrt{N}\\ N &> 10^{20} \end{align}$$

Grover's algorithm can't parallelize the evaluations, and the evaluations require at least one AND gate, so basically you only start seeing CPU time benefits when the search is taking tens of millions of years.

Unless we make the constant factors a lot better, no one is ever going to use Grover search for anything useful. Right now the quantum-vs-classical situation is exponential advantage or bust.

Answer 4

While other answers provide good points, I feel that I still disagree a bit. So, I will share my own thoughts on this point.

In short, I think featuring the constant 'as is' is a wasted opportunity at best. Perhaps it is the best we are able to get for now, but it is far from ideal.

But first, I think a brief excursion is nessecary.

When do we have an effective algorithm?

When Daniel Sank asked me what I would do if there was an algorithm for factoring prime numbers with a $10^6$ factor speedup on a test set of serious instances, I first replied that I doubt this would be due to algorithmic improvements, but other factors (either the machine or the implementation). But I think I have a different response now. Let me give you a trivial algorithm that can factor very large numbers within milliseconds and is nevertheless very ineffective:

1. Take a set $P$ of (pretty big) primes.
2. Compute $P^2$, the set of all composites with exactly two factors from $P$. For each composite, store which pair of primes is used to construct it.
3. Now, when given an instance from $P^2$, simply look at the factorization in our table and report it. Otherwise, report 'error'

I hope it is obvious that this algorithm is rubbish, as it works only correctly when our input is in $P^2$. However, can we see this when given the algorithm as a black box and "by coincide" only test with inputs from $P$? Sure, we can try to test a lot of examples, but it is very easy to make $P$ very big without the algorithm being ineffective on inputs from $P^2$ (perhaps we want to use a hash-map or something).

So, it isn't unreasonable that our rubbish algorithm might be coincidentally seem to have 'miraculous' speedups. Now, of course there are many experiment design techniques that can mitigate the risk, but perhaps more clever 'fast' algorithms that still fail in many, but not enough examples can trick us! (also note that I'm assuming no researcher is malicious, which makes matters even worse!)

So, I would now reply: "Wake me up when there is a better performance metric".

How can we do better, then?

If we can afford to test our 'black box' algorithm to on all cases, we cannot be fooled by the above. However, this is impossible for practical situations. (This can be done in theoretical models!)

What we can instead do is to create a statistical hypothesis for some parameterized running time (usually for the input size) to test this, perhaps adapt our hypothesis and test again, until we get a hypothesis we like and rejecting the null seems reasonable. (Note that there are likely other factors involved I'm ignoring. I'm practically a mathematician. Experiment design is not something within my expertise)

The advantage of statistically testing on a parameterization (e.g. is our algorithm $O(n^3)$? ) is that the model is more general and hence it is harder to be 'cheated' like in the previous section. It is not impossible, but at least the statistical claims on whether this is reasonable can be justified.

So, what to do with the constants?

I think only stating "$10^9$ speedup, wow!" is a bad way of dealing this case. But I also think completely disregarding this result is bad as well.

I think it is most useful to regard the curious constant as an anomaly, i.e. it is a claim that in itself warrants further investigation. I think that creating hypotheses based on more general models than simply 'our algorithm takes X time' is a good tool to do this. So, while I don't think we can simply take over CS conventions here, completely disregarding the 'disdain' for constants is a bad idea as well.