University of Cologne

Studying Stabilizer de Finetti Theorems

and Possible Applications

in Quantum Information Processing

Master Thesis by Paula Belzig

Date: 30th of April 2020

First assessor: Prof. Dr. David Gross

Second assessor: Prof. Dr. Renato Renner

Co-supervisor: Dr. Joe Renes

### Abstract

Symmetries are of fundamental interest in many areas of science. In quantum
information theory, if a quantum state is invariant under permutations of its
subsystems, it is a well-known and widely used result that its marginal can be
approximated by a mixture of tensor powers of a state on a single subsystem.
Applications of this quantum de Finetti theorem range from quantum key
distribution (QKD) to quantum state tomography and numerical separability
tests. Recently, it has been discovered by Gross, Nezami and Walter that a
similar observation can be made for a larger symmetry group than permutations:
states that are invariant under stochastic orthogonal symmetry are
approximated by tensor powers of stabilizer states, with an exponentially
smaller overhead than previously possible. This naturally raises the question
if similar improvements could be found for applications where this symmetry
appears (or can be enforced). Here, two such examples are investigated.

Using the postselection technique developed by Christandl, König and Renner
and generalized by Leverrier, we show that the new version of the quantum de
Finetti theorem leads to an improvement of known bounds on the diamond norm.
Subsequently, these bounds can be used in the context of a QKD protocol to
infer the security of general attacks (where an adversary can manipulate all
signals in any way they want) from the security of collective attacks (an
adversary is restricted to acting independently and identically on each
signal) with a smaller overhead on the security parameter than previously
possible.

Moreover, quantum de Finetti theorems naturally give rise to a way of
approximating separable quantum states by a hierarchy of semi-definite
programs (SDP). This facilitates (for example) the approximation of the
maximum fidelity of a quantum communication channel, which is an indicator for
the success of a quantum error correction procedure. Since the new version of
the quantum de Finetti Theorem describes closeness to separable tensor powers
of stabilizer states rather than arbitrary separable states, there is a clear
motivation to study if it can also lead to a similar SDP hierarchy for optimal
Clifford operations. Here, we find that it does, with a minimal change in
convergence speed.

Update [13 March 2024]: Our proposed fix for the proof from [1] for the
application of the postselection technique to QKD in Section 3.3.2 contains an
error that changes the scaling of the security parameter. We comment on this
at the appropriate places and refer to [2] for a detailed discussion.

###### Contents

  1. 1 Introduction and Motivation
  2. 2 Introducing Stabilizer de Finetti Theorems
    1. 2.1 Symmetry Groups
      1. 2.1.1 Permutation Invariance
      2. 2.1.2 Stochastic Orthogonal Invariance
    2. 2.2 Using Symmetries to Approximate States: de Finetti Theorems
  3. 3 The Postselection Technique Based on the Stabilizer de Finetti Theorem
    1. 3.1 Postselection Technique and its Relation to QKD
    2. 3.2 Generalized Postselection Technique for a Symmetry Group $\mathcal{S}$
    3. 3.3 Generalized Postselection Technique Applied to QKD
      1. 3.3.1 QKD Protocols, Min-entropy and Privacy Amplification
      2. 3.3.2 From Collective to General Attacks
    4. 3.4 Orbit Counting for Discrete Orthogonal Matrices
      1. 3.4.1 Orbit Counting Using Witt’s Lemma
      2. 3.4.2 Orbits of Discrete Orthogonal Group for Two Parties
      3. 3.4.3 Orbits of Discrete Orthogonal Group for N Parties
    5. 3.5 Results for QKD with Stochastic Orthogonal Symmetry
  4. 4 An SDP Hierarchy for Maximum Channel Fidelity Based on Stabilizer de Finetti Theorem
    1. 4.1 Approximating Maximum Channel Fidelity
    2. 4.2 Stabilizer de Finetti Theorem with Linear Constraints
    3. 4.3 An SDP Hierarchy for Maximum Channel Fidelity with Optimal Clifford Decoder
    4. 4.4 Remark on numerical tests
  5. 5 Summary and Outlook
  6. A Proof of the Bound on the Diamond Norm
    1. A.1 Resolution of Identity
    2. A.2 Preliminary Lemmata
  7. B Proof of the de Finetti Theorem with Linear Constraints
  8. C Stabilizer de Finetti Theorem with Linear Constraints with Stochastic Orthogonal Invariance on Both Sides

## 1 Introduction and Motivation

As information processing devices are decreasing in size, the impact of
quantum effects increases in relevance. In addition, the emergence of novel
devices like the quantum computer increase the need for understanding of the
rules and limits of information processing in a quantum setting, in particular
pertaining to secure and correct data transfer.

This work focuses on two important aspects of quantum information processing -
quantum key distribution (QKD) and quantum error correction (QEC) - and how
they can be investigated using various mathematical tools, particularly
quantum de Finetti theorems.

Quantum de Finetti theorems are an important result and a ubiquitous tool in
quantum information connecting permutation invariant quantum states to
independent and identically distributed quantum states (i.i.d. states): If a
quantum state that is spread over multiple subsystems is invariant under
swappings of the subsystems, its marginal can be approximated by a convex
mixture of i.i.d. states, where the approximation improves with increased
number of traced out systems [3, 4, 5, 6]. Thereby, this theorem can be used
to justify one of the most basic assumptions in physics, namely that the
properties of a large system can be inferred from experiments conducted on a
small part of it: if a physical law holds true in one subsystem, it is
justified to assume that it holds in all other subsystems and independently of
the subsystem. Similarly, an assumption of an i.i.d. structure is also at the
basis of many quantum information theoretical problems, like tomography [7]
and cryptography [3, 4]. Inferring the structure of a state (or a key encoded
in it) requires that its subsystems, which are measured separately, are in
fact identically distributed and independent from one another.

Additionally to their use in justifying important basic assumptions, quantum
de Finetti theorems also find application in many attempts at studying a
system’s quantum state - and here, we will study two such examples.

On the one hand, there is a direct and most natural application of quantum de
Finetti theorems to QKD security [3].

In this day and age, security of our communication systems has become more
important than ever. Sharing personal data online always comes at the risk of
revealing sensitive information to potentially bad actors. To safely share an
encrypted message, a secret, between two trusted parties (e.g. you and your
friend/your bank/your boss), we use a protocol called key distribution - at
the end of which both parties should have an identical string of bits (a key,
a password), while an adversary has no information about this shared
bitstring. Current classical cryptosystems usually rely on the fact that a
very large computing time prohibits a potential adversary from decrypting
messages [8]. However, the physical laws of quantum mechanics can provide
trusted parties with an advantage for communication, which can be exploited
for QKD.

While correlations between the trusted parties can become stronger in the
quantum mechanical framework, the potential eavesdropper also obtains an
advantage: entanglement can also be used to attack. There are two different
categories of attack: A most powerful general attack, where the adversary has
all resources available to them, and a collective attack, where the adversary
can only act identically and independently on each separate signal. One strong
result in QKD is the fact that the security of collective attacks implies the
security of general attacks, where the security parameter (and thus the chance
of information being revealed to the attacker) changes by a multiplicative
factor [3, 1, 9].

This is a direct result of quantum de Finetti theorems and leads to one of the
main results of this thesis: If a QKD protocol has a certain symmetry, namely
stochastic orthogonal symmetry introduced in [10], this factor becomes much
smaller than for previous attempts relying on permutation invariance, and thus
becomes much more achievable in a realistically small setup.

On the other hand, quantum de Finetti theorems find application in
approximating separable quantum states [11, 12, 13].

The transfer of a secret message is not only susceptible to an enemy’s
meddling, but also disturbances in the communication channel, like faulty
cables. Some such influences that corrupt the data can be counteracted by
error correction (at its simplest: exchanging a broken cable). If one cannot
pinpoint the exact instance where an error occurs, or there exist different
ways of correcting it, the success of an error correcting procedure can be
measured by determining the maximum success probability for transmitting a
uniform message over the channel [14]. Then, by comparing the maximum success
probabilities of different error correcting procedures, the best one can be
identified.

In a quantum setting, the safe transfer of data is threatened by classical
noise as well as disturbances at the quantum level, like thermal fluctuations
[15], which can be counteracted by QEC. Instead of maximum success
probability, the maximum channel fidelity of a given noisy channel is the
property that allows for comparison of the success of different QEC procedures
[16]. Maximum channel fidelity is the bilinear optimization problem of finding
the best possible combination of encoder and decoder for a given (and possibly
or partly corrected) noisy channel, and comparing input and output state of
the whole transfer to see how faithfully the state was recovered.

Instead of the complicated task of optimizing the combination of encoder and
decoder, the problem can be recast as a task for finding the best possible
separable state, which can be approximated by a hiearchy of converging
semidefinite programming (SDP) relaxations [13]. This hierarchy is chiefly
possible because of a quantum de Finetti theorem approximating states with
permutation invariance on one side (for example the decoder’s) by states with
separability between encoder and decoder. In this thesis, we show that an
analogous de Finetti theorem derived from [10] and a subsequent hierarchy can
be found for a different symmetry, leading to a hierarchy for maximum channel
fidelity with optimal Clifford decoder (or encoder, or both) instead of
optimal arbitrary encoder and decoder, which is interesting for studying
Clifford operations.

## 2 Introducing Stabilizer de Finetti Theorems

Symmetries appear in various physics related contexts: When symmetries exist,
systems often become much more straightforward to treat (e.g. crystal
structure), and when symmetries cease to exist, it is a key sign of critical
behaviour (e.g. phase transitions). Likewise, the same is true for many
problems in quantum information theory, where symmetry considerations can lead
to important information about the system’s state (e.g. concerning bosonic or
fermionic systems). One important and widely used result in quantum
information theory is the so called quantum de Finetti theorem, which relates
symmetric quantum states to i.i.d. states, which are often the desired and
most well-understood states for the analysis of many applications [3, 4].

This chapter contains a short introduction to symmetry groups in Section 2.1,
focussing on permutations and stochastic orthogonal symmetry in particular,
before outlining how the study of de Finetti theorems emerged and evolved in
Section 2.2, which ultimately lead to the discovery of a novel de Finetti
theorem in [10] which lies at the basis of this thesis.

###  2.1 Symmetry Groups

When there exists a set of operations or transformations which leave a
mathematical object unchanged, this property is referred to as a symmetry of
that object. This mathematical property occurs in numerous mathematical
contexts, including geometry, calculus and linear algebra. In this thesis, the
focus lies on symmetry in the context of group theory and representation
theory.

The symmetry group $\mathcal{S}$ of an object is the group of all
transfomations $s\in\mathcal{S}$ that leave the object invariant. The simplest
example is a sphere, which will remain exactly the same under any kind of
rotation about its center. Its symmetry group then consists of all these
rotations.

Within the space on which $\mathcal{S}$ acts, there could be multiple objects
that are left invariant by it. Such a set of objects, which are left invariant
under one and the same set of symmetry transformations $s\in\mathcal{S}$ spans
a subspace of the whole space, called the $\mathcal{S}$-invariant subspace:

######  Definition 1 ($\mathcal{S}$-invariant subspace).

Let $\mathcal{H}$ be a vector space, and let $\mathcal{S}$ be a symmetry group
acting on $\mathcal{H}$. Then, the $\mathcal{S}$-invariant subspace
$(\mathcal{H})^{s}\subseteq\mathcal{H}$ is defined as the vector space spanned
by the projection $\frac{1}{|\mathcal{S}|}\sum_{s\in\mathcal{S}}s$ applied to
$\mathcal{H}$.

Two symmetries that are central to this project are permutation invariance
(conventionally used in de Finetti type arguments) and stochastic orthogonal
invariance (appearing in [10], and possibly providing an advantage over
permutation invariance in de Finetti type considerations).

####  2.1.1 Permutation Invariance

Instead of working with a singular state $\rho$ on some Hilbert space
$\mathcal{H}$, quantum information processing tasks often consider many copies
of the same state, $\rho^{\otimes n}$ on a composite Hilbert space
$\mathcal{H}^{\otimes n}$, as an input to a protocol (e.g. teleportation [7],
quantum key distribution [17]). States with this type of structure are
generally referred to as i.i.d. states (as alluded to in Chapter 1). Because
many results on different information processing tasks rely on assuming an
i.i.d. state as input, it is of great importance and interest to analyse how
an arbitrary state differs from it. For many cases, such an analysis comes in
the form of de Finetti theorems, which show that a task’s symmetry can be
utilized to justify an approximation by a mixture of i.i.d. states (see
Section 2.2).

There are two main symmetry groups associated with such $n$-fold tensor
powers: the symmetric group $\mathcal{P}_{n}$ and the unitary group
$\mathcal{U}(d)$, which act on the $n$-fold copy of a $d$-dimensional Hilbert
space $\mathcal{H}$ in the following ways:

######  Definition 2 (Action of the symmetric group).

Let $\mathcal{H}$ be a $d$-dimensional complex vector space. Then, the action
of the symmetric group $\mathcal{P}_{n}$ on objects in $\mathcal{H}^{\otimes
n}$ is defined by the permutations $\pi\in\mathcal{P}_{n}$ with

${\pi}:\ket{\phi_{1}}\otimes\dots\otimes\ket{\phi_{n}}\mapsto\ket{\phi_{\pi_{1}}}\otimes\dots\otimes\ket{\phi_{\pi_{n}}}.$

######  Definition 3 (Action of the tensor power unitary group).

Let $\mathcal{H}$ be a $d$-dimensional complex vector space. Then, the action
of the unitary group $\mathcal{U}(d)$ on objects in $\mathcal{H}^{\otimes n}$
is defined by tensor powers of the unitary matrices $U^{\otimes n}$ for
$U\in\mathcal{U}(d)$ with

$U^{\otimes n}:\ket{\phi_{1}}\otimes\dots\otimes\ket{\phi_{n}}\mapsto
U\ket{\phi_{1}}\otimes\dots\otimes U\ket{\phi_{n}}.$

When considering a $n$-fold tensor power of some state $\rho$, the resulting
state $\rho^{\otimes n}$ is obviously invariant under permutation (i.e.
switching) of the subsystems, and therefore invariant under the action of the
symmetric group $\mathcal{P}_{n}$. Furthermore, any problem that involves the
eigenvalues of a state (like computing an entropy or a trace) will be
invariant under unitary operations $U:\rho\mapsto U\rho U^{\dagger}$ on each
subsystem $\rho\in\mathcal{H}$. Consequently, the $n$-fold tensor product
$\rho^{\otimes n}$ of the state will also be invariant under tensor powers of
unitaries, and thus invariant under the action of $U^{\otimes n}$.

There exists a special group theoretic duality between permutations of
subsystems and $n$-fold tensor powers of unitary operators $U^{\otimes n}$,
called Schur-Weyl-Duality (see, for example [18]). This duality emerges from
the fact that the two groups’ irreducible representations are double
commutants; the space of operators commuting with $n$-fold tensor powers
$U^{\otimes n}$ is spanned by permutations of the $n$ tensor factors, i.e. the
groups determine each other. Schur-Weyl duality is an important tool appearing
with applications in various areas of quantum information theory and
mathematics, for determining the spectrum of many copies of a density operator
[19, 20], studying the properties of the Haar-random state vector [21] and
(most importantly for this work) proving quantum de Finetti theorems [5].

One property of Schur-Weyl-duality is that the permutations and the unitaries
act on a state in different ways, namely with transversality. While the
permutations exchange the whole subsystem, a unitary $U$ acts on a single
subsystem, which could also contain multiple qudits, for example $r$. This
transversality is sketched in Figure 2.1.

Figure 2.1: Sketch to illustrate how unitaries $U$ and permutations $\pi$
affect the different subsystems of a state. Each black dot corresponds to a
qudit on the Hilbert space $\mathcal{H}=\mathbbm{C}^{d}$. While the unitary
operations act on a subsystem containing $r$ qudits, i.e. on a Hilbert space
$\mathcal{H}^{\otimes r}$, the permutation operations permute $n$ subsystems,
which can be regarded as an action on a Hilbert space
$\big{(}\mathcal{H}^{\otimes r}\big{)}^{\otimes n}$, or as a separate
permutation of all the first qudits in $\mathcal{H}^{\otimes r}$, all the
second qubits in $\mathcal{H}^{\otimes r}$, and so on.

####  2.1.2 Stochastic Orthogonal Invariance

