\section{Introduction}

Compression of information is essential in order to make efficient use of limited storage space or bandwidth. This is even more true if we work with quantum information for which decoherence is an existential threat that makes reliable storage or transmission an extraordinary difficult task. 

In this work, we consider the situation in which an unknown quantum state has to be stored for some time before  one out of a set of measurements is performed. We assume that this set is known beforehand and we investigate to what extent the required storage space, measured in terms of its Hilbert space dimension, can be reduced depending on the set of measurements.
 Intuitively, in this setup only the information relevant for the given set of measurements has to be preserved. So if this set is not too large and sufficiently benign, this might allow for compression that is either lossless or only introduces small errors in the measurement statistics. 
Since classical storage space is cheap compared to quantum storage, we allow for an arbitrary amount of classical side information in this process. One may envision the considered situation as part of a larger protocol, where one party has to wait for additional input that then determines the measurement to be performed. A different scenario where our analysis could be applicable is in protocols with a bounded storage assumption.

Before going into details, let us review some of the different notions of compression that appear in 
 quantum information theory and see how they relate to or differ from the setup analyzed in this paper.  A classical task is \emph{quantum source coding} \cite{Schuhmacher1995}. Here, one is given an ensemble of pure quantum states and a quantum source that prepares elements from this set with a given probability. The aim is to encode a string of these states into one of smaller length so that the original message can be retrieved up to a small error. The compression rate for which this is possible is famously bounded by the von Neumann entropy of the state describing the source and asymptotically the error can be made arbitrarily small. Hence, in this setup compression works irrespective of the measurement or operation that is eventually performed on the system. 

Another version of compression can be found in \cite{Winter2004a}. Given a quantum state and a positive operator valued measure (POVM), the task is to find another POVM acting on many copies of the state whose outcomes have fewer entropy. The new POVM is required to be close to the original on
. This amounts to reducing the number of POVM elements compared to the POVM which consists of tensor powers of the original one. The compression rate can again be bounded in terms of the entropy of the state and properties of the original POVM. These results are proven in the asymptotic setting of many copies of a given quantum state, but the results in \cite{Aubrun2016} show that similar compression is also possible in a non-asymptotic setup.

Instead of compressing either states or POVMs, one could also be interested in compressing both, which is the setting of \emph{model compression}. Given a set of states and  POVMs, the task is to find new states and POVMs in a Hilbert space of smaller dimension, such that the measurement statistics are unchanged, possibly up to a small error. The original and new elements need not be connected by a physical transformation. In \cite{Stark2014}, this was shown to be possible if all effect operators except one per POVM have low rank. Here, the compression is a non-linear map. 
In the same vein, lower bounds in terms of the entropy of measurement outcomes have been proven in \cite{Wehner2008}, based on random access codes.

Compared to the first two notions of compression discussed above, the setup of our paper starts with the single-copy scenario (rather than with the asymptotic case) and aims at minimizing the system size under the constraint that after decompression only the statistics of a given set of observables have to be preserved. In this respect, our setup is similar to model compression. Contrary to the setting of model compression, however, we demand both compression and decompression to be achieved by physical transformations. Moreover, we allow for an arbitrary amount of classical information, which is considered to be for free. 


\section{Main results} \label{sec:results}

In this section, we will briefly outline the framework together with our main results. More detailed formulations and further results will be provided in subsequent sections. The starting point of our analysis is a set of measurements described by positive operator valued measures (POVMs). This means that one can assign a positive operator---a so-called \emph{effect operator}---to every measurable subset of outcomes. Let $\mathcal{O}$ be the collection of all effect operators that belong to the considered measurements. If the underlying Hilbert space has dimension $D$, then $\mathcal{O}$ is a subset of the set $\mathcal{M}_D$ of complex $D\times D$ matrices. The type of compression we are interested in is given by a \emph{compression map} $\mathcal{C}:\mathcal{M}_D\rightarrow\mathcal{M}_d\otimes\mathds{C}^n$ and a \emph{decompression map} $\mathcal{D}:\mathcal{M}_d\otimes\mathds{C}^n\rightarrow\mathcal{M}_D$. Both maps are completely positive and trace preserving and such that for every density operator $\rho\in\mathcal{M}_D$ and every effect $E\in\mathcal{O}$ it holds that
\begin{equation}\label{eq:1mainresults}
\tr{(\mathcal{D}\circ\mathcal{C})[\rho] E}=\tr{\rho E}.
\end{equation}
That is, we require the measurement statistics after compression and decompression to be exactly preserved. Here, $n\in\mathds{N}$ quantifies the amount of classical  information and $d\in\mathds{N}$ is the intermediate Hilbert space dimension that we want to minimize. For a given $\mathcal{O}$, the minimal such dimension will be called its \emph{compression dimension}. If this equals $D$, we call $\mathcal{O}$  \emph{incompressible}. 


Our first finding (\Fref{lem:boundedsideinfo}) is that the amount of classical information can without loss of generality be restricted to $4 \log D$ bits. More precisely, if a map $\mathcal{T}:\mathcal{M}_D\rightarrow\mathcal{M}_D$ can be realized as $\mathcal{T}=\mathcal{D}\circ\mathcal{C}$ for given $n,d$, then it can be realized in this way with $n\leq D^4$ and $d$ unchanged. This fact, together with a compactness argument, then enables us to prove (\Fref{thm:inexactcase}) that the compression dimension is stable in the following sense: for every set of measurements there is an $\epsilon>0$ such that even if deviations from \Fref{eq:1mainresults} up to $\epsilon$ are allowed, the compression dimension cannot be decreased. In other words, allowing for errors does not change the picture as long as these are small enough.
In the light of this, the remaining part of the work then considers exact compression. 

We prove  bounds on the compression dimension following two different approaches: an operator algebraic and an algebro-geometric approach, to which we will for brevity refer to as algebraic and geometric, respectively. The algebraic path is based on the C$^\ast$-algebra $\cstar{\mathcal{O}}$ generated by $\mathcal{O}$. Being finite-dimensional, it is, up to an isomorphism, always of the form
\begin{equation*}\label{eq:summaryCstar1}
\cstar{\mathcal{O}}\simeq \bigoplus_i \mathcal{M}_{D_i}.
\end{equation*}
\begin{thm*}[Algebraic bounds on the compression dimension]
Let $d$ be the compression dimension of $\mathcal{O}$ and $\{D_i\}$ be the dimensions of the matrix algebras occurring in the representation of the C$^\ast$-algebra $\cstar{\mathcal{O}}$. Then it holds that $\min_i\{D_i\}\leq d \leq\max_i \{D_i\}$.
\end{thm*}
This is the content of \Fref{thm:newarveson} and \Fref{thm:blockcompression}. If $\mathcal{O}$ for instance contains the effect operators of two binary von Neumann measurements, then these bounds generically coincide and are equal to $d=2$ if $D$ is even (\Fref{sec:twoproj}). For structureless $\mathcal{O}$ with more than two elements, however, \Fref{lem:matrixalgebrameasure1} shows that the foregoing theorem implies that $d=D$, so that $\mathcal{O}$ is incompressible.
 
The bounds in the foregoing theorem are tight in the sense that they cannot be improved solely on the basis of $\cstar{\mathcal{O}}$ (unless the algebra consists only of one large block and one or two blocks of dimension one, in which case $d=\max_i \{D_i\}$, cf.\  \Fref{cor:possiblyredundant}). 
In particular, there are cases where the compression dimension is substantially smaller than the algebra generated by $\mathcal{O}$.
In more abstract terms: the  C$^\ast$-algebra is too coarse and we need to resort to the operator system that is generated by $\mathcal{O}$. In doing so,  the following is shown in \Fref{sec:computing}. The complexity of the corresponding algorithm is analyzed in \Fref{sec:complexity}. 
\begin{thm*}[Algorithm for the minimal compression dimension]
The compression dimension of $\mathcal{O}$ is given by one of the matrix dimensions $D_i$ that occur in the representation of the C$^\ast$-algebra $\cstar{\mathcal{O}}$. It can be computed by an algorithm that is based on a semidefinite program. 
\end{thm*}

The proof of correctness for this algorithm implies that the amount of classical side information needed is upper bounded by the number of matrix algebras occurring in the representation of $\cstar{\mathcal{O}}$. This bound is sharper than the one on the classical side information needed for arbitrary maps of the form $\mathcal{T} = \mathcal{D} \circ \mathcal{C}$.

The geometric approach leads to the following lower bound (\Fref{thm:geometric}):
\begin{thm*}[Algebro-geometric lower bound on the compression dimension]
Let $E_1$, $E_2 $ be in the real linear span of $\mathcal{O}$ and define the real polynomial $p(x,z):=\det[x\idop - E_1 - z E_2]$. The smallest of the degrees of the irreducible factors over the reals of $p$ is a lower bound on the compression dimension of $\mathcal{O}$. 
\end{thm*}
Again, if $E_1$ and $E_2$ are generic, structureless effect operators, then this lower bound is equal to $D$ (\Fref{lem:exirredpoly}). As such, the geometric lower bound turns out to be weaker than the algebraic one. However, it becomes more powerful if the setup is extended. 
For example, if several copies of the state $\rho$ are provided, the geometric argument is still valid and the lower bound remains unchanged (cf.\  \Fref{thm:copies}). The same is true if we allow for positive (de-)compression maps that are not necessarily completely positive (cf.\  \Fref{sec:generalizations}). Irrespective of the method, all our results still hold if we are only interested in preserving the expectation values of the measurements instead of the full statistics. This is true, because the elements in $\mathcal{O}$ need  not be positive but only Hermitian.

Along the way, we prove some results that might be of independent interest. This includes in particular results on (Schwarz-) positive maps.


\section{Preliminaries} \label{sec:prelim}
In this section, we will review some concepts and notations from quantum information theory and classical algebraic geometry. Let $\mathcal{M}_{m,n}$ for $n$, $m \in \mathds{N}$ denote the complex $m \times n$ matrices, which we concisely write as $\mathcal{M}_n$ for $m = n$. The set of Hermitian $n \times n$ matrices will be written $\mathcal{M}^\herm_n$; the set of real symmetric ones  $\mathcal{M}^\sym_n$. For a set $\mathcal{O} \subset \mathcal{M}_n$, we will denote by $\cstar{\mathcal{O}}$ the complex C$^\ast$-algebra generated by $\mathcal{O}$ and the identity matrix $\idop$. We will also need the unitary group on $\mathds{C}^d$, $d \in \mathds{N}$, which we write as $\mathcal{U}(d)$. By $\norm{\cdot}_\infty$, we denote the operator norm, whereas $\norm{A}_p$, $p \in \mathds{N}$, is the Schatten p-norm for $A \in \mathcal{M}_d$. If $\Ket{\phi} \in \mathds{C}^d$, $\norm{\Ket{\phi}}_2$ is its Euclidean norm. For brevity, we will often refer to the set $\Set{1, \ldots, n}$ as $[n]$.

 We will work exclusively in  finite-dimensional settings with Hilbert space $\mathcal{H} \simeq \mathds{C}^d$ for some $d \in \mathds{N}$ so that   the bounded linear operators are represented by $d \times d$ matrices with complex entries. The set of states/density operators is defined as $\SS(\mathds{C}^d) := \Set{\rho \in \mathcal{M}_d : \tr{\rho} = 1, \rho \geq 0}$. Any pure state on a bipartite system $\mathds{C}^{d_A} \otimes \mathds{C}^{d_B}$, $d_A$, $d_B \in \mathds{N}$, can be expressed in terms of its Schmidt decomposition. This means that for any pure state $\Ket{\psi} \in \mathds{C}^{d_A} \otimes \mathds{C}^{d_B}$ there are orthonormal sets $\Set{\Ket{e_i}}_{i = 1}^k \subset{\mathds{C}^{d_A}}$ and $\Set{\Ket{f_j}}_{j = 1}^k \subset \mathds{C}^{d_B}$ such that 
\begin{equation*}
\Ket{\psi} = \sum_{i = 1}^k \sqrt{\lambda_i} \Ket{e_i} \otimes \Ket{f_i}
\end{equation*}
for some $\lambda_i > 0$ for all $i \in [k]$ and such that $\sum_{i = 1}^k \lambda_i = 1$. Here, $k \in \mathds{N}$ is the Schmidt rank of $\Ket{\psi}$ \cite[Proposition 2.2.1]{Keyl2002}. This concept can be extended to mixed states \cite[Definition 1]{Terhal2000}:
\begin{defi}[Schmidt number]\label{def:schmidtnumber}
A mixed state $\rho \in \SS(\mathds{C}^{d_A} \otimes \mathds{C}^{d_B})$ has Schmidt number $k$ if for any decomposition $\Set{p_i \geq 0, \Ket{\psi_i}}_{i = 1}^n$, $n \in \mathds{N}$, with
\begin{equation*}
\rho = \sum_{i = 1}^n p_i \dyad{\psi_i} 
\end{equation*}
at least one of the pure states $\Ket{\psi_i} \in \mathds{C}^{d_A} \otimes \mathds{C}^{d_B}$, $i \in [n]$, has Schmidt rank $k$ and there exists a decomposition into pure states such that every pure state has Schmidt rank at most $k$.
\end{defi}

The concept of measurement will be expressed through the set of effect operators $\mathcal{E}(\mathds{C}^d): = \Set{E \in \mathcal{M}^\herm_d : 0 \leq E \leq \idop}$. Let $\Sigma$ be the set of measurement outcomes, which we assume to be countable for simplicity. A set of effect operators $\Set{E_s}_{s \in \Sigma}$, $E_s \in \mathcal{E}(\mathds{C}^d)$ for all $s \in \Sigma$ characterizes a positive operator valued measure (POVM) if 
\begin{equation*}
\sum_{s \in \Sigma} E_s = \idop
\end{equation*} 
(cf.\  \cite[Section 2.1.4]{Keyl2002}).

We describe transformations on physical systems by completely positive maps. Let $D \in \mathds{N}$. Recall that a linear map $\mathcal{T}:\mathcal{M}_D \to \mathcal{M}_d$ is called $m$-positive if $\mathcal{T} \otimes \id_m: \mathcal{M}_D \otimes \mathcal{M}_m \to \mathcal{M}_d \otimes \mathcal{M}_m$ is positive, where $\id_m$ is the identity map on $\mathcal{M}_m$. $\mathcal{T}$ is completely positive if it is positive for all $m \in \mathds{N}$. This is equivalent to $\mathcal{T}$ having the form $\mathcal{T}(A) = \sum_{i = 1}^k V_i^\ast   A V_i$, where $V_i \in \mathcal{M}_{D,d}$ are the Kraus operators \cite[Section 8.2.3]{Nielsen2010}. If the map is additionally trace preserving, we will call this a quantum channel or a CPTP map. For $\mathcal{T}: \mathcal{M}_D \to \mathcal{M}_d$ completely positive, the map $\mathcal{T}^\ast  : \mathcal{M}_d \to \mathcal{M}_D$ will be the dual map with respect to the Hilbert-Schmidt inner product. If $\mathcal{T}$ is trace preserving, the dual channel $\mathcal{T}^\ast  $ is unital and furthermore it is completely positive if and only if its dual map is. We will denote by $\Ket{\Omega}$ a maximally entangled state on $\mathds{C}^{D^2}$,
\begin{equation*}
\Ket{\Omega} := \frac{1}{\sqrt{D}} \sum_{j = 1}^D \Ket{j}\otimes\Ket{j},
\end{equation*}
where $\Set{\Ket{j}}_{j = 1}^D$ is an orthonormal basis of $\mathds{C}^D$. A convenient way to check complete positivity of a linear map $\mathcal{T}: \mathcal{M}_D \to \mathcal{M}_d$ is to compute its Choi matrix \cite{Choi1975}
\begin{equation*}
\tau = \mathcal{T} \otimes \id_D(\dyad{\Omega}).
\end{equation*}
It is known that $\mathcal{T}$ is completely positive if and only if $\tau$ is positive. One type of completely positive map which we will encounter frequently is the map $\Theta_{A}: \mathcal{M}_D \to \mathcal{M}_d$, defined as 
\begin{equation*}
\Theta_{A}(B) := A^\ast   B A \qquad \forall B \in \mathcal{M}_D
\end{equation*}
for fixed $A \in \mathcal{M}_{D,d}$.

