🍄 🤲🏿 🚰 Significant proof of the theorem on computer science captures physics with mathematics 👨🏼‍🎤 🚣 🤪

Specialists in computer science have identified new frontiers in knowledge verified through computation. And at the same time they solved significant problems from quantum mechanics and pure mathematics.

In 1935, Albert Einstein, together with Boris Podolsky and Nathan Rosen, tried to cope with the opportunity that opened up with the new laws of quantum physics: the "entanglement" of two particles, which in this case can be separated by a huge distance.

The following year, Alan Turing formulated the first generalized theory of computation and proved the existence of problems, in principle not subject to computers.

These two ideas have revolutionized their respective fields. In addition, it seemed that they had nothing to do with each other. However, now a significant proof united them, simultaneously solving a whole lot of problems from computer science, physics and mathematics.

The new evidence suggests that quantum computers that perform calculations using quantum bits, or “qubits,” rather than classical zeros and ones, can theoretically be used to confirm solutions to a huge range of problems. The connection between quantum entanglement and computer technology was a shock to many researchers.

“It was completely unexpected,” said Miguel Navazquezstudying quantum physics at the Institute of Quantum Optics and Quantum Information in Vienna.

The co-authors of the proof decided to determine the boundaries of the possibilities of confirming solutions to computational problems. Their approach uses confusion. Having found these boundaries, the researchers at the same time, as an almost side effect, answered two other questions: the Zirelson problem in physics regarding mathematical modeling of entanglements, and the related problem of pure mathematics, Conn 's hypothesis about nesting.

The results eventually fell like dominoes.

“All of the original ideas were born at about the same time. It’s convenient that they all came together in such an amazing way, ”said Henry Ewanfrom the University of Toronto, one of the authors of the evidence. Other authors: Zhengfeng Ji of the University of Technology Sydney, Anand Natarajan and Thomas Widick of the California Institute of Technology, and John Wright of the University of Texas at Austin. All five are computer scientists.

Insoluble problems

Turing identified the main platform for the study of computing even before the advent of the computers themselves. And literally right away he showed that computers, in principle, could not solve certain problems - and that this could be proved. The thing is whether the program that solves a particular problem ends its work.

Typically, computer programs receive input data and after some time produce output data. But sometimes they get stuck in endless cycles, which makes their gears spin forever. When this happens to you, you have only one option left.

“I have to manually nail the program. Just stop her, ”Ewan said.

Turing proved that there is no general algorithm that can determine whether a program will complete execution or work forever. In order to find out, you have to run the program itself.

Ewan, Vidik, Ji, Natarajan and Wright

“You waited a million years, and the program did not finish working. Do you need to wait another million years? There is no answer to this question, ”said William Slofstra , a mathematician at the University of Waterloo.

Technically speaking, the task of stopping a program is unsolvable - even the most powerful computer you can imagine cannot solve it.

After Turing, computer scientists began to classify other tasks according to their complexity. More complex tasks require more computing resources to solve - more time to work, more memory. So study the computational complexity of tasks.

As a result, you can ask two questions about each task: “How difficult is it to solve it?” and "How difficult is it to verify the correct answer?"

Interrogation for confirmation

In the case of simple tasks, the answer can be checked independently. But as they become more complicated, even checking the answer can become an impossible task. However, in 1985, computer scientists realized that it was possible to verify the correctness of the answer, even if it was impossible to confirm it yourself.

This method follows the logic of a police investigation. If the suspect tells a confusing story, you may not be able to go and check every detail of it. But by asking the right questions, you can catch the suspect in a lie, or you can be assured of the truth of the story.

In terms of informatics, the interrogation contains a powerful computer that offers a solution to the problem - known as the “prover” - and a less powerful computer that asks the prover of the questions to determine the correctness of the answer, known as the “test”.

A simple example: imagine that you do not distinguish between colors, and the other person - the prover - claims that two of some balls have a different color. You cannot verify this statement on your own, but through ingenious interrogation, you can still verify that it is true.

Put the balls behind and mix. Ask the prover to tell you which one has which color. If they are really of different colors, the prover must constantly correctly answer the question. If they are of the same color - that is, they look the same - the prover in half the cases will express the wrong guess.

“If I see that you have achieved much more success than in half the cases, then I will be almost sure that they are not the same color,” said Vidik.

