In William Slofstra’s breakthrough paper, he proves a general group embedding theorem relating to binary constraint games. (This is a wonderful proof which I’ll post some exposition about soon.) From this, he derives two very nice corollaries regarding what kinds of correlations are possible with different axioms quantum mechanics. In this note, we’ll show that one of these corollaries (or a weakened form thereof) can be derived from the other in a potentially interesting way. This leads to a question for which I’m very surprised not to know the answer: is there an algorithm to compute the approximate value of a nonlocal game, even given access to an oracle solving the halting problem?

Scott Aaronson does a very nice job explaining exactly what it is that William proved. Instead of replicating the whole endeavor, I’ll send you there. I’ll spend just a couple of paragraphs fixing some notation and recalling standard definitions; if you’re already familiar with the subject then you might skip past it.

In Scott’s post, he discusses the hierarchy of four kinds of quantum correlation classes, which I’ll give explicit names to here. Formally, these classes are sets of bipartite probability distributions. (the stands for quantum) is the class of distributions which can be generated by two non-commuting parties sharing finite-dimensional entanglement. (the stands for spatial) is the class which can be generated with infinite-dimensional entanglement in the usual spatial tensor product model, where Alice’s observables look like and Bob’s like . (the stands for approximation) are those distributions which can be obtained as a limit of distributions in (or equivalently as a limit of distributions in ). (the stands for commuting) are those distributions which can be generated in the commuting-operator model, where Alice and Bob’s observables don’t have a tensor product structure, but we still have for all , i.e. all of Alice’s observables commute with all of Bob’s.

This framework covers general correlations, but now we’ll be interested only in *games* and strategies thereof. A game consists of question sets , a probability distribution on , answer sets , and a valuation function .

If , then an -strategy is a correlation from .

The game is played as follows:

An arbiter samples a pair from the distribution and sends to Alice and to Bob. Then Alice and Bob send and respectively to the arbiter with joint probability . The value of with respect to strategy , sometimes denoted is just the expectation value of when the game is played.

We’re particularly interested in *perfect strategies*, i.e. strategies such that .

For each , let be the set of games which have a perfect -strategy that wins with probability . In other words, is the set of games which Alice and Bob can always win without communicating if they act according to the laws of quantum mechanics prescribed by . (By performing real world experiments, we can in principle set to be “whatever laws the real world obeys”. We just have to be careful to perform the experiment at time-scales comparable to the time it takes a lightspeed signal to travel between Alice and Bob. Experimentalists at TU Delft and elsewhere have done this!)

**If you tuned out for the standard background stuff, this is a good place to tune back in.**

William’s paper gives two main results of interest to quantum theorists.

- strictly contains , by demonstration of an explicit game with a perfect winning distribution which is in . This in fact shows that strictly contains .
- is an undecidable decision problem, by a recursive reduction from the word problem for groups.

This resolves what was an important open question: pinning down the complexity of the class . However, one should note that William only explicitly proves a lower bound, i.e. that is at least as hard as the word problem for groups (which in turn is exactly as hard as HALT). It’s not hard to see from that the reduction also goes the other way. Indeed, the main contribution of a previous work by Slofstra, Cleve, and Liu was to characterize the problem as a special case of the word problem for groups.

However, there’s another way to see that is at most as hard as HALT, and this method applies also to . First, let’s fix some notions from computability theory.

**Definition.** Informally, language is *recursively enumerable (r.e.)* if there is an algorithm to spit out all of the elements of , in some order. More formally, we demand the existence of a Turing machine such that

- for all , either or does not halt on input , and
- for all , there is some so that .

A language is co-r.e. if the complement of is r.e.

Another way to think of r.e. and co-r.e. are as computability versions of NP and coNP. (For a broader view, see the Wikipedia page on the arithmetical hierarchy.) Suppose we have a language and Turing machine with the property that iff there is some such that accepts, while iff for all , rejects. Then is recursively enumerable. (To prove this, pick an enumeration of the space of pairs . Let run on and then spit out if accepts.) The converse is also true.

The NPA hierarchy can be used to give a sequence of semidefinite programs whose values converge to the C_{qc} value from above. So if a game is in , then the value of the SDP at each level of its NPA hierarchy is . If a game is not in , then there is some finite level of the NPA hierarchy witnessing this fact. This suggests the following recursive enumeration procedure for the set of games with no winning -strategy: try the levels of the NPA hierarchy until one of them proves the value is .

We conclude that is co-r.e. Similarly, the Lasserre hierarchy converges to the value from below, so we can conclude that is r.e. Now we observe that this gives us an upper bound on the computational complexity of these problems.

**Remark:** If a language is r.e. or co-r.e., then it is decidable with access to a HALT oracle.

These upper bounds lead us to the implication between Slofstra’s two results. First, we need one more tool.

**Fact:** A language L is decidable iff it is both r.e. and co-r.e.

The proof uses the duality approach familiar to computer scientists from {semidefinite, linear} programming.

If , then is both r.e. and co-r.e. and therefore decidable. But is undecidable; contradiction! This proof is “worse” than that given in Slofstra’s paper in the sense that it’s not effective — it doesn’t give an explicit game separating the two classes. In return for being less effective, this idea lets us say some other stuff that I think is kind of neat.

**Proof of fact.**

Given input x, run the r.e. and co-r.e. algorithms in parallel until one of them spits out x. This certifies either that or , depending on which algorithm spat it out. This is guaranteed to happen in finite (but arbitrarily long!) time. Suppose we’re given input x. We use the r.e. algorithm to “approximate the sequence from below” and in parallel we use the co-r.e. algorithm to “approximate the sequence from above”. Eventually, after only finitely many steps, one of the approximations will show that x is in or out of the language.

We can use this idea to tell us something about approximation schemes for deciding in the sense of the LPA and Laserre hierarchies.

If is r.e., then . Otherwise, would be both r.e. and co-r.e. and therefore decidable. This resolves the weak Tsirelson conjecture is resolved. But this is equivalent to the Connes embedding conjecture, one of the biggest open problems in operator algebras.

In other words, if G_{qa} has a Lasserre-style approximation, then the Connes embedding conjecture is false. In fact, we get this conclusion even if has finite-length certificates with respect to any decidable proof system! Taking the converse, if the Connes embedding conjecture is true, then the general mathematical problem of showing that particular games lie in is hopeless. Hopefully, we would still be able to cross this “Turing barrier” for specific games that we care about.

Can we get any upper bound on the complexity of ? If the answer is somehow very shockingly no, then we shouldn’t expect to find a proof very easily. As before, if is not computable with respect to HALT, then it’s different from and Connes is false. This would similarly separate from , which would be nice but less surprising. Similarly, proving the wild noncomputability of would separate it from .

Why would this be shocking? It would violate a deeply held belief that one might call The Computable Church-Turing Thesis For People That Aren’t Logicians:

If a computational problem is defined in terms of natural computer science notions, then it’s no harder than HALT.

Of course, many people used to believe the Extended Church-Turing thesis for polynomial-time computations in the physical world, up until Shor’s algorithm happened. So the question remains: does (or ) have a recursive reduction from HALT?

[Following up from our conversation in the hallway]

Setting aside many of the nuances of this problem, it looks like you want to determine if a HALT oracle can be used to compute the limit of a sequence of SDP optimal objective values. Is this the case?

If so, is there anything in your particular problem that makes this fundamentally different from using a HALT oracle to compute a limit of a plain-vanilla sequence of real numbers? Your sequence would have some nice properties (i.e. a limit is known to exist; the sequence is monotonic) that a HALT oracle could exploit.