Major Breakthrough In Quantum Computing Shows That MIP* = RE

erek

erek

[H]F Junkie
Joined
Dec 19, 2005
Messages
10,894
Excited for all the new developments in Quantum Computin' !!!!!!!!

"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. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019).
An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 1 or at most 12. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure Cqa of the set of quantum tensor product correlations is strictly included in the set Cqc of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras."

https://science.slashdot.org/story/...rough-in-quantum-computing-shows-that-mip--re
 
Page 10 held a major revelation I did not previously grasp.
Trying to anneal some puzzle by shaking balls into holes till
they all optimally fit.

Classic can get jammed up. Heat it & start over. Repeat...
Quantum somehow tunnels straight to the best answer.
Puzzle stubbornly half-solved-wrong is not a barrier.
 
Last edited:
  • Like
Reactions: erek
like this
erek said:
Excited for all the new developments in Quantum Computin' !!!!!!!!

"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. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019).
An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 1 or at most 12. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure Cqa of the set of quantum tensor product correlations is strictly included in the set Cqc of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras."

https://science.slashdot.org/story/...rough-in-quantum-computing-shows-that-mip--re
Click to expand...

now I know what your full name is ... erek einstein
 
You must log in or register to reply here.
Back
Top