By asking the prover questions, you can confirm the correctness of solutions to a wider range of tasks than you could solve yourself.

In 1988, computer scientists thought about what would happen if two provers suggested solutions to the same problem. After all, if you have the opportunity to interrogate two suspects, it will be even easier for you to solve the crime or confirm the correctness of the decision - they can be compared with each other.

“For those who check it, it gives more room for pressure. You interrogate, ask questions related to the case, cross-check the answers, ”Vidik said. If the suspects are telling the truth, their answers should coincide most of the time. If they lie, there will be more contradictions.

Similarly, the researchers showed that by interrogating separately the two provers regarding their answers, you can quickly confirm the correctness of the solution for an even wider class of problems, compared with the one you can approach with only one prover.

Computational complexity may seem to you a purely theoretical idea, but it is nevertheless closely related to the real world. The resources computers need to solve problems and confirm decisions — time and memory — are fundamentally physical. Therefore, new discoveries in physics can change computational complexity.

“If you choose a different set of physical laws, for example, the quantum world instead of the classical one, then another theory of complexity can be deduced from it,” Natarajan said.

The new evidence is the final result of the confrontation between a 21st century computer scientist and one of the strangest ideas of 20th century physics: entanglement.

Conn's nesting hypothesis

When two particles become entangled, they do not affect each other - they have no causal relationship. Einstein et al. Revealed this idea in a 1935 paper. After that, physicists and mathematicians tried to come up with a mathematical way of describing what confusion actually means.

However, there was some confusion. Scientists came up with two different mathematical models of entanglement - and the fact that they are equivalent to each other was not at all obvious.

Indirectly, this potential dissonance influenced the emergence of an important problem from the field of pure mathematics, Conn's hypothesis of nesting. And in the end, it also served as a schism, which five computer scientists took advantage of in their new evidence.

The first way to model entanglement is to imagine spatially isolated particles. One of them, for example, is on Earth, and the other is on Mars; the distance between them excludes a causal relationship. This is called a tensor product model.

But in some situations, it is not entirely clear whether two objects are really causally isolated from each other. Therefore, mathematicians have come up with a more general way to describe causal independence.

When the sequence of operations on objects does not matter, the operation is considered switched: 3 x 2 will give the same as 2 x 3. In the second model, particles are entangled when their properties correlate, but the sequence of measurements does not matter. Measure particle A to predict the momentum of particle B, or vice versa. In any case, the answer will be the same. This is called a switched operator entanglement model.

Both descriptions of entanglement use arrays of numbers organized in columns and rows — matrices. The tensor product model uses matrices with a finite number of columns and rows. The commutation operator entanglement model uses a more general object that works like a matrix but has an infinite number of rows and columns.

Over time, mathematicians began to explore these matrices on their own, separately from their connection with physics. In the framework of this work, the mathematician Alain Conn in 1976 hypothesized that many matrices of infinite dimension can be approximated by matrices with finite dimension. This was one of the conclusions of Conn's hypothesis of nesting.

In the next decade, the Soviet physicist [in the original physicist, but on Wikipedia is listed as a mathematician / approx. transl.] Boris Tsirelson proposed his own version of this problem, which again became associated with physics. Zirelson suggested that the tensor product and commutative operator models describing entanglement are roughly equivalent. This makes sense, since theoretically these are two different ways to describe the same physical phenomenon. Subsequent works showed that, due to the connection of the matrices and the physical models using them, Conn's hypothesis about nesting and the Zirelson problem follow from each other: solve one and you solve the other.

However, the solution to both problems as a result appeared in a completely different direction.

Physics and games

In the 1960s, physicist John Bell came up with a test to determine if entanglement is a real physical phenomenon or just a theoretical idea. Something like a game participated in the test, the outcome of which reported whether something other than ordinary, non-quantum physics played a role in the experiment.

Later, computer scientists will realize that this entanglement test can also be used as a tool to validate solutions to very complex problems.

But first, to understand how these games work, imagine two players, Alice and Bob, and a 3x3 box. The judge gives Alice a line and suggests that she put 0 or 1 lines in each of the cells so that the sum of the numbers is odd. Bob is assigned a column, and he needs to fill in all of his cells so that the sum of the numbers is even. They win if they put the same number in the same cell - where the selected row and column intersect. But at the same time they cannot communicate.

