## Unitary Correlation Matrices

Today I’d like to sketch a question that’s been pushing me in a lot of different directions over the past few years — some sane, others less so; few fruitful, but all instructive. The question is motivated by the problem of placing upper bounds on the amount of entanglement needed to play a two-player non-local game (near-)optimally. But it can also be stated as a natural mathematical question in itself, so this is how I’ll present it first, and then only briefly discuss some motivation. (I wish I could write I’ll also present results, but these will be quite sparse.) All that is to come is based on discussions with Oded Regev, though all inaccuracies and naïvetés are mine.

## Prelude: Vector Correlation Matrices

Before jumping to unitary correlation matrices, let’s — rather pedantically — introduce vector correlation matrices. Most of you are already familiar with this simple object: a vector correlation matrix is an ${n\times n}$ Hermitian matrix ${C}$ with complex entries such that there exists an integer ${d}$ and unit vectors ${u_1,\ldots,u_n\in {\mathbb C}^d}$ such that ${C_{i,j} = \langle u_i,u_j\rangle}$ for all ${(i,j)\in\{1,\ldots,n\}^2}$. In other words: a Gram matrix with diagonal entries equal to ${1}$.

A natural question is, given a vector correlation matrix ${C}$, what is the minimal dimension ${d}$ in which there exists vectors achieving the specified correlations? Clearly ${d\leq n}$, the dimension of the span of the ${n}$ vectors; moreover the identity matrix implies that ${d=n}$ is sometimes necessary.

If we allow ${\varepsilon}$-approximations, we can do better: the Johnson-Lindenstrauss lemma implies that ${d=O(\varepsilon^{-2}\log n)}$ is sufficient (and necessary) to find unit vectors such that ${|\langle u_i,u_j\rangle-C_{i,j}|\leq\varepsilon}$ for each ${i,j}$. And if we only require the approximation to hold on the average over the choice of ${i}$ and ${j}$, then no dependence on ${n}$ is necessary: ${d = O(\epsilon^{-2})}$ suffices.

This is all good and well. Now onto the interesting stuff!

## Theme: Unitary Correlation Matrices

Define a unitary correlation matrix to be an an ${n\times n}$ Hermitian matrix ${C}$ with complex entries such that there exists an integer ${d}$ and unitary matrices ${U_1,\ldots,U_n\in {\mathbb C}^{d\times d}}$ such that ${C_{i,j} = d^{-1}\textrm{Tr}(U_i U_j^\dagger)}$ for all ${(i,j)\in\{1,\ldots,n\}^2}$. Considering block matrices shows that the set of unitary correlation matrices is convex.

By forgetting the unitary structure of the ${U_i}$ we see that a unitary correlation matrix is automatically a vector correlation matrix; in particular it is positive semidefinite with all diagonal entries equal to ${1}$. While the latter is a characterization of vector correlation matrices, however, as soon as ${n\geq 4}$ (and not before) there exists vector correlation matrices that are not unitary correlation matrices. This is not completely trivial to see, and appears in a paper by Dykema and Juschenko; it is a nice exercise to work out. Now for the main question:

