A computability perspective on William Slofstra’s resolution of the strong Tsirelson problem

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. C_q (the q stands for quantum) is the class of distributions which can be generated by two non-commuting parties sharing finite-dimensional entanglement. C_{qs} (the s 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 \{A_i\otimes I\}_{i\in I} and Bob’s like \{I \otimes B_j\}_{j\in J}. C_{qa} (the a stands for approximation) are those distributions which can be obtained as a limit of distributions in C_q (or equivalently as a limit of distributions in C_{qs}). C_{qc} (the c 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 [A_i,B_j] = 0 for all i,j, 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 G consists of question sets A, B, a probability distribution \pi on A\times B, answer sets X, Y, and a valuation function V: A\times B \times X \times Y \to {0,1}.
If x\in \{q,qs,qa,qc\}, then an x-strategy p: (X\times Y) \times (A\times B) \to [0,1] is a correlation from C_x.

The game G is played as follows:
An arbiter samples a pair (a,b) from the distribution \pi and sends a to Alice and b to Bob. Then Alice and Bob send x and y respectively to the arbiter with joint probability p(x,y\mid a,b). The value of G with respect to strategy p, sometimes denoted \omega (G\mid p) is just the expectation value of V when the game is played.

    \[\omega(G\mid p) = \sum_{x,y} \pi(a,b)p(x,y\mid a,b) V(a,b,x,y).\]

We’re particularly interested in perfect strategies, i.e. strategies p such that \omega (G\mid p) = 1.

For each x\in \{q,qs,qa,qc\}, let G_x be the set of games which have a perfect x-strategy that wins with probability 1. In other words, G_x 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 x. (By performing real world experiments, we can in principle set x 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.

  1. G_{qc} strictly contains G_{qs}, by demonstration of an explicit game with a perfect winning distribution which is in G_{qc}\setminus G_{qs}. This in fact shows that C_{qc} strictly contains C_{qs}.
  2. G_{qs} 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 C_{qc}. However, one should note that William only explicitly proves a lower bound, i.e. that G_{qc} 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 G_{qc} problem as a special case of the word problem for groups.

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

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

  • for all n, either T(n) \in L or T does not halt on input n, and
  • for all x\in L, there is some n so that T(n) = x.

A language L is co-r.e. if the complement of L 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 L and Turing machine T with the property that x \in L iff there is some w such that T(x,w) accepts, while x \not\in L iff for all w, T(x,w) rejects. Then L is recursively enumerable. (To prove this, pick an enumeration of the space of pairs (x,w). Let T'(n) run T on (x,w)_n and then spit out x if T 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 G_{qc}, then the value of the SDP at each level of its NPA hierarchy is 1. If a game is not in G_{qc}, 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 qs-strategy: try the levels of the NPA hierarchy until one of them proves the value is <1.

We conclude that G_{qc} is co-r.e. Similarly, the Lasserre hierarchy converges to the C_{q} value from below, so we can conclude that G_q 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 G_{q} = G_{qc}, then G_{qc} is both r.e. and co-r.e. and therefore decidable. But G_{qc} 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 x\in L or x\nin L, 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 G_{qa} in the sense of the LPA and Laserre hierarchies.
If G_{qa} is r.e., then G_{qa} \neq G_{qs}. Otherwise, G_{qs} 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 G_{qa} 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 C_{qa} 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 G_{qa}? If the answer is somehow very shockingly no, then we shouldn’t expect to find a proof very easily. As before, if G_{qa} is not computable with respect to HALT, then it’s different from G_{qs} and Connes is false. This would similarly separate from G_q, which would be nice but less surprising. Similarly, proving the wild noncomputability of G_{qs} would separate it from G_{q}.

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 G_{qa} (or G_{qs}) have a recursive reduction from HALT?


One Reply to “A computability perspective on William Slofstra’s resolution of the strong Tsirelson problem”

  1. [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.

Leave a Reply

Your email address will not be published. Required fields are marked *