rm

#  Fidelity of quantum strategies with applications to cryptography

Gus Gutoski  Perimeter Institute for Theoretical Physics, ON, Canada  Ansis
Rosmanis  Centre for Quantum Technologies, National University of Singapore,
Singapore  School of Physical and Mathematical Sciences, Nanyang Technological
University, Singapore  Jamie Sikora  Centre for Quantum Technologies, National
University of Singapore, Singapore  MajuLab, CNRS-UNS-NUS-NTU International
Joint Research Unit, UMI 3654, Singapore

(August 28, 2018)

###### Abstract

We introduce a definition of the fidelity function for multi-round quantum
strategies, which we call the _strategy fidelity_ , that is a generalization
of the fidelity function for quantum states. We provide many properties of the
strategy fidelity including a Fuchs-van de Graaf relationship with the
strategy norm. We also provide a general monotonicity result for both the
strategy fidelity and strategy norm under the actions of strategy-to-strategy
linear maps. We illustrate an operational interpretation of the strategy
fidelity in the spirit of Uhlmann’s Theorem and discuss its application to the
security analysis of quantum protocols for interactive cryptographic tasks
such as bit-commitment and oblivious string transfer. Our analysis is general
in the sense that the actions of the protocol need not be fully specified,
which is in stark contrast to most other security proofs. Lastly, we provide a
semidefinite programming formulation of the strategy fidelity.

##  1 Introduction

###  1.1 Review of quantum strategies

In this paper we consider multiple-round interactions between two parties
involving the exchange of quantum information. There is a natural asymmetry
between the parties as only one of the parties can send the first message or
receive the final message. Since we are not concerned about optimizing the
number of messages exchanged, without loss of generality both of these tasks
are done by the same party, which, for convenience, we call _Bob_. Let us call
the other party _Alice_. The interaction between Alice and Bob decomposes
naturally into a finite number $r$ of _rounds_ (see Figure 1).

Such interactions are conveniently described by the formalism of quantum
strategies introduced in Ref. [GW07]. We closely follow that formalism here
with the exception that we consider two mathematically different objects:
_strategies_ and _pure strategies_. Pure strategies are implemented using
linear isometries and preserve their final memory space, while strategies
trace out the final memory space. The object we call a strategy is called a
_non-measuring strategy_ in Ref. [GW07]. For additional details on quantum
strategies, one may refer to [GW07, CDP09, Gut09].

######  Definition 1 (Pure strategy and pure co-strategy).

Let $r\geq 1$ and let
$\mathcal{X}_{1},\ldots,\mathcal{X}_{r},\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r},\mathcal{Z}_{r}$,
$\mathcal{W}_{r}$ be complex Euclidean spaces and, for notational convenience,
let $\mathcal{X}_{r+1}:=\mathbb{C}$ and $\mathcal{Z}_{0}:=\mathbb{C}$. An _$r$
-round pure strategy_ $\tilde{A}$ having _input spaces_
$\mathcal{X}_{1},\ldots,\mathcal{X}_{r}$, _output spaces_
$\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r}$, and _final memory space_
$\mathcal{Z}_{r}$, consists of:

  1. 1.

complex Euclidean spaces $\mathcal{Z}_{1},\ldots,\mathcal{Z}_{r-1}$, called
_intermediate memory spaces_ , and

  2. 2.

an $r$-tuple of linear isometries $(A_{1},\ldots,A_{r})$ of the form
$A_{i}:\mathcal{X}_{i}\otimes\mathcal{Z}_{i-1}\to\mathcal{Y}_{i}\otimes\mathcal{Z}_{i}$.

An _$r$ -round pure co-strategy_ having input spaces
$\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r}$, output spaces
$\mathcal{X}_{1},\ldots,\mathcal{X}_{r}$, and final memory space
$\mathcal{W}_{r}$, consists of:

  1. 1.

complex Euclidean intermediate memory spaces
$\mathcal{W}_{0},\ldots,\mathcal{W}_{r-1}$,

  2. 2.

a pure quantum state $|\beta\rangle\in\mathcal{X}_{1}\otimes\mathcal{W}_{0}$,
called the _initial state_ , and

  3. 3.

an $r$-tuple of linear isometries $(B_{1},\ldots,B_{r})$ of the form
$B_{i}:\mathcal{Y}_{i}\otimes\mathcal{W}_{i-1}\to\mathcal{X}_{i+1}\otimes\mathcal{W}_{i}$.

A pure strategy and a pure co-strategy are said to be _compatible_ when the
input spaces of one are the output spaces of the other, and vice versa. The
_final state_ after the interaction between $\tilde{A}$ and $\tilde{B}$ is
denoted by

$|\psi(\tilde{A},\tilde{B})\rangle:=(I_{\mathcal{Z}_{r}}\otimes
B_{r})(A_{r}\otimes I_{\mathcal{W}_{r-1}})\cdots(I_{\mathcal{Z}_{1}}\otimes
B_{1})(A_{1}\otimes
I_{\mathcal{W}_{0}})|\beta\rangle\in\mathcal{Z}_{r}\otimes\mathcal{W}_{r}.$

In order to extract classical information from the interaction it suffices to
permit Alice and Bob to measure their respective parts of the final state
$|\psi(\tilde{A},\tilde{B})\rangle$.

StrategyCo-
StrategyAliceBob$A_{1}$$A_{2}$$A_{r}$$|\beta\rangle$$B_{1}$$B_{2}$$B_{r}$$\mathcal{W}_{0}$$\mathcal{W}_{1}$$\mathcal{W}_{2}$$\mathcal{W}_{r-1}$$\mathcal{W}_{r}$$\mathcal{Z}_{1}$$\mathcal{Z}_{2}$$\mathcal{Z}_{r-1}$$\mathcal{Z}_{r}$$\mathcal{X}_{1}$$\mathcal{X}_{1}$$\mathcal{X}_{2}$$\mathcal{X}_{2}$$\mathcal{X}_{3}$$\mathcal{X}_{r}$$\mathcal{Y}_{1}$$\mathcal{Y}_{1}$$\mathcal{Y}_{2}$$\mathcal{Y}_{2}$$\mathcal{Y}_{r}$$\mathcal{Y}_{r}$$\dots\dots$$\dots\dots$
Figure 1: An $r$-round interaction between a pure strategy of Alice (the
linear isometries above the dashed line) and a pure co-strategy of Bob (the
linear isometries below the dashed line). Arrows crossing the dashed line
represent messages exchanged between the parties, while horizontal arrows
represent private memory.

A pure strategy $\tilde{A}$ specified by linear isometries
$(A_{1},\ldots,A_{r})$ can be represented by a single isometry

$\tilde{A}:=(A_{r}\otimes I_{\mathcal{Y}_{1\dots
r-1}})\dots(I_{\mathcal{X}_{3\dots r}}\otimes A_{2}\otimes
I_{\mathcal{Y}_{1}})(I_{\mathcal{X}_{2\dots r}}\otimes
A_{1}):\mathcal{X}_{1\dots r}\to\mathcal{Y}_{1\dots r}\otimes\mathcal{Z}_{r},$
(1)

where $\mathcal{X}_{i\dots j}$ is short for
$\mathcal{X}_{i}\otimes\cdots\otimes\mathcal{X}_{j}$ and $\mathcal{Y}_{i\dots
j}$ is short for $\mathcal{Y}_{i}\otimes\cdots\otimes\mathcal{Y}_{j}$. We
abuse the notation111It will be clear from context to which we are referring.
$\tilde{A}$ here and elsewhere in the paper by using it to denote both a pure
strategy and the linear isometry representing it, and we do the same for pure
co-strategies $\tilde{B}$, discussed next. A pure co-strategy $\tilde{B}$
specified by the initial state $|\beta\rangle$ and linear isometries
$(B_{1},\ldots,B_{r})$ can be represented by a single isometry

$\tilde{B}:=(B_{r}\otimes I_{\mathcal{X}_{1\dots
r}})\cdots(I_{\mathcal{Y}_{2\dots r}}\otimes B_{1}\otimes
I_{\mathcal{X}_{1}})(I_{\mathcal{Y}_{1\dots
r}}\otimes|\beta\rangle):\mathcal{Y}_{1\dots r}\to\mathcal{X}_{1\dots
r}\otimes\mathcal{W}_{r}.$ (2)

Note that two pure strategies that are represented by the same linear isometry
are effectively indistinguishable, and the same holds true for pure co-
strategies.

After the interaction, Alice’s actions do not affect Bob’s reduced state (and
vice versa). Hence, from Bob’s point of view, Alice can trace out her final
memory space. In view of this, a _strategy_ $A$ is obtained from a pure
strategy $\tilde{A}$ by tracing out the final memory space $\mathcal{Z}_{r}$
and a _co-strategy_ $B$ is obtained from a pure co-strategy $\tilde{B}$ by
tracing out the final memory space $\mathcal{W}_{r}$.222We note that,
technically, strategies and pure strategies are (slightly) different
mathematical objects. Multiple pure strategies (pure co-strategies) can yield
the same strategy (co-strategy), and we call any such pure strategy (pure co-
strategy) a _purification_. We will use tildes to indicate purifications.

Just as a pure strategy and a pure co-strategy can be specified by linear
isometries $\tilde{A}$ and $\tilde{B}$, respectively, their corresponding
strategy $A$ and co-strategy $B$ can be specified by quantum channels

$\displaystyle\Phi_{A}\,$ $\displaystyle:\mathbf{L}(\mathcal{X}_{1\dots
r})\to\mathbf{L}(\mathcal{Y}_{1\dots r})\,$
$\displaystyle:X\mapsto\operatorname{Tr}_{\mathcal{Z}_{r}}(\tilde{A}X\tilde{A}^{*}),$
(3) $\displaystyle\Psi_{B}\,$ $\displaystyle:\mathbf{L}(\mathcal{Y}_{1\dots
r})\to\mathbf{L}(\mathcal{X}_{1\dots r})\,$
$\displaystyle:Y\mapsto\operatorname{Tr}_{\mathcal{W}_{r}}(\tilde{B}Y\tilde{B}^{*}),$
(4)

where $\mathbf{L}(\mathcal{X})$ is the set of all linear operators acting on a
space $\mathcal{X}$. In turn, both of these channels can be specified using
their Choi-Jamiołkowski representations, but, due to the asymmetry between
strategies and co-strategies, it is convenient to specify the latter one using
the Choi-Jamiołkowski representation of its adjoint map. Thus, we can
represent a strategy $A$ by $J(\Phi_{A})$ and a co-strategy $B$ by
$J(\Psi_{B}^{*})$, both of which are positive semidefinite operators acting on
$\mathcal{Y}_{1\dots r}\otimes\mathcal{X}_{1\dots r}$. In a similar abuse of
notation as mentioned before, we refer to $J(\Phi_{A})$ as the strategy $A$
and to $J(\Psi_{B}^{*})$ as the co-strategy $B$.

For compatible pure strategy $\tilde{A}$ and pure co-strategy $\tilde{B}$, let

