A new law to describe the speed of development of quantum computers?

Niven's law says that quantum computers improve at "double exponential speed." If he can stand the test of time, then wait for quantum superiority is not long.

Google's Foxtail Quantum Processor



In December 2018, scientists from Google AI performed calculations on the best quantum processor from Google. They were able to reproduce these calculations on a regular laptop. Then in January they launched the same test on an improved version of the quantum chip. This time they needed a powerful desktop computer to simulate the result. And by February, they no longer had the classic computers capable of simulating their quantum rivals. To do this, researchers had to request processor time on a huge network of servers.



“Sometime in February, I had to make a few calls and say,“ Hey, we need more quotas, ”said Hartmut Niven , director of Google’s Quantum Artificial Intelligence Laboratory. “We ran tasks that required a million processors.”



This rapid improvement led to the so-called “Niven's Law,” a new rule that describes how fast quantum computers catch up with classic computers. The rule was born as an internal observation, and only then Niven mentioned it in May at the Google Quantum Spring symposium. There, he said that quantum computers increase computing power compared to classic computers with "double exponential" speed - staggeringly fast movement.



With double exponential growth, “at first it seems that nothing is happening, nothing is happening, and then oh - and suddenly you are in another world,” Niven said. “That is what we are observing.”



Even exponential growth is a fairly rapid phenomenon. It means that a certain quantity grows, as the powers of two: 2 ¹ , 2 ² , 2 ³ , 2 ⁴ . At first, the increase is not so noticeable, but the subsequent ones are huge. Moore's Law, the famous rule by which computing power doubles approximately every two years, is exponential.



Double exponential growth looks more significant. Instead of increasing the degrees of two, the value grows as the degrees of the degree of two: 2 ^{2 1} , 2 ^{2 2} , 2 ^{2 3} , 2 ^{2 4} . Double exponential growth was highlighted in a recent article, “ Computer Specialists Expanding the Limits of Testable Knowledge, " and described the enormous growth rate of the complexity of certain computational problems. The double exponential growth is so unique that it is difficult for him to find examples in the real world. And the speed of progress in quantum computing could be the first such example.



The double exponential speed with which, according to Niven, quantum computers are catching up with classical computers, is the result of a combination of two exponential factors. First, quantum computers have an internal exponential advantage over classical ones: if, for example, there are four qubits in a quantum circuit, then its computing power is comparable to a circuit of 16 ordinary bits. That would be true even without an improvement in quantum technology.



The second exponential factor appears due to the rapid improvement of quantum processors. Niven say Google’s best quantum chips have been improving exponentially lately. This speed is due to a decrease in the number of errors. This allowed engineers to build larger quantum processors, Niven said. If classical computers require exponentially more computing power to simulate quantum processors, and the power of these quantum processors grows exponentially over time, the result is a double exponential relationship between quantum and classical machines.





Hartmut Niven, Director of Google’s Quantum Artificial Intelligence Lab



Not everyone is convinced of this. Firstly, classic computers do not stand still. Regular chips continue to improve, even if Moore’s law no longer works . In addition, computer scientists are constantly coming up with more efficient algorithms that help classic computers keep up.



"Given all the moving parts, including improvements from the classical and quantum sides, it's hard to call this growth double exponential," said Andrew Childs , one of the directors of the joint center for quantum information and computer science at the University of Maryland.



Although the exact speed with which quantum computers are catching up with classical computers can be a subject of debate, there is no doubt about the rapid improvement of quantum technology.



“I think that the undeniable reality of this progress has passed the ball to the side of people who believe that scalable quantum computers will not work,” wrote Scott Aaronson , an IT specialist at the University of Texas at Austin, by email. “Now they will have to clearly articulate where and why this progress will stop.”



The main goal of the field of quantum computing is to produce effective quantum calculations that cannot be simulated in a reasonable amount of time on the most powerful classical computers (and the Summit supercomputer of the Oak Ridge National Laboratory is now considered the most powerful). And among various research groups developing quantum computers, Google is particularly loud in declaring its pursuit of this goal, known as "quantum excellence."



So far, quantum superiority remains elusive - sometimes it seems that it has just been achieved, but so far has failed. But if Niven’s law is implemented, then this goal is short. Niven does not say exactly when, in his opinion, the Google team will achieve quantum superiority, but admits that this can happen soon.



“We often say that we think we will achieve it in 2019,” Niven said. “All the signs are already there.”