Apart from completely positive maps, we will also need the notion of Schwarz maps. These are the unital positive linear maps for which the  Schwarz inequality
\begin{equation} \label{eq:schwarz}
\mathcal{T}(A^\ast  ) \mathcal{T}(A) \leq \mathcal{T}(A^\ast   A)
\end{equation}
holds true for all $A \in \mathcal{M}_D$. Note that every unital $2$-positive map (and hence also every unital completely positive map) fulfills the Schwarz inequality \cite[Proposition 3.3]{Paulsen2003}.

Furthermore, we will need some notation to work with polynomials. Let  $\mathds{R}[x_1, \ldots, x_n]$, $n \in \mathds{N}$, be the ring of polynomials in $n$-variables with real coefficients. In this work, we will only be concerned with irreducibility over the reals. Let 
\begin{equation*}
\bfH^d(n) = \Set{f \in \mathds{R}[x_1, \ldots, x_n] : f(\lambda x_1, \ldots, \lambda x_n) = \lambda^d f(x_1, \ldots, x_n) }
\end{equation*}
be the space of homogeneous polynomials in $n$ variables of degree $d$, $d \in \mathds{N}$. We will identify a polynomial with the vector of its coefficients when convenient. The set of homogeneous polynomials in $n$ variables and of any degree will be denoted by $\bfH(n) = \bigcup_{d \in \mathds{N}}\bfH^d(n)$. We recall which homogeneous polynomials are called hyperbolic: 
\begin{defi}[Hyperbolic polynomials]
Let $p \in \bfH^d(n)$. It is called hyperbolic with respect to the vector $e \in \mathds{R}^n$ if $p(e) \neq 0$ and if for all vectors $w \in \mathds{R}^n$ the univariate polynomial $t \mapsto p(w - t e) $ has only real roots.
\end{defi}
We will write $\mathcal{Z}(f)$ for the real zero set of the polynomials contained in the ideal generated by $f$. For $f \in \mathds{R}[x,y]$ ($f \in \bfH(3)$), this set will be called an algebraic curve in real (projective) space.
We can always switch between homogeneous and affine coordinates by homogenization, introducing an additional variable, and setting this additional variable to $1$, respectively (cf.\  \cite[$\mathsection 3$]{Bix2006}).
To conclude this section, let us finish by stating a classical result in algebraic geometry about the number of intersections of two algebraic curves (cf.\  \cite[Theorem 11.10]{Bix2006}).
\begin{lem}[B{\'e}zout's theorem]\label{lem:realbezout}
Let $f \in \bfH^m(3)$, $g \in \bfH^n(3)$ such that they have no common factors of positive degree over the real numbers. Then the curves $\mathcal{Z}(f)$ and $\mathcal{Z}(g)$ intersect at most $m \cdot n$ times, counting multiplicities, in the real projective plane.
\end{lem}
Then, of course, it is also true that $\mathcal{Z}(f(\cdot,1,\cdot))$ and $\mathcal{Z}(g(\cdot,1,\cdot))$ intersect in at most $m \cdot n$ points, since going to the projective plane only adds intersection points at infinity (points with $y = 0$).


\section{Setup} \label{sec:setup}




In most of this work, we will consider the following situation: We would like to perform at some later point a set of $s$ measurements, $s \in \mathds{N}$, each with countably many outcomes $\Set{a^k_i}_{i = 1}^{m_k}$, $m_k \in \mathds{N} \cup \Set{\infty}$, where the index $k$ denotes the $k$-th measurement. That is, upon preparation $\rho \in \SS(\mathds{C}^D)$ we obtain outcome $a^k_i$ with probability $\tr{\rho E^k_i}$ for all $i \in [m_k]$, $k \in [s]$. Here, $E_i^k \in \mathcal{E}(\mathds{C}^D)$ is the effect operator associated to outcome $a_i^k$ and the effect operators $\Set{E_i^k}_{i = 1}^{m_k}$ belonging to the same measurement form a POVM.  Let us define the set of these effect operators
\begin{equation*}
\mathcal{O} = \Set{E_i^k: i \in [m_k], k \in [s]}.
\end{equation*}
Note that assuming the outcomes to be countable simplifies notation, but our setup can easily be adapted to real measurement outcomes, for example. In that case, each effect corresponds to a measurable set of outcomes. See \cite[Section 3.1.4]{Heinosaari2012a} for details. 

 We are given an unknown quantum state $\rho \in \SS(\mathds{C}^D)$ that we want to store. In order to use a minimum of storage space, we want to keep only the information in the state relevant for the measurements that give rise to $\mathcal{O}$. Motivated by the fact that classical information is cheap to store compared to quantum information,  we aim to minimize the dimension of the quantum system while allowing for an arbitrarily large amount of classical side information. Therefore, we are looking for a quantum compression channel $\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_{d}\otimes \mathds{C}^n$ and a quantum decompression channel $\mathcal{D}: \mathcal{M}_{d}\otimes \mathds{C}^n \to \mathcal{M}_D$ such that for their composition $\mathcal{T} = \mathcal{D} \circ \mathcal{C}$, the outcomes of the specified observables occur with the same probability as for the original state: 
\begin{equation*}
\tr{\rho E} = \tr{\mathcal{T}(\rho) E}= \tr{\rho \mathcal{T}^\ast  (E)} \qquad \forall \rho \in \SS(\mathds{C}^D), \forall E \in \mathcal{O}.
\end{equation*}
The channels $\mathcal{C}$ and $\mathcal{D}$ can be seen as an instrument and a parameter dependent operation, respectively (cf.\  \cite[Section 3.2.5]{Keyl2002}). 
Now we can define our notion of compression.

\begin{defi}[Compression of observables]
Let $\mathcal{O}$ be a set of Hermitian operators in $\mathcal{M}_D$. The  \emph{compression dimension} of $\mathcal{O}$ is the smallest $d\in\mathds{N}$ for which there is an $n\in\mathds{N}$, 
a CPTP map $\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_{d}\otimes \mathds{C}^n$ and a CPTP map $\mathcal{D}: \mathcal{M}_{d}\otimes \mathds{C}^n \to \mathcal{M}_D$ such that for their composition $\mathcal{T} = \mathcal{D} \circ \mathcal{C}$, the constraints 
\begin{equation}\label{eq:constraint}
\tr{\rho E} = \tr{\mathcal{T}(\rho) E}= \tr{\rho \mathcal{T}^\ast  (E)} \qquad \forall \rho \in \SS(\mathds{C}^D), \forall E \in \mathcal{O}
\end{equation}
are satisfied. If the compression dimension equals $D$, $\mathcal{O}$ is said to be \emph{incompressible}.
\end{defi}
Note that the constraints are linear, hence the relevant object is the linear subspace spanned by the effect operators, not the effect operators themselves. As the dual channel $\mathcal{T}^\ast$ is unital, we can add the identity to $\mathcal{O}$ without loss of generality. Then the linear subspace contains the identity operator and is therefore an operator system. Let us denote the Hermitian part of this operator system by
\begin{equation*}
\mathcal{L}(\mathcal{O}) := \linspan[\mathds{R}]{\mathcal{O}; \idop}.
\end{equation*}
This also implies that it is irrelevant whether the effect operators belong to the same observable or to different ones, although these are two different physical situations. Therefore, we will henceforth only assume that $\mathcal{O} \subset \mathcal{M}_D^\herm$ instead of requiring the elements in $\mathcal{O}$ to be positive or even effect operators.

\section{Approximate compression}\label{sec:inexact}

In \Fref{sec:setup}, we have demanded the measurement statistics to be exactly conserved. This may seem very restrictive, but we will see shortly that it can be relaxed without changing the picture.  The aim of this section is to show that the inexact case in which we demand 
\begin{equation*}\label{eq:inexactconstraint}
|\tr{\rho E} - \tr{\mathcal{T}(\rho) E} | \leq \epsilon \qquad \forall \rho \in \SS(\mathds{C}^D), \forall E \in \mathcal{O}.
\end{equation*}
instead of \Fref{eq:constraint} reduces to the exact case ($\epsilon = 0$) for $\epsilon$ small enough. This is the content of the following theorem:
\begin{thm}[Stability of compression dimension] \label{thm:inexactcase}
Let $\mathcal{O} \subset \mathcal{M}_D^\herm$ be a compact set with compression dimension $d$. Then there is an $\epsilon > 0$ such that for any $d^\prime < d$, $d^\prime \in \mathds{N}$ and any CPTP maps $\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_{d^\prime} \otimes \mathds{C}^n$, $\mathcal{D}:\mathcal{M}_{d^\prime} \otimes \mathds{C}^n \to \mathcal{M}_D$ with $n \in \mathds{N}$ there is a state $\rho \in \SS(\mathds{C}^D)$ and an operator $E \in \mathcal{O}$  for which 
\begin{equation*}
|\tr{\rho E} - \tr{(\mathcal{D} \circ \mathcal{C})[\rho]E}| \geq \epsilon.
\end{equation*}
\end{thm}

The compression dimension is therefore stable under small errors. To prove the statement, we will need the following lemma, which  shows that $4 \log D$ bits of classical side information suffice for compression.
\begin{lem}[Bound on classical information] \label{lem:boundedsideinfo}
Let $\mathcal{C}$, $\mathcal{D}$ be two CPTP maps, $\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^n $, $\mathcal{D}: \mathcal{M}_d \otimes \mathds{C}^n \to \mathcal{M}_D$, $n \in \mathds{N}$ and $d \leq D$. We define $\mathcal{T} := \mathcal{D} \circ \mathcal{C}$. Then there are two CPTP maps $\widetilde{\mathcal{C}}: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^{n_0}$, $\widetilde{\mathcal{D}}: \mathcal{M}_d \otimes \mathds{C}^{n_0} \to \mathcal{M}_D$ with $n_0 \in \mathds{N}$, $n_0 \leq D^4$ such that $\mathcal{T} = \widetilde{\mathcal{D}} \circ \widetilde{\mathcal{C}}$.
\end{lem}
\begin{proof}
Note that $\mathcal{M}_d \otimes \mathds{C}^n \simeq \bigoplus_{i = 1}^n \mathcal{M}_d$ has a block structure. Let $P_i$ be the projection onto the $i$-th block. Then $\mathcal{T}_i := \mathcal{D} \circ \Theta_{P_i} \circ \mathcal{C}$ is again a completely positive map, although not necessarily trace preserving. The Choi matrix can thus be written
\begin{equation*}
(\mathcal{T} \otimes \id)(\dyad{\Omega}) = \sum_{i = 1}^n (\mathcal{T}_i \otimes \id)(\dyad{\Omega}).
\end{equation*}
We will argue that the Choi matrix has Schmidt number at most $d$ (see \Fref{def:schmidtnumber}). By the introduction of an isometry $V_i: \mathds{C}^{d} \hookrightarrow \mathds{C}^{nd}$ such that $V_i V_i^\ast = P_i$, we can decompose $\mathcal{T}_i = \mathcal{D}_i \circ \mathcal{C}_i$ with $\mathcal{C}_i: \mathcal{M}_{D} \to \mathcal{M}_d$ where $\mathcal{C}_i = \Theta_{V_i} \circ \mathcal{C}$ and $\mathcal{D}_i: \mathcal{M}_{d} \to \mathcal{M}_D$ where $\mathcal{D}_i = \mathcal{D} \circ \Theta_{V_i^\ast}$. Therefore, it is easy to see that $(\mathcal{C}_i \otimes \id)(\dyad{\Omega})$ has Schmidt number at most $d$. Embedding $\mathcal{M}_d \hookrightarrow \mathcal{M}_D$, we can regard $\mathcal{D}_i$ as a map from $\mathcal{M}_D$ to itself. Since it only acts on one part of the bipartite system, $\mathcal{D}_i \otimes \id$ is a local operation. It is well known that such operations cannot increase the Schmidt number \cite[Proposition 1]{Terhal2000}. Hence, $(\mathcal{T}_i \otimes \id)(\dyad{\Omega})$ has Schmidt number at most $d$ and the same holds for $(\mathcal{T} \otimes \id)(\dyad{\Omega})$. An alternative way to see this is to note that the Kraus operators of $\mathcal{C}_i$ and $\mathcal{D}_i$ give a decomposition of $\mathcal{T}_i$ into Kraus operators of rank at most $d$.

Now consider 
\begin{equation*}
\SS_d = \Set{\dyad{\psi} \in \SS(\mathds{C}^D \otimes \mathds{C}^D):\Ket{\psi} \mathrm{~has~Schmidt~rank~} \leq d}.
\end{equation*}
The set of states on $\mathds{C}^D \otimes \mathds{C}^D$ with Schmidt number at most $d$ can then be written as the convex hull of $\SS_d$. By Carath{\'e}odory's theorem, for every $\rho \in \SS(\mathds{C}^D \otimes \mathds{C}^D)$ of Schmidt number at most $d$ there are $D^4$ elements of $\SS_d$ such that $\rho$ can be written as a convex combination of these elements. We only need $D^4$ instead of $D^4 + 1$ elements, since $\SS(\mathds{C}^D \otimes \mathds{C}^D)$ is contained in an affine subspace of dimension $D^4-1$. That means
\begin{equation*}
(\mathcal{T} \otimes \id)(\dyad{\Omega}) = \sum_{i = 1}^{D^4} p_i \dyad{\psi_i} \qquad \dyad{\psi_i} \in \SS_d,p_i \geq 0,\sum_{i = 1}^{D^4} p_i = 1.
\end{equation*}
Each $p_i \dyad{\psi_i}$ can be regarded as Choi matrix of a completely positive map $\widetilde{\mathcal{T}}_i$. We would like to decompose these maps into $\widetilde{\mathcal{C}}_i: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^{D^4}$, $\widetilde{\mathcal{D}}_i: \mathcal{M}_d \otimes \mathds{C}^{D^4} \to \mathcal{M}_D$, $\widetilde{\mathcal{T}}_i = \widetilde{\mathcal{D}}_i \circ \widetilde{\mathcal{C}}_i $. We note that since the Schmidt rank of $\Ket{\psi_i}$ is at most $d$, we can write it as 
\begin{equation*}
\Ket{\psi_i} = (X_i \otimes \idop) \Ket{\Omega} \qquad X_i \in \mathcal{M}_{D},
\end{equation*}
where $X_i$ has rank at most $d$. We can take e.g.\  $X_i = \sqrt{D\ptr{2}{\dyad{\psi_i}}}W$, where $W \in \mathcal{U}(D)$ and $\ptr{2}{\cdot}$ denotes the partial trace over the second system. Then we can find $A_i \in \mathcal{M}_{D,d}$, $B_i \in \mathcal{M}_{d,D}$ such that $X_i = A_i B_i$ \cite[Theorem 0.4.6 e)]{Horn2012}. For $A_i$ we can use the polar decomposition such that $A_i = R_i Q_i$ with $Q_i \in \mathcal{M}_d$, $Q_i \geq 0$ and $R_i \in \mathcal{M}_{D,d}$ such that $R_i$ has orthonormal columns, which means that $R_i$ is an isometry \cite[Theorem 7.3.1 c)]{Horn2012}. Choose $\widetilde{\mathcal{C}}_i: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^{D^4}$ as
\begin{equation*}
\widetilde{\mathcal{C}}_i := p_i \Theta_{(Q_i B_i)^\ast} \otimes \dyad{i}
\end{equation*}
  and $\widetilde{\mathcal{D}_i}: \mathcal{M}_d \otimes \mathds{C}^{D^4} \to \mathcal{M}_D$ as