$\rho_{A}({\tilde{B}}):=\operatorname{Tr}_{\mathcal{Z}_{r}}\left(|\psi(\tilde{A},\tilde{B})\rangle\langle\psi(\tilde{A},\tilde{B})|\right)$
(5)

denote the reduced state of the final memory space $\mathcal{W}_{r}$ of
$\tilde{B}$ after the interaction between $\tilde{A}$ and $\tilde{B}$. Since
this state is the same for all purifications of $A$, we omit the tilde above
$A$ in this notation.

###  1.2 The definition of strategy fidelity

Recall that the fidelity $\operatorname{\mathrm{F}}(P,Q)$ between two positive
semidefinite operators $P$ and $Q$ is defined as

$\operatorname{\mathrm{F}}(P,Q):=\left\lVert\mspace{1.0mu}\sqrt{P}\sqrt{Q}\mspace{1.0mu}\right\rVert_{\operatorname{Tr}}.$
(6)

When applied to density operators $\rho,\xi$, the fidelity function
$\operatorname{\mathrm{F}}(\rho,\xi)$ is a useful distance measure for quantum
states. We would like to construct a generalization of the fidelity function
that can serve as a useful distance measure for quantum strategies.

Just as the trace norm
$\lVert\mspace{1.0mu}\rho-\xi\mspace{1.0mu}\rVert_{\operatorname{Tr}}$
quantifies the distinguishability of quantum states, the strategy norm333What
we refer to as the strategy norm was introduced in [CDP08b] where it is called
the _operational norm_. We use the term _strategy norm_ to make the
connections to strategy fidelity more apparent.
$\lVert\mspace{1.0mu}S-T\mspace{1.0mu}\rVert_{\diamond{\mathrm{r}}}$ studied
in [CDP08b] and [Gut12], quantifies the distinguishability of quantum
strategies $S$ and $T$ having the same input and output spaces. In other
words, ${\lVert\mspace{1.0mu}S-T\mspace{1.0mu}\rVert_{\diamond{\mathrm{r}}}}$
is proportional to the maximum bias with which an interacting pure co-strategy
$\tilde{B}$ can distinguish $S$ from $T$. Another expression for this maximum
bias can be derived as follows. Let $\mathcal{W}_{r}$ be the final memory
space of $\tilde{B}$ and let $\rho_{S}({\tilde{B}}),\rho_{T}({\tilde{B}})$ be
the reduced states of this final memory space after an interaction between
$\tilde{B}$ and $S,T$, respectively, as defined in (5). It is clear that the
maximum bias with which $S$ can be distinguished from $T$ is proportional to
the maximum over all such $\tilde{B}$ with which the final state
$\rho_{S}({\tilde{B}})$ can be distinguished from $\rho_{T}({\tilde{B}})$,
which is precisely
$\lVert\mspace{1.0mu}\rho_{S}({\tilde{B}})-\rho_{T}({\tilde{B}})\mspace{1.0mu}\rVert_{\operatorname{Tr}}$.

######  Remark 2.

All purifications $\tilde{B}$ of $B$ are equivalent up to a unitary acting on
$\mathcal{W}_{r}$. Thus, unitarily invariant distance measures between
$\rho_{S}({\tilde{B}})$ and $\rho_{T}({\tilde{B}})$ (including the trace
distance and the fidelity) depend only upon $B$ and not upon the specific
purification $\tilde{B}$.

The strategy norm is defined (see Definition 8) so that

$\lVert\mspace{1.0mu}S-T\mspace{1.0mu}\rVert_{\diamond{\mathrm{r}}}={\max_{B}}\,\lVert\mspace{1.0mu}\rho_{S}({\tilde{B}})-\rho_{T}({\tilde{B}})\mspace{1.0mu}\rVert_{\operatorname{Tr}}.$
(7)

In light of this observation, we define the strategy fidelity by replacing the
maximization of the trace distance between $\rho_{S}({\tilde{B}})$ and
$\rho_{T}({\tilde{B}})$ with the minimization of the fidelity between
$\rho_{S}({\tilde{B}})$ and $\rho_{T}({\tilde{B}})$.

######  Definition 3 (Strategy fidelity).

For any $r$-round strategies $S$ and $T$ having the same input and output
spaces, the _strategy fidelity_ is defined as

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T):=\min_{B}\,\operatorname{\mathrm{F}}(\rho_{S}({\tilde{B}}),\rho_{T}({\tilde{B}}))$
(8)

where the minimization is over all compatible co-strategies $B$ and the states
$\rho_{S}({\tilde{B}}),\rho_{T}({\tilde{B}})$ are as defined in (5).

In the following discussion, we argue that this definition is a meaningful one
by proving analogues of the Fuchs-van de Graaf inequalities and Uhlmann’s
Theorem for the strategy fidelity, among many other properties.

######  Remark 4.

The same definition of fidelity has been considered for the case of channels
[BDR05]. In that setting, they establish several properties which we
generalize to the strategy setting.

First, let us observe that the fidelity for quantum states is recovered as a
special case of the strategy fidelity when $S,T$ are one-round strategies with
no input (that is, $\mathcal{X}_{1}=\mathbb{C}$) and only one output message.
To see this, observe that one-round strategies such as $S,T$ are simply states
$\rho,\xi$ acting on $\mathcal{Y}_{1}$. Bob’s most general pure co-strategy is
an isometry $\tilde{B}:\mathcal{Y}_{1}\to\mathcal{W}_{1}$. In this case the
effect of Bob’s purified strategy $\tilde{B}$ is cancelled in the computation
of $\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)$ so that

$\operatorname{\mathrm{F}}_{1}(S,T)=\min_{B}\,\operatorname{\mathrm{F}}(\rho_{S}({\tilde{B}}),\rho_{T}({\tilde{B}}))=\operatorname{\mathrm{F}}(\tilde{B}\rho\tilde{B}^{*},\tilde{B}\xi\tilde{B}^{*})=\operatorname{\mathrm{F}}(\rho,\xi)$
(9)

as claimed.

#### Basic properties of the strategy fidelity

We now list several other properties of the strategy fidelity, all of which
immediately hold using the corresponding properties of the fidelity of quantum
states (see references [FvdG99, NC00]).

######  Proposition 5 (Basic properties).

  * •

(Fuchs-van de Graaf inequalities for strategies) For any $r$-round strategies
$S$ and $T$, it holds that

$1-\frac{1}{2}\lVert\mspace{1.0mu}S-T\mspace{1.0mu}\rVert_{\diamond{\mathrm{r}}}\leq\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)\leq\sqrt{1-\frac{1}{4}\lVert\mspace{1.0mu}S-T\mspace{1.0mu}\rVert_{\diamond{\mathrm{r}}}^{2}}.$
(10)

  * •

(Symmetry) For any $r$-round strategies $S$ and $T$, it holds that
$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)=\operatorname{\mathrm{F}_{\mathrm{r}}}(T,S)$.

  * •

(Joint concavity) For any $r$-round strategies $S^{1},\ldots,S^{n}$ and
$T^{1},\ldots,T^{n}$, and nonnegative scalars $\lambda_{1},\ldots,\lambda_{n}$
satisfying $\sum_{i=1}^{n}\lambda_{i}=1$, we have

$\operatorname{\mathrm{F}_{\mathrm{r}}}\left(\sum_{i=1}^{n}\lambda_{i}S^{i},\sum_{i=1}^{n}\lambda_{i}T^{i}\right)\geq\sum_{i=1}^{n}\lambda_{i}\operatorname{\mathrm{F}_{\mathrm{r}}}\left(S^{i},T^{i}\right).$
(11)

  * •

(Bounds on the strategy fidelity) For any $r$-round strategies $S$ and $T$, we
have ${0\leq\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)\leq 1}$. Moreover,
$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)=1$ if and only if $S=T$ and
$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)=0$ if and only if $S$ and $T$ are
perfectly distinguishable.

We later discuss that the strategy version of the Fuchs-van de Graaf
inequalities is crucial to our cryptographic applications. This was also used
implicitly in [CDP+13].

#### Monotonicity of the strategy fidelity and the strategy norm

The fidelity for quantum states is known to be monotonic under channels,
meaning that

$\operatorname{\mathrm{F}}(\Phi(\rho),\Phi(\xi))\geq\operatorname{\mathrm{F}}(\rho,\xi)$
(12)

for any choice of states $\rho,\xi$ and channel $\Phi$ [BCF+96]. It was
observed in Ref. [BDR05] that the fidelity function of _quantum channels_
(that aligns with our definition of strategy fidelity for a $1$-round
interaction) is also monotonic under composition (both left and right) with
another channel. That is,

$\operatorname{\mathrm{F}}_{1}(\Phi\circ\Delta,\Psi\circ\Delta)\geq\operatorname{\mathrm{F}}_{1}(\Phi,\Psi)\qquad\textnormal{and}\qquad\operatorname{\mathrm{F}}_{1}(\Delta^{\prime}\circ\Phi,\Delta^{\prime}\circ\Psi)\geq\operatorname{\mathrm{F}}_{1}(\Phi,\Psi)$
(13)

for all channels $\Phi,\Psi:\mathbf{L}(\mathcal{X})\to\mathbf{L}(\mathcal{Y})$
and $\Delta$ into $\mathbf{L}(\mathcal{X})$ and $\Delta^{\prime}$ on
$\mathbf{L}(\mathcal{Y})$. However, there are other physical maps on channels
that cannot in general be written as a composition with another channel.
Chiribella, D’Ariano, and Perinotti call such mappings _supermaps_ and
characterize them in Ref. [CDP08a]. Thus, the natural generalization of
monotonicity of the kind described above would be the analogous statement
involving supermaps. We provide an even stronger result concerning
monotonicity of the strategy fidelity using the following definition.

######  Definition 6.

A _strategy supermap_ is a completely positive linear map (with respect to
Choi-Jamiołkowski representations) that maps $r$-round strategies to
$r^{\prime}$-round strategies. It is understood that $r$-round strategies are
for some choice of input spaces $\mathcal{X}_{1},\dots,\mathcal{X}_{r}$ and
output spaces $\mathcal{Y}_{1},\dots,\mathcal{Y}_{r}$ and $r^{\prime}$-round
strategies are for some choice of input spaces
$\mathcal{X}^{\prime}_{1},\dots,\mathcal{X}^{\prime}_{r^{\prime}}$ and output
spaces $\mathcal{Y}^{\prime}_{1},\dots,\mathcal{Y}^{\prime}_{r^{\prime}}$.

The definition of strategy supermaps are inspired by physically realizable
maps from $r$-round strategies to $r^{\prime}$-round strategies studied by
Chiribella, D’Ariano, and Perinotti [CDP09]. Our result, however, is purely
mathematical and does not require strategy supermaps to be physically
realizable.

######  Theorem 7 (Monotonicity of the strategy fidelity).

For all natural numbers $r,r^{\prime}$, all $r$-round strategies $S,T$, and
all strategy supermaps $\Upsilon$ from $r$-round strategies to
$r^{\prime}$-round strategies, it holds that

