# What are the practical implications of "MIP\* = RE" for the forseable future? **URL:** \ **Category:** Factual Questions\ **Created:** [December 29, 2020, 10:29am UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167 "2020-12-29T10:29:14Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![Saffer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saffer/32/6440_2.png) [@Saffer](https://boards.straightdope.com/u/Saffer)\ **Post date:** [December 29, 2020, 10:29am UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/1 "2020-12-29T10:29:14Z")
> **[MIP\*=RE](https://scottaaronson.blog/?p=4512)** > > Another Update (Jan. 16): Yet another reason to be excited about this result—one that somehow hadn’t occurred to me—is that, as far as I know, it’s the first-ever fully conv… Is this just another result along the lines of “If we had quantum computers it would be awesome”? ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [December 29, 2020, 12:59pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/2 "2020-12-29T12:59:12Z")
No, such complexity results are of supreme importance. So are the constructions used to get such reductions. But who said anything about quantum computers? Anyway quantum computers do not magically solve any halting problem, unless there is something I’m missing. ---
**Author:** ![Saffer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saffer/32/6440_2.png) [@Saffer](https://boards.straightdope.com/u/Saffer)\ **Post date:** [December 29, 2020, 1:37pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/3 "2020-12-29T13:37:51Z")
References are made to entangled quantum provers. Are these not some sort of quantum computer? ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [December 29, 2020, 3:10pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/4 "2020-12-29T15:10:59Z")
Correct, this result concerns multiple quantum interactive provers. However, an interactive prover is not a (classical or quantum) “computer”. It is not computationally bounded in any way, rather you, the classical polynomial-time _verifier_ are. ---
**Author:** ![Precambrianmollusc](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/precambrianmollusc/32/63_2.png) [@Precambrianmollusc](https://boards.straightdope.com/u/Precambrianmollusc)\ **Post date:** [December 29, 2020, 3:13pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/5 "2020-12-29T15:13:55Z")
Could anyone dumb this down as to what the big deal is ? There was a link to a CNBC 15 minute piece on quantum computing in the link which was cool , so I assume this has either something to do with quantum computing or a wizard has figured out how to cast a fireball. ---
**Author:** ![Saffer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saffer/32/6440_2.png) [@Saffer](https://boards.straightdope.com/u/Saffer)\ **Post date:** [December 29, 2020, 3:16pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/6 "2020-12-29T15:16:48Z")
To add to this question: do we have (or might we soon have) the technology to build a quantum prover or whatever else is required to make practical use of this result? I don’t mean to diminish purely theoretical stuff, just curious about the practical implications. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [December 29, 2020, 3:17pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/7 "2020-12-29T15:17:43Z")
The interactive prover is like a magic quantum wizard, but you are not and it still has to be able to formally convince you that a given Turing machine halts or not in a way that you can verify. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [December 29, 2020, 3:22pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/8 "2020-12-29T15:22:46Z")
You can’t even theoretically build one, that’s the point, it is by definition a magic black box. This by no means means that the constructions that appear in the paper have no practical uses in quantum optics or whatever (they have practical _mathematical_ implications), but maybe some of the physicists reading this board have more to say about that. ---
**Author:** ![Saffer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saffer/32/6440_2.png) [@Saffer](https://boards.straightdope.com/u/Saffer)\ **Post date:** [December 29, 2020, 3:30pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/9 "2020-12-29T15:30:36Z")
Ok, so I think I can now dumb this down a bit. The just of it is that even if you know the answer to a difficult problem, it is not always easy to prove that you have the correct answer. For example “does some program halt?”. This paper says that 2 god like entities who can answer such questions that are unanswerable for non god like entities, can prove (to said non god like entities) that they have the correct answer, by playing some sort of interactive game. ---
**Author:** ![Precambrianmollusc](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/precambrianmollusc/32/63_2.png) [@Precambrianmollusc](https://boards.straightdope.com/u/Precambrianmollusc)\ **Post date:** [December 29, 2020, 3:42pm UTC](https://boards.straightdope.com/t/what-are-the-practical-implications-of-mip-re-for-the-forseable-future/929167/10 "2020-12-29T15:42:43Z")
Awesome thanks, my wizard reference was supposed to be along the the lines of ‘any sufficiently advanced technology will look like magic’ as this all was way above my head and looked like magic to me, I had no idea the point was how to prove something incomprehensible to someone who would not understand it.