While preparing for class, and for my general edification, I have been trying to organize thoughts about recent important results in theory and algorithms. The latter I try to keep up with on general principles, but the former is largely above my station on the mountain, as I stand on the col looking up at the peak through the swirling clouds of my own ignorance. I'm an engineer, and proud of it, and so I have an engineer's understanding of complexity theory. In fact, I have the understanding of an engineer trained in the 1980s; the theorists have been busy since then, and have really changed the landscape! So, take all that I say here with a grain of salt...
(announced in January 2020, with evaluation ongoing)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
I'm not part of the CS theory community, but I could hear the trumpets, kazoos and champagne corks from over here in the Engineering quad on our global, virtual campus. This paper is considered a big deal, assuming it's right, to which most people seem to have given provisional assent.
The introductory paragraph of the CACM version summarizes forty years of theory -- exactly what I need. The key advances: understanding the importance of randomness (in both the action of the algorithm, and in a willingness to accept a probabilistic answer, I believe), interactive proofs, and multiple interactive provers. The authors then go on to cite the addition of entanglement as the fourth major shift. I feel like if I understood this paragraph alone, I would be a far better researcher.
Backing up a bit, computational complexity classes...checking The Complexity Zoo, we see that there are currently 546 complexity classes acknowledged there. Back when I was an undergrad, I learned about 2.5 of them: P, NP, and "bigger than NP", so things have changed a bit. To understand the importance of this paper, we are going to have to understand IP, MIP, MIP*, and RE and their relationship to some of the other basics. Okay, the Complexity Zoo itself is pretty intimidating, so let's try the introductory Petting Zoo, which introduces sixteen important classes...none of which are IP, MIP, MIP*, or RE. All right, let's roll up our sleeves and see what we know...
- P is the class of problems solvable in polynomial time -- the simple ones.
- NP does not mean "non-polynomial", it means non-deterministic polynomial. If you have a Turing machine that solves problems with high combinatoric complexity, then the challenge is to pick good potential answers to try. If trying one solution and failing doesn't help a whole lot in eliminating other possible solutions, you might be in NP territory. Typically, if the size of the problem is n, then the number of possible solutions is O(e^n). But the formal definition of NP is such that the Turing machine scratches its head, shrugs its shoulders, and somehow magically picks the right answer each time, in polynomial time. The practical implication is that there is an exponential number of potential answers that have to be checked one by one, but once you have found an answer it is easy to verify that the answer is correct.
- MA is Merlin-Arthur, and is the first time we run into two parties in our theoretical conception and proofs. Merlin has infinite computational power, and wants to prove to Arthur that he knows the solution to a problem, so Merlin sends Arthur a proof. (This proof must be no more than polynomial in size, relative to the problem size n.) Arthur has normal, mortal computational power, but he also has access to a source of randomness (coin flips), which he uses after receiving the proof from Merlin. Arthur checks the proof, using his coin flips as needed, but there is a probability he will wrongly decide whether or not the proof is correct. Generally, we require the probability of correctly accepting a true proof to be at least 2/3, and the probability of incorrectly accepting a wrong proof at 1/3. (That is, the probability of false positive or false negative is each no more than 1/3.) This is the introduction of randomness discussed above. Note that, in this conception, only one round of communication is used.
Merlin can be called the prover (P), and Arthur the verifier (V). Those terms come up a lot later.
(Theorists were actively working on this around the time I was an undergrad, but I was completely oblivious to it. Babai 1985 is a key reference.) - AM is Arthur-Merlin, which is similar except that Arthur makes his coin tosses before Merlin produces the proof, and sends the coin toss results to Merlin, who can use them as he wishes. After Merlin sends the proof to Arthur, Arthur is required to deterministically check the proof.
- IP is Interactive Proof, also introduced in 1985 by Goldwasser, Micali and Rackoff. It's similar to AM, except that there can be a polynomial number of rounds. This is where the interaction mentioned above comes in.
- MIP is Multiple Interactive Provers, introduced by Goldwasser & co. in 1988, uses two (or more?) provers. The provers are allowed to decide on a shared strategy or otherwise share information before the proof starts, but not after it begins. Perhaps the easiest way to enforce that non-communication is to verify the position of the two provers, and require their answers to be received by the verifier in time so short that the speed of light prevents them from having communicated with each other. Now we have our multiple provers.
- RE is Recursively Enumerable, and is the set of all problems that a Turing machine can solve in finite (but not limited to polynomial) time. It's a very big set.
- ...and for the purposes of this blog entry, there things stood for a long time...until:
- MIP*: MIP, except that the provers get to share entanglement beforehand. MIP* includes things like the CHSH game.
I'd like to have good pedagogical examples to go with each of those classes, but at the moment, I don't. My apologies; I'll try to add some later. One important note is that from MA on down, a lot of classes are often expressed in terms of cryptographic functions or cryptographic games.
Also, roughly, that list goes from less complex to more complex, with each class including all of the problems in the classes above it on the list, but in general not all of the relationships are exactly known. Most famously, NP is commonly believed to include problems that are outside of P, but that has never been proven.
And so, the proof of MIP* = RE...drum roll, please...
I don't understand it.
But I'm not alone, most people don't. It's a complicated thing.
In fact, the link above is to the CACM version of the paper, which is written for readers like me, but the full paper is 237 pages. Not very many people have even read the whole thing.
But, I think I am safe in saying this: Very, very, very roughly, it is now (provisionally) known that polynomial amounts of entanglement can be used to solve some very enormous problems. What "polynomial" means here, and what the constant factors are, and real-world examples of problems that are classically intractable but quantumly tractable in practice, all remain as future work. Henry Yuen even refers to this as an "elephant" they are trying to get a feel for.
I wish I could do a better job of explaining its importance, though. Instead, I will defer to one of the authors, Henry Yuen, and to Scott Aaronson. Scott in particular links to a lot of other explanations, so you can go from there.
