# Geometry of Banach spaces: a new route towards Position Based Cryptography

Marius Junge<EMAIL_ADDRESS>Department of Mathematics, University of
Illinois, Urbana, IL 61801, USA  Aleksander M. Kubicki<EMAIL_ADDRESS>Carlos Palazuelos<EMAIL_ADDRESS>David Pérez-García<EMAIL_ADDRESS>
###### Abstract

In this work we initiate the study of Position Based Quantum Cryptography
(PBQC) from the perspective of geometric functional analysis and its
connections with quantum games. The main question we are interested in asks
for the optimal amount of entanglement that a coalition of attackers have to
share in order to compromise the security of any PBQC protocol. Known upper
bounds for that quantity are exponential in the size of the quantum systems
manipulated in the honest implementation of the protocol. However, known lower
bounds are only linear.

In order to deepen the understanding of this question, here we propose a
Position Verification (PV) protocol and find lower bounds on the resources
needed to break it. The main idea behind the proof of these bounds is the
understanding of cheating strategies as vector valued assignments on the
Boolean hypercube. Then, the bounds follow from the understanding of some
geometric properties of particular Banach spaces, their type constants. Under
some regularity assumptions on the former assignment, these bounds lead to
exponential lower bounds on the quantum resources employed, clarifying the
question in this restricted case. Known attacks indeed satisfy the assumption
we make, although we do not know how universal this feature is. Furthermore,
we show that the understanding of the type properties of some more involved
Banach spaces would allow to drop out the assumptions and lead to
unconditional lower bounds on the resources used to attack our protocol.
Unfortunately, we were not able to estimate the relevant type constant.
Despite that, we conjecture an upper bound for this quantity and show some
evidence supporting it. A positive solution of the conjecture would lead to
prove the proposed PV protocol to be secure for all practical purposes and to
a drastic progress towards the question asked above.

###### Contents

  1. 1 Introduction
    1. 1.1 Summary of results
    2. 1.2 Proof sketch
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Position Based Cryptography in 1-D
    3. 2.3 One-round Quantum games
    4. 2.4 Banach spaces, operator ideals and type constants
      1. 2.4.1 Operator ideals
      2. 2.4.2 Interpolation of Banach spaces
      3. 2.4.3 Type/cotype of a Banach space
      4. 2.4.4 Vector valued maps on the Boolean hypercube
      5. 2.4.5 Some key estimates of type constants
  3. 3 The game $\mathbf{G_{Rad}}$
    1. 3.1 Use of classical communication in cheating strategies
    2. 3.2 Pure strategies
  4. 4 Bounds for “smooth” strategies. Theorem 1.1
    1. 4.1 Proofs of Lemmas 4.1 and 4.3
    2. 4.2 Proof of Proposition 4.6
  5. 5 A conjecture towards unconditional lower bounds
    1. 5.1 Type constant of subspaces
    2. 5.2 Volume ratio
  6. 6 Discussion
  7. A Handier expressions for $\sigma^{i}_{\mathcal{S}^{\mathcal{U}}}$, $\sigma^{ii}_{\mathcal{S}^{\mathcal{U}}}$
  8. B Non-pure strategies in Theorem 4.5
  9. C Tensor norms and enough symmetries

##  1 Introduction

In the field of Position Based Cryptography (PBC) one aims to develop
cryptographic tasks using the geographical position of a third party as its
only credential. Once the party proves to the verifier that it is in fact
located at the claimed position, they interact considering the identity of the
third party as granted. Basing cryptographic security on the position of the
communicating parties could result very appealing in practical contexts such
as the use of autonomous cars, or the secure communication between public
services or banks. Besides that, at a more fundamental level, secure PBC could
also serve as a way to circumvent insecurity under man-in-the middle attacks,
a security leak suffered by standard cryptographic primitives. This
vulnerability still prevails even in presence of information-theoretical
security, as, for example, in the celebrated case of Quantum Key Distribution.
In these settings, the security guarantees always come after the assumption
that the identity of the trusted agents is granted. In PBC this assumption can
be, at least, relaxed. Moreover, PBC proved to be a rich field of research
emanating deep questions and connections from its study. To mention a few,
attacks for PBC has been related with quantum teleportation [1], circuit
complexity [41], classical complexity theory [5] and, very recently, with
properties of the boundary description of some processes in the context of the
holographic duality AdS/CFT [27, 28]. In this work, we add to this list a
connection with deep questions on the geometry of Banach spaces.

The main task in PBC is the one of _Position Verification_ (PV). In PV a
prover has to convince a verifier (usually composed by several agents
spatially distributed) that it is located at a claimed position. This setting
has been studied since the 90’s in the context of classical cryptography.
Nonetheless, in purely classical scenarios, PV is easily proven to be insecure
against a team of colluding adversaries surrounding the honest location [11].
This motivates the study of _quantum_ PV schemes, in which the communication
between prover and verifier is in general quantum. This idea was initially
developed by A. Kent [22] and made rigorous only later on in [4]. In this last
paper, the authors construct a generic attack for any quantum PV scheme. To
construct the general attack of [4], the authors built on works by L. Vaidman
[50], realizing that the cheating action in the setting of PV consists on
performing what they called _instantaneous non-local computation_. In this
last task, two (or more) distant agents have to implement a quantum operation
on a distributed input when subjected to non-signalling constraints – see [4]
or Section 2.2 below for more details. At a first sight, the existence of
general attacks to quantum PV renders the development of secure PBQC a
hopeless program. However, their attack did not come for free for the
adversaries, as in the case of classical PV. On the contrary, in order to
cheat, the dishonest agents have to use a huge amount of entanglement – a
delicate and expensive resource in quantum information processing. Even when
in [1] another generic attack to PV was proposed exponentially reducing the
entanglement consumption, the amount of entanglement required is still far
from what is realizable in any practical situation. This leads naturally to
the following question, which is the one motivating this work:

######  Question 1.

How much entanglement is necessary to break _any_ PV scheme?

Answering this question with a large enough lower bound would lead to the
existence of PBC schemes which are _secure for all practical purposes_ , term
coined in [10]. The search of such an answer has been an active field of
research in the last decades, specially in the years right after the
publication of [4]. Therefore, some progress is already available. Indeed, [4]
provides the first PV protocol secure against cheaters with _no_ entanglement.
This was improved in [1] and later in [46] providing PV protocols requiring a
linear amount of entanglement (linear in the size of the quantum system used
in the honest protocol). In terms of this figure of merit, the entanglement
consumption in the generic attack of [1] is exponentially large, hence leaving
an exponential gap between lower and upper bounds for the amount of
entanglement necessary to break PV schemes. After almost ten years since [4]
this is still essentially all it is known about Question 1 in its original
formulation. Other works have studied attacks with some specific structure
[5], have designed attacks that are efficient emulating the computation of
unitaries with low complexity [41] or have studied security under additional
cryptographic assumptions [49].

###  1.1 Summary of results

Here we aim to go back to Question 1 in its simplest form: the one-dimensional
case without any further assumptions. Unfortunately, we were not able to find
a definite answer to the question but we report here some progress that opens
an avenue for a deeper understanding of the problem.

From now on, we focus on the study of _quantum_ resources required to attack
PV, considering classical communication as a free resource and unlimited
computational power for all the agents involved. In this work,

  * •

we rephrase the setting of PV in the framework of quantum games,

  * •

connecting that way Question 1 with powerful techniques coming from Banach
space theory,

  * •

and providing new lower bounds on the amount of entanglement necessary to
break a specific PV protocol presented in Section 3. However, these bounds are
not completely general but depend on some properties of the strategies
considered. Intuitively, _smooth_ strategies, i.e., strategies with a smooth
dependence in the unitary to be implemented, lead to exponential lower bounds.
This provides evidence for the existence of PV schemes that are _secure for
all practical purposes_ ;

  * •

finally, we consider the possibility of turning the previous bounds
unconditional. We relate the validity of this with a collection of open
problems in local Banach space theory. In particular, we relate the bounds on
resources to break our PV protocol with estimates for type constants of tensor
norms of $\ell_{2}$ spaces. In this direction, we put forward a conjecture
that would imply the desired unconditional exponential lower bounds and then
provide some evidence supporting it.

##### The protocol $G_{Rad}$.

To formalize this discussion, we propose a PV protocol that we denote
$G_{Rad}$. This makes reference to a family
$\\{G_{Rad}^{(n)}\\}_{n\in\mathbb{N}}$ rather than to a single task. The index
$n$ represents the security parameter and determines the size of the quantum
systems manipulated in the honest implementation of the protocol.

The general structure of a PV protocol in the studied setting – one-
dimensional PV – proceeds in four basic steps:

  1. 1.

The verifier prepares a bipartite system and distributes it to two verifying
agents that surrounds the location to be verified, $x$. For the sake of
concreteness, we locate these agents at points $x\pm\delta$ for some positive
$\delta$.

  2. 2.

Agents at $x\pm\delta$, when synchronized, communicate the registers they hold
to $x$.

  3. 3.

A honest prover located at $x$, upon receiving both registers, immediately
applies a required computation resulting in another bipartite system. The
latter has to be returned to locations $x\pm\delta$. One register should be
sent to the agent at the left of $x$ ($x-\delta$), and the other, to its right
($x+\delta$).

  4. 4.

Finally, the verifiers check whether prover’s answer arrives on time and
whether the computation was performed correctly. Based on this information
they declare the verification successful or not.

In the dishonest scenario, two cheaters surrounding the location $x$,
intercept the communication with the honest prover and try to emulate the
ideal action in the honest protocol. In order to succeed, they have to prevent
any delay in their response. This restricts cheaters’ action to consist of two
rounds of local operations mediated by a step of _simulatenous two-way
communication_ – see Section 2.2 for a detailed discussion of this model.

Once we have fixed this basic setting, let us describe the protocol $G_{Rad}$
involved in our main results. The honest implementation is as follows:

  1. 1.

Given a natural number $n$, in $G_{Rad}^{(n)}$ the verifier starts uniformly
sampling a vector of $n^{2}$ signs
$\varepsilon=(\varepsilon_{ij})_{i,j=1}^{n}$, where each
$\varepsilon_{ij}\in\\{\pm 1\\}$, and preparing the state
$|\psi\rangle:=\frac{1}{n}\sum_{i,j}|i\rangle_{A}\otimes|j\rangle_{B}\otimes|ij\rangle_{C}$
in a tripartite Hilbert space
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$. The agent at
$x-\delta$ receives registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ while
the one at $x+\delta$ is informed (classically) of the choice of
$\varepsilon$. Register $\mathcal{H}_{C}$ is kept as private during the
execution of the protocol.

  2. 2.

Then, registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ are forwarded to the
verifying location $x$ from its left. From the right, the classical
information about the choice of $\varepsilon$ is communicated.

  3. 3.

A honest prover located at $x$, upon receiving both pieces of information, has
to apply the diagonal unitary on $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
determined by $\varepsilon$. Immediately, registers
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ must be returned, but this time only
$\mathcal{H}_{A}$ should travel to the verifier at $x-\delta$. Register
$\mathcal{H}_{B}$ should be sent to the verifier at $x+\delta$.

  4. 4.

After receiving those registers, the verifiers check answer’s timing and, at
some later time, they perform the measurement
$\\{|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|,\mathrm{Id}-|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|\\}$
on system $\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$, where
$|\psi_{\varepsilon}\rangle:=\frac{1}{n}\sum_{i,j}\varepsilon_{ij}|i\rangle_{A}\otimes|j\rangle_{B}\otimes|ij\rangle_{C}$.
They accept the verification only if the arriving time was correct and the
outcome of the measurement was the one associated to
$|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|$.

Next, let us specify the implementation of $G_{Rad}^{(n)}$ in an adversarial
scenario. In this situation, we consider that two cheaters located between the
honest location $x$ and the verifying agents at $x\pm\delta$, intercepts the
communication in the honest protocol. In this work, we refer to these cheaters
as Alice, at position $x-\delta^{\prime}$, and Bob, at position
$x+\delta^{\prime}$, for some $0<\delta^{\prime}<\delta$. Their general action
proceeds as follows111 For simplicity, we state here the case in which Alice
and Bob use what we call _pure_ strategies. The most general case can be
reduced to this one by purification. See Section 3 for a detailed discussion.:
in advance, the cheaters share a state $|\varphi\rangle$ in which Bob, after
receiving the information about $\varepsilon$, applies an isometry
$W_{\varepsilon}$ and sends part of the resulting system to Alice together
with the classical information determining $\varepsilon$. On her part, when
Alice receives registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ of
$|\psi\rangle$, she applies another isometry $V$ (independent of
$\varepsilon$) on these registers and her part of the shared state
$|\varphi\rangle$. Part of her resulting system is communicated to Bob. After
this step of simultaneous two-way communication Alice and Bob are allowed to
apply another pair of local isometries
$\tilde{V}_{\varepsilon}\otimes\tilde{W}_{\varepsilon}$ on the systems they
hold. Then, they have to forward an answer to agents at $x\pm\delta$.

##### Main results.

The structure of $G_{Rad}$ allows us to understand cheating strategies as
vector valued assignments on the $n^{2}$-dimensional boolean hypercube,
$\mathcal{Q}_{n^{2}}=\\{\pm 1\\}^{n^{2}}$. In our main result, we find lower
bounds for the resources consumed in such an attack depending on the
_regularity_ of the former assignment. Very informally, we can state:

Cheating strategies depending on the value of $\varepsilon\in\\{\pm
1\\}^{n^{2}}$ in a sufficiently regular way require an amount of entanglement
exponential in $n$ in order to pass $G_{Rad}^{(n)}$ .

To quantify the regularity of a strategy we introduce a parameter $\sigma$
that can be regarded as a measure of the _total influence_ of the associated
function on the Boolean hypercube. We give a precise definition for this
parameter in Section 4. Here, we restrict ourselves to give an intuitive idea
behind this definition presenting some approximate expressions below. Based on
two complementary ideas, given a strategy we construct two different
assignments leading to two parameters $\sigma^{i}_{\mathcal{S}}$ and
$\sigma^{ii}_{\mathcal{S}}$. The subscript $\mathcal{S}$ makes reference to
the strategy we started with. According to the previous discussion, any such
strategy can be characterized by a sequence of elements
$\mathcal{S}=\\{\tilde{V}_{\varepsilon},\tilde{W}_{\varepsilon},V,W_{\varepsilon},|\varphi\rangle\\}_{\varepsilon\in\mathcal{Q}_{n^{2}}}$.
With that, we can bound, up to logarithmic factors:

$\sigma^{i}_{\mathcal{S}}\lesssim_{\log}\ \mathbb{E}_{\varepsilon}\
\left(\sum_{i,j}\frac{1}{2}\big{\|}\tilde{V}_{\varepsilon}\otimes\tilde{W}_{\varepsilon}-\tilde{V}_{\overline{\varepsilon}^{ij}}\otimes\tilde{W}_{\overline{\varepsilon}^{ij}}\big{\|}^{2}\right)^{1/2}+O\left(\frac{1}{n}\right),$

$\sigma^{ii}_{\mathcal{S}}\lesssim_{\log}\ \mathbb{E}_{\varepsilon}\
\left(\sum_{i,j}\frac{1}{2}\big{\|}\left(V\otimes(W_{\varepsilon}-W_{\overline{\varepsilon}^{ij}})\right)|\varphi\rangle\big{\|}_{\ell_{2}}^{2}\right)^{1/2}+O\left(\frac{1}{n}\right).$

Here, $\overline{\varepsilon}^{ij}$ denotes the sign vector
$(\varepsilon_{11},\ldots,$$-\varepsilon_{ij},$$\ldots,$ $\varepsilon_{nn})$.
The first of these parameters is therefore related with how strongly the
_second round of local operations_ in the strategy depends on $\varepsilon$.
In the other hand, $\sigma^{ii}_{\mathcal{S}}$ is similarly concerned with the
dependence on $\varepsilon$ of the _first round of local operations_. With
this at hand, we can state – yet informally – our main result. Denoting the
success probability attained by a strategy $\mathcal{S}$ in $G_{Rad}^{(n)}$ as
$\omega(G_{Rad}^{(n)};\mathcal{S})$, we can say that:

######  Theorem 1.1 (Informal).

Given a cheating strategy for $G_{Rad}^{(n)}$, $\mathcal{S}$, using quantum
resources of local dimension $k$,

  1. I.

$\omega(G_{Rad}^{(n)};\mathcal{S})\leq C_{1}+C_{2}\
{\sigma^{i}_{\mathcal{S}}}\,\log^{1/2}(k)+O\left(\frac{1}{n^{1/2}}\right);$

  2. II.

$\displaystyle\omega(G_{Rad}^{(n)};\mathcal{S})$
$\displaystyle\quad\leq\tilde{C}_{1}+C_{3}\
\sigma^{ii}_{\mathcal{S}}\,n^{3/4}\log^{3/2}(nk)+O\left(\frac{1}{n^{1/2}}+\frac{\log^{3/2}(nk)}{n}\right);$

where $C_{1},\,\tilde{C}_{1}<1,\,C_{2},\,C_{3}$ are positive constants.

What this theorem tells us is that cheating strategies for $G_{Rad}$ for which
$\sigma^{i}_{\mathcal{S}}$ or $\sigma^{ii}_{\mathcal{S}}$ are small enough
necessarily need to make use of quantum resources of size exponential in a
power of $n$, (loosely) matching the exponential entanglement consumption of
known attacks222 The attack from [1] requires an entangled system of dimension
$O(\exp(n^{4}))$, that is still much larger than our bounds for smooth
strategies. Nonetheless, we consider any strategy using quantum systems of
dimension exponential in a power of $n$ to be infeasible for _all practical
purposes_. This is our main motivation in this work. . We give a more concrete
statement in the form of a corollary:

######  Corollary 1.2 (Informal).

Consider a cheating strategy for $G_{Rad}^{(n)}$, $\mathcal{S}$, attaining
value $\omega(G_{Rad};\mathcal{S})$ $\geq 1-\epsilon$ for some
$0\leq\epsilon\leq\frac{1}{8}$. Denote by $k$ the local dimension of the
quantum resources used in $\mathcal{S}$.

If $\sigma^{i}_{\mathcal{S}}=O(\mathrm{polylog}(n)/n^{\alpha})$ or
$\sigma^{ii}_{\mathcal{S}}=O(\mathrm{polylog}(n)/n^{3/4+\alpha})$ for some
$\alpha>0$, then:

$k=\Omega\big{(}\exp\big{(}n^{\alpha^{\prime}}\big{)}\big{)}\quad\text{for
some }\alpha^{\prime}>0.$