Many aspects of quantum information theory make use of permutation symmetry
and its Schur Weyl duality to the unitary group, and its intimate connection
to $n$-fold copies of quantum states. However, one could consider a special,
interesting subgroup of the unitary group, the Clifford group, which is the
group of unitary operations that map the Pauli group onto itself under
conjugation. It appears in many subfields of quantum information science and
is intimately connected to a special set of states, which are called
stabilizer states, as they can be generated by applying Clifford operations to
the state $\ket{00\cdots 0}$ [22]. In fact, as it turns out, there is a close
relation between restricting oneself to $n$ copies of Clifford unitaries
$U_{C}^{\otimes n}$, which are a subset of unitary operations $U^{\otimes n}$,
and considering the set of $n$-fold tensor powers of stabilizer states
$\sigma^{\otimes n}$ instead of the set of $n$-fold tensor powers of arbitrary
states. Stabilizer states are a central object of quantum coding and are
frequently used as input states of quantum information processing tasks, for
example in entanglement based QKD [17], where one is interested in such
$n$-fold copies.

To further study the subset of Clifford unitaries and applications connected
to it, finding a version of Schur Weyl duality for the Clifford group by
identifying the commutant of tensor powers of Clifford unitaries is of great
interest, which was achieved by Gross, Nezami and Walter in [10]. Since the
group of Clifford unitaries is a subgroup of the whole unitary group, its
commutant contains permutations, but is not restricted to them. Therefore, to
construct the commutant, permutations were used as a basis and extended, which
eventually lead to the appearance of a new group that leaves tensor powers of
stabilizer states invariant: the stochastic orthogonal group. For a Clifford
unitary acting on $r$ qudits, the commutant of $n$-fold Clifford tensor powers
contains $r$-fold tensor powers of the action of the stochastic orthogonal
group, which acts on $n$ qudits. Details can be found in Chapter 4 of [10].

It must be noted that the commutant of tensor power Clifford unitaries is not
exclusively spanned by representations of tensor powers of the stochastic
orthogonal group, but also contains tensor powers of orthogonal projections
onto CSS codes. However, the additional basis elements are not unitary (and
not even invertible), and all unitary basis elements correspond to tensor
powers of the stochastic orthogonal group. Therefore, it is sufficient to
consider this group in the context of the de Finetti theorem.

Importantly, while the Schur-Weyl duality is not exact for all cases, the
property of transversality is recovered in this theory: stochastic orthogonal
transformations and Clifford unitaries act transversally, as sketched in
Figure 2.2. This means that there are generally three parameters appearing:
$d$, the dimension of a singular Hilbert space, $r$, the number of such
Hilbert spaces affected by a singular Clifford unitary, and $n$, the number of
copies of such Hilbert spaces that are transformed by stochastic orthogonal
transformations.

Figure 2.2: Sketch to illustrate how Clifford unitaries $U_{C}$ and stochastic
orthogonal transformations $O$ affect the different subsystems of a state.
Each black dot corresponds to a qudit on the Hilbert space
$\mathcal{H}=\mathbbm{C}^{d}$. While the Clifford unitaries act on a subsystem
containing $r$ qudits, i.e. on a Hilbert space $\mathcal{H}^{\otimes r}$, the
stochastic orthogonal operations act on $n$ such subsystems. Note the
similarities to Figure 2.1.

The stochastic orthogonal group is defined in the following way:

######  Definition 4 (Action of the stochastic orthogonal group).

The action of the stochastic orthogonal group $\mathcal{O}_{n}(d)$ is defined
by the stochastic orthogonal $n\times n$-matrices $O$:

  * •

The matrices $O$ are discrete orthogonal: $O^{T}O=\mathbbm{1}\mod d$

  * •

The matrices $O$ are stochastic: $O{v_{1}}={v_{1}}\mod d$ for the all-ones
vector ${v_{1}}=(1,1,...,1)$ containing $n$ ones.

For part of this project (namely, the results in Section 3.4), we consider a
slight relaxation of this definition, leading to the discrete orthogonal
group:

######  Definition 5 (Action of the discrete orthogonal group).

The action of the discrete orthogonal group $\tilde{\mathcal{O}}_{n}(d)$ is
defined by the discrete orthogonal $n\times n$-matrices $\tilde{O}$, with

$\tilde{O}^{T}\tilde{O}=\mathbbm{1}\mod d.$

This relaxation is justified because we are interested in the particular task
of counting orbits, i.e. basis elements which are distinct under the action of
the stochastic orthogonal group. The stochastic orthogonal group is a subgroup
of the discrete orthogonal group which leaves the all-ones vector invariant.
As long as $n$ is not a multiple of the local dimension $d$, there is a direct
relation between orbits of the stochastic orthogonal group
$\mathcal{O}_{n}(d)$ and the discrete orthogonal group
$\tilde{\mathcal{O}}_{n-1}(d)$. A more detailed justification of this
relaxation is given in Section 3.4.

The stochastic orthogonal group always contains permutations. In some cases
(for example for $(n,d)=(2,d)$, $(3,2)$ or $(3,3)$), the groups are actually
equal.

For qubits, some special group elements can be identified: In addition to the
usual permutation matrices, because of the modulo constraint, the binary
complement of any permutation will also be part of the group of stochastic
orthogonal matrices. These kinds of operations are termed anti-permutations in
[10]. For example, the $r$-qubit anti-identity
$O_{\tilde{I}}\in\mathcal{O}_{6}(2)$ on $n=6$ subsystem copies is the
following $n\times n$-matrix:

$O_{\tilde{I}}=\begin{pmatrix}0&1&1&1&1&1\\\ 1&0&1&1&1&1\\\ 1&1&0&1&1&1\\\
1&1&1&0&1&1\\\ 1&1&1&1&0&1\\\ 1&1&1&1&1&0\end{pmatrix}$ (2.1)

For $n$ copies, the $r$-qubit anti-identity representation (acting on
$\big{(}(\mathbbm{C}^{d})^{\otimes r}\big{)}^{\otimes n}$) is given by:

$R(O_{\tilde{I}})=\frac{1}{2^{r}}\big{(}\mathbbm{1}^{\otimes n}+X^{\otimes
n}+Y^{\otimes n}+Z^{\otimes n}\big{)}^{\otimes r}$ (2.2)

There are some particularities connected to stabilizer states which lead to
some constraints on $n$ and $d$ for all results in [10], including the de
Finetti theorem which is the basis of this project. To counteract this
restriction, instead of considering invariance under the stochastic orthogonal
group, investigating a subset of non-trivial operations that leave tensor
powers of stabilizer states invariant could lead to analogous results for
combinations of $n$ and $d$ that were excluded before. In particular, these
restrictions encompass that the theorem does not hold for qubits ($d=2$),
which are interesting for numerical studies and easy examples. As we will
observe in the next section, considering a state’s invariance under
permutations plus anti-identity leads to a de Finetti statement for qubits.

More details and examples describing the commutant of Clifford unitaries can
be found in Chapter 4.3 of [10].

###  2.2 Using Symmetries to Approximate States: de Finetti Theorems

Almost anything we could want to know about a quantum system is intimately
connected to the system’s quantum state. Studying states, and classifying them
and their correlations, is therefore a central objective in quantum theory,
for example in quantum state tomography [23] or entanglement certification
[24]. In quantum information, where one is frequently interested in multiple
copies of one state, there is a class of states that is of particular
importance: i.i.d. states. Given a quantum state $\rho$ on a Hilbert space
$\mathcal{H}=\mathbbm{C}^{d}$, a tensor product of $n$ copies of the state
$\rho$, the state $\rho\otimes\rho\otimes\cdots\otimes\rho=\rho^{\otimes n}$
on the Hilbert space $\mathcal{H}^{\otimes
n}=\big{(}\mathbbm{C}^{d}\big{)}^{\otimes n}$, would be an example of an
i.i.d. state, as it is independently and identically distributed over the $n$
subsystems. Any mixture of i.i.d. states is also an i.i.d. state.

Many quantum information processing tasks assume this structure, and most
mathematical framework and results are built around it. This assumption is
connected to a very important result and tool in quantum information
processing: quantum de Finetti theorems. On its own, a quantum de Finetti
theorem describes the closeness of a class of states (usually: permutation
invariant states) to an i.i.d. state, which can be used to justify an i.i.d.
assumption and give an error on it. Thereby, this theorem can also be employed
as a mathematical tool for approximating states, for example in terms of a
numerical hierarchy.

The classical de Finetti theorem was first introduced in [25] and [26], the
first of which was translated in [27]; further details about de Finetti’s work
on probability theory and statistics can be found in [28]. It is a statement
relating symmetric probability distributions to i.i.d. probability
distributions. More specifically, it states that a marginal distribution (of a
potentially small subset of variables) of a symmetric probability distribution
is close (with an error $\leq\epsilon$) to a mixture of i.i.d. probability
distributions.

Clearly, a quantum analogue of such a statement, where a marginal of a large
symmetric state could be related to an i.i.d. state, is of interest for many
problems in quantum information processing. First attempts at generalizing the
classical de Finetti theorem to a quantum context can be found in [29, 30],
and subsequently garnered significant interest following [3], where this idea
was first explored in the context of its most immediate and obvious
application, the security of a QKD protocol with a given symmetry. One
important result is the fact that the permutation invariance of a given
protocol can be used to prove that its security against general attacks (where
an adversary may act on all signals at once and even be entangled with the
system) can be inferred from its security against collective attacks (where
the adversary acts i.i.d.ly on each signal).

However, this is by far not the only situation where quantum de Finetti
theorems have found application. Many quantum information theory problems
previously relied on the assumption that the resources are independent and
ideally distributed, which can now be scrutinized and often justified via de
Finetti type arguments, for example in the study of quantum tomography [7].
Furthermore, de Finetti theorems are useful for bounding the diamond norm of a
permutation invariant channel [1], and can be employed to provide an
alternative proof of quantum Shannon reverse coding theorem [31]. In addition,
there is a close connection to the approximation of separable states by a
hierarchy of symmetric extensions [12]. Studying the set of separable states
is a difficult but ubiquitous problem with application to countless aspects of
quantum information theory, and of great importance for improving our
understanding of entanglement in general [11].

Since the earlier versions of the theorem require the number of traced out
systems to be rather large (which is especially problematic considering the
size of the devices that are currently being developed), an improvement in the
form of the exponential de Finetti theorem [4] was proposed. In this version,
the state must only be exponentially close to the uniform state. However, the
resulting bounds are still largely unattainable in practical implementations.
Several more attempts have been made to generalize and explore the
possibilities of this theorem [32, 5, 33, 34, 35, 36].

The most recent and currently best known version of a finite quantum de
Finetti theorem is the following:

######  Theorem 2.2.1 (Quantum de Finetti Theorem, see [6]).

Let $\rho_{B_{1}^{n}}$ be a quantum state on ${(\mathcal{H}_{B})}^{\otimes
n}={\big{(}{(\mathbbm{C}^{d})}\big{)}}^{\otimes n}$ that commutes with the
action of $\mathcal{P}_{n}$. Let $k\in[1,n]$. Then, there exists a probability
distribution $p$ on the set of mixed states on $\mathbbm{C}^{d}$, such that

$\Big{\|}\rho_{B_{1}^{k}}-\int p(\rho_{B})\rho_{B}^{\otimes
k}\Big{\|}_{\operatorname{tr}}\leq 2d^{2}\frac{k}{n}.$

In [10], a new version with promisingly low error values was proposed, which
is the basis of our analysis in this work. In contrast to first versions, this
new de Finetti theorem takes into account a new symmetry beyond permutation
symmetry. Instead, it considers protocols that are invariant under stochastic
orthogonal symmetry, as introduced in Definition 2.1.2. Because of
particularities of the stabilizer formalism, this theorem will only hold for
some specific cases, namely for odd prime dimensions $d$.

######  Theorem 2.2.2 (Stabilizer de Finetti Theorem, see [10], Theorem 7.6).

Let $\rho_{B_{1}^{n}}$ be a quantum state on ${(\mathcal{H}_{B})}^{\otimes
n}={\big{(}{(\mathbbm{C}^{d})}^{\otimes r}\big{)}}^{\otimes n}$ that commutes
with the action of $\mathcal{O}_{n}(d)$, with $d$ being an odd prime. Let
$k\in[1,n]$. Then, there exists a probability distribution $p_{S}$ on the set
of mixed stabilizer states of $r$ qudits, such that

$\Big{\|}\rho_{B_{1}^{k}}-\sum_{\sigma}p_{S}(\sigma_{B})\sigma_{B}^{\otimes
k}\Big{\|}_{\operatorname{tr}}\leq 2d^{2(r+1)^{2}}d^{-\frac{1}{2}(n-k)}.$

However, knowledge about the commutant of tensor powers of the Clifford group
can also be used to infer a version of the stabilizer de Finetti theorem for a
simpler case, dimension $d=2$. In general, a state being invariant under
something more than permutations can lead to an alternative version - so a
special case to regard is the case of invariance under permutation and one
additional group action, the anti-identity introduced in (2.2). This leads to
the following stabilizer de Finetti theorem for qubits:

######  Theorem 2.2.3 (Stabilizer de Finetti Theorem for Qubits, see [10],
Theorem 7.7).

Let $\rho_{B_{1}^{n}}$ be a quantum state on ${(\mathcal{H}_{B})}^{\otimes
n}={\big{(}{(\mathbbm{C}^{2})}^{\otimes r}\big{)}}^{\otimes n}$ that commutes
with all permutations and the action of the anti-identity on a subsystem
consisting of six $r$-qubit blocks. Let $k\in[1,n]$ be a multiple of six.
Then, there exists a probability distribution $p_{S}$ on the set of mixed
stabilizer states of $r$ qubits, such that

$\Big{\|}\rho_{B_{1}^{k}}-\sum_{\sigma}p_{S}(\sigma_{B})\sigma_{B}^{\otimes
k}\Big{\|}_{\operatorname{tr}}\leq 6\sqrt{2}\ 2^{r}\sqrt{\frac{k}{n}}.$

For a true comparison between Theorem 2.2.1 and Theorems 2.2.2 and 2.2.3, it
must be noted that the subspaces which are permuted or orthogonally
transformed differ slightly. In the stabilizer de Finetti theorems, each
subspace contains $r$ qudits (or qubits) that are transformed by stochastic
orthogonal transformations (or permutations and anti-identity). To compare the
bounds to the bound of the de Finetti theorem with permutation invariance, one
therefore needs to consider a subspace containing $r$ qudits, of which there
are $n$ copies, which are permuted. Then, for a state on
${(\mathcal{H}_{B})}^{\otimes n}={\big{(}{(\mathbbm{C}^{2})}^{\otimes
r}\big{)}}^{\otimes n}$ that commutes with all permutations of the $n$
subsystems, the permutation-based de Finetti theorem in 2.2.1 holds if the
dimension $d$ in the bound is replaced by $d^{r}$.

Therefore, the bounds which should be compared in the case where $d=2$ and
$k\leq n$ is a multiple of 6 are the following:

$\epsilon_{\text{perm}}=2^{2r+1}\frac{k}{n}\text{ and }\epsilon_{\text{anti-
identity}}=12\sqrt{2}\ 2^{r}\sqrt{\frac{k}{n}}$

It can be noted that, for qubits, approximating an orthogonally invariant
state by a convex combination of stabilizer states is more costly in the limit
of large $n$ than an approximation of permutation invariant states by a convex
combination of i.i.d. states. But while the stabilizer de Finetti theorem for
qubits in 2.2.3 leads to no improvement in the convergence (and therefore e.g.
error rate for QKD security proofs), it is nonetheless interesting in cases
where one is interested in studying stabilizer states specifically (like, for
example, in Chapter 4).

For $d$ an odd prime, the following bounds are eligible for comparison:

$\epsilon_{\text{perm}}=2d^{2r}\frac{k}{n}\text{ and
}\epsilon_{\text{ortho}}=2d^{2(r+1)^{2}}d^{-\frac{1}{2}(n-k)}$

As the bound for stochastic orthogonal invariance is exponential in the number
of copies $n$, this bound provides a significant improvement in the limit of
large $n$. Therefore, using this de Finetti theorem has two advantages, which
both motivate this project: On the one hand, it shows improved convergence in
the limit of large $n$, which is interesting for QKD error rates (Chapter 3).
On the other hand, it is interesting for problems that could benefit from
using stabilizer states as input (like entanglement based QKD, or quantum
error correction related problems, Chapter 4).

## 3 The Postselection Technique Based on the Stabilizer de Finetti Theorem

The postselection technique as introduced in [1] is a mathematical tool to
bound the diamond norm without performing an optimization over the state
space, which will be motivated and described in detail in Section 3.1. In this
chapter, the technique is generalized to accommodate different symmetry
groups, which includes developing the necessary mathematical framework in
Section 3.2 and investigating its usefulness in QKD settings in Section 3.3,
before it can be applied to the stochastic orthogonal group via Section 3.4
and 3.5.

###  3.1 Postselection Technique and its Relation to QKD

QKD is the task of generating a string of bits (a key) that is only known to
two trusted distant parties, Alice and Bob, whilst being completely unknown to
an additional party, the adversary Eve. It is assumed that Alice and Bob are
linked by an authentic classical communication channel and a potentially
insecure quantum channel.

