“The ability of quantum computers to solve certain problems that conventional computers cannot effectively solve is called “quantum supremacy”.

“

The ability of quantum computers to solve certain problems that conventional computers cannot effectively solve is called “quantum supremacy”.

▲ The picture above shows a component (dilution refrigerator) in a quantum computer system. This photo was taken in a clean operating room in 2016. If quantum computers can really perform certain calculations at a speed and efficiency that exceeds that of conventional computers, then the goal of “quantum supremacy” is truly achieved. However, this goal alone will not help us realize all the development dreams of quantum computing.

In the past September, there was a breaking news disclosure: as one of the global technology giants dedicated to the research and development of quantum computing, Google announced that it had just achieved the goal of “quantum supremacy”. While classical computers (including laptops, smartphones, and even modern supercomputers) are now very powerful, the complexities inherent in many scientific problems remain unsolvable.

And if we can build a more powerful quantum computer, we can use it to solve a series of problems that classical computers cannot. This state of solving some problems that conventional computers cannot effectively solve by quantum computers is called “quantum supremacy”. So, has Google really done it? We will find out the answer step by step through research.

>>> Difference between classical computer and quantum computer

▲ Today, the basic working principle of solid-state memory devices is to express the encoded result of 0 or 1 by resisting or allowing charged particles to pass through the substrate/gate to generate current flow. In principle, we can also convert a conventional bit into a qubit by replacing the gate with a permanent charge, but the qubit’s transient state is no longer a 0 or a 1, but a superposition of the two states coexisting.

The concept of a classical computer is very simple and can be traced back to the Turing machine model first proposed by Alan Turing. By encoding information into bits (i.e. 0s and 1s), we can perform a series of operations (such as AND, OR, NOT, etc.) on those bits and perform any other computations based on that. However, some of these calculations are easy to implement, and some are extremely difficult. Of course, in theory, as long as we can design an algorithm that corresponds to the computing needs, then no matter how much computing resources it takes, we can program it into a classical computer.

The problem, though, is that the fundamentals of quantum computers differ from those of classical computers. Quantum computers use quantum analogs of qubits, or ordinary bits, to replace ordinary bits that can usually only be 0 or 1. This disruptive design philosophy means that in order to enter the quantum age, certain physical principles that are well known in the classical age must be transformed.

▲ This ion trap design scheme is mainly based on the work of Wolfgang Paul, and it is also one of the early examples of quantum computer application of ion trap technology. This photo, taken in 2005 at a laboratory in Innsbruck, Austria, shows one of the components of an early quantum computer that is now obsolete. Ion trap computers are far less computationally fast than superconducting qubit computers, but their coherence times are longer on scales, making it less difficult to maintain computational stability.

Qubits are not permanently recorded as definite 0s or 1s, but represent a two-state quantum mechanical system in which the ground state represents 0 and the excited state represents 1. (For example, electrons can maintain their spin either up or down; photons can spin left or right in the direction of their polarization, etc.) During the initial preparation of the system and when the final result is read, the value of the qubit is also It will only be displayed as 0 and 1, which is exactly the same as ordinary bits in classical computers.

The biggest difference is that, instead of being in a deterministic state when performing actual computing operations, qubits exhibit a superposition of 0s and 1s: similar to Schrödinger’s cat that is both alive and dead. Only when the computation is over and the final result is read will we be able to get the only true final state value.

▲ In the classic experiment proposed by Schrödinger, we do not know whether the cat was killed by quantum decay. Specifically, the kitten in the box lives or dies depending on whether or not the radioactive particles decay. If this represents a true quantum system, the kitten itself is neither alive nor dead, but in a superposition of the two states until the experimenter directly observes the result.

There are huge differences between classical and quantum computers, including prediction, certainty, and probability. Like all other quantum mechanical systems, we cannot accurately predict the final state by simply giving the quantum system initial conditions and algorithmic operators on which it can operate. Instead, we can only predict the probability distribution of the final state first, and then, through repeated key experiments, come up with a distribution trend that matches and produces this expected outcome.