As we see, the regularity parameters $\sigma^{i(ii)}_{\mathcal{S}}$ play a key
role in these results. We notice that known attacks in [4, 1] in fact fulfil
the hypothesis of the previous corollary: the second round of local operations
in these attacks is $\varepsilon$-independent, hence
$\sigma^{i}_{\mathcal{S}}\sim\log(n)/n$. However, we do not known how generic
this behaviour is. More generally, it turns out that from any Programmable
Quantum Processor [31] – as the already considered protocol of Port Based
Teleportation, for example – with the capability of implementing the diagonal
unitaries required in $G_{Rad}^{(n)}$, we can construct an assignment $\Phi$
fulfilling Theorem 1.1 with regularity parameter again of order
$\sigma^{i}_{\Phi}\sim\log(n)/n$. Therefore, Corollary 1.2 also applies to
this broader case allowing to recover some of the results obtained in [24].
This is not a coincidence, our approach here builds on ideas introduced in
this previous work.

Turning our attention towards $\sigma^{ii}_{\mathcal{S}}$, a trivial example
of a family of _smooth_ attacks for which
$\sigma^{ii}_{\mathcal{S}}\sim\log(n)/n$ is given by cheaters sharing no
entanglement in advance – even when entanglement can be created in the first
round of local operations and distributed for the second round. On the
contrary, we can also easily compute $\sigma^{ii}_{\mathcal{S}}$ for the
attack in [1] obtaining $\sigma^{ii}_{\mathcal{S}}\geq O(1)$. Therefore, our
second item in Theorem 1.1 is not able to predict good lower bounds for this
case. Still, we think that this second item might be useful for restricting
the structure of possible attacks to PV, especially in conjunction with the
first part of the theorem.

More importantly, the second part of Theorem 1.1 leads us to put forward the
possibility of an unconditional lower bound for $k$, i.e., a bound in the
spirit of Corollary 1.2 but dropping out the assumptions regarding
$\sigma^{i(ii)}_{\mathcal{S}}$. Even when we were not able to prove such a
bound, we relate its validity with a conjecture about the geometry of some
Banach spaces. The positive resolution of this conjecture would prove our
scheme $G_{Rad}$ _secure for all practical purposes_. More concretely, our
conjecture has to do with estimates of type constants of tensor norms on
finite dimensional Hilbert spaces. Even when these constructions are
relatively simple and well known in the theory of Banach spaces, there are
long-standing open questions about the type of these kind of spaces. E.g., the
type-2 constant of the simple space
$\ell_{2}^{n}\otimes_{\varepsilon}\ell_{2}^{n}\otimes_{\varepsilon}\ell_{2}^{n}$
is still poorly understood. In fact, the related cotype-2 constant of its dual
is a famous open question asked by Pisier decades ago – see, for instance,
[36]. Once we formally state the conjecture, we provide some computation
supporting it. We analyze the most direct approaches to disprove the
conjectured statement computing the type constants of some subspaces and
giving some volume ratio estimates. This might have interesting ramifications
on the still not completely understood relation between volume ratio and
cotype of Banach spaces.

###  1.2 Proof sketch

Here we sketch the main ideas behind the proof of Theorem 1.1. These ideas are
also at the bottom of the constructions that allow us to establish the more
general connection between Question 1 and type constants leading to the
conjecture indicated above.

As we have already anticipated, the starting point of our study is the
identification of each cheating strategy to $G_{Rad}^{(n)}$, $\mathcal{S}$,
with a vector-valued function
$\Phi_{\mathcal{S}}:\mathcal{Q}_{n^{2}}\rightarrow X$, being $X$ a suitable
Banach space. With a clever definition of $\Phi_{\mathcal{S}}$ we can obtain a
bound to the success probability $\omega(G_{Rad},\mathcal{S})$ in terms of the
average norm of the image of that function. We obtain bounds of the following
kind:

$\omega(G_{Rad};\mathcal{S})\leq\,\mathbb{E}_{\varepsilon}\,\big{\|}\Phi_{\mathcal{S}}(\varepsilon)\big{\|}_{X},$

where $\varepsilon$ are taken uniformly distributed in $\mathcal{Q}_{n^{2}}$.
Therefore, the key quantity we study is precisely
$\mathbb{E}_{\varepsilon}\,\big{\|}\Phi_{\mathcal{S}}(\varepsilon)\big{\|}_{X}$.
For that, we bring together two main ingredients. On one hand, a Sobolev-type
inequality of Pisier for vector-valued function on the Boolean cube, and, on
the other, the type-2 constant of the Banach space $X$, $\mathrm{T}_{2}(X)$.
The combination of these two tools provides us with an inequality:

$\mathbb{E}_{\varepsilon}\big{\|}\Phi_{\mathcal{S}}(\varepsilon)\big{\|}_{X}\leq\big{\|}\mathbb{E}_{\varepsilon}\Phi(\varepsilon)\big{\|}_{X}+C\
\sigma_{\Phi_{\mathcal{S}}}\ \mathrm{T}_{2}(X),$ (1)

where $C$ is an independent constant and $\sigma_{\Phi_{\mathcal{S}}}$ is a
regularity measure for $\Phi_{\mathcal{S}}$333 See Section 2.4.4 for a
detailed discussion. There, the more refined type-2 constant with $m$ vectors
is considered, see Corollary 2.24. For the sake of simplicity, we consider the
plain type-2 constant in this introductory section.. Specific choices for
$\Phi_{\mathcal{S}}$ and $X$ leads to parameters
$\sigma^{i(ii)}_{\mathcal{S}}$ appearing in Theorem 1.1.

Now, depending on how $\Phi_{\mathcal{S}}$ is constructed, we are able to
upper bound $\|\mathbb{E}_{\varepsilon}\Phi(\varepsilon)\big{\|}_{X}$ – see,
for instance, Proposition 4.6 – so we can focus on the second term in the RHS
of (1).

To obtain Theorem 1.1 we propose in Section 4 two possible choices for
$\Phi_{\mathcal{S}}$ and study the type constants of their image spaces.
Furthermore, in order to remove the dependence on $\sigma$ in the bounds
obtained in that way, we propose in Section 5 yet another choice for
$\Phi_{\mathcal{S}}$. This third function is regular enough by construction
allowing to obtain bounds depending only on the dimension of the system used
by the cheaters. The downside of this latter approach is that the space $X$ in
this last case becomes more involved and its type properties cannot be
estimated with the techniques at our disposal.

To finish this introduction we sum up the structure of the paper: we start
introducing in Section 2 preliminary material needed to develop this work.
Then, in Section 3 we introduce in complete detail the setting studied here
and the PV scheme $G_{Rad}$. The analysis of strategies for this scheme
leading to Theorem 1.1 is presented in Section 4. In Section 5 we discuss the
possibility of pushing forward the techniques presented in this work to obtain
unconditional lower bounds on the resources required by the cheaters, only
dependent on the dimension of the quantum system they manipulate. We connect
this question with the problem in local Banach space theory of obtaining
precise estimates for the _type constants_ of particular Banach spaces. After
establishing that connection in a precise and rigorous way, we provide some
calculations supporting a positive resolution of a conjecture that would lead
to the security _for all practical purposes_ of $G_{Rad}$. The paper ends with
a discussion of the results presented and possible directions for future work.
This corresponds to Section 6.

##  2 Preliminaries

###  2.1 Notation

In order to simplify the presentation, we use symbols $\approx$ and $\lesssim$
to denote equality and inequality up to multiplicative dimension independent
constants and $\approx_{\log}$ and $\lesssim_{\log}$, equality and inequality
up to multiplicative logarithmic factors on the dimensions involved.

The quantum mechanical description of a system is based on an underlying
complex Hilbert space, that we denote
$\mathcal{H},\,\mathcal{H}^{\prime},\,\mathcal{H}_{A},\,\mathcal{H}_{B},\,\ldots$.
When the dimension is known to be a specific natural number, say $n$, we use
the notation $\ell_{2}^{n}$. Given that, a density matrix is a trace one,
positive operator $\rho:\mathcal{H}\rightarrow\mathcal{H}$. We denote the set
of density matrices as $\mathcal{D}(\mathcal{H})$. Quantum operations are
completely positive trace preserving linear maps
$\mathcal{D}(\mathcal{H})\rightarrow\mathcal{D}(\mathcal{H}^{\prime})$. The
set of these maps is denoted here as
$\mathrm{CPTP}(\mathcal{H},\mathcal{H}^{\prime})$ or simply
$\mathrm{CPTP}(\mathcal{H})$ when the input and output spaces are the same.
The operation of discarding a subsystem is implemented by the partial trace.
We specify the subsystem discarded by its underlying Hilbert space, e.g., in a
composed system with underlying Hilbert space
$\mathcal{H}\otimes\mathcal{H}^{\prime}$ the operation of discarding
$\mathcal{H}^{\prime}$ is denoted
$\mathrm{Tr}_{\mathcal{H}^{\prime}}\in\mathrm{CPTP}(\mathcal{H}\otimes\mathcal{H}^{\prime},\mathcal{H})$.
To describe the evolution of a quantum system after a measurement, we make use
of _instruments_ , that are collections of completely positive trace non-
increasing maps summing up to a trace preserving map. To denote a completely
positive (maybe non trace-preserving) map we use the symbol $\mathrm{CP}$
instead of the previous $\mathrm{CPTP}$. The set of instruments composed by
finite collections of maps in $\mathrm{CP}(\mathcal{H},\mathcal{H}^{\prime})$
are denoted $\mathrm{Ins}(\mathcal{H},\mathcal{H}^{\prime})$.

To denote Banach spaces we usually use letters $X,\,Y,\,\ldots$ and
$X^{*},\,Y^{*},\,\ldots$ for the corresponding Banach duals. $B_{X}$ denotes
the unit ball of a Banach space $X$. $\mathcal{B}(X,Y)$ is the space of linear
operators between arbitrary Banach spaces $X$ and $Y$, while $\ell_{p}(X)$ and
$L_{p}(X)$, with $p\in(0,\infty]$, are the classical (vector valued) spaces of
$p-$summable sequences and $p-$integrable functions on the unit interval. More
specifically, we also fix now the notation for two Banach spaces that will
appear repeatedly. Given two Hilbert spaces $\mathcal{H}$,
$\mathcal{H}^{\prime}$, we denote as
$\mathcal{B}(\mathcal{H},\mathcal{H}^{\prime})$ and
$\mathcal{S}_{1}(\mathcal{H},\mathcal{H}^{\prime})$ the space of bounded and
trace class operators from $\mathcal{H}$ into $\mathcal{H}^{\prime}$,
respectively. In the finite dimensional case, $\mathcal{H}=\ell_{2}^{m}$,
$\mathcal{H}^{\prime}=\ell_{2}^{n}$, we simplify this notation to $M_{n,m}$
and $\mathcal{S}_{1}^{n,m}$ ($M_{n}$, $\mathcal{S}_{1}^{n}$ when $n=m$). To
denote elements of the computational basis we use the quantum information
oriented convention of using the symbols $|i\rangle,\,\langle
i|,\,|j\rangle,\,\ldots$. When working with elements in the complex vector
space composed by $n\times m$ matrices – as is the case of elements in
$M_{n,m}$ or $\mathcal{S}^{n,m}$, case we consider repeatedly below – the
usual basis of matrices with only one non-zero entry is denoted here as
$\\{|i\rangle\langle j|\\}_{\begin{subarray}{l}i=1,\ldots,n\\\
j=1,\ldots,m\end{subarray}}$. Observing the range of each subindex, the
convention chosen here matches the standard agreement on regarding _kets_
$|i\rangle$ as column vectors and _bras_ $\langle i|$ as rows.

###  2.2 Position Based Cryptography in 1-D

The major aim of this work is to make progress towards Question 1. For that,
we restrict ourselves to the simplest scenario: position verification in 1-D.
In this situation, we restrict the world to a line in which we consider a
preferred location, $x$ – the position to be verified. The verifier, composed
by two agents, $V_{A}$ and $V_{B}$, is located around the honest position $x$.
Let us consider $V_{A}$ in position $x-\delta$ and $V_{B}$ in position
$x+\delta$. Then, $V_{A}$ and $V_{B}$ perform an interactive protocol sending
in the direction of $x$ (possibly quantum) messages. These messages arrive to
$x$ at the same time, so that a honest prover located at $x$ could receive
them and, accordingly, generate answers for $V_{A}$ and $V_{B}$. The verifier
accept the verification if and only if

  * •

(correctness) the answers are correct with respect to verifier’s messages
(according to some public rule);

  * •

(timeliness) the answers arrive on time to the locations of $V_{A}$ and
$V_{B}$. Assuming that the signals between verifier and prover travels at some
known velocity $c$, the answers should arrive to $V_{A}$ and $V_{B}$ at time
$2\delta c$ after the start of the protocol.

Before continuing, let us set a generic structure for such a protocol. To
prepare the messages $V_{A}$ and $V_{B}$ must forward, the verifier prepares a
(publicly known) state in a composite system with some underlying Hilbert
space $\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$. That is,
he prepares a density matrix $\rho_{0}$ on that state space and sends the
register $\mathcal{H}_{A}$ to $V_{A}$ and $\mathcal{H}_{B}$ to $V_{B}$.
$\mathcal{H}_{C}$ is considered to take into account the possibility that the
verifier keeps some part of the initial system as private during the protocol.
Then, $V_{A}$ and $V_{B}$ send their systems in the direction of $x$. Now, the
agent(s) interacting in the middle with $V_{A}$ and $V_{B}$ apply some quantum
operation on the communicated system $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
obtaining as output another state
$\rho_{ans}\in\mathcal{D}(\mathcal{H}_{A}^{\prime}\otimes\mathcal{H}_{B}^{\prime})$.
The subsystems $\mathcal{H}_{A}^{\prime}$, $\mathcal{H}_{B}^{\prime}$ are
forwarded to $V_{A}$, $V_{B}$, respectively. To decide whether the
verification is correct or not, the verifier first check the _timeliness_
condition is fulfilled and then performs a (publicly known) dichotomic
measurement on the system
$\mathcal{H}_{A}^{\prime}\otimes\mathcal{H}_{B}^{\prime}\otimes\mathcal{H}_{C}$.

######  Remark 2.1.

Above, $\rho_{0}$ and $\rho_{ans}$ are in general quantum states but they
could perfectly describe also classical messages as well as quantum-classical
messages. This will be indeed the case in the concrete scheme analized in this
work.

######  Remark 2.2.

Note that a honest prover, that is, an agent at position $x$, shouldn’t have
any problem to pass the test: at time $\delta c$ he would receive the whole
system $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ from the verifiers, having the
capability to perform any global operation on it to prepare his answer. This
answer can still arrive on time to $V_{A}$ and $V_{B}$. The depicted prover’s
action is the most general operation that can be performed on verifier’s
messages, which are the only information transmitted in the protocol.
Therefore, if the challenge is well designed (it can be passed), the honest
prover must be able to succeed at it444 We don’t take into account here the
computational limitations at which the agents might be subjected..

Next, let us focus on how the general protocol described above can be cheated.
In order to impersonate the identity of a honest prover at position $x$, a
couple of adversaries, Alice and Bob, at positions $x\pm\delta^{\prime}$,
$0<\delta^{\prime}<\delta$, can intercept the message systems
$\mathcal{H}_{A}$, $\mathcal{H}_{B}$, interact between themselves to generate
answers for the verifier and forward those answers in correct timing. In order
to respect the timeliness of the protocol, the most general action of the
cheaters proceeds as follows:

1. Before the start of the protocol, Alice and Bob prepare some shared entangled state in a private register $\mathcal{H}_{A_{E}}\otimes\mathcal{H}_{B_{E}}$; 2. Alice receives question register $\mathcal{H}_{A}$ and applies a quantum channel $\mathcal{A}\in\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{A_{E}},\,\mathcal{H}_{A\shortrightarrow B}\otimes\mathcal{H}_{A\shortrightarrow A})$. Similarly, Bob receives $\mathcal{H}_{B}$ and applies $\mathcal{B}\in\mathrm{CPTP}(\mathcal{H}_{B}\otimes\mathcal{H}_{B_{E}},\,\mathcal{H}_{B\shortrightarrow A}\otimes\mathcal{H}_{B\shortrightarrow B})$; 3. the cheaters interchange registers $\mathcal{H}_{A\shortrightarrow B}$ and $\mathcal{H}_{B\shortrightarrow B}$, keeping $\mathcal{H}_{A\shortrightarrow A}$, $\mathcal{H}_{B\shortrightarrow B}$555 In general, we model in that way any kind of communication between Alice and Bob, classical or quantum. However, in the particular setting studied later on in Section 3, we will see that the dimension of $\mathcal{H}_{A\shortrightarrow B}$ and $\mathcal{H}_{B\shortrightarrow B}$ is essentially determined by the quantum resources the cheaters share, allowing us to disregard the classical communication that they might additionally use. See Section 3, Lemma 3.1, for a precise statement.; 4. after this last step, Alice holds system $\mathcal{H}_{A\shortrightarrow A}\otimes\mathcal{H}_{B\shortrightarrow A}$, in which she applies another channel $\tilde{\mathcal{A}}\in\mathrm{CPTP}(\mathcal{H}_{A\shortrightarrow A}\otimes\mathcal{H}_{B\shortrightarrow A},\,\mathcal{H}_{A}^{\prime})$. Similarly, Bob applies $\tilde{\mathcal{B}}\in\mathrm{CPTP}(\mathcal{H}_{B\shortrightarrow B}\otimes\mathcal{H}_{A\shortrightarrow B},\,\mathcal{H}_{B}^{\prime})$; 5. finally, Alice sends $\mathcal{H}_{A}^{\prime}$ to $V_{A}$ and Bob $\mathcal{H}_{B}^{\prime}$ to $V_{B}$.

Figure 1:  Structure of adversarial action attacking 1-D PV schemes.

We call in this work _simultaneous two-way communication scenario_ , $s2w$,
the set of actions – strategies from now on – with this structure. This
scenario is central for us and will appear repeatedly in the rest of this
manuscript.

###  2.3 One-round Quantum games

Our approach starts rephrasing the scheme presented in the previous section in
the framework of cooperative _quantum games_ , a generalization of nonlocal
games. For the purpose of this manuscript it is enough to restrict ourselves
to the case of two-player quantum games. In this setting, two players, Alice
and Bob, interact with a referee receiving from him a bipartite quantum state.
Acting on the received system, Alice and Bob obtain another bipartite state
which is communicated back to the referee who checks the validity of player’s
answer performing a measurement. The parallelism with the situation of a team
of cheaters attacking a 1-D PV scheme is now obvious, we just have to identify
the players with the cheaters, the referee with the verifier and the
definition of the game (which question state the referee prepares and which
measurement he applies at the end of the game) with the definition of the test
to be passed in a given PV protocol.

Quantum games have appeared naturally in quantum information theory in several
places and some specific classes of quantum games were rigorously defined and
studied in [13, 40, 8, 21]. Indeed, our starting point is one of these latest
notions. In the rest of this section we introduce rank one quantum games,
originally defined in [13], and present a slight generalization that we call
_mixed_ rank-one quantum games. This is precisely the setting in which we
develop this work.

