Quantum Computing - Neven's Law of Double Exponential Growth

 

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

Most of you will be familiar with Moore's Law that predicts exponential growth in computing power - a doubling every 18 months. In the world of Quantum Computing, there is a law that predicts double exponential growth. What does this mean ? Is it true ? Who made this law ?

1.1 Who is Neven?

Hartmut Neven is an Engineering Director at Google. He is the founder of the the Quantum AI Lab. The objective of this lab is to fabricate quantum processors and dvelop novel quantum algorithms to dramatically accelerate computational tasks for machine intelligence.

2 What does Neven’s Double Exponential Law mean?

https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/

Neven 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. Even exponential growth is pretty fast. It means that some quantity grows by powers of 2: 2¹, 2², 2³, 2⁴ – 2,4,8,16…. 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 Doubly exponential growth is far more dramatic. Instead of increasing by powers of 2, quantities grow by powers of powers of 2: 221,222,223,224. 2exp2exp1, 2exp2exp2, 2exp2exp3, 2exp2exp3 – 4, 16, 256, 6536… !

1.3 What is the origin of the double exponential rate?

https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/

The doubly exponential rate at which, according to Neven, quantum computers are gaining on classical ones is a result of two exponential factors combined with each other. The first is that quantum computers have an intrinsic exponential advantage over classical ones: If a quantum circuit has four quantum bits, for example, it takes a classical circuit with 16 ordinary bits to achieve equivalent computational power. This would be true even if quantum technology never improved.

The second exponential factor comes from the rapid improvement of quantum processors. Neven says that Google’s best quantum chips have recently been improving at an exponential rate. (This rapid improvement has been driven by a reduction in the error rate in the quantum circuits. Reducing the error rate has allowed the engineers to build larger quantum processors, Neven said.) If classical computers require exponentially more computational power to simulate quantum processors, and those quantum processors are growing exponentially more powerful with time, you end up with this doubly exponential relationship between quantum and classical machines.

1.4 BTW, What Is Quantum Computing? 

https://spectrum.ieee.org/tech-talk/computing/hardware/how-googles-quantum-supremacy-plays-into-quantum-computings-long-game

Quantum computing harnesses the rules of quantum physics that hold sway over some of the smallest particles in the universe in order to build devices very different from today’s “classical” computer chips used in smartphones and laptops. Instead of classical computing’s binary bits of information that can only exist in one of two basic states, a quantum computer relies on quantum bits (qubits) that can exist in many different possible states. It’s a bit like having a classical computing coin that can only go “heads” or “tails” versus a quantum computing marble that can roll around and take on many different positions relative to its “heads” or “tails” hemispheres.

Because each qubit can hold many different states of information, multiple qubits connected through quantum entanglement hold the promise of speedily performing complex computing operations that might take thousands or millions of years on modern supercomputers. To build such quantum computers, some research labs have been using lasers and electric fields to trap and manipulate atoms as individual qubits.

More on Quantum Computing

Quantum Computing for the Curious - https://quantum.country/qcvc

Quantum Computing for the determined –

 http://michaelnielsen.org/blog/quantum-computing-for-the-determined/

1.5 Quantum Supremacy

https://spectrum.ieee.org/tech-talk/computing/hardware/how-googles-quantum-supremacy-plays-into-quantum-computings-long-game

Google’s claim to have demonstrated quantum supremacy—one of the earliest and most hotly anticipated milestones on the long road toward practical quantum computing. The leaked draft of Google’s paper likely represents the first experimental proof of the long-held theoretical premise that quantum computers can outperform even the most powerful modern supercomputers on certain tasks, experts say. 

1.6 Google’s Experiment on Quantum Supremacy

Google’s experiment tested whether the company’s quantum computing device, named Sycamore, could correctly produce samples from a random quantum circuit—the equivalent of verifying the results from the quantum version of a random number generator. In this case, the quantum circuit consisted of a certain random sequence of single- and two-qubit logical operations, with up to 20 such operations (known as “gates”) randomly strung together.

The Sycamore quantum computing device sampled the random quantum circuit one million times in just three minutes and 20 seconds. When the team simulated the same quantum circuit on classical computers, it found that even the Summit supercomputer that is currently ranked as the most powerful in the world would require approximately 10,000 years to perform the same task.

Applications of Quantum Computing – a very good compilation

https://medium.com/@jackkrupansky/what-applications-are-suitable-for-a-quantum-computer-5584ef62c38a

If you wish to read more about this topic - Scott Aaranson’s FAQ on Quantum Supremacy – https://www.scottaaronson.com/blog/?p=4317

Navin Kabra on understanding Quantum Supremacy - https://www.linkedin.com/pulse/understanding-quantum-supremacy-navin-kabra/?trackingId=yM%2BxJ5Y7TsyDwSlx%2BTpvPA%3D%3D

Further Reading

https://www.quantamagazine.org/computer-scientists-expand-the-frontier-of-verifiable-knowledge-20190523/

Quantum Complexity Theory – Bernstein & Vazirani

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.655.1186&rep=rep1&type=pdf

Free Will – Ilyas Khan -

Scott Aaranson’s Paul Bernay Lectures - https://www.scottaaronson.com/blog/?p=4301

Quantum Computing & Information Processing – Nielsen and Chuang – http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf

D-Wave’s Quantum Computing Primer –

https://www.dwavesys.com/tutorials/background-reading-series/quantum-computing-primer

Quantum Mechanics – Nobel Physics Prize - https://medium.com/@jackkrupansky/nobel-physics-prize-lectures-related-to-quantum-mechanics-eb71cca69388

Quantum Computing - https://medium.com/@jackkrupansky/list-of-my-papers-on-quantum-computing-af1be336410e

Mobility - https://eandt.theiet.org/content/articles/2019/04/how-quantum-computers-are-transforming-travel/

https://www.dwavesys.com/sites/default/files/1663_JULY-2016-Not-Magic-Quantum.pdf

TED-like Talks

Quantum Computing is the Future – Jason Ball - https://www.youtube.com/watch?v=7hg5eaGpjDg

How Quantum Computers work – Catalina Curceaunu https://www.youtube.com/watch?v=3xHVcKeuF5o

Quatum Computing – AI is here – Geordie Rose (D Wave) - https://www.youtube.com/watch?v=PqN_2jDVbOU

Toward a Quantum World – Dario Gil (IBM Research) - https://www.youtube.com/watch?v=yy6TV9Dntlw

Quantum Computing demystified – Ilyas Khan - https://www.youtube.com/watch?v=43---kMJrlA

What Quantum Computing isn’t – Scot Aaronson - https://www.youtube.com/watch?v=JvIbrDR1G_c