>>> Church-Turing Theory

Many people might think that to simulate quantum activity, you have to use a quantum computer — but it doesn’t. We can simulate quantum activity on a quantum computer, and we can achieve the same effect on a Turing machine (i.e. a classical computer).

▲ On the premise of sufficient computing power, computer programs can also use flawless running algorithms on classical (non-quantum) computers to perform brute force analysis of candidate Mersenne primes to see if they correspond to ideal numbers. For small numbers, this operation can be easily achieved; but for large-scale computing tasks, it is extremely difficult and requires huge computing power.

This is also one of the most important ideological achievements in computer science: Church-Turing theory. This theory states that if a problem can be solved by a Turing machine, it must also be solved by any other computing device. Such computing devices could be laptops, smartphones, supercomputers or even quantum computers. In other words, a problem that can be solved on one computing device should be solved on all computing devices. This is absolutely true, but it does not mention the computational speed or efficiency of the problem, nor does it reflect any information about the theory of quantum supremacy.

At the same time, there is another, more controversial issue, the extension of Church-Turing theory. The theory states that Turing machines, such as classical computers, can always effectively simulate any computational model, even the inherent quantum computing process. And if we can come up with a counter-example to this – such as demonstrating an example that proves that quantum computers are far more efficient than classical computers, it means that “quantum supremacy” has been directly proved.

▲ IBM’s four-qubit square circuit is a pioneer in computing, and one day a powerful quantum computer may be enough to simulate the entire universe. However, the field of quantum computing is still in its infancy, so demonstrating quantum supremacy under any constraints is a remarkable milestone at the moment.

This is also the common goal that many researchers and technology giants are currently working towards: to design a quantum computer that can significantly outperform classical computers, at least under certain reproducible conditions. So, how to achieve this goal? The key can be simply summarized as – in a classical computer, we can perform a variety of classical operations on any information bit (or bit combination), including the well-known AND, OR, and NOT operations.

But if we have a quantum computer, the qubits provided in it can perform a series of pure quantum operations in addition to classical operations. These quantum operations follow specific rules that can be simulated on classical computers, but without the huge computational cost of the latter. At the same time, all operations can be easily simulated on a quantum computer, and the time required to perform all computational operations will be greatly reduced compared to the coherence duration of qubits.

▲ In a quantum computer, a qubit in an excited state (state “1”) will error back to the ground state (state “0”) on a time scale called coherence time. An error occurs if one of the qubits decays before all computations are performed and we read the result it gives.

>>> Google: Trying to achieve “quantum supremacy” with a specific protocol

With this in mind, the Google team published a paper on NASA’s website (probably an early draft of the final version), but later deleted it, leaving many scientists before they could read it and download it. While the full implications of what is mentioned in the article have not been clarified, we can imagine their solution in the following ways.

Here, we imagine that we have 5 bits or qubits of information, all 0 or 1. These states all start with 0, but we have a new state for them, where two bits/qubits are excited to the “1” state. If these bits or qubits are fully controlled, state preparation can be achieved in an explicit manner. For example, we can fire bits 1 and 3 to 1. In this case, the physical state of the system will appear as |10100>. Next, you can manipulate these bits/qubits through pulsed random operations to get specific probability distribution results.

▲ A 9-qubit quantum circuit, imaged and labeled by a microscope. The gray part is the aluminum base plate, and the dark area is the part where the surface aluminum material is etched. Various colors are used to distinguish different circuit components. For such computers to use superconducting qubits, the devices themselves must remain extremely cold at millikelvin-scale temperatures and operate on timescales well below 50 microseconds, which makes quantum computing possible.