The setting can be described as follows: between them, Alice and Bob ideally
share $n$ copies of a quantum state on a $d$-dimensional Hilbert space
$\mathcal{H}$, on which they perform measurements to obtain a secret key. In
total, they thereby have access to a state on the trusted Hilbert space
$\mathcal{H}^{\otimes n}\equiv\mathcal{H}_{T}$, which decomposes into the
singular Hilbert spaces $\mathcal{H}$. However, the adversary Eve also has
access to a Hilbert space of her own, denoted by $\mathcal{H}_{E}$, and Alice
and Bob’s input state could be correlated with Eve’s state, therefore giving
her indirect access to the states that encode Alice and Bob’s secret key.
Therefore, proving security of a given QKD protocol essentially revolves
around bounding Eve’s influence on the state on the whole, combined Hilbert
space $\mathcal{H}_{T}\otimes\mathcal{H}_{E}$, see Figure 3.1.

A QKD protocol for two parties is described by a quantum channel, which is a
completely positive, trace preserving (CPTP) map $\mathcal{E}$, that
transforms Alice and Bob’s shared input state into two keys. The security of a
QKD protocol $\mathcal{E}$ is defined through a comparison between such a
quantum channel $\mathcal{E}$ and an ideal version of the same protocol
$\mathcal{F}$, which transforms the same input state into two identical keys,
with no information about those keys leaking to the eavesdropper Eve. The
closer the actual protocol $\mathcal{E}$ is to the ideal protocol
$\mathcal{F}$, the more secure it is. In other words, if the distance between
the two CPTP maps $\mathcal{E}$ and $\mathcal{F}$ is very small, while taking
Eve’s access into account, the protocols are approximately equal and
$\mathcal{E}$ is approximately secure.

Mathematically, a natural measure of security is therefore given by a
difference between two CPTP maps in terms of the diamond distance.

Figure 3.1: Sketch of the parts making up the total Hilbert space of Alice,
Bob and Eve in a QKD scheme. The pair of Alice and Bob shares $n$ copies of a
quantum state on the $d$-dimensional Hilbert space $\mathcal{H}$, thereby
having access to the entire trusted Hilbert space
$\mathcal{H}_{T}=\mathcal{H}^{\otimes n}$. Eve, the untrusted party and
potential eavesdropper, also has access to some Hilbert space
$\mathcal{H}_{E}$, which the trusted parties know nothing about. In total, the
entire Hilbert space therefore consists of the combination of Alice and Bob’s
and Eve’s space: $\mathcal{H}_{T}\otimes\mathcal{H}_{E}$. Usually, it is
assumed that the worst case scenario applies, where Eve has access to a
complete copy of Alice and Bob’s Hilbert space, i.e.
$\mathcal{H}_{E}=\mathcal{H}_{T}=\mathcal{H}^{\otimes n}$. (With less, she
could not properly entangle herself with each of the trusted qudits.)

######  Definition 6 (Diamond distance between two CPTP maps).

Let $\Delta=\mathcal{E}-\mathcal{F}$ be a difference between CPTP maps
$\mathcal{E}$ and $\mathcal{F}$ acting on the Hilbert space $\mathcal{H}_{T}$,
let $\mathcal{H}_{E}$ be a Hilbert space, and
$\rho_{TE}\in\mathfrak{S}(\mathcal{H}_{T}\otimes\mathcal{H}_{E})$ be a quantum
state. Then, the diamond distance between the maps, i.e. the diamond norm of
$\Delta$, is given by

$\big{\|}\Delta\big{\|}_{\diamond}=\sup_{\rho_{TE}\in\mathfrak{S}(\mathcal{H}_{T}\otimes\mathcal{H}_{E})}\big{\|}(\Delta\otimes\mathbbm{1}_{E})\rho_{TE}\big{\|}_{\operatorname{tr}}$

The trace norm in the above definition is defined by:
$\big{\|}\rho\big{\|}_{\operatorname{tr}}=\frac{1}{2}\big{\|}\rho\big{\|}_{1}=\frac{1}{2}\operatorname{tr}\big{(}\sqrt{\rho^{\dagger}\rho}\big{)}$.

In principle, the diamond norm constitutes taking two suprema, one over the
input state, and one over the dimension of the space $\mathcal{H}_{E}$ (Eve’s
space) that the identity acts on; however, for positive quantum states, the
suprema are reached for $\mathcal{H}_{E}$ having equal dimension to
$\mathcal{H}_{T}$ [37], which we suppose for the QKD analysis. Using this
distance measure, security of a protocol is then defined by comparing the
diamond distance of a protocol $\mathcal{E}$ and a perfect version of the
protocol $\mathcal{F}$ to some small parameter $\epsilon$ that bounds the
probability of not obtaining perfectly identical, secret keys for Alice and
Bob.

######  Definition 7 ($\epsilon$-security).

A protocol $\mathcal{E}$ is $\epsilon$-secure if

$\big{\|}\mathcal{E}-\mathcal{F}\big{\|}_{\diamond}\leq\epsilon.$

Clearly, this kind of comparison between an actual protocol and a perfect
version (where Alice and Bob share i.i.d. states that are decoupled from an
adversary’s state) is closely related to quantum de Finetti theorems, where a
marginal of a large symmetric state can be approximated by an i.i.d. state
(more precisely, a mixture of i.i.d. states). In fact, this has been a key
motivation for studying quantum de Finetti theorems in the first place [3].
Thereby, it can be proven that the security of a protocol against a collective
attack implies its security against a much more powerful general attack, at
the cost of an overhead factor. In most quantum de Finetti theorems, tracing
out a small number of systems leads to unattainable security parameters (large
$\epsilon$ and impossible key lengths for practical purposes) [38, 39].
Subsequent improvements on the bound of the theorem resulted in improvements
of the corresponding security parameters, but are in general still far from
useful for current applications.

Another alternative way of improving security bounds, in particular the
additional factor between collective and general attacks, emerged in the form
of the postselection technique [1] discovered by Christandl, König and Renner.
By definition, computing the diamond norm in principle entails an optimization
over a large number of states. However, this can be circumvented by the
postselection technique, which showed that it is sufficient to consider a
single input state $\tau_{TR}$. Namely, if the map $\Delta$ is invariant under
the group of permutations $\mathcal{P}_{n}$, the diamond norm of $\Delta$ is
bound in the following way:

$\big{\|}\Delta\big{\|}_{\diamond}\leq
g_{n,d}\big{\|}(\Delta\otimes\mathbbm{1}_{R})\tau_{TR}\big{\|}_{\operatorname{tr}}$
(3.1)

with

$g_{n,d}=\left(\begin{array}[]{c}d^{2}-1+n\\\ \
n\end{array}\right)\leq(n+1)^{d^{2}-1}.$ (3.2)

The state $\tau_{T{R}}$ is the purification of a particular input state, which
is called the de Finetti state, with a specific form:

$\tau_{T}=\int\rho^{\otimes n}\mu(\rho)$ (3.3)

with $\rho\in\mathfrak{S}({\mathcal{H}})$, where $\mathcal{H}$ is a
$d$-dimensional Hilbert space. $\mu$ is the measure induced by the Hilbert-
Schmidt metric on a single subsystem $\operatorname{End}(\mathcal{H})$.

Apart from its application to QKD, this is an interesting mathematical bound
on the diamond norm which is useful in any scenario where the
distinguishability of quantum operators is of interest [40, 41]. Note that an
alternative version and proof of this bound can be found in [42]. The
technique was generalized and adapted to continuous variable schemes by
Leverrier [9]. In the case of continuous variables, there is an additional
step to replace the total Hilbert space with a finite dimensional Hilbert
space (“energy test”).

In the next section, we will show that the technique can also be generalized
to accommodate symmetry groups beyond permutation invariance, leading to an
analogous bound on the diamond norm that depends on the dimension of an
invariant subspace.

###  3.2 Generalized Postselection Technique for a Symmetry Group
$\mathcal{S}$

Generalizing de Finetti type arguments for symmetries beyond permutation is
not a novel concept [9, 36]. In fact, there is a short comment in the outlook
and appendix of [1] itself which outlines how the postselection technique can
be generalized to arbitrary symmetries. Nonetheless, it can be considered
interesting to analyze this in more detail and scrutinize the necessary steps
and assumptions. There is one main assumption, the resolution of identity,
which we will investigate at the beginning of this section and in Appendix
A.1. All necessary lemmata for the proof of the bound on the diamond norm for
arbitrary symmetry groups $\mathcal{S}$ can be found in Appendix A.2.

As a first step of extending the postselection technique to a symmetry group
$\mathcal{S}$, a generalization of the de Finetti state must be considered. In
analogy to (3.3), such a (symmetry-dependent) de Finetti state of
$\mathcal{S}$ is given by
$\tau_{T}\in\mathfrak{S}(\mathcal{H}_{T})=\mathfrak{S}(\mathcal{H}^{\otimes
n})$ :

$\tau_{T}=\int\rho^{\otimes n}D_{\mathcal{S}}(\rho)$ (3.4)

with states $\rho\in\mathfrak{S}({\mathcal{H}})$ and a symmetry-dependent
integration measure $D_{\mathcal{S}}$.

The assumption that justifies applying the postselection technique is not tied
to $\tau_{T}$ directly, but to a purification of it, where each of the $n$
subsystems has been purified separately. This defines the state
$\tau_{TE}\in\mathfrak{S}(\mathcal{H}_{T}\otimes\mathcal{H}_{E})=\mathfrak{S}(\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n})$:

$\tau_{TE}=\int\tilde{\rho}^{\otimes n}{d}_{\mathcal{S}}(\tilde{\rho})$ (3.5)

with the pure states
$\tilde{\rho}\in\mathfrak{S}(\mathcal{H}\otimes\mathcal{H})$.

Then, for the postselection technique to be applicable, this state has to
fulfill the following relation, called resolution of identity:

$\tau_{TE}=\frac{1}{g_{n,d}}\mathbbm{1}_{(\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes
n})^{(s\otimes\overline{s})}}=\frac{1}{\dim(\mathcal{N})}\mathbbm{1}_{{N}}$
(3.6)

with

$g_{n,d}=dim((\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(s\otimes\overline{s})})=\dim(\mathcal{N}).$ (3.7)

In other words, the state $\tau_{TE}$ must be maximally mixed on the
$\mathcal{S}$-invariant subspace
$(\mathcal{H}_{T}\otimes\mathcal{H}_{E})^{(s\otimes\overline{s})}\equiv\mathcal{N}$.
This implies that the symmetry-dependent integration measure must be invariant
under the symmetry $\mathcal{S}$.

Since the resolution of identity is a key ingredient to proving a bound on the
diamond norm using the postselection technique, it must therefore be assumed
that an integration measure $d_{\mathcal{S}}(\cdot)$ exists such that (3.6)
holds and $D_{\mathcal{S}}(\cdot)$ exists. Since all states $\tilde{\rho}$ are
pure, $d_{\mathcal{S}}(\cdot)$ is a measure on pure states. Then, the
existence of an integration measure $D_{\mathcal{S}}(\cdot)$ can be inferred
from the existence of $d_{\mathcal{S}}(\cdot)$. To allow for a resolution of
identity, the integration measure $d_{S}(\cdot)$ must be invariant under the
symmetry $\mathcal{S}$.

Rephrased in mathematical terms, the postselection technique can only be
applied for a symmetry group $\mathcal{S}$ if the following condition holds:

$\operatorname{Cond0}=\Big{\\{}\exists d_{\mathcal{S}}(\cdot)\
\operatorname{s.t.}\ \int\tilde{\rho}^{\otimes
n}{d}_{\mathcal{S}}(\tilde{\rho})=\frac{1}{g_{n,d}}\mathbbm{1}_{{N}}\Big{\\}}$
(3.8)

For the symmetric group $\mathcal{P}_{n}$ with permutations as its
representation, the required integration measures are the one induced by the
Hilbert-Schmidt metric as $D_{\mathcal{P}_{n}}(\cdot)$, and the one induced by
the Haar measure on the unitary group acting on
$\mathcal{H}\otimes\mathcal{H}$ as ${d}_{\mathcal{P}_{n}}(\cdot)$. Then, since
the measure for $\tau_{TE}$ is invariant under permutations and under unitary
group (its dual under Schur-Weyl-duality), a resolution of identity holds
because of Schur’s lemma [1].

In the case of continuous variables [9], another integration measure is
needed. Instead of independent and ideally distributed states, the states of
interest are the general coherent states $\rho^{\otimes
n}=\ket{\Lambda,n}\bra{\Lambda,n}=(\ket{\Lambda,1}\bra{\Lambda,1})^{\otimes
n}$. For such states, an invariant measure on the corresponding space is
established in [43], and their resolution of identity relies on a version of
Schur’s lemma for general unimodular groups with a square-integrable
representation (such as $SU(p,q)$) [35]. In addition, since a truncation of
the Hilbert space is performed, it has to be shown that the finite dimensional
truncated space also incorporates an (approximate) resolution of identity [9]
to make bounding the diamond norm possible.

However, when extending the postselection technique to other symmetry groups,
this condition must also be met. Therefore, it may be instructive and helpful
to rephrase the assumption using conditions in linear algebra. In Appendix
A.1, two necessary, but not sufficient conditions are given.

Thus, if the resolution of identity holds for a given symmetry, it can be
shown that it is sufficient to consider the particular (symmetry-dependent)
state $\tau_{T}$ when computing the diamond norm of an $\mathcal{S}$-invariant
map, instead of performing an optimization over a large number of states. For
the purpose of this section, we assume that the symmetry group $\mathcal{S}$
fulfills the condition; later, when we apply the postselection technique to
the stochastic orthogonal group, we will find that resolution of identity
holds for this case.

Given the following preliminary lemmata, which are generalizations of lemmata
found in [3] and [1], the proof of the bound on the diamond norm becomes
rather concise. The first lemma shows that it is sufficient to consider states
with support on the invariant subspace instead of arbitrary states for the
diamond norm of an invariant map.

######  Lemma 3.2.1.

Let $\Delta$ be a linear map from $\operatorname{End}(\mathcal{H}^{\otimes
n})$ to $\operatorname{End}(\mathcal{H}^{\prime})$ that is invariant under the
symmetry $\mathcal{S}$. For any finite-dimensional space $\mathcal{M}$ and any
(arbitrary) density operator $\sigma_{TM}$, the following holds:

$\big{\|}\
(\Delta\otimes\mathbbm{1})\sigma_{TM}\big{\|}_{\operatorname{tr}}\leq\big{\|}(\Delta\otimes\mathbbm{1})\rho_{TE}\big{\|}_{\operatorname{tr}}$

where $\rho_{TE}$ is a state with support on
$\mathcal{N}=(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(s\otimes\overline{s})}$.

Then, the second lemma establishes a connection between states with support on
the invariant subspace and the de Finetti state in (3.5).

######  Lemma 3.2.2.

Suppose we have a state $\rho_{TE}$ with support on the subspace
$\mathcal{N}=(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(s\otimes\overline{s})}\subseteq\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n}$. For any such state, there exists a linear
completely positive trace-nonincreasing map
$\mathcal{C}:\operatorname{End}(\mathcal{N})\to\mathbbm{C}$ such that

$\rho_{TE}=g_{n,d}(\mathbbm{1}_{TE}\otimes\mathcal{C})(\tau_{TEN})$

with
$\operatorname{tr}_{\mathcal{N}}\tau_{TEN}=\tau_{TE}=\frac{1}{g_{n,d}}\mathbbm{1}_{N}$
(3.5), and $g_{n,d}=\dim(\mathcal{N})$.

A more precise description and the proofs of these lemmata can be found in
Appendix A.2. Using these two lemmata, the main theorem can be proven, which
constitutes a mathematical bound on the diamond norm of an invariant map:

######  Theorem 3.2.1 (Bound on the Diamond Norm).

For a linear map
$\Delta:\operatorname{End}(\mathcal{H}_{T})\to\operatorname{End}(\mathcal{H}^{\prime})$
that is invariant under symmetry group $\mathcal{S}$ for which (3.8) holds,
and a purification $\tau_{TR}$ of $\tau_{T}$ as given in (3.4),

$\big{\|}\Delta\big{\|}_{\diamond}\leq
g_{n,d}\big{\|}(\Delta\otimes\mathbbm{1}_{{R}})\tau_{TR}\big{\|}_{\operatorname{tr}}$
(3.9)

with $g_{n,d}=\dim(\mathcal{N})$ being the dimension of the invariant subspace
$\mathcal{N}\equiv(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(s\otimes\overline{s})}\subseteq\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n}$.

###### Proof of Theorem 3.2.1.

