Scientists in the United States have figured out how to test problems that are not yet available to humans. Scientists use the same method as police investigators in their dialogue with computers solving these problems. They "confuse" the interrogated, interrogate two cars separately, etc. Even quantum mechanics is being used.
Imagine: a man comes to you and says that he has a soothsayer, and that this soothsayer can reveal the incomprehensible secrets of the universe. You are intrigued, but you hardly believe him. You will definitely want to make sure that the diviner is telling the truth, and for this you will need some way or method.
This is the essence of one of the main problems of computer science. Some tasks are too difficult to accomplish within a reasonable time frame. But their solution is easy to verify. For this reason, computer scientists want to know: How complex can a problem be that has a verifiable solution?
It turns out the answer is: it can be incredibly complex.
In April, two computer scientists published a research paper that multiplied the number of problems that are difficult to solve, but easy to verify. They described a method for testing solutions to problems of almost incredible complexity. “It sounds like crazy,” said Thomas Vidick, a computer scientist at the California Institute of Technology, who was not involved in this new work.
The research concerns quantum computers that perform computations according to the contradictory rules of quantum mechanics. Quantum computers are just starting to emerge, but in the future they may revolutionize computation and computation.
In fact, the new scientific research conducted gives us the opportunity to influence the diviner described at the beginning of the article. Even if he promises to give us answers to those problems that we ourselves are not able to solve, so even in this seemingly hopeless situation, we will still have a way to test the diviner and make sure that he is telling the truth (or deceiving).
Promotional video:
TO THE DEATH OF THE UNIVERSE
When a problem is difficult to solve, but easy to verify, finding a solution takes a lot of time, but checking the correctness of the given solution is not.
Here's an example. Imagine being given a drawing. It is a collection of points (vertices) that are connected by lines (edges). You are asked if it is possible to paint these points of a shape with just three colors so that the points connected by lines are of different colors.
This “three-color” problem is difficult to solve. In general, the amount of time it takes to compose a three-color figure (or to determine that it cannot exist) grows exponentially as the figure increases in size. For example, if a figure has 20 points of connection of lines, then the solution of the problem takes 3 to the twentieth power of nanoseconds, that is, several seconds in terms of the units of time we are used to. But if the figure is with 60 points, then the search for a solution will take 100 times longer than our estimated age of the universe.
But let's imagine: someone claims to have made such a three-colored figure. It will take us a little time to check the veracity of his statement. We'll just start checking the connection points of the lines one by one. As the figure grows, the check time will also slowly increase. This is the so-called polynomial time. As a result, it turns out that the computer does not take much more time to check a three-color figure with 60 vertices than it does to check a figure with 20 connection points.
"It's pretty easy to test that this circuit works, provided it's a real three-color figure," says MIT physicist John Wright, who co-wrote a new paper with Caltech's Anand Natarajan. …
In the 1970s, programmers identified a class of problems that are easy to test, although sometimes difficult to solve. They gave this class the name NPT - non-deterministic polynomial time. Since then, many computer scientists have been studying these problems very intensively. In particular, scientists want to know how this class of problems changes when the inspector has new ways to check the correctness of the solution.
CORRECT QUESTIONS
Prior to the work of Natarajan and Wright, two important discoveries were made in verifying the correctness of the solution. They have greatly increased our ability to test super hard problems.
To understand the essence of the first breakout discovery, imagine that you are color blind. Two cubes are placed on the table in front of you, and you are asked whether they are the same color or different. This task is impossible for you. Moreover, you are not in a position to test another person's decision.
But you are allowed to question this person, whom we will call the prover. Let's say the prover tells you that a pair of cubes are different colors. We will designate the first cube with the letter "A", and the second with the letter "B". You take the cubes, hide them behind your back and transfer them from hand to hand several times. Then you show the cubes and ask the prover to show cube A.
If the cubes are of different colors, everything is extremely simple. The prover knows that the cube A is, say, red, and he will point it correctly every time.
But if the cubes are of the same color, that is, the prover told a lie, saying that their color is different, he can only guess where which cube is. Because of this, he will only correctly indicate die A 50 percent of the time. This means that by repeatedly asking the prover about the solution, you can verify its correctness.
“The examiner can ask the prover questions,” Wright said. "And maybe at the end of the conversation, the verifier's confidence will increase."
In 1985, a trio of programmers proved that such interactive proofs can be used to test solutions to problems that are more complex than the NIP class. As a result of their work, a new class of problems called IPT appeared - interactive polynomial time. The method used to test the color of two cubes can be used to test solutions to more complex problems and questions.
The second major step was taken in the same decade. Everything here follows the logic of a police investigation. If you have two suspects who you think have committed a crime, you will not interrogate them together. You will interrogate them in different rooms, and then compare the answers given by them. By interrogating these people separately, you can learn more truth than if you have only one suspect.
“The two suspects won't be able to come up with some plausible and consistent version because they simply won't know each other's answers,” Wright said.
In 1988, a group of four computer scientists proved that if two computers were asked to solve the same problem separately, and then separately questioned about the answers, then an even broader class of problems could be tested than IPV. This class is called IDMD - interactive proof with many provers.
Using this approach, one can, for example, test "tricolor" problems against a sequence of shapes that grow in size much faster than shapes in nondeterministic polynomial time. In non-deterministic polynomial time, the size of the shapes increases linearly - the number of connection points of lines can increase from 1 to 2, then to 3, then to 4, and so on. Thus, there will never be a huge disparity in the size of a figure with the amount of time it takes to test its tricolor. But if we are talking about an interactive proof with many provers, then here the number of points in the figure increases exponentially.
As a result, these figures become too large and do not fit into the memory of the checking computer, which is why it cannot check their tricolor by running through the list of connecting points. But it is still possible to check the tricolor by asking the two provers separate, but related questions.
In the IDMD problem class, the examiner has enough memory to run a program to determine if two points in a shape are connected by a line. The prover can then ask each prover to name one of the two dots connected by a line, after which he can easily compare the provers' answers to make sure that the three-colored figure is correct.
Increasing the level of tasks that are difficult to solve, but easy to verify, from NPV to IPV, and then to IDMD, could be achieved through classical computers. Quantum computers work differently. For decades, it was not clear how they change the picture, that is, whether it is more difficult or easier to check the solution with their help.
New work by Natarajan and Wright provides an answer to this question.
QUANTUM DECEPTION
Quantum computers perform computation by manipulating quantum bits (qubits). They have a strange property, the essence of which is that they can get confused with each other. When two qubits, or even large systems of qubits, become entangled with each other, it means that their physical properties play them out in a certain way.
In their new work, Natarajan and Wright consider a scenario with two separate quantum computers that share common entangled qubits.
It would seem that this kind of scheme works against validation. The persuasiveness of an interactive proof with many provers is precisely due to the fact that you can interrogate two provers separately, and then compare their answers. If these answers match, then most likely they are correct. But if two provers are in a confused state, then they have more opportunities to consistently and consistently give wrong answers.
Indeed, when a scenario with two entangled quantum computers was first proposed in 2003, scientists suggested that entanglement would weaken verification capabilities. “Everyone, including me, had a very obvious reaction: now the provers will have more strength and persuasiveness,” said Vidik. "They can use entanglement to coordinate their answers."
Despite this initial pessimism, Vidic spent several years trying to prove otherwise. In 2012, he, along with Tsuyoshi Ito, proved that it is still possible to test all problems in the IDMD class with the help of entangled quantum computers.
Now Natarajan and Wright have proven that the situation is even better. A wider class of problems can be tested with entanglement than without it. The connections between entangled quantum computers can be turned to the benefit of the examiner.
To understand how, let us recall the procedure for testing three-colored figures, the size of which increases exponentially if an interactive proof with many provers is used. The verifier does not have enough memory to store the entire figure, but enough to identify two related points and ask the provers what color they are.
If we talk about the problems that Natarajan and Wright consider - and they belong to the class called nondeterministic double exponential time (NDEW) - then the size of the figure in them increases even faster than in the problem of the IDMD class. The figure in NDEV is growing at a "double exponential" rate. That is, it is a double geometric progression. The figure increases not with the speed of the 21st, 22nd, 23rd degree, but "in the degree of degrees." Because of this, the shapes grow so quickly that the examiner cannot find a single pair of connected points.
“It takes 2n bits to mark a point, which is exponentially larger than the verifier's working memory,” Natarajan says.
But Natarajan and Wright argue that it is possible to test the three-color coloring of a doubly exponential figure without being able to determine which points to ask the provers about. The point is that the provers themselves ask questions.
According to scientists, the idea of asking computers to check their own decisions by the method of polling is as reasonable as the idea of asking suspects of a crime to interrogate themselves. That is, this is complete nonsense. True, Natarajan and Wright argue that this is not the case. The reason is confusion.
"Entangled state is a shared resource," says Wright. "Our entire protocol aims to understand how to use this shared resource to prepare related questions."
If quantum computers are confused, then their choice of points will be interconnected, and they will give the right set of questions to test tricolor.
At the same time, the examiner does not need the two quantum computers to be too closely interconnected, since their answers to these questions will be consistent (this is equivalent to the fact that two suspects agree among themselves on a false alibi). Another strange quantum feature fixes this problem. In quantum mechanics, the uncertainty principle prevents us from simultaneously knowing the position of a particle and the momentum of its force. If you measure one, then destroy information about the other. The uncertainty principle severely limits your knowledge of two "complementary" properties of a quantum system.
Natarajan and Wright took advantage of this in their work. To calculate the color of a vertex, they use two quantum computers that complement each other with measurements. Each computer calculates the color of its points, and in doing so, it destroys all information about the points of the other computer. In other words, entanglement allows computers to formulate interrelated questions, but the uncertainty principle prevents them from conspiring in answering them.
“We need to make the prover forget [about the false version of events], and this is the main thing that they [Natarajan and Wright] did in their work,” Vidik said. "They force the prover to remove the information when he takes measurements."
Their work has enormous and very important consequences. Before this work appeared, the limit on the amount of knowledge that we could have with complete confidence was significantly lower. If we were given an answer to the IDMD problem, we would have to accept it on faith, since we have no other choice. But Natarajan and Wright removed this limitation and made it possible to validate answers to many more computational problems.
But now that they have done that, it is not clear where the validation limit is.
"This could go a lot further," said Lance Fortnow, a computer science researcher at the Georgia Institute of Technology. "They leave room for one more step."
Kevin Hartnett