Under normal conditions, the best that players are capable of is to win in 89% of cases. But in the quantum world, they can improve this result.

Suppose Alice and Bob shared a pair of entangled particles. Each of them takes measurements of its particle and uses the results to determine whether to write 0 or 1 in each cell. Since the particles are entangled, the results of their measurements will correlate with each other, which means that their answers will also correlate - which means , they will be able to win in 100% of cases.

So if you see that two players win the game unexpectedly often, you can conclude that they use something outside of classical physics. Now Bell’s experiments are called “non-local” games, referring to the separation of players. And physicists actually do such experiments in laboratories.

“People have done such experiments for years, and it follows from them that this frightening effect really exists,” Ewan said.

When analyzing any game, you may need information about how often players win a non-local game if they try to play in the best possible way. For example, if you take Solitaire Solitaire, then you can calculate the probability with which the player who plays perfectly will be able to win.

But in 2016, William Slofstra proved that there is no general algorithm for calculating the exact maximum probability of winning in non-local games. The researchers asked the question: is it possible to at least roughly predict the maximum percentage of winnings?

Computer scientists sought an answer using two models describing intricacies. The algorithm using the tensor product model determined the lower bound, or the minimum value of the approximate maximum probability of winning for all non-local games. Another algorithm that used the entanglement model with a dial-up operator determined its upper bound.

The longer these algorithms work, the more accurate the result they produce. If Zirelson’s prediction is true, and these two models are really equivalent, then the lower and upper bounds should gradually come closer, converging to a single value of the approximate maximum probability of winning.

But if Cirelson’s prediction is wrong, and the two models are not equivalent, “the lower and upper bounds will forever remain separate,” Ewan said. It will be impossible to calculate even the approximate value of the maximum probability of winning for non-local games.

In the new work, five researchers used this topic - whether the lower and upper boundaries converge, and whether the Tsirelson hypothesis is true - to solve a separate question about the possibility of confirming the correctness of the solution of a computational problem.

Intricate help

In the early 2000s, computer scientists thought: how will the range of tasks change, the solutions of which can be confirmed by interviewing two provers with intricate particles?

Most decided that entanglement would play against confirmation. Indeed, it will be easier for two suspects to construct a consistent lie if they have a way to coordinate the answers.

But in recent years, computer scientists have realized that it’s actually the opposite: by interrogating provers, dividing pairs of entangled particles, one can confirm solutions to a much wider range of problems than without entanglement.

“Confusion is one way to get a correlation that seems to help them lie and cheat,” Vidik said. “But you can actually wrap it in your favor.”

To understand how this is possible, you first need to evaluate the almost supernatural range of tasks whose solutions you can check with this interactive procedure.

Imagine a graph - a set of points (vertices) connected by lines (edges). You might want to find out if it is possible to color the vertices with three colors so that there are no pairs of vertices of the same color, united by a common edge.

If you give a couple of people proving a very large graph, and they say that it can be colored in three colors as described, you will think: is there a way to check this answer?

Very large graphs cannot be verified directly. Instead, you can ask each prover to report the color of two vertices connected by an edge. If they report different colors, and each time give out different colors during the survey about other vertices, your confidence that painting in three colors works will grow.

But such a polling strategy also ceases to work when the graphs become really large - when the number of edges and vertices begins to exceed the number of atoms in the Universe. For the verifier, even such a task as posing a specific question (“tell me the color of the XYZ vertex”) becomes unbearable - the amount of data needed to name a particular vertex exceeds the working memory available to it.

However, confusion allows the provers to ask questions themselves.

“The reviewer does not need to figure out the questions. The inspector makes the provers themselves calculate the questions for him, ”Wright said.

The inspector needs the provers to tell him the colors of the connected vertices. If the vertices are not connected, then the answers to the question will not say anything about the possibility of coloring the graph in three colors. In other words, the examiner wants the prover to ask related questions: one prover asks the question about the vertex ABC, and the other about the vertex XYZ. And I would like these two peaks to be connected, although not one of the provers knows which peak the other is talking about. In the same way that Alice and Bob hope to put the same number in the same square, although none of them knows which row and column the other works with.

If each of the two provers would issue a question completely on their own, they could not be forced to select connected, or correlating, peaks, so that the examiner could confirm their answers. However, entanglement just allows you to build a correlation.