A (two-player one-round) rank-one quantum game, ROQG, is specified by:

  1. 1.

a tripartite Hilbert space
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$;

  2. 2.

and unit vectors $|\psi\rangle$, $|\gamma\rangle$
$\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$.

The game then proceeds as follows:

  * •

the referee starts preparing the state
$|\psi\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$
and sends registers $\mathcal{H}_{A}$, $\mathcal{H}_{B}$ to Alice and Bob,
respectively;

  * •

the players apply an allowed quantum operation666 The action of the players
might be constrained for physical or other reasons forbidding Alice and Bob to
apply a completely general quantum channel. Below we state these limitations
in more detail.  on the received registers, $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$, sending them back to the referee;

  * •

finally, to decide whether the players win or lose the game, the referee
performs the projective measurement given by elements
$\\{|\gamma\rangle\langle\gamma|,\mathrm{Id}-|\gamma\rangle\langle\gamma|\\}$.
When the outcome of this measurement is the one associated to
$|\gamma\rangle\langle\gamma|$, the referee declares Alice and Bob winning.
Otherwise they lose.

We give now a formal definition for this type of games (see [13] for further
details):

######  Definition 2.3.

We identify a rank-one quantum game, $G$, with a tensor
$\hat{G}=\mathrm{Tr}_{\mathcal{H}_{C}}|\psi\rangle\langle\gamma|\in
B_{\mathcal{S}_{1}(\mathcal{H}_{AB})}$.

A strategy for $G$ is a quantum channel $\mathcal{S}$ acting on the system
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ shared with the players by the
referee. That is,
$\mathcal{S}\in\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$. The
value achieved by this strategy is defined by:

$\displaystyle\omega(G;\mathcal{S})$
$\displaystyle:=\mathrm{Tr}\left[\>|\gamma\rangle\langle\gamma|\>\,\>(\mathrm{Id}_{C}\otimes\mathcal{S})\>\big{(}|\psi\rangle\langle\psi|\big{)}\>\right],$
(2)

and corresponds with the winning probability achieved in the game described
above when the players use $\mathcal{S}$ to play.

In general, not any quantum operation will be considered to be an allowed
strategy, since the actions of Alice and Bob might be restricted in a given
situation. For example, one can consider situations in which Alice and Bob are
spatially isolated so they cannot communicate between themselves. In this work
we consider situations in which Alice and Bob are restricted to apply
operations in the form of Figure 1. We study this setting in detail in Section
3. Until then, we refer as _scenarios_ to sets of allowed strategies, which
will be usually motivated by physical constraints on the players.

######  Definition 2.4.

In a particular scenario
$\mathfrak{S}\subseteq\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$,
the value of the game is:

$\omega_{\mathfrak{S}}(G):=\sup_{\begin{subarray}{c}\mathcal{S}\in\mathfrak{S}\end{subarray}}\omega_{\mathfrak{S}}\left(G;\mathcal{S}\right).$
(3)

######  Example 2.5 (The honest scenario).

In this preliminary section we only introduce the simplest scenario, the one
in which we allow any quantum channel on
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ to be a valid strategy. That is, in
this scenario, the set of allowed strategies is
$\mathfrak{S}=\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$. This
corresponds to the case in which Alice and Bob are allowed to apply any global
operation, so they perform as if they were a single agent with access to the
full question in the game. We refer to this situation as the _honest
scenario_.

######  Definition 2.6.

The Honest value of $G$ is given by:

$\omega_{H}(G)=\sup_{\mathcal{S}\in\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})}\omega(G;\mathcal{S}).$
(4)

As suggested by the nomenclature we use, this scenario is related with the
action of a honest prover in a PV setting. Furthermore, it also serves as a
normalization for the game, since it is the largest value achievable under the
unique assumption that quantum mechanics is the underlying model explaining
players’ behaviour.

######  Remark 2.7.

It turns out that the supremum in (4) can be restricted to unitary channels
without altering its value, see [13, Theorem 3.2, 3.]. In this case, we can
work out (4) to obtain the following equivalent expression:

$\displaystyle\omega_{H}(G)$
$\displaystyle=\sup_{U\in\mathcal{B}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})}\omega(G;U(\,\cdot,\,)U^{\dagger})=\sup_{U\in\mathcal{B}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})}\left(\mathrm{Tr}(\hat{G}\,U)\right)^{2}$
$\displaystyle\equiv\sup_{U\in\mathcal{B}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})}\langle
U,\hat{G}\rangle^{2}=\|\hat{G}\|^{2}_{\mathcal{S}_{1}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})}.$
(5)

Indeed, by compactness, this supremum is achieved by some unitary $U_{G}$,
that can be interpreted as the ideal action players have to perform to
maximize their chances to win the game. This gives us a useful interpretation
of rank-one quantum games: Alice and Bob have to simulate the application of a
given unitary, $U_{G}$, on registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
of the system $\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$
prepared on the initial state $|\psi\rangle$. Restricting the action of the
players to the s2w model of Figure 1, this is just the _instantaneous non-
local computation_ of $U_{G}$.

To complete this section, we introduce in the notion of _mixed rank-one
quantum games_. These games are constructed from a family of rank-one quantum
games, say $\\{G_{t_{a},t_{b}}\\}_{t_{a},t_{b}}$, indexed by
$t_{a}\in\mathcal{T}_{A}$, $t_{b}\in\mathcal{T}_{B}$, together with a
probability distribution $\\{p_{t_{a},t_{b}}\\}_{t_{a},t_{b}}$777 For each
$t_{a}$ $t_{b}$, $p_{t_{a},t_{b}}\geq 0$ and
$\sum_{t_{a},t_{b}}p_{t_{a},t_{b}}=1$. We restrict ourselves to finite index
sets $\mathcal{T}_{A}$, $\mathcal{T}_{B}$.. For the sake of readability, we
refer to pairs $(t_{a},t_{b})$ by $\mathbf{t}$, so that
$\mathbf{t}\in\mathcal{T}_{A}\times\mathcal{T}_{B}$. The game proceeds as
follows:

  * •

The referee chooses randomly one of the ROQG, $G_{\mathbf{t}}$, according to
the probability distribution $p_{\mathbf{t}}$.

  * •

The referee prepares the state corresponding to the game $G_{\mathbf{t}}$. He
sends to Alice and Bob a quantum system as specified by the ROQG
$G_{\mathbf{t}}$ together with the classical information $\mathbf{t}$. Alice
receives $t_{a}$ and Bob $t_{b}$ – recall that $\mathbf{t}=(t_{a},t_{b})$;

  * •

Alice and Bob, with the information they received, prepares a state to answer
the referee;

  * •

finally, with the state communicated by Alice and Bob, the referee performs
the final measurement defined in $G_{\mathbf{t}}$. This decides whether the
players win or lose.

Once we introduced this family of games, we now give a formal definition:

######  Definition 2.8.

We identify a mixed rank-one quantum game (MROQG), $G$, with a sequence of
tensors
$\big{\\{}\hat{G}_{\mathbf{t}}=\mathrm{Tr}_{C}|\psi_{\mathbf{t}}\rangle\langle\gamma_{\mathbf{t}}|\big{\\}}_{\mathbf{t}}$,
where each $G_{\mathbf{t}}\in B_{\mathcal{S}_{1}(\mathcal{H}_{AB})}$, together
with a probability distribution $\\{p_{\mathbf{t}}\\}_{\mathbf{t}}$.

A strategy for $G$ is a sequence of quantum channels
$\\{\mathcal{S}_{\mathbf{t}}\\}_{\mathbf{t}}$ acting on the system
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ shared with the players by the
referee. The value achieved by this strategy is defined by:

$\displaystyle\omega(G;\\{\mathcal{S}_{\mathbf{t}}\\}_{\mathbf{t}})$
$\displaystyle:=\mathbb{E}_{\mathbf{t}}\
\mathrm{Tr}\left[\>|\gamma_{\mathbf{t}}\rangle\langle\gamma_{\mathbf{t}}|\>\,\>(\mathrm{Id}_{C}\otimes\mathcal{S}_{\mathbf{t}})\>\big{(}|\psi_{\mathbf{t}}\rangle\langle\psi_{\mathbf{t}}|\big{)}\>\right],$
(6)

where $\mathbb{E}_{\mathbf{t}}$ denotes the expectation over the random
variable $\mathbf{t}$ distributed according to
$\\{p_{\mathbf{t}}\\}_{\mathbf{t}}$.

As in the previous discussion, we also consider restricted families of allowed
strategies for MROQGs, that is, subsets
$\mathfrak{S}\subseteq\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})^{\times|\mathrm{T}_{\mathcal{A}}\times\mathrm{T}_{B}|}$.
This leads to the value of a MROQG in a given scenario:

######  Definition 2.9.

In a particular scenario
$\mathfrak{S}\subseteq\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})^{\times|\mathrm{T}_{\mathcal{A}}\times\mathrm{T}_{B}|}$,
the value of the game is:

$\omega_{\mathfrak{S}}(G):=\sup_{\begin{subarray}{c}\mathcal{S}\in\mathfrak{S}\end{subarray}}\omega_{\mathfrak{S}}\left(G;\mathcal{S}\right).$
(7)

As commented before, we are interested in the scenario resulting from the
restrictions in Figure 1, but we leave the study of this situation for
forthcoming sections. Matching our earlier discussion on ROQGs, we also
comment that the _honest_ scenario is recovered considering any strategy as
valid, that is, setting
$\mathfrak{S}=\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})^{\times|\mathrm{T}_{\mathcal{A}}\times\mathrm{T}_{B}|}$.
This leads to define $\omega_{H}(G)$ for a MROQG in analogy with (4). With
similar computations as in Remark 2.7 we can obtain:

$\omega_{H}(G)=\,\mathbb{E}_{\mathbf{t}}\,\|G_{\mathbf{t}}\|^{2}_{\mathcal{S}^{AB}_{1}}.$

Formally, this equation perfectly matches the idea of MROQGs as distributions
of ROQGs.

######  Remark 2.10.

From now on we further restrict the games considered here. In Section 3 we
study a concrete MROQG in which:

  1. 1.

$\mathcal{T}_{A}$ is trivial so the information about the ROQG played in each
instance is completely given to Bob – the game is completely determined by
$t_{b}\in\mathcal{T}_{B}$.

  2. 2.

The quantum part of the input is entirely given to Alice. Even though, we will
still denote the question register as $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$,
since in the last phase of the game, both players have to answer the referee
with a quantum register, ideally Alice answers $\mathcal{H}_{A}$ and Bob
$\mathcal{H}_{B}$.

To sum up, in the kind of MROQGs we are going to work with, after the first
communication between the referee and the players, Bob is aware of the ROQG
chosen by the referee, $G_{t_{b}}$, but is Alice who has the input to this
game. In order to win, Alice and Bob have to interact such that at the end of
their action each of the players holds the register that has to give back to
the referee. The challenge is that Alice, when holding the whole quantum part
of the input, does not know which ROQG she has to play. We come back to this
point in Section 3, where we introduce in detail the specific game analized in
this work.

###  2.4 Banach spaces, operator ideals and type constants

At a technical level, the results of this work follow from the study of Banach
spaces formed by tensor products of Hilbert spaces. The spaces $M_{n,m}$ and
its dual, $\mathcal{S}_{1}^{n,m}$, play a prominent role in the rest of the
manuscript. Properties of these spaces in conjunction with a classical
Sobolev-type inequality of Pisier allow us to obtain our main result, Theorem
1.1.

The key property we study of these spaces are type constants, that we
introduce in Section 2.4.3. Before that, we need to introduce some objects we
work with in the following sections.

####  2.4.1 Operator ideals

A deeper understanding of the constructions appearing in this work is provided
by the perspective of the theory of operator ideals. For the reader’s
convenience, we first sum up the contents of this section: given two finite-
dimensional888 Even though in most cases the following material also applies
in the infinite-dimensional case, for simplicity, we restrict to finite
dimension that is all we will use here. This allows us to use the equivalence
between operators and tensor products in a comfortable way ignoring the
subtleties that appear at this point for infinite dimension. Banach spaces $X$
and $Y$ we consider the space of linear operators from $X$ into $Y$,
$\mathcal{B}(X,Y)$. An operator ideal is essentially an assignment of any pair
of Banach spaces $X$ and $Y$ with a subset of $\mathcal{B}(X,Y)$ that has the
_ideal_ property of being closed under composition with bounded linear maps.
We provide [32, 14] as standard references on this matter for the interested
reader. In this section:

  1. 1.

The first examples of operator ideals we introduce are _tensor norms_ on pairs
of Banach spaces. This includes the space of bounded operators,
$\mathcal{B}(X^{*},Y)$, or $X\otimes_{\varepsilon}Y$ in tensor norm notation,
2-summing operators $\pi_{2}(X^{*},Y)$, or $X\otimes_{\pi_{2}}Y$, and the
ideal of nuclear operators, denoted as $\mathcal{N}(X^{*},Y)$, or
$X\otimes_{\pi}Y$999 Recall that here we restrict $X$ and $Y$ to be finite
dimensional..

  2. 2.

When $X$ and $Y$ are Hilbert spaces, another prominent family of operator
ideals are the well-known Schatten classes $\mathcal{S}_{p}$, for
$p\in[1,\infty]$. It turns out that these classes can be generalized to
operators between arbitrary Banach spaces, leading to the definition of weak
Schatten von-Neumman operators of type $p\in[1,\infty]$, denoted here as
$\mathfrak{S}_{p}^{w}(X,Y)$ or $X^{*}\otimes_{\mathfrak{S}_{p}^{w}}Y$.

  3. 3.

Finally, here we also define a variant of the space
$\mathfrak{S}_{p}^{w}(X,Y)$ that appears naturally in our study and that seems
to be new in the literature. We denote this space
$\mathfrak{S}_{p}^{w-cb}(X,Y)$ or $X^{*}\otimes_{\mathfrak{S}_{p}^{w-cb}}Y$
and call it the space of _weak-cb_ Schatten von-Neumman operators of type
$p\in[1,\infty]$. The appellative cb is reminiscent of the fact that this new
structure makes use of constructions coming from operator space theory.
Indeed, $\mathfrak{S}_{p}^{w-cb}$ is an operator ideal but in the operator
space sense, therefore belonging more naturally to that category than to the
one of Banach spaces. In any case, we state this as a matter of curiosity and
completeness, and these fine-grained details are irrelevant for the scope of
the present work. Nonetheless, it is possible that a further exploration of
these structures could lead to the clarification of some of the problems we
leave open.

After this brief summary, we provide now the details of the contents cited
above. We follow part of the exposition [32, Chapter 2] with suitable
simplifications adapted to the scope of this work.

For finite dimensional Banach spaces $X$ and $Y$, the space of linear maps
$X\rightarrow Y$ can be identified in a simple way with the tensor product
$X^{*}\otimes Y$, as was implicitly assumed above. The identification consists
on associating to any element in $X^{*}\otimes Y$,
$\,\hat{f}=\sum_{i}x_{i}^{*}\otimes y_{i}$, the linear map $f:X\ni x\mapsto
f(x):=\sum_{i}x_{i}^{*}(x)\,y_{i}\,\in Y$. Conversely, to any linear map
$f:X\rightarrow Y$ we associate the tensor $\hat{f}=\sum_{i}x^{*}_{i}\otimes
f(x_{i})$, where $\\{x_{i}\\}_{i},\,\\{x_{i}^{*}\\}_{i}$ are dual bases of $X$
and $X^{*}$, respectively. Based on that, we will tend to present our results
making explicit the tensor product structure but sometimes, especially in this
introductory part of the paper, it will be more natural to talk about
mappings, so we will use both conventions interchangeably.

The first operator ideal we encounter is the one of bounded operators from $X$
into $Y$, that we denote $\mathcal{B}(X,Y)$ and that is the Banach space of
linear operators $f:X\rightarrow Y$ endowed with the operator norm,
$\|f\|:=\sup_{x\in B_{X}}\|f(x)\|_{Y}<\infty$. Using the equivalence stated
before, understanding this space as a tensor product is precisely how the
injective tensor product is defined:
$X^{*}\otimes_{\varepsilon}Y\simeq\mathcal{B}(X,Y)$. If $X$ and $Y$ are finite
dimensional spaces, the dual of $X^{*}\otimes_{\varepsilon}Y$ coincides with
the projective tensor product,
$X\otimes_{\pi}Y^{*}\simeq(\mathcal{B}(X,Y))^{*}$. It is enough for the scope
of this manuscript to take this equivalence as the definition of
$X\otimes_{\pi}Y^{*}$. These norms satisfy the desirable _metric mapping
property_ : for any Banach spaces $X_{0}$, $X_{1}$, $Y_{0}$, $Y_{1}$, and any
operators $f\in\mathcal{B}(X_{0},X_{1})$, $g\in\mathcal{B}(Y_{0},\,Y_{1})$,

$\big{\|}f\otimes g:X_{0}\otimes Y_{0}\rightarrow X_{1}\otimes
Y_{1}\big{\|}\leq\big{\|}f\big{\|}\,\big{\|}g\big{\|}.$ (8)

Furthermore, we call _tensor norm_ to any $\alpha$ that associates to any pair
of Banach spaces $X$, $Y$, a norm $\|\,\cdot\,\|_{X\otimes_{\alpha}Y}$ such
that:

  * •

$\alpha$ is _in between_ of the tensor norms $\varepsilon$ and $\pi$. That is,

$\text{for any }x\in X\otimes_{\alpha}Y,\
\,\|x\|_{X\otimes_{\varepsilon}Y}\leq\|x\|_{X\otimes_{\alpha}Y}\leq\|x\|_{X\otimes_{\pi}Y};$

  * •

$\alpha$ satisfies the metric mapping property.

Later on, in Section 5 we will more generally refer as tensor norms to norms
defined _tensorizing_ consecutively different tensor norms. For example, if
$\alpha,\,\alpha^{\prime}$ are tensor norms, the assignment on any three
Banach spaces $X,\,Y,\,Z$ of the norm
$(X\otimes_{\alpha}Y)\otimes_{\alpha^{\prime}}Z$ will be called also tensor
norm.

The last tensor norm that we need is the 2-summing norm: for an operator
$f\in\mathcal{B}(X,Y)$,

$\|f\|_{\pi_{2}(X,Y)}:=\big{\|}\mathrm{Id}\otimes
f:\ell_{2}\otimes_{\varepsilon}X\rightarrow\ell_{2}(Y)\big{\|}.$ (9)

