Neven’s law states that quantum computers are improving at a “doubly exponential” rate. If it holds, quantum supremacy is around the corner.

Quote Originally Posted by Quanta Magazine
In December 2018, scientists at Google AI ran a calculation on Google’s best quantum processor. They were able to reproduce the computation using a regular laptop. Then in January, they ran the same test on an improved version of the quantum chip. This time they had to use a powerful desktop computer to simulate the result. By February, there were no longer any classical computers in the building that could simulate their quantum counterparts. The researchers had to request time on Google’s enormous server network to do that.

“Somewhere in February I had to make calls to say, ‘Hey, we need more quota,’” said Hartmut Neven, the director of the Quantum Artificial Intelligence lab. “We were running jobs comprised of a million processors.”

That rapid improvement has led to what’s being called “Neven’s law,” a new kind of rule to describe how quickly quantum computers are gaining on classical ones. The rule began as an in-house observation before Neven mentioned it in May at the Google Quantum Spring Symposium. There, he said that quantum computers are gaining computational power relative to classical ones at a “doubly exponential” rate — a staggeringly fast clip.

With double exponential growth, “it looks like nothing is happening, nothing is happening, and then whoops, suddenly you’re in a different world,” Neven said. “That’s what we’re experiencing here.”

Even exponential growth is pretty fast. It means that some quantity grows by powers of 2: 2^1, 2^2, 2^3, 2^4. The first few increases might not be that noticeable, but subsequent jumps are massive. Moore’s law, the famous guideline stating (roughly) that computing power doubles every two years, is exponential.

Doubly exponential growth is far more dramatic. Instead of increasing by powers of 2, quantities grow by powers of powers of 2: 2^2^1, 2^2^2, 2^2^3, 2^2^4. Doubly exponential growth featured in the recent Quanta story “Computer Scientists Expand the Frontiers of Verifiable Knowledge,” where it described the extreme rate at which certain computational problems increase in complexity. Doubly exponential growth is so singular that it’s hard to find examples of it in the real world. The rate of progress in quantum computing may be the first.