$\operatorname{\mathrm{F}}_{\mathrm{r^{\prime}}}(\Upsilon(S),\Upsilon(T))\geq\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T).$
(14)

We can also prove a similar monotonicity result for the strategy norm. By
analogy with the fidelity, the trace norm is known to be monotonic under
channels, meaning that

$\lVert\mspace{1.0mu}\Phi(X)\mspace{1.0mu}\rVert_{\operatorname{Tr}}\leq\lVert\mspace{1.0mu}X\mspace{1.0mu}\rVert_{\operatorname{Tr}}$
(15)

for all operators $X$ and all channels $\Phi$ [Rus94]. Similarly, the diamond
norm can be shown to be monotonic under composition (both left and right) with
channels, meaning that

$\lVert\mspace{1.0mu}\Phi\circ\Delta\mspace{1.0mu}\rVert_{\diamond}\leq\lVert\mspace{1.0mu}\Phi\mspace{1.0mu}\rVert_{\diamond}\qquad\textnormal{and}\qquad\lVert\mspace{1.0mu}\Delta^{\prime}\circ\Phi\mspace{1.0mu}\rVert_{\diamond}\leq\lVert\mspace{1.0mu}\Phi\mspace{1.0mu}\rVert_{\diamond}$
(16)

for all linear maps $\Phi:\mathbf{L}(\mathcal{X})\to\mathbf{L}(\mathcal{Y})$
and all channels $\Delta$ into $\mathbf{L}(\mathcal{X})$ and $\Delta^{\prime}$
on $\mathbf{L}(\mathcal{Y})$. As with the fidelity function for quantum
channels, defined in Ref. [BDR05], monotonicity of the diamond norm under
arbitrary supermaps has not yet been observed, nor has monotonicity of the
strategy norm under strategy supermaps.

We now establish a monotonicity result for the strategy norm, defined below.

######  Definition 8 (Strategy norm [CDP08b], [Gut12]).

Consider $\mathcal{X}_{1},\ldots,\mathcal{X}_{r}$ and
$\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r}$ as input and output spaces of
$r$-round strategies, respectively. The strategy norm of a Hermitian operator
$H$ acting on $\mathcal{Y}_{1\dots r}\otimes\mathcal{X}_{1\dots r}$ is defined
as

$\left\lVert\mspace{1.0mu}H\mspace{1.0mu}\right\rVert_{\diamond{\mathrm{r}}}:=\max_{B_{0},B_{1}\succeq
0}\left\\{\left\langle B_{0}-B_{1},H\right\rangle:\textnormal{$B_{0}+B_{1}$ is
an $r$-round co-strategy}\right\\},$ (17)

where the maximization is over all positive semidefinite operators
$B_{0},B_{1}$ acting on $\mathcal{Y}_{1\dots r}\otimes\mathcal{X}_{1\dots r}$
such that $B_{0}+B_{1}$ is an $r$-round co-strategy having input spaces
$\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r}$ and output spaces
$\mathcal{X}_{1},\ldots,\mathcal{X}_{r}$.

Given $H$ as a difference of two $r$-round strategies $S$ and $T$, Definition
8 implies Eqn. (7).

######  Theorem 9 (Monotonicity of the strategy norm).

For all natural numbers $r,r^{\prime}$, all Hermitian operators $H$ acting on
$\mathcal{Y}_{1\dots r}\otimes\mathcal{X}_{1\dots r}$ and strategy supermaps
$\Upsilon$ from $r$-round strategies to $r^{\prime}$-round strategies, it
holds that

$\left\lVert\mspace{1.0mu}\Upsilon(H)\mspace{1.0mu}\right\rVert_{\diamond{\mathrm{r^{\prime}}}}\leq\left\lVert\mspace{1.0mu}H\mspace{1.0mu}\right\rVert_{\diamond{\mathrm{r}}}.$
(18)

#### Operational interpretation (min-max properties)

Here we propose an operationally motivated generalization of Uhlmann’s Theorem
[Uhl76] to the strategy fidelity. In so doing we elucidate the need for a min-
max theorem. Recall that Uhlmann’s Theorem for quantum states asserts that the
fidelity $\operatorname{\mathrm{F}}(\rho,\xi)$ between any two quantum states
$\rho$ and $\xi$, acting on $\mathcal{X}$, is given by

$\operatorname{\mathrm{F}}(\rho,\xi)=\max_{U}\left|\mspace{1.0mu}\langle\phi|(U\otimes
I_{\mathcal{X}})|\psi\rangle\mspace{1.0mu}\right|$ (19)

where $|\phi\rangle,|\psi\rangle\in\mathcal{X}\otimes\mathcal{Y}$ are any
purifications of $\rho,\xi$ and the maximization is over all unitaries $U$
acting on $\mathcal{Y}$ alone.

Intuitively, $\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)$ should quantify the
extent to which any purifications $\tilde{S},\tilde{T}$ of two strategies
$S,T$ can be made to look the same by acting only on the final memory space
$\mathcal{Z}_{r}$. It follows immediately from the definition of the strategy
fidelity and Uhlmann’s Theorem that

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)=\min_{B}\operatorname{\mathrm{F}}(\rho_{S}({\tilde{B}}),\rho_{T}({\tilde{B}}))=\min_{B}\max_{U}\left|\mspace{1.0mu}\langle\psi(\tilde{S},\tilde{B})|\left(U\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{T},\tilde{B})\rangle\mspace{1.0mu}\right|$
(20)

where, again, the maximization is over all unitaries $U$ acting on
$\mathcal{Z}_{r}$ alone.

Notice the order of minimization and maximization in (20). This could be
viewed as a competitive game between Alice (who plays according to $S$ or $T$)
and Bob (who plays according to any arbitrary co-strategy $B$) in which Bob is
trying to distinguish $S$ from $T$ and Alice is trying to make $S$ and $T$
look the same. To these ends, Bob chooses his strategy $B$ so as to minimize
the overlap
$|\mspace{1.0mu}\langle\psi(\tilde{S},\tilde{B})|\psi(\tilde{T},\tilde{B})\rangle\mspace{1.0mu}|$;
given such a choice $B$ for Bob, Alice’s responds with a unitary $U$ that
maximizes this overlap.

The problem is that Alice’s choice of $U$ may depend upon Bob’s co-strategy
$B$. The task of distinguishing $S$ from $T$ should depend only upon $S$ and
$T$—Alice should not be granted the ability to tweak $S$ or $T$ after she has
acquired knowledge of Bob’s specific choice of distinguishing co-strategy $B$.
From an operational perspective, it would be much more desirable if the order
of minimization and maximization in (20) were reversed. Alice should select
her unitary $U$ so as to make $S$ look as much as possible like $T$ _before_
Bob selects his distinguishing co-strategy $B$. Thus, we require a type of
_min-max theorem_.

The set of all co-strategies $B$ for Bob is compact and convex [GW07], but it
is not at all clear that the objective function in (20) is convex in $B$; we
show later (Lemma 16) that this is indeed the case. However, the set of all
unitaries $U$ for Alice is not a convex set. One might think that we could
extend the domain of maximization to the convex hull of the unitaries in the
hopes that there is a saddle point $(U,B)$ with $U$ unitary. Unfortunately,
saddle points do not in general occur at extreme points of the domain, so we
are not guaranteed that such a unitary saddle point exists. Thus, a min-max
theorem for the strategy fidelity involving unitaries is not so easily
forthcoming.

However, if we allow Alice to apply a general _quantum channel_ , we are able
to obtain a min-max result, as stated below.

######  Theorem 10 (Strategy generalization of Uhlmann’s Theorem).

Let $S,T$ be $r$-round strategies and let $\tilde{S},\tilde{T}$ be any
purifications of $S,T$. Let $|\psi(\tilde{S},\tilde{B})\rangle$,
$|\psi(\tilde{T},\tilde{B})\rangle$ be as defined in Definition 1. We have

$\displaystyle\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)^{2}$
$\displaystyle=\max_{\Xi}\,\min_{B}\,\langle\psi(\tilde{S},\tilde{B})|\left[\left(\Xi\otimes
I_{\mathbf{L}(\mathcal{W}_{r})}\right)\left(|\psi(\tilde{T},\tilde{B})\rangle\langle\psi(\tilde{T},\tilde{B})|\right)\right]|\psi(\tilde{S},\tilde{B})\rangle$
(21)

where the minimum is over all $r$-round pure co-strategies $\tilde{B}$ and the
maximum is over all quantum channels $\Xi$ acting on $\mathcal{Z}_{r}$ alone.

Note that similar min-max results are derived in [BDR05] and [CDP+13]. It will
be convenient to define the following quantum channel.

######  Definition 11.

A _strategy fidelity-achieving_ channel $\Xi$ is a channel which attains the
maximum in (21), above.

#### Semidefinite programming formulation of strategy fidelity

It was shown in [Gut12] that the strategy norm has a semidefinite programming
formulation. Also, the fidelity of quantum states has semidefinite programming
formulations, see [Wat09, Wat13] for examples. It is natural to ask whether
the strategy fidelity has such a formulation. We answer this question in the
affirmative, below.

######  Theorem 12 (Semidefinite programming formulation of strategy
fidelity).

Fix any purifications $\tilde{S}$ and $\tilde{T}$ of $r$-round strategies $S$
and $T$, respectively. Then $\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)^{2}$
is equal to the optimal objective function value of the following semidefinite
program:

$\begin{array}[]{rrrllllll}\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)^{2}=&{\max}&t\\\
&\textup{subject
to}&tI_{\mathcal{X}_{1}}&\preceq&\operatorname{Tr}_{\mathcal{Y}_{1}}(R_{1})\\\
&&R_{j}\otimes
I_{\mathcal{X}_{j+1}}&\preceq&\operatorname{Tr}_{\mathcal{Y}_{j+1}}(R_{j+1}),\,\textup{
for }j\in\\{1,\ldots,r-1\\},\\\
&&R_{r}&\preceq&\frac{1}{2}\operatorname{Tr}_{\mathcal{Z}_{r}}\left(\left(K\otimes
I_{\mathcal{Y}_{1\dots r}\otimes\mathcal{X}_{1\dots
r}}\right)|\tilde{T}\rangle\rangle\langle\langle\tilde{S}|\right)+h.c.\\\
&&\left[\begin{array}[]{cc}I_{\mathcal{Z}_{r}}&K\\\
K^{*}&I_{\mathcal{Z}_{r}}\end{array}\right]&\succeq&0\end{array}$ (22)

where the variables $R_{j}$ are Hermitian matrices acting on
$\mathcal{Y}_{1\dots j}\otimes\mathcal{X}_{1\dots j}$ for each
$j\in\\{1,\ldots,r\\}$, and $h.c.$ denotes the Hermitian conjugate. Note that
the optimization is over the Hermitian matrices $R_{1},\ldots,R_{r}$, the
scalar $t$, and a (not neccessarily Hermitian) matrix $K$. (The last
constraint requires $K$ to be in the convex hull of the set of unitaries
acting on space $\mathcal{Z}_{r}$.)