Next we introduce Schatten classes of compact operators between Hilbert
spaces, that are the model to define the generalizations in the theory of
operator ideals that we use later on. To define the $p$-th Schatten class
$\mathcal{S}_{p}(\mathcal{H})$, for $1\leq p\leq\infty$, we associate to any
compact operator on a Hilbert space, $f:\mathcal{H}\rightarrow\mathcal{H}$,
its sequence of singular values $(s_{i}(f))_{i\in\mathbb{N}}$, where
$s_{1}(f)\leq s_{2}(f)\leq\ldots$. With this sequence, we define the norm
$\|f\|_{\mathcal{S}_{p}}:=\big{\|}(s_{i}(f))_{i}\big{\|}_{\ell_{p}}$, which
provides the normed structure on $\mathcal{S}_{p}(\mathcal{H})$. We use the
simpler notation $\mathcal{S}_{p}$ to denote the $p$-th Schatten class of
operators on the separable Hilbert space $\ell_{2}$. In the finite dimensional
case we use the notation $\mathcal{S}_{p}^{n,m}$ to refer to the $p$-th
Schatten class of operators from $\ell_{2}^{m}$ into $\ell_{2}^{n}$. Notice
that the case $p=\infty$ coincides with the operator ideal we denoted before
as $M_{n,m}$, while for $p=1$ we obtain $\mathcal{S}_{1}^{n,m}$.

Now, moving into operators between arbitrary Banach spaces we define:

######  Definition 2.11.

Given an operator $f:X\rightarrow Y$ and $1\leq p\leq\infty$ we say that $f$
is of weak Schatten-von Neumann type $\ell_{p}$ if

$\|f\|_{\mathfrak{S}_{p}^{w}(X,Y)}:=\sup\left\\{\Big{\|}\Big{(}s_{i}(g\circ
f\circ h)\Big{)}_{i}\Big{\|}_{\ell_{p}}\ :\
\begin{array}[]{l}\|g:Y\rightarrow\ell_{2}\|\leq 1\\\\[5.0pt]
\|h:\ell_{2}\rightarrow X\|\leq 1\end{array}\right\\}<\infty,$

where $(s_{i}(g\circ f\circ h)\big{)}_{i}$ is the sequence of singular values
of the operator $g\circ f\circ h:\ell_{2}\longrightarrow\ell_{2}$.

We denote by $\mathfrak{S}_{p}^{w}(X,Y)$ the space of operators
$f:X\longrightarrow Y$ of weak Schatten-von Neumann type $\ell_{p}$.
Alternatively, in the tensor product notation, we refer to this space by
$X^{*}\otimes_{\mathfrak{S}_{p}^{w}}Y$.

To finish this section we introduce the space $\mathfrak{S}_{p}^{w-cb}(X,Y)$
announced at the beginning of this section. Its definition is based on
Definition 2.11 and it incorporates elements of the theory of operators
spaces. This forces us to endow $X$ and $Y$ with operator space structures
(o.s.s), that is, norms on the _matrix levels_ of these spaces,
$M_{n}(X)\equiv M_{n}\otimes X$, $M_{n}(Y)\equiv M_{n}\otimes Y$ for any
$n\in\mathbb{N}$ – see [16] or [35] for a detailed exposition on operator
spaces. With that, the natural notion for maps between operator spaces is the
notion of _completely bounded_ operators, that is, linear operators
$f:X\rightarrow Y$ such that

$\|f:X\rightarrow Y\|_{cb}:=\sup_{n\in\mathbb{N}}\|\mathrm{Id}\otimes
f:M_{n}(X)\rightarrow M_{n}(Y)\|<\infty.$

The space of completely bounded operators between $X$ and $Y$ is denoted by
$\mathcal{C}\mathcal{B}(X,Y)$.

A Banach space can be endowed in general with several o.s.s. In the case of
the space $\mathcal{B}(\mathcal{H},\mathcal{K})$, with $\mathcal{H}$ and
$\mathcal{K}$, Hilbert spaces, there is a natural o.s.s. determined by
promoting the isomorphism
$M_{n}\left(\mathcal{B}(\mathcal{H},\mathcal{K})\right)$ $\simeq$
$\mathcal{B}(\mathcal{H}^{\otimes n},\mathcal{K}^{\otimes n})$ to an isometry
(fixing that way the norm in the _matrix levels_ of the space)101010 Here we
considered hilbertian tensor products in such a way that $\mathcal{H}^{\otimes
n}$ and $\mathcal{K}^{\otimes n}$ are again Hilbert spaces.. For a Hilbert
space $\mathcal{H}$, we introduce here the so-called _row_ and _column_
o.s.s., denoting the corresponding operator spaces $R$ and $C$, respectively.
$R$ is defined via the _row_ embedding:

$\mathcal{H}\simeq\mathcal{B}(\ell_{2},\mathbb{C}),$

from which we define a norm on $M_{n}(\mathcal{H})$ considering the following
isomorphism to be an isometry: $M_{n}(\mathcal{H})\simeq
M_{n}\left(\mathcal{B}(\mathcal{H},\mathbb{C})\right)\simeq\mathcal{B}(\mathcal{H}^{\otimes
n},\ell_{2}^{n}).$

Similarly, $C$ is defined substituting the previous _row_ embedding by it
_column_ version

$\mathcal{H}\simeq\mathcal{B}(\mathbb{C},\ell_{2}).$

These last two operator spaces turn out to be non-isomorphic, on the contrary
to what happens at the Banach level, where they are simply Hilbert spaces.
They are still dual between themselves, that is, $C^{*}\simeq R$ and $C\simeq
R^{*}$ completely isometrically111111 Meaning that not only $C^{*}\simeq R$
and $C\simeq R^{*}$ stand isometrically but also $M_{n}(C^{*})\simeq M_{n}(R)$
and $M_{n}(C)\simeq M_{n}(R^{*})$ for any $n\in\mathbb{N}$.. However, to
properly state those identifications we need a notion of duality for operator
spaces. This notion is induced by that of completely bounded maps introduced
before. We say that, for an operator space $X$, $X^{*}$ is its dual if

$M_{n}(X^{*})=\mathcal{C}\mathcal{B}(X,M_{n})\quad\text{ for any
}n\in\mathbb{N}.$

Notice that for $n=1$ the previous characterization of $X^{*}$ coincides with
the dual as Banach spaces121212 For that it is necessary to consider the fact
that $\mathcal{C}\mathcal{B}(X,\mathbb{C})\simeq\mathcal{B}(X,\mathbb{C})$..
As a last comment on operator spaces, we note that this duality allows to
endow $\mathcal{S}_{1}(\mathcal{H})$ with a natural o.s.s. as the dual of
$\mathcal{B}(\mathcal{H})$. Now we finally have all the ingredients to define:

######  Definition 2.12.

Given an operator between operator spaces $f:X\rightarrow Y$ and $1\leq
p\leq\infty$ we say that $f$ is of weak-cb Schatten-von Neumann type
$\ell_{p}$ if

$\|f\|_{\mathfrak{S}_{p}^{w-cb}(X,Y)}:=\sup\left\\{\Big{\|}\left(s_{i}\left(g\circ
f\circ h\right)\right)_{i}\Big{\|}_{\ell_{p}}\ :\
\begin{array}[]{l}\big{\|}\,g:Y\longrightarrow C\,\big{\|}_{cb}\leq
1\\\\[5.0pt] \big{\|}\,h:R\longrightarrow X\,\big{\|}_{cb}\leq
1\end{array}\right\\}<\infty,$

where $(s_{i}(g\circ f\circ h)\big{)}_{i}$ is the sequence of singular values
of the operator $g\circ f\circ h:\ell_{2}\longrightarrow\ell_{2}$.

We denote by $\mathfrak{S}_{p}^{w-cb}(X,Y)$ the space of operators
$f:X\longrightarrow Y$ of weak-cb Schatten-von Neumann type $\ell_{p}$.
Alternatively, in the tensor product notation, we refer to this space by
$X^{*}\otimes_{\mathfrak{S}_{p}^{w-cb}}Y$.

######  Remark 2.13.

Since $B_{\mathcal{CB}(X,Y)}\subseteq B_{\mathcal{B}(X,Y)}$ for any operator
spaces $X$, $Y$, it follows that

$\|f\|_{\mathfrak{S}_{p}^{w-cb}(X,Y)}\leq\|f\|_{\mathfrak{S}_{p}^{w}(X,Y)},$
(10)

for any $1\leq p\leq\infty$ and any $f\in\mathfrak{S}_{p}^{w-cb}(X,Y)$.

Before ending this section, we provide an alternative characterization of the
norm introduced above when $X=M_{n,m}$, $Y=\mathcal{S}_{1}^{n,m}$ and $p=2$.
That is the case appearing in our study of cheating strategies for PV in
Section 4. For that, we understand
$\mathfrak{S}_{2}^{w-cb}(M_{n,m},\mathcal{S}_{1}^{n,m})$ as the tensor product
$\mathcal{S}_{1}^{n,m}\otimes_{\mathfrak{S}_{2}^{w-cb}}\mathcal{S}_{1}^{n,m}$.
Then,

######  Lemma 2.14.

Given a tensor $f\in\mathcal{S}_{1}^{n,m}\otimes\mathcal{S}_{1}^{n,m}$, where
$\mathcal{S}_{1}^{n,m}$ is endowed with its natural o.s.s. (as the dual of
$M_{n,m}$), we have that:

$\|f\|_{\mathcal{S}_{1}^{n,m}\otimes_{\mathfrak{S}_{2}^{w-cb}}\mathcal{S}_{1}^{n,m}}=\sup_{\begin{subarray}{c}r\in\mathbb{N}\\\
g,h\in B_{M_{nr,m}}\end{subarray}}\big{\|}(h\otimes
g)(f)\big{\|}_{\ell_{2}^{r^{2}}}.$

Above, the action of
$h=\sum_{i=1}^{n}\sum_{j=1}^{r}\sum_{l=1}^{m}h_{ijl}|ij\rangle\langle l|\in
M_{nr,m}$ on a tensor $t=\sum_{i=1}^{n}\sum_{j=1}^{m}$ $t_{ij}|i\rangle\langle
j|\in\mathcal{S}_{1}^{n,m}$ is defined by

$h(t):=\sum_{j=1}^{r}\left(\sum_{i=1}^{n}\sum_{l=1}^{m}h_{ijl}t_{ijl}\right)\,|j\rangle\in\ell_{2}^{r}.$

###### Proof.

The claim follows from the following observations:

  * •

a standard argument shows that the supremum in Definition 2.12 can be taken
over finite dimensional $C_{r}$ and $R_{r}$, where $r\in\mathbb{N}$ is
arbitrarily large;

  * •

for an operator between Hilbert spaces, as $g\circ f\circ h$ in Definition
2.12, the $\ell_{2}$-sum of the singular values coincide with the Hilbert-
Schmidt norm of the operator, which is the same as the Euclidean norm of the
tensor associated. In our case, with a slight abuse of notation, the relevant
tensor is $(h\otimes g)(f)$;

  * •

finally, when we set $X=M_{n,m}$, $Y=\mathcal{S}_{1}^{n,m}$ in Definition
2.12, the optimization is carried over elements $g\in
B_{\mathcal{CB}(\mathcal{S}_{1}^{n,m},C_{r})}$ ans $h\in B_{M_{n,m}}$. But
now, it is again a standard result that the following are complete isometries
[16, Section 9.3]: $\mathcal{CB}(\mathcal{S}_{1}^{n,m},C_{r})\simeq
M_{nr,m}\simeq\mathcal{CB}(R_{r},M_{n,m})$. The claim of the lemma is obtained
acting with $g,\,h$ viewed as elements in $B_{M_{nr,m}}$ as defined in the
statement.

∎

####  2.4.2 Interpolation of Banach spaces

Properties of interpolation spaces allow us to obtain estimates for the type
constants of certain spaces that are useful for our purposes in this work.
Here we restrict ourselves to the study of the complex interpolation space
$(X_{0},X_{1})_{\theta}$ for $0<\theta<1$ and finite dimensional Banach spaces
$X_{0}$, $X_{1}$. We decided to avoid here a full treatment of the rather
cumbersome definition of these spaces and focus on stating some natural
properties they display. That is enough for the scope of our work. We redirect
the interested reader to the classical references [2, 48].

In our case, in which $X_{0}$, $X_{1}$ are finite dimensional, the space
$(X_{0},X_{1})_{\theta}$ can always be constructed. In the general case, for
arbitrary Banach spaces, if we still can define $(X_{0},X_{1})_{\theta}$ we
say that the couple $(X_{0},\,X_{1})$ is compatible131313 Technically, this
condition is usually stated as the requirement that $X_{0}$ and $X_{1}$ embed
continuously in a common Hausdorff topological vector space., so we fix this
terminology from now on. For the sake of concreteness, here we will consider
the case in which $X_{0}$, $X_{1}$ and $(X_{0},X_{1})_{\theta}$ are
algebraically the same space but endowed with different norms. The complex
interpolation method, that assigns to any compatible couple $(X_{0},\,X_{1})$
the space $(X_{0},X_{1})_{\theta}$, is an _exact interpolation functor of
exponent_ $\theta$. This means that it satisfies the following:

######  Theorem 2.15 ([2], Thm. 4.1.2.).

For any compatible couples $(X_{0},\,X_{1})$, $(Y_{0},\,Y_{1})$, and any
linear map $f:(X_{0},X_{1})_{\theta}\rightarrow(Y_{0},Y_{1})_{\theta}$:

$\big{\|}f:(X_{0},X_{1})_{\theta}\rightarrow(Y_{0},Y_{1})_{\theta}\big{\|}\leq\big{\|}f:X_{0}\rightarrow
Y_{0}\big{\|}^{1-\theta}\ \big{\|}f:X_{1}\rightarrow Y_{1}\big{\|}^{\theta},$

where $\|\,\cdot\,\|$ above denotes the usual operator norm.

Now we turn our attention to the classical sequence $\ell_{p}$ spaces.
Interpolation in this case becomes remarkably natural. We have the isometric
identification $\ell_{p}=(\ell_{\infty},\,\ell_{1})_{\nicefrac{{1}}{{p}}}$ for
any $1\leq p\leq\infty$. Indeed, such an identification follows in a much more
general setting. For a Banach space $X$ and $p\in(0,\infty]$, let us denote
$L_{p}(X)$ the space of p-integrable $X$ valued functions on the unit
interval. That is, measurable functions $f:[0,1]\rightarrow X$ such that

$\|f\|_{L_{p}(X)}:=\left(\int_{0}^{1}\|f(t)\|_{X}^{p}\mathrm{d}\mu(t)\right)^{\frac{1}{p}},$

for an (implicitly) given measure $\mu$. With that we can state:

######  Theorem 2.16 ([2], Thm. 5.6.1.).

For any compatible couple $(X_{0},\,X_{1})$, $p_{0},\,p_{1}\in[1,\infty]$ and
$\theta\in(0,1)$ the following follows with equal norms:

$\Big{(}L_{p_{0}}(X_{0}),\,L_{p_{1}}(X_{1})\Big{)}_{\theta}=L_{p}\Big{(}(X_{0},\,X_{1})_{\theta}\Big{)},$

where $\frac{1}{p}=\frac{1-\theta}{p_{0}}+\frac{\theta}{p_{1}}$.

Notice that $\ell_{p}(X)$ spaces can be regarded as particular instances of
$L_{p}(X)$ where the natural numbers are identified with a subset of the
interval $[0,1]$ and $\mu$ is fixed as the discrete measure with unit weights
on that subset. This allows us to translate the previous statement also to
this case:

$\Big{(}\ell_{p_{0}}(X_{0}),\,\ell_{p_{1}}(X_{1})\Big{)}_{\theta}=\ell_{p}\Big{(}(X_{0},\,X_{1})_{\theta}\Big{)},$
(11)

where $\frac{1}{p}=\frac{1-\theta}{p_{0}}+\frac{\theta}{p_{1}}$.

Pleasantly, an analogue result for Schatten classes is also true.

######  Theorem 2.17 ([38], Cor. 1.4.).

For a $p_{0},\,p_{1}\in[1,\infty]$ and $\theta\in(0,1)$ the following follows
with equal norms:

$(\mathcal{S}_{p_{0}},\,\mathcal{S}_{p_{1}})_{\theta}=\mathcal{S}_{p},$

where $\frac{1}{p}=\frac{1-\theta}{p_{0}}+\frac{\theta}{p_{1}}$. When it
applies, $\mathcal{S}_{\infty}$ must be understood as the Banach space (with
the operator norm) of compact operators in a separable Hilbert space.

These are all the basic results we need regarding complex interpolation. To
finish this section, we now relate some of the norms introduced in Section
2.4.1 with the space
$(X^{*}\otimes_{\varepsilon}Y,X^{*}\otimes_{\pi}Y)_{\frac{1}{2}}$.

######  Proposition 2.18.

Given finite dimensional Banach spaces $X$, $Y$, for any $f\in X\otimes Y)$,

$\big{\|}f\big{\|}_{X\otimes_{\mathfrak{S}_{2}^{w-cb}}Y}\leq\big{\|}f\big{\|}_{X\otimes_{\mathfrak{S}_{2}^{w}}Y}\leq\big{\|}f\big{\|}_{(X^{*}\otimes_{\varepsilon}Y,X^{*}\otimes_{\pi}Y)_{\frac{1}{2}}}.$

###### Proof.

Recalling that we have already established the first inequality in Remark
2.13. Therefore we focus on the second inequality.

According to the definition of $\mathfrak{S}_{2}^{w}(X,Y)$, Definition 2.11,
we can directly write:

$\big{\|}f\big{\|}_{\mathfrak{S}_{2}^{w}(X,Y)}=\sup_{\begin{subarray}{c}g\in
B_{\mathcal{B}(Y,\ell_{2})}\\\ h\in
B_{\mathcal{B}(\ell_{2},X)}\end{subarray}}\|g\circ f\circ
h\|_{\mathcal{S}_{2}}=\sup_{\begin{subarray}{c}g\in
B_{\mathcal{B}(Y,\ell_{2})}\\\ h\in
B_{\mathcal{B}(\ell_{2},X)}\end{subarray}}\|g\circ f\circ
h\|_{(\mathcal{S}_{\infty},\mathcal{S}_{1})_{1/2}},$

where we have used Theorem 2.17 to state the last equality.

The map $g\circ f\circ h:\ell_{2}\rightarrow\ell_{2}$ can be interpreted, as a
tensor, as the image of the mapping $h^{*}\otimes g:X^{*}\otimes
Y\rightarrow\ell_{2}\otimes\ell_{2}$ acting on $f$. With this, the previous
expression can be rewritten as:

$\displaystyle\big{\|}f\big{\|}_{\mathfrak{S}_{2}^{w}(X,Y)}$
$\displaystyle=\sup_{\begin{subarray}{c}g\in B_{\mathcal{B}(Y,\ell_{2})}\\\
h\in B_{\mathcal{B}(\ell_{2},X)}\end{subarray}}\|(h^{*}\otimes
g)(f)\|_{(\mathcal{S}_{\infty},\mathcal{S}_{1})_{\frac{1}{2}}}$
$\displaystyle\leq\|f\|_{(X^{*}\otimes_{\varepsilon}Y,X^{*}\otimes_{\pi}Y)_{\frac{1}{2}}}\
\sup_{\begin{subarray}{c}g\in B_{\mathcal{B}(Y,\ell_{2})}\\\ h\in
B_{\mathcal{B}(\ell_{2},X)}\end{subarray}}\|h^{*}\otimes
g:(X^{*}\otimes_{\varepsilon}Y,X^{*}\otimes_{\pi}Y)_{\frac{1}{2}}\rightarrow(\mathcal{S}_{\infty},\mathcal{S}_{1})_{\frac{1}{2}}\|.$

