Why do we need quantum computing?

Author's Note

At the request of a friend, I was supposed to write a popular science video about quantum computing, but I accidentally wrote too much. I think it may be helpful to the public, so I shamelessly post the full manuscript here. In fact, there are many popular science articles about quantum computing, and I have written them before, but the perspective of this article is slightly different: Why do we need quantum computing? Why has it attracted so much attention in recent years? If these questions can be answered, it may make some people feel relieved: quantum computing is not a fantasy of scientists, but a product of this era. Just as quantum mechanics and relativity are the glorious marks left by mankind in the 20th century, quantum computing may also become another eternal mark left by mankind in the 21st century.

Written by | Wuxie

Produced by: Science Popularization China-Starry Sky Project

We live in the age of computing

Human beings have an endless desire for computing power. Since the days of knotting, the improvement of computing power has been closely related to the progress of civilization. The Pythagorean school of ancient Greece even regarded it as the truth. Today, we are so accustomed to the benefits of computing that most people ignore its greatness. When we slide on the screen, enter a keyword, and the search engine pops up the results we want, these operations can be completed in a few seconds. How many people know how many "calculations" have been experienced behind this? While we are happily drooling and watching short videos, how many people know that the machine is desperately calculating which video to push to you next? At this time when the epidemic situation is severe, each of us cooperates with scanning codes and checking nucleic acids. How many people can perceive the great achievements of "computing" in fighting the epidemic? Today, our computing power has reached its peak. Machines have conquered the last intellectual fortress that humans are proud of-Go. Next, machines are trying to conquer autonomous driving and conquer the metaverse. It can be said that we live in an era of computing.

Knotted Cord Records of the Inca Civilization: Khipu

Today's super computing power is due to a nonlinear component called "transistor". It is made of the most ordinary material in nature - silicon, but it concentrates the most advanced wisdom of mankind. It is everywhere around us, but it is born in the cleanest dust-free factory. It is changing our lives so rapidly, but now we Chinese find ourselves controlled by others. This is the chip.

In the top silicon semiconductor chips, tens of billions of transistors follow a binary logic called "Boolean algebra" to perform operations. This logic is not efficient, but it is very flexible and universal. After more than 50 years of exponential growth at the speed of Moore's Law, it has eliminated all opponents and has become almost the only computing tool.

Moore's Law has been in existence for more than 50 years and is still valid today, with corresponding exponential growth in computing power. It is a commonplace to say that as transistors get smaller and smaller, approaching the nanometer level, Moore's Law will eventually cease. What I want to say is that in today's Internet age, even if Moore's Law is valid for a long time, the development of computing power is far behind the speed of data expansion on the Internet. The amount of information we can mine from the Internet through computing will be pitifully small compared to the amount of information actually contained in the Internet. If we imagine data as a mine and computing power as a mining machine, then the mining machine will become increasingly dwarfed by the mine. In this case, the human demand for new computing power that goes beyond the current paradigm is imminent. In this context, we can understand why companies like Google are so concerned about quantum computing and are willing to dive in themselves. Because it owns the mine. Imagine sitting on a gold mine but having no tools and having to pick it up with your hands!

Fifty Years of Moore's Law

Quantum computing becomes reality

Having said so much, the topic finally came to quantum computing. Many people tend to associate quantum with mysterious phenomena, such as being both a wave and a particle, teleportation, etc., but this is actually unnecessary. When I talk about quantum with others, I am most afraid of falling into discussions such as nihilism and epistemology, because I am actually an experimentalist, not a philosopher. I like to look at quantum from a pragmatic perspective: it accurately describes the underlying behavior patterns of matter; it is still very accurate. Well, let's see what extraordinary things we can do under the rules of quantum? Using quantum to do computing is definitely one of the boldest ideas of the last century, because in that era, the ability to control the quantum world was very different from that of today, so that the first few important quantum algorithms, including Shor's algorithm and Grover's algorithm, were actually developed by mathematicians - they studied this as a mathematical toy and never thought about realizing it.

