> On 18 Feb 2020, at 11:55, Lawrence Crowell <goldenfieldquaterni...@gmail.com> > wrote: > > The preprint at 165 pages is a bit much to tackle right away. This does > though indicate that quantum computing can work a subset of recursively > enumerable languages > > LC > > On Monday, February 17, 2020 at 1:44:55 PM UTC-6, Philip Thrift wrote: > Quantum computing, entanglement, and theorem provers > > "We show that the class MIP* of languages that can be decided by a classical > verifier interacting with multiple all-powerful quantum provers sharing > entanglement is equal to the class RE of recursively enumerable languages.”
What does that mean? All universal machine is “equal" to the Class of all RE set. The main difference is that in the quantum case, the simulation can be done in (unbounded) polynomial time and space, where with classical machine some will need super-exponential time for some simulation. The quantum universal machine does not compute more, nor less, than the Babbage Machine (already Turing universal, although never completed as such). The class MIP should be better defined, I think. “multiple all-powerful quantum provers sharing entanglement” is a bit fuzzy too. Bruno > > MIP*=RE > by Scott Aaronson > January 14th, 2020 > https://www.scottaaronson.com/blog/?p=4512 > <https://www.scottaaronson.com/blog/?p=4512> > > ref: https://arxiv.org/abs/2001.04383 <https://arxiv.org/abs/2001.04383> > > Verifying proofs to very hard math problems is possible with infinite quantum > entanglement > by Tom Siegfried > February 17, 2020 > https://www.sciencenews.org/article/how-quantum-technique-highlights-math-mysterious-link-physics > > <https://www.sciencenews.org/article/how-quantum-technique-highlights-math-mysterious-link-physics> > > A quantum strategy could verify the solutions to unsolvable problems — in > theory > by Emily Conover > January 24, 2020 > https://www.sciencenews.org/article/quantum-strategy-could-verify-solutions-unsolvable-problems-theory > > <https://www.sciencenews.org/article/quantum-strategy-could-verify-solutions-unsolvable-problems-theory> > > > @philipthrift > > -- > You received this message because you are subscribed to the Google Groups > "Everything List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to everything-list+unsubscr...@googlegroups.com > <mailto:everything-list+unsubscr...@googlegroups.com>. > To view this discussion on the web visit > https://groups.google.com/d/msgid/everything-list/81b5965b-caf5-4bfe-afe7-1ec3d7e304d9%40googlegroups.com > > <https://groups.google.com/d/msgid/everything-list/81b5965b-caf5-4bfe-afe7-1ec3d7e304d9%40googlegroups.com?utm_medium=email&utm_source=footer>. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/9152D2AF-7322-4505-B213-C200127F8F9A%40ulb.ac.be.