Now, it only remains to show that for any contractions
$h^{*}:X^{*}\rightarrow\ell_{2}$, $g:Y\rightarrow\ell_{2}$

$\|h^{*}\otimes
g:(X^{*}\otimes_{\varepsilon}Y,X^{*}\otimes_{\pi}Y)_{\frac{1}{2}}\rightarrow(\mathcal{S}_{\infty},\mathcal{S}_{1})_{\frac{1}{2}}\|\leq
1.$

This follows from the interpolation property, Theorem 2.15:

$\|h^{*}\otimes
g:(X^{*}\otimes_{\varepsilon}Y,X^{*}\otimes_{\pi}Y)_{\frac{1}{2}}\rightarrow(\mathcal{S}_{\infty},\mathcal{S}_{1})_{\frac{1}{2}}\|\leq\|h^{*}\otimes
g:X^{*}\otimes_{\varepsilon}Y\rightarrow\mathcal{S}_{\infty}\|^{\frac{1}{2}}\
\|h^{*}\otimes
g:X^{*}\otimes_{\pi}Y\rightarrow\mathcal{S}_{1}\|^{\frac{1}{2}},$

together with the understanding of $\mathcal{S}_{\infty}$ and
$\mathcal{S}_{1}$ as the tensor products
$\ell_{2}\otimes_{\varepsilon}\ell_{2}$ and $\ell_{2}\otimes_{\pi}\ell_{2}$,
respectively. This allows us to bound

$\|h^{*}\otimes
g:X^{*}\otimes_{\varepsilon}Y\rightarrow\mathcal{S}_{\infty}\|=\|h^{*}:X^{*}\rightarrow\ell_{2}\|\
\|g:Y\rightarrow\ell_{2}\|\leq 1,$

thanks to the metric mapping property displayed by the injective tensor norm,
$\varepsilon$ (8). Analogously

$\|h^{*}\otimes
g:X^{*}\otimes_{\pi}Y\rightarrow\mathcal{S}_{1}\|=\|h^{*}:X^{*}\rightarrow\ell_{2}\|\
\|g:Y\rightarrow\ell_{2}\|\leq 1.$

Hence, the claim in the statement follows. ∎

Being more specific, when $X^{*}=Y=\mathcal{S}_{1}^{n,m}$, Proposition 2.18
reads

$\|f\|_{\mathcal{S}_{1}^{n,m}\otimes_{\mathfrak{S}_{2}^{w-cb}}\mathcal{S}_{1}^{n,m}}\leq\|f\|_{\mathcal{S}_{1}^{n,m}\otimes_{\mathfrak{S}_{2}^{w}}\mathcal{S}_{1}^{n,m}}\leq\|f\|_{(\mathcal{S}_{1}^{n,m}\otimes_{\varepsilon}\mathcal{S}_{1}^{n,m},\,\mathcal{S}_{1}^{n,m}\otimes_{\pi}\mathcal{S}_{1}^{n,m})_{\frac{1}{2}}}.$
(12)

####  2.4.3 Type/cotype of a Banach space

The key properties of a Banach space we study are its _type_ and _cotype_.
These are probabilistic notions in the local theory of Banach spaces that
built on _Rademacher_ random variables141414 There also exists in the
literature a _gaussian_ notion of type/cotype. See, e.g., [47]. Both notions
are in fact intimately related, but here we only consider the _Rademacher_
version of the story.. We call a random variable $\varepsilon$ Rademacher if
it takes values -1 and 1 with probability 1/2 each. We refer by
$\\{\varepsilon_{i}\\}_{i=1}^{n}$ to a family of n i.i.d. such random
variables. Then, $\mathbb{E}_{\varepsilon}\,\phi(\varepsilon)$ denotes the
expected value of a function $\phi$ over any combination of signs
$\\{\varepsilon_{i}\\}_{i=1}^{n}$ with uniform weight $1/2^{n}$.

######  Definition 2.19.

Let $X$ be a Banach space and $1\leq p\leq 2$. We say $X$ is of (Rademacher)
type $p$ if there exists a positive constant $\mathrm{T}$ such that for every
natural number $n$ and every sequence $\\{x_{i}\\}_{i=1}^{n}\subset X$ we have

$\left(\mathbb{E}_{\varepsilon}\Big{[}\big{\|}\sum_{i=1}^{n}\varepsilon_{i}x_{i}\big{\|}_{X}^{2}\Big{]}\right)^{1/2}\leq\mathrm{T}\left(\sum_{i=1}^{n}\|x_{i}\|_{X}^{p}\right)^{1/p},$

Moreover, we define the Rademacher type $p$ constant $\mathrm{T}_{p}(X)$ as
the infimum of the constants $\mathrm{T}$ fulfilling the previous inequality.

The notion of type of a normed space finds a dual notion in the one of cotype:

_For $2\leq q<\infty$, the Rademacher cotype $q$ constant of $X$,
$\mathrm{C}_{q}(X)$, is the infimum over the constants $\mathrm{C}$ (in case
they exist) such that the following inequality holds for every natural number
$n$ and every sequence $\\{x_{i}\\}_{i=1}^{n}\subset X$,_

$\displaystyle\mathrm{\mathrm{C}}^{-1}\Big{(}\sum_{i=1}^{n}\|x_{i}\|_{X}^{q}\Big{)}^{1/q}\leq\left(\mathbb{E}_{\varepsilon}\Big{[}\big{\|}\sum_{i=1}^{n}\varepsilon_{i}x_{i}\big{\|}_{X}^{2}\Big{]}\right)^{1/2}.$

_In parallel with the previous definition, we also say that $X$ is of cotype
$q$ if $\mathrm{C}_{q}(X)<\infty$. _

If the number of elements $x_{i}$ in the definitions above is restricted to be
lower or equal to some natural number $m$, we obtain the related notion of
_type/cotype constants of $X$ with $m$ vectors_, denoted here as
$\mathrm{T}_{p}^{(m)}(X)$ and $\mathrm{C}_{q}^{(m)}(X)$. This is the precise
notion we will use later on. Although it will be frequently enough to work
with the notion of type constants, sometimes we will need to make this
distinction.

Coming back to the better studied context of type and cotype (without any
restriction on the number of elements), it is well known that $X$ being of
type $p$ implies cotype $q$ for the dual, $X^{*}$, where $q$ is the conjugate
exponent such that $1/p+1/q=1$. This can be subsumed in the inequality – see,
e.g., [26]:

$\mathrm{C}_{q}(X^{*})\leq\mathrm{T}_{p}(X),\qquad\text{ for }1<p\leq 2,\
2\leq q<\infty\ :\ \frac{1}{p}+\frac{1}{q}=1.$ (13)

On the contrary, the reverse inequality fails in general – and, in fact, the
pair of spaces considered in this work, $(M_{n}$, $\mathcal{S}_{1}^{n})$, is
an instance of that phenomenon. However, it turns out that the reverse
inequality can be made true _up to logarithmic_ factors [33, 26]:

$\mathrm{T}_{p}(X)\lesssim\log(\dim(X))\,\mathrm{C}_{q}(X^{*}),\qquad\text{
for }1<p\leq 2,\ 2\leq q<\infty\ :\ \frac{1}{p}+\frac{1}{q}=1.$ (14)

Our interest now turns into the interaction between type and interpolation. In
fact, type constants behave well w.r.t. interpolation methods, fact that will
be extremely useful in next section. We state the following general known
result:

######  Proposition 2.20.

Let $X_{0},\,X_{1}$ be an interpolation couple, where $X_{i}$ has type $p_{i}$
for some $1\leq p_{i}\leq 2$, $i=0,\,1$. Let $0<\theta<1$ and $1<p<2$ such
that $\frac{1}{p}=\frac{1-\theta}{p_{0}}+\frac{\theta}{p_{1}}$. Then,

$\mathrm{T}_{p}\big{(}(X_{0},X_{1})_{\theta}\big{)}\leq\big{(}\mathrm{T}_{p_{0}}(X_{0})\big{)}^{1-\theta}\left(\mathrm{T}_{p_{1}}(X_{1})\right)^{\theta}.$

The proof follows easily from the interpolation properties of vector valued
$\ell_{p}$ and $L_{p}$ spaces. We decided to include a simple proof next
without any claim of originality.

###### Proof.

An alternative characterization of the type-p constant of a Banach space $X$
is given by the norm of the mapping:

$\begin{array}[]{cccc}\mathrm{Rad}:&\ell_{p}(X)&\longrightarrow&L_{2}(X)\\\
&(x_{i})_{i}&\mapsto&\sum_{i}\varepsilon_{i}\,x_{i}\end{array},$

where $\\{\varepsilon_{i}\\}_{i}$ are i.i.d. Rademacher random variables
and151515 Formally, to establish this identification we consider a realization
of the random variables $\varepsilon_{i}$ as real valued functions on the
interval $[0,1]$. A standard choice is setting
$\varepsilon_{i}(t)=\mathrm{sign}\left(\sin(2^{i}\pi t)\right)$. In that way,
for a function $\phi$ of the random variable $\varepsilon$,
$\mathbb{E}_{\varepsilon}\phi(\varepsilon)=\int_{0}^{1}\phi(\varepsilon(t))\mathrm{d}t$,
which makes the connection with $L_{p}$ spaces.

$\|\sum_{i}\varepsilon_{i}\,x_{i}\|_{L_{2}(X)}:=\left(\mathbb{E}_{\varepsilon}\big{\|}\sum_{i}\varepsilon_{i}x_{i}\big{\|}^{2}_{X}\right)^{\frac{1}{2}}.$

Then, we write

$\displaystyle\mathrm{T}_{p}\left((X_{0},X_{1})_{\theta}\right)$
$\displaystyle=\left\|\mathrm{Rad}:\ell_{p}\left((X_{0},X_{1})_{\theta}\right)\longrightarrow
L_{2}\left((X_{0},X_{1})_{\theta}\right)\right\|.$

Taking into account the equivalences (Theorem 2.16):

$\ell_{p}\left((X_{0},X_{1})_{\theta}\right)=\left(\ell_{p_{0}}(X_{0}),\ell_{p_{1}}(X_{1})\right)_{\theta},\qquad
L_{2}\left((X_{0},X_{1})_{\theta}\right)=\left(L_{2}(X_{0}),L_{2}(X_{1})\right)_{\theta},$

we can bound:

$\displaystyle\left\|\mathrm{Rad}:\ell_{p}\left((X_{0},X_{1})_{\theta}\right)\longrightarrow
L_{2}\left((X_{0},X_{1})_{\theta}\right)\right\|$
$\displaystyle\leq\left\|\mathrm{Rad}:\ell_{p_{0}}(X_{0})\longrightarrow
L_{2}(X_{0})\right\|^{1-\theta}\
\left\|\mathrm{Rad}:\ell_{p_{1}}(X_{1})\longrightarrow
L_{2}(X_{1})\right\|^{\theta}$
$\displaystyle=\left(\mathrm{T}_{p_{0}}(X_{0})\right)^{1-\theta}\left(\mathrm{T}_{p_{1}}(X_{1})\right)^{\theta}.$

∎

####  2.4.4 Vector valued maps on the Boolean hypercube

The main idea in this work consists on studying strategies to break a
particular family of PV schemes – defined in Section 3 – as assignments on the
boolean hypercube $\mathcal{Q}_{m}=\\{-1,1\\}^{m}$. We will associate to any
cheating strategy a vector valued mapping $\Phi:\mathcal{Q}_{m}\rightarrow X$,
being $X$ some Banach space. Regular enough $\Phi$’s will lead to good lower
bounds on resources required by the cheaters, contributing that way to shed
some new light on Question 1. To quantify the regularity of this kind of maps
we introduce the following parameter (depending also on the choice of the
space $X$):

######  Definition 2.21.

To any Banach-space valued map $\Phi:\mathcal{Q}_{m}\rightarrow X$ we
associate the parameter:

$\sigma_{\Phi}:=\log(m)\
\mathbb{E}_{\varepsilon\in\mathcal{Q}_{m}}\,\left(\sum_{i=1}^{m}\|\partial_{i}\Phi_{S}(\varepsilon)\|^{2}_{X}\right)^{1/2},$

where
$\partial_{i}\Phi(\varepsilon):=\frac{\Phi(\varepsilon_{1},\ldots,\varepsilon_{i},\ldots,\varepsilon_{m})-\Phi(\varepsilon_{1},\ldots,-\varepsilon_{i},\ldots,\varepsilon_{m})}{2}$
is the discrete derivative on the boolean hypercube in the i-th direction.

Intuitively, $\sigma$ is an average on both, the point $\varepsilon$ and the
direction $i$ (unnormalized in this last case), of the magnitude of the
derivative of the map $\Phi$. The prefactor $\log(n)$ is of minor importance
for our purposes and we added it to the definition of $\sigma_{\Phi}$ to
obtain more compact expressions later on.

######  Example 2.22.

In order to gain some familiarity, let us compute the parameter $\sigma$ of a
linear map

$\begin{array}[]{rccc}\Phi:&D_{m}&\longrightarrow&X\\\\[10.00002pt]
&\varepsilon&\mapsto&\Phi(\varepsilon):=\frac{1}{m}\sum_{j}\varepsilon_{j}x_{j}\end{array},$

where $x_{j}\in B_{X}$ for $j=1,\ldots m$

First, for any point $\varepsilon\in\mathcal{Q}_{m}$, and a direction
$i\in[m]$:

$\partial_{i}\Phi(\varepsilon)=\frac{1}{2m}\
\left(\sum_{j}\varepsilon_{j}x_{j}-\varepsilon_{j}(-1)^{\delta_{i,j}}x_{j}\right)=\frac{1}{m}\varepsilon_{i}\,x_{i}.$

Therefore,

$\sigma_{\Phi}=\frac{\log(m)}{m}\left(\sum_{i}\|x_{i}\|_{X}^{2}\right)^{\frac{1}{2}}\leq\frac{\log(m)}{m^{\frac{1}{2}}}.$

This is the ideal case in which our results lead directly to powerful lower
bounds on the resources required to break our PV schemes.

Ultimately, the motivation for the definition of $\sigma_{\Phi}$ is the bound
in Corollary 2.24 below. This is a consequence of the following Sobolev-type
inequality due to Pisier for vector-valued functions on the hypercube:

######  Lemma 2.23 ([34], Lemma 7.3).

In a Banach space $X$, let $p\geq 1$, $\Phi:\mathcal{Q}_{m}\rightarrow X$ and
$\varepsilon,\,\tilde{\varepsilon}$ be independent random vectors uniformly
distributed on $\mathcal{Q}_{m}$. Then,

$\mathbb{E}_{\varepsilon}\Big{\|}\Phi(\varepsilon)-\mathbb{E}_{\varepsilon}\Phi(\varepsilon)\Big{\|}_{X}^{p}\leq(C\log
m)^{p}\
\mathbb{E}_{\varepsilon,\tilde{\varepsilon}}\Big{\|}\sum_{i}\tilde{\varepsilon}_{i}\partial_{i}\Phi(\varepsilon)\Big{\|}^{p}_{X},$

where
$\partial_{i}\Phi(\varepsilon):=\frac{\Phi(\varepsilon_{1},\ldots,\varepsilon_{i},\ldots,\varepsilon_{n})-\Phi(\varepsilon_{1},\ldots,-\varepsilon_{i},\ldots,\varepsilon_{n})}{2}$.

It is now very easy to combine this result with the type properties of $X$ in
order to obtain:

######  Corollary 2.24 (of Lemma 2.23).

Consider a function $\Phi:\mathcal{Q}_{m}\longrightarrow X$, where $X$ is a
Banach space. Then

$\mathbb{E}_{\varepsilon}\big{\|}\Phi(\varepsilon)\big{\|}_{X}\leq\big{\|}\mathbb{E}_{\varepsilon}\Phi(\varepsilon)\big{\|}_{X}+C\
\sigma_{\Phi}\ \mathrm{T}^{(m)}_{2}(X),$

where $C$ is an independent constant.

This is the cornerstone of the building leading to Theorem 1.1.

###### Proof of Corollary 2.24.

Fix $p=1$ in Lemma 2.23. Therefore, we have that :

$\mathbb{E}_{\varepsilon}\Big{\|}\Phi(\varepsilon)-\mathbb{E}_{\varepsilon}\Phi(\varepsilon)\Big{\|}_{X}\leq(C\log
m)\
\mathbb{E}_{\varepsilon,\tilde{\varepsilon}}\Big{\|}\sum_{i}\tilde{\varepsilon}_{i}\partial_{i}\Phi(\varepsilon)\Big{\|}_{X}.$

Additionally, we can trivially bound:

$\mathbb{E}_{\varepsilon}\Big{\|}\Phi(\varepsilon)-\mathbb{E}_{\varepsilon}\Phi(\varepsilon)\Big{\|}_{X}\geq\mathbb{E}_{\varepsilon}\Big{\|}\Phi(\varepsilon)\Big{\|}_{X}-\Big{\|}\mathbb{E}_{\varepsilon}\Phi(\varepsilon)\Big{\|}_{X}.$

On the other hand, according to the definition of the type-2 constant (with
$m$ vectors if one wants to be more precise) of $X$ we also can say:

$\mathbb{E}_{\varepsilon,\tilde{\varepsilon}}\Big{\|}\sum_{i}\tilde{\varepsilon}_{i}\partial_{i}\Phi(\varepsilon)\Big{\|}_{X}\leq\mathrm{T}_{2}^{(m)}(X)\
\mathbb{E}_{\varepsilon}\,\left(\sum_{i}\|\partial_{i}\Phi_{S}(\varepsilon)\|^{2}_{X}\right)^{1/2}.$

That’s enough to obtain the statement. ∎

####  2.4.5 Some key estimates of type constants

Corollary 2.24 provides us with a tool to upper bound the expected norm of the
image of a map $\Phi:\mathcal{Q}_{m}\rightarrow X$, provided that we have some
control over the RHS of the inequality in the statement. The only piece there
that is independent of the map $\Phi$ is the type-2 constant (with m vectors)
$\mathrm{T}_{2}^{(m)}(X)$, to which the rest of this section is devoted.

Later on, the normed spaces $M_{n,m}$ and
$\mathcal{S}_{1}^{n,m}\otimes_{\mathfrak{S}_{2}^{cb-w}}\mathcal{S}_{1}^{n,m}$
will play a prominent role. The type and cotype properties of $M_{n,m}$ as
well as $\mathcal{S}_{1}^{n,m}$ are well known. In particular the following
estimates hold:

