Monday, October 05, 2020

MIP* = RE Redux

Everything pre-covid seems at least five years ago to me, so it's hard to believe that MIP* = RE is a 2020 result. To remind you, consider the model where we have two powerful provers put in separate rooms where they can't communicate (think suspects of a crime put in separate interrogation rooms). An computationally efficient verifier can ask them questions based on random coins. Thirty years ago, Laszlo Babai, Carsten Lund and myself showed that every language in nondeterministic exponential time has proofs in this model.

Now suppose the provers have entangled quantum bits. This question has a long history that culminates in the MIP* = RE paper earlier this year by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen showing that every proof of any length can be proven in this model. Incredible!

But wait, why is there a new version 2 dated last week? Turns out the MIP* = RE paper relied on a 2016 paper by Vidick which was later discovered to have a bug. No worries, as the authors of the MIP* = RE paper got around this issue by a quantum analysis of a low-degree test from that old Babai-Fortnow-Lund paper.

Vidick's blog post explains it all, including the angst of a major result falling apart temporarily. He has good company. Glad it all worked out. 

No comments:

Post a Comment