There are a few reasons why it is beneficial to have a semidefinite
programming formulation of the strategy fidelity (or any other function for
that matter). One is that efficient algorithms that approximate semidefinite
programs allow for the calculation of numerical values for specific instances
(assuming the problem instance is not too large for the computational
platform). Another reason is that semidefinite programming has a rich duality
theory, which allows one to certify bounds (upper bounds in this case) on the
value of the strategy fidelity. Otherwise, such a task would be very hard
using the definition alone.

###  1.3 Applications to two-party quantum cryptography

Since the seminal work of Wiesner [Wie83] and Bennett and Brassard [BB84],
there has been much interest in knowing the advantages, and limitations, of
quantum protocols for cryptographic tasks. Due to the interactive setting of
such protocols, the use of quantum strategy analysis has proven to be useful.
In [GW07], it was shown how to rederive Kitaev’s lower bound for coin-flipping
[Kit02]. In [CDP+13], it was shown how to find a simple proof of the
impossibility of interactive bit-commitment. Here, we find a similar proof of
this and extend the argument to oblivious string transfer.

In this paper, we present our ideas using the machinery we have developed for
the strategy fidelity. In particular, we show that the strategy version of the
Fuchs-van de Graaf inequalities (Eqn. (10)) are of central importance in
providing security lower bounds. In fact, due to the nature of the strategy
norm and strategy fidelity, we are able to bound the security without even
specifying the entire protocol! To the best of our knowledge, this very
general setting has only been studied in a few security proofs (in particular,
of bit-commitment) [BDR05, DKSW07, CDP+13] and is in stark contrast to many
other security proofs, for example in [Kit02, SR01, Amb01, NS03, ABDR04, KN04,
GW07, CK09, CK11, CKS13, CKS14, NST15, NST16, CGS16, Sik17] where Alice and
Bob’s actions are assumed to be fully specified (and known to cheating
parties).

In this paper, we show the impossibility of ideal quantum protocols for
interactive _bit-commitment_ and _oblivious string transfer_.

#### Interactive bit-commitment

In bit-commitment, we require Alice and Bob to interact over two communication
stages:

  * •

Commit Phase: Alice chooses a uniformly random bit $a$ and interacts with Bob
using an $r$-round pure strategy $\tilde{A}^{a}$.

  * •

Reveal Phase: Alice sends $a$ to Bob and continues her interaction444Note that
the interaction of the Reveal Phase is not part of the strategy
$\tilde{A}^{a}$. In fact, our results do not depend on the structure of the
Reveal Phase, other than revealing $a$. with him (so that Bob can test if she
has cheated).

  * •

Cheat Detection: Bob, knowing which pure strategy $\tilde{B}$ he has used,
measures to check if the final state is consistent with Alice’s pure strategy
$\tilde{A}^{a}$. He aborts the protocol if this measurement detects the final
state is not consistent with Alice’s pure strategy $\tilde{A}^{a}$. If Alice
is honest, he never aborts.

Protocols are designed with the intention to achieve the following two
important properties of interest:

  * •

Binding: Alice cannot change her mind after the Commit Phase and reveal the
other value of $a$ (without being detected by Bob).

  * •

Concealing: Bob cannot learn Alice’s bit $a$ before she reveals it during the
Reveal Phase.

The references [May97, LC97, LC98] showed that when Alice and Bob’s actions
are known to both parties, bit-commitment with perfect binding and concealing
is impossible. In the more general setting when the actions need not be fully
specified beforehand, bit-commitment was shown to be impossible in [BDR05] for
the channel setting, and in [DKSW07, CDP+13] for the interactive setting.
Here, we give another proof of this fact which follows straightforwardly from
the properties of the strategy fidelity and strategy norm which we have
already discussed.

We define the cheating probabilities of Alice and Bob as follows:

$\mathrm{B_{BC}}$: |  The maximum probability with which a dishonest Bob can cheat by _learning_ an honest Alice’s committed bit $a\in\\{0,1\\}$ after the Commit Phase.
---|---
$\mathrm{A_{BC}}$: |  The maximum probability with which a dishonest Alice can cheat by _changing_ her commitment from $0$ to $1$ (or from $1$ to $0$) after the Commit Phase such that Bob accepts the new value (i.e., he does not abort).

######  Remark 13.

Note that in the definition of cheating Alice above, we do not assume Alice
knows Bob’s actions. It could even be the case that Bob’s sole purpose is to
choose a co-strategy such as to minimize $\mathrm{A_{BC}}$.

Cheating Bob wishes to distinguish between one of two uniformly randomly
chosen strategies. We know from [Gut12] that

$\mathrm{B_{BC}}=\frac{1}{2}+\frac{1}{4}\lVert\mspace{1.0mu}A^{0}-A^{1}\mspace{1.0mu}\rVert_{\diamond{\mathrm{r}}}.$
(23)

In Section 5, we show that

$\mathrm{A_{BC}}\geq\operatorname{\mathrm{F}}_{r}(A^{0},A^{1})^{2}.$ (24)

An interesting observation is that this only depends on Alice’s honest
strategies, not Bob’s.

Thus, by the Fuchs-van de Graaf inequalities for strategies (Proposition 5),
we have the following trade-off lower bound.

######  Theorem 14.

In any interactive quantum protocol for bit-commitment, we have that

$\sqrt{\mathrm{A_{BC}}}+2\mathrm{B_{BC}}\geq 2$ (25)

implying

$\max\\{\mathrm{A_{BC}},\mathrm{B_{BC}}\\}\geq\frac{9-\sqrt{17}}{8}\approx
61\%$ (26)

(recall the definitions of $\mathrm{A_{BC}}$ and $\mathrm{B_{BC}}$ above
Remark 13). In other words, at least one of Alice or Bob can successfully
cheat with probability at least $61\%$ making bit-commitment insecure.

Note that this is a similar bound to the one obtained in [CDP+13] for the
interactive setting and exactly the same as in [BDR05] in the channel setting.

We remark that, in the scenario when Alice and Bob’s actions are completely
specified, optimal protocols are known [CK11] (albeit with a slightly
different definition of cheating Alice). We leave it as an open problem to
determine if the bound we present above is optimal in the scenario when Bob’s
actions are not specified. Moreover, it would be interesting to see whether
the two scenarios share the same optimal cheating probabilities.

#### 1-out-of-2 interactive oblivious string transfer

This is an interactive cryptographic task between Alice and Bob where Bob has
two bit-strings555The bit-length of the strings are, surprisingly, not
important for the purposes of this paper. $(x_{0},x_{1})$ and Alice wishes to
learn one of the two in the following manner:

  * •

Alice chooses a uniformly random bit $a$ which corresponds to her choice of
which string she wishes to learn, and interacts with Bob via the $r$-round
pure strategy $\tilde{A}^{a}$.

  * •

For every $(x_{0},x_{1})$, Bob uses a pure co-strategy
$\tilde{B}^{x_{0},x_{1}}$, such that Alice learns the string $x_{a}$ with
certainty by measuring her private space $\mathcal{Z}_{r}$ at the end of the
protocol.

Note that we do not assume any structure on how Bob behaves other than the
consistency condition above. For example, $x_{0}$ and $x_{1}$ may be the
result of another protocol of which Alice is not part, and thus she does not
even know the distribution from which they are drawn. Again, Bob’s strategy
may be such that, conditioned on the above requirements, he just wants to foil
Alice’s cheating, as defined below.

We define the cheating probabilities of Alice and Bob as follows:

$\mathrm{B_{OT}}$: |  The maximum probability with which a dishonest Bob can cheat by correctly _learning_ an honest Alice’s choice bit $a$.
---|---
$\mathrm{A_{OT}}$: |  The maximum probability with which a dishonest Alice can cheat by correctly _learning_ $x_{0}$ after learning $x_{1}$ with certainty, or vice versa.

Cheating Bob behaves the exact same as in a bit-commitment protocol. Thus his
cheating probability is again

$\mathrm{B_{OT}}=\frac{1}{2}+\frac{1}{4}\lVert\mspace{1.0mu}A^{0}-A^{1}\mspace{1.0mu}\rVert_{\diamond{\mathrm{r}}}.$
(27)

In Section 5, we show the following bound on cheating Alice:

$\mathrm{A_{OT}}\geq\operatorname{\mathrm{F}}_{r}(A^{0},A^{1})^{2}.$ (28)

This yields the same bound as in bit-commitment, below.

######  Theorem 15.

In any interactive quantum protocol for 1-out-of-2 oblivious string transfer,
we have that

$\sqrt{\mathrm{A_{OT}}}+2\mathrm{B_{OT}}\geq 2$ (29)

implying

$\max\\{\mathrm{A_{OT}},\mathrm{B_{OT}}\\}\geq\frac{9-\sqrt{17}}{8}\approx
61\%$ (30)

(recall the definitions of $\mathrm{A_{OT}}$ and $\mathrm{B_{OT}}$ above). In
other words, at least one of Alice or Bob can successfully cheat with
probability at least $61\%$, making oblivious string transfer insecure.

Note that in the case where Bob has two _bits_ (i.e., the strings have bit-
length $1$), an optimal security trade-off between Alice and Bob is known
[CGS16]:

$\mathrm{A_{OT}}+2\mathrm{B_{OT}}\geq 2.$ (31)

However, this assumes perfect knowledge of Alice and Bob’s honest strategies.
Thus, our bound for cheating Alice is a bit weaker, but has the added benefit
of only depending on her honest strategies.

###  1.4 Paper organization

We start with presenting some technical lemmas involving the strategy fidelity
and generalizing Uhlmann’s Theorem in Section 2. In Section 3, we prove the
monotonicity of the strategy fidelity under the action of supermaps. We then
use the technical lemmas to formulate the strategy fidelity of two strategies
as a semidefinite program in Section 4. We conclude the paper by presenting
our main application of the study of strategy fidelity which is to capture
Alice’s cheating probability in interactive bit-commitment and oblivious
string transfer, discussed in Section 5.

##  2 Technical lemmas and the strategy generalization of Uhlmann’s Theorem

In this section we prove two lemmas that allow us to establish nontrivial
properties of the strategy fidelity. These lemmas are used to prove the
strategy generalization of Uhlmann’s Theorem (Theorem 10) and to provide a
semidefinite programming formulation of the strategy fidelity (Theorem 12).