(${\mathfrak{D}}$): Dimension reduction for unitaries. Let ${n\in{\mathbb N}}$ and ${\epsilon > 0 }$ be given. Does there exist an explicit ${d'=d'(n;\epsilon)}$ such that for every ${n\times n}$ unitary correlation matrix ${C}$ there are ${d'}$-dimensional unitaries ${V_1,\ldots,V_n}$ such that

$\displaystyle \Big|\frac{1}{d'}\textrm{Tr}\big(V_i\,V_j^\dagger\big) - C_{i,j} \Big| \leq \varepsilon \qquad \forall (i,j)\in\{1,\ldots,n\}^2\; .$

While the analogue question for vectors is trivial for ${\epsilon=0}$, and a fundamental result in geometry for ${\epsilon>0}$, extremely little is known on the question for unitaries. Virtually the only general statement that can be made is that, at least, some bound ${d'}$ exists. This follows by a simple compactness argument, but does not yield any meaningful bound on the growth of ${d'}$ as a function of ${n}$ and ${\epsilon}$. In fact no explicit bound, however large, is known to hold in general. Let’s explore the problem a bit.

## Variatio: Equivalent formulations

A nice feature of question (${\mathfrak{D}}$) is that it is reasonably robust, in the sense that different natural formulations of the question can be shown equivalent, up to simple variations on the precise scaling of ${d'}$. For example, one can relax the constraint of being unitary to the sole requirement that the matrices have all singular values at most ${1}$. At the opposite end of the spectrum one can consider a more structured problem which considers correlations between projection matrices (so all eigenvalues are ${0}$ or ${1}$). Both these variants can be shown equivalent to the unitary case via some simple reductions.

The one variant which makes a substantial difference is the case of correlation matrices with real entries. A beautiful result of Tsirelson shows that any extremal real correlation matrix can be realized exactly, by Hermitian matrices having all eigenvalues ${\{-1,1\}}$,  in dimension ${d' = 2^{\sqrt{\lfloor n/2\rfloor}}}$, and this bound is tight; relatively precise bounds of the form ${d'=2^{\Theta(\epsilon^{-1})}}$ are known for small enough ${\epsilon>0}$. (Note that even though projection matrices are Hermitian, and thus give rise to real correlations, Tsirelson’s result does not imply a positive answer for the case of projections as the dimension-${d'}$ matrices recovered via Tsirelson’s construction will in general be Hermitian, but not projectors, even when the original matrices were.)

## Interlude: Motivation

Quantum games. One can arrive at question (${\mathfrak{D}}$) by asking about the minimal dimension of near-optimal strategies in a quantum two-player game. Experts will immediately see the connection, and I will not elaborate on this. Roughly, the easy observation is that correlations that are achievable by entangled players in a nonlocal game take the form

$\displaystyle \langle \psi| A \otimes B |\psi\rangle = \textrm{Tr}(AKB^TK^\dagger),$

where ${|\psi\rangle}$ is a unit vector in ${{\mathbb C}^d \otimes {\mathbb C}^d}$ (the entanglement), ${K}$ is a complex ${d\times d}$ matrix that can be computed from ${|\psi\rangle}$, and ${A,B}$“observables”, i.e. Hermitian operators that square to identity describing the players’ measurement operators. (A more general formulation considers projections, rather than observables.) In case ${|\psi\rangle}$ is the so-called “maximally entangled state”, ${K = d^{-1/2} I}$ and we recover precisely an entry from a correlation matrix. (The case of a general state gives rise to a slight variant of question ${(\mathfrak{D})}$, to which I am not sure whether it is equivalent or not.)
Arriving at the question from this “physical” angle, it seems like it “ought” to have a reasonable answer: certainly, if one fixes the size of the game, and an approximation error ${\epsilon>0}$, then there must exist some dimension that suffices to implement an ${\epsilon}$-optimal strategy. No such result is known. If anything existing signs seem to point in the negative direction: for instance, Slofstra very recently showed that there exists a fixed, constant-sized game such that the optimal winning probability of ${1}$ can only be achieved in the limit of infinite dimension (but it does seem to be the case that, for this game, ${\epsilon}$-optimal strategies can be found in dimension ${\textrm{poly}(\epsilon^{-1}}$). Note that this result implies that the set of correlation matrices of projections is not closed.

Connes’ conjecture. A different, though related, way to arrive at question (${\mathfrak{D}}$) is via the famous “Connes embedding conjecture” in the theory of ${C^*}$ algebras. Connes’ embedding conjecture states, rather informally, that any separable ${II_1}$ factor (i.e. a von Neumann algebra with trivial center that is infinite-dimensional as a vector space, but has a finite faithful trace) embeds into a suitable ultrapower of the hyperfinite factor ${\mathcal{R}}$. Kirchberg showed that the conjecture is equivalent to the following statement.

Theorem. The validity of Connes’ conjecture for some factor ${M}$ is equivalent to the following: For all ${\epsilon>0}$, ${n,k\in{\mathbb N}}$ and unitaries ${U_1,\ldots,U_n\in M}$ there is a ${d'\in{\mathbb N}}$ and unitaries ${V_1,\ldots,V_n\in M_{d'}({\mathbb C})}$, such that

$\displaystyle \Big|\tau\big(U_i\,U_j^*\big)-\frac{1}{d}\textrm{Tr}\big(V_i\,V_j^\dagger\big)\Big|\leq \epsilon,$

where ${\tau}$ is the trace on ${M}$.
This formulation is close to question (${\mathfrak{D}}$), except for two important differences: first, we assume that the target correlations are achievable in finite dimension ${d}$. This makes the problem easier, and would make it trivial if we were not to introduce a second important difference, which is that we ask for explicit bounds on ${d'}$. As a result I do not know of any formal implication between (${\mathfrak{D}}$) and Connes’ conjecture, in either direction.

Graph limits. Finally, for the combinatorialist let me mention an analogous (though, as far I can tell, not directly related) question, formulated by Aldous and Lyons in the context of their study of limits of bounded-degree graphs. The distance between two finite graphs of the same constant degree (but not necessarily the same number of vertices) can be measured via the sampling distance ${\delta}$: ${\delta(G,G') = \sum_{r=1}^\infty 2^{-r}\delta_r(G,G')}$, where ${\delta_r(G,G')}$ denotes the total variation distance between the distributions on rooted ${r}$-neighborhoods obtained by sampling a random vertex from ${G}$ (resp. ${G'}$) and considering the sub-graph induced on all vertices at distance at most ${r}$ from the sampled vertex. With this notion in place, Question 10.1 in Aldous and Lyons’ paper on unimodular random networks asks the following:

(Aldous-Lyons:) For every ${\epsilon>0}$ there is an integer ${d}$ such that for every (finite) graph ${G}$ there is a graph ${G'}$ on ${d}$ vertices such that ${\delta(G,G')\leq \epsilon}$.

In page 1458 the authors mention that the validity of their conjecture for the special class of Cayley graphs would imply that all finitely generated groups are sofic (very roughly, can be embedded into finite-dimensional permutation groups). Even though we do not know of an example of a group that is not sofic, this would be a very surprising result. In particular, it would imply Connes’s Embedding Conjecture for group von Neumann algebras, since the latter is known to hold for sofic groups.

## Development: Results

Unfortunately this is going to be one of the shortest, most boring developments in musical history: there is too little to say! I could describe multiple failed attempts. In particular, naïve attempts at dimension reduction, inspired by Johnson-Lindenstrauss or other standard techniques, or incremental “gradient-descent” type of progressive block diagonalization procedures, all seem doomed to fail.

Aside from Tsirelson’s result for real correlation matrices, the one case for which we were able to find a cute proof is the case of permutation correlation matrices, where each ${U_i}$ is assumed to be a permutation matrix. The fact that permutations are sparse seems to make it easier to operate on them by “shifting entries around”; unitaries have a more rigid structure. The proof uses a simple combinatorial argument, with the heaviest hammer being Hall’s theorem guaranteeing the existence of a perfect matching, which is used to simultaneously re-organize the “${1}$” entries in a subset of the permutation matrices while preserving all correlations. The upper bound on ${d'}$ we obtain is of order ${2^n/\varepsilon^2}$, which may be the right order.

More is known in terms of negative results, i.e. lower bounds on ${d'}$. Such bounds abound in the theory of nonlocal games, where they go by the name of “dimension witness”. The best known results I am aware of imply that ${d'}$ should grow at least like ${\min(2^{\Omega(\epsilon^{-1})},2^n)}$, which is good for very small ${\epsilon}$, and also ${d'=\Omega(n^c)}$, which holds for ${\epsilon}$ smaller than a universal constant (the two bounds are obtained from different families of correlations; see here for the former and here for the latter). An interesting consequence of the (proof of) the second bound, which appears in joint work with Natarajan, is that even an ${\varepsilon}$-approximation on average (over the entries of C) requires large dimension. This implies that no “oblivious” rounding technique, as in the Johnson-Lindenstrauss lemma, will work: such a technique would guarantee small approximation error on average independently of ${n}$.

## Coda

There has been a lot of progress recently on lower bounds, stimulated by works on quantum non-local games. This includes a beautiful framework of games for checking “non-commutative” analogues of linear equations over ${\mathbb{F}_2}$, developed by Cleve and Mittal and Ji; extensions of the framework to testing finitely presented groups by Slofstra; a development of approaches based on operator systems by Paulsen and co-authors, and many others. But no upper bounds! Get to work: things can’t remain this way.