$\begin{array}[]{c}\mathrm{C}_{2}(M_{n,m})\approx\min(n^{1/2},m^{1/2}),\qquad\mathrm{T}_{2}(M_{n,m})\approx\log^{1/2}(\min(n,m)),\end{array}$
(15) $\begin{array}[]{c}\mathrm{C}_{2}(\mathcal{S}_{1}^{n,m})\approx
1,\qquad\mathrm{T}_{2}(\mathcal{S}_{1}^{n,m})\approx(\min(n,m))^{1/2}.\end{array}$
(16)

For
$\mathcal{S}_{1}^{n,m}\otimes_{\mathfrak{S}_{2}^{cb-w}}\mathcal{S}_{1}^{n,m}$
the situation is not that well understood at all. In fact, we were not able to
obtain any non-trivial estimate for its type properties so far. Then, instead
of dealing directly with this space, we will consider the interpolation space
$(\mathcal{S}_{1}^{n,m}\otimes_{\varepsilon}\mathcal{S}_{1}^{n,m},\mathcal{S}_{1}^{n,m}\otimes_{\pi}\mathcal{S}_{1}^{n,m})_{\frac{1}{2}}$,
that turns out to be an upper bound to the norm in
$\mathcal{S}_{1}^{n,m}\otimes_{\mathfrak{S}_{2}^{cb-w}}\mathcal{S}_{1}^{n,m}$,
recall Proposition 2.18. From now on we use the following notational short-
cut:
$(\mathcal{S}_{1}^{n,m}\otimes_{\varepsilon}\mathcal{S}_{1}^{n,m},\mathcal{S}_{1}^{n,m}\otimes_{\pi}\mathcal{S}_{1}^{n,m})_{\theta}=\mathcal{S}_{1}^{n,m}\otimes_{(\varepsilon,\pi)_{\theta}}\mathcal{S}_{1}^{n,m}$.
Thanks to the extra structure in
$\mathcal{S}_{1}^{n,m}\otimes_{(\varepsilon,\pi)_{1/2}}\mathcal{S}_{1}^{n,m}$
provided by interpolation, we are able to obtain a bound for its type
constants. To simplify the presentation, we consider in the following that
$\min(n,m)=n$. We can state:

######  Proposition 2.25.

Given $0<\theta<1$, and natural numbers $n\leq m$:

$\mathrm{T}_{\frac{2}{1+\theta}}\left(\mathcal{S}_{1}^{n,m}\otimes_{(\varepsilon,\pi)_{\theta}}\mathcal{S}_{1}^{n,m}\right)\lesssim_{\log}n^{\frac{1-\theta}{2}}.$

An immediate consequence of the previous corollary is a bound for the type-2
constant with $n^{2}$ vectors:

$\mathrm{T}_{2}^{(n^{2})}\left(\mathcal{S}_{1}^{n,m}\otimes_{(\varepsilon,\pi)_{\theta}}\mathcal{S}_{1}^{n,m}\right)\leq
n^{\theta}\
\mathrm{T}_{\frac{2}{1+\theta}}\left(\mathcal{S}_{1}^{n,m}\otimes_{(\varepsilon,\pi)_{\theta}}\mathcal{S}_{1}^{n,m}\right)\lesssim_{\log}n^{\frac{1+\theta}{2}}.$

Particularizing for $\theta=\frac{1}{2}$:

$\mathrm{T}_{2}^{(n^{2})}\left(\mathcal{S}_{1}^{n,m}\otimes_{(\varepsilon,\pi)_{\frac{1}{2}}}\mathcal{S}_{1}^{n,m}\right)\lesssim_{\log}n^{\frac{3}{4}}.$
(17)

This is the key type-estimate to obtain part II. of the main Theorem 1.1.

For the sake of concreteness, we explicit here the logarithmic corrections in
(17):

$\mathrm{T}_{2}^{(n^{2})}\big{(}\mathcal{S}_{1}^{n,m}\otimes_{(\varepsilon,\pi)_{\frac{1}{2}}}\mathcal{S}_{1}^{n,m}\big{)}\lesssim
n^{3/4}\log^{1/2}(nm)\log(n).$

###### Proof of 2.25.

The proof proceeds in two steps. First, using techniques from [36, 37], we
obtain the estimate

$\mathrm{T}_{2}(\mathcal{S}_{1}^{n,m}\otimes_{\varepsilon}\mathcal{S}_{1}^{n,m})\lesssim_{\log}n^{1/2}.$
(18)

With this at hand, Proposition 2.25 follows from how type constants interact
with the complex interpolation method, Proposition 2.20. In particular, it is
enough to fix $p_{0}=2$, $p_{1}=1$ in that result and consider the trivial
bound
$\mathrm{T}_{1}(\mathcal{S}_{1}^{n,m}\otimes_{\pi}\mathcal{S}_{1}^{n,m})=1$.

Therefore, there remains to provide a proof for (18). To prove the stated
estimate we bound the cotype-2 constant of the dual,
$M_{n,m}\otimes_{\pi}M_{n,m}$. Therefore, from the duality between type and
cotype, Proposition 14, we obtain:

$\mathrm{T}_{2}(\mathcal{S}_{1}^{n,m}\otimes_{\varepsilon}\mathcal{S}_{1}^{n,m})\lesssim\log(nm)\,\mathrm{C}_{2}(M_{n,m}\otimes_{\pi}M_{n,m}).$

To estimate $\mathrm{C}_{2}(M_{n,m}\otimes_{\pi}M_{n,m})$, we use the
following bound on the cotype of the projective tensor product, implicit in
[36]161616 The key result here is Theorem 5.1 in [36]. The bound we use is
obtained keeping track of the constants appearing in the isomorphic statement
of that theorem. We are indebted to Jop Briët for kindly sharing with us some
very useful private notes on Pisier’s method.

$\mathrm{C}_{2}(M_{n,m}\otimes_{\pi}M_{n,m})\lesssim\mathrm{C}_{2}(M_{n,m})\,\mathrm{UMD}(M_{n,m})\,\mathrm{T}_{2}^{2}(M_{n,m}),$

where $\mathrm{UMD}(X)$ is the analytic UMD (unconditional martingale
difference) parameter of the Banach space $X$. We now bound each of the
quantities in the RHS of the last inequality:

  * •

recalling (15) we have that $\mathrm{C}_{2}(M_{n,m})\lesssim n^{1/2}$ and
$\mathrm{T}_{2}(M_{n,m})\lesssim\log^{1/2}(n)$;

  * •

we estimate $\mathrm{UMD}(M_{n,m})$ from known bounds for the UMD constant of
the p-Schatten class $\mathcal{S}_{p}$, for $1<p<\infty$. It is known that
these spaces are UMD and the following estimate for
$\mathrm{UMD}(\mathcal{S}_{p})$ is available [39]:

$\mathrm{UMD}(\mathcal{S}_{p})\lesssim p.$

This also translates on the same bound for the subspace
$\mathcal{S}_{p}^{n,m}$. Now, we take into account the following relation
between the UMD constants of arbitrary spaces $X$ and $Y$ at Banach-Mazur
distance $d(X,Y)$. This is a direct consequence of the geometric
characterization of the UMD property due to Burkholder [6] – see also [7]:

$\mathrm{UMD}(X)\lesssim d(X,Y)\,\mathrm{UMD}(Y).$

Finally, with this at hand, we obtain the bound

$\mathrm{UMD}(M_{n,m})\lesssim
d(M_{n,m},\mathcal{S}_{p}^{n,m})\,\mathrm{UMD}(\mathcal{S}_{p}^{n,m})\lesssim
n^{1/p}\,p.$

Adjusting the parameter $p$ as $p=\log(n)$ we obtain

$\mathrm{UMD}(M_{n,m})\lesssim\log(n),$

that is enough to conclude that

$\mathrm{T}_{2}(\mathcal{S}_{1}^{n,m}\otimes_{\varepsilon}\mathcal{S}_{1}^{n,m})\lesssim\log(nm)\,\log^{2}(n)\,n^{1/2}.$

∎

##  3 The game $\mathbf{G_{Rad}}$

In this section we describe the precise scheme we analyse in this work, which
we denote $G_{Rad}$. For that, we come back to the setting fixed at the end of
Section 2.3, in Remark 2.10. But first, we introduce $G_{Rad}$ from the point
of view of protocols for PV – cf. section 2.2 –. Actually, $G_{Rad}$ will
rather refer to a family of protocols indexed by a natural number, $n$, making
reference to the _size_ of the protocol. This will become clear in a second.
We omit explicit reference to index $n$ when there is no risk of confusion.

Recall that in 1-D PV, we consider a privileged point $x$ and a couple of
verifiers, $V_{A}$, $V_{B}$, at locations $x\pm\delta$. In the dishonest
scenario, that will be later considered, two cheaters hold locations
$x\pm\delta^{\prime}$ for some $0<\delta^{\prime}<\delta$. $G_{Rad}$ proceeds
as follows:

  1. 1.

The verifier prepares the state
$|\psi\rangle=\frac{1}{n}\sum_{i,j=1}^{n}|ij\rangle_{AB}\otimes|ij\rangle_{C}\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$
and distributes registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ to $V_{A}$.
He also chooses uniformly at random an $n^{2}$ dimensional sign vector
$\varepsilon=(\varepsilon_{ij})_{i,j=1}^{n}\in\mathcal{Q}_{n^{2}}$ and informs
$V_{B}$ of that choice.

  2. 2.

$V_{A}$ forwards the quantum system $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ to
the prover at $x$. From the other side, $V_{B}$ communicates the classical
information specifying the vector $\varepsilon$.

  3. 3.

After receiving both messages, a honest prover located at $x$ has to apply the
unitary $U_{\varepsilon}=diag(\varepsilon_{11},\ldots,\varepsilon_{nn})$ on
the received system $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ and forwards
$\mathcal{H}_{A}$ back to $V_{A}$ and $\mathcal{H}_{B}$ _to_ $V_{B}$.

  4. 4.

At some later time, $V_{A}$ and $V_{B}$ perform the joint measurement defined
by elements
$\big{\\{}|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|,\mathrm{Id}-|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|\big{\\}}$,
where we have defined
$|\psi_{\varepsilon}\rangle=U_{\varepsilon}\otimes\mathrm{Id}_{C}\,|\psi\rangle$.
The verification is correct if the outcome of this final measurement is the
one corresponding to $|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|$
and the registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ were received on
time.

Consider now a coalition of attackers, Alice and Bob, trying to impersonate
the honest prover intercepting the communication with $V_{A}$ and $V_{B}$ at
points $x-\delta^{\prime}$, $x+\delta^{\prime}$. As described in Section 2.3,
the cheaters’ action can be understood as Alice and Bob playing a
collaborative quantum game with suitable restrictions in their resources – we
consider the s2w scenario defined in Figure 1. The game associated with the PV
scheme above turns out to be a MROQG, as introduced in Section 2.3. This game,
which we also denote as $G_{Rad}$, is defined by tensors
$\big{\\{}G_{\varepsilon}:=\mathrm{Tr}_{C}|\psi_{\varepsilon}\rangle\langle\psi|=\frac{1}{n^{2}}\sum_{i,j=1}^{n}\varepsilon_{ij}|ij\rangle\langle
ij|\big{\\}}_{\varepsilon\in\mathcal{Q}_{n^{2}}}$ and the uniform probability
distribution over $\mathcal{Q}_{n^{2}}$. The game proceeds as follows:

  1. 1.

The referee prepares the state
$|\psi\rangle=\frac{1}{n}\sum_{i,j}^{n}|ij\rangle_{AB}\otimes|ij\rangle_{C}\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$
and samples uniformly at random an $n^{2}$ dimensional sign vector,
$\varepsilon=(\varepsilon_{ij})_{ij=1}^{n}\in\mathcal{Q}_{n^{2}}$.

  2. 2.

He sends registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ to Alice and the
classical description of $\varepsilon$ to Bob.

  3. 3.

Alice and Bob apply a quantum operation with the information received and send
to the referee quantum messages resulting from that operation. Register
$\mathcal{H}_{A}$ has to be communicated from Alice and $\mathcal{H}_{B}$ from
Bob. Their action is restricted to be of the form of Figure 1. We study in
detail this scenario below.

  4. 4.

The referee performs the measurement
$\\{|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|,\mathrm{Id}-|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|\\}$
on registers $\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$. He
declares the players winning when the outcome of this last measurement is the
one corresponding to $|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|$.

The main object of study in this work is the value of this game in the $s2w$
scenario, denoted by $\omega_{s2w}(G_{Rad})$. A strategy in this scenario is
determined by – cf. Figure 1 and Definition 2.8:

  * •

a shared entangled state
$\varphi\in\mathcal{D}(\mathcal{H}_{E_{a}}\otimes\mathcal{H}_{E_{b}})$ that we
assume here to be pure171717 It can be easily checked that, by convexity, the
value achieved in $G_{Rad}$ by strategies using mixed states is always upper
bounded by the value when using pure states. Since the quantity we are
interested in is the optimal value of the game, restricting ourselves to
strategies using pure states would be enough. . From now on we use
interchangeably the notations $\varphi$ or $|\varphi\rangle\langle\varphi|$ to
refer to that state;

  * •

a family – indexed on $\varepsilon$ – of tuples of four “local” channels:

for each $\varepsilon\in\mathcal{Q}_{n^{2}}$,

$\mathcal{A}\in\mathrm{CPTP}(\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{E_{a}},\mathcal{H}_{A\shortrightarrow
A}\otimes\mathcal{H}_{A\shortrightarrow
B}),\quad\mathcal{B}_{\varepsilon}\in\mathrm{CPTP}(\mathcal{H}_{E_{b}},\mathcal{H}_{B\shortrightarrow
B}\otimes\mathcal{H}_{B\shortrightarrow A}),$
$\tilde{\mathcal{A}}_{\varepsilon}\in\mathrm{CPTP}(\mathcal{H}_{A\shortrightarrow
A}\otimes\mathcal{H}_{B\shortrightarrow
A},\mathcal{H}^{\prime}_{A}),\quad\tilde{\mathcal{B}}_{\varepsilon}\in\mathrm{CPTP}(\mathcal{H}_{B\shortrightarrow
B}\otimes\mathcal{H}_{A\shortrightarrow B},\mathcal{H}^{\prime}_{B}).$

For verification, $\mathcal{H}^{\prime}_{A}$, $\mathcal{H}^{\prime}_{B}$
should be communicated to $V_{A}$ and $V_{B}$ respectively. Therefore,
according to the definition of the game, these registers should be isomorphic
to the originals $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$.

Understood as a family of quantum channels, the strategy defined by these
elements reads:

$\begin{array}[]{cccc}\mathcal{S}_{\varepsilon}:&\mathcal{D}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})&\longrightarrow&\mathcal{D}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})\\\\[10.00002pt]
&\psi&\mapsto&\mathcal{S}_{\varepsilon}(\psi)=(\tilde{\mathcal{A}}_{\varepsilon}\otimes\tilde{\mathcal{B}}_{\varepsilon})\circ(\mathcal{A}\otimes\mathcal{B}_{\varepsilon})(\psi\otimes\varphi)\end{array},$
(19)

for each $\varepsilon\in\mathcal{Q}_{n^{2}}$. The value attained by such a
strategy is given by (6), that is, denoting as $\mathfrak{S}_{s2w}$ the set of
strategies in the form (19):

$\displaystyle\omega_{s2w}(G_{Rad})$
$\displaystyle=\sup_{\\{\mathcal{S}_{\varepsilon}\\}_{\varepsilon}\in\mathfrak{S}_{s2w}}\omega(G_{Rad};\\{\mathcal{S}_{\varepsilon}\\}_{\varepsilon})$
(20) $\displaystyle=\sup_{\begin{subarray}{c}\mathcal{H}_{E_{a(b)}},\\\
\mathcal{H}_{A(B)\shortrightarrow A(B)},\,\mathcal{H}_{B(A)\shortrightarrow
A(B)}\end{subarray}}\
\sup_{\begin{subarray}{c}\tilde{\mathcal{A}}_{\varepsilon},\,\tilde{\mathcal{B}}_{\varepsilon},\,\mathcal{A},\,\mathcal{B}_{\varepsilon}\\\
\varphi\end{subarray}}\mathbb{E}_{\varepsilon}\
\omega\Big{(}G_{\varepsilon};(\tilde{\mathcal{A}}_{\varepsilon}\otimes\tilde{\mathcal{B}}_{\varepsilon})\circ(\mathcal{A}\otimes\mathcal{B}_{\varepsilon})(\,\cdot\,\otimes\varphi)\Big{)},$

where
$\tilde{\mathcal{A}}_{\varepsilon},\,\tilde{\mathcal{B}}_{\varepsilon},\,\mathcal{A},\,\mathcal{B}_{\varepsilon}$
and $\varphi$ in the last supremum are as indicated above. For future
reference, we recall here the expression of (6) in our particular case:
consider the strategy defined by the family of channels (19), then

$\displaystyle\omega(G_{Rad};\\{\mathcal{S}_{\varepsilon}\\}_{\varepsilon})$
$\displaystyle:=\mathbb{E}_{\varepsilon}\
\mathrm{Tr}\left[\>|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|\,(\mathrm{Id}_{C}\otimes\mathcal{S}_{\varepsilon})(|\psi\rangle\langle\psi|)\>\right],$
(21)

where
$|\psi_{\varepsilon}\rangle=\frac{1}{n}\sum_{i,j}^{n}\,\varepsilon_{ij}\,|i\rangle\otimes|j\rangle\otimes|ij\rangle,\,|\psi\rangle=\frac{1}{n}\sum_{i,j}^{n}|i\rangle\otimes|j\rangle\otimes|ij\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$.

In this language, the existence of general attacks for arbitrary PV schemes
translates into the coincidence of the value in the $s2w$ scenario with the
honest value181818 In fact this coincidence holds in general for any MROQG.:

$\omega_{s2w}(G_{Rad})=\omega_{H}(G_{Rad})=1.$ (22)

As we said in the introduction, the main question we are interested in is the
amount of entanglement necessary to establish this equality. It is natural
then to define a restricted version of $\omega_{s2w}(G_{Rad})$ considering
only strategies using a limited amount of resources. Here, we restrict the
local dimension at any time during the protocol: for
$\tilde{k},\,k\in\mathbb{N}$ we define:

$\displaystyle\omega_{s2w;\tilde{k},k}(G_{Rad}):=\sup_{\begin{subarray}{c}\tilde{\mathcal{A}}_{\varepsilon},\,\tilde{\mathcal{B}}_{\varepsilon},\,\mathcal{A},\,\mathcal{B}_{\varepsilon}\\\
\varphi\in\mathcal{D}(\mathbb{C}^{k}\otimes\mathbb{C}^{k})\end{subarray}}\mathbb{E}_{\varepsilon}\
\omega\Big{(}G_{\varepsilon};(\tilde{\mathcal{A}}_{\varepsilon}\otimes\tilde{\mathcal{B}}_{\varepsilon})\circ(\mathcal{A}\otimes\mathcal{B}_{\varepsilon})(\,\cdot\,\otimes\varphi)\Big{)},$
(23)