\begin{equation*}
\widetilde{\mathcal{D}}_i := \Theta_{R_i^\ast}\otimes \ev{\cdot}{i}.
\end{equation*}  
Then we can define $\widetilde{\mathcal{C}} := \sum_{i = 1}^{D^4} \widetilde{\mathcal{C}}_i$ and $\widetilde{\mathcal{D}} := \sum_{i = 1}^{D^4} \widetilde{\mathcal{D}}_i$, where $\Set{\Ket{i}}_{i = 1}^{D^4}$ is an orthonormal basis of $\mathds{C}^{D^4}$. The maps $\widetilde{\mathcal{C}}$ and $\widetilde{\mathcal{D}}$ are CPTP with $\widetilde{\mathcal{D}}\circ \widetilde{\mathcal{C}} = \mathcal{T}$.
\end{proof}
Now we want to argue that taking the infimum over channels which arise from compression and decompression maps amounts to taking the infimum over a compact set. Define 
\begin{align*}
\mathcal{CH}_d :=& \{\mathcal{T}^\ast: \mathcal{M}_D \to \mathcal{M}_D| \mathcal{T} \mathrm{~CPTP~};  \exists \mathcal{C},\mathcal{D} \mathrm{~s.t.~} \mathcal{D} \circ \mathcal{C} = \mathcal{T},~\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^n,\\&~\mathcal{D}: \mathcal{M}_d \otimes \mathds{C}^n \to \mathcal{M}_D, n \in \mathds{N};~\mathcal{C}, \mathcal{D} \mathrm{~CPTP}\}\end{align*}
and 
\begin{align*}
\widetilde{\mathcal{CH}}_d :=& \{(\mathcal{C}^\ast, \mathcal{D}^\ast)| \mathcal{C}: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^{D^4}, ~\mathcal{D}: \mathcal{M}_d \otimes \mathds{C}^{D^4} \to \mathcal{M}_D;~\mathcal{C}, \mathcal{D} \mathrm{~CPTP}\}.
\end{align*}
\begin{lem} \label{lem:compactset}
$\widetilde{\mathcal{CH}}_d$ is a compact subset of the space $\mathcal{X} := \mathcal{B}(\mathcal{M}_d \otimes \mathds{C}^{D^4}, \mathcal{M}_D)\times \mathcal{B}(\mathcal{M}_D, \mathcal{M}_d \otimes \mathds{C}^{D^4})$ equipped with some norm $\norm{\cdot}_{\mathcal{X}}$. Here, $\mathcal{B}(\mathcal{H}, \mathcal{K})$ is the vector space of bounded linear operators from $\mathcal{H}$ to $\mathcal{K}$.
\end{lem}
\begin{proof}
Define 
\begin{equation*}
\mathcal{Y}_1: = \Set{\mathcal{D}^\ast: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^{D^4}: \mathcal{D} \mathrm{~CPTP}}.
\end{equation*}
This set is both closed and bounded (by the Russo-Dye theorem). Since $\mathcal{B}(\mathcal{M}_D,\mathcal{M}_d \otimes \mathds{C}^{D^4})$ is a finite-dimensional normed space, $\mathcal{Y}_1$ is compact. By the same reasoning,
\begin{equation*}
\mathcal{Y}_2: = \Set{\mathcal{C}^\ast: \mathcal{M}_d \otimes \mathds{C}^{D^4} \to \mathcal{M}_D: \mathcal{C} \mathrm{~CPTP}}
\end{equation*} 
is compact. It can easily be seen that $\widetilde{\mathcal{CH}}_d \simeq \mathcal{Y}_1 \times \mathcal{Y}_2$. Since products of compact sets are compact again in the product topology and all our spaces are finite dimensional, the assertion follows.
\end{proof}
Now we can finally prove the main result of this section.

\begin{proof}[Proof of \Fref{thm:inexactcase}]
Consider
\begin{equation*}
\epsilon_{d^\prime} := \inf_{\mathcal{T}^\ast \in \mathcal{CH}_{d^\prime}} \max_{E \in \mathcal{O}} \opnorm{E - \mathcal{T}^\ast(E)}.
\end{equation*}
By \Fref{lem:boundedsideinfo}, we can equivalently write 
\begin{equation} \label{eq:inf}
\epsilon_{d^\prime} := \inf_{(\mathcal{C}^\ast, \mathcal{D}^\ast) \in \widetilde{\mathcal{CH}}_{d^\prime}} \max_{E \in \mathcal{O}} \opnorm{E - (\mathcal{C}^\ast\circ \mathcal{D}^\ast)(E)}.
\end{equation}
In \Fref{lem:compactset}, we have shown that $\widetilde{\mathcal{CH}}_{d^\prime}$ is a compact set. Note that $\mathcal{R} \mapsto \max_{E \in \mathcal{O}} \opnorm{\mathcal{R}(E)}$ is a seminorm for any linear map $\mathcal{R}: \mathcal{M}_D \to \mathcal{M}_D$ and seminorms on finite-dimensional vector spaces are continuous. It is thus easy to see that $f:(\widetilde{\mathcal{CH}}_{d^\prime}, \norm{\cdot}_{\mathcal{X}}) \to \mathds{R}$, $f(\mathcal{C}^\ast, \mathcal{D}^\ast) = \max_{E \in \mathcal{O}} \opnorm{E - (\mathcal{C}^\ast\circ \mathcal{D}^\ast)(E)}$ is continuous.   Therefore, the infimum in \Fref{eq:inf} is attained  and we can write
\begin{equation*}
\epsilon_{d^\prime} := \min_{(\mathcal{C}^\ast, \mathcal{D}^\ast) \in \widetilde{\mathcal{CH}}_{d^\prime}} \max_{E \in \mathcal{O}} \opnorm{E - (\mathcal{C}^\ast\circ \mathcal{D}^\ast)(E)}.
\end{equation*}
Let $\epsilon := \min_{d^\prime \in [d-1]} \epsilon_{d^\prime}$.  As the compression dimension is $d$, we know that $\epsilon > 0$. This implies that for any $\mathcal{T}^\ast \in \mathcal{CH}_{d^\prime}$, ${d^\prime} \in [d-1]$, there is an $E \in \mathcal{O}$ such that
\begin{equation*}
\max_{\rho \in \SS(\mathds{C}^D)}|\tr{\rho E} - \tr{\mathcal{T}(\rho)E}| \geq \epsilon.
\end{equation*}

\end{proof}
\section{Lower bounds} \label{sec:lower}

\subsection{Algebraic arguments} \label{sec:arveson}


In this section, we will prove and discuss a lower bound on the compression dimension using techniques from operator algebras. This lower bound will depend on the structure of the algebra which is generated by the measurements we would like to perform. Note that any finite-dimensional C$^\ast$-subalgebra of $\mathcal{M}_D$ containing the identity has the form \cite[Theorem 5.6]{Farenick2001}
\begin{equation*}
U^\ast \left(\bigoplus_{i = 1}^s \mathcal{M}_{D_i} \otimes \idop_{m_i}\right) U
\end{equation*}
with $\sum_{i = 1}^s D_i m_i= D$, $U \in \mathcal{U}(D)$. The following theorem will be the main result of this section.

\begin{thm}[Operator algebraic lower bound on compression dimension]\label{thm:newarveson}
Let $\mathcal{O}\subset\mathcal{M}^\herm_D$ and \begin{equation*}
\cstar{\mathcal{O}} = U^\ast \left(\bigoplus_{i = 1}^s \mathcal{M}_{D_i} \otimes \idop_{m_i}\right) U,
\end{equation*}
where $\sum_{i = 1}^s D_i m_i= D$ and $U \in \mathcal{U}(D)$. Then $\min_{i \in [s]}D_i$ is a lower bound on the  compression dimension of $\mathcal{O}$. In particular, if $\cstar{\mathcal{O}}=\mathcal{M}_D$, then $\mathcal{O}$ is incompressible.
\end{thm}
The proof of this statement goes back to an idea of Arveson \cite[p. 288]{Arveson1972}. In his paper, he proved the following:
\begin{lem} \label{lem:Arvesonthm}
Let $\Phi$ be a unital completely positive map of a matrix algebra $\mathcal{M}_D$ onto itself whose fixed points algebraically generate the full matrix algebra. Then $\Phi$ is the identity map. 
\end{lem}
In Arveson's work, \Fref{lem:Arvesonthm} follows from a more general statement about boundary representations (cf.\  \cite[Theorem 2.1.1]{Arveson1972}). The proof of \Fref{thm:newarveson} uses Arveson's idea and extends it to more general situations, connecting it to the compression of quantum measurements. We start by proving a lemma which is essentially Lemma 1 on p.\ 285 f.\ in \cite{Arveson1972}. For this, we recall the definition of the support projection of a unital completely positive map. Let $\mathcal{R}$ be such a map on a matrix $\ast$-algebra $\mathcal{A}$. Then the support projection of $\mathcal{R}$ is the minimal orthogonal projection $P \in \mathcal{A}$ such that  $\mathcal{R}(P) = \idop$.  An equivalent definition as well as basic properties of the support projection can be found in the appendix (\Fref{lem:propsuppproj}).

\begin{lem} \label{lem:commsuppproj}
Let $\mathcal{R}$ be a unital completely positive linear map on a finite-dimensional C$^\ast  $-algebra $\mathcal{A} \subset \mathcal{M}_{D}$, $D \in \mathds{N}$, such that $\mathcal{R} \circ \mathcal{R} = \mathcal{R}$. Let $P$ be the support projection of $\mathcal{R}$. Then $P$ commutes with the fixed points of $\mathcal{R}$.
\end{lem}
\begin{proof}
Since for positive maps $\mathcal{R}(A)^\ast   = \mathcal{R}(A^\ast  )$ for all $A \in \mathcal{A}$, this implies that the set of fixed points is closed under involution. Thus, proving $PAP = AP$ for all fixed points $A$ is enough, since it implies $AP = PA$ for self-adjoint elements and arbitrary fixed points can be decomposed into self-adjoint components. It is even sufficient to prove $PA^\ast   PAP = PA^\ast   AP$, since for any vector $\Ket{\phi}\in \mathds{C}^D$ it holds that
\begin{align*}
\norm{(\idop - P) A P \Ket{\phi}}_2^2 &= \norm{AP\Ket{\phi}}_2^2 - \norm{PAP\Ket{\phi}}_2^2 \\ &= \ev{PA^\ast  AP}{ \phi} - \ev{PA^\ast   PAP}{\phi}.
\end{align*}
By the polarization identity, this extends to all matrix elements. For the first equality, we used that $\idop - P$ is an orthogonal projection. Now let $A \in \mathcal{A}$ be a fixed point of $\mathcal{R}$. Then $A^\ast  A \leq \mathcal{R}(A^\ast  PA)$ follows from the Schwarz inequality, $\mathcal{R}(A) = \mathcal{R}(PA)$ and from the fact that $A$ is a fixed point. Multiplying by $P$ from both sides and using $A^\ast  PA \leq A^\ast  A$, this gives 
\begin{equation} \label{eq:arvesonineq}
PA^\ast  PAP \leq PA^\ast  AP \leq P\mathcal{R}(A^\ast  PA)P
\end{equation}
This can be rewritten as $P\mathcal{R}(A^\ast  PA)P - PA^\ast  PAP \geq 0$. The support projection $P$ fulfills the equation
\begin{equation*}
\mathcal{R}(A) = \mathcal{R}(PAP) \qquad \forall A \in \mathcal{A}
\end{equation*}
and $\mathcal{R}|_{P\mathcal{A} P}$ is faithful, i.e.\ 
\begin{equation} \label{eq:faithfulsupport}
\mathcal{R}(A) = 0\quad \leftrightarrow\quad PAP = 0 \qquad \forall A \in \mathcal{A}_+.
\end{equation}
Here, $\mathcal{A}_+$ are the positive elements of the algebra. This implies that 
\begin{equation*}
P\mathcal{R}(A^\ast  PA)P - PA^\ast  PAP = 0.
\end{equation*}
holds since $\mathcal{R}$ was assumed to be idempotent. The statement then follows from \Fref{eq:arvesonineq}.
\end{proof}

We will also need a simple proposition which allows us to consider simpler algebras. From a physicist's point of view the $\ast$-isomorphism $\pi$ takes care of the right choice of measurement basis and the elimination of duplicate blocks in the structure of the operators in $\mathcal{O}$.

\begin{prop} \label{prop:simpleralgebra} Let $\mathcal{O} \subset \mathcal{M}_D^\herm$ be such that 
\begin{equation*}
\cstar{\mathcal{O}} = U^\ast \left(\bigoplus_{i = 1}^s \mathcal{M}_{D_i} \otimes \idop_{m_i}\right) U
\end{equation*}
with $\sum_{i = 1}^s D_i m_i= D$ and $U \in \mathcal{U}(D)$. Then there exist unital CP maps $\pi: \mathcal{M}_D \to \mathcal{M}_{\sum_{i = 1}^s D_i}$ and $\pi^{-1}:\mathcal{M}_{\sum_{i = 1}^s D_i} \to \mathcal{M}_D$ such that
\begin{equation*}
\pi(\cstar{\mathcal{O}}) = \bigoplus_{i = 1}^s \mathcal{M}_{D_i}=:\mathcal{A}.
\end{equation*}
and $\pi|_{\cstar{\mathcal{O}}}$ is a $\ast$-isomorphism with inverse $\pi^{-1}|_{\mathcal{A}}$. Moreover, $\mathcal{O}$ can be compressed to dimension $d$ if and only if $\pi(\mathcal{O})$ can be compressed to dimension $d$.
\end{prop}
\begin{proof}
Let $A \in \cstar{\mathcal{O}}$. Then it has the form
\begin{equation*}
A = U^\ast \left(\bigoplus_{i = 1}^s A_{i} \otimes \idop_{m_i}\right) U,
\end{equation*}
where $A_i \in \mathcal{M}_{D_i}$. It is easy to see that $\tilde{\pi}: \cstar{\mathcal{O}} \to \mathcal{A}$,
\begin{equation*}
\tilde{\pi}(A) = \bigoplus_{i = 1}^s A_{i},
\end{equation*}
is a $\ast$-isomorphism. Note that both $\tilde{\pi}$ and its inverse $\tilde{\pi}^{-1}$ are unital completely positive maps. Let $\mathcal{E}_1: \mathcal{M}_D \to \cstar{\mathcal{O}}$ and $\mathcal{E}_2: \mathcal{M}_{\sum_{i=1}^s D_i} \to \mathcal{A}$ be conditional expectations onto the respective subalgebras. These maps are known to be completely positive and unital. Then $\pi = \tilde{\pi} \circ \mathcal{E}_1$ and $\pi^{-1} = \tilde{\pi}^{-1} \circ \mathcal{E}_2$ are the desired maps. Let $\mathcal{C}^\ast: \mathcal{M}_d \otimes \mathds{C}^n \to \mathcal{M}_D $, $\mathcal{D}^\ast: \mathcal{M}_D \to \mathcal{M}_d \otimes \mathds{C}^n$ be a dual compression and decompression map for $\mathcal{O}$, respectively. For the constraints in \Fref{eq:constraint} to hold, $\mathcal{O}$ must be in the fixed point set of $\mathcal{T}^\ast = \mathcal{C}^\ast \circ \mathcal{D}^\ast$. Then $\pi \circ \mathcal{C}^\ast$ and $\mathcal{D}^\ast \circ \pi^{-1}$ are again dual channels and achieve compression to dimension $d$ for $\pi(\mathcal{O})$, because $\pi(\mathcal{O})$ is contained in the fixed point set for the composition of these maps. Conversely, let $\widetilde{\mathcal{C}}^\ast: \mathcal{M}_d \otimes \mathds{C}^n \to \mathcal{M}_{\sum_{i = 1}^s D_i}$, $\widetilde{\mathcal{D}}^\ast: \mathcal{M}_{\sum_{i = 1}^s D_i} \to \mathcal{M}_d \otimes \mathds{C}^n$ be a dual compression and decompression map for $\pi(\mathcal{O})$, respectively. Then by a similar argument, $\pi^{-1} \circ \widetilde{\mathcal{C}}^\ast$ and $\widetilde{\mathcal{D}}^\ast \circ \pi$ achieve compression to dimension $d$ for $\mathcal{O}$.
\end{proof}
With these preparations, we can prove the main result of this section.
\begin{proof}[Proof of \Fref{thm:newarveson}]

By \Fref{prop:simpleralgebra}, we can assume without loss of generality that the algebra is of the form $\bigoplus_{i = 1}^s \mathcal{M}_{D_i}$ for $\sum_{i = 1}^s D_i = D$, because $\cstar{\mathcal{O}}$ must be $\ast  $-isomorphic to such an algebra.  We already noted that for the constraints in \Fref{eq:constraint} to hold, $\mathcal{O}$ must be in the fixed point set of $\mathcal{T}^\ast = \mathcal{C}^\ast \circ \mathcal{D}^\ast$.

