Finally there was a task that only quantum computers can solve.

For years, computer scientists have been looking for tasks of a certain type that only a quantum computer would be capable of solving, but not a classical computer, even from future generations. And so they found one of them.

In the early stages of studying quantum computers, computer scientists asked a question, the answer to which, in their opinion, should have revealed some deep truth about the capabilities of these futuristic machines. 25 years later, the answer was found. In a paper published in May 2018, computer scientists Ren Rez and Avishai Tal offered convincing evidence that the computing power of quantum computers exceeds anything that classic computers can achieve in principle.

Raz, a professor at Princeton University and the Wiseman Science Institute, as well as Tal, a postdoc at Stanford University, identified a special type of computational problem. They proved, with one proviso, that quantum computers could effectively solve the problem, and traditional computers would be bogged down forever, trying to do it. Computer scientists have been looking for such a task since 1993, when they first identified a class of BQP tasks , including all the tasks that a quantum computer is capable of solving.

Since then, they hoped to counterpose BQP to a class of tasks, known as PH, including all tasks that can be performed on any classic computer, even an incredibly advanced one, developed by some civilization of the future. The possibility of such an opposition depended on finding a task that would belong to the BQP class, but not to the PH class. And now Rase and Tal did it.

This result does not make quantum computers better than classical ones from a practical point of view. Firstly, specialists in theoretical computer science already know that quantum computers are capable of solving any problems that classical computers are capable of. And engineers can hardly solve the problem of creating a useful quantum machine. But the work of Raza and Tala demonstrates the difference in the categories in which quantum and classical computers are located - and the fact that even in a world in which classical computers have exceeded the limits of any dreams, quantum computers will still be able to outrun them.

Quantum classes

The basic task of theoretical computer science is to divide tasks into complexity classes. The complexity class contains all the tasks that can be solved with a certain resource, such as time or memory.

Scientists, for example, have discovered an efficient algorithm that checks whether a number is simple. However, they could not find an effective algorithm for finding prime factors of large numbers. Consequently, they believe (although they could not prove it) that these two tasks belong to different classes of complexity.

The two famous difficulty classes are P and NP. P - these are all the tasks that a classic computer can quickly solve. (The “is a number simple?” Task belongs to P). All tasks that a classic computer does not necessarily solve quickly belong to NP, but he can quickly verify the correctness of the available solution to any of which. (“What are the prime factors of a number?” Belongs to NP). Scientists believe that the classes P and NP are different, but the task to prove this difference is the most difficult and most important of the open problems in this area.


PH contains NP, which contains P. Is BQP a class separate from PH?

In 1993, computer scientists Ethan Bernstein and Umes Vaziraniidentified a new class of complexity, which they called BQP, or "quantum polynomial time with limited probability of errors." They identified a class as containing all decision-making tasks — tasks with a “yes” or “no” answer — that quantum computers are able to effectively solve. At about the same time, they proved that quantum computers are capable of solving all the problems that classical computers are capable of. That is, BQP contains all the tasks contained in P.

Another example of individual classes of tasks. The traveling salesman task asks if there is a path that passes through certain cities that is shorter than a given distance. Such a task is in NP. A more difficult task asks if this distance is the shortest way through these cities. Such a task is in PH.

However, they could not determine whether BQP contains tasks that are not found in another important class of problems, known as PH or the “polynomial hierarchy”. PH is a generalization of NP. It contains all the tasks that can be obtained by starting with the task from NP, and complicating it by adding clarifying statements like “whether there is” and “for all”. Classic computers cannot yet solve most of the tasks in PH, but this class can be considered a class of problems that classical computers could solve if it turned out that P is equivalent to NP. In other words, in order to compare BQP and PH, it is necessary to determine whether quantum computers have an advantage over classical ones, which will remain even if classic computers suddenly learn to solve many more problems than they can solve today.

“PH is one of the simplest existing classes of complexity,” said Scott Aaronson , an information technology specialist at the University of Texas at Austin. "Therefore, we seem to want to know the place of quantum computing in the world of classical complexity."

The best way to divide two classes of complexity is to find a problem that is provably included in one of them and not in the other. However, due to a combination of fundamental and technical obstacles, such a task was very difficult to find.

To find a task belonging to BQP, but not to PH, you need to define something to which “a classical computer by definition could not even effectively check the answer, let alone find it,” said Aaronson. “This eliminates many of the tasks we work with in computer science.”

Ask the oracle

Task. Suppose we have two random number generators, each of which generates a sequence of numbers. A question to a computer: are these two sequences completely independent of each other, or are they somehow imperceptibly connected (for example, was one obtained a Fourier transform of the other)? Aaronson introduced this “furrelation” task in 2009 and proved that it belongs to BQP. There remains a second, more difficult step - to prove that the furrelation is not included in PH.


Ren Raz

In a sense, this is exactly what Raz and Talu managed to do. Their work separates BQP and PH with the help of the so-called. " oracle " or "black box". This is a result that is widespread in computer science, which researchers resort to when they do not give what they want to prove.

The best way to separate the complexity classes BQP and PH is to measure the computational time required to solve problems from each class. But in computer science there is no "deep understanding of real computational time or the ability to measure it," said Henry Yoon, an IT specialist from the University of Toronto.

Instead, computer science measures something else that is thought to give an understanding of computational time, which cannot be measured directly. Scientists calculate the number of computer accesses to the "oracle" to answer the question. The oracle seems to give hints. We do not know how he gets them, but we know that they are reliable.

If your task is to find out if there is a secret connection between two random number generators, the oracle can be asked questions like “what will be the sixth number of each generator?” Then you need to compare the processing power based on the number of hints each computer needs to solve the problem. A computer that needs more hints is slower.

“In a sense, we understand this model much better. It talks more about information than about calculations, ”Tal said.


Avishai Tal

The new work of Raz and Tala proves that to solve the problem of furrelation, a quantum computer will require far fewer tips than a classical one. Moreover, a quantum computer needs only one hint, despite the fact that PH does not have an algorithm for solving such a problem, even with an unlimited number of hints. “This means that there is an extremely efficient quantum algorithm that solves such a problem,” said Rez. “But if we consider only classical algorithms, then even if we reach the uppermost classes of classical algorithms, they will not cope with it.” This proves that with oracle, furrelation refers to tasks belonging to BQP, but not to PH.

Raz and Tal almost came to this result about four years ago, but could not take one step in future proof. And then, just a month before the publication, Tal heard about the new work on pseudo-random number generators, and realized that the technologies from that article just give what he and Raz needed in order to finish their own. “It was the missing piece,” Tal said.

News about the separation of the classes BQP and PH spread quickly. “The world of quantum complexity is buzzing,” wrote Lance Fortnau, an informatics specialist from Georgia Tech, the day after the publication of the work.

The work gives iron confidence that quantum computers exist in a separate computing world from classical ones (at least, by definition, with an oracle). Even in a world where P is equivalent to NP — where solving a traveling salesman problem is as easy as finding the most suitable line in a spreadsheet — Raz and Tahl's evidence demonstrates the existence of problems that only a quantum computer can solve.

"Even if P were equivalent to NP, even with such a strong assumption," Fortnau said, "quantum computers will still not catch up."