Before we proceed, let us introduce some notation. Let $\mathcal{Y}_{i\dots
j}\mathcal{X}_{i^{\prime}\dots j^{\prime}}$ be short for $\mathcal{Y}_{i\dots
j}\otimes\mathcal{X}_{i^{\prime}\dots j^{\prime}}$. Let
$\mathbf{L}(\mathcal{X})$, $\mathbf{U}(\mathcal{X})$,
$\mathbf{Her}(\mathcal{X})$, $\mathbf{Pos}(\mathcal{X})$, and
$\mathbf{Dens}(\mathcal{X})$ be, respectively, the set of all linear, unitary,
Hermitian, positive semidefinite, and density operators acting on
$\mathcal{X}$. Let $\mathbf{K}(\mathcal{X})$ be the convex hull of
$\mathbf{U}(\mathcal{X})$, namely, the set of all operators
$K\in\mathbf{L}(\mathcal{X})$ such that
$\lVert\mspace{1.0mu}K\mspace{1.0mu}\rVert\leq 1$. Suppose $\mathcal{X}$ and
$\mathcal{Y}$ are two complex Euclidean spaces with fixed standard basis.
Given a linear operator $A:\mathcal{X}\to\mathcal{Y}$ written in the standard
basis as

$A=\sum_{i=1}^{\dim(\mathcal{X})}\sum_{j=1}^{\dim(\mathcal{Y})}a_{j,i}|j\rangle\langle
i|,$ (32)

the _vectorization_ of $A$ is

$|A\rangle\rangle:=\sum_{i=1}^{\dim(\mathcal{X})}\sum_{j=1}^{\dim(\mathcal{Y})}a_{j,i}|j\rangle\otimes|i\rangle\in\mathcal{Y}\otimes\mathcal{X}$
(33)

and its adjoint is $\langle\langle A|:=\left(|A\rangle\rangle\right)^{*}$.

######  Lemma 16 (Inner product is linear in $B$).

Let $S,T$ be $r$-round strategies and let $\tilde{S},\tilde{T}$ be any
purifications of $S,T$. Let $B$ be a compatible $r$-round co-strategy and let
$\tilde{B}$ be any purification of $B$. Let
$|\psi(\tilde{S},\tilde{B})\rangle,|\psi(\tilde{T},\tilde{B})\rangle$ be as in
Definition 1 and let $K\in\mathbf{L}(\mathcal{Z}_{r})$. It holds that

$\langle\psi(\tilde{S},\tilde{B})|\left(K\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{T},\tilde{B})\rangle=\langle\langle\tilde{S}|\left(K\otimes
B\right)|\tilde{T}\rangle\rangle.$ (34)

Note that the inner product above depends on $B$ but not on its purification
$\tilde{B}$. This exemplifies what we stated earlier as Remark 2.

###### Proof of Lemma 16.

The proof mirrors that of Ref. [GW07, Theorem 5]. The main difference is that
here we compute an inner product between two _distinct_ vectors

$|\psi(\tilde{S},\tilde{B})\rangle\quad\text{and}\quad(K\otimes
I_{\mathcal{W}_{r}})|\psi(\tilde{T},\tilde{B})\rangle$ (35)

(both being _normalized_ if $K$ is unitary) arising from the distinct pure
strategies $\tilde{S},\tilde{T}$ for Alice, whereas the proof of Ref. [GW07,
Theorem 5] computes a similar inner product between two _identical,
subnormalized_ vectors. Further clarification of that proof is given in Ref.
[Gut09]; we draw upon both of the references [GW07, Gut09] for the present
proof.

It was proved in [GW07] that

$\displaystyle|\psi(\tilde{S},\tilde{B})\rangle$
$\displaystyle=\left(\langle\langle I_{\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots r}}|\otimes
I_{\mathcal{Z}_{r}\mathcal{W}_{r}}\right)\left(|\tilde{S}\rangle\rangle\otimes|\tilde{B}\rangle\rangle\right),$
(36) $\displaystyle|\psi(\tilde{T},\tilde{B})\rangle$
$\displaystyle=\left(\langle\langle I_{\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots r}}|\otimes
I_{\mathcal{Z}_{r}\mathcal{W}_{r}}\right)\left(|\tilde{T}\rangle\rangle\otimes|\tilde{B}\rangle\rangle\right),$
(37)

from which we obtain

$\langle\psi(\tilde{S},\tilde{B})|\left(K\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{T},\tilde{B})\rangle\\\
=\left(\langle\langle\tilde{S}|\otimes\langle\langle\tilde{B}|\right)\left(|I_{\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots r}}\rangle\rangle\langle\langle I_{\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots r}}|\otimes K\otimes
I_{\mathcal{W}_{r}}\right)\left(|\tilde{T}\rangle\rangle\otimes|\tilde{B}\rangle\rangle\right).$
(38)

Let

$K=\sum_{i,i^{\prime}=1}^{\dim(\mathcal{Z}_{r})}k_{i,i^{\prime}}|i\rangle\langle
i^{\prime}|$ (39)

and, for each $i=1,\dots,\dim(\mathcal{Z}_{r})$ and
$j=1,\dots,\dim(\mathcal{W}_{r})$, let

$\displaystyle\tilde{S}_{i},\tilde{T}_{i}$ $\displaystyle:\mathcal{X}_{1\dots
r}\to\mathcal{Y}_{1\dots r}$ (40) $\displaystyle\tilde{B}_{j}$
$\displaystyle:\mathcal{Y}_{1\dots r}\to\mathcal{X}_{1\dots r}$ (41)

be the operators satisfying

$\tilde{S}=\sum_{i=1}^{\dim(\mathcal{Z}_{r})}\tilde{S}_{i}\otimes|i\rangle,\qquad\tilde{T}=\sum_{i=1}^{\dim(\mathcal{Z}_{r})}\tilde{T}_{i}\otimes|i\rangle,\qquad\tilde{B}=\sum_{j=1}^{\dim(\mathcal{W}_{r})}\tilde{B}_{j}\otimes|j\rangle$
(42)

so that (38) becomes

$\sum_{i,i^{\prime}=1}^{\dim(\mathcal{Z}_{r})}\sum_{j=1}^{\dim(\mathcal{W}_{r})}k_{i,i^{\prime}}\left(\langle\langle\tilde{S}_{i}|\otimes\langle\langle\tilde{B}_{j}|\right)|I_{\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots r}}\rangle\rangle\langle\langle I_{\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots
r}}|\left(|\tilde{T}_{i^{\prime}}\rangle\rangle\otimes|\tilde{B}_{j}\rangle\rangle\right).$
(43)

Using an identity from Ref. [Gut09, Proposition 3.5] we have that (43) becomes

$\sum_{i,i^{\prime}=1}^{\dim(\mathcal{Z}_{r})}\sum_{j=1}^{\dim(\mathcal{W}_{r})}k_{i,i^{\prime}}\langle\langle\tilde{S}_{i}|\tilde{B}_{j}^{*}\rangle\rangle\cdot\langle\langle\tilde{B}_{j}^{*}|\tilde{T}_{i^{\prime}}\rangle\rangle=\sum_{i,i^{\prime}=1}^{\dim(\mathcal{Z}_{r})}k_{i,i^{\prime}}\langle\langle\tilde{S}_{i}|B|\tilde{T}_{i^{\prime}}\rangle\rangle=\langle\langle\tilde{S}|\left(K\otimes
B\right)|\tilde{T}\rangle\rangle$ (44)

given that Bob’s co-strategy equals
$B=\sum_{j}|\tilde{B}_{j}^{*}\rangle\rangle\langle\langle\tilde{B}_{j}^{*}|$
as observed in Ref. [Gut09, Theorem 3.1]. ∎

######  Lemma 17.

Let $S,T$ be $r$-round strategies and let $\tilde{S},\tilde{T}$ be any
purifications of $S,T$. It holds that

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)=\max_{K}\min_{B}\;\Re\,\left({\langle\langle\tilde{S}|\left(K\otimes
B\right)|\tilde{T}\rangle\rangle}\right)$ (45)

where the minimum is over all compatible $r$-round co-strategies $B$ for Bob
and the maximum is over all $K\in\mathbf{K}(\mathcal{Z}_{r})$ acting on the
final memory space $\mathcal{Z}_{r}$ for Alice.

###### Proof.

By applying Lemma 16 to Eqn. (20), we get

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)=\min_{B}\max_{U}\left|\mspace{1.0mu}\langle\langle\tilde{S}|\left(U\otimes
B\right)|\tilde{T}\rangle\rangle\mspace{1.0mu}\right|=\min_{B}\max_{U}\;\Re\left(\langle\langle\tilde{S}|\left(U\otimes
B\right)|\tilde{T}\rangle\rangle\right),$ (46)

where the maximum is over all $U\in\mathbf{U}(\mathcal{Z}_{r})$. The advantage
of this identity is that the objective function is linear in $U$. Since linear
functions are also convex and since the maximum of a convex function over a
compact convex set is always achieved at an extreme point, the above quantity
does not change if we replace the maximization over unitaries with the
maximization over the convex hull of the unitaries. Namely,

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)=\min_{B}\max_{K}\;\Re\left(\langle\langle\tilde{S}|\left(K\otimes
B\right)|\tilde{T}\rangle\rangle\right),$ (47)

where the maximization is over all $K\in\mathbf{K}(\mathcal{Z}_{r})$. By a
standard min-max theorem from convex analysis (see, for example, [Roc70]), we
may reverse the order of optimization, concluding the proof. ∎

Now, with Lemmas 16 and 17 at our disposal, we proceed to prove the strategy
generalization of Uhlmann’s Theorem.

###### Proof of Theorem 10.

From Lemma 17, it follows that

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)\leq\max_{K}\min_{B}\left|\mspace{1.0mu}\langle\langle\tilde{S}|\left(K\otimes
B\right)|\tilde{T}\rangle\rangle\mspace{1.0mu}\right|.$ (48)

We square this inequality and apply Lemma 16 to obtain

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)^{2}\leq\max_{K}\min_{B}\,\langle\psi(\tilde{S},\tilde{B})|\left(K\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{T},\tilde{B})\rangle\langle\psi(\tilde{T},\tilde{B})|\left(K^{*}\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{S},\tilde{B})\rangle.$ (49)

Let us define $\bar{K}=\sqrt{I_{\mathcal{Z}_{r}}-K^{*}K}$ (noting that
$K^{*}K\preceq I_{\mathcal{Z}_{r}}$) and

$\Xi_{K}:\mathbf{L}(\mathcal{Z}_{r})\to\mathbf{L}(\mathcal{Z}_{r}):X\mapsto
KXK^{*}+\bar{K}X\bar{K}^{*},$ (50)

which is a quantum channel as its Kraus representation $\\{K,\bar{K}\\}$
satisfies $K^{*}K+\bar{K}^{*}\bar{K}=I_{\mathcal{Z}_{r}}$. Since

$\langle\psi(\tilde{S},\tilde{B})|\left(\bar{K}\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{T},\tilde{B})\rangle\langle\psi(\tilde{T},\tilde{B})|\left(\bar{K}^{*}\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{S},\tilde{B})\rangle\geq 0$ (51)

for all $K$ and all $\tilde{B}$, we have