Now, we note that there is an idempotent map with the same fixed points as $\mathcal{T}^\ast$. We can for example consider the Ces\`aro-mean
\begin{equation*}
\mathcal{T}^\ast_\infty = \lim_{N \to \infty} \frac{1}{N}\sum_{n = 1}^N (\mathcal{T}^\ast)^n.
\end{equation*}
It is known that $\mathcal{T}^\ast_\infty$ has the same fixed points as $\mathcal{T}^\ast$, is unital, idempotent and also completely positive (cf.\  \Fref{lem:cesaro}). Moreover, $\mathcal{T}^\ast_\infty \circ \mathcal{T}^\ast = \mathcal{T}^\ast_\infty$ holds.  

Now we prove that 
\begin{equation*}
\mathcal{F} := \Set{A \in \mathcal{M}_D:  P\mathcal{T}^\ast(A)P =P AP; ~[P,A] = 0}
\end{equation*}
is a $\ast$-algebra, where $P$ is the support projection of $\mathcal{T}_\infty^\ast$. We note that $\mathcal{F}$ is an operator system as $\mathcal{T}^\ast_\infty$ is a unital positive linear map and that $P$ commutes with $\cstar{\mathcal{F}}$. Thus, we only need to show that $\mathcal{F}$ is closed under multiplication. Using the Schwarz inequality and the fact that $P$ is an orthogonal projection, it follows for $A \in \mathcal{F}$ that
\begin{align*}
PA^\ast  A P &= PA^\ast P  A P \\
&= P\mathcal{T}^\ast(A^\ast) P   \mathcal{T}^\ast(A)P \\
&\leq P\mathcal{T}^\ast(A^\ast)   \mathcal{T}^\ast(A)P \\
& \leq P\mathcal{T}^\ast(A^\ast  A)P.
\end{align*}
Hence, we see that
\begin{equation*}
P[\mathcal{T}^\ast(A^\ast  A) - A^\ast  A]P \geq 0.
\end{equation*}
Finally, we show that equality holds here. Applying $\mathcal{T}^\ast_\infty$ to this and using both $\mathcal{T}^\ast_\infty(PBP) = \mathcal{T}^\ast_\infty(B)$ for all $B \in \mathcal{M}_D$  and $\mathcal{T}^\ast_\infty \circ \mathcal{T}^\ast = \mathcal{T}^\ast_\infty$, we infer
\begin{equation*}
\mathcal{T}^\ast_\infty(P\left[\mathcal{T}^\ast(A^\ast  A) - A^\ast  A\right]P) = 0.
\end{equation*}
This implies by faithfulness of $\mathcal{T}^\ast_\infty|_{P \mathcal{M}_D P}$ that
\begin{equation*}
P \left[\mathcal{T}^\ast(A^\ast  A) - A^\ast  A\right] P = 0.
\end{equation*}
Thus, $A \in \mathcal{F}$ implies $A^\ast A \in \mathcal{F}$ and the fact that $\mathcal{F}$ is a $\ast$-algebra then follows from the polarization identity
\begin{align*}
B^\ast A =& \frac{1}{4} [(A + B)^\ast(A + B) - (A - B)^\ast(A - B) + \imI (A + \imI B)^\ast(A + \imI B) - \imI (A - \imI B)^\ast(A - \imI B) ].
\end{align*}


The second main ingredient of the proof is the fact that the support projection $P$ of $\mathcal{T}^\ast_\infty$ commutes with the fixed points of the map as shown in \Fref{lem:commsuppproj}. Then $P$ also commutes with every element of the C$^\ast  $-algebra generated by the fixed points of $\mathcal{T}^\ast$.
Thus, it commutes especially with $\cstar{\mathcal{O}}$. Therefore, $\cstar{\mathcal{O}} \subset \mathcal{F}$ and 
\begin{equation*}
P [\mathcal{T}(A) - A] P = 0 \qquad \forall A \in \cstar{\mathcal{O}}. 
\end{equation*}
We can now use the structure of $\cstar{\mathcal{O}}$. By Schur's lemma, we can conclude that
\begin{equation*}
P = \bigoplus_{i \in [s]} \chi_{\mathcal{I}}(i) \idop_{\mathcal{M}_{D_i}}
\end{equation*}
for some $\mathcal{I} \subset [s]$, where $\chi_\mathcal{I}$ is the indicator function of the set $\mathcal{I}$. Let $V_i: \mathds{C}^{D_i} \hookrightarrow \mathds{C}^D$  for $i \in [s]$ be an isometry such that $V_i V_i^\ast  $ is the projection onto the $i$-th block. As $\theta_{V_i^\ast}(B) \in \cstar{\mathcal{O}}$ for all $B \in \mathcal{M}_{D_i}$, we have shown that 
\begin{equation*}
(\Theta_{V_i} \circ \mathcal{T}^\ast   \circ \Theta_{V_i^\ast  })(A) = A \qquad \forall A \in \mathcal{M}_{D_i}, i \in \mathcal{I}.
\end{equation*}
Thus, $\Theta_{V_i} \circ \mathcal{T}^\ast   \circ \Theta_{V_i^\ast  } = \id$ $\forall i \in \mathcal{I}$ holds.
By the definition of the support projection, we infer further that 
\begin{equation*}
\mathcal{T}^\ast  _\infty((\idop - P) A) = \mathcal{T}^\ast  _\infty(A(\idop - P)) = 0
\end{equation*}
for all $A \in \mathcal{M}_D$, hence especially $0 \oplus \mathcal{M}_{D_i} \oplus 0 \in \ker{\mathcal{T}_\infty^\ast  }$ $\forall i \in [s] \setminus \mathcal{I}$. 

It could, however, be possible to enlarge the intermediate space, but to use classical side information to compress the quantum component of the system nonetheless. The following shows that this cannot happen. We identify the intermediate space $\mathcal{M}_d \otimes \mathds{C}^n$ with $\bigoplus_{i = 1}^n \mathcal{M}_d$. Let $Q_i$ be the orthogonal projection onto the $i$-th block, $i \in [n]$. Then 
\begin{equation*}
\mathcal{T}_{ij} = \Theta_{V_j^\ast}  \circ \mathcal{D} \circ \Theta_{Q_i} \circ \mathcal{C} \circ \Theta_{V_j} 
\end{equation*}
is again a completely positive map and $\sum_{i = 1}^n \mathcal{T}_{ij} = \id$ for every $j \in \mathcal{I}$. Looking at the Choi matrices for $\mathcal{T}_{ij}$, we can see that each needs to be proportional to $\dyad{\Omega}$, because each Choi matrix is positive semidefinite and their sum is a rank one projection. We infer that $\mathcal{T}_{ij}$ must be proportional to the identity channel, i.e.\  $\mathcal{T}_{ij} = p_i \id$, $p_i \geq 0$, $\sum_{i = 1}^n p_i = 1$. This is a well-known result in quantum information (no information without disturbance, see \cite[Section 5.2.2]{Heinosaari2012a}). From the rank-nullity theorem we conclude that $d \geq D_j$ for all $j \in \mathcal{I}$. As the set of fixed points of $\mathcal{T}^\ast  $ is non-empty, we know that $\mathcal{I}$ has to be non-empty as well. From there, the lower bound on $d$ follows.
\end{proof}
The following corollary follows immediately from the proof of \Fref{thm:newarveson}.
\begin{cor}[Fixed points of Schwarz maps]\label{cor:algsub}
Let $\mathcal{T}^\ast:\mathcal{M}_D\rightarrow\mathcal{M}_D$ be a Schwarz map and $\mathcal{O}$  a set of fixed points of $\mathcal{T}^\ast$ such that 
\begin{equation*}
\cstar{\mathcal{O}} = \bigoplus_{i = 1}^s \mathcal{M}_{D_i}
\end{equation*}
and $\sum_{i = 1}^s D_i = D$ and let $V_i: \mathds{C}^{D_i} \hookrightarrow \mathds{C}^D$ be an isometry such that $V_i V_i^\ast  $ is the projection onto the $i$-th block for $i \in [s]$.
Then there is an index set $\mathcal{I} \subset [s]$ such that $\Theta_{V_i} \circ \mathcal{T}^\ast   \circ \Theta_{V_i^\ast  } = \id$ for all $i \in \mathcal{I}$ and $0 \oplus \mathcal{M}_{D_i} \oplus 0 \in \ker{\mathcal{T}^\ast  _\infty}$ for all $i \in [s]\setminus \mathcal{I}$, where $\mathcal{T}^\ast  _\infty$ is the Ces\`aro-mean of $\mathcal{T}^\ast  $.  Moreover, $d \geq \max_{i \in \mathcal{I}}D_i$.
\end{cor} 



To conclude this section, we will prove that two matrices generically generate the full matrix algebra. This shows that a set of unstructured effect operators is typically incompressible.
More precisely, we show that the set of pairs of Hermitian matrices which do not generate the full matrix algebra has measure zero.
\begin{lem} \label{lem:matrixalgebrameasure1}
Let $\mathcal{N} = \Set{(A,B) \in \mathcal{M}_D^\herm \times \mathcal{M}_D^\herm: \cstar{\Set{A,B}} \subsetneq \mathcal{M}_D}$. Then the set $\mathcal{N}$ has Lebesgue measure zero on $\mathcal{M}_D^\herm \times \mathcal{M}_D^\herm$.
\end{lem}
\begin{proof}
By Burnside's theorem (cf.\  \cite{Lomonosov2004}), it is clear that $\mathcal{N}$ is contained in the set of tuples of matrices which have a non-trivial common invariant subspace. This requirement can be formulated as the zero set of a polynomial as we will see. From \cite[Theorem 2.2]{George1999}, we know that if $A$, $B \in \mathcal{M}^\herm_D$ have a common invariant subspace of dimension $k$, then also
\begin{equation*}
P_k(A,B) := \det[\sum_{i,j = 1}^{D-1} \comm{C_k(A)^i}{C_k(B)^j}^\ast   \comm{C_k(A)^i}{C_k(B)^j}] = 0 
\end{equation*}
where $C_k(A)$ is the $k$-th compound matrix of $A$, i.e.\  the matrix with entries $\det(A[\alpha|\beta])$ and $\alpha$, $\beta$ sequences of strictly increasing integers contained in $[n]$, $A[\alpha|\beta]$ the submatrix of $A$ in rows $\alpha$ and columns $\beta$. The entries of $C_k(A)$ are arranged in lexicographical order.
Multiplying the $P_k$, we obtain a polynomial $P := \prod_{k = 1}^{n-1} P_k$ in the real and imaginary parts of the entries of $A$, $B$ which contains $\mathcal{N}$ in its zero set. Since $P$ is not identically zero, its zero set and therefore $\mathcal{N}$ must have measure zero.
\end{proof}
We could also consider $\mathcal{M}_D$ instead of $\mathcal{M}_D^\herm$ and the statement would still hold. However, in the setting of (operator systems generated by) quantum observables, assuming the matrices involved to be Hermitian is more natural. 


\subsection{Geometric arguments} \label{sec:geoargument}

To give a different perspective on the problem, we will prove in this section again that compression in the setup of \Fref{sec:setup} is impossible in general, this time using basic techniques from algebraic geometry. This will be useful later to obtain results in situations in which we cannot apply the techniques of \Fref{sec:arveson} (see \Fref{sec:copies}). We emphasize again that we are interested in irreducibility over the reals. The following lemma is the main technical result of this section.
\begin{lem} \label{lem:nosmalleropnorm}
Let $A$, $B \in \mathcal{M}_D^\herm$ such that $p(x, z) := \det[x\idop - A - zB]$ is a polynomial of degree $D$ with a decomposition into irreducible factors
\begin{equation*}
p(x,z) = \prod_{i =1}^s p_i(x,z)^{m_i} \qquad m_i \in \mathds{N},
\end{equation*}
where $\deg p_i = D_i$ and $\sum_{i = 1}^s m_i D_i = D$.  Moreover, let $W \subset \mathds{R}$ be open and non-empty and let $C$, $F \in \mathcal{M}^\herm_d$ be such that 
\begin{equation*}
\opnorm{C + t F} = \opnorm{A + t B} \qquad \forall t \in W.
\end{equation*}
Then this implies that $d \geq \min_{i \in [s]}D_i$. 
\end{lem}
From this statement follows in particular that  $d \geq D$ if $p(x,z)$ is an irreducible polynomial. This lemma can be used to prove lower bounds on the compression dimension. 

\begin{thm}[Lower bound on compression dimension (geometric)]\label{thm:geometric}
Let $\mathcal{O} \subset \mathcal{M}_D^\herm$ be a set of Hermitian operators, $E_1$, $E_2 \in \mathcal{L}(\mathcal{O})$ and 
\begin{equation*}
p(x,z):=\det[x \idop - E_1 - z E_2].
\end{equation*}
Then the smallest among the degrees of the irreducible factors of $p$ is a lower bound on the compression dimension of $\mathcal{O}$. In particular, if $p$ is irreducible over the reals, then $\mathcal{O}$ is incompressible.
\end{thm}

\begin{proof}
First, we have that $\mathcal{T}^\ast$ is a contraction by the Russo-Dye theorem, since $\mathcal{T}^\ast  $ is a positive unital map. The same is true for the dual channels $\mathcal{D}^\ast  $, $\mathcal{C}^\ast  $. If we require \Fref{eq:constraint} to hold, then $\mathcal{L}(\mathcal{O})$ has to be in the fixed point space of $\mathcal{T}^\ast  $ as seen before. By the fixed point property, the quantity $\opnorm{E_1 + t E_2}$ has to be preserved under $\mathcal{T}^\ast  $ for all $t \in \mathds{R}$. Here, we have taken the modulus and then the maximum over all states in \Fref{eq:constraint}. Since  both $\mathcal{C}^\ast$ and $\mathcal{D}^\ast$ are contractions as well, this implies that 
\begin{equation*} 
\opnorm{E_1 + t E_2} = \opnorm{\mathcal{D}^\ast  (E_1) + t \mathcal{D}^\ast  (E_2)} \qquad \forall t \in \mathds{R}.
\end{equation*}
The assertion then follows from \Fref{lem:nosmalleropnorm}.
\end{proof}

In fact, we can strengthen  \Fref{thm:geometric} in the case when $\cstar{\mathcal{O}}$ is a proper subalgebra and we have more information on its block structure. This is captured by the next corollary.


\begin{cor}
Let $\mathcal{O} \subset \mathcal{M}_D^\herm$ be such that
\begin{equation*}
\cstar{\mathcal{O}} = U^\ast\left(\bigoplus_{i = 1}^s \mathcal{M}_{D_i} \otimes \idop_{m_i}\right) U
\end{equation*}
with $\sum_{i = 1}^s D_i m_i = D$ and $U \in \mathcal{U}(D)$. Then the minimal compression dimension is lower bounded by $D_{j_0}$ if there are $E_1$, $E_2 \in \mathcal{O}$, $j_0 \in [s]$ and an open set $V \subset \mathds{R}$ such that 
\begin{equation*}
\opnorm{E_1 + t E_2} = \|E_1^{j_0}+ t E_2^{j_0}\|_{\infty}
\end{equation*}
for all $t \in V$ and $E_1^{j_0}$, $E_2^{j_0}$ are such that 
$\det[x \idop - E_1^{j_0} - z E_2^{j_0}]$
is irreducible over the reals.
Here, we have used that for all $E \in \mathcal{O}$ we can write 
\begin{equation*}
E = U^\ast \left(\bigoplus_{j = 1}^s E^j \otimes \idop_{m_j} \right)U
\end{equation*}
for $E^j  \in \mathcal{M}_{D_j}$, $j \in [s]$.
\end{cor}

\begin{proof}
As in the proof of \Fref{thm:geometric}, we obtain
\begin{equation} \label{eq:opnormconstraint}
\opnorm{E_1 + t E_2} = \opnorm{\mathcal{D}^\ast  (E_1) + t \mathcal{D}^\ast  (E_2)} \qquad \forall t \in \mathds{R}.
\end{equation}
The definition of $\mathcal{D}$ requires \begin{equation*}
\mathcal{D}^\ast  (\mathcal{L}(\Set{E_1, E_2})) \subset \bigoplus_{i = 1}^n \mathcal{M}_{d} \simeq \mathcal{M}_d \otimes \mathds{C}^n.
\end{equation*}
Assume therefore that $\mathcal{D}^\ast  (E_1) + t \mathcal{D}^\ast  (E_2) = \bigoplus_{i = 1}^n \left(F_1^i + t F_2^i\right)$, $F_j^i \in \mathcal{M}_{d}$ for all $i \in [n]$, $j \in [2]$ and $t \in \mathds{R}$. Since 
\begin{equation*}
\opnorm{\mathcal{D}^\ast  (E_1) + t \mathcal{D}^\ast  (E_2)} = \max_{i \in [n]}\opnorm{F^i_1 + t F^i_2}
\end{equation*}
for a fixed $t$, we can assume that there is an open set $W \subset V$ such that 
\begin{equation} \label{eq:relevantblock}
\opnorm{\mathcal{D}^\ast  (E_1) + s \mathcal{D}^\ast  (E_2)} = \opnorm{F^{k_0}_1 + s F^{k_0}_2} \qquad \forall s \in W
\end{equation}
for some $k_0 \in [n]$. This is true since for two blocks either 
\begin{equation*}
\opnorm{F^{1}_1 + t F^{1}_2} = \opnorm{F^{2}_1 + t F^{2}_2}
\end{equation*}
for all $t \in V$ or there is a $t_0 \in V$ such that 
\begin{equation*}
\opnorm{F^{1}_1 + t_0 F^{1}_2} > \opnorm{F^{2}_1 + t_0 F^{2}_2}.
\end{equation*}
In the latter case, we can find an open neighborhood $W$ of $t_0$ such that
\begin{equation*}
\opnorm{F^{1}_1 + t_0 F^{1}_2} > \opnorm{F^{2}_1 + t_0 F^{2}_2}
\end{equation*}
for all $t \in W$ by continuity of the operator norm with respect to $t$. This can be extended to more blocks by induction in the block number and possibly further shrinking $W$.

By assumption, \Fref{eq:opnormconstraint} and \Fref{eq:relevantblock} then imply
\begin{equation*}
\opnorm{E_1^{j_0}+ t E_2^{j_0}} = \opnorm{F^{k_0}_1 + t F^{k_0}_2} \qquad \forall t \in W
\end{equation*}
The assertion $d \geq D_{j_0}$ then follows from \Fref{lem:nosmalleropnorm}.
\end{proof}

The condition
$\opnorm{E_1 + t E_2} = \|E_1^{j_0}+ t E_2^{j_0}\|_{\infty}$
might look artificial, but can easily be checked. We just have to find a $t_0 \in \mathds{R}$ which is not a crossing point and check which block has the largest operator norm in some open neighborhood of $t_0$. If furthermore $\mathrm{det}[x \idop - E_1^{j_0} - z E_2^{j_0}]$ is irreducible (this might be hard to check), we can apply the above corollary to find a lower bound on $d$. Note that the condition also implies that the $j_0$-th block is not redundant (cf.\  discussion in \Fref{sec:computing}), since \Fref{lem:nosmalleropnorm} guarantees that smaller blocks have smaller operator norm for some $t \in U$. By contractivity, it then follows that there is no unital completely positive map $\Phi: \mathcal{M}_{\sum_{j = 1}^s D_j} \to \mathcal{M}_{D_{j_0}}$ such that
\begin{equation*}
E_k^{j_0} = \Phi\left(\bigoplus_{i = 1}^s \chi_\mathcal{I}(i)E_k^{i}\right) \qquad \forall k \in [2]
\end{equation*} 
and $\mathcal{I}$ such that $D_i < D_{j_0}$ $\forall i \in \mathcal{I}$ and $\chi_\mathcal{I}$ is the indicator function of $\mathcal{I}$. We still have to prove \Fref{lem:nosmalleropnorm}, which we will do now.

\begin{proof}[Proof of \Fref{lem:nosmalleropnorm}]
First note that $A + t B$ has only real eigenvalues for $t \in \mathds{R}$. Thus, for any fixed $t$, the characteristic polynomial has $D$ real solutions counting multiplicities. Without loss of generality, let $U \subset W$ be a non-empty open set such that $\opnorm{A + t B}$ is the maximal eigenvalue $\lambda_{max}(t)$ of $A + t B$ for all $t \in U$ and the same holds for $C + t F$. We denote the maximal eigenvalue of the latter matrix by $\mu_{max}(t)$. This is possible,
since there are only finitely many level crossings in any finite interval (cf.\  \cite[p.124]{Kato1966}). Moreover, if the minimal eigenvalue of $A + t B$ has larger modulus, we can consider $-(A + t B)$ instead which clearly has the same operator norm and the same is possible for $C + t F$. Then 
\begin{equation*}
V := \Set{(x,z) : x = \lambda_{max}(z), z \in U}
\end{equation*}
is a subset of $\mathcal{Z}(p)$ with infinitely many points since $U$ is open in $\mathds{R}$. Let 
\begin{equation*}
q(x,z) := \det[x\idop - C - z D]
\end{equation*}
which is a polynomial of degree $d$. Assume $d < D_i$ for all $i \in [s]$. Since the $p_i$ are irreducible by assumption, $p_i$ and $q$ have no common factors for any $i \in [s]$. Therefore, by B\'ezout's theorem and since 
\begin{equation*}
\mathcal{Z}(p)\cap\mathcal{Z}(q) = \bigcup_{i \in [s]} (\mathcal{Z}(p_i)\cap \mathcal{Z}(q)),
\end{equation*}
the zero sets of the two polynomials have at most $\sum_{i = 1}^s d \cdot D_i$ points in common (cf.\  \Fref{lem:realbezout}). Thus, $\mathcal{Z}(q)$ especially cannot contain $V$, which implies $\opnorm{A + t B} \neq \opnorm{C + t F}$ for infinitely many $t \in U$, since 
\begin{equation*}
\Set{(x,z): x=\mu_{max}(z), z \in U} \subset \mathcal{Z}(q).
\end{equation*} 
\end{proof}
Let us make the following remark concerning our use of B{\'e}zout's theorem. Commonly, the theorem is formulated as an equality (counting multiplicities) over an algebraically closed field such as $\mathds{C}$. Since real polynomials are coprime over the reals if and only if they are coprime over the complex numbers (cf.\  \cite[Theorem 11.9]{Bix2006}), the complex version of B{\'e}zout's theorem implies an upper bound on the number of intersections of real coprime polynomials over the reals which we used here (cf.\  \cite[Theorem 11.10]{Bix2006}).

The last question we have to answer in this section is the existence of irreducible polynomials of any degree which arise from a determinant of $D \times D$ matrices. We would also like to know how common these are. This will also show that there are effect operators which give rise to irreducible polynomials. For this, we do not require the matrices $A$, $B \in \mathcal{M}_D^\herm$ to be positive, because we can convert them into effect operators. For any $A \in \mathcal{M}_D^\herm$ there is a $\lambda \in \mathds{R}$ such that $A + \lambda \idop \geq 0$ and we can scale this expression by a positive scalar such that it becomes smaller than the identity operator. This way, we can find non-zero effect operators $E_1$, $E_2$ such that $A, B \in \mathcal{L}(\Set{E_1, E_2})$ and $E_1$, $E_2$ are fixed points if and only if $A$, $B$ are. Furthermore, $\det[x \idop - E_1 - z E_2]$ is irreducible if and only if $\det[x \idop - A - z B]$ is irreducible for linearly independent $A$, $B \in \mathcal{L}(\Set{E_1, E_2})$, since a (non-singular) coordinate transformation does not change reducibility properties of the polynomial (cf.\  \cite[discussion before Theorem 4.5]{Bix2006}). The key ingredient to show existence of the required polynomials is the Lax conjecture which was proven in \cite[Conjecture 4]{Lewis2005}. We give it here for convenience.
\begin{thm}[Lax conjecture]
A polynomial $p \in \bfH^D(3)$ is hyperbolic with respect to the vector $e := (1,0,0)$ and satisfies $p(e) = 1$ if and only if there exist matrices $A,B \in \mathcal{M}_D^\sym$ such that $p$ is given by
\begin{equation*}
p(x,y,z) = \det\left[ x\idop + y A + z B\right].
\end{equation*}
\end{thm}
The result that $A$, $B$ can be chosen real symmetric is even stronger than needed for our purposes.

\begin{lem} \label{lem:exirredpoly}
For any $D \in \mathds{N}$, there is an irreducible homogeneous polynomial and $A$, $B \in \mathcal{M}_D^\sym$ such that 
\begin{equation*}
p(x,y,z) = \det[x \idop + y A + z B].
\end{equation*}
Moreover, these elements are generic in the set of homogeneous polynomials normalized to $p(e) = 1$ for $e := (1, 0, 0)$.
\end{lem}
\begin{proof}

By the Lax conjecture, it suffices to show that there are homogeneous polynomials of any degree which are both hyperbolic with respect to $e$ and irreducible. The case $D = 1$ is trivial, since there are no reducible elements and all polynomials are hyperbolic.
Hence, assume $D > 1$. It is known that the set of reducible elements in this case does not contain any open subset in the Euclidean topology (see \Fref{lem:reduciblenoopensets} for a proof). Since the set of hyperbolic polynomials with respect to a fixed point $e$ has non-empty interior in this topology by \cite{Nuij1968} (cf.\  \Fref{sec:polyappendix} to see that this is not affected by normalization), it especially contains an open set, hence it cannot be fully contained in the set of reducible elements. Therefore, there must be elements which are both hyperbolic and irreducible. \Fref{lem:reduciblenoopensets} also states that the set of normalized reducible polynomials has measure zero, hence its intersection with the set of normalized hyperbolic polynomials has measure zero as well.
\end{proof}

\Fref{thm:geometric} states that compression is not possible if the polynomial
\begin{equation} \label{eq:detrep}
p(x,y,z) = \det[x\idop - y A - z B]
\end{equation}
is irreducible, where $A$, $B \in \mathcal{L}(\Set{E_1, E_2})$. \Fref{lem:exirredpoly} therefore implies that effect operators which cannot be compressed are the generic case, i.e.\  the set of $p(x,y,z)$ corresponding to effect operators which admit compression has Lebesgue measure zero in the space of normalized homogeneous polynomials in 3 variables of fixed degree $D$. This follows because $p$ has to be hyperbolic to admit a determinantal representation as in \Fref{eq:detrep}, even if we allow for Hermitian matrices. Furthermore, $p$ needs to be reducible to possibly admit a compression by the above. Unfortunately, irreducibility over the reals is difficult to check.

So far, we have only shown existence of such $p(x,y,z)$. We can also give an explicit example of such a polynomial in every dimension (with Hermitian matrices). 

\begin{prop} \label{prop:irredexample}
Let 
\begin{equation*}
A := \frac{1}{2}\begin{bmatrix}
0 & 1 & \ldots & 1 \\
1 & \ddots & & \vdots\\
\vdots & & \ddots & 1\\
1 & \ldots & 1 & 0
\end{bmatrix}, 
\qquad 
B := \frac{1}{2}\begin{bmatrix}
0 & \imI & \ldots & \imI \\
-\imI & \ddots & & \vdots\\
\vdots & & \ddots & \imI\\
-\imI & \ldots & -\imI & 0
\end{bmatrix},
\end{equation*}
$A$, $B \in \mathcal{M}_D$, $D \geq 1$. Then the polynomial $p(x,z) := \det[x\idop + A + z B]$ is irreducible.
\end{prop}

\begin{proof}
$D = 1$ is trivial, thus assume $D \geq 2$. Reparameterizing with $\tilde{z} := z - \imI$, we obtain
\begin{equation*}
\tilde{p}(x, \tilde{z}) := \det[\tilde{A}(x) + \tilde{z} B]
\end{equation*}
with
\begin{equation*}
\tilde{A}(x) := \begin{bmatrix}
x & 0 & \ldots & 0 \\
1 & \ddots & & \vdots\\
\vdots & & \ddots & 0\\
1 & \ldots & 1 & x
\end{bmatrix}.
\end{equation*}
We know that $\tilde{p}(x,0) = x^D$. In order to prove that $\tilde{p}$ is irreducible, we show first that it cannot be decomposed as $\tilde{p} = q \cdot r$ with $q$, $r \in \mathds{C}[x,\tilde{z}]$ with $q(0,0) = 0 = r(0,0)$. Since the constant terms of both $q$ and $r$ must be zero, the expansion of $\tilde{p}(x,\epsilon)$ to first order in $\epsilon$ would have at least one root $x = 0$ if such a decomposition existed (cf.\  \Fref{lem:constantzero}). We can expand 
\begin{equation*}
\tilde{p}(x,\epsilon) := x^D - \frac{\epsilon \imI}{2} \left[D x^{D-1} + (x-1)^D - x^D\right] + \mathcal{O}(|\epsilon|^2),
\end{equation*}
(cf.\  \Fref{lem:detexpansion}). However, 
\begin{equation*}
\tilde{p}(0,\epsilon) = (-1)^{D+1} \epsilon \imI/2 + \mathcal{O}(|\epsilon|^2),
\end{equation*}
i.e.\  the term linear in $\epsilon$ does not vanish. Therefore, without loss of generality, $r(0,0)$ is non-zero. This implies that $r$ is constant, since $x$ cannot divide $r(x,0)$, which implies that $q(x,0)$ must have degree $D$, and $\tilde{p}$ is of degree $D$. Thus, $\tilde{p}$ is irreducible (even over the complex numbers) and hence the same holds for $p$.
\end{proof}

\subsection{Comparing the arguments}

Before we continue, let us compare the two techniques used to prove that compression is not possible in general. We will see that the algebraic method shows incompressibility for a larger class of effect operators. However, we will see in \Fref{sec:copies} that the geometric argument can be used in situations where the algebraic argument is not applicable.

If $\cstar{\mathcal{O}}$ is only a subalgebra of $\mathcal{M}_D$, then $\mathcal{L}(\mathcal{O}) \subset U^\ast (\mathcal{M}_{D_1} \oplus \mathcal{M}_{D_2})U  $, with $D_1$, $D_2 \in \mathds{N}$ and $D_1 + D_2 = D$. Let $A$, $B \in \mathcal{L}(\mathcal{O})$. By the above, they have the form $A = U^\ast(A_1 \oplus A_2) U$, $B = U^\ast (B_1 \oplus B_2)U$ with $A_i$, $B_i \in \mathcal{M}_{D_i}$, $i \in [2]$.  Hence, 
\begin{align*}
\det[x \idop -  A - z B]& = \det[x \idop_{D_1} -  A_1 - z B_1] \det[x \idop_{D_2} -  A_2 - z B_2]\\
& = p_1(x,z) p_2(x,z) 
\end{align*}
with $p_1$, $p_2$ real polynomials of degree strictly less than $D$. Therefore, we know that $\cstar{\mathcal{O}} \subsetneq \mathcal{M}_D$ implies that $\det[x \idop - A - z B]$ for $A$, $B \in \mathcal{L}(\mathcal{O})$ is not irreducible over the reals. We could suppose that also the converse holds, namely that for $A$, $B$ such that the above determinant is a reducible polynomial, $\cstar{\Set{A, B}}$ must be a proper subalgebra of $\mathcal{M}_D$ (note that the C$^{\ast  }$-algebra does not depend on which generators were used as long as $\mathcal{L}(\Set{A,B}) = \mathcal{L}(\mathcal{O})$). Alas, this is not the case, as the following counterexample shows:
\begin{ex}
Let $p \in \bfH^3(3)$ be defined as 
\begin{equation*}
p(x,y,z) := (x- 1/2y)(x^2 - y^2 - z^2).
\end{equation*}
This is clearly reducible over the reals. However, $p$ admits a monic determinantal representation
\begin{equation*}
p(x,y,z) = \det[x\idop + y A + z B]
\end{equation*}
such that $\cstar{\Set{A, B}} = \mathcal{M}_3$.
\end{ex}
\begin{proof}
By unitary invariance of the determinant, we can assume that $A$ is diagonal. It is easy to verify that $p(x,y,z)$ is hyperbolic with respect to $(1,0,0)$ and that $p(1,0,0) = 1$, such that we can choose $A$ to be real (cf.\  \cite{Lewis2005}). We can therefore compare coefficients directly and solve a system of equations for the matrix coefficients which is reasonably small. One possible determinantal representation is given by
\begin{equation*}
A = \begin{bmatrix}
-1 & & \\
& -1/2 & \\
& & ~1
\end{bmatrix} \qquad B = \begin{bmatrix}
0 & -1/2 & 0 \\
-1/2 & 0 & -\sqrt{3}/2 \\
0 & - \sqrt{3}/2 & 0
\end{bmatrix}.
\end{equation*}
The matrix $B$ has eigenvalues $-1$, $1$, $0$ with corresponding eigenvectors $(1, 2, \sqrt{3})$, $(1, -2, \sqrt{3})$ and $(-\sqrt{3}, 0, 1)$. Note that both matrices have non-degenerate spectrum. By Burnside's theorem (cf.\  \cite{Lomonosov2004} for the exact statement and a simple proof), the generators of any proper subalgebra of $\mathcal{M}_D$ must have a common invariant subspace other than $0$ or $\mathds{C}^D$. Since the eigenvectors of $A$ and $B$ are pairwise linearly independent, there are no common invariant subspaces of dimension one. As only the eigenvector of $B$ corresponding to eigenvalue $0$ is in any of the two-dimensional subspaces spanned by the pairs of eigenvectors of $A$, there are no common two-dimensional invariant subspaces, either. By Burnside's theorem thus $\cstar{\Set{A,B}} = \mathcal{M}_3$.
\end{proof}
Note that from \cite{Vinnikov1989}, we know that the determinantal representation of (irreducible smooth) algebraic curves of degree $2$ is unique up to equivalence, whereas in degree $3$, there are infinitely many (not-necessarily real symmetric) determinantal representations. Hence, it was natural to look for counterexamples of this degree.



\section{Upper bounds} \label{sec:upper}

\subsection{Compression to maximal block size}

We will show now that using classical side information we can at least compress to the dimension of the largest block. Note that the proof of the lemma yields explicit coding and decoding channels. 
\begin{thm}[Upper bound on the compression dimension] \label{thm:blockcompression}
Let $\mathcal{O} \subset \mathcal{M}_D^\herm$ be such that
\begin{equation} \label{eq:originalalgebra}
\cstar{\mathcal{O}} = U^\ast \left(\bigoplus_{i = 1}^s \mathcal{M}_{D_i} \otimes \idop_{m_i}\right) U
\end{equation}
where $\sum_{i = 1}^s D_i m_i= D$ and $U \in \mathcal{U}(D)$.  Then $\max_{j \in [s]}D_j$ is an upper bound on the minimal compression dimension.
\end{thm}
\begin{proof}
By \Fref{prop:simpleralgebra}, we can assume that
\begin{equation*}
\cstar{\mathcal{O}} = \bigoplus_{i = 1}^s \mathcal{M}_{D_i}
\end{equation*}
with $\sum_{i = 1}^s D_i = D$. Without loss of generality, let $D_1 \geq D_j$ $\forall j \in [s]$. Let $V_j: \mathds{C}^{D_j} \hookrightarrow \mathds{C}^D$ be an isometry such that $V_jV_j^\ast   = P_j$ is the projection onto the $j$-th block. In the same vein, let $W_j: \mathds{C}^{D_j} \hookrightarrow \mathds{C}^{D_1}$ be an isometry such that $W_j W_j^\ast   = Q_j$ is the projection onto $M_{D_j}$, i.e.\  $Q_j = \idop_{D_j} \oplus 0$. We define $\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_{D_1}\otimes \mathds{C}^s$ as
\begin{equation} \label{eq:blockcompression}
\mathcal{C}(\rho) = \sum_{j = 1}^s W_j V_j^\ast   \rho V_j W_j^\ast   \otimes \dyad{j},
\end{equation}
where $\Set{\Ket{j}}_{j = 1}^s$ is an orthonormal basis of $\mathds{C}^s$. This map is obviously completely positive, since it is given in Kraus decomposition. It is also trace preserving, because
\begin{align*}
\tr{\mathcal{C}(\rho)} &= \sum_{j = 1}^s \tr{W_j V_j^\ast   \rho V_j W_j^\ast   \otimes \dyad{j}} \\
&= \sum_{j = 1}^s \tr{P_j \rho} = \tr{\rho}.
\end{align*}
For $\mathcal{D}$, it is easier to define the dual map. We will need the following maps $\mathcal{R}_j: \mathcal{M}_{D_j} \to \mathcal{M}_{D_1}$ given by
\begin{equation*}
A \mapsto A \oplus \tr{A \eta_j} \idop_{D_1 - D_j} \qquad \eta_j \in \SS(\mathds{C}^{D_j}).
\end{equation*}
The choice of $\eta_j$ is somewhat arbitrary and is needed to ensure linearity. This map is completely positive, since it is a composition of $A \mapsto A \otimes \idop_2$ and the direct sum of the identity map and the map $A \mapsto \tr{A\eta_j}\idop_{D_1 - D_j}$, all of which are completely positive and unital.
With this, we define the dual channel $\mathcal{D}^\ast  : \mathcal{M}_D \to \mathcal{M}_{D_1}\otimes \mathds{C}^s$ as
\begin{equation} \label{eq:blockdecompression}
A \mapsto \sum_{j = 1}^s \mathcal{R}_j(V_j^\ast   A V_j) \otimes \dyad{j}.
\end{equation}
This map is unital since $\mathcal{R}_j$ is. To show correctness, we need to verify that $\tr{\rho E} = \tr{\mathcal{C}(\rho) \mathcal{D}^\ast  (E) }$ for all $\rho \in \SS(\mathds{C}^D)$, $E \in \mathcal{O}$. We compute for such $\rho$, $E$
\begin{align*}
\tr{\mathcal{C}(\rho) \mathcal{D}^\ast  (E) } & = \sum_{j = 1}^s \tr{[V_j^\ast  \rho V_j V_j^\ast   E V_j] \oplus 0} \\
& = \sum_{j = 1}^s \tr{\rho P_j E P_j},
\end{align*}
where we used $W_j V_j^\ast \rho V_j  W_j^\ast = V_j^\ast \rho V_j \oplus 0$  in the first equation. The last line is equal to $\tr{\rho E}$ since $E$ is block diagonal.

To obtain compression and decompression maps for the original algebra $\cstar{\mathcal{O}}$ in \Fref{eq:originalalgebra}, we can use the $\ast$-isomorphism given in \Fref{prop:simpleralgebra} and define $\widetilde{\mathcal{D}}^\ast := \mathcal{D}^\ast \circ \pi$, $\widetilde{\mathcal{C}}^\ast := \pi^{-1} \circ \mathcal{C}^\ast$, where $\mathcal{C}$, $\mathcal{D}$ are the maps constructed above.
\end{proof}
We have given an explicit way to compress a subalgebra to the size of its largest block. So far, it is, however, unclear if compression to the largest block is indeed the best we can do or if $d$ can be chosen smaller. Before we will pursue this, we will apply the above theorem in two concrete situations. First, we prove that for $\dim \mathcal{L}(\mathcal{O}) < 3$, the set of effect operators $\mathcal{O}$ is trivially compressible.
\begin{prop}[Compression of a single binary measurement]
Let $\mathcal{O} = \Set{E, \idop - E}$ be a set of effect operators, where $E \in \mathcal{E}(\mathds{C}^D)$. Then the compression dimension is $1$.
\end{prop}
\begin{proof}
As $E$ is an effect operator, we can diagonalize $E$ to show that $\cstar{\mathcal{O}}$ is $\ast  $-isomorphic to $\bigoplus_{i = 1}^s\mathds{C}$, $s \leq D$. The assertion follows from \Fref{thm:blockcompression}.
\end{proof}
We will now continue to use \Fref{thm:blockcompression} to discuss the important example of two von Neumann measurements with two outcomes each.

\subsection{Compressibility for two binary von Neumann measurements} \label{sec:twoproj}

We have shown that compressibility strongly depends on the algebra generated by the desired effect operators. In this section, we will show that in the case of two  bipartite projective measurements, we can compress to qubits ($d = 2$) using classical side information. The idea is that two projections generate an algebra which has a block structure of $2 \times 2$-matrices. This will use a finite-dimensional version of Halmos' two projections theorem (cf.\  \cite[Theorem 2]{Halmos1969}, \cite[Theorem 1.1]{Boettcher2010}).

Suppose we are given two orthogonal projections $P$ and $Q$ acting on a $\mathds{C}^D$ with $\ran P = M$, $\ran Q = N$. Then $\mathds{C}^D$ can be decomposed as
\begin{equation*}
\mathds{C}^D = (M \cap N) \oplus (M\cap N^\bot) \oplus (M^\bot \cap N) \oplus (M^\bot \cap N^\bot) \oplus M_0 \oplus M_1
\end{equation*}
The spaces $M_0$ and $M_1$ are defined through the decomposition of $\mathds{C}^D$ into $M$ and $M^\bot$,
\begin{align*}
M &= (M \cap N) \oplus (M\cap N^\bot) \oplus M_0 \\
M^\bot &= (M^\bot \cap N) \oplus (M^\bot \cap N^\bot) \oplus M_1,
\end{align*}
and their dimensions have to agree in order for them to be non-empty. We will use the abbreviation 
\begin{equation*}
(\alpha_1, \alpha_2, \alpha_3, \alpha_4) = \alpha_1 \idop_{M \cap N} \oplus \alpha_2 \idop_{M \cap N^\bot} \oplus \alpha_3 \idop_{M^\bot \cap N} \oplus \alpha_4 \idop_{M^\bot \cap N^\bot}.
\end{equation*}
If one of these subspaces is $\set{0}$, we will just ignore this contribution irrespective of $\alpha_j$. Note that this is the generic case. With this, we have the following theorem which is \cite[Corollary 2.2]{Boettcher2010}:

\begin{lem}\label{lem:twoproj}
If one of the spaces $M_0$ and $M_1$ is nontrivial, then these two spaces have the same dimension $r \in \mathds{N}$ and there exists a unitary matrix $V \in \mathcal{M}_D$ such that 
\begin{align*}
VPV^\ast   &= (1,1,0,0) \oplus \diag \begin{bmatrix} 1 & 0 \\0 & 0 \end{bmatrix}_{j = 1}^r, \\
VQV^\ast   &= (1,0,1,0) \oplus \diag\begin{bmatrix} 1-\mu_j & \sqrt{\mu_j(1-\mu_j)}\\\sqrt{\mu_j(1-\mu_j)} & \mu_j  \end{bmatrix}_{j = 1}^r,
\end{align*}
where $0 \leq \mu_j \leq 1$ for all $j \in [r]$.
\end{lem}
This theorem is attributed to \cite[Section 2]{Wedin1983}, but similar questions concerning pairs of projections have already been studied by Camille Jordan in the 19th century. See \cite[Remark 1.3]{Boettcher2010} for a discussion of related results. Thus, the algebra generated by two projections and the identity operator consists essentially of block diagonal matrices with $2 \times 2$-blocks. For three projections, such a form can no longer be proven, since there are cases in which three projections generate the full matrix algebra (cf.\  concluding remarks of \cite{Boettcher2010}). Hence, we cannot guarantee compression to be possible for more than two bipartite von Neumann measurements.

\begin{prop}[Compression of two binary projective measurements]
Let $\mathcal{O} = \{P, \idop - P, Q, \idop - Q\}\subset \mathcal{M}_D$ be a set of effect operators and $P$, $Q$ two distinct orthogonal projections. Then the compression dimension for the set of these effect operators is upper bounded by $d = 2$.
\end{prop}

\begin{proof}
Let $P$, $Q \in \mathcal{M}_D$ be two distinct orthogonal projections. \Fref{lem:twoproj} provides a unitary operator $V$ such that
\begin{align*}
Q &= V^\ast   ((1,1,0,0) \oplus Q_5 \oplus \ldots \oplus Q_k) V, \\
P &= V^\ast   ((1,0,1,0)\oplus P_5 \oplus \ldots \oplus P_k) V, 
\end{align*}
where $Q_i$, $P_j \in \mathcal{M}_2$ for $i$, $j \in \Set{5, \ldots, k}$.
We are therefore in the situation of \Fref{thm:blockcompression} with $D_i = 1$ for $i \in [4]$ and $D_j = 2$ for $j \in [k] \setminus [4]$ (identifying $\Set{(\alpha_1, \ldots, \alpha_4): \alpha_i \in \mathds{C}, i \in [4]}$ with $\mathds{C}^4$, thus eliminating redundancies). \Fref{thm:blockcompression} gives us a coding map $\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_2 \otimes \mathds{C}^k$ and a decoding map $\mathcal{D}: \mathcal{M}_2 \otimes \mathds{C}^k \to \mathcal{M}_D$ which satisfies the constraints in \Fref{eq:constraint}.
\end{proof}

\section{Computing the compression dimension} \label{sec:computing}

Hitherto, we have only seen that the dimension of the largest block is attainable for compression (\Fref{thm:blockcompression}), whereas the dimension of the smallest block is a lower bound on the compression dimension (\Fref{thm:newarveson}), which is not necessarily attainable. In this section, we give an algorithm which allows us to compute the minimal dimension we can compress to using classical side information. We will assume that the operators in $\mathcal{O}$ are already given in block diagonal form. Whether two given Hermitian operators have a common block diagonal structure can be checked using the algorithm in \cite[Section 4]{George1999}. Algorithms to bring a finite-dimensional C$^\ast  $-algebra into block diagonal form can be found e.g.\  in \cite{Murota2010}. We analyze the latter algorithm in \Fref{sec:complexity}. Assume that we are given a set of Hermitian operators $\mathcal{O}$. By \Fref{prop:simpleralgebra}, we can assume that $\cstar{\mathcal{O}} = \bigoplus_{i = 1}^s \mathcal{M}_{D_i}$ with $\sum_{i = 1}^s D_i = D$. The question of finding the minimal dimension which we can compress to amounts to determining which blocks are redundant, as will be proven below (cf.\  \Fref{thm:algorithmcorrect}). Let us define what we mean by redundant. 
\begin{defi}[Redundancy]
Let $\mathcal{O} \subset \mathcal{M}_D^\herm$ be such that 
\begin{equation*}
\cstar{\mathcal{O}} = \bigoplus_{i = 1}^s \mathcal{M}_{D_i} 
\end{equation*}
with $\sum_{i = 1}^s D_i = D$. We will call the $i$-th block \emph{redundant} if the compression dimension is smaller than $D_i$.
\end{defi}
We claim that checking redundancy can be phrased as an interpolation problem. Let $D_1$ be a block of maximal dimension (it does not matter which one we take if several of them have the same dimension, since all are redundant if one of them is). Then we ask whether there is a completely positive map $\Phi_1: \mathcal{M}_{D} \to \mathcal{M}_{D_1}$ such that 
\begin{equation*}
\Phi_1\left(\begin{bmatrix}
0& & & \\ &E^2 & & \\ & &\ddots & \\& & & E^s 
\end{bmatrix}\right) = E^1 \qquad \forall E \in \mathcal{O}\cup \Set{\idop},
\end{equation*}
where $E^i \in \mathcal{M}_{D_i}$ for all $i \in [s]$. This is a problem which can be solved using a semidefinite program (SDP, cf.\  \cite{Boyd2004}) as shown in \cite{Heinosaari2012}. Without loss of generality, we can assume that $\mathcal{O} = \Set{\idop, E_2, \ldots, E_k}$, $k \in \mathds{N}$. If this is not the case, substitute $\mathcal{O}$ by a set of linearly independent Hermitian operators including the identity where $k = \dim{\mathcal{L}(\mathcal{O})}$. The SDP is the following:
\begin{align*}
&\mathrm{Minimize} & & \sum_{i = 1}^k \tr{(E^1_i)^T H_i}\\
&\mathrm{Subject~to}& & \sum_{i = 1}^k \begin{bmatrix}
0 & & & \\ &E_i^2 & & \\ &  &\ddots & \\ & & & E_i^s 
\end{bmatrix} \otimes H_i \geq 0 \qquad H_i \in \mathcal{M}_{D_1}, \forall i \in [k]
\end{align*}
We will refer to an algorithm which solves this problem as InterpolationSDP with parameters $E_1, \ldots, E_k$ and $j$, where $j$ denotes the block which appears in the minimization (in the above case $j = 1$). This SDP has either $-\infty$ or $0$ as solution, the latter solution confirming that there is a $\Phi_1$ as specified above. If such a $\Phi_1$ cannot be found, $D_1$ is the minimal dimension we can compress to, otherwise we proceed to the next block.
Then we can repeat the procedure with the remaining blocks until we either encounter one block which is not redundant or we are left with only one block. This algorithm is formalized in pseudocode in \Fref{alg:mindimalgo}.

\begin{algorithm}
\caption{Compute minimal compression dimension} \label{alg:mindimalgo}
\begin{algorithmic}[1]
\Require{List of $E_i = \Set{E_i^1, \ldots, E_i^s}, E_i^j \in \mathcal{M}_{D_j}, i \in [k], j \in [s]$, where $E_1 = \idop$; List $\Set{D_1, \ldots, D_s}$ s. t. $D_1 \geq \ldots \geq D_s$.}
\State $j := 1$
\State $\mathrm{Dmax} := D_1$
\While{$j < s$}
\State $h \gets \mathrm{InterpolationSDP}(E_1, \dots, E_k)(j)$ \Comment 0 if block redundant, $- \infty$ otherwise
\State $j \gets j+1$
\If{h = 0}
\State $\mathrm{Dmax} \gets D_{j}$
\State $E_i^j \gets 0$ $\forall i \in [k]$ \Comment Set largest non-zero block to zero
\Else
\State $j \gets s$ \Comment Terminates computation
\EndIf
\EndWhile
\State \Return $\mathrm{Dmax}$ \Comment Dimension of largest non-redundant block
\end{algorithmic}
\end{algorithm}

To see that there are actually Hermitian operators which give rise to redundant blocks such that the dimension we can compress to is strictly less than the maximal block dimension, we refer to the end of this section. We proceed with a proof that the dimension computed by \Fref{alg:mindimalgo} is indeed the minimal one. 
\begin{thm}[Correctness of the algorithm] \label{thm:algorithmcorrect}
The dimension computed by \Fref{alg:mindimalgo} is the compression dimension.
\end{thm}
\begin{proof}
We proceed in three steps. First, we see that $d$ is the dimension of the largest block on which an optimal compression map acts as the identity. Then, we see that all larger blocks can be interpolated. Last, we see that no other blocks have a solution to the interpolation problem. Assume that we have found a map $\mathcal{T}^\ast  $ such that $d$ is the compression dimension. Then this map has to be the identity on some blocks by \Fref{cor:algsub}. Let $\mathcal{I} \subset [s]$ be the index set of the blocks for which this is the case. Again by \Fref{cor:algsub}, we can conclude that $d \geq \max_{i \in \mathcal{I}}D_{i} =: D_{\max}$. We have to show that $D_{\max}$ can be attained to complete the first step, whereby $d = D_{\max}$. Since $\mathcal{T}^\ast  $ and $\mathcal{T}^\ast  _\infty$ have the same fixed point set, we can use $\mathcal{T}^\ast  _\infty$ to construct another compression map. Note that all blocks with $i \notin \mathcal{I}$ lie in the kernel of $\mathcal{T}^\ast  _\infty$ by \Fref{cor:algsub}. Thus, for all $j \in [s]\setminus \mathcal{I}$ there must be a completely positive map $\Phi_j: \mathcal{M}_D \to \mathcal{M}_{D_j}$ such that
\begin{equation} \label{eq:redundantblock}
\Phi_j\left(\bigoplus_{i = 1}^s \chi_{\mathcal{I}}(i) E^i\right) = E^j \qquad \forall E \in \mathcal{O} \cup \Set{\idop},
\end{equation}
where $\chi_{\mathcal{I}}$ is the indicator function of the set $\mathcal{I}$. Hence, we can give the following compression scheme which attains $D_{\max}$. For the decompression map $\mathcal{D}$, we can almost use the map given in the proof of \Fref{thm:blockcompression} with $d = D_{\max}$, but requiring the sum in \Fref{eq:blockdecompression} to run only over $\mathcal{I}$. Without loss of generality, we can assume that $\mathcal{I}$ is the set of the first $|\mathcal{I}|$ entries, such that $n = |\mathcal{I}|$ is the dimension needed for the classical side information. Let $V_i: \mathds{C}^{D_i} \hookrightarrow \mathds{C}^D$ be an isometry such that $V_i V_i^\ast   = P_i$ is the projection onto the $i$-th block $\forall i \in [s]$ and $W_j: \mathds{C}^{D_j} \hookrightarrow \mathds{C}^{D_{\max}}$ an isometry such that $W_j W_j^\ast   = Q_j$ is the projection onto $\mathcal{M}_{D_j}$ $\forall j \in [s]$. Then we can define the dual compression map $\mathcal{C}^\ast : \mathcal{M}_{D_{\max}} \otimes \mathds{C}^n \to \mathcal{M}_D$ as
\begin{equation*}
\mathcal{C}^\ast  (A) := \mathcal{T}^\ast  _\infty \left(\sum_{j \in \mathcal{I}} V_j\left(W_j^\ast   \otimes \Bra{j}\right)A\left(W_j \otimes \Ket{j}\right) V_j^\ast  \right).
\end{equation*}
This map can easily be seen to be completely positive, because $\mathcal{T}^\ast  _\infty$ is. Correctness follows from the construction in \Fref{thm:blockcompression} since the missing blocks are all in the kernel of $\mathcal{T}_\infty^\ast  $. The same holds for unitality. Hence, $d = D_{\max}$ since otherwise the map just defined would allow for an even better decompression, which contradicts that $d$ is minimal. This shows that all redundant blocks have a solution to the interpolation problem and completes the second step.

If we could find a set $\mathcal{J} \subset [s]$ and completely positive maps such that \Fref{eq:redundantblock} holds for this $\mathcal{J}$ instead of $\mathcal{I}$ and such that $D_{\max}^\prime = \max_{j \in J}D_j < d$, we could construct a dual channel attaining better compression. To see this, define a map $\mathcal{R}^\ast  $ which is $\Phi_j$ on blocks $j \in [s] \setminus \mathcal{J}$ and the identity on all other blocks. Then we could substitute $\mathcal{J}$ for $\mathcal{I}$, $D_{\max}^\prime$ for $D_{\max}$ and $\mathcal{R}^\ast  $ for $\mathcal{T}^\ast  _\infty$ in the above construction to obtain a map with compression dimension $D_{\max}^\prime$, which contradicts minimality of $d$. This shows that a block admits a solution to the interpolation problem if and only if it is redundant and completes the last step.
\end{proof}
For a discussion of the complexity of the proposed algorithm, we refer to \Fref{sec:complexity}. Instead, we will show now that unless the algebra has a very specific structure, any block can  be redundant. We start with two lemmas investigating the matrix $\ast$-algebra generated by the image of a unital CP map.

\begin{lem}\label{lem:smalltobig}
Let $\mathcal{A}$ be a unital matrix $\ast$-algebra that contains $\mathcal{M}_2$ or $\mathds{C}^3$ as a subalgebra, which we denote by $\mathcal{A}^\prime$. For every unital matrix $\ast$-algebra $\mathcal{B}$, there is a unital CP map $\Phi: \mathcal{A} \to \mathcal{B}$ and positive rank one elements $A_1,A_2,A_3\in\mathcal{A}^\prime$ such that 
\begin{enumerate}
\item $\cstar{\{A_1,A_2,A_3\}}=\mathcal{A}^\prime$,
\item $\cstar{\{\Phi(A_1),\Phi(A_2),\Phi(A_3)\}} = \mathcal{B}$, and
\item each $\Phi(A_i)$, $i\in[3]$ is positive definite.   
\end{enumerate} 
\end{lem}
\begin{proof}
Assume that $\mathcal{B}$ is not $\ast$-isomorphic to a subalgebra of $\mathcal{A}^\prime$ (otherwise the statement is trivial). Without loss of generality let $\mathcal{B} = \bigoplus_{i=1}^s\mathcal{M}_{D_i}$, as $\mathcal{B}$ is $\ast$-isomorphic to such an algebra and any $\ast$-isomorphism is a unital CP map. Choose $X_i$, $Y_i \in \mathcal{M}_{D_i}$ such that $0 < X_i,Y_i < \idop/2$, $\cstar{\Set{X_i, Y_i, \idop}}= \mathcal{M}_{D_i}$ and such that $B_1 := \bigoplus_{i = 1}^s X_i$ and $B_2 := \bigoplus_{i = 1}^s Y_i$ both have non-degenerate spectrum. This is possible, because invoking \Fref{lem:matrixalgebrameasure1} lets us choose generic Hermitian $\tilde{X}_i$, $\tilde{Y}_i$ such that these generate the respective algebras. The non-singular transformation $X_i \mapsto \lambda_{x,i}(X_i + \mu_{x,i} \idop)$ with $\lambda_{x,i}$, $\mu_{x,i} > 0$ and $Y_i \mapsto \lambda_{y,i}(Y_i + \mu_{y,i} \idop)$ with $\lambda_{y,i}$, $\mu_{y,i} > 0$ allow us to choose the elements positive definite and not too large with an appropriate choice of parameters. 

Now set $B_3 := \idop - B_1 -B_2$. Note that $B_3 > 0$ and $\cstar{\Set{B_1, B_2, \idop}} = \mathcal{B}$ hold by the above construction, which in particular implies that the $B_i$ are linearly independent if $\mathcal{B}$ is non-commutative. Choose a set of linearly independent, positive rank one operators $A_i$, $i \in [3]$ such that $\sum_{j = 1}^3 A_j = \idop$ and $\tr{A_j} = c$, $c > 0$. For $\mathcal{A}^\prime = \mathds{C}^3$, we can pick an ONB and for $A^\prime = \mathcal{M}_2$ the operators $A_i = 2/3 \dyad{a_i}$ with $\Ket{a_i} = \cos{\theta_i}\Ket{0} + \sin{\theta_i}\Ket{1}$  and $\theta_i = i 2 \pi/3$, $i \in [3]$. Note that both these choices generate $\mathcal{A}^\prime$ as a C$^\ast$-algebra.

We define $\tilde{\Phi}: \mathcal{A}^\prime \to \mathcal{B}$ as
\begin{equation*}
\tilde{\Phi}(Z) = \frac{1}{c} \sum_{i = 1}^3 \tr{A_i Z}B_j.
\end{equation*}
This is clearly a unital CP map. If $\mathcal{B}$ is commutative, then it follows that $D_i = 1$ for all $i \in [s]$ and it is easy to see that the assertion of the lemma holds if we extend $\tilde{\Phi}$ to a map $\Phi$ on $\mathcal{A}$. If $\mathcal{B}$ is not commutative, we claim that $\dim(\ran(\tilde{\Phi})) = 3$, even if the preimage is restricted to the linear span of the $A_i$'s.
This can be seen as follows. Assume that $\tilde{\Phi}(A_1) = \lambda \tilde{\Phi}(A_2) + \mu \tilde{\Phi}(A_3)$ for some $\lambda$, $\mu \in \mathds{C}$. By linear independence of the $B_j$, this implies
\begin{equation*}
\tr{A_j (A_1 - \lambda A_2 - \mu A_3)} = 0 \qquad \forall j \in [3].
\end{equation*}
The above implies, however, that $\tr{|A_1 - \lambda A_2 - \mu A_3|^2} = 0$ and hence $A_1 - \lambda A_2 - \mu A_3 = 0$. This is a contradiction due to the linear independence of the $A_i$, which proves the claim that $\dim(\ran(\tilde{\Phi})) = 3$. 

Therefore, $\tilde{\Phi}$ maps $\linspan{A_1,A_2,A_3}$ onto  $\linspan{B_1, B_2, \idop}$. Let $\Phi$ be the extension of $\tilde{\Phi}$ to $\mathcal{A}$. So we have finally proven claim (2) of the Lemma since
\begin{equation*}
\mathcal{B}\supset \cstar{\Phi(\mathcal{A})} \supset \cstar{\{\Phi(A_1),\Phi(A_2),\Phi(A_3)} = \cstar{\Set{\idop, B_1, B_2}} = \mathcal{B}.
\end{equation*}
\end{proof}

\begin{lem} \label{lem:toosmall}
Let $\mathcal{A}$ be $\ast$-isomorphic to $\mathds{C}^1$ or $\mathds{C}^2$ and let $\mathcal{B}$ be non-commutative. Then there is no unital CP map $\Phi: \mathcal{A} \to \mathcal{B}$ such that $\cstar{\Phi(\mathcal{A})} = \mathcal{B}$.
\end{lem}
\begin{proof}
If $\mathcal{A} = \mathds{C}^1$, then $\cstar{\Phi(\mathcal{A})}$ is clearly commutative due to linearity of the map. The algebra is also commutative for $\mathcal{A} = \mathds{C}^2$ due to unitality of $\Phi$. 
\end{proof}
As a corollary to these two lemmas, we can now investigate the possible redundancies of blocks in the representation of a finite-dimensional C$^\ast$-algebra.
\begin{cor}[Tightness of algebraic bounds]\label{cor:possiblyredundant}
Let $\mathcal{A} = \bigoplus_{i = 1}^s \mathcal{M}_{D_i}$.
\begin{enumerate}
\item If $\mathcal{A} $ contains three $\mathcal{M}_1$-blocks in its block structure, then there is a set of effect operators $\mathcal{W} \subset \mathcal{A}$ with compression dimension $d=1$ and s.t. $\cstar{\mathcal{W}} = \mathcal{A}$.
\item If $\mathcal{A}$ contains $\mathcal{M}_\delta$ for some $\delta \geq 2$ in its block structure, then we can find a set of effect operators $\mathcal{W} \subset \mathcal{A}$ with compression dimension $d=\delta$ and such that $\cstar{\mathcal{W}} = \mathcal{A}$.
\item Let $\delta := \max_{i \in [s]}D_i$. If $\mathcal{A} \setminus \mathcal{M}_\delta$ does neither contain $\mathcal{M}_2$ nor $\mathds{C}_3$ as subalgebra, then every $\mathcal{W}$ with $\cstar{\mathcal{W}} = \mathcal{A}$ has compression dimension $\delta$.
\end{enumerate}
\end{cor}
\begin{proof}
Claim (1) as well as claim (2) for $\delta=2$ follow 
directly from \Fref{lem:smalltobig} when choosing $\mathcal{A}^\prime$ as the considered subalgebra $\mathcal{M}_2$ or $\mathds{C}^3$ and $\mathcal{B}:=\mathcal{A}\setminus\mathcal{A}^\prime$: we define $\mathcal{W} = \Set{A_i \oplus \Phi(A_i): i \in [3]}$ where $A_i$, $\Phi$ are as in the lemma. From the representation theory of matrix $\ast$-algebras it follows that $\cstar{\mathcal{W}} = \mathcal{A}$, since we constructed the map such that $\Phi(A_i) > 0$. This excludes that the block generated by the $A_i$ has multiplicity greater than $1$ in $\cstar{\mathcal{W}}$. The assertions then follows from \Fref{thm:algorithmcorrect}.

Claim (2) with $\delta>2$ is a simple consequence of the assertion for $\delta=2$ by using an isometric embedding of $\mathcal{M}_2$ into $\mathcal{M}_\delta$. The set $\mathcal{W}$ is then obtained by taking the above (embedded) construction and adding sufficiently many elements of the form $A\oplus 0\in\mathcal{M}_\delta\oplus (\mathcal{A}\setminus\mathcal{M}_\delta)$ so that the $C^*$-algebra that they generate is the entire block $\mathcal{M}_\delta\oplus 0$ (and not only the embedded $\mathcal{M}_2$ subalgebra). We can choose one of these elements such that all blocks of dimension less than $\delta$ have operator norm strictly less than the block of dimension $\delta$. This guarantees that the compression dimension is not smaller than $\delta$ because of the contractivity of unital positive maps.

Claim (3) follows directly from \Fref{lem:toosmall} and \Fref{thm:algorithmcorrect}.
\end{proof}
Note that we can extend the above corollary to general matrix $\ast$-algebras by invoking \Fref{prop:simpleralgebra}. We have therefore shown that unless we are in the last case of the corollary, our upper and lower bounds on the compression dimension are tight.


\section{Generalizations} \label{sec:generalizations}

\subsection{Measurements and expectation values} \label{sec:modimeasure}

When we presented the setup in \Fref{sec:setup}, we were interested in preserving the measurement statistics, i.e.\  the probabilities of each outcome of a fixed set of measurements. Subsequently, we realized that it makes no difference whether we assume $\mathcal{O} \subset \mathcal{E}(\mathds{C}^D)$ or $\mathcal{O} \subset \mathcal{M}_D^\herm$, since only the operator system generated by $\mathcal{O}$ was important. This implies, however, that instead of (approximately) preserving the probabilities for each outcome, we could also only aim to preserve the expectation values of a set $\mathcal{O} \subset \mathcal{M}_D^\herm$ of observables and all results of this paper still apply. In particular, for generic $A$, $B \in \mathcal{M}_D^\herm$ such that $\cstar{\set{A,B}} = \mathcal{M}_D$, \Fref{thm:newarveson} still states that those observables are incompressible. 

Another possible modification of our setup would be to ask only for measurements $E^\prime$ on the compressed state $\mathcal{C}(\rho)$ which return the original statistics, but without imposing that $E^\prime = \mathcal{D}^\ast(E)$ for some $E \in \mathcal{O}$ and some channel $\mathcal{D}$. This relaxation, however, can easily be seen to allow for more powerful compression in certain cases. Let $\mathcal{O} = \Set{E_1, E_2, E_3}$, where the elements form a POVM and $E_1$ and $E_2$ are generic. In the alternative setup, we can see that it is possible to compress to $d=1$ using 
\begin{equation*}
\mathcal{C}(\rho) = \sum_{i=1}^3 \tr{E_i \rho} \dyad{i}
\end{equation*}
and choosing $E^\prime_i = \dyad{i}$. However, \Fref{thm:newarveson} implies that $\mathcal{O}$ is incompressible in the original setup. The explanation for this difference is that there is no channel $\mathcal{D}$ which allows to map the elements of $\mathcal{O}$ to projections. Therefore, we see that this modification changes the problem significantly and we leave it for future work. 

\subsection{Positive and Schwarz maps}

The aim of this section is to explore how much we can relax the requirements on the compression and decompression channel. We still consider the setup of \Fref{sec:setup}, but now we require $\mathcal{C}$, $\mathcal{D}$ only to be positive instead of completely positive. Since the argument at the beginning of the proof of \Fref{thm:geometric} uses only that the maps involved are positive and trace preserving to apply the Russo-Dye theorem, the results of \Fref{thm:geometric} carry over to this setting. Note that the results obtained in the algebraic setting do not carry over to arbitrary positive maps, since for Arveson's result it is important that the map is a Schwarz map (see remark before \cite[Example 5.3]{Wolf2012}). Complete positivity, however, is not needed; a trace preserving positive map whose dual is also a Schwarz map is enough. See \Fref{lem:schwarzcesaro} for a proof that the Ces{\`a}ro-mean of a Schwarz map is again a Schwarz map. Using  \Fref{lem:noinfo} instead of the corresponding well-known result for completely positive maps, we can extend \Fref{thm:newarveson} and \Fref{lem:Arvesonthm} to Schwarz maps. From a physicist's perspective exchanging $\mathcal{D}$ for a positive instead of a completely positive map can be interpreted as measuring different effect operators and inferring from them the statistics with respect to the original effect operators. Note that this is still less general than the modified setup discussed in \Fref{sec:modimeasure}. Since only completely positive maps are considered meaningful evolutions of a physical system, we have proven the theorems under these stronger conditions.

\subsection{Completely positive maps on operator spaces}

Most of our analysis has been carried out in the Heisenberg picture. The dual maps $\mathcal{T}^\ast  $, $\mathcal{C}^\ast  $ and $\mathcal{D}^\ast  $ have been assumed to be completely positive on the full matrix algebra. However, one could argue that only complete positivity on the operator system $\mathcal{L}^\prime(\mathcal{O})$ generated by $\mathcal{O}$ is required. By Arveson's extension theorem \cite[Theorem 7.5]{Paulsen2003} (or \cite[Theorem 6.2]{Paulsen2003}, since we only need the finite-dimensional version) any completely positive map $\mathcal{T}^\ast  : \mathcal{L}^\prime(\mathcal{O}) \to \mathcal{M}_D$ can be extended to a completely positive map on $\mathcal{M}_D$. Hence, as long as we consider the setup relevant for quantum information, we need not distinguish whether $\mathcal{T}^\ast  $ is completely positive on the full matrix algebra or on the operator system. For positive maps, this is no longer true in general (see \cite[remark after Corollary 7.6]{Paulsen2003}).

\subsection{Finitely many states}

This section will briefly address the question of what can be proven if instead of all states $\SS(\mathds{C}^D)$ we only want to measure effect operators on a subset $\SS_{\mathcal{I}} = \Set{\rho_i : i \in \mathcal{I}}$ for some states $\rho_i \in \SS(\mathds{C}^D)$ and some index set $\mathcal{I} \subset \mathds{R}$. We note that the situation in \Fref{sec:setup} is not changed if $\mathcal{M}_D = \linspan[\mathds{C}]{\SS_{\mathcal{I}}}$, since again only the operator space spanned by the states matters, not the states themselves. We could thus exchange the set of all states for the set of pure states and our results in the above sections still hold.

Consider next the situation in which we allow only for states from $\SS_{\mathcal{I}}$, but this time we want to measure a set of effect operators $\widetilde{\mathcal{O}}$ such that $\mathcal{L}(\widetilde{\mathcal{O}}) = \mathcal{M}^\herm_D$. For example, $\widetilde{\mathcal{O}} = \mathcal{E}(\mathds{C}^D)$. This is the converse situation of what we considered before. Although we cannot apply the techniques used so far in this situation, this setup is actually significantly simpler. Let us adapt our definition of compressibility to this new setting.
\begin{defi}[Compression of states]
Let $\SS_{\mathcal{I}}$ be a set of states in $\mathcal{M}_D$. The  \emph{compression dimension} of $\SS_{\mathcal{I}}$ is the smallest $d\in\mathds{N}$ for which there is an $n\in\mathds{N}$, 
a CPTP map $\mathcal{C}: \mathcal{M}_D \to \mathcal{M}_{d}\otimes \mathds{C}^n$ and a CPTP map $\mathcal{D}: \mathcal{M}_{d}\otimes \mathds{C}^n \to \mathcal{M}_D$ such that for their composition $\mathcal{T} = \mathcal{D} \circ \mathcal{C}$, the constraints 
\begin{equation}\label{eq:stateconstraint}
\tr{\rho A} = \tr{\mathcal{T}(\rho) A}= \tr{\rho \mathcal{T}^\ast  (A)} \qquad \forall \rho \in \SS_{\mathcal{I}}, \forall A \in \mathcal{M}^\herm_D
\end{equation}
are satisfied. If the compression dimension equals $D$, $\SS_{\mathcal{I}}$ is said to be \emph{incompressible}.
\end{defi}

Then we can give a lower bound on the compression dimension in this setup.

\begin{thm}[Lower bound for states] \label{thm:nostatecomp}
Let $\SS_{\mathcal{I}}$ be a set of states and
\begin{equation*}
\cstar{\SS_\mathcal{I}} = W \left[ 0 \oplus \bigoplus_{k = 1}^s (\mathcal{M}_{D^\prime_k} \otimes \idop_{m^\prime_k}) \right]W^\ast
\end{equation*}
with $D_0 + \sum_{k = 1}^s m_k D^\prime_k = D$ and $W \in \mathcal{U}(D)$. Then the compression dimension is $\max_{k \in [s^\prime]} D^\prime_k$. In particular, if  $\cstar{\SS_{\mathcal{I}}} = \mathcal{M}_D$, then $\SS_{\mathcal{I}}$ is incompressible.
\end{thm}

Before we can proof this, we need to prove a lemma.
\begin{lem} \label{lem:noduplicatecompression}
Let $\mathcal{C}$, $\mathcal{D}^\ast  : \mathcal{M}_D \to \mathcal{M}_{d} \otimes \mathds{C}^n$ be linear positive maps and let $\mathcal{T} = \mathcal{D} \circ \mathcal{C}$. If the fixed point set of $\mathcal{T}$ has the form $\mathcal{M}_{D^\prime} \otimes \rho$, $\rho \in \SS(\mathds{C}^m)$ such that $m \cdot D^\prime = D$, then $d \geq D^\prime$.
\end{lem}
\begin{proof}
We define $\iota_{\rho}: \mathcal{M}_{D^\prime} \to \mathcal{M}_D$ by $\iota_{\rho}(A) = A \otimes \rho$ for all $A \in \mathcal{M}_{D^\prime}$. This defines a completely positive map. We can also define $\widetilde{\mathcal{T}}: \mathcal{M}_{D^\prime} \to \mathcal{M}_{D^\prime}$
\begin{equation*}
\widetilde{\mathcal{T}} := \mathrm{Tr}_{\mathds{C}^m}{} \circ \mathcal{T} \circ \iota_\rho.
\end{equation*}
Here, we have made the identification $\mathds{C}^D \simeq \mathds{C}^{D^\prime} \otimes \mathds{C}^m$. By our assumption on the fixed point set of $\mathcal{T}$, we know that $\widetilde{\mathcal{T}}$ is the identity map. By the same argument as in the proof of \Fref{thm:newarveson},  $d \geq D^\prime$ follows from \Fref{lem:noinfo}.
\end{proof}


\begin{proof}[Proof of \Fref{thm:nostatecomp}]
Since we require \Fref{eq:stateconstraint} to hold, we see that $\SS_\mathcal{I} \subset \mathcal{F}_{\mathcal{T}}$ for $\mathcal{F}_{\mathcal{T}}$ the fixed point set of $\mathcal{T}$. For $\mathcal{T}$ a completely positive and trace preserving map, it is known that the fixed point set has the structure
\begin{equation} \label{eq:fixedpointset}
\mathcal{F}_{\mathcal{T}} = U \left(0 \oplus \bigoplus_{k = 1}^s \mathcal{M}_{D_k} \otimes \rho_k\right) U^\ast  
\end{equation}
with $U \in \mathcal{U}(D)$, $\rho_k \in \SS(\mathds{C}^{m_k})$ and $D = D_0 + \sum_{k = 1}^s m_k D_k$, where $D_0$ is the dimension of the zero block. The $\rho_k$ can be assumed to be diagonal (we can absorb the unitaries diagonalizing them into $U$), hence 
\begin{equation*}
\cstar{\mathcal{F}_{\mathcal{T}}} \subset U \left(0 \oplus \bigoplus_{k = 1}^s \bigoplus_{j = 1}^{m_k} \mathcal{M}_{D_k} \right) U^\ast. 
\end{equation*}
These blocks can be considered independently. Let $V_k: \mathds{C}^{D_k \cdot m_k} \hookrightarrow \mathds{C}^D$ be an isometry such that $V_k V_k^\ast  $ is the projection onto the $k$-th block in the outer direct sum. Then define $\mathcal{T}_k: \mathcal{M}_{m_k \cdot D_k} \to \mathcal{M}_{m_k \cdot D_k}$ by
\begin{equation*}
\mathcal{T}_k := \Theta_{V_k  }\circ \Theta_{U} \circ \mathcal{T} \circ \Theta_{U^\ast} \circ \Theta_{V_k^\ast}.
\end{equation*}
By construction, the fixed point set of $\mathcal{T}_k$ is $\mathcal{M}_{D_k} \otimes \rho_k$. The map factorizes into $\mathcal{C}_k: \mathcal{M}_{m_k \cdot D_k} \to \mathcal{M}_d \otimes \mathds{C}^n$ with 
\begin{equation*}
\mathcal{C}_k = \mathcal{C} \circ \Theta_{U^\ast} \circ \Theta_{V_k^\ast}
\end{equation*}
and $\mathcal{D}_k:\mathcal{M}_d \otimes \mathds{C}^n \to \mathcal{M}_{m_k \cdot D_k}$ with
\begin{equation*}
\mathcal{D}_k = \Theta_{V_k  }\circ \Theta_{U}\circ \mathcal{D}.
\end{equation*}
\Fref{lem:noduplicatecompression} shows that $d \geq D_k$. Since this holds for all $k \in [s]$, it follows that $d \geq \max_{k \in [s]} D_k$. Furthermore, for all $i \in [s^\prime]$ there must be a $k \in [s]$ such that $D_k \geq D^\prime_i$, otherwise the structure of $\cstar{S_\mathcal{I}}$ could not be as assumed. Hence, also $d \geq \max_{k \in [s^\prime]} D^\prime_k$. That this bound is achievable can be seen through a slight modification of the construction in \Fref{thm:blockcompression}. The maps can be chosen the same (assuming $\SS_{\mathcal{I}}$ already to be in block-diagonal form), but the isometries need to be chosen such that they respect the block structure of the states instead of the block structure of the operators in $\mathcal{O}$. Here, we treat the zero block as a direct sum of $D_0$ $1$-dimensional blocks, which do not affect the compression dimension.
\end{proof}

The same result also holds in a more general setting. For the theorem to hold, $\mathcal{T}$ needs not be completely positive. Since \Fref{eq:fixedpointset} is also valid if $\mathcal{T}$ is a positive, trace preserving, linear map such that the dual map satisfies the Schwarz inequality, the above theorem also holds for $\mathcal{C}, \mathcal{D}$ such that $\mathcal{T}$ satisfies these weaker conditions (see \cite[Theorem 6.14]{Wolf2012}).

 We have shown that unlike in the converse situation, there are no redundant blocks. Whether better bounds can be shown for finite sets of both states and effect operators beyond the results from \cite{Stark2014} and \cite{Wehner2008} remains an open problem.
\section{Several copies of the same state} \label{sec:copies}

In this section, we consider the following modifications compared to \Fref{sec:setup}. We are given a set of Hermitian operators as before which we denote by $\mathcal{O}$. Instead of only one state, we consider finitely many copies of the same state (provided e.g.\  by identical preparations). Hence, we consider a quantum channel $\mathcal{C}: \mathcal{M}_{mD} \to \mathcal{M}_{d} \otimes \mathds{C}^n$. Compression in this setting is defined as follows: 
\begin{defi}[Compression of observables using copies]
Let $\mathcal{O}$ be a set of Hermitian operators in $\mathcal{M}_D$ and $m \in \mathds{N}$ the number of copies available. The  \emph{compression dimension} of $\mathcal{O}$ is the smallest $d\in\mathds{N}$ for which there is an $n\in\mathds{N}$, 
a CPTP map $\mathcal{C}: \mathcal{M}_{mD} \to \mathcal{M}_{d}\otimes \mathds{C}^n$ and a CPTP map $\mathcal{D}: \mathcal{M}_{d}\otimes \mathds{C}^n \to \mathcal{M}_D$ such that for their composition $\mathcal{T} = \mathcal{D} \circ \mathcal{C}$, the constraints 
\begin{equation} \label{eq:copyconstraints}
\Tr{\rho E} = \Tr{\mathcal{T}(\rho^{\otimes m})E} = \Tr{\rho^{\otimes m}\mathcal{T}^\ast  (E)} \qquad \forall \rho \in \SS(\mathds{C}^D), \forall E \in \mathcal{O}
\end{equation}
are satisfied. If the compression dimension equals $D$, $\mathcal{O}$ is said to be \emph{incompressible}.
\end{defi}
We prove now that taking copies of the state does not affect compressibility in the geometric picture.
\begin{thm}[Lower bounds on compression dimension  for finitely many copies] \label{thm:copies}
Let $\mathcal{O} \subset \mathcal{M}_D^\herm$ a set of Hermitian operators, $E_1$, $E_2 \in \mathcal{L}(\mathcal{O})$ and 
\begin{equation*}
p(x,z) := \det[x \idop - E_1 - z E_2].
\end{equation*}
Then the smallest among the degrees of the irreducible factors of $p$ is a lower bound on the compression dimension of $\mathcal{O}$. In particular, if $p$ is irreducible over the reals, then $\mathcal{O}$ is incompressible.
\end{thm}
\begin{proof}
Maximizing \Fref{eq:copyconstraints} over $\rho \in \SS(\mathds{C}^D)$, we obtain
\begin{equation} \label{eq:lowerboundcopy}
\opnorm{A} = \max_{\rho \in \SS(\mathds{C}^D)} |\Tr{\rho^{\otimes m}\mathcal{T}^\ast  (A)}| \qquad \forall A \in \mathcal{L}(\mathcal{O}).
\end{equation}
The right hand side of the above is clearly upper bounded by $\opnorm{\mathcal{T}^\ast  (A)}$. Since $\mathcal{T}^\ast  $ is unital, it is a contraction by the Russo-Dye theorem and
\begin{equation*}
\opnorm{\mathcal{T}^\ast  (A)} \leq \opnorm{A}
\end{equation*} 
from which equality follows together with \Fref{eq:lowerboundcopy}. Thus, we are able to apply the techniques from \Fref{sec:geoargument}. Since $\mathcal{C}^\ast  $ and $\mathcal{D}^\ast  $  are unital as well, we obtain again
\begin{equation*}
\opnorm{E_1 + t E_2} = \opnorm{\mathcal{D}^\ast  (E_1) + t \mathcal{D}^\ast  (E_2)} \qquad \forall t \in \mathds{R}.
\end{equation*} 
The assertion then directly follows from \Fref{lem:nosmalleropnorm}. 
\end{proof}
Note that in this case, we have to make use of the geometric arguments since we cannot infer from \Fref{eq:copyconstraints} that $E \in \mathcal{O}$ have to be fixed points of the dual channel. 
\newline
\newline
\textbf{Acknowledgements}: AB would like to thank Michael Kech for helpful discussions concerning the use of semialgebraic sets and the Stack Exchange user Simone Weil for pointing out the strategy to prove the existence of irreducible hyperbolic polynomials in any dimension. MMW thanks John Watrous for suggesting the problem and David P\'erez-Garc\'ia as well as John Watrous for interesting discussions.

