Shulou(Shulou.com)11/24 Report--

Since its birth, quantum hegemony has become a proposition that countless researchers are trying to break. Now, the joint team of Harvard University, the University of California, Berkeley and the Hebrew University of Israel has finally taken a solid step in this direction. Experiments show that quantum hegemony does not exist!

Quantum hegemony, the word has been born for nearly four years.

In 2019, Google physicists announced that they had successfully achieved quantum hegemony with a 53-qubit machine, a milestone with a major symbol.

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

What is quantum hegemony? The so-called "quantum hegemony", or "quantum superiority" (hereinafter referred to as "quantum hegemony") means that the task that a quantum computer can accomplish is beyond the scope of any feasible classical algorithm.

Even if these tasks are placed on the most advanced traditional supercomputers, the long computing time (often thousands of years) will make the algorithm useless.

Interestingly, in Google's results in 2019, it only mentioned the realization of quantum hegemony, but did not say in which specific examples, quantum computers surpassed classical computers.

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

In fact, what scientists want to know more than the realization of quantum hegemony is another question: as quantum computers get bigger and bigger, whether classical algorithms can keep up.

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

Most researchers speculate that the answer is no.

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

Now, there seems to be a preliminary answer to this question:

Current-saving: quantum computing will produce errors, if the error correction can not keep up, this error will break the ideal "quantum hegemony", so that the classical algorithm can keep up with the pace of quantum algorithms.

Recently, in a preprinted paper published on Arxiv, a joint team of Harvard University, the University of California, Berkeley and the Hebrew University of Israel took a big step towards confirming this conclusion.

They proved that target error correction is a necessary condition for lasting quantum hegemony in random circuit sampling, supporting Google's research findings a few years ago. At the current level of quantum error correction, quantum hegemony actually does not exist.

There is no more quantum hegemony "golden zone" researchers have developed a classical algorithm that can simulate random circuit sampling experiments in the presence of errors to prove this conclusion.

Starting with an array of qubits, these qubits are randomly manipulated with an operation called a "quantum gate". Some quantum gates make pairs of qubits entangled, which means they share a quantum state with each other and cannot be described separately.

By repeatedly setting these quantum gates in a multi-layer circuit, qubits can enter a more complex entangled state.

The left picture shows the sampling of random circuits in the ideal state, and the picture on the right shows the sampling of random circuits with interference.

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

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

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

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

In 2019, Google researchers proved that this goal is difficult for error-free, error-free quantum circuits. In the case of no errors, it is really difficult to simulate a random circuit sampling experiment with classical algorithms.

From the point of view of computational complexity, when the number of qubits increases, the computational complexity of the traditional classification algorithm increases exponentially, while the quantum algorithm increases exponentially.

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

This is the difference when we talk about a problem that is difficult for classical computers but easy for quantum computers. The best classical algorithms require exponential time, while quantum computers can solve problems in polynomial time.

However, the 2019 paper did not take into account the wrong effects of imperfect quantum gates, and the conclusion actually left a gap, that is to say, can random circuit sampling without error correction still achieve quantum hegemony?

In fact, if we consider the cumulative errors in quantum entanglement, the difficulty of using classical algorithms to simulate random circuit sampling experiments will be greatly reduced. If the computational complexity of the classical algorithm is reduced to the same polynomial level as the quantum algorithm, the quantum hegemony will no longer exist.

This new paper shows that assuming that the depth of the circuit remains constant, such as a very shallow three-layer, with the increase of the number of qubits, there will not be too much quantum entanglement, and the output can still be simulated classically.

On the other hand, if we increase the depth of the circuit and keep up with the increasing number of qubits, then the effect accumulated by quantum gate errors will dilute the complexity of entanglement, and it will still be easier to simulate the output with classical algorithms.

There is a "golden zone" between the two, that is, the window through which quantum hegemony can survive, that is, the simulation of traditional algorithms can not keep up with the range of quantum entanglement.

Before the publication of this paper, even with the increase in the number of qubits, quantum hegemony still existed when the number of qubits reached a certain intermediate range.

At this circuit depth, even if the output is steadily degraded due to the error of the quantum algorithm, it is difficult to simulate the classical algorithm at each step.

This new paper has almost wiped out this "golden zone".

In this paper, a classical algorithm for simulating random circuit sampling is derived, and it is proved that the running time is a polynomial function of the time required to run the corresponding quantum experiment, not an exponential function.

This result establishes a close theoretical relationship between the classical method of random circuit sampling and the speed of the quantum method, that is, it declares that the quantum hegemony which has been realized in theory almost does not exist in practice.

The reason for saying "almost" is that the basic assumption of the new algorithm is invalid for some shallow circuits, leaving an unknown "small gap".

However, few researchers are hopeful of achieving quantum hegemony in this gap. "I think the odds are pretty slim," says Bill Fefferman, a computer scientist at the University of Chicago and one of the authors of the 2019 Google paper.

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

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

Reference:

Https://www.nature.com/articles/d41586-023-00017-0

Https://www.quantamagazine.org/new-algorithm-closes-quantum-supremacy-window-20230109/

Https://scottaaronson.blog/?p=6957

This article comes from the official account of Wechat: Xin Zhiyuan (ID:AI_era)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.