We refer to the definition of the diamond distance (6) of a linear map
$\Delta$. Let $\sigma_{TM}\in\mathfrak{S}(\mathcal{H}_{T}\otimes\mathcal{M})$
be an arbitrary state, associated to a finite space $\mathcal{M}$. Let
$\rho_{TE}$ denote a state with support on the $\mathcal{S}$-invariant
subspace $\mathcal{N}$, $\mathcal{C}$ be a CPTP map, and
$g_{n,d}=\dim(\mathcal{N})$. Using the fact that $\Delta$ is invariant under
$\mathcal{S}$, we find:

$\big{\|}\
(\Delta\otimes\mathbbm{1}_{{M}})\sigma_{TM}\big{\|}\overset{\mathrm{Lemma\
\ref{lemmasym}}}{=}\big{\|}(\Delta\otimes\mathbbm{1}_{E})\rho_{TE}\big{\|}$
$\overset{\mathrm{Lemma\
\ref{lemma2}}}{=}\big{\|}(\Delta\otimes\mathbbm{1}_{E}\otimes\mathbbm{1}_{{N}})(g_{n,d}(\mathbbm{1}_{TE}\otimes\mathcal{C})(\tau_{TEN}))\big{\|}$
$\overset{\mathrm{g_{n,d}\geq
0}}{=}g_{n,d}\big{\|}(\Delta\otimes\mathbbm{1}_{E}\otimes\mathcal{C})(\tau_{TEN}))\big{\|}$
$\leq g_{n,d}\big{\|}(\Delta\otimes\mathbbm{1}_{EN})(\tau_{TEN}))\big{\|}$
$\overset{\mathrm{\mathcal{H}^{\otimes
n}\otimes\mathcal{N}\equiv\mathcal{R}}}{=}g_{n,d}\big{\|}(\Delta\otimes\mathbbm{1}_{{R}})(\tau_{AR}))\big{\|}$

where the second-to-last step is possible because $\mathcal{C}$ is trace-
nonincreasing (by construction). ∎

In summary, as long as the assumption of the existence of a resolution of
identity holds, the bound on the diamond norm for an arbitrary symmetry
$\mathcal{S}$ is directly given by the dimension
$g_{n,d}=\dim(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(s\otimes\overline{s})}=\dim(\mathcal{N})$ of an invariant subspace, and
the symmetry dependent state state $\tau_{T}$.

###  3.3 Generalized Postselection Technique Applied to QKD

As mentioned in Section 3.1, there have been various attempts in quantum
cryptography to use the security of a protocol against collective attacks to
infer security against general, more powerful attacks via quantum de Finetti
theorems by exploiting the permutation symmetry of the protocol [3, 4]. The
postselection technique can be applied to the same problem, and significantly
improved previously known security bounds for permutation-invariant protocols.
Here, it is shown that the generalized postselection theorem (Theorem 3.2.1)
may be used in the same manner, to derive new (and, as we will see in Section
3.4 for discrete/stochastic orthogonal symmetry, tighter) bounds for a
protocol with a different symmetry.

First, in Section 3.3.1, the general steps of a QKD protocol (for two parties
and $N$ parties) will be described, with special focus on the step of privacy
amplification and its relation to the length of the final, secret key shared
by Alice and Bob. Then, in Section 3.3.2, we will show how the symmetry of a
protocol can be used to infer security against general attacks from security
against collective attacks via the postselection theorem.

####  3.3.1 QKD Protocols, Min-entropy and Privacy Amplification

A QKD protocol refers to the task of establishing a common secret key between
two parties, Alice and Bob, while ensuring that a potential adversary Eve has
no knowledge about it. A typical two-party QKD protocol consists of the
following steps:

  * 1)

Key exchange. The two parties exchange qubits and perform measurements to
generate the raw keys.

  * 2)

Key sifting. Only certain cases out of the raw key are selected and kept (e.g.
the cases where some particular measurements were made), the rest is discarded
of. The resulting bit sequence is called sifted keys.

  * 3)

Key distillation.

    * a)

Parameter Estimation. Some random bits are selected and announced publicly via
the classical communication channel to estimate the error rate. If the error
rate exceeds some limit, the protocol will abort.

    * b)

Information Reconciliation. Error correction is performed to transform the
keys into identical bitstrings. An adversary might still have some information
about the resulting key.

    * c)

Privacy Amplification. The two parties use two-universal hashing to get a
shorter, but secret key.

In an $N$ party protocol (for example $N$-six-state protocol [44] and $N$-BB84
[45]), the goal is to establish a secret key known to all $N$ trusted parties,
but unknown to Eve. The $N$ parties consist of one Alice, and $N-1$ Bobs.
Here, genuinly multipartite entangled states are shared between the parties,
and all parties perform local measurements to collect a raw key. Similarly to
the two party protocol, the parties reveal some random bits to estimate the
error rate of their channel. Then, Alice performs an information
reconciliation procedure with each Bob to ensure that they have identical bit
sequences, before each party applies the same randomly chosen hashing function
during the privacy amplification step to ensure their key’s secrecy.

Each of the steps can contribute to the overall error rate of the protocol,
and can separately be bounded, but because of composability [3] the different
bounds can be added together. For the application treated here, the most
notable and important step is privacy amplification, introduced in Chapter 5
of [3]. After obtaining two identical, perfectly correlated bit strings in the
information reconciliation step, the two parties perform a series of
operations which produces two shorter, perfectly correlated and perfectly
secret keys. With this step, it is ensured that an eavesdropper will have no
information about the key shared between the two trusted parties if it was
shortened by some set amount (or more). This amount is determined by the
Leftover Hashing Lemma (originally introduced as Theorem 5.5.1. in [3], and
stated using more up-to-date definitions in [46]).

To arrive at such a bound, the amount of information about the key that is
available to an eavesdropper has to be determined, typically in terms of
conditional entropy. In general, the adversary Eve may have gained access to
correlated side information during previous steps of the QKD protocol. This
information may include access to a quantum state holding memory of
interfering with the quantum communication in previous steps. Then,
conditional entropy measures the amount of uncertainty Eve perceives in the
key, while taking into account the side information available to her.

Different assumptions about Eve’s knowledge can entail different measures of
entropy, which can lead to different bounds on the security of a protocol. The
most commonly used measure of entropy is von Neumann entropy - however, this
would relate to Eve attempting to guess the key from taking a classical
average, which is not optimal. The first attempt to eliminate Eve’s knowledge
by reducing key size used Renyi collision entropy [3], where Eve could use the
quantum state of her subsystem to construct good measurements. Although
carrying out these measurements will provide her with a good guess, it is not
optimal. A natural generalization of conditional Renyi entropy is conditional
min-entropy, first proposed in [3] and expanded upon in [47], where Eve makes
use of the best possible measurements, giving her the best possible
probability of guessing the key. This is optimal for her, and the “worst case
scenario” for us.

It is important to note that this bound on Eve’s information is relevant at a
certain point during the protocol, namely directly before privacy
amplification is carried out. Therefore, while we take $\mathcal{H}_{T}$ to be
the space of the input state to the overall protocol, we use $\mathcal{H}_{X}$
to refer to the space that the state is on after all previous steps and before
the privacy amplification step.

######  Definition 8 (Min-entropy).

Let $\rho_{XE}$ be a state on $\mathcal{H}_{X}\otimes\mathcal{H}_{E}$. The
min-entropy of $\rho_{XE}$ given $E$ is

$H_{min}(X|E)_{\rho}=\sup_{\sigma_{E}\in\mathfrak{S}(\mathcal{H}_{E})}\big{(}\min_{\lambda\in\mathbbm{R}}\\{-\log(\lambda)|{\rho}_{XE}\leq\lambda(\mathbbm{1}_{X}\otimes\sigma_{E})\\}\big{)}.$

Notably, the computation of the min-entropy can be transformed into a SDP,
which can be solved efficiently numerically [48]. Firstly, note that the above
definition can be rewritten to read:

$H_{min}(X|E)_{\rho}=\min_{\sigma_{E}\in\mathfrak{S}(\mathcal{H}_{E})}\\{-\log(\operatorname{tr}\sigma_{E})|\rho_{XE}\leq\mathbbm{1}_{X}\otimes\sigma_{E}\\}$

which can directly be translated to the following primal problem:

######  Optimization problem 3.3.1.

$\begin{split}\text{minimize }&\operatorname{tr}\sigma_{E}\\\ \text{subject to
}&\rho_{XE}\leq\mathbbm{1}_{X}\otimes\sigma_{E}\\\ &\sigma_{E}\geq 0\\\
\end{split}$

and the corresponding dual problem:

######  Optimization problem 3.3.2.

$\begin{split}\text{maximize }&\operatorname{tr}(\Lambda_{XE}\rho_{XE})\\\
\text{subject to }&\operatorname{tr}_{X}\Lambda_{XE}\leq\mathbbm{1}_{E}\\\
&\Lambda_{XE}\geq 0\\\ \end{split}$

Both of the objective functions of these SDP characterizations evaluate to
$2^{-H_{min}(X|E)_{\rho}}$ and can thus be used to compute conditional min-
entropy (which we will make use of later). However, min-entropy is very
sensitive to changes of the system’s state. Since most applications entail
some small error probability, this makes min-entropy a less desireable
measure. Instead, one introduces another generalized entropy measure, smooth
min-entropy. This entropy measure takes into account a ball of states that are
close to $\rho_{ABE}$ in terms of purifying distance, thereby accounting for
some deviations in the system’s state.

######  Definition 9 (Smooth min-entropy).

Let $\rho_{XE}$ be a state on $\mathcal{H}_{X}\otimes\mathcal{H}_{E}$ and let
$\mathcal{B}^{\tilde{\epsilon}}(\rho_{XE})\subseteq\mathfrak{S}(\mathcal{H}_{X}\otimes\mathcal{H}_{E})$
be a ball of states with $d(\rho_{XE},\tilde{\rho}_{XE})\leq\tilde{\epsilon}\
\forall\tilde{\rho}_{XE}\in\mathcal{B}^{\tilde{\epsilon}}(\rho_{XE})$. Then,
smooth min-entropy of $\rho_{XE}$ given $E$ is

$H_{min}^{\tilde{\epsilon}}(X|E)_{\rho}=\sup_{\sigma_{E}\in\mathfrak{S}(\mathcal{H}_{E})}\Big{(}\sup_{\tilde{\rho}_{XE}\in\mathcal{B}^{\tilde{\epsilon}}(\rho_{XE})}\big{(}\min_{\lambda\in\mathbbm{R}}\\{-\log(\lambda)|\tilde{\rho}_{XE}\leq\lambda(\mathbbm{1}_{X}\otimes\sigma_{E})\\}\big{)}\Big{)}.$

Although a similar lemma for privacy amplification can be stated with other
entropy measures, the version using smooth min-entropy is most widely used and
most appropriate for potential applications. In the Leftover Hashing Lemma,
security of a protocol $\mathcal{E}$ (expressed by its distance from a
perfectly secure protocol $\mathcal{F}$) is related to the achievable key
length $l$ and smooth min-entropy.

######  Theorem 3.3.1 (Leftover Hashing Lemma).

For an input state $\rho_{XE}$ under privacy amplification with hashing output
of length $l$, the following holds:

$\big{\|}(\mathcal{PA}\otimes\mathbbm{1})(\rho_{XE})\big{\|}_{\operatorname{tr}}\leq\frac{1}{2}2^{-\frac{1}{2}(H_{min}^{\tilde{\epsilon}}({X}|E)_{\rho}-l)}+2\tilde{\epsilon}.$

The proof can be found in [3, 46].

Importantly, this directly links the key length $l$ for which the protocol
becomes secure to the smooth min-entropy via the following security criterion
(first found in [3]):

$l\leq H_{min}^{\tilde{\epsilon}}(X|E)_{\rho}$ (3.10)

For a protocol to be at least $\epsilon$-secure, the key length must be chosen
to be at least
$l=H_{min}^{\tilde{\epsilon}}(X|E)_{\rho}-2\log\frac{1}{2(\epsilon-2\tilde{\epsilon})}$.
Clearly, there is a tradeoff between key length and security: increasing the
key length leads to a decrease in the error $\tilde{\epsilon}$, which leads an
increasingly secure protocol.

####  3.3.2 From Collective to General Attacks

As found in [1], the postselection technique can be applied to prove that
security of a protocol against collective attacks implies security against
general attacks, with an improved multiplicative factor security bound in
comparison to previous studies. Similarly, the generalized postselection
theorem (Theorem 3.2.1) can be employed to derive such a relation for a
protocol with a more general symmetry $\mathcal{S}$. In one sentence, the
result can be summarized as follows:

If a protocol $\mathcal{E}$ is $\epsilon$-secure against collective attacks,
performing an additional privacy amplification $\mathcal{PA}$ whereby the key
is shortened by $2\log(\dim(\mathcal{N}))=2\log(g_{n,d})$, then the protocol
$\mathcal{E}^{\prime}=\mathcal{PA}\circ\mathcal{E}$ is
$\epsilon^{\prime}$-secure against general attacks with
$\epsilon^{\prime}=g_{n,d}\epsilon$.

Update [13 March 2024]: This statement is not known to be true with
$\epsilon^{\prime}=g_{n,d}\epsilon$, but rather with
$\epsilon^{\prime}=4g_{n,d}\sqrt{2\epsilon}$. For details, we refer to [2].

The remainder of this section will be spent justifying the above statement. No
actual changes need to be made to the original argument in [1] to accommodate
general symmetry groups. However, the original argument is given mostly in
terms of intuition rather than mathematical terms, whereas we will attempt to
describe and justify it in more detail. Thereafter, applying this result to a
protocol with the symmetry of tensor powers of stabilizer states from [10], an
even better overhead for general attacks can be found.

For collective attacks, the adversary Eve would act on each signal
independently and identically - the input of the protocol would be a pure
state $\sigma\in\mathfrak{S}(\mathcal{H}\mathcal{H})$ taken to the $n$-fold
tensor power: $\sigma_{TE}=\sigma^{\otimes
n}\in\mathfrak{S}(\mathcal{H}_{T}\otimes\mathcal{H}_{E})$ with the Hilbert
space $\mathcal{H}_{T}=\mathcal{H}^{\otimes n}$ associated to the trusted pair
of Alice and Bob and the Hilbert space $\mathcal{H}_{E}=\mathcal{H}^{\otimes
n}$ associated to Eve (see Figure 3.1). A protocol $\mathcal{E}$ would
therefore be called $\epsilon$-secure against collective attacks if, for any
such tensor product state $\sigma_{TE}=\sigma^{\otimes n}$,

$\big{\|}\mathcal{E}-\mathcal{F}\big{\|}_{\diamond,coll}=\big{\|}((\mathcal{E}-\mathcal{F})\otimes\mathbbm{1}_{E})\sigma^{\otimes
n}\big{\|}_{\operatorname{tr}}\leq\epsilon.$ (3.11)

Because of the structure of
$\tau_{TE}\in\mathfrak{S}(\mathcal{H}_{T}\otimes\mathcal{H}_{E})$ in (3.5),
which is a mixture of such tensor products of pure states, this implies the
following statement:

$\big{\|}((\mathcal{E}-\mathcal{F})\otimes\mathbbm{1}_{E})\tau_{TE}\big{\|}_{\operatorname{tr}}\leq\sup_{\sigma\in\mathfrak{S}(\mathcal{H}\otimes\mathcal{H})}\big{\|}((\mathcal{E}-\mathcal{F})\otimes\mathbbm{1}_{E})\sigma^{\otimes
n}\big{\|}_{\operatorname{tr}}\leq\epsilon.$ (3.12)