Entering the 21st century, the situation is very different. The 2012 Nobel Prize in Physics was awarded to Serge Haroche and David J. Wineland for their "groundbreaking experimental progress in measuring and manipulating independent quantum systems." They trapped atoms for the first time and used the interaction between light and atoms to manipulate and measure atomic quantum states - this was actually the beginning of ion trap quantum computing. This work opened the door to manipulating and reading quantum states, and also ignited the fire of hope for the physical realization of quantum computing. From then on, quantum bits, quantum gates, and quantum computing were no longer just in the mathematical and theoretical stages.

2012 Nobel Prize in Physics Winners

At the turn of the century, there was another very important breakthrough. Cai Zhaoshen's research group at the RIKEN Institute of Physical and Chemical Research in Japan discovered the phenomenon of quantum oscillations on a superconducting "island" for the first time. The biggest difference from the work of Haroche and Wineland is that the quantum system at this time is a "macroscopic quantum system" - electrons at the macroscopic level jointly participate in the entire quantum process. This "superconducting Cooper pair box" is the predecessor of superconducting quantum computing, one of the most popular quantum computing candidates today. Macroscopic quantum systems are easy to control and read, and their manufacturing process is largely compatible with semiconductor chips, which has led to the system bursting out with super vitality in the next decade. (For more information on superconducting quantum bits, please refer to "When Quantum Computing Meets Superconductivity: A Beautiful Encounter")

Macroscopic quantum bits: Cooper pair box | Source: Nakamura, Y., Pashkin, YA & Tsai, JS Coherent control of macroscopic quantum states in a single-Cooper-pair box. Nature 398, 786–788 (1999).

Early superconducting quantum bits, including the "Cooper pair box" mentioned above, as well as flux quantum bits and phase quantum bits, have solved many technical problems related to manipulation, coupling, and reading, but they have always been troubled by an important indicator - decoherence time (quantum "lifetime"). Decoherence time refers to the characteristic time when the quantum properties of a system disappear and tend to the classical system. We know that no system can be completely isolated, otherwise the system is the same as non-existence. As a quantum bit that can do "computing", it is even less likely to be isolated. It must interact with the outside world, otherwise how can we manipulate it and measure it? And if there is interaction, it will inevitably lead to the loss of quantum information. Particles in nature, such as atoms, can have a very long lifespan. They only have very weak interactions with photons, which becomes a double-edged sword: because the interaction is weak, the quantum properties are very strong; at the same time, because of the weak interaction, it is also difficult for us to manipulate and measure it. This also partially understands why Haroche and Wineland's work can win the Nobel Prize - it is indeed too difficult.

The situation of superconducting quantum bits is just the opposite. The hyperfine energy levels that make up the quantum bits are caused by the collective behavior of a macroscopic number of Cooper pairs. They are in a more macroscopic solid system, where the environment is much worse than that of a single atom. Photons from nowhere, remaining electrons, and changes in charge and magnetic field caused by external electromagnetic field disturbances will all have an impact on the quantum bits. In addition, it is a macroscopic degree of freedom, so the coupling strength with these external degrees of freedom is also very strong, causing the information of the quantum bits to be lost in a very short time. However, it is precisely because of this that we can manipulate and read them in a very short time through the means of electromagnetic field regulation, so fast that we can't even say "pull, pull, pull the carrots..." (See "The Lifetime of Superconducting Quantum Bits Exceeds 500 Microseconds-Although It's Only a Moment in the World, It's of Extraordinary Significance")

The decoherence time problem ushered in a turning point in 2007. At that time, scientists in the field had already noticed the effect of increasing capacitance on suppressing charge noise, and Koch et al. from Yale University and You Jianqiang from my country almost simultaneously and systematically studied the effect of increasing bypass capacitance on the decoherence time in Cooper pair boxes and flux qubit systems, respectively. The former is the currently popular transmon qubit. Since then, the decoherence time of superconducting qubits has rapidly reached the order of 10 microseconds to 100 microseconds, which is a very long time compared to the manipulation time of 10 nanoseconds. Following closely, the Martinis group at the University of California, Santa Barbara, quickly proposed a scalable solution based on transmon qubits and a systematic electronic solution, laying the foundation for superconducting quantum computing to enter engineering. The story behind this is that this group joined Google and built the "Sycamore" chip for Google, creating the sensational milestone of quantum supremacy. This story can be opened in a separate issue, so I will not go into it for now. (See "IBM refutes Google, quantum supremacy vs. quantum advantage, how far are we from quantum computing?" and "Google's "quantum supremacy" core figure: Why I resigned from Google?")

Google's Sycamore chip (Source: wikipedia.org)

In short, today, quantum computing has gradually transformed from a toy of mathematicians and a concept of theoretical physicists into reality. This is due to the efforts of a large number of experimental physicists and engineers, which is difficult for outsiders to understand. In any case, with these experiments, technological progress and accumulation, we are qualified to talk about the future of quantum computing and have the confidence to brag about how quantum computing will crush traditional computing. Next, let's brag!

The Power of Quantum Computing

The concept of bit comes from Shannon's information theory. Some data show that this concept was created by mathematicians earlier (in the 1940s). It is used to represent the smallest unit of information under binary algebraic logic. In traditional computers, information is encoded, processed, transmitted and acquired in bits. In the quantum world, the smallest unit of information becomes a quantum bit, which is also the unit of information encoding, processing, transmission and acquisition, but now it is carried out in the quantum field. Logically, it is a two-state system that can be coherently superimposed; physically, it is a distinguishable (quasi) two-level system. Multiple quantum bits together can form a composite system. If they can be entangled, it is the moment to witness a miracle.

Claude Shannon, founder of information theory | Source: Internet

Entanglement is unique to the quantum world. It hides very profound physics that cannot be fully understood until now, but we have confirmed its existence through a large number of experiments. Take the composite system formed by two quantum bits as an example: this system can be in a certain quantum state. At this time, if we take them as a whole, the system is quantum, but once we look at a certain quantum bit alone, the system is no longer quantum. In other words, the composite system can only be viewed as a whole, and no information can be obtained from its subsystems. Mathematically speaking, the entangled system opens up a larger direct product space, and the dimension of this direct product space grows exponentially with the number of bits. Here are a few terrifying numbers: when N=50, the dimension of this space is approximately equivalent to the number of calculations per second of the most advanced supercomputer today; when N=300, the dimension has exceeded the sum of all atoms in the entire known universe (there are about 1023 atoms in a glass of water).

This terrifying dimensional expansion brought about by entanglement provides a huge encoding space for computational problems, allowing some problems to seek more efficient solutions in higher dimensions. After more than a hundred years of development, traditional computers and theories have been able to efficiently solve many problems, but there are still many problems that cannot be solved, such as weather forecasts, stock prices, cancer drugs... If these problems can be accurately calculated, then our world will become very beautiful, or perhaps very boring. For example, we can accurately calculate the score by which the Chinese national football team will lose in the next game. Unfortunately, quantum computing can't solve these problems either. Well, then why are we working so hard? ! Don't worry, we have found that some problems can be solved with amazing efficiency under the framework of quantum computing, and these problems are also very meaningful.

One of them is the famous Shor algorithm. On the Internet today, when we browse the web and enter our username and password, how can we ensure that others will not peek at us? How can we prevent others from stealing our bank card passwords? Some people say, keep it secret. In fact, on the Internet, if there is no encryption system to protect it, this information is almost transparent. Another feature of the Internet is that information can be transmitted to any corner of the earth in an instant: the person who peeks at your password may be drinking coconut juice in Mauritius at this moment. Traditional point-to-point encryption is not suitable for the Internet. As the number of nodes increases, storing passwords alone will be a disaster. An asymmetric encryption system, RSA encryption, effectively solves this problem. The so-called asymmetry means that the keys used for encryption and decryption are different: a private key is used for decryption; a public key is used for encryption. The public key is public and can be obtained by anyone. If Li Si wants to send an indescribable data to Zhang San, he needs to use the public key published by Zhang San to encrypt it. After Zhang San receives it, he can use the private key to open it and enjoy it. At this time, if there is a Wang Wu who secretly covets these data, sorry, even if he can get the public key, he can't open it without the private key. Since anyone who wants to communicate with Zhang San can share a public key, this encryption system greatly saves the required key resources.

This encryption system has been protecting the Internet for many years and rarely makes mistakes. Its encryption principle is derived from a mathematical discovery: the principle of the indivisibility of large numbers. If you multiply two known large prime numbers to get a larger number, a careful junior high school student can calculate the result. But on the other hand, if I tell you the result of the multiplication and ask you which two prime numbers are multiplied together to get it, even the top mathematicians will be dumbfounded. The most impressive achievement achieved by humans so far is the cracking of RSA-768, please see:

