# Approximate traces on groups and the quantum complexity class
$\operatorname{MIP}^{co,s}$

Isaac Goldbring and Bradd Hart  Department of Mathematics
University of California, Irvine, 340 Rowland Hall (Bldg.# 400), Irvine, CA
92697-3875<EMAIL_ADDRESS>http://www.math.uci.edu/ isaac Department of
Mathematics and Statistics, McMaster University, 1280 Main St., Hamilton ON,
Canada L8S 4K1<EMAIL_ADDRESS>http://ms.mcmaster.ca/ bradd/

###### Abstract.

An open question in quantum complexity theory is whether or not the class
$\operatorname{MIP}^{co}$, consisting of languages that can be efficiently
verified using interacting provers sharing quantum resources according to the
quantum commuting model, coincides with the class $coRE$ of languages with
recursively enumerable complement. We introduce the notion of a qc-modulus,
which encodes approximations to quantum commuting correlations, and show that
the existence of a computable qc-modulus gives a negative answer to a natural
variant of the aforementioned question.

I. Goldbring was partially supported by NSF grant DMS-2504477.

##  1\. Introduction

Throughout this note, $n$ and $m$ denote natural numbers that are at least $2$
and $[n]$ denotes the set $\\{1,\ldots,n\\}$ (and likewise for $[m]$).

We recall the following definitions from quantum information theory and
quantum complexity theory.

######  Definition 1.1.

  1. (1)

The set $C_{q}(n,m)$ of quantum correlations consists of the correlations of
the form $p(i,j|v,w)=\langle A^{v}_{i}\otimes B^{w}_{j}\xi,\xi\rangle$ for
$v,w\in[n]$ and $i,j\in[m]$, where H is a finite-dimensional Hilbert space,
$\xi\in H\otimes H$ is a unit vector, and for every $v,w\in[n]$,
$(A^{v}_{i}:i\in[m])$ and $(B^{w}_{j}\ :\ j\in[m])$ are positive operator-
valued measures (POVMs) on H.

  2. (2)

We set $C_{qa}(n,m)$ to be the closure in $[0,1]^{n^{2}m^{2}}$ of
$C_{q}(n,m)$.

  3. (3)

The set $C_{qc}(n,m)$ of quantum commuting correlations consists of the
correlations of the form $p(i,j|v,w)=\langle A^{v}_{i}B^{w}_{j}\xi,\xi\rangle$
for $v,w\in[n]$ and $i,j\in[m]$, where H is a separable Hilbert space, $\xi\in
H$ is a unit vector, and for every $v,w\in[n]$, $(A^{v}_{i}:i\in[m])$ and
$(B^{w}_{j}\ :\ j\in[m])$ are POVMs on H for which
$A^{v}_{i}B^{w}_{j}=B^{w}_{j}A^{v}_{i}$ for all $v,w\in[n]$ and $i,j\in[m]$.

Note that $C_{q}(n,m)\subseteq C_{qc}(n,m)$; since it is know that the latter
set is closed, we in fact have that $C_{qa}(n,m)\subseteq C_{qc}(n,m)$.
Tsirelson’s problem in quantum information theory asks if these latter two
sets in fact coincide; a negative resolution to this problem follows from the
main result of [1].

######  Definition 1.2.

  1. (1)

A nonlocal game with $n$ questions and $m$ answers is a pair
$\mathfrak{G}=(\mu,D)$, where $\mu$ is a probability distribution on
$[n]\times[n]$ and

$D:[n]\times[n]\times[m]\times[m]\to\\{0,1\\}$

is a function.

  2. (2)

Given a nonlocal game $\mathfrak{G}$ as in the previous item and
$p\in[0,1]^{n^{2}m^{2}}$, we define the value of $\mathfrak{G}$ at $p$ to be

$\operatorname{val}(\mathfrak{G},p):=\sum_{v,w\in[n]}\mu(v,w)\sum_{i,j\in[m]}D(v,w,i,j)p(i,j|v,w).$

######  Definition 1.3.

Given a nonlocal game $\mathfrak{G}$ with $n$ questions and $m$ answers, we
define:

  1. (1)

the entangled value of $\mathfrak{G}$ to be

$\operatorname{val}^{*}(\mathfrak{G}):=\sup_{p\in
C_{qa}(n,m)}\operatorname{val}(\mathfrak{G},p);$

  2. (2)

the quantum commuting value of $\mathfrak{G}$ to be

$\operatorname{val}^{co}(\mathfrak{G}):=\sup_{p\in
C_{qc}(n,m)}\operatorname{val}(\mathfrak{G},p).$

######  Definition 1.4.

A language $L$ (in the sense of complexity theory) belongs to the class
$\operatorname{MIP}^{*}$ if there is an effective mapping
$z\mapsto\mathfrak{G}_{z}$ from strings to nonlocal games such that:

  * •

if $z\in L$, then $\operatorname{val}^{*}(\mathfrak{G}_{z})\geq\frac{2}{3}$

  * •

if $z\notin L$, then
$\operatorname{val}^{*}(\mathfrak{G}_{z})\leq\frac{1}{3}$.

The complexity class $\operatorname{MIP}^{co}$ is defined in the analogous
fashion, using $\operatorname{val}^{co}$ instead of $\operatorname{val}^{*}$.

The following landmark result in quantum complexity theory appears in [1]:

######  Theorem 1.5.

$\operatorname{MIP}^{*}=\operatorname{RE}$. In other words, the languages that
belong to $\operatorname{MIP}^{*}$ are precisely the recursively enumerable
languages, that is, those languages $L$ for which there is an algorithm that
enumerates $L$.

In particular, $\operatorname{MIP}^{*}$ contains undecidable problems (such as
the halting problem).

In [1], it was pointed out that every element of the class
$\operatorname{MIP}^{co}$ is co-recursively enumerable, that is, the
complement of $\operatorname{MIP}^{co}$ is recursively enumerable. Denoting by
$\operatorname{coRE}$ the complexity class of langauges that are co-
recursively enumerable, the authors of [1] ask whether or not the
aforementioned inclusion is actually an equality:

######  Question 1.6.

Does $\operatorname{MIP}^{co}=\operatorname{coRE}$?

The main result of this note is that a very natural variant of the above
question has a negative answer provided a certain computability assumption
about “approximate” quantum commuting correlations holds, and that, in fact,
all languages that belong to this natural variant of $\operatorname{MIP}^{co}$
are actually decidable.

First, we recall the following definitions:

######  Definition 1.7.

  1. (1)

Given $p\in[0,1]^{n^{2}m^{2}}$, we say that $p$ is synchronous if
$p(i,j|v,v)=0$ for all $v\in[n]$ and all _distinct_ $i,j\in[m]$.

  2. (2)

We let $C_{qa}^{s}(n,m)$ and $C_{qc}^{s}(n,m)$ denote the synchronous elements
of $C_{qa}(n,m)$ and $C_{qc}(n,m)$ respectively.

  3. (3)

Given a nonlocal game $\mathfrak{G}$, we let
$\operatorname{s-val}^{*}(\mathfrak{G})$ and
$\operatorname{s-val}^{co}(\mathfrak{G})$ denote the corresponding synchronous
values of $\mathfrak{G}$, which are defined analogously to
$\operatorname{val}^{*}(\mathfrak{G})$ and
$\operatorname{val}^{co}(\mathfrak{G})$, except that we only take the supremum
over $C^{s}_{qa}(n,m)$ and $C^{s}_{qc}(n,m)$ respectively.

  4. (4)

We define the complexity class $\operatorname{MIP}^{*,s}$ and
$\operatorname{MIP}^{co,s}$ analogously to $\operatorname{MIP}^{*}$ and
$\operatorname{MIP}^{co}$, this time using the appropriate synchronous values
of the games in the definition.

The main result of [1] actually shows that $\operatorname{MIP}^{*,s}$
coincides with $RE$ and thus a reasonable variant of Question 1.6 above is
whether or not $\operatorname{MIP}^{co,s}$ coincides with coRE.

We will see later in Proposition 3.5 that synchronous commuting correlations
satisfy a certain “stability” property, namely that correlations that are
almost quantum commuting correlations (in a certain technical sense) are near
actual quantum commuting correlations. The main result of this note (Theorem
4.3 below) will show that if this stability relation can be realized
“effectively,” then all languages in $\operatorname{MIP}^{co,s}$ are in RE,
and are thus decidable. Since there are elements of coRE that are undecidable
(such as the complement of the halting problem), we would obtain a negative
solution to the synchronous version of Question 1.6 above. Said in the
opposite direction: if it turns out that $\operatorname{MIP}^{co,s}=$ coRE,
then there is no effective version of stability for almost quantum commuting
correlations.

The authors would like to thank Alec Fox, Thomas Vidick, and Henry Yuen for
helpful conversations around this work.

##  2\. Preliminaries: traces on groups and group $\mathrm{C}^{*}$-algebras

Fix a countable group $G$ and let $\mathbb{C}G$ denote the corresponding group
ring. We recall the following terminology:

######  Definition 2.1.

A function $\tau:G\to\mathbb{C}$ is called:

  1. (1)

of positive type if for all
$\sum_{\lambda}a_{\lambda}u_{\lambda}\in\mathbb{C}G$, we have
$\sum_{\lambda,\gamma}\overline{a_{\lambda}}a_{\gamma}\tau(\lambda^{-1}\gamma)\geq
0$

  2. (2)

a class function if $\tau$ is constant on conjugacy classes.

The following terminology is not standard, but convenient for our purposes. In
what follows, $\mathbb{D}$ denotes the unit disc in the complex plane.

######  Definition 2.2.

A function $\tau:G\to\mathbb{D}$ is called a trace on $G$ if it is a class
function of positive type.

Here is the reason for the abuse in terminology. Below, $C^{*}(G)$ denotes the
universal $\mathrm{C}^{*}$-algebra of the group $G$.

######  Fact 2.3.

Given a trace $\tau$ on $C^{*}(G)$, its restriction to $G$ is a trace on $G$
(in the sense of Definition 2.2). Moreover, the map $\tau\mapsto\tau|G$ is a
bijection between traces on $C^{*}(G)$ and traces on $G$.

In the sequel, we will freely abuse notation and use $\tau$ to denote both the
trace on the group $G$ as well as the corresponding trace on $C^{*}(G)$.

Note that in the definition of being positive type, we can restrict attention
to elements of the subring $\mathbb{Q}(i)G$ without changing the notion.
Assuming then that some countable enumeration $G=(g_{0},g_{1},g_{2},\ldots)$
of $G$ has been given, there is thus an effectively enumerable countable list
$(R_{l})$ of requirements that characterize when a function
$\tau:G\to\mathbb{D}$ is a trace on $G$. Note really that this list of
requirements is independent of the group $G$ in question and just depends on
some fixed effective coding of $\mathbb{Q}(i)$.

We now consider “relaxations” of these requirements:

######  Definition 2.4.

Fix $k,l\in\mathbb{N}$ with $k\geq 1$.

  1. (1)

If $R_{l}$ is the requirement
$\sum_{\lambda,\gamma}\overline{a_{\lambda}}a_{\gamma}\tau(\lambda^{-1}\gamma)\geq
0$, then we define the relaxed requirement $R_{l}^{k}$ to be that
$\sum_{\lambda,\gamma}\overline{a_{\lambda}}a_{\gamma}\tau(\lambda^{-1}\gamma)$
is within $\frac{1}{k}$ of the positive real axis.

  2. (2)

If $R_{l}$ is the requirement $\tau(\gamma^{-1}\lambda\gamma)=\tau(\lambda)$,
then we define the relaxed requirement $R_{l}^{k}$ to be
$|\tau(\gamma^{-1}\lambda\gamma)-\tau(\lambda)|<\frac{1}{k}$.

We say that $\tau:G\to\mathbb{D}$ is a $k$-approximate trace on $G$ if the
relaxed requirements $R_{1}^{k},\ldots,R_{k}^{k}$ hold.

The following lemma is obvious:

######  Lemma 2.5.

For each $k\in\mathbb{N}$, there is $\delta>0$ such that, for all functions
$\tau,\tau^{\prime}:G\to\mathbb{D}$, if $\tau$ is a trace on $G$ and
$\|\tau-\tau^{\prime}\|_{\infty}<\delta$, then $\tau^{\prime}$ is a
$k$-approximate trace on $G$. Moreover, $\delta$ depends only on $k$ and not
on $G$ and this dependence is computable from $k$.

##  3\. The groups $\mathbb{F}(n,m)$

Below, for $n,m\geq 2$, we let $\mathbb{F}(n,m)$ denote the group freely
generated by $n$ elements of order $m$. In the $\mathrm{C}^{*}$-algebra
$C^{*}(\mathbb{F}(n,m))$, for each $v\in[n]$, we let
$e^{n,m}_{v,1},\ldots,e^{n,m}_{v,m}$ denote the projections onto the
eigenspaces corresponding to the eigenvalue $\xi_{m}^{i}$ of the unitary
operator corresponding to the $v^{\text{th}}$ generator $u^{n,m}_{v}$ of
$\mathbb{F}(n,m)$, where $\xi_{m}$ denotes a primitive $m^{\text{th}}$ root of
unity. We then have that
$(u_{v}^{n,m})^{j}=\sum_{i=1}^{m}\xi_{m}^{ji}e^{n,m}_{v,i}$ for each $v\in[n]$
and $j\in[m]$.

######  Definition 3.1.

Given $p\in[0,1]^{n^{2}m^{2}}$, we say that a trace $\tau$ on
$\mathbb{F}(n,m)$ is adapted to $p$ if
$p(i,j|v,w)=\tau(e^{n,m}_{v,i}e^{n,m}_{w,j})$ for all $v,w\in[n]$ and all
$i,j\in[m]$.

Here is the key fact relating traces on $\mathbb{F}(n,m)$ and quantum
commuting correlations:

######  Fact 3.2.

([2]) For $p\in[0,1]^{n^{2}m^{2}}$, we have $p\in C_{qc}^{s}(n,m)$ if and only
if there is a trace $\tau$ on $\mathbb{F}(n,m)$ that is adapted to $p$.

###### Proof.

In [2], they show that $p\in C_{qc}^{s}(n,m)$ if and only if there is a
tracial C*-algebra $(A,\tau)$ and a generating family of projections $p_{v,i}$
such that $\sum_{i=1}^{m}p_{v,i}=1$ for each $v=1,\ldots,n$ and such that
$p(i,j|v,w)=\tau(p_{v,i}p_{w,j})$. However, letting
$\pi:C^{*}(\mathbb{F}(n,m))\to A$ be the surjective *-homomorphism determined
by sending $e_{v,i}$ to $p_{v,i}$ and defining $\tau^{\prime}$ on
$C^{*}(\mathbb{F}(n,m))$ by $\tau^{\prime}(x):=\tau(\pi(x))$, we obtain the
equivalence with the above statement. ∎

######  Lemma 3.3.

There is a computable function $s:\mathbb{N}^{7}\to\bigcup_{n,m\geq
2}\mathbb{Q}(i)\mathbb{F}(n,m)$ so that, for each $n,m\geq 2$, each
$v,w\in[n]$, each $i,j\in[m]$, and each $k\geq 1$, we have that
$s(v,w,i,j,k,n,m)\in\mathbb{Q}(i)\mathbb{F}(n,m)$ and
$\|e^{n,m}_{v,i}e^{n,m}_{w,j}-s(v,w,i,j,k,n,m)\|<\frac{1}{k}$, where the norm
is the norm on the universal representation of $\mathbb{C}\mathbb{F}(n,m)$,
that is, the norm on $C^{*}(\mathbb{F}(n,m))$.

###### Proof.

The theorem follows from the fact that the relation
$(u_{v}^{n,m})^{j}=\sum_{i=1}^{m}\xi_{m}^{ji}e^{n,m}_{v,i}$ mentioned above
can be effectively inverted to express each $e^{n,m}_{v,i}$ as a polynomial in
the generator $u_{v}^{n,m}$ with coefficients in the computable field
$\mathbb{Q}(\xi_{m})$. Moreover, this procedure is uniform in $n$ and $m$. ∎

In order to match notation, in what follows we will rewrite $s(v,w,i,j,k,n,m)$
as $s_{v,w,i,j,k}^{n,m}$. Also, given a function
$\tau:\mathbb{F}(n,m)\to\mathbb{D}$, we extend it to a function
$\tau:\mathbb{Q}(i)\mathbb{F}(n,m)\to\mathbb{C}$ by linearity.

######  Definition 3.4.

Fix $n,m\geq 2$, $p\in\mathbb{[}0,1]^{n^{2}m^{2}}$, and $k\geq 1$. We say that
a function (not necessarily a trace) $\tau:\mathbb{F}(n,m)\to\mathbb{D}$ is
$k$-adpated to $p$ if

$|p(i,j|v,w)-\tau(s^{n,m}_{v,w,i,j,k})|<\frac{1}{k}$

for all $v,w\in[n]$ and all $i,j\in[m]$.

Here is the “stability” property satisfied by synchornous quantum commuting
correlations:

######  Proposition 3.5.

Given $m,n\geq 2$ and $\epsilon>0$, there is $k\geq 1$ such that, for all
$p\in[0,1]^{n^{2}m^{2}}$, if there is a $k$-approximate trace $\tau$ on
$\mathbb{F}(n,m)$ that is $k$-adpated to $p$, then there is $p^{\prime}\in
C_{qc}^{s}(n,m)$ with $\|p-p^{\prime}\|_{\infty}<\epsilon$.

###### Proof.

Suppose that the lemma is false for some $m,n,\epsilon$, that is, for each
$k\geq 1$, there is $p_{k}\in\mathbb{[}0,1]^{n^{2}m^{2}}$ for which there is a
$k$-approximate trace $\tau_{k}$ on $\mathbb{F}(n,m)$ that is $k$-adapted to
$p_{k}$ and yet $\|p_{k}-p\|_{\infty}\geq\epsilon$ for all $p\in
C_{qc}^{s}(n,m)$. Let $p$ be a subsequential limit of $p_{k}$. Since
$\tau_{k}$ is pointwise bounded, by passing to a subsequence if necessary, we
may suppose that $\tau_{k}$ converges pointwise to a function
$\tau:\mathbb{F}(n,m)\to\mathbb{D}$. Note then that $\tau$ is an actual trace
on $\mathbb{F}(n,m)$ that is adapted to $p$, whence $p\in C_{qc}^{s}(n,m)$.
Since $\|p-p_{k}\|_{\infty}<\epsilon$ for some $k$, this is a contradiction. ∎

##  4\. The main theorem

######  Definition 4.1.

We say that $T:\mathbb{N}^{2}\to\mathbb{N}$ is a qc-modulus if it satisfies
the conclusion of Proposition 3.5 for $\epsilon=\frac{1}{12}$, that is, for
all $n,m\geq 2$ and all $p\in\mathbb{[}0,1]^{n^{2}m^{2}}$, if there is a
$T(n,m)$-approximate trace $\tau$ on $\mathbb{F}(n,m)$ that is
$T(n,m)$-adapted to $p$, then there is $p^{\prime}\in C_{qc}^{s}(n,m)$ with
$\|p-p^{\prime}\|_{\infty}<\frac{1}{12}$.

We let $X^{n,m}_{k}$ denote those
$p\in\mathbb{(}[0,1]\cap\mathbb{Q})^{n^{2}m^{2}}$ for which there is a
$k$-approximate trace $\tau:\mathbb{F}(n,m)\to\mathbb{Q}(i)$ that is
$k$-adpated to $p$.

The following lemma is clear:

######  Lemma 4.2.

Each $X^{n,m}_{k}$ is recursively enumerable, uniformly in $k$, $n$, and $m$.

Here is the main result of this note:

######  Theorem 4.3.

If there is a computable qc-modulus $T:\mathbb{N}^{2}\to\mathbb{N}$, then
every language in $\operatorname{MIP}^{co,s}$ is in RE (and thus decidable).

###### Proof.

Fix a computable qc-modulus $T$ and suppose that
$L\in\operatorname{MIP}^{co,s}$. Let $z\mapsto\mathfrak{G}_{z}$ be an
efficient mapping from strings to nonlocal games such that:

  * •

if $z\in L$, then $\operatorname{s-val}^{co}(\mathfrak{G}_{z})\geq\frac{2}{3}$

  * •

if $z\notin L$, then
$\operatorname{s-val}^{co}(\mathfrak{G}_{z})\leq\frac{1}{3}$.

Here is the algorithm for enumerating $L$. Given a string $z$, first determine
the dimensions $n$ and $m$ for $\mathfrak{G}_{z}$. Set $k:=T(n,m)$ and let
$(p_{l})$ be a computable enumeration of $X^{n,m}_{k}$. The algorithm then
simply starts computing $\operatorname{val}(\mathfrak{G}_{z},p_{l})$ for each
$l$; if for some $l$ we see that
$\operatorname{val}(\mathfrak{G}_{z},p_{l})>\frac{1}{2}$, then we declare that
$z\in L$.

Soundness of the algorithm: suppose that
$\operatorname{val}(\mathfrak{G}_{z},p_{l})>\frac{1}{2}$. By the choice of
$k$, there is $p\in C_{qc}^{s}(n,m)$ such that
$\|p_{l}-p\|_{\infty}<\frac{1}{12}$. It follows that
$\operatorname{val}^{co,s}(\mathfrak{G}_{z})\geq\operatorname{val}(\mathfrak{G}_{z},p)>\frac{1}{2}-\frac{1}{12}>\frac{1}{3}$,
which tells us that $z\in L$.

Completeness of the algorithm: suppose that $z\in L$ and take $p\in
C_{qc}^{s}(n,m)$ such that
$\operatorname{val}(\mathfrak{G}_{z},p)\geq\frac{2}{3}$. Let $\tau_{p}$ be a
trace on $\mathbb{F}(n,m)$ that is adapted to $p$, whence
$|p(i,j|v,w)-\tau_{p}(s^{n,m}_{v,w,i,j,k})|\leq\|e^{n,m}_{v,i}e^{n,m}_{w,j}-s^{n,m}_{v,w,i,j,k}\|<\frac{1}{k}$
for all $v,w\in[n]$ and all $i,j\in[m]$. Fix $\eta>0$ small enough and let
$p^{\prime}\in([0,1]\cap\mathbb{Q}m)^{n^{2}m^{2}}$ and
$\tau^{\prime}:\mathbb{F}(n,m)\to\mathbb{D}\cap\mathbb{Q}(i)$ be such that
$\|p-p^{\prime}\|_{\infty},\|\tau_{p}-\tau^{\prime}\|_{\infty}<\eta$. By Lemma
2.5, if $\eta$ is small enough, then $\tau^{\prime}$ is a $k$-approximate
trace on $\mathbb{F}(n,m)$. Note also that

$|p^{\prime}(i,j|v,w)-\tau^{\prime}(s^{n,m}_{v,w,i,j,k})|<2\eta+\|e^{n,m}_{v_{i}}e^{n,m}_{w,j}-s^{n,m}_{v,w,i,j,k}\|<\frac{1}{k}$

as long as $\eta$ is small enough. (Note that the conditions on $\eta$ are
effective in terms of $k$ and thus in terms of $n$ and $m$.) It follows that
$\tau^{\prime}$ is $k$-adapted to $p^{\prime}$, whence there is $l$ such that
$p^{\prime}=p_{l}$. As long as $\eta<\frac{1}{12}$, we have that
$\operatorname{val}(\mathfrak{G}_{z},p_{l})\geq\frac{2}{3}-\frac{1}{12}>\frac{1}{2}$.
Consequently, the algorithm will tell us that $z\in L$. ∎

We note that it remains a possibility that $\operatorname{MIP}^{co,s}$ is
properly contained in co-RE and yet there is no computable qc-modulus.

## References

  * [1] Z. Ji, A. Natarajan, T. Vidick, J. Wright and H. Yuen, MIP* = RE, preprint, arxiv 2001.04383
  * [2] V. Paulsen, S. Severini, D. Stahlke, I. Todorov, and A. Winter. Estimating quantum chromatic numbers, Journal of Functional Analysis, vol. 270 (2016), 2180-2222.


See pages 1-last of RFF_ICA_LDA_Submission.pdf