$\displaystyle\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)^{2}$
$\displaystyle\leq\displaystyle\max_{K}\displaystyle\min_{B}\,\langle\psi(\tilde{S},\tilde{B})|\left[\left(\Xi_{K}\otimes
I_{\mathbf{L}(\mathcal{W}_{r})}\right)\left(|\psi(\tilde{T},\tilde{B})\rangle\langle\psi(\tilde{T},\tilde{B})|\right)\right]|\psi(\tilde{S},\tilde{B})\rangle$
(52)
$\displaystyle\leq\displaystyle\max_{\Xi}\displaystyle\min_{B}\,\langle\psi(\tilde{S},\tilde{B})|\left[\left(\Xi\otimes
I_{\mathbf{L}(\mathcal{W}_{r})}\right)\left(|\psi(\tilde{T},\tilde{B})\rangle\langle\psi(\tilde{T},\tilde{B})|\right)\right]|\psi(\tilde{S},\tilde{B})\rangle.$
(53)

However, we clearly have

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)^{2}=\min_{B}\max_{\Xi}\,\langle\psi(\tilde{S},\tilde{B})|\left[\left(\Xi\otimes
I_{\mathbf{L}(\mathcal{W}_{r})}\right)\left(|\psi(\tilde{T},\tilde{B})\rangle\langle\psi(\tilde{T},\tilde{B})|\right)\right]|\psi(\tilde{S},\tilde{B})\rangle$
(54)

due to Eqn. (20) and the fact that Uhlmann’s Theorem also holds replacing
unitaries with channels. Hence, the inequality (53) is in fact an equality due
to the max–min inequality. ∎

##  3 Monotonicity

Recall that strategy supermaps $\Upsilon$ map $r$-round strategies to
$r^{\prime}$-round strategies and they are linear and completely positive. For
our results, we need certain properties of the adjoints of strategy supermaps.
To this end, we first prove the following lemma.

######  Lemma 18.

If $X\in\mathbf{Pos}(\mathcal{Y}_{1\dots r}\mathcal{X}_{1\dots r})$ satisfies
$\langle X,S\rangle=1$ for all $r$-round strategies $S$ having input spaces
$\mathcal{X}_{1},\ldots,\mathcal{X}_{r}$ and output spaces
$\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r}$, then $X$ is an $r$-round co-strategy
having input spaces $\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r}$ and output spaces
$\mathcal{X}_{1},\ldots,\mathcal{X}_{r}$.

###### Proof.

If $X\succeq 0$ satisfies $\langle X,S\rangle=1$ for all strategies $S$, then
$X$ also satisfies $\langle X,S^{\prime}\rangle\leq 1$ for all $S^{\prime}$
such that $0\preceq S^{\prime}\preceq S$ for some strategy $S$. Thus, from
Ref. [GW07]666In the terminology of [GW07], we have that
$X\in(\downarrow\mathcal{S}_{r}(\mathcal{X}_{1\dots r},\mathcal{Y}_{1\dots
r}))^{\circ}$., we have that there exists a co-strategy $B$ such that
$X\preceq B$. For any pair of compatible strategy $S$ and co-strategy $B$, we
have $\langle B,S\rangle=1$ [GW07], therefore, we have $\langle
X,S\rangle=\langle B,S\rangle$ for all strategies $S$. Next, if we consider

$S=\frac{1}{\dim(\mathcal{Y}_{1\dots r})}I_{\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots r}},$ (55)

where $\dim(\mathcal{Y}_{1\dots r})$ is the product of the dimensions of
spaces $\mathcal{Y}_{1},\ldots,\mathcal{Y}_{r}$, then this is a valid
strategy. Then we get that $X$ and $B$ have the same trace. Since $0\preceq
X\preceq B$, we have that $X=B$, which completes the proof. ∎

We can now provide an important property of the adjoint of strategy supermaps.

######  Lemma 19.

If $\Upsilon$ is a strategy supermap from $r$-round strategies to
$r^{\prime}$-round strategies, then $\Upsilon^{*}$ is a co-strategy
supermap777Here, we define co-strategy supermaps in the analogous way as
strategy supermaps. from $r^{\prime}$-round co-strategies to $r$-round co-
strategies.

###### Proof.

Let $B$ be an $r^{\prime}$-round co-strategy. Then have have that

$\langle\Upsilon^{*}(B),S\rangle=\langle B,\Upsilon(S)\rangle=1$ (56)

for all $r$-round strategies $S$. Since $\Upsilon$ is completely positive, so
is $\Upsilon^{*}$, implying that $\Upsilon^{*}(B)$ is positive semidefinite.
From Lemma 18, we have that $\Upsilon^{*}(B)$ is an $r$-round co-strategy, as
required. ∎

###  3.1 Monotonicity of the strategy fidelity

We now provide a proof of Theorem 7.

###### Proof of Theorem 7.

Since $\Upsilon$ is completely positive, we can let

$\displaystyle\Upsilon$ $\displaystyle:S$
$\displaystyle\mapsto\operatorname{Tr}_{\mathcal{M}}(MSM^{*})$ (57)
$\displaystyle\Upsilon^{*}$ $\displaystyle:S^{\prime}$ $\displaystyle\mapsto
M^{*}(I_{\mathcal{M}}\otimes S^{\prime})M$ (58)

be Stinespring representations of $\Upsilon$ and its adjoint $\Upsilon^{*}$,
respectively, where the operator $M$ has the form

$M:\mathcal{Y}_{1\dots r}\mathcal{X}_{1\dots r}\to\mathcal{Y}^{\prime}_{1\dots
r^{\prime}}\mathcal{X}^{\prime}_{1\dots r^{\prime}}\mathcal{M}$ (59)

for some appropriately large space $\mathcal{M}$. Let

$\tilde{S},\tilde{T}:\mathcal{X}_{1\dots r}\to\mathcal{Y}_{1\dots
r}\mathcal{Z}_{r}$ (60)

be purifications of the $r$-round strategies $S,T$ for some appropriately
large final memory space $\mathcal{Z}_{r}$, and let
$|\tilde{S}\rangle\rangle,|\tilde{T}\rangle\rangle$ be their respective
vectorizations. Given the standard basis
$\\{|i\rangle:i\in\\{1,\ldots,\dim(\mathcal{X}_{1\dots r})\\}\\}$ of
$\mathcal{X}_{1\dots r}$, we have

$S=\sum_{i,j}\operatorname{Tr}_{\mathcal{Z}_{r}}\left(\tilde{S}|i\rangle\langle
j|\tilde{S}^{*}\right)\otimes|i\rangle\langle
j|=\mathrm{Tr}_{\mathcal{Z}_{r}}\bigg{(}{\bigg{(}\sum_{i}\tilde{S}|i\rangle\otimes|i\rangle\bigg{)}\bigg{(}\sum_{j}\langle
j|\tilde{S}^{*}\otimes\langle
j|\bigg{)}\bigg{)}}=\operatorname{Tr}_{\mathcal{Z}_{r}}\left(|\tilde{S}\rangle\rangle\langle\langle\tilde{S}|\right).$
(61)

Hence

$\Upsilon(S)=\operatorname{Tr}_{\mathcal{M}}\left(MSM^{*}\right)=\operatorname{Tr}_{\mathcal{Z}_{r}\mathcal{M}}\left((M\otimes
I_{\mathcal{Z}_{r}})|\tilde{S}\rangle\rangle\langle\langle\tilde{S}|(M^{*}\otimes
I_{\mathcal{Z}_{r}})\right),$ (62)

and an analogous equality holds for $T$ and $\tilde{T}$. Thus one can observe
that the vectors

$(M\otimes I_{\mathcal{Z}_{r}})|\tilde{S}\rangle\rangle,(M\otimes
I_{\mathcal{Z}_{r}})|\tilde{T}\rangle\rangle\in\mathcal{Y}_{1\dots
r}\mathcal{X}_{1\dots r}\mathcal{Z}_{r}\mathcal{M}$ (63)

are the vectorizations of purifications of the $r^{\prime}$-round strategies
$\Upsilon(S),\Upsilon(T)$ with final memory space
$\mathcal{Z}_{r}\mathcal{M}$.

By Eqn. (20) and Lemma 16 we have

$\operatorname{\mathrm{F}}_{\mathrm{r^{\prime}}}(\Upsilon(S),\Upsilon(T))=\min_{B^{\prime}}\max_{U^{\prime}}\left|\mspace{1.0mu}\langle\langle\tilde{S}|(M^{*}\otimes
I_{\mathcal{Z}_{r}})\left(U^{\prime}\otimes B^{\prime}\right)(M\otimes
I_{\mathcal{Z}_{r}})|\tilde{T}\rangle\rangle\mspace{1.0mu}\right|$ (64)

where the minimum is over all $r^{\prime}$-round co-strategies $B^{\prime}$
for Bob and the maximum is over all unitaries
$U^{\prime}\in\mathbf{U}(\mathcal{Z}_{r}\mathcal{M})$ on the final memory
space $\mathcal{Z}_{r}\mathcal{M}$ for Alice. The quantity (64) can only
decrease if we restrict the domain of maximization to unitaries of the form
$U\otimes I_{\mathcal{M}}$ for some $U\in\mathbf{U}(\mathcal{Z}_{r})$, thus

$\displaystyle\operatorname{\mathrm{F}}_{\mathrm{r^{\prime}}}(\Upsilon(S),\Upsilon(T))$
$\displaystyle\geq{\min_{B^{\prime}}\max_{U}}\left|\mspace{1.0mu}\langle\langle\tilde{S}|(M^{*}\otimes
I_{\mathcal{Z}_{r}})\left(U\otimes I_{\mathcal{M}}\otimes
B^{\prime}\right)(M\otimes
I_{\mathcal{Z}_{r}})|\tilde{T}\rangle\rangle\mspace{1.0mu}\right|$ (65)
$\displaystyle={\min_{B^{\prime}}\max_{U}}\left|\mspace{1.0mu}\langle\langle\tilde{S}|\left(U\otimes
M^{*}(I_{\mathcal{M}}\otimes
B^{\prime})M\right)|\tilde{T}\rangle\rangle\mspace{1.0mu}\right|$ (66)
$\displaystyle={\min_{B^{\prime}}\max_{U}}\left|\mspace{1.0mu}\langle\langle\tilde{S}|\left(U\otimes\Upsilon^{*}(B^{\prime})\right)|\tilde{T}\rangle\rangle\mspace{1.0mu}\right|.$
(67)

As the image under $\Upsilon^{*}$ of the set of all $r^{\prime}$-round co-
strategies is a subset of the set of all $r$-round co-strategies (by Lemma
19), the quantity (67) can only decrease if we extend the domain of
minimization to all $r$-round co-strategies $B$ for Bob:

$\operatorname{\mathrm{F}}_{\mathrm{r^{\prime}}}(\Upsilon(S),\Upsilon(T))\geq\min_{B}\max_{U}\left|\mspace{1.0mu}\langle\langle\tilde{S}|\left(U\otimes
B\right)|\tilde{T}\rangle\rangle\mspace{1.0mu}\right|=\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)$
(68)

as desired. ∎

###  3.2 Monotonicity of the strategy norm

###### Proof of Theorem 9.

By the definition of the strategy norm, Definition 8, we have