where we restrict

$\dim(\mathcal{H}_{E_{a(b)}})\leq
k,\qquad\dim(\mathcal{H}_{A(B)\shortrightarrow
A(B)})\times\dim(\mathcal{H}_{A(B)\shortrightarrow B(A)})\leq\tilde{k}.$

I.e., we restrict, for each $\varepsilon\in\mathcal{Q}_{n^{2}}$,

$\mathcal{A}\in\mathrm{CPTP}(\ell_{2}^{n^{2}k},\,\ell_{2}^{\tilde{k}}),\quad\mathcal{B}_{\varepsilon}\in\mathrm{CPTP}(\ell_{2}^{k},\,\ell_{2}^{\tilde{k}}),$
$\tilde{\mathcal{A}}_{\varepsilon}\in\mathrm{CPTP}(\ell_{2}^{\tilde{k}},\,\ell_{2}^{n}),\quad\tilde{\mathcal{B}}_{\varepsilon}\in\mathrm{CPTP}(\ell_{2}^{\tilde{k}},\,\ell_{2}^{n}).$

Clearly,

$\lim_{\tilde{k},k\shortrightarrow\infty}\omega_{s2w;\tilde{k},k}(G_{Rad})=\omega_{s2w}(G_{Rad})=\omega_{H}(G_{Rad}).$
(24)

We want to study the rate of convergence of this limit. To the best of our
knowledge, it is not even known whether the limit is in general attained for
finite $k,\,\tilde{k}$. We worry about lower bounds in $k,\,\tilde{k}$ to
achieve a given degree of approximation in (24). More precisely, we lower
bound the difference $\omega_{H}(G_{Rad})-\omega_{s2w;\tilde{k},k}(G_{Rad})$
in terms of $k,\,\tilde{k}$ and properties of the strategies considered.
However, we postpone those results until Section 4. Before that, we need to
provide here two reductions to the kind of strategies we consider in order to
prepare the ground for next section.

###  3.1 Use of classical communication in cheating strategies

First, we consider the role of classical communication between Alice and Bob.
In our model, we regard this resource as free and, in fact, we built into the
structure of the considered strategies the free communication of the classical
information about $\varepsilon$ (in the second round of local operations this
parameter was considered as public). This is justified by the fact that our
interest is in bounding the _quantum_ resources used for attacking $G_{Rad}$,
which are assumed to be much more expensive than classical communication.
However, there is a potential problem with this approach. That is the
possibility of the players using further classical communication apart from
that of $\varepsilon$ – _extra classical communication_ from now on –. In our
model, this extra classical communication would be included in the definition
of the channels $\mathcal{A}$ and $\mathcal{B}_{\varepsilon}$. In the
$\mathfrak{S}_{s2w,\tilde{k},k}$ scenario, this would affect the dimension
$\tilde{k}$ being no longer a reliable witness for the quantum resources spent
by a given strategy: $\tilde{k}$ would also include the dimension of the extra
classical messages shared by Alice and Bob. Nonetheless, we show that the
amount of _useful_ extra classical communication in our setting is bounded by
the initial dimension of the quantum system manipulated by the players, that
is, by $k$ and $n$. The following lemma let us to control the contribution of
the classical part of players action to $\tilde{k}$.

######  Lemma 3.1.

The optimization over $\mathcal{S}\in\mathfrak{S}_{s2w,\tilde{k},k}$ in (23)
can be restricted to strategies using extra classical communication of local
dimension $\tilde{k}_{cl}\leq n^{4}k^{2}$.

###### Proof.

The result follows from convexity taking into account that the extreme points
of the set of instruments acting on a given Hilbert space of dimension $d$ has
at most $d^{2}$ outcomes. See, for instance, [9, Rmk. 7.9., p.158].

Consider an arbitrary strategy
$\mathcal{S}=\\{\tilde{\mathcal{A}}_{\varepsilon},\tilde{\mathcal{B}}_{\varepsilon},\mathcal{A},\mathcal{B}_{\varepsilon},\varphi\\}\in\mathfrak{S}_{s2w,m,k}$
using extra classical communication of local dimension $m_{cl}$. The
dimensions $m$, $m_{cl}$ are free parameters that will fixed at the end of the
proof. Therefore, we can further specify these classical messages in the
structure of the channels $\mathcal{A}$ and $\mathcal{B}_{\varepsilon}$:

$\mathcal{A}(\,\cdot\,)=\sum_{c_{a}=1}^{m_{cl}}\mathcal{A}^{c_{a}}(\,\cdot\,)\otimes|c_{a}\rangle\langle
c_{a}|\quad:\quad\mathcal{A}^{c_{a}}\in\mathrm{CP}(\ell_{2}^{n^{2}k},\ell_{2}^{m/m_{cl}})\text{
for any }c_{a},$
$\mathcal{B}_{\varepsilon}(\,\cdot\,)=\sum_{c_{b}=1}^{m_{cl}}\mathcal{B}_{\varepsilon}^{c_{b}}(\,\cdot\,)\otimes|c_{b}\rangle\langle
c_{b}|\quad:\quad\mathcal{B}^{c_{b}}_{\varepsilon}\in\mathrm{CP}(\ell_{2}^{k},\ell_{2}^{m/m_{cl}})\text{
for any }c_{b}.$

These expressions are nothing else than the description of some instruments in
$\mathrm{Ins}(\ell_{2}^{k},\ell_{2}^{m/m_{cl}})$
($\mathrm{Ins}(\ell_{2}^{n^{2}k},\ell_{2}^{m/m_{cl}})$ in the first case) with
$m_{cl}$ outcomes each. As we said before, the extreme points of
$\mathrm{Ins}(\ell_{2}^{k},\ell_{2}^{m/m_{cl}})$ consist of instruments with
at most $k^{2}$ outcomes ($n^{4}k^{2}$ in the first case). Therefore, we can
rewrite the channels $\mathcal{A}$, $\mathcal{B}_{\varepsilon}$ as a convex
combination of such extreme points:

$\mathcal{A}(\,\cdot\,)=\sum_{s}\alpha_{s}\mathcal{A}_{s}(\,\cdot\,),$
$\mathcal{B}_{\varepsilon}(\,\cdot\,)=\sum_{s}\beta_{\varepsilon,s}\mathcal{B}_{\varepsilon,s}(\,\cdot\,),$

where, for each $s,\,\varepsilon$:

  * •

$0\leq\alpha_{s},\,\beta_{\varepsilon,s}\leq 1$ :
$\sum_{s}\alpha_{s}=1=\sum_{s}\beta_{\varepsilon,s}$;

  * •

$\mathcal{A}_{s}\in\mathrm{Ins}(\ell_{2}^{n^{4}k^{2}},\ell_{2}^{m/m_{cl}})$,
$\mathcal{B}_{\varepsilon;s}\in\mathrm{Ins}(\ell_{2}^{k},\ell_{2}^{m/m_{cl}})$
with at most $n^{4}k^{2}$ and $k^{2}$ outcomes, respectively. For simplicity
we just fix $\tilde{k}_{cl}$ bounded by the largest of these bounds,
$\tilde{k}_{cl}\leq n^{4}k^{2}$.

Denote $\mathcal{S}_{s,s^{\prime}}$ the strategy specified by elements
$\\{\tilde{\mathcal{A}}_{\varepsilon},\tilde{\mathcal{B}}_{\varepsilon},\mathcal{A}_{s},\mathcal{B}_{\varepsilon,s^{\prime}},\varphi\\}_{\varepsilon}$
and $\mathcal{S}_{\varepsilon;s,s^{\prime}}(\,\cdot\,)$ the corresponding
channels, defined by the generic prescription (19). Notice that
$\mathcal{S}_{\varepsilon}(\,\cdot\,)=\sum_{s,s^{\prime}}\,\alpha_{s}\beta_{s^{\prime}}\,\mathcal{S}_{\varepsilon;s,s^{\prime}}(\,\cdot\,)$.
Now, focus on the value achieved in $G_{Rad}$. It turns out that
$\omega(G_{Rad};\mathcal{S})$ is linear in $\mathcal{S}$, fact that allows us
to write:

$\omega(G_{Rad};\mathcal{S})=\sum_{s}\alpha_{s}\,\mathbb{E}_{\varepsilon}\,\sum_{s^{\prime}}\,\beta_{\varepsilon,s}\,\omega(G_{Rad};\\{\mathcal{S}_{\varepsilon;s,s^{\prime}}\\}_{\varepsilon})\leq\max_{s}\left\\{\mathbb{E}_{\varepsilon}\max_{s^{\prime}}\left\\{\omega(G_{Rad};\\{\mathcal{S}_{\varepsilon;s,s^{\prime}}\\}_{\varepsilon})\right\\}\right\\}.$

Denoting $s^{*}$, ${s^{\prime}_{\varepsilon}}^{*}$ the indexes at which the
maxima above are attained, the strategy
$\\{\tilde{\mathcal{A}}_{\varepsilon},\tilde{\mathcal{B}}_{\varepsilon},$
$\mathcal{A}_{s^{*}},\mathcal{B}_{\varepsilon,{s^{\prime}_{\varepsilon}}^{*}},\varphi\\}_{\varepsilon}$,
that uses extra classical communication of local dimension at most
$\tilde{k}_{cl}\leq n^{4}k^{2}$, can be now regarded as an element in
$\mathfrak{S}_{s2w;\tilde{k},k}$ with $\tilde{k}=m\tilde{k}_{cl}/m_{cl}$. This
proves the claim.

∎

###  3.2 Pure strategies

The second reduction consist on purifying arbitrary strategies. We start
fixing some notation. We say that a strategy
$\mathcal{S}=\\{\tilde{\mathcal{A}}_{\varepsilon},\tilde{\mathcal{B}}_{\varepsilon},\mathcal{A},\mathcal{B}_{\varepsilon},\varphi\\}_{\varepsilon}\in\mathfrak{S}_{s2w}$
is _pure_ if the channels
$\tilde{\mathcal{A}}_{\varepsilon},\tilde{\mathcal{B}}_{\varepsilon},\mathcal{A},\mathcal{B}_{\varepsilon}$
can be written as:

$\displaystyle\mathcal{A}(\,\cdot\,)$ $\displaystyle=V(\,\cdot\,)V^{\dagger},$
$\displaystyle\mathcal{B}_{\varepsilon}(\,\cdot\,)$
$\displaystyle=W_{\varepsilon}(\,\cdot\,)W_{\varepsilon}^{\dagger},$ (25)
$\displaystyle\tilde{\mathcal{A}}_{\varepsilon}(\,\cdot\,)$
$\displaystyle=\mathrm{Tr}_{anc_{a}}\,\tilde{V}_{\varepsilon}(\,\cdot\,)\tilde{V}_{\varepsilon}^{\dagger},$
$\displaystyle\tilde{\mathcal{B}}_{\varepsilon}(\,\cdot\,)$
$\displaystyle=\mathrm{Tr}_{anc_{b}}\,\tilde{W}_{\varepsilon}(\,\cdot\,)\tilde{W}_{\varepsilon}^{\dagger},$
(26)

for some contractive operators

$V:\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{E_{a}}\longrightarrow\mathcal{H}_{A\shortrightarrow
A}\otimes\mathcal{H}_{A\shortrightarrow B},\qquad
W_{\varepsilon}:\mathcal{H}_{E_{b}}\longrightarrow\mathcal{H}_{B\shortrightarrow
B}\otimes\mathcal{H}_{B\shortrightarrow A},$
$\tilde{V}_{\varepsilon}:\mathcal{H}_{A\shortrightarrow
A}\otimes\mathcal{H}_{B\shortrightarrow
A}\longrightarrow\mathcal{H}_{A}\otimes\mathcal{H}_{anc_{a}},\qquad\tilde{W}_{\varepsilon}:\mathcal{H}_{B\shortrightarrow
B}\otimes\mathcal{H}_{A\shortrightarrow
B}\longrightarrow\mathcal{H}_{B}\otimes\mathcal{H}_{anc_{b}},$

being $\mathcal{H}_{anc_{a}}$, $\mathcal{H}_{anc_{b}}$ arbitrary ancillary
Hilbert spaces. In the restricted scenario s2w;$\tilde{k},k$, these operators
are of the form:

$V:\ell_{2}^{n^{2}k}\longrightarrow\ell_{2}^{\tilde{k}},\qquad
W_{\varepsilon}:\ell_{2}^{k}\longrightarrow\ell_{2}^{\tilde{k}},\qquad\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon}:\ell_{2}^{\tilde{k}}\longrightarrow\ell_{2}^{nr},$
(27)

being $r$ some natural number. For convenience, we identify pure strategies
with families of such _pure_ objects, setting the notation
$\mathcal{S}^{\mathcal{U}}=\\{\tilde{V}_{\varepsilon},\tilde{W}_{\varepsilon},V,W_{\varepsilon},|\varphi\rangle\\}_{\varepsilon}$.

We further denote $\mathfrak{S}^{\mathcal{U}}_{s2w}$ the subset of pure
strategies in the s2w scenario and
$\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k},k}$ the corresponding subset in the
model with limited dimension. Due to Stinespring’s dilation theorem [42], it
turns out that $\mathfrak{S}^{\mathcal{U}}_{s2w}=\mathfrak{S}_{s2w}$. However,
when we restrict the dimension of the considered strategies, the situation is
a bit subtler and the Stinespring’s dilation of the channels involved affects
the relevant dimensions defining the models $\mathfrak{S}_{s2w;\tilde{k},k}$
and $\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k},k}$. This is taken care of by
the following lemma:

######  Lemma 3.2.

Any strategy $\mathcal{S}\in\mathfrak{S}_{s2w;\tilde{k},k}$ can be regarded as
a pure strategy
$\mathcal{S}^{\mathcal{U}}\in\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k}^{\prime},k}$
where $\tilde{k}^{\prime}\leq n^{2}k\tilde{k}^{4}.$ That is, the chain of
containments
$\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k},k}\subseteq\mathfrak{S}_{s2w;\tilde{k},k}\subseteq\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k}^{\prime},k}$
holds.

###### Proof.

Set a strategy
$\mathcal{S}=\\{\tilde{\mathcal{A}}_{\varepsilon},\tilde{\mathcal{B}}_{\varepsilon},\mathcal{A},\mathcal{B}_{\varepsilon},\varphi\\}$
in $\mathfrak{S}_{s2w;\tilde{k},k}$.

We are going to consider Stinespring’s dilations to purify the corresponding
channels

$\mathcal{S}_{\varepsilon}(\,\cdot\,)=(\tilde{\mathcal{A}}_{\varepsilon}\otimes\tilde{\mathcal{B}}_{\varepsilon})\circ(\mathcal{A}\otimes\mathcal{B}_{\varepsilon})(\,\cdot\,\otimes\varphi).$
(28)

We start with

$\tilde{\mathcal{A}}_{\varepsilon},\,\tilde{\mathcal{B}}_{\varepsilon}\in\mathrm{CPTP}(\ell_{2}^{\tilde{k}},\,\ell_{2}^{n}).$

These channels can be lifted (due to a Stinespring’s dilation) to be of the
form:

$\tilde{\mathcal{A}}_{\varepsilon}(\,\cdot\,)=\mathrm{Tr}_{\widetilde{anc}}\tilde{V}_{\varepsilon}(\,\cdot\,)\tilde{V}_{\varepsilon}^{\dagger},\qquad\tilde{\mathcal{B}}_{\varepsilon}(\,\cdot\,)=\mathrm{Tr}_{\widetilde{anc}}\tilde{W}_{\varepsilon}(\,\cdot\,)\tilde{W}_{\varepsilon}^{\dagger},$

where
$\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon}:\ell_{2}^{\tilde{k}}\longrightarrow\ell_{2}^{n}\otimes\mathcal{H}_{\widetilde{anc}}$
are Stinespring’s isometries and $\dim(\mathcal{H}_{\widetilde{anc}})$ can be
upper bounded by $n\tilde{k}$.

Proceeding similarly with
$\mathcal{A}\in\mathrm{CPTP}(\ell_{2}^{n^{2}k},\,\ell_{2}^{\tilde{k}})$ and
$\mathcal{B}_{\varepsilon}\in\mathrm{CPTP}(\ell_{2}^{k},\,\ell_{2}^{\tilde{k}})$
we obtain:

$\mathcal{A}(\,\cdot\,)=\mathrm{Tr}_{anc_{1}}V(\,\cdot\,)V^{\dagger},\qquad\mathcal{B}_{\varepsilon}(\,\cdot\,)=\mathrm{Tr}_{anc_{2}}W_{\varepsilon}(\,\cdot\,)W_{\varepsilon}^{\dagger},$

for Stinespring’s dilations
$V:\ell_{2}^{n^{2}k}\longrightarrow\ell_{2}^{\tilde{k}}\otimes\mathcal{H}_{anc_{1}}$,
$W_{\varepsilon}:\ell_{2}^{k}\longrightarrow\ell_{2}^{\tilde{k}}\otimes\mathcal{H}_{anc_{2}}$
such that $\dim(\mathcal{H}_{anc_{1}})\leq n^{2}k\tilde{k}$,
$\dim(\mathcal{H}_{anc_{2}})\leq k\tilde{k}$.

With all that, and denoting
$\mathcal{H}_{anc_{a}}\equiv\mathcal{H}_{anc_{1}}\otimes\mathcal{H}_{\widetilde{anc}}$,
$\mathcal{H}_{anc_{b}}\equiv\mathcal{H}_{anc_{2}}\otimes\mathcal{H}_{\widetilde{anc}}$,
we define the channels

$\displaystyle\tilde{\mathcal{A}}_{\varepsilon}^{\mathcal{U}}(\,\cdot\,)$
$\displaystyle:=\mathrm{Tr}_{anc_{a}}(\tilde{V}_{\varepsilon}\otimes\mathrm{Id}_{anc_{1}})\,(\,\cdot\,)\,(\tilde{V}_{\varepsilon}^{\dagger}\otimes\mathrm{Id}_{anc_{1}}),$
$\displaystyle\tilde{\mathcal{B}}_{\varepsilon}^{\mathcal{U}}(\,\cdot\,)$
$\displaystyle:=\mathrm{Tr}_{anc_{b}}(\tilde{W}_{\varepsilon}\otimes\mathrm{Id}_{anc_{2}})\,(\,\cdot\,)\,(\tilde{W}_{\varepsilon}^{\dagger}\otimes\mathrm{Id}_{anc_{2}}),$
$\mathcal{A}^{\mathcal{U}}(\,\cdot\,):=V_{\varepsilon}(\,\cdot\,)V_{\varepsilon}^{\dagger},\qquad\mathcal{B}_{\varepsilon}^{\mathcal{U}}(\,\cdot\,):=W_{\varepsilon}(\,\cdot\,)W_{\varepsilon}^{\dagger}.$

