New research from Stanford and Berkeley overthrows Google's 'quantum supremacy”! Beautiful in theory, but useless in practice

Quantum supremacy, this word has been born for nearly 4 years.

In 2019, Google physicists announced that they had successfully achieved quantum hegemony with a 53-qubit machine, which was a significant symbolic milestone.

According to a paper published in Nature, the quantum system only took 200 seconds to complete a calculation, while the same calculation was performed by Summit, the most powerful supercomputer at the time, which took about 10,000 years.

What is quantum supremacy?

The so-called "quantum hegemony", or "quantum advantage" (hereinafter referred to as "quantum supremacy"), means that the tasks that quantum computers can complete are beyond the scope of any feasible classical algorithm.

Even if these tasks are placed on the most advanced traditional supercomputers, the long calculation time (often thousands of years) will make the algorithm lose its practical significance.

Interestingly, in Google’s results in 2019, it only stated that quantum hegemony had been achieved, but did not explain the specific instances in which quantum computers surpassed classical computers.

This is a difficult question to answer because currently quantum computers are plagued by errors that can accumulate and undermine the performance and stability of quantum computing.

In fact, compared with the field of realizing quantum hegemony, what scientists want to know more is another question: as quantum computers become larger and larger, whether classical algorithms can keep up. .

We hope that eventually the quantum side will completely distance itself and end this completely, said Scott Aaronson, a computer scientist at the University of Texas at Austin. Competition."

Most researchers speculate that the answer is no.

That is, classical algorithms will one day be completely unable to keep up with the pace of quantum computing, but it has been unable to prove this accurately and comprehensively. One way to definitively prove this inference is to find the conditions under which quantum computing can gain a "lasting advantage" over traditional computing.

Now, this question seems to have a preliminary answer:

Save money: Quantum computing will produce errors. If corrected If you fail to keep up, this kind of error will break the "quantum hegemony" in the ideal state, allowing classical algorithms to keep up with quantum algorithms. ​

##Recently, in a preprint paper published on Arxiv, researchers from Harvard University, University of California, Berkeley, and Israel A joint team from Burei University has taken a big step towards confirming this conclusion.

They demonstrated that targeted error correction is a necessary condition for durable quantum supremacy in random circuit sampling, supporting the conclusions of Google's research a few years ago. Under the current level of quantum error correction, quantum hegemony does not actually exist. ​

There is no more "golden zone" for quantum supremacy

Researchers have developed a A classic algorithm that can simulate random circuit sampling experiments when errors exist to prove this conclusion.

Start with an array of qubits and randomly manipulate the qubits using operations called "quantum gates." Some quantum gates cause pairs of qubits to become entangled, meaning they share a quantum state that cannot be described individually.

Repeatedly setting up these quantum gates in multi-layer circuits can allow qubits to enter more complex entangled states.

The left picture shows random circuit sampling under ideal conditions, and the right picture shows random circuit sampling including interference

In order to understand this quantum state, the researchers measured all qubits in the array. This behavior causes the collective quantum state of all qubits to collapse into a random string of ordinary bits, namely 0s and 1s.

The number of possible outcomes grows rapidly with the number of qubits in the array. In Google's 2019 experiment, 53 qubits contained nearly 10 trillion results.

Moreover, this method requires many repeated measurements from random circuits to build a probability distribution map of the results.

The question about quantum supremacy is, is it difficult or even impossible to imitate this probability distribution with a classical algorithm that does not use any entanglement?

In 2019, Google researchers demonstrated that this goal is difficult for error-free quantum circuits that do not produce errors. It is indeed difficult to simulate a random circuit sampling experiment using classical algorithms without errors.

From the perspective of computational complexity, when the number of qubits increases, the computational complexity of traditional classification algorithms increases exponentially, while the computational complexity of quantum algorithms increases polynomially.

When n increases large enough, an algorithm that is exponential in n lags far behind any algorithm that is polynomial in n.

This is the difference we are referring to when we talk about a problem that is hard for a classical computer but easy for a quantum computer. The best classical algorithms take exponential time, while quantum computers can solve problems in polynomial time.

However, the 2019 paper did not consider the impact of errors caused by imperfect quantum gates, and the research conclusion actually left a hole. In other words, random without error correction Can quantum supremacy be achieved through circuit sampling?

In fact, if you consider the errors that occur in quantum entanglement and can accumulate, then the difficulty of simulating random circuit sampling experiments with classical algorithms will be greatly reduced. And if the computational complexity of classical algorithm simulation is reduced to the same polynomial level as quantum algorithms, quantum hegemony will no longer exist.

This new paper shows that assuming the circuit depth is kept constant, say a very shallow 3 layers, as the number of qubits increases, there will not be too much quantum entanglement, The output is still available for classic simulation.

On the other hand, if the circuit depth is increased to keep up with the increasing number of qubits, then the cumulative effect of quantum gate errors will dilute the complexity caused by entanglement, simulated with classical algorithms Exporting will still be easier.

There is a "golden zone" between the two, that is, the window in which quantum hegemony can continue to survive, that is, the range where traditional algorithm simulations cannot keep up with quantum entanglement.

Before the publication of this paper, even as the number of qubits increased, quantum supremacy still existed when the number of qubits reached a certain intermediate range.

At this circuit depth, it is difficult to simulate the classical algorithm at every step, even though the output steadily degrades due to quantum algorithm errors.

This new paper almost eliminates this "golden zone". ​

The paper derives a classical algorithm for simulating random circuit sampling and proves that its running time is a polynomial function of the time required to run the corresponding quantum experiment , rather than an exponential function.

This result establishes a close theoretical connection between the speed of the classical method of random circuit sampling and the quantum method, that is, it declares that quantum hegemony has been achieved in theory, and in practice It almost doesn't exist.

The reason why I say "almost" is because the basic assumptions of the new algorithm are invalid for some shallower circuits, leaving an unknown "small gap".

However, few researchers still hold out hope for achieving quantum supremacy in this gap. Even Bill Fefferman, a computer scientist at the University of Chicago and one of the authors of the 2019 Google paper, said: "I think the chance is quite small."

It can be said that according to the strict standards of computational complexity theory, random circuit sampling will no longer produce quantum supremacy.

Also, faced with this conclusion, all researchers agree on how critical quantum error correction will be to the long-term success of quantum computing. Fefferman said: "In the end of our research, we found that quantum error correction is the solution."

The above is the detailed content of New research from Stanford and Berkeley overthrows Google's 'quantum supremacy”! Beautiful in theory, but useless in practice. For more information, please follow other related articles on the PHP Chinese website!