Recent articles have been published describing something called Neven’s Law. It states that if the resources required to perform a classical simulation of a quantum computer doubles every time one adds a qubit and if researchers are increasing the quantum computers capability (a function of both the number and quality of the qubits) of qubits every 12 or so months then the growth is a double exponential increase which could be stated mathematically as 22n.
While this is correct and an important consideration when one is trying to simulate a quantum computer on a classical computer, it can be easily misinterpreted if one is trying to understand the future improvement quantum computers will bring to solving specific problems. Normally, when one talks about the growth of a technology, the comparison is usually a comparison against the previous generation of the same technology. For example, when Gordon Moore postulated Moore’s Law, he did not compare the growth of transistors on a chip versus the growth in the number of abacuses required to achieve a similar computing capability.
Or another way is to look at the increase in the amount of work that can be performed from one generation to the next. Let’s take a specific hypothetical example. Suppose someone is given a 100 qubit quantum computer and develops a program that uses Shor’s algorithm to factor a 25 bit number. A year later that person is given a 200 qubit quantum computer. Could they use their program to factor a 50 bit number (exponential growth) or a 100 bit number (double exponential growth)? The answer is a 50 bits number. So if the quantum computers increase their capability exponentially year by year, the size of the number that can be factored will also increase at the same rate. We do not know of any problem where if the size of a quantum computer is doubled, the size of the problem that can be solved is quadrupled.
In the language of a quantum physicist, one might say that the results of a measurement would depend upon what basis is used to perform the measurement. Yes, if you compare the capability of a quantum computer versus a classical computer, you can see a double exponential growth. However, we do expect that quantum computers will achieve quantum supremacy for certain problems in the near future. And at that point, comparison against classical computers will become irrelevant. After that, the only meaningful comparison will be from one generation of quantum computer to the next and that will certainly not show a double exponential rate of improvement.
6/22/2019