Then, we can rewrite (28) as:

$\mathcal{S}_{\varepsilon}(\,\cdot\,)=(\tilde{\mathcal{A}}^{\mathcal{U}}_{\varepsilon}\otimes\tilde{\mathcal{B}}^{\mathcal{U}}_{\varepsilon})\circ(\mathcal{A}^{\mathcal{U}}\otimes\mathcal{B}^{\mathcal{U}}_{\varepsilon})(\,\cdot\,\otimes|\varphi\rangle\langle\varphi|).$

But clearly the strategy
$\mathcal{S}^{\mathcal{U}}:=\\{\tilde{\mathcal{A}}_{\varepsilon}^{\mathcal{U}},\tilde{\mathcal{B}}_{\varepsilon}^{\mathcal{U}},\mathcal{A}^{\mathcal{U}},\mathcal{B}_{\varepsilon}^{\mathcal{U}},\varphi\\}_{\varepsilon}$
is pure, finishing the proof of the lemma. A careful look at the definition of
the channels defining $\mathcal{S}^{\mathcal{U}}$ reveals that
$\mathcal{S}^{\mathcal{U}}\in\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k}^{\prime},k}$
with $\tilde{k}^{\prime}\leq n^{2}k\tilde{k}^{2}.$

∎

With Lemmas 3.1 and 3.2 at hand we can focus now in the study of strategies in
$\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k}^{\prime},k}$. Given a general
strategy $\mathcal{S}\in\mathfrak{S}_{s2w;\tilde{k},k}$, Lemma 3.1 guarantees
that $\mathcal{S}$ can be taken such that the dimension of the classical
resources used is upper bounded by

$\tilde{k}_{cl}\leq n^{4}k^{2}.$ (29)

Then, Lemma 3.2 allows us to relate $\mathcal{S}$ with a pure strategy
$\mathcal{S}^{\mathcal{U}}\in\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k}^{\prime},k}$
such that

$\tilde{k}^{\prime}\leq n^{2}k\tilde{k}^{2}.$ (30)

Accordingly, in the rest of this manuscript we work in the model
$\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k}^{\prime},k}$ redirecting the reader
to (30) and (29) for the relation with the resources used by more general
strategies. However, notice that these correspondences are at most polynomial
in $n$, $k$ and $\tilde{k}$ and, in fact, will only introduce corrections by
constant factors in the bounds we state later on. In this sense, the precise
exponents in (30), (29) are irrelevant. This will become clearer in the next
section.

For convenience, we finish this section recalling the expression of
$\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})$, Equation (21), particularized for
pure strategies
$\mathcal{S}^{\mathcal{U}}=\\{\tilde{V}_{\varepsilon},\tilde{W}_{\varepsilon},V,W_{\varepsilon},\varphi\\}$:

$\displaystyle\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})$
$\displaystyle=\mathbb{E}_{\varepsilon}\
\mathrm{Tr}\left[\>|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|\,(\mathrm{Id}_{C}\otimes\mathcal{S}^{\mathcal{U}}_{\varepsilon})\>\big{(}|\psi\rangle\langle\psi|\big{)}\>\right],$
(31)

where now:

$\mathcal{S}_{\varepsilon}^{\mathcal{U}}(\,\cdot\,)=\mathrm{Tr}_{\mathcal{H}_{anc_{a}\otimes
anc_{b}}}\,\left[(\tilde{V}_{\varepsilon}\otimes\tilde{W}_{\varepsilon})\,(V\otimes
W_{\varepsilon})\,(\,\cdot\,\otimes|\varphi\rangle\langle\varphi|)\,(V^{\dagger}\otimes
W_{\varepsilon}^{\dagger})\,(\tilde{V}_{\varepsilon}^{\dagger}\otimes\tilde{W}_{\varepsilon}^{\dagger})\right].$

Notice that for strategies in the more specific model
$\mathfrak{S}_{s2w;\tilde{k}^{\prime},k}^{\mathcal{U}}$, the operators
$\tilde{V}_{\varepsilon},\tilde{W}_{\varepsilon},V,W_{\varepsilon}$ are
specified as in (27) and, therefore, $\mathcal{H}_{anc_{a}}$ and
$\mathcal{H}_{anc_{b}}$ in this case are identified with $\ell_{2}^{r}$ for
some $r\in\mathbb{N}$.

######  Remark 3.3.

Alternatively, (31) can be rewritten as:

$\displaystyle\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})$
$\displaystyle=\,\mathbb{E}_{\varepsilon}\,\Big{\|}\frac{1}{n^{2}}\sum_{i,j}\varepsilon_{ij}(\langle
i|\tilde{V}_{\varepsilon}\otimes\langle
j|\tilde{W}_{\varepsilon})\,(V|ij\rangle\otimes
W_{\varepsilon})\,|\varphi\rangle\Big{\|}^{2}_{\mathcal{H}_{anc_{a}}\otimes\mathcal{H}_{anc_{b}}}.$
(32)

As commented before, in the
$\mathfrak{S}_{s2w;\tilde{k}^{\prime},k}^{\mathcal{U}}$ scenario,
$\mathcal{H}_{anc_{a}}\otimes\mathcal{H}_{anc_{b}}=\ell_{2}^{r^{2}}$.

Before showing the easy proof of this claim, let us clarify the notation used
above. By $V|ij\rangle$ we mean the operator $V\in
M_{\tilde{k}^{\prime},n^{2}k}$ with its indices corresponding to
$\ell_{2}^{n^{2}}$ contracted with the vector $|ij\rangle$. That is, if we
expand $V$ on its coordinates,
$V=\sum_{k,l=1}^{n}\sum_{m=1}^{k}\sum_{p}^{\tilde{k}^{\prime}}V_{p,klm}|p\rangle\langle
klm|$, and then
$V|ij\rangle=\sum_{m=1}^{k}\sum_{p}^{\tilde{k}^{\prime}}V_{p,ijm}|p\rangle\langle
m|\in M_{\tilde{k}^{\prime},k}$. Similarly with $\langle
i|\tilde{V}_{\varepsilon}$ and $\langle j|\tilde{W}_{\varepsilon}$.

###### Proof.

The proof is completely elementary and follows the next lines:

In first place, we notice that for any vectors $|\xi\rangle\in\mathcal{H}$,
$|\eta\rangle\in\mathcal{H}^{\prime}$ and any operator
$U\in\mathcal{B}(\mathcal{H}^{\prime},\mathcal{H}\otimes\mathcal{K})$

$\displaystyle\mathrm{Tr}\left[|\xi\rangle\langle\xi|\,\mathrm{Tr}_{\mathcal{K}}U\,|\eta\rangle\langle\eta|\,U^{\dagger}\right]$
$\displaystyle=\mathrm{Tr}\left[(|\xi\rangle\langle\xi|\otimes\mathrm{Id}_{\mathcal{K}})\,U\,|\eta\rangle\langle\eta|\,U^{\dagger}\right]$
$\displaystyle=\langle\eta|U^{\dagger}(|\xi\rangle\otimes\mathrm{Id}_{\mathcal{K}})\
(\langle\xi|\otimes\mathrm{Id}_{\mathcal{K}})\,U\,|\eta\rangle$
$\displaystyle=\big{\|}(\langle\xi|\otimes\mathrm{Id}_{\mathcal{K}})\,U\,|\eta\rangle\big{\|}^{2}_{\mathcal{K}}.$

Applying this elementary identity to
$|\psi_{\varepsilon}\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}\equiv\mathcal{H}$,
$|\psi\rangle\otimes|\varphi\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}\otimes\mathcal{H}_{E}\equiv\mathcal{H}^{\prime}$
and the operator
$\mathrm{Id}_{C}\otimes(\tilde{V}_{\varepsilon}\otimes\tilde{W}_{\varepsilon})\,(V\otimes
W_{\varepsilon})\in\mathcal{B}(\mathcal{H}^{\prime},\mathcal{H}\otimes\mathcal{H}_{anc_{a}}\otimes\mathcal{H}_{anc_{b}})$
we have that, for each $\varepsilon\in\mathcal{Q}_{n^{2}}$:

$\displaystyle\mathrm{Tr}\left[\>|\psi_{\varepsilon}\rangle\langle\psi_{\varepsilon}|\,(\mathrm{Id}_{C}\otimes\mathcal{S}^{\mathcal{U}}_{\varepsilon})\>\big{(}|\psi\rangle\langle\psi|\big{)}\>\right]$
$\displaystyle\qquad=\,\mathbb{E}_{\varepsilon}\,\left\|(\langle\psi_{\varepsilon}|\otimes\mathrm{Id}_{anc_{a}\otimes
anc_{b}})\left(\mathrm{Id}_{C}\otimes(\tilde{V}_{\varepsilon}\otimes\tilde{W}_{\varepsilon})\,(V\otimes
W_{\varepsilon})\right)\,(|\psi\rangle\otimes|\varphi\rangle)\right\|^{2}_{\mathcal{H}_{anc_{a}}\otimes\mathcal{H}_{anc_{b}}}.$

Equation (32) is obtained from the last line above just recalling the
definitions
$|\psi_{\varepsilon}\rangle=\frac{1}{n}\sum_{i,j=1}^{n}\varepsilon_{ij}|ij\rangle_{AB}\otimes|ij\rangle_{C}$
and
$|\psi\rangle=\frac{1}{n}\sum_{i,j=1}^{n}|ij\rangle_{AB}\otimes|ij\rangle_{C}$.
∎

##  4 Bounds for “smooth” strategies. Theorem 1.1

This section is devoted to the proof of Theorem 1.1, which provides lower
bounds on resources needed to break $G_{Rad}$ by strategies characterized by
regularity measures based on parameter $\sigma$ defined in Section 2.4.3. When
we refer here to a cheating strategy for $G_{Rad}$, unless the opposite is
explicitly specified, we mean a pure strategy
$\mathcal{S}^{\mathcal{U}}=\\{\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon},\,V,\,W_{\varepsilon},\,|\varphi\rangle\\}_{\varepsilon}\in\mathfrak{S}^{\mathcal{U}}_{s2w;\tilde{k}^{\prime},k}$.

As explained in the introduction, the main idea leading to Theorem 1.1 is the
understanding of cheating strategies for $G_{Rad}$ as assignments on the
hypercube $\mathcal{Q}_{n^{2}}$, i.e., vector-valued functions
$\Phi:\mathcal{Q}_{n^{2}}\rightarrow X$ where $X$ is a suitable Banach space.
Given a strategy $\mathcal{S}^{\mathcal{U}}$, the corresponding assignment
$\Phi_{\mathcal{S}^{\mathcal{U}}}$ must be related with the value
$\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})$. Ideally, we hope to bound
$\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})$ with the expected value of the
norm of $\Phi_{\mathcal{S}^{\mathcal{U}}}$, quantity for which we can use
Corollary 2.24 to obtain upper bounds. Equation (32) gives us a first hint on
how to construct $\Phi_{\mathcal{S}^{\mathcal{U}}}$. Given
$\mathcal{S}^{\mathcal{U}}=\\{\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon},\,V,\,W_{\varepsilon},\,|\varphi\rangle\\}_{\varepsilon}$,
consider the map:

$\begin{array}[]{rccc}\Phi_{\mathcal{S}^{\mathcal{U}}}:&\mathcal{Q}_{n^{2}}&\longrightarrow&\ell_{2}^{r^{2}}\\\\[10.00002pt]
&\varepsilon&\mapsto&\Phi^{i}_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)=\frac{1}{n^{2}}\,\sum_{ij}\,\,\varepsilon_{ij}\,(\langle
i|\tilde{V}_{\varepsilon}\otimes\langle
j|\tilde{W}_{\varepsilon})\,(V|ij\rangle\otimes W)|\varphi\rangle\end{array},$
(33)

where $r$ is determined by the strategy, recall (27).

The referred Equation (32) now reads:

$\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})=\mathbb{E}_{\varepsilon}\|\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\|_{\ell_{2}^{r^{2}}}^{2},$
(34)

so we are in good track. Considering the trivial bound
$\mathbb{E}_{\varepsilon}\|\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\|_{\ell_{2}^{r^{2}}}^{2}\leq\mathbb{E}_{\varepsilon}\|\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\|_{\ell_{2}^{r^{2}}}$
and Corollary 2.24, we can obtain – recall Definition 2.21 for
$\sigma_{\Phi_{\mathcal{S}^{\mathcal{U}}}}$:

$\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})\leq\big{\|}\mathbb{E}_{\varepsilon}\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\big{\|}_{\ell_{2}^{r^{2}}}+C\
\sigma_{\Phi_{\mathcal{S}^{\mathcal{U}}}}\mathrm{T}^{(n^{2})}_{2}(\ell_{2}^{r^{2}}).$

Furthermore, $\mathrm{T}^{(n^{2})}_{2}(\ell_{2}^{r^{2}})=1$ since, more
generally, $\mathrm{T}_{2}(\ell_{2}^{r^{2}})=1$.

The main problem with this approach is that the quantity
$\big{\|}\mathbb{E}_{\varepsilon}\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\big{\|}_{\ell_{2}^{r^{2}}}$
might be of the same order as $\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})$,
making the previous bound trivial. The reason is that, if the strategy is near
optimal, that is, $\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})\approx 1$, for
most $\varepsilon\in\mathcal{Q}_{n^{2}}$,
$\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)$ is a vector with Euclidean
norm $\approx 1$. Then, we can easily modify the map
$\Phi_{\mathcal{S}^{\mathcal{U}}}$ _without increasing_ any relevant dimension
composing $\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)$ with an
$\varepsilon$ dependent unitary that “aligns” all vectors
$\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)$ in the same direction. For
this modified map,
$\big{\|}\mathbb{E}_{\varepsilon}\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\big{\|}_{\ell_{2}^{r^{2}}}=\mathbb{E}_{\varepsilon}\big{\|}\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\big{\|}_{\ell_{2}^{r^{2}}}=\omega(G_{Rad};\mathcal{S}^{\mathcal{U}}).$
The approach presented so far is unable to detect such an artefact, so we now
look at alternative constructions for $\Phi_{\mathcal{S}^{\mathcal{U}}}$.

What we do next, is simplifying the image of the map
$\Phi_{\mathcal{S}^{\mathcal{U}}}$ considering more involved choices for the
output Banach space. This allows us to preserve an equivalence of the kind of
(34) while obtaining good upper bounds for
$\big{\|}\mathbb{E}_{\varepsilon}\Phi_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\big{\|}_{X}$.

Given a strategy
$\mathcal{S}^{\mathcal{U}}=\\{\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon},\,V,\,W_{\varepsilon},\,|\varphi\rangle\\}_{\varepsilon}$
we define the following two alternatives to
$\Phi_{\mathcal{S}^{\mathcal{U}}}$:

$\begin{array}[]{rccc}\Phi^{i}_{\mathcal{S}^{\mathcal{U}}}:&\mathcal{Q}_{n^{2}}&\longrightarrow&M_{r^{2},k\tilde{k}^{\prime}}\\\\[10.00002pt]
&\varepsilon&\mapsto&\Phi^{i}_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)=\frac{1}{n^{2}}\,\sum_{ij}\,\,\varepsilon_{ij}\,(\langle
i|\tilde{V}_{\varepsilon}\otimes\langle
j|\tilde{W}_{\varepsilon})\,(V|ij\rangle\otimes\mathrm{Id}_{\ell_{2}^{\tilde{k}^{\prime}}}),\\\\[20.00003pt]
\Phi^{ii}_{\mathcal{S}^{\mathcal{U}}}:&\mathcal{Q}_{n^{2}}&\longrightarrow&\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}\otimes_{(\varepsilon,\pi)_{\nicefrac{{1}}{{2}}}}\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}\\\\[10.00002pt]
&\varepsilon&\mapsto&\Phi^{ii}_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)=\frac{1}{n^{2}}\,\sum_{ij}\,\,\varepsilon_{ij}\,\langle
i|\otimes\langle j|\otimes(V|ij\rangle\otimes
W_{\varepsilon})\,|\varphi\rangle.\end{array}$

These are the central objects we study to obtain Theorem 1.1. Recall that the
output space in $\Phi^{ii}_{\mathcal{S}^{\mathcal{U}}}$ was defined at the end
of Section 2.4.3 as the interpolation space
$(\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}\otimes_{\varepsilon}\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n},\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}\otimes_{\pi}\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n})_{1/2}$.

Now we comment on the idea behind the definitions of these maps: recall that a
strategy
$\mathcal{S}^{\mathcal{U}}=\\{\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon},\,V,\,W_{\varepsilon},\,|\varphi\rangle\\}_{\varepsilon}$
consists of two rounds of local operations with a communication stage in
between. Fixing the first round, that is related to $V,\,W_{\varepsilon}$ and
$|\varphi\rangle$, and understanding the optimization over any
$\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon}$ as computing a particular
norm leads to define $\Phi^{ii}_{\mathcal{S}^{\mathcal{U}}}$. When we fix
$\tilde{V}_{\varepsilon},\,\tilde{W}_{\varepsilon}$ and $V$ – this last one is
$\varepsilon$-independent –, optimizing then over any possible
$(\mathrm{Id}_{\ell_{2}^{k}}\otimes W_{\varepsilon})|\varphi\rangle$, we
obtain $\Phi^{i}_{\mathcal{S}^{\mathcal{U}}}$.

Next we describe how these maps are related to $G_{Rad}$, postponing the
proofs for later on – cf. Section 4.1.

######  Lemma 4.1.

For any strategy $\mathcal{S}^{\mathcal{U}}$,

$\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})\leq\,\mathbb{E}_{\varepsilon}\,\big{\|}\Phi^{i(ii)}_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\big{\|}_{X^{i(ii)}},$

where we have denoted $X^{i}=M_{r^{2},k\tilde{k}^{\prime}}$ and
$X^{ii}=\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}\otimes_{(\varepsilon,\pi)_{\nicefrac{{1}}{{2}}}}\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}$.

######  Remark 4.2.

For $\Phi_{\mathcal{S}^{\mathcal{U}}}^{ii}$, the previous statement can be
strengthen to

$\omega(G_{Rad};\mathcal{S}^{\mathcal{U}})\leq\,\mathbb{E}_{\varepsilon}\,\big{\|}\Phi^{ii}_{\mathcal{S}^{\mathcal{U}}}(\varepsilon)\big{\|}_{\tilde{X}^{ii}},$

where
$\tilde{X}^{ii}=\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}\otimes_{\mathfrak{S}_{2}^{w-cb}}\mathcal{S}_{1}^{\tilde{k}^{\prime}\\!,n}$.
Recall Definition 2.12 for this last norm.

The regularity of these maps can be characterized by parameters