Quantum computing, entanglement, and theorem provers
බැලීම් 13
පළමු නොකියවූ පණිවිඩය දක්වා මඟ හරින්න
Philip Thrift
2020 පෙබ 17, 14.44.552020-02-17
සිට Everything List
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."
MIP*=RE
by Scott Aaronson
January 14th, 2020
Verifying proofs to very hard math problems is possible with infinite quantum entanglement
by Tom Siegfried
February 17, 2020
A quantum strategy could verify the solutions to unsolvable problems — in theory
by Emily Conover
January 24, 2020
@philipthrift
Lawrence Crowell
2020 පෙබ 18, 05.55.002020-02-18
සිට Everything List
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
Philip Thrift
2020 පෙබ 18, 06.56.132020-02-18
සිට Everything List
But of course theory may not end up in reality - of actually making a quantum computer that works according to the theory.
@philipthrift
Bruno Marchal
2020 පෙබ 18, 08.19.582020-02-18
සිට everyth...@googlegroups.com
On 18 Feb 2020, at 11:55, Lawrence Crowell <goldenfield...@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 languagesLC
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*=REby Scott AaronsonJanuary 14th, 2020Verifying proofs to very hard math problems is possible with infinite quantum entanglementby Tom SiegfriedFebruary 17, 2020A quantum strategy could verify the solutions to unsolvable problems — in theoryby Emily ConoverJanuary 24, 2020@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-li...@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.
Bruno Marchal
2020 පෙබ 18, 08.26.182020-02-18
සිට everyth...@googlegroups.com
On 18 Feb 2020, at 12:56, Philip Thrift <cloud...@gmail.com> wrote:Purely theoretically, not surprising that quantum computing - computing with qubits ( geometry of qubits: http://home.lu.lv/~sd20008/papers/essays/Geometry%20[paper].pdf ) - should be RE-language capable.
Yes, that was the first result in the field, by Benioff.
But of course theory may not end up in reality - of actually making a quantum computer that works according to the theory.
Quantum computer are expected to be more quick on some task, albeit this has not yet been proven (but I gave few doubt that’s the case).
What Deutsch already understood is that the universal quantum computer does not violate the Church-Turing thesis. They cannot compute a function that the Babbage computer, or your laptop can’t already compute.
The complexity classes might differ, but all universal machine, classical or quantum, compute the exact same class of functions. They all compute the same Phi_i, and enumerate the same W_i.
Bruno
@philipthrift
On Tuesday, February 18, 2020 at 4:55:00 AM UTC-6, Lawrence Crowell 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 languagesLC
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."MIP*=REby Scott AaronsonJanuary 14th, 2020Verifying proofs to very hard math problems is possible with infinite quantum entanglementby Tom SiegfriedFebruary 17, 2020A quantum strategy could verify the solutions to unsolvable problems — in theoryby Emily ConoverJanuary 24, 2020@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-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/5e27b503-b8de-4d53-984d-c9e4bf7850e4%40googlegroups.com.
Lawrence Crowell
2020 පෙබ 18, 17.37.202020-02-18
සිට Everything List
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> 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 languagesLC
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*=REby Scott AaronsonJanuary 14th, 2020Verifying proofs to very hard math problems is possible with infinite quantum entanglementby Tom SiegfriedFebruary 17, 2020A quantum strategy could verify the solutions to unsolvable problems — in theoryby Emily ConoverJanuary 24, 2020@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.
සියල්ලට පිළිතුරු දෙන්න
කර්තෘට පිළිතුරු දෙන්න
ඉදිරියට යවන්න
නව පණිවිඩ 0