The Google team chose a specific protocol in their experiments to try to achieve “quantum supremacy”, where the requirement is that after performing any number of operations, the bits/qubits that have been excited (that is, bits with a state of “1” ) must remain the same. These operations are completely random, meaning we don’t need to specify which bits/qubits are in the excited state (1) or ground state (0); in short, we only need to get 2 “1” states out of 5 qubits bit and 3 “0” status bits will do. If we do not perform completely random operations, and do not programmatically implement pure quantum operations on the computer, then the 10 potential final states exhibited by 5 qubits are expected to be distributed with uniform probability.

(The 10 possible outcomes are |11000>, |10100>, |10010>, |10001>, |01100>, |01010>, |01001>, |00110>, |00101>, and |00011>.)

However, if our quantum computer strictly follows our definition of a quantum computing device, the resulting probability distribution is not actually uniform. Conversely, some states appear more frequently in the final state result, while others appear less frequently. This is a very typical counter-intuitive result, derived from quantum phenomena and the inherent properties of pure quantum gates. We can also simulate this phenomenon with classical computers, but at a huge computational cost.

▲ When we perform the experiment starting from the |10100> qubit state, and after 10 coupled pulses (i.e. quantum operations), for each of the 10 possible outcomes, we do not get a uniform with equal probability distribution; instead, some outcomes will have an unusually high probability of occurring, and some outcomes will have an extremely low probability of occurring. The results of a quantum computer can be measured to determine whether we are able to maintain the expected quantum activity, or have gone out of control in an experiment.

On a quantum computer, even with classical bit gates alone, we still cannot completely eliminate quantum effects. But we can clearly see that the probability distribution actually obtained is not uniform, with some possible states having a significantly higher probability of occurring than the intuitively predicted 10%, and some less than 10%. The existence of these ultra-low and ultra-high probability states is a purely quantum phenomenon, and the probability of obtaining these low- and high-probability outcomes (rather than a uniform distribution) is itself an important existential marker of quantum activity.

In the field of quantum computing, the probability of obtaining at least one final state that exhibits an extremely low probability of occurrence also follows a specific probability distribution, the Porter-Thomas distribution. If your quantum computer is flawless and working well, you can perform as many damages as you want, and then read the results to see if your computer conforms to the expected Porter-Thomas distribution.

▲ Porter-Thomas distribution, which shows the probability that the 5th, 6th, 7th, 8th, and 9th qubits will obtain certain operation results under a certain number of qubits and possible states. Note the straight line, which represents the expected quantum result. If the total time required to run the quantum circuit is too long, it gives results consistent with classical computers: in the case of the short green line, this clearly does not fit the Porter-Thomas distribution.

But in reality, our current quantum computers are far from flawless. Any quantum system, no matter how well prepared (the Google team used superconducting qubits, but you can use other quantum computers, such as quantum dots or ion traps), will still have a coherence time: between this time period , we can expect a particular qubit to remain excited (i.e. 1) all the time. And once this time is exceeded, it decays back to the ground state 0.

This is very important and means that applying quantum operations to real systems must strictly control the time period, the gate time. Within the coherence time scale, the gate time must be very short, otherwise the measured state may decay and the final state will not provide the results we need. Likewise, the more qubits you have, the more complex the device, and the higher the chance of erroneous crosstalk between qubits. To build an error-free quantum computer, we must apply all quantum gates to all qubits before the system collapses.

Superconducting qubits are currently only stable for periods of 50 microseconds. And even with a gate time of about 20 nanoseconds, only a few dozen calculations can be performed stably in a cycle, and decoherence quickly destroys the experimental environment and brings horrible uniform distribution results – in other words, we Quantum activity that is striving for will disappear in an instant.

▲ The ideal 5-qubit setup, where the initial circuit is prepared using 2 qubits with an initial state of 1 and 3 with an initial state of 0, requires 10 separate pulses (or quantum gates) before producing the final state result. ). If the total time taken to pass through the quantum gate is much shorter than the coherence/decoherence period of the system, then we can obtain quantum computation results as expected. And without it, we wouldn’t be able to perform meaningful computational operations on this quantum computer.

