Landmark computer science proof cascades through physics and math
I&#x27;m not a physicist or mathematician, but I tried to reduce this article to a basic level to see if I understood it. Maybe this will be helpful to someone else:<p>Assumptions in CS complexity theory:<p>1. Turing showed that you can&#x27;t tell ahead of time if a program will run forever or eventually stop. This is the halting problem. It proves that some problems are impossible to solve with computers even with infinite memory and CPU.<p>2. But you can often verify if an answer to a problem is correct more easily than solving the problem itself.<p>3. But some problems are so difficult that even verifying if an answer is correct is seemingly impossible - like verifying some properties of an infinite graph of nodes. This is because the graph could be infinitely large, so you could never have enough memory in your computer to even number the nodes, let alone inspect them.<p>4. Sometimes if you can&#x27;t verify the solution with your own computer, you can use your computer to interrogate a more power computer to indirectly verify it. You ask inter-related questions that are easy to verify to the more power computer (called the &quot;prover&quot;) about it&#x27;s solution. If you get consistent answers back more frequently then chance, you can assume the entire solution is correct.<p>5. Going even further, you could have two &#x27;prover&#x27; computers and ask inter-related questions to both about the same solution. Since you can now cross-check their answers against each other, you are able to indirectly verify even more complex solutions. This is like a detective checking the stories if different witnesses against each other.<p>tl;dr - Some problems are unsolvable, but it may or may not be possible to verify a single solution. Computer scientists want to quantify the complexity of verifying these solutions.<p>Assumptions in Quantum Physics:<p>1. Particles can be &quot;entangled&quot;. This means that if you observe one particle, some other particle somewhere else will exhibit the exact same state change, as though they are connected by a mysterious communication channel.<p>2. This is super weird. Einstein thought it was so weird that he thought they must be missing something in their understanding.<p>3. Physicists created two separate mathematical models to describe how entanglement works: (A) the Tensor Product model, using finite dimension matrices and (B) the Commuting Operator mode, using infinite dimension matrices<p>tl;dr - Quantum Physics is so weird that they came up with two mathematical models for entanglement<p>Assumptions in Mathematics:<p>1. Because physicists said that the same physical property (entanglement) could be described either with infinite matrices or finite matrices, maybe you can approximate an infinite matrix using a finite matrix. This idea is the &#x27;Connes embedding conjecture&#x27;.<p>2. If finite and infinite matrices are actually interrelated by the Connes embedding conjecture, maybe it means that solving one means you solved the other.<p>tl;dr - The two quantum physics models inspired mathematicians to conjecture about the relationship between finite and infinite matrices<p>Back to Physics:<p>1. To prove that quantum entanglement exists in real life and isn&#x27;t just a math mistake, they came up with the idea of a &quot;nonlocal game&quot;. You set up a seemingly-random test where two &#x27;players&#x27; make guesses and the goal is to have them hit on the same guess more often than chance. If they win higher than chance, you can assume they are entangled.<p>2. Using those tests, they showed that quantum entanglement is real.<p>Back to Computer Science:<p>1. Computational complexity is not just a theory. &quot;The resources that computers need to solve and verify problems — time and memory — are fundamentally physical.&quot; If you change the rules physics, you can change the rules of computer science. Our understanding of quantum entanglement as a real thing thus changes the rules of what a computer can do.<p>2. If two entangled particles can behave in a correlated manner, you can (in theory) use that coordination to verify the solution to harder problems by using them as two &quot;provers&quot;. For example, you could have each particle randomly pick a node in your infinite graph and inspect a different edge. But since they are entangled, the two particles always pick the same node. That means you can use them to indirectly inspect an infinite graph and verify a previously unverifiable solution.<p>New CS discovery in the paper:<p>1. Entangled provers allow you to verify solutions to the unsolvable halting problem. That implies that you can also verify the solution to any problem easier than the halting problem using quantum particles.<p>2. This neat and re-writes the rules of CS complexity, but at a glance appears not very interesting to other fields.<p>New Implication for Physics:<p>1. Wait a sec! Since the problem you are verifying itself is unsolvable, this implies the two mathematical models of quantum entanglement are NOT equivalent (more details in article).<p>New Implication for Math:<p>1. This means the Connes embedding conjecture (which said we can estimate an infinite-dimension matrix from from a finite dimension matrix) is also definitely FALSE.<p>So in the process of computer scientists trying to clarify the bounds of computational complexity theory, they accidentally re-wrote the rules of quantum physics and invalidated a major mathematical assumption. But the CS researchers aren&#x27;t physicists or classical mathematicians, so they don&#x27;t even claim to fully understand the cross-discipline implications of what they discovered.