MIP * = RE-This isn't a typo; this can be a breakthrough that shakes the globe of physics and arithmetic. A new 165-page paper maybe a major quantum computing discovery that is dashing physicists and mathematicians.
MIP * = RE isn’t an erratum. This is a breakthrough discovery in the field of quantum complexity theory and the eye-catching title of a recent paper. Complexity theory is a zoo of "complexity classes" (a collection of computational problems), in which MIP* and RE are only two.The 165-page paper shows that the two categories are the same. In the absence of any practical application, this seems to be a trivial detail in abstract theory. But physicists and mathematicians are flocking, even though they may not understand all this. Because it turns out that the discovery has amazing ramifications for their own disciplines.
In 1936, Alan Turing demonstrated that the "stopping problem" (the algorithm used to determine whether a computer program would stop or loop forever) could not be solved. Modern computer science was born. Its success gave the impression that all practical problems would soon succumb to the immense power of the computer.But although some problems can be solved through algorithms, the actual calculations will last a long time after our Sun has swallowed the computers that perform the calculations. It is not enough to find a solution to the problem through algorithms. It is important to classify solutions by efficiency. Complexity theory classifies problems according to the difficulty of solving them. The hardness of the problem is measured by the calculated duration.
RE stands for problems that can be solved by computers. It is a zoo.
Class P contains problems that known algorithms can solve quickly (technically in polynomial time). For example, multiplying two numbers belongs to P, because long multiplication is an effective algorithm to solve this problem. The problem of finding prime numbers cannot be found in P; this problem can of course be solved with a computer, but there is no known algorithm that can be solved effectively. Until 2004, when an effective algorithm showed that the problem was in P, a related problem (that is, whether a given number is a prime number) was in a similar predicament.
Another complexity category is NP. Imagine a maze. "Is there a way to get out of this maze?" is a yes/no question. If the answer is yes, then there is an easy way to convince us: just provide us with instructions, we will follow the instructions, and then find the exit. However, if the answer is no, then we will have to traverse the entire maze and never find a convincing way out. Such a yes/no question, if the answer is yes, we can effectively prove that it belongs to NP. The solution to any problem can make us believe the answer, so P is included in NP. Surprisingly, the one-million-dollar problem is P = NP. no one knows.
The classes described so far represent the problems faced by ordinary computers. But computers are undergoing fundamental changes-quantum computers are under development. But if a new type of computer emerges and claims to be able to solve one of our problems, how can we believe it is correct? Imagine the interaction between two entities (the inquirer and the prover). In the police interrogation, the witness may be a suspect trying to prove his innocence. The inquirer must decide whether the prover is persuasive enough. There is an imbalance; in terms of knowledge, the interrogator is in a worse position.
In complexity theory, the interrogator is a person who is trying to solve a problem and has limited computing power. The prover is a new computer, believed to have huge computing power. An interactive proof system is a protocol that the inquirer can use to determine at least with a high probability whether the prover should be trusted. By analogy, these crimes may not be solved by the police, but at least innocent people can convince the police that they are not guilty. This is the IP class. If multiple certifiers can be asked, and the certifier is not allowed to coordinate their answers (usually when the police asks multiple suspects), then we enter the MIP category. This kind of inquiry provides the inquirer with greater ability by cross-checking the prover's answer, so MIP includes IP.
Quantum communication is a new form of communication using qubits. Entanglement is a quantum feature. Even if separated, qubits will be entangled together, which makes quantum communication fundamentally different from ordinary communication. Allowing MIP provers to share an entangled qubit leads to MIP* classes. Obviously, the communication between the provers can only help the prover to coordinate the lies, but not the interrogator to discover the truth. Therefore, no one expects that allowing more communications will make computing problems more reliable and solvable. Surprisingly, we now know that MIP * = RE. This means that the behaviour of quantum communication is completely different from normal communication.
Far-reaching
In the 1970s, Alain Connes raised the so-called "Connes embedding problem." Roughly speaking, this asks whether an infinite matrix can be approximated by a finite matrix. Now, this new paper proves that this is impossible-an important discovery for pure mathematicians. At the same time, in 1993, Boris Tsirelson pointed out a problem in physics, the current Tsirelson problem. These are two different forms of mathematical formalism about a situation in quantum mechanics-so far, a very successful theory explains the subatomic world. As two different descriptions of the same phenomenon, it can be expected that these two formalisms are mathematically equivalent.
However, the new paper now shows that this is not the case. Exactly how they can still produce the same results, and both describe the same physical reality is unknown, but this is why physicists suddenly became interested. Time will tell what other unresolved scientific problems exist in complexity research. There is no doubt that MIP * = RE is a huge leap forward.
Coming Soon...!
Comments (0)