$\displaystyle\left\lVert\mspace{1.0mu}\Upsilon(H)\mspace{1.0mu}\right\rVert_{\diamond{\mathrm{r^{\prime}}}}$
$\displaystyle=\max\left\\{\left\langle
B^{\prime}_{0}-B^{\prime}_{1},\Upsilon(H)\right\rangle:\textnormal{$B^{\prime}_{0}+B^{\prime}_{1}$
is an $r^{\prime}$-round co-strategy, $B^{\prime}_{0},B^{\prime}_{1}\succeq
0$}\right\\}$ (69)
$\displaystyle=\max\left\\{\left\langle\Upsilon^{*}(B^{\prime}_{0})-\Upsilon^{*}(B^{\prime}_{1}),H\right\rangle:\textnormal{$B^{\prime}_{0}+B^{\prime}_{1}$
is an $r^{\prime}$-round co-strategy, $B^{\prime}_{0},B^{\prime}_{1}\succeq
0$}\right\\}$ (70) $\displaystyle\leq\max\left\\{\left\langle
B_{0}-B_{1},H\right\rangle:\textnormal{$B_{0}+B_{1}$ is an $r$-round co-
strategy, $B_{0},B_{1}\succeq 0$}\right\\}$ (71)
$\displaystyle=\left\lVert\mspace{1.0mu}H\mspace{1.0mu}\right\rVert_{\diamond{\mathrm{r}}}.$
(72)

Note that $\Upsilon^{*}$ is both linear and completely positive. Thus, given
$B^{\prime}_{0},B^{\prime}_{1}\succeq 0$ such that
$B^{\prime}_{0}+B^{\prime}_{1}$ is an $r^{\prime}$-round co-strategy, we have
that $B_{0}:=\Upsilon^{*}(B^{\prime}_{0})\succeq 0$ and
$B_{1}:=\Upsilon^{*}(B^{\prime}_{1})\succeq 0$ and, by Lemma 19, $B_{0}+B_{1}$
is an $r$-round co-strategy. But the image under $\Upsilon^{*}$ of the set of
all $r^{\prime}$-round co-strategies may be a strict subset of the set of all
$r$-round co-strategies, hence the inequality in the above expression. ∎

##  4 Semidefinite programming formulation for strategy fidelity

In this section, we use Lemma 17 to prove Theorem 12. From Lemma 17, we have
that

$\operatorname{\mathrm{F}_{\mathrm{r}}}(S,T)^{2}={\max}\;\\{\phi(K):K\in\mathbf{K}(\mathcal{Z}_{r})\\}$
(73)

where
$\phi(K):={\displaystyle\min_{B}}\;\Re\,\langle\langle\tilde{S}|\left(K\otimes
B\right)|\tilde{T}\rangle\rangle$, and $B$ is Bob’s co-strategy. By defining

$C:=\frac{1}{2}\operatorname{Tr}_{\mathcal{Z}_{r}}\left(\left(K\otimes
I_{\mathcal{Y}_{1\dots r}\mathcal{X}_{1\dots
r}}\right)|\tilde{T}\rangle\rangle\langle\langle\tilde{S}|\right)+\frac{1}{2}\left[\operatorname{Tr}_{\mathcal{Z}_{r}}\left(\left(K\otimes
I_{\mathcal{Y}_{1\dots r}\mathcal{X}_{1\dots
r}}\right)|\tilde{T}\rangle\rangle\langle\langle\tilde{S}|\right)\right]^{*}$
(74)

we can write

$\phi(K)={\min_{B}}\,\langle C,B\rangle.$ (75)

From [GW07, Corollary 7], we know that $B$ must satisfy $B=Q_{r}\otimes
I_{\mathcal{Y}_{r}}$ for some $(Q_{1},\ldots,Q_{r})$ satisfying

$\operatorname{Tr}(Q_{1})=1,\quad\operatorname{Tr}_{\mathcal{X}_{i}}(Q_{i})=Q_{i-1}\otimes
I_{\mathcal{Y}_{i-1}},\textup{ for }i\in\\{2,\ldots,r\\}$ (76)

and $Q_{1}\in\mathbf{Pos}(\mathcal{X}_{1})$,
$Q_{i}\in\mathbf{Pos}(\mathcal{Y}_{1\dots i-1}\otimes\mathcal{X}_{1\dots i})$,
for $i\in\\{2,\ldots,r\\}$. Thus, $\phi(K)$ can be formulated as a
semidefinite program. Its dual can be written as

$\alpha(K):=\max\Big{\\{}\;t\;:\;tI_{\mathcal{X}_{1}}\preceq\operatorname{Tr}_{\mathcal{Y}_{1}}(R_{1}),\\\
R_{j}\otimes
I_{\mathcal{X}_{j+1}}\preceq\operatorname{Tr}_{\mathcal{Y}_{j+1}}(R_{j+1})\textup{
for }j\in\\{1,\ldots,r-1\\},\;R_{r}\preceq C\;\Big{\\}},$ (77)

where $R_{j}\in\mathbf{Her}(\mathcal{Y}_{1\dots j}\otimes\mathcal{X}_{1\dots
j})$. Since this has a strictly feasible solution, as does the primal, we know
$\alpha(K)=\phi(K)$ by strong duality and $\alpha(K)$ attains an optimal
solution. We now let $M=\left[\begin{array}[]{cc}I_{\mathcal{Z}_{r}}&K\\\
K^{*}&I_{\mathcal{Z}_{r}}\end{array}\right]$ and set $M\succeq 0$ to get
$\|K\|\leq 1$. We can check that $C$ is a linear function in $M$ (since $M$ is
Hermitian). Thus, we have that the strategy fidelity can be written as in
Theorem 12.

##  5 Alice’s cheating in interactive bit-commitment and oblivious string
transfer

In this section we show that Alice can cheat with probability
$\operatorname{\mathrm{F}}_{r}(A^{0},A^{1})^{2}$ in either bit-commitment or
oblivious string transfer. The cheating has the same flavour in both cases:
Alice will follow the protocol honestly, then try to change her state as to
make it look like she chose the other strategy from the beginning. Suppose
Alice uses pure strategy $\tilde{A}^{a}$ and Bob uses pure co-strategy
$\tilde{B}$. For brevity, define for each $a\in\\{0,1\\}$ the following states

$|\psi_{a}\rangle:=|\psi(\tilde{A}^{a},\tilde{B})\rangle\quad\textup{ and
}\quad\sigma_{a}:=(\Xi^{a}\otimes
I_{\mathcal{W}_{r}})(|\psi_{a}\rangle\langle\psi_{a}|)$ (78)

where $\Xi_{a}$ is the strategy fidelity-achieving channel (from Definition
11) such that

$\langle\psi_{\bar{a}}|\sigma_{a}|\psi_{\bar{a}}\rangle\geq\operatorname{\mathrm{F}_{\mathrm{r}}}(A^{0},A^{1})^{2}.$
(79)

Note that the aim of $\Xi^{a}$ is to get $\sigma_{a}$ as close as possible to
$|\psi_{\bar{a}}\rangle\langle\psi_{\bar{a}}|$.

###  5.1 Bit-commitment

When we study interactive bit-commitment, we are applying the strategy/co-
strategy formalism _only_ to the Commit Phase. From the above discussion,
Alice can create the state

$\sigma_{a}\in\mathbf{Dens}(\mathcal{Z}_{r}\otimes\mathcal{W}_{r})$ (80)

to try to change her commitment from $a$ to $\bar{a}$. Then Alice continues
her actions to “reveal” $\bar{a}$ in the Reveal Phase, as does Bob (even
though Bob’s actions are not specified to Alice). We just assume that this
entire process is done by a unitary $U_{\bar{a}}$ acting on
$\mathcal{Z}_{r}\otimes\mathcal{W}_{r}$. Then, Bob has a projective
measurement $\\{\Pi_{accept},\Pi_{reject}\\}$ which accepts
$U_{\bar{a}}|\psi_{\bar{a}}\rangle$ with certainty, thus leading to a _non-
destructive measurement_. Thus, we have

$(I_{\mathcal{Z}_{r}}\otimes\Pi_{accept})U_{\bar{a}}|\psi_{\bar{a}}\rangle=U_{\bar{a}}|\psi_{\bar{a}}\rangle.$
(81)

This implies that

$(I_{\mathcal{Z}_{r}}\otimes\Pi_{accept})\succeq
U_{\bar{a}}|\psi_{\bar{a}}\rangle\langle\psi_{\bar{a}}|U_{\bar{a}}^{*}.$ (82)

However, Alice’s actions have led to them sharing
$U_{\bar{a}}\sigma_{a}U_{\bar{a}}^{*}$ at the end of the protocol. So, we have
that Alice successfully reveals $\bar{a}$ with probability

$\mathrm{A_{BC}}\geq\langle
I_{\mathcal{Z}_{r}}\otimes\Pi_{accept},U_{\bar{a}}\sigma_{a}U_{\bar{a}}^{*}\rangle\geq\left\langle
U_{\bar{a}}|\psi_{\bar{a}}\rangle\langle\psi_{\bar{a}}|U_{\bar{a}}^{*},U_{\bar{a}}\sigma_{a}U_{\bar{a}}^{*}\right\rangle=\left\langle|\psi_{\bar{a}}\rangle\langle\psi_{\bar{a}}|,\sigma_{a}\right\rangle\geq\operatorname{\mathrm{F}}_{r}(A^{0},A^{1})^{2}$
(83)

using Eqn. (79), as desired.

###  5.2 Oblivious string transfer

We can assume Alice uses a projective measurement $\\{\Pi^{a}_{z}\\}$ to learn
her desired string. Note that since $x_{a}$ is learned with certainty, this is
a _non-destructive measurement_ , as in the bit-commitment analysis above.
That is, we have

$\left(\Pi^{a}_{x_{a}}\otimes
I_{\mathcal{W}_{r}}\right)|\psi(\tilde{A}^{a},\tilde{B}^{x_{0},x_{1}})\rangle=|\psi(\tilde{A}^{a},\tilde{B}^{x_{0},x_{1}})\rangle$
(84)

for all $a$ and $(x_{0},x_{1})$. Again, this implies

$\Pi^{a}_{x_{a}}\otimes
I_{\mathcal{W}_{r}}\succeq|\psi(\tilde{A}^{a},\tilde{B}^{x_{0},x_{1}})\rangle\langle\psi(\tilde{A}^{a},\tilde{B}^{x_{0},x_{1}})|.$
(85)

Thus, after learning $x_{a}$, she can create the state $\sigma_{a}$ (defined
above) to try to learn $x_{\bar{a}}$. (Here, the $\tilde{B}$ in the definition
of $\sigma_{a}$ is $\tilde{B}^{x_{0},x_{1}}$.) Then she measures as if she had
used pure strategy $\tilde{A}^{\bar{a}}$ (that is, using
$\\{\Pi^{\bar{a}}_{z}\\}$) to try to learn $x_{\bar{a}}$. Then, using (85) and
the definitions in (78), we have

