Verifying proofs to very hard math problems is possible with infinite quantum entanglement

It has long been a mystery why pure math can reveal so much about the nature of the physical world.

Antimatter was discovered in Paul Dirac’s equations before being detected in cosmic rays. Quarks appeared in symbols sketched out on a napkin by Murray Gell-Mann several years before they were confirmed experimentally. Einstein’s equations for gravity suggested the universe was expanding a decade before Edwin Hubble provided the proof. Einstein’s math also predicted gravitational waves a full century before behemoth apparatuses detected those waves (which were produced by collisions of black holes — also first inferred from Einstein’s math).

Nobel laureate physicist Eugene Wigner alluded to math’s mysterious power as the “unreasonable effectiveness of mathematics in the natural sciences.” Somehow, Wigner said, math devised to explain known phenomena contains clues to phenomena not yet experienced — the math gives more out than was put in. “The enormous usefulness of mathematics in the natural sciences is something bordering on the mysterious and … there is no rational explanation for it,” Wigner wrote in 1960.

But maybe there’s a new clue to what that explanation might be. Perhaps math’s peculiar power to describe the physical world has something to do with the fact that the physical world also has something to say about mathematics.

At least that’s a conceivable implication of a new paper that has startled the interrelated worlds of math, computer science and quantum physics.

In an enormously complicated 165-page paper, computer scientist Zhengfeng Jiand colleagues present a result that penetrates to the heart of deep questions about math, computing and their connection to reality. It’s about a procedure for verifying the solutions to very complex mathematical propositions, even some that are believed to be impossible to solve. In essence, the new finding boils down to demonstrating a vast gulf between infinite and almost infinite, with huge implications for certain high-profile math problems. Seeing into that gulf, it turns out, requires the mysterious power of quantum physics.

Everybody involved has long known that some math problems are too hard to solve (at least without unlimited time), but a proposed solution could be rather easily verified. Suppose someone claims to have the answer to such a very hard problem. Their proof is much too long to check line by line. Can you verify the answer merely by asking that person (the “prover”) some questions? Sometimes, yes. But for very complicated proofs, probably not. If there are two provers, though, both in possession of the proof, asking each of them some questions might allow you to verify that the proof is correct (at least with very high probability). There’s a catch, though — the provers must be kept separate, so they can’t communicate and therefore collude on how to answer your questions. (This approach is called MIP, for multiprover interactive proof.)

Verifying a proof without actually seeing it is not that strange a concept. Many examples exist for how a prover can convince you that they know the answer to a problem without actually telling you the answer. A standard method for coding secret messages, for example, relies on using a very large number (perhaps hundreds of digits long) to encode the message. It can be decoded only by someone who knows the prime factors that, when multiplied together, produce the very large number. It’s impossible to figure out those prime numbers (within the lifetime of the universe) even with an army of supercomputers. So if someone can decode your message, they’ve proved to you that they know the primes, without needing to tell you what they are.

Someday, though, calculating those primes might be feasible, with a future-generation quantum computer. Today’s quantum computers are relatively rudimentary, but in principle, an advanced model could crack codes by calculating the prime factors for enormously big numbers.

That power stems, at least in part, from the weird phenomenon known as quantum entanglement. And it turns out that, similarly, quantum entanglement boosts the power of MIP provers. By sharing an infinite amount of quantum entanglement, MIP provers can verify vastly more complicated proofs than nonquantum MIP provers.

It is obligatory to say that entanglement is what Einstein called “spooky action at a distance.” But it’s not action at a distance, and it just seems spooky. Quantum particles (say photons, particles of light) from a common origin (say, both spit out by a single atom) share a quantum connection that links the results of certain measurements made on the particles even if they are far apart. It may be mysterious, but it’s not magic. It’s physics.

Say two provers share a supply of entangled photon pairs. They can convince a verifier that they have a valid proof for some problems. But for a large category of extremely complicated problems, this method works only if the supply of such entangled particles is infinite. A large amount of entanglement is not enough. It has to be literally unlimited. A huge but finite amount of entanglement can’t even approximate the power of an infinite amount of entanglement.

As Emily Conover explains in her report for Science News, this discovery proves false a couple of widely believed mathematical conjectures. One, known as Tsirelson’s problem, specifically suggested that a sufficient amount of entanglement could approximate what you could do with an infinite amount. Tsirelson’s problem was mathematically equivalent to another open problem, known as Connes’ embedding conjecture, which has to do with the algebra of operators, the kinds of mathematical expressions that are used in quantum mechanics to represent quantities that can be observed.

Refuting the Connes conjecture, and showing that MIP plus entanglement could be used to verify immensely complicated proofs, stunned many in the mathematical community. (One expert, upon hearing the news, compared his feces to bricks.) But the new work isn’t likely to make any immediate impact in the everyday world. For one thing, all-knowing provers do not exist, and if they did they would probably have to be future super-AI quantum computers with unlimited computing capability (not to mention an unfathomable supply of energy). Nobody knows how to do that in even Star Trek’s century.

Still, pursuit of this discovery quite possibly will turn up deeper implications for math, computer science and quantum physics.

It probably won’t shed any light on controversies over the best way to interpret quantum mechanics, as computer science theorist Scott Aaronson notes in his blog about the new finding. But perhaps it could provide some sort of clues regarding the nature of infinity. That might be good for something, perhaps illuminating whether infinity plays a meaningful role in reality or is a mere mathematical idealization.

On another level, the new work raises an interesting point about the relationship between math and the physical world. The existence of quantum entanglement, a (surprising) physical phenomenon, somehow allows mathematicians to solve problems that seem to be strictly mathematical. Wondering why physics helps out math might be just as entertaining as contemplating math’s unreasonable effectiveness in helping out physics. Maybe even one will someday explain the other.

Source:

https://www.sciencenews.org/article/how-quantum-technique-highlights-math-mysterious-link-physics