From this, we now want to infer a statement about the security against general
attacks, which is related to bounding another protocol $\mathcal{E}^{\prime}$
with a bigger input state, giving Eve access to an additional (quantum) system
$N$ associated to the Hilbert space
$\mathcal{N}=\mathcal{N}=(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{s\otimes\overline{s}}$. By the previously stated definition of security
in (7), a protocol $\mathcal{E}^{\prime}$ is said to be
$\epsilon^{\prime}$-secure against general attacks if

$\big{\|}\mathcal{E}^{\prime}-\mathcal{F}^{\prime}\big{\|}_{\diamond}=\sup_{\sigma_{TEN}\in\mathfrak{S}(\mathcal{H}_{T}\otimes\mathcal{H}_{E}\otimes\mathcal{N})}\big{\|}((\mathcal{E}^{\prime}-\mathcal{F}^{\prime})\otimes\mathbbm{1}_{EN})\sigma_{TEN}\big{\|}_{\operatorname{tr}}\leq\epsilon^{\prime}$
(3.13)

Here, the postselection theorem (3.2.1) that was established in Section 3.2
can be applied, which implies:

$\big{\|}\mathcal{E}^{\prime}-\mathcal{F}^{\prime}\big{\|}_{\diamond}\leq
g_{n,d}\big{\|}((\mathcal{E}^{\prime}-\mathcal{F}^{\prime})\otimes\mathbbm{1}_{EN})\tau_{TEN}\big{\|}_{\operatorname{tr}}\leq\epsilon^{\prime}$
(3.14)

This relates the notion of collective $\epsilon$-security with the state
$\tau_{TE}$, while the notion of general $\epsilon$-security is connected to
the state $\tau_{TEN}$, which is a purification of $\tau_{TE}$. Now, we want
to exploit this relation, in combination with the Leftover Hashing Lemma [3,
46], to relate the protocol $\mathcal{E}^{\prime}$ to $\mathcal{E}$ via an
additional privacy amplification $\mathcal{PA}$:

$\mathcal{E}^{\prime}=\mathcal{PA}\circ\mathcal{E}$ (3.15)

Let $\omega_{XEN}=\mathcal{E}(\tau_{TEN})$ be the state that the input
$\tau_{TEN}$ was transformed into in the previous steps of the protocol. The
system $X$ denotes the system that the trusted system $T$ of the input state
$\tau_{TEN}$ was transformed to during the protocol so far. Of course, the
same additional privacy amplification step is performed in
$\mathcal{F}^{\prime}$. It must be noted that the dimension of the spaces did
not change; in particular, $X$ now contains Alice and Bob’s perfectly
correlated but not yet perfectly secret keys. According to the Privacy
Amplification Theorem (3.3.1), the following holds for the additional privacy
amplification step:

$\big{\|}((\mathcal{E^{\prime}}-\mathcal{F^{\prime}})\otimes\mathbbm{1}_{EN})\tau_{TEN}\big{\|}_{\operatorname{tr}}=\big{\|}(\mathcal{PA}\otimes\mathbbm{1}_{EN})\omega_{XEN}\big{\|}_{\operatorname{tr}}\leq\frac{1}{2}2^{-\frac{1}{2}(H_{min}^{\tilde{\epsilon}}(X|EN)_{\omega}-l^{\prime})}+2\tilde{\epsilon}$
(3.16)

where $l^{\prime}$ is the length of the key and
$H_{min}^{\tilde{\epsilon}}(X|EN)_{\omega}$ is the smooth min-entropy of the
state $\omega_{XEN}$ with side information $EN$.

To establish a relation between the key length $l$ of $\mathcal{E}$ and
$l^{\prime}$ of $\mathcal{E}^{\prime}$, we therefore need to find the relation
between their entropies. Note that these entropies are related to a state on
different spaces, because protocol $\mathcal{E}^{\prime}$ acts on a
purification of the space of $\mathcal{E}$, with an additional system ${N}$.
In fact, the act of shortening the key can be interpreted as a compensation of
the additional information available to the adversary in the general scenario
in form of the space $\mathcal{N}$.

The process of deriving how much the key need to be shortened has three steps:
firstly, a relation between the quantum state $\omega_{XEN}$ and its partial
trace $\omega_{XE}=\operatorname{tr}_{N}\omega_{XEN}$ is established (Lemma
3.3.1). Secondly, it is investigated how min-entropy changes under this
purification (Lemma 3.3.2), before ‘’smoothing” the relation (using (3.23)) to
insert smooth min-entropy in the Leftover Hashing Lemma in (3.25).

One key technique that this process relies on is twirling, which is the
operation of taking the average of a channel under unitary operations [49,
50]. For a given set $\\{U_{k}\\}_{k=1,...,K}$ of unitary operators on the
Hilbert space $\mathcal{H}$, applying the associated twirling channel
$\mathcal{T}$ to a quantum state $\rho\in\mathfrak{S}(\mathcal{H})$ yields

$\mathcal{T}(\rho)=\frac{1}{\dim(\mathcal{H})^{2}}\sum_{k=1}^{K}U_{k}\rho
U_{k}^{\dagger}.$

This kind of map can be defined for different sets of unitary operators, e.g.
Clifford group or Pauli group. This technique is useful in the context of
various quantum information processing tasks, such as entanglement
purification [51], randomized benchmarking [52], and the simulation of noise
in quantum error correction codes [53].

If the set of unitaries is chosen to be the set of Heisenberg-Weyl operators
$\\{W_{k}\\}_{k=1,...,\dim(\mathcal{H})^{2}}=\\{X_{i}Z_{j}\\}_{i,j=0,...,\dim(\mathcal{H})-1}$
(with $X$ and $Z$ being Pauli operators, and the index indicating which space
they are applied to), it can be shown that applying them with uniform
probability to any qudit density operator yields the maximally mixed state
[49]:

$\mathcal{T}_{HW}(\rho)=\frac{1}{\dim(\mathcal{H})^{2}}\sum_{k=1}^{\dim(\mathcal{H})^{2}}W_{k}\rho
W_{k}^{\dagger}=\frac{\mathbbm{1}}{\dim(\mathcal{H})}$ (3.17)

For the qubit case, i.e. for Pauli operators, the above relation can easily be
checked by writing the density operator as a Bloch vector and using
commutation relations [49].

Now, we introduce the following preliminary lemma about the relation of
$\omega_{XEN}$ and its partial trace
$\omega_{XE}=\operatorname{tr}_{N}\omega_{XEN}$, which uses twirling in its
proof.

######  Lemma 3.3.1.

For a quantum state
$\omega_{XEN}\in\mathfrak{S}(\mathcal{H}_{X}\otimes\mathcal{H}_{E}\otimes\mathcal{N})$,
the following bound holds:

$\omega_{XEN}\leq\dim(\mathcal{N})(\omega_{XE}\otimes\mathbbm{1}_{N})$

where $\omega_{XE}=\operatorname{tr}_{N}\omega_{XEN}$.

###### Proof of Lemma 3.3.1.

Inserting the state of interest $\omega_{XEN}$ and applying the twirling
channel $T_{HW}$ associated to such Heisenberg-Weyl operators (3.17)
partially, i.e. only to the subsystem $N$, yields

$\begin{split}\mathcal{T}_{HW}^{N}(\omega_{XEN})&=\frac{1}{\dim(\mathcal{N})^{2}}\sum_{k}(\frac{\mathbbm{1}}{\dim(\mathcal{H}_{XE})}\otimes
W_{k})\omega_{XEN}(\frac{\mathbbm{1}_{N}}{\dim(\mathcal{H}_{XE})}\otimes
W_{k})^{\dagger}\\\
&=\omega_{XE}\otimes\frac{\mathbbm{1}}{\dim(\mathcal{N})}.\end{split}$ (3.18)

Some of the Heisenberg Weyl operators are tensor powers of the identity
matrix, and the sum can be separated:

$\mathcal{T}_{HW}^{N}(\omega_{XEN})=\frac{1}{\dim(\mathcal{N})^{2}}(\omega_{XEN}+\delta_{XEN})$
(3.19)

with some positive $\delta_{XEN}\geq 0$.

Combining (3.19) and (3.18) yields

$\begin{split}\omega_{XEN}&=\dim(\mathcal{N})^{2}\mathcal{C}_{HW}^{N}(\omega_{XEN})-\delta_{XEN}\\\
&=\dim(\mathcal{N})^{2}\omega_{XE}\otimes\frac{\mathbbm{1}_{N}}{\dim(\mathcal{N})}-\delta_{XEN}\\\
&\leq\dim(\mathcal{N})(\omega_{XE}\otimes\mathbbm{1}_{N}).\end{split}$

∎

######  Remark.

Note that this bound is tight for the maximally entangled state.

Knowing how these pre-privacy amplification states appearing in the protocol
for a collective and a general attack are related to one another directly
leads to a relation between the states’ min-entropies:

######  Lemma 3.3.2 (Min-entropy and purification).

The following relation holds for the min-entropy
$H_{min}(X|E)_{\operatorname{tr}_{N}\omega}$ of a state
$\omega_{XE}=\operatorname{tr}_{N}\omega_{XEN}$ and the min-entropy
$H_{min}(X|EN)_{\omega}$ of the state’s Stinespring dilation
$\omega_{XEN}\in\mathfrak{S}(\mathcal{H}_{X}\otimes\mathcal{H}_{E}\otimes\mathcal{N})$:

$H_{min}(X|EN)_{\omega}\geq
H_{min}(X|E)_{\operatorname{tr}_{N}\omega}-2\log\dim(\mathcal{N}).$

###### Proof of Lemma 3.3.2.

Recall the definition of the min-entropy $H_{min}(X|EN)_{\omega}$ in terms of
a semi-definite optimization problem (3.3.1). Suppose we have found a feasible
solution with a certain $\Lambda_{XEN}$ \- then the min-entropy is defined by

$2^{H_{min}(X|EN)_{\omega}}=\operatorname{tr}\Lambda_{XEN}\omega_{XEN}.$
(3.20)

Then, Lemma 3.3.1 ensures the following bound:

$\operatorname{tr}\Lambda_{XEN}\omega_{XEN}\leq\dim{(\mathcal{N})}\operatorname{tr}\Lambda_{XEN}\omega_{XE}\otimes\mathbbm{1}=(\dim\mathcal{N})^{2}\operatorname{tr}\Gamma_{XE}\omega_{XE}$
(3.21)

Here, a renaming of
$\Gamma_{XE}=\frac{1}{\dim(\mathcal{N})}\operatorname{tr}_{N}\Lambda_{XEN}$
has taken place in the last step. Now it remains to be shown that
$\Gamma_{XE}$ is in itself a solution (if not the best solution) to the semi-
definite optimization problem defining
$H_{min}(X|E)_{\operatorname{tr}_{N}\omega}$.

To show this, we check the feasibility criteria. The second criterion,
$\Gamma_{XE}\geq 0$, can be directly inferred from the feasibility of
$\Lambda_{XEN}$, which entails $\Lambda_{XEN}\geq 0$. Similarly, the
feasibility of $\Lambda_{XEN}$ implies
$\operatorname{tr}_{X}\Lambda_{XEN}=\Lambda_{EN}\leq\mathbbm{1}_{EN}$, which
can be used to show that $\Gamma_{XE}$ fulfills the first criterion:

$\Gamma_{E}=\operatorname{tr}_{X}\Gamma_{XE}=\dim(\mathcal{N})\operatorname{tr}_{X}\operatorname{tr}_{N}\Lambda_{XEN}=\operatorname{tr}_{N}\Lambda_{EN}\leq\operatorname{tr}_{N}\mathbbm{1}_{EN}\leq\mathbbm{1}_{E}$

In conclusion, $\Gamma_{XE}$ fullfills the criteria, and is thus a feasible
solution for the SDP defining $H_{min}(X|E)_{\operatorname{tr}_{N}\omega}$.
Since the SDP still entails a maximization, this implies

$\operatorname{tr}\Gamma_{XE}\omega_{XE}\leq
2^{-H_{min}(X|E)_{\operatorname{tr}_{N}\omega}}$ (3.22)

where equality would hold if $\Gamma_{XE}$ was optimal. Inserting (3.20) and
(3.22) into the bound (3.21), we obtain:

$2^{-H_{min}(X|EN)_{\omega}}\leq\dim(\mathcal{N})^{2}2^{-H_{min}(X|E)_{\operatorname{tr}_{N}\omega}}$

which directly implies

$H_{min}(X|EN)_{\omega}\geq
H_{min}(X|E)_{\operatorname{tr}_{N}\omega}-2\log\dim(\mathcal{N}).$

∎

Update [13 March 2024]: The corresponding statement is not known to hold for
smooth entropy wrt to trace distance with the same smoothing parameter
$\tilde{\epsilon}$ on both smoothed entropies.

With this established, the next step is to extend this statement to smooth
min-entropy. Smooth min-entropy is related to min-entropy via the following
smoothing relation:

$\sup_{\tilde{\omega}_{XEN}\in
B^{\tilde{\epsilon}}(\omega_{XEN})}H_{min}(X|EN)_{\tilde{\omega}}=H_{min}^{\tilde{\epsilon}}(X|EN)_{{\omega}}.$
(3.23)

Since the smoothing parameters $\epsilon$ and $\tilde{\epsilon}$ are defined
via the trace distance, which is trace preserving, $\tilde{\omega}_{XEN}\in
B^{\tilde{\epsilon}}(\omega_{XEN})$ directly implies
$\operatorname{tr}_{N}\tilde{\omega}_{XEN}\in
B^{\tilde{\epsilon}}(\operatorname{tr}_{N}\omega_{XEN})$, which we can use to
write:

$\sup_{\tilde{\operatorname{tr}_{N}\omega}_{XEN}\in
B^{\tilde{\epsilon}}(\operatorname{tr}_{N}(\omega_{XEN}))}H_{min}(X|E)_{\operatorname{tr}_{N}\tilde{\omega}}=H_{min}^{\tilde{\epsilon}}(X|E)_{{\operatorname{tr}_{N}\omega}}$

Update [13 March 2024]: For a given state
$\operatorname{tr}_{N}\tilde{\omega}_{XEN}\in
B^{\tilde{\epsilon}}(\operatorname{tr}_{N}\omega_{XEN})$, does there always
exist a state $\tilde{\omega}_{XEN}\in B^{\tilde{\epsilon}}(\omega_{XEN})$?
Using $\tilde{\epsilon}$-balls with respect to purified distance like in [46],
this is indeed true. For the trace distance, the argument can be fixed at the
cost of a worse smoothing parameter (going via purified distance, in fact).
For details, we refer to [2].

Assuming that we have found a state $\tilde{\omega}_{XEN}$ such that
$H_{min}(X|E)_{\operatorname{tr}_{N}\tilde{\omega}}=H_{min}^{\tilde{\epsilon}}(X|E)_{{\operatorname{tr}_{N}\omega}}$,
this immediately implies

$\begin{split}H_{min}^{\tilde{\epsilon}}(X|E)_{{\operatorname{tr}_{N}\omega}}-2\log(\dim(\mathcal{N}))&=H_{min}(X|E)_{\operatorname{tr}_{N}\tilde{\omega}}-2\log(\dim(\mathcal{N}))\\\
&\leq H_{min}(X|EN)_{\tilde{\omega}}\leq
H_{min}^{\tilde{\epsilon}}(X|EN)_{\omega}\end{split}$ (3.24)

where the last inequality follows from the definition of smooth min-entropy as
a supremum. This directly implies that a smoothed version of Lemma 3.3.2 is
true, and thus tells us how smooth min-entropy transforms under purification.

Now, the relation between the two smooth min-entropies can be used to connect
the security against general attacks of the protocol $\mathcal{E}^{\prime}$
with the security parameter $\epsilon$ of the protocol $\mathcal{E}$ against
collective attacks because of privacy amplification, by inserting the relation
between the smooth min-entropies (3.24) into the Leftover Hashing Lemma
associated to the additional privacy amplification step (3.16):

$\begin{split}\big{\|}\big{(}(\mathcal{E}-\mathcal{F})\otimes\mathbbm{1}_{EN}\big{)}\tau_{TEN}\big{\|}_{\operatorname{tr}}&\leq\frac{1}{2}2^{-\frac{1}{2}(H_{min}^{\tilde{\epsilon}}(X|EN)_{\omega}-l^{\prime})}+2\tilde{\epsilon}\\\
&\leq\frac{1}{2}2^{-\frac{1}{2}(H_{min}^{\tilde{\epsilon}}(X|E)_{\operatorname{tr}_{N}\omega}-2\log(\dim(\mathcal{N}))-l^{\prime})}+2\tilde{\epsilon}\\\
&\leq\frac{1}{2}2^{-\frac{1}{2}(l-2\log\frac{1}{2(\epsilon-2\tilde{\epsilon})}-2\log\dim(\mathcal{N})-l^{\prime})}+2\tilde{\epsilon}:=\epsilon\end{split}$
(3.25)

Thus it is found that Eve gaining more knowledge from a bigger system can be
counter-acted by reducing the length of the key by exactly the system’s
dimension. For the system
$\mathcal{N}=(\mathcal{H}_{T}\otimes\mathcal{H}_{E})^{s\otimes\overline{s}}=(\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n})^{s\otimes\overline{s}}$, this dimension is
$g_{n,d}$, as appears in Section 3.2. This implies the following relation
between the key lengths:

$l^{\prime}\geq l-2\log\dim(\mathcal{N})=l-2\log(g_{n,d})$ (3.26)

Now, equation (3.26) can be related back to a statement about the general
security of $\mathcal{E}^{\prime}$ in the following way: If
$\mathcal{E}^{\prime}$ is obtained from $\mathcal{E}$ by shortening the output
of the hashing function by $2\log(g_{n,d})$, i.e. shortening the key by this
amount, then

