Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The paper[1] claims that MIP* = RE. At first I wasn't sure whether that was true, because the paper is too long and complicated for me to verify.

But then I found a series of questions and answers written by this quantum guy Scott Aaronson[2] and by this other quantum guy Kenneth Regan[3], who both know a bunch of quantum stuff. Each one of their blog posts makes me more certain about MIP* = RE, to the point that now I'm 99.9% sure it's true, even though I could never verify it myself.

[1] https://arxiv.org/abs/2001.04383

[2] https://www.scottaaronson.com/blog/?p=4512

[3] https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-ti...



I hadn't heard of Aaronson or Regan before, but perhaps they communicate, and therefore their blog posts might be correlated.

From the new proof though, I'm certain that I can't put an upper or lower bound on the probability of whether they're right.


They do communicate, but only nonclassically.


No, they don’t communicate. They use entangled particles to coordinate their blog posts. :P


Start with 100 and 0 and go from there


What about complex numbers in probabilities?


Their modulus squared gives you the probability.

https://en.wikipedia.org/wiki/Probability_amplitude


They „denote by MIP the class of languages that have multiprover interactive proof systems,“ and by „MIP∗, the ‚entangled-prover‘ analogue of the class MIP. Informally the class MIP∗, first introduced in [CHTW04], contains all languages that can be decided by a classical polynomial-time verifier interacting with multiple quantum provers sharing entanglement.“


very meta


So, from reading a bit, it seems MIP* was proven harder than it was thought to be, correct?


Perhaps Scott and Kenneth were in cahoots.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: