On Tuesday, February 18, 2020 at 7:19:58 AM UTC-6, Bruno Marchal wrote:
>
>
> On 18 Feb 2020, at 11:55, Lawrence Crowell <goldenfield...@gmail.com
> <javascript:>> 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
>
>
One possible insight I have on this is that this may be a quantum version
of hyper-computation. I am a bit loathe to reading a 165 page paper of
considerable density, but this may illustrate a correspondence with QM on
hyper-computation. In order to fully perform this theorem proving it
requires an infinite entanglement, which seems parallel to the context in
general relativity where there is continuity between I^{+∞} and r_- for
hypercomputation. The failure thought of GR based hypercomputation to
circumvent Gödel may then be parallel to an incompleteness here wiith GR
and the ability to compute all RE functions by a single scheme. Such would
require infinite entanglement.
LC
>
>
>
>
>> MIP*=RE
>> by Scott Aaronson
>> January 14th, 2020
>> https://www.scottaaronson.com/blog/?p=4512
>>
>> ref: 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
>>
>> 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
>>
>>
>> @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 everyth...@googlegroups.com <javascript:>.
> 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/10ca2ea5-bbd7-4d69-9073-4b8e137e3b27%40googlegroups.com.