$\big{\|}\mathcal{E}^{\prime}-\mathcal{F}^{\prime}\big{\|}_{\diamond}\leq
g_{n,d}\big{\|}((\mathcal{E}^{\prime}-F^{\prime})\otimes\mathbbm{1}_{EN})\tau_{TEN}\big{\|}_{\operatorname{tr}}\leq{g_{n,d}}\epsilon\coloneqq\epsilon^{\prime}.$
(3.27)

Therefore, if a protocol $\mathcal{E}$ is $\epsilon$-secure against collective
attacks, and we obtain $\mathcal{E}^{\prime}$ from $\mathcal{E}$ by shortening
the hashing function’s output by $2\log(g_{n,d})$, then we can infer that
$\mathcal{E}^{\prime}$ is $\epsilon^{\prime}$-secure against general attacks
with $\epsilon^{\prime}=g_{n,d}\epsilon$.

In summary (similarly to the mathematical bound on the diamond norm), the
comparison between security against general and collective attacks of a
protocol with invariance under an arbitrary symmetry $\mathcal{S}$ is directly
related to the dimension $g_{n,d}=\dim(\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n})^{(s\otimes\overline{s})}=\dim(\mathcal{N})$
of an invariant subspace. For this reason, the next section is occupied with
computing this number for the symmetry group of interest in this project, the
stochastic orthogonal group.

###  3.4 Orbit Counting for Discrete Orthogonal Matrices

As established in Section 3.2, the bound on the diamond norm is related to the
coefficients $g_{n,d}=\dim(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(s\otimes\overline{s})}=\dim(\mathcal{N})$, which are equal to the
dimension of an invariant subspace associated to the general symmetry group
$\mathcal{S}$. Subsequently, as described in Section 3.3, these coefficients
directly determine the difference in security parameter between collective and
general attacks. In this section, we will introduce Witt’s Lemma (described in
Section 3.4.1) and use it to compute this dimension by counting orbits for the
symmetry group of discrete orthogonal matrices, as introduced in [10] and
Definition 5. Firstly, we will describe how the dimension was computed in the
context of two party QKD protocols in Section 3.4.2, before showing how this
can be generalized to the $N$ party case in Section 3.4.3. Note that this does
not directly have implications relevant to QKD - instead, the dimension for
discrete orthogonal group is a stepping stone for getting the dimension for
stochastic orthogonal group introduced in Definition 4, which is the group
that is relevant to the postselection theorem and subsequent QKD results, as
will be explained in more detail in Section 3.5.

####  3.4.1 Orbit Counting Using Witt’s Lemma

In a system with a given symmetry, some elements of the phase space may become
equivalent under transformations with that symmetry (called: being in the same
orbit). Many problems can then be simplified because the behaviour of elements
in the same orbit can be inferred from one another. As established in previous
sections, we are highly interested in the dimension of a certain invariant
subspace, $\mathcal{N}$. Computing the dimension of the space of elements that
are invariant under a given symmetry group is achieved by counting the
dimension of the space that the symmetry group projects to. In case of the
stochastic orthogonal group and discrete orthgonal group (and also permutation
group), the computational basis is preserved under their action. In such
cases, the invariant subspace is spanned by mixtures of states within the same
orbit, and each distinct orbit constitutes one basis vector of the invariant
subspace. Therefore, the dimension of the invariant subspace is given by the
number of distinct orbits of the group, and computing the dimension is
achieved by counting the orbits of the symmetry group.

######  Definition 10 (Orbit of a group).

Let $G$ be a group acting on a set $X$. For each element $x\in X$ of the set,
let $\operatorname{orb}G(x)=\\{gx|g\in G\\}$. The set $\operatorname{orb}G(x)$
is a subset of $X$ that is called the orbit of $x$ under $G$.

The orbit of an element $x\in X$ is given by all the elements $y\in X$ that
are connected to $x$ via the group elements $g\in G$. Therefore, objects in a
given orbit can be considered isomorphic in the sense that they will map to
the same object under application of some $g\in G$. The dimension of the space
that the $g\in G$ map to is thus equal to the number of distinct orbits of
$G$.

One important tool for orbit counting is Witt’s Lemma [54] (sometimes called
Witt’s Theorem, stated here [55, 56] for symplectic groups). This lemma
relates two sets of vectors, $\\{v_{i}\\}$ and $\\{w_{i}\\}$, with the same
linear product relations to a mapping $M$ (with one particular property)
between these two vectors.

######  Theorem 3.4.1 (Witt’s Lemma).

Let $V$ be a vector space with a non-degenerate bilinear product
$\beta(\cdot,\cdot)$. Let $\\{v_{i}\\}$ and $\\{w_{i}\\}$ be two sets of $k$
linearly independent elements (vectors) of $V$ satisfying

$\beta(v_{i},v_{j})=\beta(w_{i},w_{j})\ \forall i,j=1,...,k.$

Then, there exists a map $M:V\mapsto V$ satisfying

$\beta(Mv,Mw)=\beta(v,w)\ \forall v,w\in V$

for which

$Mv_{i}=w_{i}\ \forall i=1,...,k.$

The converse of this statement is also true and comparatively easy to see: If
such a mapping exists (that conserves linear products and maps $v_{i}$ to
$w_{i}$ $\forall i$), then the two vector sets $\\{v_{i}\\}$ and $\\{w_{i}\\}$
obey the same linear product relations.

This theorem directly relates to orbits, since by definition, phase space
elements that can be mapped to one another are in the same orbit. Therefore,
to compute the number of distinguishable orbits in a discrete space (which we
aim to do in Sections 3.4.2 and 3.4.3), one needs to count how many distinct
values there are for the linear product $\beta(\cdot,\cdot)$ associated to the
space.

It can be noted that orbit counting can easily be employed to reproduce the
known dimension for the permutation group found in [1]. To compute the
dimension of the space that is invariant unter permutations, i.e. the orbits
of the permutation group, the number of distinct basis elements has to be
counted. Firstly, consider a single permutation matrix applied to a Hilbert
space vector in the computational basis $\ket{x_{1},x_{2},...x_{n}}$, where
each $x_{i}$ is some discrete number between $0$ and $d-1$. Applying a
permutation will switch the numbers $x_{i}$ with each other while conserving
the number of times each number between $0$ and $d-1$ appears. For example,
applying a permutation to the vector $\ket{1,0,...,0}$ will change the
position of the $1$, but the number “0” will always appear $n-1$ times, and
the number “1” will always appear one single time. In total, the basis
elements that are distinct with respect to permutations are thus characterized
by occupational numbers $n_{j}$ for $j=1,...,d$ with $\sum_{j}n_{j}=n$. This
is a simple and well known combinatorics problem (“Stars and Bars” [57], boson
statistics): How many distinct ways are there to put $n$ stars into $d$ boxes?
The solution is exactly $\binom{n+d-1}{n}=(n+1)^{d-1}$, which would be the
dimension of the Hilbert space $(\mathcal{H}^{\otimes n})^{\pi}$. However, the
postselection theorem is related to the space $(\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n})^{\pi\otimes\pi}$. In this case, there is the
same permutation acting on a vector $\ket{x_{1},x_{2},...x_{n}}$ in the first
Hilbert space and a vector $\ket{y_{1},y_{2},...y_{n}}$ in the second Hilbert
space, which can be understood as a permutation of the rows of the following
matrix:

$\left(\begin{array}[]{r r}x_{1}&y_{1}\\\ \vdots&\vdots\\\ x_{n}&y_{n}\\\
\end{array}\right).$

Since the same permutation acts on each column, elements $x_{i}$ and $y_{i}$
always stay together and can thus be considered as a pair. Applying the same
logic as before, the occupation numbers of such pairs $(x_{i},y_{i})$ (of
which there exist $d^{2}$ possibilities) now define discrete orbits, so there
exist $\binom{n+d^{2}-1}{n}=(n+1)^{d^{2}-1}$ orbits, which is exactly the
number in equation (3.2), found in [1].

Using the same argument, this problem can also easily be extended to the $N$
party case: then, the number of orbits is
$\binom{n+d^{2N}-1}{n}=(n+1)^{d^{2N}-1}$, as it appears in [45].

For the symmetry group of discrete orthogonal matrices, Witt’s Lemma will be
employed to recast the task of orbit counting as a combinatorics problem.

####  3.4.2 Orbits of Discrete Orthogonal Group for Two Parties

To apply the postselection theorem using the new symmetry group discovered in
[10], the dimension of the subspace that is invariant under its action has to
be computed. This dimension for the stochastic orthogonal group
$\mathcal{O}_{n}$ can be computed via a relaxation to the discrete orthogonal
group $\tilde{\mathcal{O}}_{n}$, which is described by discrete orthogonal
matrices $\tilde{O}\in\tilde{\mathcal{O}}_{n}$, which are introduced in
Definition 5 (see Section 2.1.2). Therefore, our aim is to compute the
dimension of the space $(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(\tilde{O}\otimes\tilde{O})}$ (since $\tilde{O}$ is real, note that
$\overline{\tilde{O}}=\tilde{O}$) which is invariant under the action
$\tilde{O}\otimes\tilde{O}$. As established in Section 3.4.1, the dimension of
that space is equal to the number of distinct orbits of that group.

As a precursor, we will consider the group of discrete orthogonal matrices
acting on $\mathcal{H}^{\otimes n}$, thus calculating the dimension ${D_{1}}$
of the invariant subspace $(\mathcal{H}^{\otimes
n})^{\tilde{O}}\subseteq\mathcal{H}^{\otimes n}$. Note that this space is only
a potentially helpful construct with no direct relation to the relevant
subspace. However, on the one side, this will be helpful to describe the
counting strategy - and on the other side, this will become important when
treating the $N$ party generalization, where a recursion relation will be
proposed.

The representation of the discrete orthogonal transformations act on
computational basis elements of the Hilbert space in the following way:

$R(\tilde{O})\ket{x}=\ket{\tilde{O}x}$

where $\ket{x}$ is a vector on the Hilbert space $\mathcal{H}^{\otimes n}$,
and the symbols $x$ live on the discrete Hilbert space $\mathbb{F}_{d}^{n}$,
on which the $n\times n$ matrix $\tilde{O}$ acts. Thereby, $R(\tilde{O})$ acts
by preserving a finite set of basis elements, which justifies that the number
of orbits is equal to the dimension of the invariant subspace.

According to Witt’s Lemma (3.4.1) [54], orbits of the symmetry group
$\tilde{\mathcal{O}}_{n}$ are defined in the following way:

$\ket{x^{\prime}}\in\operatorname{orb}\tilde{\mathcal{O}}(\ket{x})\Leftrightarrow\beta({x},{x})=\beta({x}^{\prime},{x}^{\prime})\mod
d$ (3.28)

with a linear product $\beta(\cdot,\cdot)$ associated to the discrete vector
space $\mathbb{F}_{d}^{\otimes n}$, for $\ket{x},\ket{x^{\prime}}$ be vectors
on $\mathcal{H}^{\otimes n}$ and $x,x^{\prime}$ on $\mathbb{F}_{d}^{n}$.

The number of distinct orbits is thus given by the number of distinct numbers
$\beta(x,x)\mod d$ that define each orbit. Thereby, the task of counting
orbits becomes a combinatorics problem where two distinct cases have to be
considered. On the one hand, let $x\neq 0$. Because of the modulo on the
condition, there are $d$ distinct possibilities to choose from:
$\beta(x,x)=0,1,...,d-1$, and alll of these possibilities are realized if $n$
is large enough. On the other hand, let ${x}=0$; then, it is immediate that
$\beta(x,x)=0$ by linearity. This case cannot be transformed into the case
where $x\neq 0$, $\beta(x,x)=0$ and must thus be considered a separate orbit.

In summary, there are $d$ ways to choose distinct $\beta(x,x)$ for $x\neq 0$,
and only one way to choose $\beta(x,x)$ for $x=0$. In conclusion, we obtain
the following number of orbits, and thus dimension of $(\mathcal{H}^{\otimes
n})^{\tilde{O}}$:

${D_{1}}=d+1$ (3.29)

Now, this can be expanded to the case of interest, where the dimension of
interest is $D_{2}$, the dimension of the invariant subspace
$(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(\tilde{O}\otimes\tilde{O})}\subseteq\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n}$. In this case, the space that
$R(\tilde{O})\otimes R(\tilde{O})$ maps to has to be considered:

$R(\tilde{O})\otimes
R(\tilde{O})\ket{x_{1}}\otimes\ket{x_{2}}=\ket{\tilde{O}x_{1}}\otimes\ket{\tilde{O}x_{2}}$

Using Witt’s Lemma (3.4.1), orbits of the group acting by
$(\tilde{O}\otimes\tilde{O})\ket{x_{1},x_{2}}$ can then be defined by the
following set of equations for $x_{1}$ and $x_{2}$ being linearly independent:

$\ket{x_{1}^{\prime},x_{2}^{\prime}}\in\operatorname{orb}(\tilde{\mathcal{O}}\otimes\tilde{\mathcal{O}})(\ket{x_{1},x_{2}})\Leftrightarrow\begin{cases}\beta(x_{1},x_{1})=\beta(x_{1}^{\prime},x_{1}^{\prime})\mod
d\\\ \beta(x_{2},x_{2})=\beta(x_{2}^{\prime},x_{2}^{\prime})\mod d\\\
\beta(x_{1},x_{2})=\beta(x_{1}^{\prime},x_{2}^{\prime})\mod d\end{cases}$

where $\ket{x_{i}}$ are a vector on the Hilbert space $\mathcal{H}^{\otimes
n}$, and the symbol $x_{i}$ are a discrete vector on $\mathbb{F}_{d}^{n}$
$\forall i$.

Now, combinatorics can be employed to upper bound how many different discrete
values can be chosen for $\beta(x_{1},x_{1}),\ \beta(x_{2},x_{2})$ and
$\beta(x_{1},x_{2})$.

Figure 3.2: Tree diagram to illustrate the different cases and how the choices
influence each other. In red, the number of paths between knots have been
indicated along each branch of the tree diagram. (1 path connected after d
paths is short-hand notation for d paths each having a knot, and 1 path
pertruding from this knot.) At the bottom, the total number of possible
choices for each of the cases is indicated in bold and red. These numbers have
to be added up to sum to the total number of possibilites, which is equal to
the dimension $D_{2}$ we are looking for.

Added difficulty stems from the fact that $\beta(x_{1},x_{2})$ can depend on
the previous choices, and that the two vectors $x_{1}$ and $x_{2}$ could be
linearly dependent on one another. The latter could in principle prohibit the
application of Witt’s Lemma. However, we are actually not using Witt’s Lemma
directly, but employing it to derive an upper bound which can be improved upon
by considering the different cases, and treating the possibility of linearly
dependent vectors separately. In fact, the vectors must be linearly dependent
when the number of subsystems $n$ (corresponding to the entries of the
computational basis vector which are transformed via discrete orthgonal
matrices in $\tilde{O}x_{i}$) is small compared to the number of vectors
(here: 2, namely $x_{1}$ and $x_{2}$). Therefore, for $n<2$, there will always
be linear dependency between the $x_{i}$ for any computational basis vector.
For $n\geq 2$, i.e. $n$ large enough, there may be linearly dependent and
linearly independent vectors, and both cases must be taken into account. In an
$N$ party scenario, there are $N$ different vectors $x_{i}$ with $i=1,...,N$
\- then, $n<N$ will lead to definitive linear dependency, and both cases are
possible for $n\geq N$. Since $n$ is usually assumed to be large (since larger
$n$ means larger key length, or smaller error in the de Finetti bound), it can
usually be assumed that both cases occur. But even for small $n$, linear
dependency would fix some $\beta(x_{i},x_{j})$, and the assumption that these
linear products can be chosen freely can therefore lead to an overcounting,
making our result an upper bound, which is sufficient for our purposes.

In total, linear dependency between $x$-vectors and the differentiation
between $x_{i}=0$ and $x_{i}\neq 0$ for $i=1,2$ all have to be taken into
account. We will now list all the different cases and how they influence the
available choices for the linear products $\beta(x_{1},x_{1}),\
\beta(x_{2},x_{2})$ and $\beta(x_{1},x_{2})$. All of the cases and the number
of choices for each are sketched in Figure 3.2 in a tree diagram.

The simplest case that must be differentiated is the case where both vectors
are $x_{1}=x_{2}=0$. This fully determines
$\beta(x_{1},x_{1})=\beta(x_{2},x_{2})=\beta(x_{1},x_{2})=0$ by linearity, and
thus only has one path associated to it.

If the first vector $x_{1}=0$, and $x_{2}\neq 0$, $\beta(x_{2},x_{2})$ can
still be chosen out of the $d$ members of the set $\\{0,1,...d-1\\}$ \- which
constitutes to $d$ choices, while $\beta(x_{1},x_{1})=\beta(x_{1},x_{2})=0$ by
linearity (1 choice each).

