5 ms·
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 fo
by lwneal 7y ago
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 https://arxiv.org/abs/2001.04383
[2] https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512
[3] https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-time-quantum-provable/ https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-ti...
- iamvik 7y agovery meta
- xenonite 7y agoThey „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.“
- raverbashing 7y agoSo, from reading a bit, it seems MIP* was proven harder than it was thought to be, correct?
- peterburkimsher 7y agoI 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.
- titanomachy 7y agoThey do communicate, but only nonclassically.
- fortydegrees 7y agoStart with 100 and 0 and go from there
- peterburkimsher 7y agoWhat about complex numbers in probabilities?
- bergoid 7y agoTheir modulus squared gives you the probability. https://en.wikipedia.org/wiki/Probability_amplitude https://en.wikipedia.org/wiki/Probability_amplitude
- bjornsing 7y agoNo, they don’t communicate. They use entangled particles to coordinate their blog posts. :P
- jconnop 7y agoPerhaps Scott and Kenneth were in cahoots.