>>> Practical “quantum supremacy” still not achieved

The problem is that the problems Google scientists are solving with its 53-qubit computer aren’t practical problems by any means. In fact, the system setup was specifically designed to perform a task that is easy for a quantum computer but computationally expensive for a classical computer. The approach they took was to build a system of n qubits (which would require at least 2n ordinary bits to simulate on a classical computer), and then choose a computational task that would be as computationally expensive as possible for a classical computer.

The original algorithm proposed by scientists, including several current members of the Google team, required at least a 72-qubit quantum computer to complete the proof of quantum supremacy. However, since 72 qubits are not yet possible, everyone has to return to the 53-qubit computer and introduce another quantum gate (fSim gate, which belongs to the combination of CZ and iSWAP gate) to replace the originally easy-to-simulate quantum gate CZ (fSim gate). gates are relatively more expensive to execute on classical computers).

▲ Different types of quantum gates show different fidelity (ie, the percentage of error-free gates) according to the specific type, and can also reflect the extremely high computing power consumption required by classical computers to process such tasks. The quantum supremacy proof experiment initially attempted to use CZ gates, but the researchers found that at least a 72-qubit device was needed to complete it; they then employed iSWAP gates, allowing the Google team to prove the theory using only 53 qubits.

Many proponents of Church-Turing theory hold the hope that, given the existence of some sufficiently advanced algorithm, we can also significantly reduce the computation time of such problems on classical computers. Although the probability is not high, it does mean that the current “quantum supremacy” achievement still has a slight possibility of collapse.

So far, though, the Google team does appear to have achieved “quantum supremacy” for the first time by solving a particular (and impractical) mathematical problem. When they used a quantum computer to perform this task, it far outperformed even the most powerful classical supercomputer in the United States. But a truly practical goal of quantum supremacy should help us do three things: perform high-performance quantum chemistry and quantum physics calculations; replace all classical computers with advanced quantum computers; and run the Shure algorithm on any number of numbers.

In other words, the era of quantum supremacy may have arrived, but practical quantum supremacy capabilities are still far from being realized. For example, if we wanted to factor a semi-prime number of length 20 bits, Google’s quantum computer simply couldn’t do it. However, existing laptops can already do this in milliseconds.

▲ The Sycamore processor is a rectangular array of 54 qubits, each qubit is connected to the adjacent 4 qubits through a coupler, including one inoperable qubit. Through this structure, Google has built a quantum computer with an actual effective qubit of 53. From the image above, we can see the size and color of the Sycamore chip under optical conditions.

The progress in quantum computing has been astounding, and while critics still scoff at it, orders of magnitude higher qubit systems will undoubtedly continue to emerge. With the emergence of successful quantum error correction mechanisms (which undoubtedly require more qubits to correct errors, while solving a host of other complex problems), we will be able to significantly extend coherence timescales and perform deeper computations.

As the Google team noted when announcing the results: “Our experiments suggest that there may indeed be computational models that do not conform to the Church-Turing paper. We have exploited a physically implemented quantum processor (with a sufficiently low error rate) to perform in polynomial time The tests performed a random quantum circuit sampling task – a task for which no efficient solution exists in a classical computer.”

With the birth of the first programmable quantum computer, quantum supremacy has been demonstrated by finally being able to use qubits in an efficient way to handle specific tasks that would have left classical computers at a loss. The Google team is sure to release more detailed experimental results later this year, and will be applauded and applauded for this remarkable achievement.

But we also have to admit that today, we are still far from the dream of the ultimate quantum computing. If we want to shorten this journey of exploration, we need to push the frontier development with all our strength, so as to finally achieve this most important (if not one of the most important) technical goals of the moment.

The Links: **SKIIP13AC12T4V1** **6RI30G-160**