1

1230186684530117755130494958384962720772853569595334792197 3224521517264005072636575187452021997864693899564749427740 6384592519255732630345373154826850791702612214291346167042 9214311602221240479274737794080665351419597459856902143413

=

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489

×

36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

Currently, RSA-1024 and RSA-2048 are commonly used. The number behind them is an exponent. Since the difficulty of cracking this problem increases exponentially with the size of the problem, modern computers can only look up to it and are far behind.

Thanks to the exponential acceleration of the quantum Fourier transform, the Shor algorithm can solve the above problem at a quasi-polynomial difficulty level, reducing the time required to crack the problem from millions of years to seconds - a dimensionality reduction attack. The Shor algorithm is terrifying, but it would not be a problem in the 20th century: implementing the Shor algorithm, based on the technology at the time, was more difficult than landing on Mars.

The situation is different now, as I have already said. Everyone is afraid, because in the cryptography world, one of the most troubling problems is that you are never sure whether your password has been cracked. In addition, passwords that cannot be cracked now can be saved, and even if they are cracked in twenty years, the lethality is still sufficient. Therefore, the emergence of Shor's algorithm, especially the possibility of technical realization, has forced people to actively look for new forms of encryption. China prefers quantum communication and leads the world in this regard, while Americans are lagging behind in quantum cryptography, and Europeans don't want to let go... In short, this is an urgent problem that needs to be solved. If any party finds a way to crack it first, the international balance of power will be broken in an instant, and the consequences will be disastrous.

Another useful quantum algorithm is Grover's algorithm: it searches for a target in an unstructured array, square root N times faster than the classical algorithm, where N is the length of the array. This acceleration is dwarfed by Shor's algorithm, but perhaps this algorithm is more useful because search problems are the basis for solving many problems and an important means of mining information. When N is very large, the benefits of this algorithm are very significant. Isn't the massive amount of data generated on the Internet every moment corresponding to the situation where N is very large?

A long road ahead

After boasting, we have to face the reality: the above two algorithms, as well as their derivative algorithms, have extremely high requirements for manipulation and reading error rates, almost requiring quantum bits to be perfect and error-free. The problem is that any physical system will make mistakes, and any practical operation has precision. We can achieve error correction by creating a certain amount of redundancy, which is also an important topic in the early research of traditional computers. Interestingly, the probability of bit errors in today's semiconductor chips is so low that error correction has become completely unnecessary. Just when these error correction theory legacies were about to be lost, quantum computing came to inherit them.

Quantum error correction is a major challenge in realizing quantum computing. It is difficult to achieve in the short term, even if we find a topological code error correction technology such as surface coding, which can reduce the error correction requirements to a level acceptable to today's technology. This is a very complex scientific and engineering cross-cutting problem. Only when the number of bits reaches 1,000 and the control, isolation, and reading technologies progress simultaneously, then perhaps we can truly face this problem. (See "The Next Super Challenge of Quantum Computing")

During this period, should we wait patiently for the breakthrough of quantum error correction? In fact, no one does this. At present, scientists and engineers in the entire field are focusing more on "noisy intermediate-scale quantum computing (NISQ)". This idea is to allow the existence of noise based on the current level of quantum hardware, and to find quantum algorithms or quantum simulation methods with practical application value in a targeted manner. Therefore, the current research hotspots are variational quantum algorithms (VQE) and quantum approximate optimization algorithms (QAOA) based on classical-quantum hybrid computing, and their application scenarios include quantum chemical computing, financial portfolio optimization, artificial intelligence, etc. Once quantum advantages are achieved in a certain application field, our confidence in quantum computing can continue, attracting more funds and talents to join, and then overcome difficulties such as quantum error correction.

The road ahead is long and arduous! I will keep searching. Quantum computing is a difficult road. We are at the forefront, but we cannot see the direction we are heading. Maybe we will get into a maze, draw our swords and look around in confusion. Maybe we will cut through the fog and see the road ahead! Some people think this is a contest between countries, but I think it is a shining example of the human spirit. We may fail, but we will not bow our heads.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.