“We are going to use confusion to dump all the work on the provers. We will make them choose their own questions, ”said Vidik.

At the end of the procedure, each of the provers reports a color. The reviewer checks them for a match. If a graph can actually be colored in three colors, provers should never produce the same color.

“If the count can be painted in three colors, the provers can convince you of this,” Ewan said.

It turns out that this confirmation procedure is another example of a non-local game. The provers “win” by convincing you of the correctness of their decision.

In 2012, Vidik and Tsiyoshi Ito proved that it is possible, by playing various non-local games with confusing evidence, to confirm the answers to at least the same number of tasks as when interrogating two classic computers. That is, the use of confusing provers does not harm the confirmation of their ottetes. And last year, Natarajan and Wright proved that interacting with convoluted provers actually extends the class of validated tasks.

However, to this point, computer scientists have not guessed the size of the full range of tasks, the solutions of which can be confirmed in a similar way.

Cascade of consequences

In the new work, five computer scientists prove that the interrogation of convoluted provers can confirm solutions to unsolved problems, including the stop problem.

“The validation capabilities of this model are amazing,” Ewan said.

However, the stopping problem cannot be solved. And this fact became key to complete the proof.

Suppose you give a program to a couple of confusing provers. You ask them to say whether its execution will stop. You are ready to test their answer through a variety of non-local games: the provers give questions and win depending on the consistency of their answers.

If the program really stops, the provers should be able to win this game in 100% of cases - as in the case of a graph that can be colored with three colors, when the convoluted provers do not have to give the same color for two connected vertices. If the program does not stop, then the provers should win only by chance - that is, in 50% of cases.

This means that if someone asks you to determine the approximate maximum probability of winning for a particular non-local game, you will first need to solve the stop problem. But it is impossible to solve. Which means that the task of calculating the approximate maximum probability of winning is unsolvable, as is the problem of stopping.

And this, in turn, means that the answer to the Zirelson problem is negative - the two models of entanglement are not equivalent. If they were, it would be possible to reduce the lower and upper bounds of the score together and calculate the approximate maximum probability of winning.

“There cannot be such an algorithm, so the two models must be different,” said David Perez-Garcia from Complutense University of Madrid.

The new work proves that the class of problems whose solutions can be confirmed by interacting with entangled quantum provers, MIP *, is completely equivalent to the class of problems that are not more complicated than the stop problem, RE. The title of the work briefly describes its essence: “MIP * = RE”.

In the process of searching for evidence of the equality of two complexity classes, computer scientists proved the falsity of the Tsirelson hypothesis, which, thanks to previous works, means the falsity of the Conn hypothesis about nesting.

It was a shock to researchers from the relevant fields that the answers to such complex problems were identified in the process of seemingly unrelated evidence from the field of computer science.

“Having seen a work called MIP * = RE, I would definitely not think that it has anything to do with my work,” said Navazquez, co-author of a previous work linking the Cirelson hypothesis with Conn's hypothesis about nesting. “It came as a complete surprise to me.”

Specialists in quantum physics and mathematics are just beginning to digest this information. Previously, mathematicians were interested in whether they can approximate infinite-dimensional matrices by large finite ones. Now, knowing the falsity of Conn's hypothesis of nesting, they know that they cannot.

“From their result, it’s impossible,” said Slofstra.

The computer scientists themselves did not try to find confirmation of Conn's hypothesis about nesting, so other people should explain all the consequences of the answers they found instead.

“I myself am not a mathematician. I do not understand very well the initial definition of Conn's hypothesis about nesting, ”said Natarajan.

They and co-authors suggest that mathematicians themselves will translate the new result into the language of their field. In an article declaring evidence, Vidik wrote: “I have no doubt that the theory of complexity will no longer be needed in order to obtain purely mathematical results.”

The resulting evidence interrupts the long chain of research that led to it. For more than three decades, computer scientists have been trying to find out how far their interactive confirmation will lead. Now they have an answer in the form of a long work with a simple heading and references to Turing.

“There is a rather large list of works that asked about what opportunities might be” in the confirmation procedure with the help of two confusing provers, Natarajan said. “Now we know which ones. The story is over. ”

Significant proof of the theorem on computer science captures physics with mathematics