If $x_{1}\neq 0$, there are $d$ possibilities to fix
$\beta(x_{1},x_{1})=0,1,...,d-1$. Then, there are two possibilites for the
vector $x_{2}$: it can either be linearly independent of $x_{1}$, or not. If
it is linearly independent, i.e. $x_{1}\neq\lambda x_{2}$ for any
$\lambda\in\\{0,1,...,d-1\\}$, $\beta(x_{2},x_{2})$ can be chosen from the set
$\\{0,1,...d-1\\}$. Furthermore, there are $d$ possible choices for
$\beta(x_{1},x_{2})$. Overall, this contributes $d^{3}$ possible paths to the
number of orbits. For small $n$, these choices might be restricted, but as
this would only lead to a smalller number of orbits, it can be assumed that it
can be chosen freely, leading to an upper bound. However, if $x_{2}$ is
linearly dependent on $x_{1}$, i.e. $x_{2}=\lambda x_{1}$, then
$\beta(x_{2},x_{2})=\lambda^{2}\beta(x_{1},x_{1})\mod d$ and
$\beta(x_{1},x_{2})=\lambda\beta(x_{1},x_{1})\mod d$ are fixed by the choice
of $\beta(x_{1},x_{1})$, contributing one path for each possibility of
$\lambda\in\\{0,1,...,d-1\\}$. There are thus $d$ distinct possibilities of
choosing $\beta(x_{1},x_{1})$ and $d$ distinct choices of $\lambda$ \-
constituting to an overall addition of $d^{2}$ possible paths.

In total, summing up all the possible choices for each case results in

$D_{2}=d^{3}+d^{2}+d+1$ (3.30)