$\mathrm{A_{OT}}\geq\langle\Pi^{\bar{a}}_{x_{\bar{a}}}\otimes
I_{\mathcal{W}_{r}},\sigma_{a}\rangle\geq\langle\psi_{\bar{a}}|{\sigma_{a}}|\psi_{\bar{a}}\rangle\geq\operatorname{\mathrm{F}_{\mathrm{r}}}(A^{0},A^{1})^{2},$
(86)

as desired.

## Acknowledgements

Research at the Perimeter Institute is supported by the Government of Canada
through Industry Canada and by the Province of Ontario through the Ministry of
Research and Innovation. GG also acknowledges support from CryptoWorks21. JS
acknowledges support from NSERC Canada. Research at the Centre for Quantum
Technologies at the National University of Singapore is partially funded by
the Singapore Ministry of Education and the National Research Foundation, also
through the Tier 3 Grant “Random numbers from quantum processes,”
(MOE2012-T3-1-009). This material is based on research supported in part by
the Singapore National Research Foundation under NRF RF Award No. NRF-
NRFF2013-13.

## References

  * [ABDR04] Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, and Hein Röhrig.  Multiparty quantum coin flipping.  In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, pages 250–259. IEEE Computer Society, 2004.  https://doi.org/10.1109/CCC.2004.1313848DOI: 10.1109/CCC.2004.1313848.
  * [Amb01] Andris Ambainis.  A new protocol and lower bounds for quantum coin flipping.  In Proceedings of 33rd Annual ACM Symposium on the Theory of Computing, pages 134 – 142. ACM, 2001.  https://doi.org/10.1145/380752.380788DOI: 10.1145/380752.380788.
  * [BB84] Charles Bennett and Gilles Brassard.  Quantum cryptography: Public key distribution and coin tossing.  In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, pages 175–179. IEEE Computer Society, 1984.
  * [BCF+96] Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Benjamin Schumacher.  Noncommuting mixed states cannot be broadcast.  Physical Review Letters, 76:2818–2821, 1996.  https://doi.org/10.1103/PhysRevLett.76.2818DOI: 10.1103/PhysRevLett.76.2818.  arXiv:quant-ph/9511010.
  * [BDR05] Viacheslav P. Belavkin, Giacomo Mauro D’Ariano, and Maxim Raginsky.  Operational distance and fidelity for quantum channels.  Journal of Mathematical Physics, 46(6):062106, 2005.  https://doi.org/10.1063/1.1904510DOI: 10.1063/1.1904510.  arXiv:quant-ph/0408159.
  * [CDP08a] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti.  Transforming quantum operations: Quantum supermaps.  Europhysics Letters, 83(3):30004, 2008.  arXiv:0804.0180 [quant-ph].
  * [CDP08b] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti.  Memory effects in quantum channel discrimination.  Physical Review Letters, 101:180501, 2008.  https://doi.org/10.1103/PhysRevLett.101.180501DOI: 10.1103/PhysRevLett.101.180501.  arXiv:0803.3237 [quant-ph].
  * [CDP09] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti.  Theoretical framework for quantum networks.  Physical Review A, 80(2):022339, 2009.  https://doi.org/10.1103/PhysRevA.80.022339DOI: 10.1103/PhysRevA.80.022339.  arXiv:0904.4483 [quant-ph].
  * [CDP+13] Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, Dirk Schlingemann, and Reinhard F. Werner.  A short impossibility proof of quantum bit commitment.  Physics Letters A, 377(15):1076–1087, 2013.  https://doi.org/10.1016/j.physleta.2013.02.045DOI: 10.1016/j.physleta.2013.02.045.  arXiv:0905.3801v1 [quant-ph].
  * [CGS16] André Chailloux, Gus Gutoski, and Jamie Sikora.  Optimal bounds for semi-honest quantum oblivious transfer.  Chicago Journal of Theoretical Computer Science, (13), 2016.  https://doi.org/10.4086/cjtcs.2016.013DOI: 10.4086/cjtcs.2016.013.
  * [CK09] André Chailloux and Iordanis Kerenidis.  Optimal quantum strong coin flipping.  In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, FOCS 2009, pages 527–533, 2009.  https://doi.org/10.1109/FOCS.2009.71DOI: 10.1109/FOCS.2009.71.  arXiv:0904.1511 [quant-ph].
  * [CK11] André Chailloux and Iordanis Kerenidis.  Optimal bounds for quantum bit commitment.  In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011, pages 354–362, 2011.  https://doi.org/10.1109/FOCS.2011.42DOI: 10.1109/FOCS.2011.42.  arXiv:1102.1678 [quant-ph].
  * [CKS13] André Chailloux, Iordanis Kerenidis, and Jamie Sikora.  Lower bounds for quantum oblivious transfer.  Quantum Information and Computation, 13(1&2):158–177, 2013.  arXiv:1007.1875 [quant-ph].
  * [CKS14] André Chailloux, Iordanis Kerenidis, and Jamie Sikora.  Strong connections between quantum encodings, nonlocality, and quantum cryptography.  Phys. Rev. A, 89:022334, 2014.  https://doi.org/10.1103/PhysRevA.89.022334DOI: 10.1103/PhysRevA.89.022334.  arXiv:1304.0983 [quant-ph].
  * [DKSW07] Giacomo Mauro D’Ariano, Dennis Kretschmann, Dirk Schlingemann, and Reinhard F. Werner.  Reexamination of quantum bit commitment: The possible and the impossible.  Phys. Rev. A, 76:032328, 2007.  https://doi.org/10.1103/PhysRevA.76.032328DOI: 10.1103/PhysRevA.76.032328  arXiv:0605224 [quant-ph].
  * [FvdG99] Christopher A. Fuchs and Jeroen van de Graaf.  Cryptographic distinguishability measures for quantum mechanical states.  IEEE Transactions on Information Theory 45(4):1216–1227, 1999.  https://doi.org/10.1109/18.761271DOI: 10.1109/18.761271.
  * [Gut09] Gus Gutoski.  Quantum strategies and local operations.  PhD thesis, University of Waterloo, 2009.  arXiv:1003.0038 [quant-ph].
  * [Gut12] Gus Gutoski.  On a measure of distance for quantum strategies.  Journal of Mathematical Physics, 53(3):032202, 2012.  https://doi.org/10.1063/1.3693621DOI: 10.1063/1.3693621.  arXiv:1008.4636 [quant-ph].
  * [GW07] Gus Gutoski and John Watrous.  Toward a general theory of quantum games.  In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pages 565–574, 2007.  https://doi.org/10.1145/1250790.1250873DOI: 10.1145/1250790.1250873.  arXiv:quant-ph/0611234.
  * [Kit02] Alexei Kitaev.  Quantum coin-flipping.  Presentation at the 6th Workshop on _Quantum Information Processing_ (QIP 2003), 2002.
  * [KN04] Iordanis Kerenidis and Ashwin Nayak.  Weak coin flipping with small bias.  Information Processing Letters, 89(3):131–135, 2004.  https://doi.org/10.1016/j.ipl.2003.07.007DOI: 10.1016/j.ipl.2003.07.007.  arXiv:quant-ph/0206121.
  * [LC97] Hoi-Kwong Lo and Hoi Fung Chau.  Is quantum bit commitment really possible?  Physical Review Letters, 78(17):3410–3413, 1997.  https://doi.org/10.1103/PhysRevLett.78.3410DOI: 10.1103/PhysRevLett.78.3410.
  * [LC98] Hoi-Kwong Lo and Hoi Fung Chau.  Why quantum bit commitment and ideal quantum coin tossing are impossible.  Physica D: Nonlinear Phenomena, 120(1–2):177–187, September 1998\.  Proceedings of the Fourth Workshop on Physics and Consumption.  https://doi.org/10.1016/S0167-2789(98)00053-0DOI: 10.1016/S0167-2789(98)00053-0.
  * [May97] Dominic Mayers.  Unconditionally secure quantum bit commitment is impossible.  Physical Review Letters, 78(17):3414–3417, 1997.  https://doi.org/10.1103/PhysRevLett.78.3414DOI: 10.1103/PhysRevLett.78.3414.
  * [NS03] Ashwin Nayak and Peter Shor.  Bit-commitment based quantum coin flipping.  Physical Review A, 67(1):012304, 2003.  https://doi.org/10.1103/PhysRevA.67.012304DOI: 10.1103/PhysRevA.67.012304.  arXiv:quant-ph/0206123.
  * [NST15] Ashwin Nayak, Jamie Sikora, and Levent Tunçel.  Quantum and classical coin-flipping protocols based on bit-commitment and their point games.  Available as arXiv.org e-Print quant-ph/1504.04217, 2015.
  * [NST16] Ashwin Nayak, Jamie Sikora, and Levent Tunçel.  A search for quantum coin-flipping protocols using optimization techniques.  Mathematical Programming, 156(1):581–613, 2016.  https://doi.org/10.1007/s10107-015-0909-yDOI: 10.1007/s10107-015-0909-y.
  * [NC00] Michael A. Nielsen and Isaac Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, Cambridge, 2000.
  * [Roc70] R. Tyrrell Rockafellar.  Convex Analysis.  Princeton University Press, 1970.
  * [Rus94] M. B. Ruskai.  Beyond strong subadditivity? Improved bounds on the contraction of generalized relative entropy.  Reviews in Mathematical Physics, 6:1147–1161, 1994.  https://doi.org/10.1142/S0129055X94000407DOI: 10.1142/S0129055X94000407.
  * [Sik17] Jamie Sikora.  Simple, near-optimal quantum protocols for die-rolling.  Cryptography, 1(2), 11, 2017.  https://doi.org/10.3390/cryptography1020011DOI: 10.3390/cryptography1020011.
  * [SR01] Robert W. Spekkens and Terence Rudolph.  Degrees of concealment and bindingness in quantum bit commitment protocols.  Physical Review A, 65:012310, 2001.  https://doi.org/10.1103/PhysRevA.65.012310DOI: 10.1103/PhysRevA.65.012310.
  * [Uhl76] A. Uhlmann.  The “transition probability” in the state space of a *-algebra.  Reports on Mathematical Physics, 9(2):273–279, 1976.  https://doi.org/10.1016/0034-4877(76)90060-4DOI: 10.1016/0034-4877(76)90060-4.
  * [Wat09] John Watrous.  Semidefinite programs for completely bounded norms.  Theory of Computing, 5:217–238, 2009.  http://dx.doi.org/10.4086/toc.2009.v005a011DOI: 10.4086/toc.2009.v005a011.  arXiv:0901.4709v2 [quant-ph].
  * [Wat13] John Watrous.  Simpler semidefinite programs for completely bounded norms.  Chicago Journal of Theoretical Computer Science, (8), 2013.  http://dx.doi.org/10.4086/cjtcs.2013.008DOI: 10.4086/cjtcs.2013.008.
  * [Wie83] Stephen Wiesner.  Conjugate coding.  SIGACT News, 15(1):78–88, January 1983.  https://doi.org/10.1145/1008908.1008920DOI: 10.1145/1008908.1008920.