as an upper bound to the number of orbits of $\tilde{O}\otimes\tilde{O}$,
where $\tilde{O}\in\tilde{\mathcal{O}}_{n}$, and thus the dimension of
$(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{(\tilde{O}\otimes\tilde{O})}$.

####  3.4.3 Orbits of Discrete Orthogonal Group for N Parties

From the computation of the two party case 3.30, it can already be suspected
that there may be a recursion relation associated to the number of tensor
products of $\tilde{O}$: if the first choice $x_{1}=0$, for which there is
only one choice, the situation is mapped back to the situation where there is
only one vector (3.29), which corresponds to having $D_{1}=d+1$ choices for
$\beta(x_{2},x_{2})$. Similarly, when $x_{1}$ and $x_{2}$ are non-zero and
linearly independent, it is clear that there will be an additional factor of
$d$ for the choice of each new party ($\beta(x_{1},x_{1})$) and for each cross
term ($\beta(x_{1},x_{2})$). For linear dependency, each possibility of having
two vectors linearly dependent contributes a factor of $d$, while fixing cross
terms. Here, this argument will be generalized to find a recursion relation
for the dimension $D_{K}$ that is associated to the subspace that is invariant
under $\tilde{O}^{\otimes K}$.

We thus assume that the number of orbits of $K-1$ applications of $\tilde{O}$,
$D_{K-1}$, is known, and an additional $K$-th $\tilde{O}$ is brought in.

For a more instructive argument, imagine adding the additional $x_{K}$ at the
top of the tree diagram, choosing it first (since the order of choosing should
not matter). If $x_{K}=0$, this branch will reproduce the tree diagram for the
$K-1$ case. If $x_{K}\neq 0$, there are $d$ choices for $\beta(x_{K},x_{K})$.
Then, all subsequent choices for $x_{i}$ will either linearly depend on
$x_{K}$ (introducing a factor $d$ for $\lambda_{K}$ each time) or be linearly
independent (introducing a factor of $d$ because of the cross term
$\beta(x_{K},x_{i})$. In total, each $x_{i}$ introduces a factor of $d$,
making it a total of $d^{K-1}$ for all subsequent choices. In total,
introducing $x_{K}\neq 0$ will contribute $dd^{K-1}=d^{K}$. By assuming that
all other choices are the same as in the $K-1$ case, we may be overcounting
again, because new linear dependencies could emerge, but our result is an
upper bound in any case. Thus, there must be a factor of $d^{K}D_{K-1}$.

In combining the $x_{K}=0$ case and the $x_{K}\neq 0$ case, we obtain the
following recursion relation:

$D_{K}=(d^{K}+1)D_{K-1}=\prod_{k=0}^{K}(d^{k}+1)$ (3.31)

This reproduces all the countings made by hand for $K=1$ (see equation
(3.29)), $K=2$ (see equation (3.30)), and $K=3$ and $K=4$.

This does not correspond to $K$ party protocols. It is important to keep in
mind that one copy of the space $\mathcal{H}_{E}=\mathcal{H}^{\otimes n}$
belongs to Eve, while Alice and Bob share the other one,
$\mathcal{H}_{T}=\mathcal{H}^{\otimes n}$. In an $N$ party protocol, Alice
shares states with $N$ Bobs, which means that there are $N$ Hilbert spaces
$\mathcal{H}_{T_{i}}=\mathcal{H}^{\otimes n}$ for $i=1,...N$. However, when
aiming to apply the postselection theorem, Eve’s space must be taken into
consideration. In an $N$ party protocol, Eve has access to a copy of each of
Alice and Bob’s shared Hilbert spaces $\mathcal{H}_{T_{i}}$, meaning that Eve
has access to $N$ Hilbert spaces $\mathcal{H}_{E_{i}}=\mathcal{H}^{\otimes
n}$. In total, this means that there are $2N$ spaces $\mathcal{H}^{\otimes
n}$. Therefore, the dimension that will be relevant for the postselection
technique in Section 3.5 is the dimension of the subspace

$\big{(}(\mathcal{H}^{\otimes n})^{\otimes 2N}\big{)}^{\tilde{O}^{\otimes
2N}}.$

In conclusion, from the result for $D_{K}$, the $N$ party-related dimension
can easily be obtained by setting $K=2N$.

###  3.5 Results for QKD with Stochastic Orthogonal Symmetry

In this section, the postselection technique is applied to the stochastic
orthogonal symmetry group $\mathcal{O}_{n}$ introduced in Definition 4, which
leads to a mathematical bound on the diamond norm of
$\mathcal{O}_{n}$-invariant maps (as shown in Section 3.2), and subsequently
to a result on the security of $\mathcal{O}_{n}$-invariant QKD protocols (as
shown in Section 3.3). Both of these results depend on one number, the
dimension of the $\mathcal{O}_{n}$-invariant subspace
$g_{n,d}=\dim(\mathcal{N})=\dim((\mathcal{H}^{\otimes
n}\otimes\mathcal{H}^{\otimes n})^{O\otimes O})$. This number can be computed
via the counting of orbits of the discrete orthogonal group
$\tilde{\mathcal{O}}_{n-1}$, which has been achieved in Section 3.4.

Postselection technique can only be applied to the stochastic orthogonal group
because it fulfills the central assumption: resolution of identity. The
resolution of identity of the stochastic orthogonal group is ensured because
an appropriate integration measure has been shown to exist in [10]; for
discrete orthogonal group, it is not guaranteed.

As alluded to in Section 2.1.2, the discrete orthogonal group (for $n-1$
copies) and stochastic orthogonal group (for $n$ copies) are closely related
to each other for $n$ not a multiple of $d$. This is a result of the fact that
the difference between the two groups is the fact that the stochastic
orthogonal group preserves the all-ones-vector, while the discrete orthogonal
group does not. If the all-ones vector is not self-orthogonal (i.e. $n$ is not
a multiple of $d$), the vector space can be decomposed into a direct sum of a
part spanned by the all-ones vector and its orthocomplement, and the
stochastic orthonal matrices are block-diagonalized in the corresponding
basis, where one block acts on the all-ones vector’s span, and one block acts
on its orthocomplement. The block acting on the orthocomplement corresponds to
a discrete orthogonal matrix in $\tilde{\mathcal{O}}_{n-1}$, preserving the
linear product on this part of the vector space. Then, any vector ${v}$ on the
whole vector space can be written as a sum ${v}=k{v_{1}}+{v_{2}}$ where
${v_{1}}$ denotes the all-ones vector, the factor $k$ ranges from
$0,1,...,d-1$ and ${v_{2}}$ is a vector in the orthocomplement space of the
all-ones vector, which means ${v_{2}}$ is a vector in the vector space where
the discrete orthogonal group acts. For each orbit of the discrete orthogonal
group, the stochastic orthogonal group has $d$ orbits, corresponding to the
choices of $k$. In total, therefore, the number of orbits of the stochastic
orthogonal group for $n$ copies corresponds to the number of discrete
orthogonal group orbits for $n-1$ copies multiplied by $d$.

Because of this, the results obtained from orbit counting for
$\tilde{\mathcal{O}_{n-1}}$ have direct implications for the postselection
technique for $\mathcal{O}_{n}$, for $n$ not a multiple of $d$:

$g_{n,d}=\dim(\dim(\mathcal{H}^{\otimes n}\otimes\mathcal{H}^{\otimes
n})^{O\otimes
O})=d\dim(\mathcal{H}^{\otimes(n-1)}\otimes\mathcal{H}^{\otimes(n-1)})^{\tilde{O}\otimes\tilde{O}}=d^{4}+d^{3}+d^{2}+d$
(3.32)

For application to QKD, as established in Section 3.3, the
$\epsilon^{\prime}=g_{n,d}\epsilon=\dim(\mathcal{H}_{T}\otimes\mathcal{H}_{E})^{s\otimes\overline{s}}\epsilon$-security
of a protocol $\mathcal{E}^{\prime}$ against general attacks can be inferred
from $\epsilon$-security against collective attacks of a protocol
$\mathcal{E}$, if $\mathcal{E}^{\prime}$ is obtained from $E$ with an
additional privacy amplification shortening the key by $2\log
g_{n,d}=2\log\dim((\mathcal{H}_{T}\otimes\mathcal{H}_{E})^{s\otimes\overline{s}})$
bits. Therefore, for a two party QKD protocol, the security of general attacks
can be inferred from the security of collective attacks at the cost of
$g_{n,d}$ in the error, and $2\log g_{n,d}$ in the key length, with $g_{n,d}$
as given in equation (3.32).

This result can easily be extended to accommodate $N$ party QKD protocols,
with the following result:

$\dim\Big{(}\big{(}(\mathcal{H}^{\otimes n})^{\otimes 2N}\big{)}^{O^{\otimes
2N}}\Big{)}=g_{n,d,N}=\prod_{k=0}^{2N}d(d^{k}+1)$ (3.33)

as the multiplicative factor between collective and general attacks.

In comparison to previous results for permutation invariant maps, this number
constitutes a significant improvement, as it is very small and does not depend
on the number of copies $n$. Permutation-based postselection technique leads
to a polynomial in $n$:

$g_{n,d}^{(\mathcal{P}_{n})}=(n+1)^{d^{2}-1}$

for two parties, and

$g_{n,d,N}^{(\mathcal{P}_{n})}=(n+1)^{d^{2N}-1}$

for $N$ parties (see (3.2), and explained briefly in Section 3.4.1).

This means that the multiplicative factor between the diamond distance of CPTP
maps and the trace distance with one particular input state is smaller,
meaning there is a smaller gap between the upper bound and true diamond norm.
Furthermore, since the stochastic orthogonal symmetry preserves tensor powers
of stabilizer states, the relevant input state is a purification of a de
Finetti state constructed with tensor powers of stabilizer states. In a given
setting, there are significantly fewer stabilizer states than arbitrary
states, which is also an improvement.

To use this in the context of an actual QKD protocol, the number of copies $n$
should preferably be rather high in order to get a raw key that is as long as
possible. After the key has been sifted and error corrected, privacy
amplification is performed to transform it into a shorter, but completely
secret key. During this step, it is preferable to shorten the key as little as
possible, to ensure that the final key that Alice and Bob share is as long as
possible. In case of a general attack, there is an additional privacy
amplification step, where the same holds true: we want to shorten the key as
little as possible, while increasing the error as little as possible. During
this step, the shortening of the key and the change in the error is determined
by $g_{n,d}$. For our result, this means that the multiplicative change in the
error is smaller, and the key has to be shortened less in comparison with
previous schemes.

However, for the postselection technique to be applicable with stochastic
orthogonal group, a map with this symmetry is needed. In the context of QKD,
this would require a protocol with stochastic orthogonal symmetry. While such
a protocol could likely be constructed, investigating existing protocols also
has some potential, for example in form of 6-state protocol [58], $N$-party
6-state protocol [45] or protocols with orthogonal symmetry in continuous
variable schemes [59].

## 4 An SDP Hierarchy for Maximum Channel Fidelity Based on Stabilizer de
Finetti Theorem

While QKD security was initially the chief motivation for studying quantum de
Finetti theorems, the focus has long shifted to other applications as well.
One such example is the approximation of separable states using a hierarchy of
SDPs [13], based on DPS hierarchy [11, 12]. Under symmetric extension of one
party’s system (e.g. Bob’s), a bipartite state’s marginal becomes close to
separable in the cut between the two parties (Alice and Bob), with closeness
determined by a de Finetti theorem. In other words, a state
$\rho_{AB_{1}B_{2}\cdots B_{n}}\equiv\rho_{AB_{1}^{n}}$ which is invariant
under permutations of the subsystems $B_{i}$, can be approximated by a state
that is separable in the cut between $A$ and $B_{1}$ via a convergent
hierarchy of SDPs. In this Chapter, an analogue will be shown for stochastic
orthogonal transformations instead of permutations, leading to an
approximation by separable and (partly) stabilizer states.

In Section 4.1, a motivation for considering this kind of problem will be
given in the form of a QEC application. Section 4.2 states and proves the
underlying stabilizer de Finetti statement with linear constraints before
giving the associated SDP hierarchy and using it to establish convergence in
4.3. While this chapter will focus on the stabilizer de Finetti theorem with
linear constraints obtained from Theorem 2.2.2, an analogous version for
qubits using Theorem 2.2.3 will be mentioned, and an extended version with
stochastic orthogonal invariance on both Alice’s and Bob’s side is given in
Appendix C. Finally, in Section 4.4, some thoughts pertaining to numerical
results will be briefly stated.

###  4.1 Approximating Maximum Channel Fidelity

When classical communication channels are unreliable, the successful transfer
of a message is by no means certain. Common noise models include errors
occuring randomly but with fixed probability, or dynamic models where errors
may occur in bursts. When trying to counteract such noise with error
correction, it is integral to know if errors occur, and with what probability
they occur, which depends on the nature and amount of the imposed noise and
the length of the message. Therefore, a chief quantity of interest is the
maximum success probability for transmitting a uniform $d_{M}$-dimensional
message over a channel with a noise model $N_{X\rightarrow Y}$, given by
$p(N,d_{M})$. Finding this probability for different error correction
procedures then gives a hint as to which error correction is most successful.

Determining this success probability is a bilinear maximization problem, for
which the solution is in general NP-hard to approximate. However, there are
methods to approximate the solution from below as well as above, where the
latter is achieved by a linear programming relaxation of the problem [60, 61].
This linear programming relaxation $lp(N,d_{M})$ is efficiently computable and
has many useful analytic properties.

In similar spirit, the task of understanding data transfer in a quantum
setting, i.e. transferring a quantum state over a noisy quantum channel, gains
relevance as devices evolve and improve. Instead of maximum success
probability, one most commonly considers the maximum channel fidelity
$F_{c}(N,d_{M})$ for transmitting one part of a maximally entangled state over
a noisy channel, which can then be used to analyze and compare existing QEC
procedures.

For a channel $\mathcal{C}$ that transforms some input state $\rho_{in}$ into
an output state $\rho_{out}$, its fidelity is related to the overlap of the
transformed input $C(\rho_{in})$ and the desired output $\rho_{out}$, which
quantifies how much they differ. The fidelity of two states is therefore
defined in the following way:

$F_{s}(\rho_{out},C(\rho_{in}))=\big{\|}\sqrt{\rho_{out}}\sqrt{C(\rho_{in})}\big{\|}_{\operatorname{tr}}^{2}$

When defining channel fidelity for an error correcting procedure, the input
state is given by the maximally entangled state $\Phi_{AR}$, and the goal is
to transfer one part of it from system $A$ to system $\tilde{B}$ via a channel
$\mathcal{D}_{B\rightarrow\tilde{B}}\circ\mathcal{N}_{\tilde{A}\rightarrow{B}}\circ\mathcal{E}_{A\rightarrow\tilde{A}}$
(without affecting the part on system $R$). The sytems $A$, $R$ and
$\tilde{B}$ are all of dimension $d_{M}$. In applying this channel, the
quantum state passes an encoder channel $\mathcal{E}_{A\rightarrow\tilde{A}}$,
a noisy transmission channel $\mathcal{N}_{\tilde{A}\rightarrow{B}}$, and a
decoder channel $\mathcal{D}_{B\rightarrow\tilde{B}}$. To quantify how well
this channel transfers a part of the maximally entangled state, we want to
compare the transformed input
$\big{(}(\mathcal{D}_{B\rightarrow\tilde{B}}\circ\mathcal{N}_{\tilde{A}\rightarrow{B}}\circ\mathcal{E}_{A\rightarrow\tilde{A}})\otimes\mathbbm{1}_{R}\big{)}(\Phi_{AR})$
and the desired output $\Phi_{\tilde{B}R}$.

To determine maximum channel fidelity, we want to use the best possible
encoder and decoder. This translates to the following maximization problem for
determining $F_{c}(N,d_{M})$:

######  Optimization problem 4.1.1.

$\begin{split}F(N,d_{M})=\text{maximize}\
&F_{s}\Big{(}\Phi_{\tilde{B}R},\big{(}(\mathcal{D}_{B\rightarrow\tilde{B}}\circ\mathcal{N}_{\tilde{A}\rightarrow{B}}\circ\mathcal{E}_{A\rightarrow\tilde{A}})\otimes\mathbbm{1}_{R}\big{)}(\Phi_{AR})\Big{)}\\\
\text{subject to
}&\mathcal{E}_{A\rightarrow\tilde{A}},\mathcal{D}_{B\rightarrow\tilde{B}}\text{
are quantum channels}\end{split}$

Using the Choi-Jamiołkowski isomorphism, this can be rewritten as the
following bilinear optimization problem (note the similarity to the classical
case) with matrix-valued variables (see [13], Lemma 5.2):

######  Optimization problem 4.1.2.

$\begin{split}F(N,d_{M})=\text{maximize}\
&d_{\tilde{A}}d_{B}\operatorname{tr}\Big{(}\big{(}J_{\tilde{A}B}^{N}\otimes\Phi_{A\tilde{B}}\big{)}\big{(}E_{A\tilde{A}}\otimes
D_{B\tilde{B}}\big{)}\Big{)}\\\ \text{subject to }&E_{A\tilde{A}}\geq 0,\
D_{B\tilde{B}}\geq 0\\\
&\operatorname{tr}_{\tilde{A}}(E_{A\tilde{A}})=\frac{\mathbbm{1}_{A}}{d_{A}},\
\operatorname{tr}_{\tilde{B}}(D_{B\tilde{B}})=\frac{\mathbbm{1}_{B}}{d_{B}}\\\
\end{split}$

where $\Phi_{A\tilde{B}}$ is a maximally entangled state of dimension $d_{M}$
and $J_{\tilde{A}B}^{N}$ is the normalized Choi state corresponding to the
noisy channel transmitting a state from $\tilde{A}$ to $B$.

The maximum fidelity can be bound from below by seesaw methods [62], and there
exists an SDP relaxation to bound it from above [16]. (It is also worth
mentioning that there exist converse bounds which bound the message length
$d_{M}$ for a given fidelity [63, 64, 65, 66].) While this SDP relaxation is
efficiently computable, the gap between the SDP relaxation’s solution and the
actual maximum fidelity is not well understood. In [13], a converging
hierarchy of SDP relaxations on the maximum fidelity is proposed, enabling us
to study $F(N,d_{M})$ directly. (In fact, the first level of the hierarchy
reproduces the bounds of [16].) This relies on the idea that separable states
(like $E_{A\tilde{A}}\otimes D_{B\tilde{B}}$) can be approximated by a
hierarchy [67, 68, 11, 12].

This hierarchy relies on two key concepts: Firstly, that separable states
$\rho_{AB}$ are $n$-extendible, which means that $n-1$ systems can be added on
Bob’s side, extending the state to $\rho_{AB_{1}\cdots
B_{n}}\equiv\rho_{AB_{1}^{n}}$, such that $\rho_{AB_{1}^{n}}$ is invariant
under permutations of the subsystems of $B_{1}^{n}$. For example, a separable
quantum state $\rho_{AB}=\omega_{A}\otimes\tau_{B}$ can be $n$-extended to
$\rho_{AB_{1}^{n}}=\omega_{A}\otimes\tau_{B_{1}}\otimes\cdots\otimes\tau_{B_{n}}$,
which is obviously invariant under permutation of $B_{1}^{n}$. However, given
a state $\rho_{AB_{1}^{n}}$ that is invariant under permutations of the
subsystems of $B_{1}^{n}$, it is not immediately implied that it originates in
an $n$-extension of a separable state; but it is close, and this closeness can
be quantified in terms of a de Finetti theorem, which is the second key
concept. This approximation improves with increasing $n$, as the de Finetti
error decreases.

Using the extendibility property, the following approximation of maximum
channel fidelity in (4.1.2) can be proposed:

######  Optimization problem 4.1.3.

$\begin{split}F^{(n)}(N,d_{M})=\text{maximize}\
&d_{\tilde{A}}d_{B}\operatorname{tr}\Big{(}\big{(}J_{\tilde{A}B}^{N}\otimes\Phi_{A\tilde{B}}\big{)}\big{(}\rho_{A\tilde{A}B\tilde{B}}\big{)}\Big{)}\\\
\text{subject to }&\rho_{A\tilde{A}(B\tilde{B})_{1}^{n}}\geq 0,\
\operatorname{tr}(\rho_{A\tilde{A}(B\tilde{B})_{1}^{n}})=1\\\
&\rho_{A\tilde{A}(B\tilde{B})_{1}^{n}}\text{ is invariant under all
permutations}\\\
&\operatorname{tr}_{\tilde{A}}(\rho_{A\tilde{A}(B\tilde{B})_{1}^{n}})=\frac{\mathbbm{1}_{A}}{d_{A}}\otimes\rho_{(B\tilde{B})_{1}^{n}}\\\
&\operatorname{tr}_{\tilde{B}_{n}}(\rho_{A\tilde{A}(B\tilde{B})_{1}^{n}})=\rho_{A\tilde{A}(B\tilde{B})_{1}^{n-1}}\otimes\frac{\mathbbm{1}_{B_{n}}}{d_{B}}\\\
\end{split}$

This corresponds to level $n$ of a hierarchy approximating maximum channel
fidelity. Then, the convergence of such a hiearchy relies on a de Finetti
theorem.

It is important to note that a specific type of de Finetti theorem is needed
here; in particular, the standard version with best known convergence in 2.2.1
is not applicable in this scenario. While any extendability property leads to
separability on the side where permutation invariance is imposed, i.e. between
the systems $B_{i}$ in the above example and additional separability in the
cut between Alice and Bob (or encoder and decoder), the additional constraint
on the encoder’s and decoder’s marginal is not guaranteed in general.

The convergence towards a separable state with desired constraints on the
marginal ($Tr_{\tilde{A}}(E_{A\tilde{A}})=\frac{\mathbbm{1}_{A}}{d_{A}}$,
$\operatorname{tr}_{\tilde{B}}(D_{B\tilde{B}})=\frac{\mathbbm{1}_{B}}{d_{B}}$
in 4.1.2) can be ensured by imposing additional linear constraints of a
particular form on the state during the hierarchy (namely,
$\operatorname{tr}_{\tilde{A}}(\rho_{A\tilde{A}(B\tilde{B})_{1}^{n}})=\frac{\mathbbm{1}_{A}}{d_{A}}\otimes\rho_{(B\tilde{B})_{1}^{n}}$
and
$\operatorname{tr}_{\tilde{B}_{n}}(\rho_{A\tilde{A}(B\tilde{B})_{1}^{n}})=\rho_{A\tilde{A}(B\tilde{B})_{1}^{n-1}}\otimes\frac{\mathbbm{1}_{B_{n}}}{d_{B}}$
at level $n$ in 4.1.3), leading to the de Finetti theorem found in [13] and
stated below. Because a de Finetti theorem incorporating these constraints can
be found, the hierarchy can be shown to converge towards the desired form,
i.e. towards a solution of 4.1.2.

One could propose a simplified hierarchy where these constraints are modified
to be local constraints, i.e.
$\operatorname{tr}_{\tilde{A}}(\rho_{A\tilde{A}})=\frac{\mathbbm{1}_{A}}{d_{A}}$
and
$\operatorname{tr}_{\tilde{B}_{n}}(\rho_{B_{n}\tilde{B}_{n}})=\frac{\mathbbm{1}_{B_{n}}}{d_{B}}$
instead of constraints on the larger state as in (4.1.3), which allows for
communication between Alice and Bob. However, this would not lead to a
convergent hierarchy approximating the desired form, as it would not lead to a
mixture of normalized channels. In other words, not having these linear
constraints would lead to a convergence towards a mixture of maps which are
completely positive, but not trace preserving (in fact, maybe not even trace
non-increasing). Thereby, the desired constraint does not hold for each
summand in the mixture separately. For our applications, each summand must
obey the desired linear constraints separately, so that each part of the
mixture corresponds to a CPTP map via Choi-Jamiołkowski isomorphism. In
summary, what we want is separability with states that correspond to CPTP maps
instead of just separability. For details and counter-examples of theorems
with local (or no) linear constraints, we refer to Examples 3.7 in [13].

The theorem which ensures convergence of (4.1.3) towards maximum channel
fidelity is the following:

######  Theorem 4.1.1 (De Finetti Theorem with Linear Constraints, see [13],
Theorem 3.4).

Let $\rho_{AB_{1}^{n}}$ be a quantum state that is permutation invariant with
respect to permutations of the $n$ subsystems $B_{1}^{n}$. Let
$\Lambda_{A\rightarrow C_{A}}$ and $\Gamma_{B\rightarrow C_{B}}$ be linear
maps, and $X_{C_{A}}$ and $Y_{C_{B}}$ be operators such that the following two
linear constraints hold:

$\Lambda_{A\rightarrow
C_{A}}(\rho_{AB_{1}^{n}})=X_{C_{A}}\otimes\rho_{B_{1}^{n}},$
$\Gamma_{B_{n}\rightarrow C_{B}}(\rho_{B_{1}^{n}})=\rho_{B_{1}^{n-1}}\otimes
Y_{C_{B}}.$

Then, there exists an $m\in[0,n-1]$ and a probability distribution
$\\{p_{Z}(z_{1}^{m})\\}_{z_{1}^{m}\in Z}$ such that

$\Big{\|}\rho_{AB_{m+1}}-\sum_{z_{1}^{m}}p_{Z}(z_{1}^{m})\rho_{A|z_{1}^{m}}\otimes\rho_{B_{m+1}|z_{1}^{m}}\Big{\|}_{\operatorname{tr}}\leq\epsilon(d_{B},d_{A},n)$

where

$\epsilon(d_{B},d_{A},n):=\min\Big{\\{}d_{B}^{2}(d_{B}+1),18\sqrt{d_{A}d_{B}}\Big{\\}}\sqrt{\frac{2\ln(2)\ln(d_{A})}{n}}$
(4.1)

and

$\Lambda_{A\rightarrow C_{A}}(\rho_{A|z_{1}^{m}})=X_{C_{A}},\
\Gamma_{B_{m+1}\rightarrow C_{B}}(\rho_{B_{m+1}|z_{1}^{m}})=Y_{C_{B}}.$

######  Remark.

Note that Theorem 4.1.1 is not equivalent to the full theorem as it appears in
[13], but rather appears at an intermediate step in the proof of their main
theorem. For completeness, the full proof of this modified statement is given
in Appendix B.

######  Remark.

As noted before, the linear constraints are of a particular form, requiring
$\Lambda_{A\rightarrow
C_{A}}(\rho_{AB_{1}^{n}})=X_{C_{A}}\otimes\rho_{B_{1}^{n}}$ instead of a
localized version $\Lambda_{A\rightarrow C_{A}}(\rho_{AB_{1}^{n}})=X_{C_{A}}$.
While these two conditions are equivalent under the trace, it is important
that they are not equivalent in general. Phrasing the constraint like this
ensures that any correlations may only be within Alice’s or within Bob’s side,
not between them, and it is crucial for the convergence of the hierarchy
towards the desired form in 4.1.2.

As found in [13], using this theorem while renaming $A\rightarrow A\tilde{A}$,
$B\rightarrow B\tilde{B}$, $C_{A}={A}$,
$\Lambda_{A\tilde{A}\rightarrow{A}}=\operatorname{tr}_{\tilde{A}}$ and
$X_{A}=\frac{\mathbbm{1}_{A}}{d_{A}}$, as well as $C_{B}={B}$,
$\Gamma_{B\tilde{B}\rightarrow{B}}=\operatorname{tr}_{\tilde{B}}$ and
$Y_{B}=\frac{\mathbbm{1}_{B}}{d_{B}}$, it can be shown that the optimal values
of the SDP relaxation in (4.1.3) converge to the optimal value of (4.1.2) for
$n\rightarrow\infty$. The difference between the state
$\rho_{A\tilde{A}B\tilde{B}}$ obeying the constraints in (4.1.3), and the
state $E_{A\tilde{A}}\otimes D_{B\tilde{B}}$ obeying the constraints listed in
(4.1.2) is essentially given by the error bound in Theorem 4.1.1, which means
that the proof and speed of this convergence rely exclusively on Theorem
4.1.1.

In this project, we want to investigate the problem of studying maximum
channel fidelity using stabilizer de Finetti theorems instead of the
traditional de Finetti theorems with permutation invariance. Because Theorems
2.2.2 and 2.2.3 describe closeness to tensor powers of stabilizer states
rather than arbitrary states, this would lead to a new hierarchy containing
additional constraints which ensure that the encoder, decoder or encoder and
decoder are related to Choi-matrixes of stabilizer states, which are Clifford
operations. This does not only greatly reduce the amount of states one has to
optimize over, but also makes it interesting for studying Clifford-related
problems in general, in particular for studying Clifford encoders and/or
decoders rather than arbitrary encoders and decoders.

In short, we want to approximate (for example) the following fidelity:

######  Optimization problem 4.1.4.

$\begin{split}F_{C}(N,d_{M})=\text{maximize}\
&F_{s}\Big{(}\Phi_{\tilde{B}R},\big{(}(\mathcal{D}_{B\rightarrow\tilde{B}}\circ\mathcal{N}_{\tilde{A}\rightarrow{B}}\circ\mathcal{E}_{A\rightarrow\tilde{A}})\otimes\mathbbm{1}_{R}\big{)}(\Phi_{AR})\Big{)}\\\
\text{subject to }&\mathcal{E}_{A\rightarrow\tilde{A}}\text{ is a quantum
channel}\\\ &\mathcal{D}_{B\rightarrow\tilde{B}}\text{ is a Clifford
channel}\end{split}$

We find that this is indeed possible for stochastic orthogonal symmetry at a
small cost to precision by finding a stabilizer de Finetti theorem with
additional linear constraints. This cost can be neglected in comparison to the
overall error. From this theorem, an analogous converging hierarchy for states
with stochastic orthogonal symmetry instead of permutation symmetry can be
proposed for odd prime dimensions $d_{B}$. Using this hierarchy, we can
approximate the maximum channel fidelity of an optimal (arbitrary) encoder and
optimal Clifford decoder instead of the maximum channel fidelity of an optimal
arbitrary encoder and decoder. In addition, a hierarchy for qubits can also be
found for states with invariance under permutations plus anti-identity,
following from stabilizer de Finetti theorem for qubits 2.2.3. However, since
both of these results are obtained very similarly, details will only be given
for the case of stochastic orthogonal symmetry.

Because our results will be symmetric under exchange of Alice and Bob, note
that our theorem and subsequent hierarchy can also be employed to approximate
maximum channel fidelity of an optimal Clifford encoder and an optimal
(arbitrary) decoder. Furthermore, the theorem can be extended to lead to a
hierarchy for finding maximum channel fidelity of an optimal Clifford encoder
and an optimal Clifford decoder, see Appendix C.

######  Remark.

In Theorem 4.1.1, when permuting the systems $B_{1}^{n}$, each subsystem
$B_{i}$ has local Hilbert space dimension $d_{B}$, containing
$d_{B}$-dimensional qudits. In the case of stochastic orthogonal
transformations of $B_{1}^{n}$, each subsystem consists of $r$ qudits, which
means that each subsystem $B_{i}$ has a Hilbert space dimension $d_{B}^{r}$.
To effectively compare results for permutation invariance and stochastic
orthogonal invariance, this difference needs to be taken into account, i.e.
one has to look at $\epsilon(d_{B}^{r},d_{A},n)$. However, comparing results
and bounds is not the main objective of replacing permutation invariance by
stochastic orthogonal invariance - instead, this replacement is motivated by
the prospect of studying Clifford decoders and encoders instead of arbitrary
encoders and decoders.

###  4.2 Stabilizer de Finetti Theorem with Linear Constraints

For proposing an analogue hierarchy to approximate maximum channel fidelity
with Clifford encoders or decoders, an appropriate de Finetti theorem is