preliminaries.tex

%!TEX root = thesis.tex
%-------------------------------------------------------------------------------
\chapter{Preliminaries}
\label{chap:preliminaries}
%-------------------------------------------------------------------------------

In this chapter we summarize basic concepts of quantum information theory 
that will be used in the rest of the thesis.
Along the way, we will also pin down the notation that  
we use throughout this thesis, although for most part, 
we use notation that is standard in quantum information theory.
In particular, we will follow the same terminology and conventions adopted 
in \cite{Watrous15}.
This should not serve as in introduction to quantum information. For such
an introduction we refer the reader to a standard textbook \cite{Nielsen11}.

The last section introduces the basic concepts of convex optimization that are
necessary for analyzing problems in quantum information theory. 
For a more extended treatment of semidefinite programming and cone programming, 
we refer the reader to \cite{Wolkowicz00,Tuncel12} and the references therein.

\minitoc

%-------------------------------------------------------------------------------
\section{Basic notions of quantum information theory}
\label{sec:basic-notions-of-quantum-information-theory}
%-------------------------------------------------------------------------------

\subsection{Vector spaces, linear operators, and linear mappings}

All vector spaces considered here are assumed to be complex Euclidean spaces
(or, equivalently, finite-dimensional complex Hilbert spaces) and are denoted 
by scripted capital letters from the end of the English alphabet, 
such as $\X, \Y, \Z$.
Elements of a complex Euclidean space are denoted by lower-case letters
from the end of the English alphabet, such as $u, v, w, z$. For a complex
Euclidean spaces of dimension $n$, elements of the space can be represented as 
vectors in $\complex^{n}$. 
The standard basis of such a space is denoted using the Dirac notation as
$\left\{ \ket{0}, \ldots, \ket{n-1} \right\}$.

The inner product of two vectors $u, v \in \complex^{n}$ is defined as
\begin{equation}
  \ip{u}{v} = \sum_{i\in\{1,\ldots,n\}}\overline{u(i)}v(i).
\end{equation}

We write $\Lin(\X,\Y)$ to denote the space of linear operators from a space $\X$ 
to a space $\Y$, and we write $\Lin(\X)$ as shorthand for $\Lin(\X,\X)$.
Throughout the thesis, linear operators will be denoted with capital letters from the
beginning and the end of the English alphabet, such as $A, B, C, X, Y, Z$. 

For every operator $A\in\Lin(\X,\Y)$, the operator $A^{\ast}\in\Lin(\Y,\X)$
denotes the adjoint of $A$, that is, the unique operator that satisfies the equation
\begin{equation}
  \ip{v}{Au} = \ip{A^{\ast}v}{u},
\end{equation}
for all $u\in\X$ and $v\in\Y$.
In the matrix representation of linear operators, $A^{\ast}$ is the conjugate transpose of 
the matrix corresponding to $A$.

\renewcommand{\descriptionlabel}[1]{\hspace{\labelsep}\emph{#1}}

For any space $\X$, we consider the following important sets of operators acting on $\X$:
\begin{description}
\item[Hermitian operators -- $\Herm(\X)$]: operators $X\in\Lin(\X)$ such that $X^{\ast} = X$.
\item[Positive semidefinite operators -- $\Pos(\X)$]: operators $X\in\Lin(\X)$ for which it holds 
  that $X = Y^{\ast}Y$ for some operator $Y\in\Lin(\X)$.
\item[Density operators -- $\Density(\X)$]: positive semidefinite operators
  having trace equal to $1$. To denote density operators, we will use letters from 
  the Greek alphabet, such as $\rho,\sigma,\xi$.
\end{description}
The eigenvalues of an Hermitian operator are all real numbers. 
Positive semidefinite operators are Hermitian by definition, and they can be
described as those Hermitian operators that have only nonnegative eigenvalues.
To recap, we have the following chain of containments:
\begin{equation}
  \Density(\X) \subset \Pos(\X) \subset \Herm(\X) \subset \Lin(\X).
\end{equation}
The identity operator acting on a given space $\X$ is denoted by $\I_{\X}$, 
or just as $\I$ when $\X$ is implicit.
For Hermitian operators $A, B \in \Herm(\X)$ the notations $A\geq B$ 
and $B \leq A$ indicate that $A - B$ is positive semidefinite.

Other important operators are \emph{linear isometries}, which are all operators
$X\in\Lin(\X,\Y)$ such that $X^{\ast}X=\I_{\X}$. The set of linear isometries 
from $\X$ to $\Y$ is denoted by $\Unitary(\X,\Y)$.
Linear isometries in $\Lin(\X)$ are called \emph{unitary operators} and their 
set is denoted by $\Unitary(\X)$.

We denote the standard Hilbert-Schmidt inner product of two operators
$X$ and $Y$ as
\begin{equation}
  \ip{X}{Y} = \tr(X^{\ast}Y).
\end{equation}

The trace norm of an operator $A\in\Lin(\X,\Y)$ is defined as
\begin{equation}
  \norm{A}_{1} = \tr(\sqrt{A^{\ast}A}),
\end{equation}
where $\sqrt{X}$ denotes the square root of a positive semidefinite
operator $X$, that is, the unique positive semidefinite operator $Y$ such that $Y^{2} = X$.

A quantum state is represented by a density operator $\rho\in\Density(\X)$, 
for some complex Euclidean space $\X$. A state $\rho\in\Density(\X)$ is said 
to be \emph{pure} if and only if it has rank equal to 1, or equivalently, 
if there exists a unit vector $u\in\X$ such that
\[
  \rho = uu^{\ast}.
\]

Along with linear operators, we will consider linear mappings of the form
\[
  \Phi:\Lin(\X) \rightarrow \Lin(\Y),
\]
for complex Euclidean spaces $\X$ and $\Y$.
The \emph{adjoint} of a mapping $\Phi$ is defined to be the unique mapping 
\[
  \Phi^{\ast}:\Lin(\Y) \rightarrow \Lin(\X),
\]
which satisfies the equation
\begin{equation}
\label{eq:adjoint-map}
  \ip{\Phi(X)}{Y} = \ip{X}{\Phi^{\ast}(Y)},
\end{equation}
for every $X\in\Lin(\X)$ and $Y\in\Lin(\Y)$.
Some important sets of linear mappings that we will consider in this thesis are
the following:
\begin{description}
\item[Hermiticity preserving] -- mappings of the form 
  $\Phi:\Lin(\X)\to\Lin(\Y)$ such that \[\Phi(X) \in \Herm(\Y),\] for any $X\in\Herm(\X)$.
\item[Positive] -- mappings of the form 
  $\Phi:\Lin(\X)\to\Lin(\Y)$ such that $\Phi(X) \in \Pos(\Y)$, for any $X\in\Pos(\X)$.
\item[Completely positive] -- mappings of the form 
  $\Phi:\Lin(\X)\to\Lin(\Y)$, such that 
  \[\Phi\otimes\I_{\Lin(\Z)}(X)\in\Pos(\Y\otimes\Z),\]
  for every complex Euclidean space $\Z$, and any $X\in\Pos(\X\otimes\Z)$.
\item[Trace-preserving] -- mappings of the form
  $\Phi:\Lin(\X)\to\Lin(\Y)$ such that 
  \[ \tr(\Phi(X)) = \tr(X),\] 
  for all $X\in\Lin(\X)$.
\end{description}
Transformations of a quantum system from one state to another are described by 
\emph{quantum channel}, which are completely positive, trace-preserving linear mappings.

Given the tensor product $\X_{1}\otimes\ldots\otimes\X_{n}$ of $n$ complex Euclidean spaces
$\X_{1},\ldots,\X_{n}$, and a partition 
\[ (k_{1},\ldots,k_{i} : k_{i+1},\ldots,k_{n}) \]
of the set $\{1, \ldots, n\}$, we use the notation 
\[ 
  (\X_{k_{1}}\otimes\ldots\otimes\X_{k_{i}} : \X_{k_{i+1}}\otimes\ldots\otimes\X_{k_{n}})
\]
to denote a bipartition of the entire space.

It is convenient for the analysis of states in a bipartition $(\X:\Y)$ 
to make use of the correspondence between operators and vectors 
given by the linear function 
\begin{equation}
\label{eq:vec}
  \op{vec} : \Lin(\Y,\X) \rightarrow \X\otimes\Y
\end{equation}
defined by the action
\begin{equation}
  \op{vec}(\ket{k}\bra{j}) = \ket{k} \ket{j}
\end{equation}
on standard basis vectors, and by linearity to all $\Lin(\Y,\X)$.

\begin{definition}
\label{def:max-ent-states}
Suppose that $\X$ and $\Y$ are complex Euclidean spaces with $n = \dim(\X)$ and 
$m = \dim(\Y)$, and assume $n\geq m$.
A unit vector $u\in\X\otimes\Y$, representing a pure state, is said to be
\emph{maximally entangled} provided that
\begin{equation}
  \tr_{\X}(u u^{\ast}) = \frac{\I_{\Y}}{m}.
\end{equation}
This condition is equivalent to
\begin{equation}
  u = \frac{1}{\sqrt{m}} \vec(A)
\end{equation}
for $A\in\Unitary(\Y,\X)$ being a linear isometry.
\end{definition}

\subsection{Pauli operators and Bell states}
One particularly important set of linear operators in $\Lin(\complex^{2})$ is 
the set of Pauli operators
\begin{equation} 
\label{eq:Pauli-operators}
  \begin{array}{llll}
    \sigma_{0} = \I = \begin{pmatrix} 1 & 0  \\ 0 & 1  \end{pmatrix}, & 
    \sigma_{1} = \begin{pmatrix} 0 & 1  \\ 1 & 0  \end{pmatrix}, & 
    \sigma_{2} = \begin{pmatrix} 0 & -i \\ i & 0  \end{pmatrix}, & 
    \sigma_{3} = \begin{pmatrix} 1 & 0  \\ 0 & -1 \end{pmatrix}.
  \end{array}
\end{equation}
The operators $\sigma_{1},\sigma_{2},\sigma_{3}$ are often referred as Pauli-$X$, -$Y$, -$Z$, respectively. 
The Pauli operators are Hermitian, unitary operators, and moreover,
they are orthogonal under the inner product, thus forming an orthogonal basis for
$\Lin(\complex^{2})$.

Through the vector-operator correspondence of Eq.~\ref{eq:vec}, 
the Pauli operators define an important class of maximally
entangled states, famously known as \emph{Bell states}:
\begin{equation}
  \psi_{k} = \frac{1}{2}\vec(\sigma_{k})\vec(\sigma_{k})^{\ast},
\end{equation}
for $k \in \{0,1,2,3\}$. More explicitly, the Bell states can be written down as follows:
\begin{equation} 
\label{eq:Bell-states}
  \begin{aligned}
    \ket{\psi_0} & = \frac{1}{\sqrt{2}}\ket{0}\ket{0} 
    + \frac{1}{\sqrt{2}}\ket{1}\ket{1},\\
    \ket{\psi_1} & = \frac{1}{\sqrt{2}}\ket{0}\ket{1} 
    + \frac{1}{\sqrt{2}}\ket{1}\ket{0},\\
    \ket{\psi_2} & = \frac{1}{\sqrt{2}}\ket{0}\ket{1} 
    - \frac{1}{\sqrt{2}}\ket{1}\ket{0},\\
    \ket{\psi_3} & = \frac{1}{\sqrt{2}}\ket{0}\ket{0} 
    - \frac{1}{\sqrt{2}}\ket{1}\ket{1}.
  \end{aligned}
\end{equation}
In higher dimensions, one can consider a generalization of the Pauli operators.
For any positive integer $n$, let us the define an $n$-th primitive root of unity as 
\begin{equation}
  \omega_{n} = \exp(2\pi i/n).
\end{equation}
The generalizations of Pauli-$X$ and Pauli-$Z$ in $\Unitary(\complex^{n})$ 
are defined as follows:
\begin{equation}
  X_{n} = \sum_{j \in \integer_{n}}\ket{j+1}\bra{j},
\end{equation}
and
\begin{equation}
  Z_{n} = \sum_{j \in \integer_{n}}\omega_{n}^{j}\ket{j}\bra{j}.
\end{equation}
Now we can define the set of \emph{generalized Pauli operators} in $\Unitary(\complex^{n})$ as the set
\begin{equation}
\label{eq:generalized-Pauli-operators}
  \left\{ W_{a,b}^{(n)} = X_{n}^{a}Z_{n}^{b} : a,b\in\integer_{n}\right\}.
\end{equation}
Starting from these operators we define the \emph{generalized Bell basis}
through the vector-operator bijection:
\begin{equation}
\label{eq:generalized-bell-basis}
  \left\{ \psi_{a,b}^{(n)} = \frac{1}{\sqrt{n}}\vec\left(W_{a,b}^{(n)}\right)
    \vec\left(W_{a,b}^{(n)}\right)^{\ast} : a,b\in\integer_{n} \right\}.
\end{equation}

%-------------------------------------------------------------------------------
\subsection{The Choi isomorphism}
\label{sec:choi-isomorphism}
%-------------------------------------------------------------------------------

To a quantum mapping $\Phi : \Lin(\X)\rightarrow\Lin(\Y)$, we associate an 
operator $J(\Phi) \in \Lin(\Y\otimes\X)$ defined as follows:
\begin{equation}
\label{eq:choi-operator}
  J(\Phi) = (\Phi\otimes\I_{\Lin(\X)})(\vec(\I_{\X})\vec(\I_{\X})^{\ast}).
\end{equation}
If we assume that $\X$ has dimension $n$, we can alternatively write this as
\begin{equation}
  J(\Phi) = \sum_{1\leq i,j \leq n}\Phi(\ket{i}\bra{j})\otimes\ket{i}\bra{j}.
\end{equation}
The operator $J(\Phi)$ is called the \emph{Choi representation}
of $\Phi$.
It is often the case that properties of the Choi representation reveal useful information 
on the mapping. For instance, positive semidefinite operators correspond to Choi representations 
of completely positive mappings.

%-------------------------------------------------------------------------------
\section{Quantum measurements}
\label{sec:quantum-measurements}
%-------------------------------------------------------------------------------
When we analyze state distinguishability problems, all the physical operations
performed by the involved parties can be formally phrased in terms of quantum 
measurements. 
A \emph{quantum measurement} is defined as a function 
\begin{equation}
\label{eq:def-measurement}
  \mu : \{ 1, \ldots, N \} \rightarrow \Pos(\X),
\end{equation}
for some choice of a positive integer $N > 0$ and a complex Euclidean space $\X$, 
satisfying the constraint
\begin{equation}
\label{eq:measurement-sum}
  \sum_{k=1}^{N} \mu(k) = \I_{\X}.
\end{equation}
The values $\{1, \ldots, N\}$ are the \emph{measurement outcomes} of $\mu$,
and the operator $\mu(k)$ is the \emph{measurement operator} of $\mu$ 
associated with the outcome $k$.
The set of all measurements over $\X$ with $N$ outcomes is denoted by 
$\Meas(N, \X)$ and it is a subset of all functions of the same kind of $\mu$, that is,
\begin{equation}
  \Meas(N, \X) \subset \Pos(\X)^{\{1,\ldots,N\}}.
\end{equation}

Given a measurement $\mu: \{1, \ldots, N \} \rightarrow \Pos(\X)$,
it is useful to associate a mapping $\Phi_{\mu}:\Lin(\X)\rightarrow\Lin(\complex^{N})$ to it,
defined as follows:
\begin{equation}
\label{eq:measurement-channel}
  \Phi_{\mu}(X) = \sum_{k=1}^{N}\ip{\mu(k)}{X}\ket{k}\bra{k},
\end{equation}
for any $X\in\Lin(\X)$. The mapping $\Phi_{\mu}$ is a quantum channel and, in fact,
it is a \emph{quantum-to-classical} channel.

In order to capture the limitation of some physical processes, we can define more restricted 
classes of measurements, which will be the object of study of this thesis.
In the definitions that follow it will be assumed that the measurements always act on a 
bipartite space $\X\otimes\Y$, where $\X$ and $\Y$ denote the complex Euclidean spaces 
underlying Alice's and Bob's systems, respectively. Although all the notions considered 
in this section could be extended to a more general scenario where more than two parties 
are involved in the measurement, here and in the rest of the thesis we restrict our attention
to the bipartite case.

\subsection{LOCC measurements}

We refer the reader to the references \cite{Mancinska13,Watrous15} for the precise
definition of an LOCC channel.
To a measurement $\mu: \{1, \ldots, N \} \rightarrow \Pos(\X\otimes\Y)$ on a bipartite
system, we associate the quantum-to-classical channel
\begin{equation}
\label{eq:measurement-channel-bipartite}
  \Phi_{\mu}(X) = \sum_{k=1}^{N}\ip{\mu(k)}{X}\ket{k}\bra{k}\otimes\ket{k}\bra{k},
\end{equation}
and we say that $\mu$ is an LOCC measurement if the channel $\Phi_{\mu}$ can be 
implemented by an LOCC protocol between Alice and Bob.

Notice that we can define different classes of LOCC, 
according to the number (finite or infinite) of rounds that compose the protocols.
For the scope of this thesis, the only important thing to notice is that all the LOCC variants
are contained in the class of separable measurement (defined in the next section).

We denote the set of all $N$-outcome LOCC bipartite measurements 
on the bipartition $(\X:\Y)$ by $\Meas_{\LOCC}(N, \X:\Y)$.

\subsection{Separable measurements}

The class of \emph{separable measurements} represents a commonly studied
approximation of the set of LOCC measurements.
A positive semidefinite operator $P\in\Pos(\X\otimes\Y)$ is said to be
\emph{separable} if it is possible to write
\begin{equation}
  P = \sum_{k = 1}^{M} Q_k \otimes R_k,
\end{equation}
for some choice of a positive integer $M$ and positive semidefinite operators
\begin{equation}
  Q_1,\ldots,Q_M \in \Pos(\X)
  \hspace*{1cm}\mbox{and}\hspace*{1cm}
  R_1,\ldots,R_M\in\Pos(\Y).
\end{equation}

\begin{definition}
Let $\X^{\reg{A}}, \X^{\reg{B}}, \Y^{\reg{A}}$, and $\Y^{\reg{B}}$ be complex
Euclidean spaces.
A completely positive mapping 
\[
  \Phi:\Lin(\X^{\reg{A}}\otimes\X^{\reg{B}})\to\Lin(\Y^{\reg{A}}\otimes\Y^{\reg{B}})
\]
is said to be a 
\emph{separable channel} if it is a trace-preserving mappings and it is possible 
to write
\begin{equation}
  \Phi = \sum_{k = 1}^{M}\Psi_{k}^{\reg{A}}\otimes\Psi_{k}^{\reg{B}},
\end{equation}
for some choice of a positive integer $M$ and collections of
completely positive mappings 
\begin{equation}
  \Psi_1^{\reg{A}},\ldots,\Psi_{M}^{\reg{A}} : \Lin(\X^{\reg{A}})\to\Lin(\Y^{\reg{A}})
  \hspace*{1cm}\mbox{and}\hspace*{1cm}
  \Psi_1^{\reg{B}},\ldots,\Psi_{M}^{\reg{B}} : \Lin(\X^{\reg{B}})\to\Lin(\Y^{\reg{B}}).
\end{equation}
\end{definition}

\begin{definition}
Let $\X$ and $\Y$ be complex Euclidean spaces and $N > 0$ be a positive integer. 
A measurement
\begin{equation}
  \mu: \{1, \ldots, N \} \rightarrow \Pos(\X\otimes\Y)
\end{equation}
is said to be a \emph{separable measurement} if the 
corresponding quantum-to-classical channel $\Phi_{\mu}$, defined as in 
Eq.~\eqref{eq:measurement-channel-bipartite}, is a separable channel.
\end{definition}

We denote the set of all $N$-outcome separable measurements on the bipartition 
$(\X:\Y)$ by $\Meas_{\Sep}(N, \X:\Y)$.
Separable measurements can be alternatively characterized as those measurements
whose measurement operators are separable, as it is formalized by the following
proposition.
\begin{prop}
\label{prop:separable-each}
Let $\X$ and $\Y$ be complex Euclidean spaces, and let $N > 0$. A measurement 
$\mu \in\Meas_{\Sep}(N, \X:\Y)$ is separable
if and only if each $\mu(k)$ is a separable operator, that is, 
$\mu(k)\in \Sep(\X:\Y)$, for each $k\in\{1, \ldots, N\}$.
\end{prop}

We refer the reader to \cite{Watrous15} for a proof of Proposition \ref{prop:separable-each},
as well as for a proof that every LOCC measurement is necessarily a separable measurement. 
From this latter fact it follows that any limitation proved to hold for 
every separable measurement must also hold for every LOCC measurement.

\subsection{PPT measurements}
\label{sec:ppt-measurements}

Another class that represents a relaxation of the set of LOCC measurements is 
the class of PPT measurements.
Let $\pt_{\negsmallspace\X}:\Lin(\X\otimes\Y)\rightarrow\Lin(\X\otimes\Y)$ be
the linear mapping representing partial transposition with respect to the
standard basis $\{\ket{0},\ldots,\ket{n-1}\}$ of $\X$. Equivalently,
\begin{equation}
  \pt_{\X}(X) = (\pt\otimes\I_{\Lin(\Y)})(X),
\end{equation}
for any operator $X\in\Lin(X\otimes\Y)$, where $\pt:\Lin(\X)\to\Lin(\X)$
is the transpose mapping.

When proving facts about PPT operators, we will use the fact that the transpose 
mapping is its own adjoint and inverse, that is,
\begin{equation}
  \ip{\pt(X)}{Y} = \ip{X}{\pt(Y)}, \qquad\mbox{for any }X,Y\in\Lin(\X),
\end{equation}
and 
\begin{equation}
  \pt(\pt(X)) = X,\qquad\mbox{for any }X\in\Lin(\X).
\end{equation}

A positive semidefinite operator $P\in \Pos(\X\otimes\Y)$ is a \emph{PPT} operator 
(short for \emph{positive partial transpose}) if it holds that
\begin{equation}
  \pt_{\negsmallspace\X}(P) \in \Pos(\X\otimes\Y).
\end{equation}
We denote the set of all PPT operators in $\Pos(\X\otimes\Y)$ as 
\begin{equation}
\PPT(\X:\Y) = \{ P \in \Pos(\X\otimes\Y) \,:\,
    \pt_{\X}(P) \in \Pos(\X\otimes\Y) \}.
\end{equation}
Notice that transpose and partial transpose are basis dependent, but the notion of PPT
is not. Also, in the definition of $\PPT(\X:\Y)$, it is irrelevant which of the two subspaces the partial transpose acts on. In fact, since the transpose is a positive mapping, we have that
\begin{equation}
  \pt_{\negsmallspace\Y}(P) \in \Pos(\X\otimes\Y)\Rightarrow
  \pt(\pt_{\negsmallspace\Y}(P)) = \pt_{\negsmallspace\X}(P) 
    \in \Pos(\X\otimes\Y).
\end{equation}

A measurement is PPT if all its operators are PPT, as formally specified by the following
definition.  
\begin{definition}
\label{def:ppt-measurements}
A measurement $\mu : \{1, \ldots, N\}\rightarrow\Pos(\X\otimes\Y)$ is called 
\emph{PPT} if it is represented by a collection
of PPT measurement operators, that is,
\begin{equation}
\mu(k) \in \PPT(\X:\Y),
\end{equation}
for all $k \in \{1,\ldots,N\}$.
\end{definition}

We denote the set of all $N$-outcome PPT measurements on the bipartition 
$(\X:\Y)$ by $\Meas_{\PPT}(N, \X:\Y)$.

Every separable operator is a PPT operator, so every separable measurement
(and therefore every LOCC measurement) is a PPT measurement as well. 

\begin{prop}
Any separable operator $P \in \Sep(\X:\Y)$ is also a PPT operator over the same
bipartition, that is, $P \in \PPT(\X:\Y)$.
\end{prop}
\begin{proof}
Suppose that $P \in \Sep(\X:\Y)$. Then it holds that
\begin{equation}
  P = \sum_{k = 1}^{M} Q_k \otimes S_k,
\end{equation}
for some choice of a positive integer $M > 0$ and collections of operators 
\begin{equation}
  Q_1,\ldots,Q_M \in \Pos(\X)
  \hspace*{1cm}\mbox{and}\hspace*{1cm}
  R_1,\ldots,R_M\in\Pos(\Y).
\end{equation}
As the transpose mapping is positive, we have
\begin{equation}
  (\pt \otimes \I_{\Lin(\Y)})(S) = \sum_{k=1}^{M}\pt(P_{k})\otimes Q_{k} 
    \in \Pos(\X\otimes\Y),
\end{equation}
and therefore $S \in \PPT(\X:\Y)$.
\end{proof}

For a positive semidefinite operator, the condition of remaining positive semidefinite under 
the operation of partial transpose is therefore a necessary condition for separability. 
It is also sufficient in $\complex^{2}\otimes\complex^{3}$ and 
$\complex^{2}\otimes\complex^{3}$ \cite{Peres1996,Horodecki1996}, 
but it is not in higher dimension, where there are entangled PPT operators. 

The Choi operator of the transpose mapping $\pt : \Lin(\complex^{n})\to\Lin(\complex^{n})$
is the \emph{swap operator} 
$W_{n} \in \Unitary(\complex^{n}\otimes\complex^{n})$, defined on the standard basis as
\begin{equation}
\label{eq:swap-operator}
  W_{n} = \sum_{i,j=0}^{n-1}\ket{i}\bra{j}\otimes\ket{j}\bra{i}.
\end{equation}
The swap operator is not positive semidefinite and therefore the transpose
mapping is not completely positive.

The primary appeal of the set of PPT measurements is its mathematical simplicity.
In particular, the PPT condition is represented by linear and positive
semidefinite constraints, which allows for an optimization over the collection
of PPT measurements to be represented by a semidefinite program.

The reader may find useful the Venn diagram of Figure~\ref{fig:classes-measurements}, 
which pictures inclusion relationships between the main classes of mesaurements
considered in the thesis. Notice that all inclusion in the diagram are known
to be strict.

\begin{figure}[!ht]
  \centering
    \def\svgwidth{200pt}
    \scalebox{.75}{\input{drawing.pdf_tex}}
    \caption{Inclusion relationships between the classes of measurements studied 
      in the thesis.}
    \label{fig:classes-measurements}
\end{figure}

%-------------------------------------------------------------------------------
\section{Convex optimization}
\label{sec:convex-optimization}
%-------------------------------------------------------------------------------

All the results of this thesis are based on a mathematical framework 
called cone programming, which generalizes semidefinite programming.
There has been an extensive range of applications of semidefinite programming
to quantum information theory, but this is not the case for  
the more general cone programming framework. 
The success of semidefinite programming in quantum information comes from the fact 
that many quantum primitives (states, channels, global measurements) 
can be represented within the cone of positive semidefinite operators with the addition of 
simple linear constraints. 
Problems in which one optimizes over the cone of separable operators, such as 
the problem of discriminating states by separable measurements considered in this thesis, 
do not have a characterization in the framework of semidefinite programming and 
for such problems the full expressivity of the general cone programming framework is required.  
In this section we review basic definitions in convex analysis and convex optimization.

Let $\V$ be an arbitrary vector space over the real or complex number.
A subset $\K$ of $\V$ is a \emph{cone} if $u\in\K$ implies that $\lambda u \in \K$,
for all scalar $\lambda \geq 0$. A cone $\K$ is convex if $u,v\in\K$ implies that
$u + v \in \K$.
A cone program (also known as a \emph{conic program}) expresses the
maximization of a linear function over the intersection of an affine subspace
and a closed convex cone in a finite-dimensional real inner product
space \cite{Boyd04}. 

When describing a cone program, it is sometimes convenient to compose small closed convex 
cones in a bigger one, and in order to do that, one can make use of the following fact. 
\begin{fact}
\label{fact:direct-sum-closed}
The direct sum $\K \oplus \K'$ of two closed convex cones $\K$ and $K'$ is a 
closed convex cone. 
\end{fact}

Linear programming (LP) and semidefinite programming (SDP) are special cases of cone
programming: in linear programming, the closed convex cone over which the
optimization occurs is the positive orthant in $\real^n$, while in semidefinite
programming the optimization is over the cone $\Pos(\complex^n)$ of positive
semidefinite operators on $\complex^n$.
In the case of semidefinite programming, the finite-dimensional real inner
product space is the real vector space $\Herm(\complex^n)$ of Hermitian
operators on $\complex^n$, equipped with the Hilbert-Schmidt inner product.

\subsection*{Linear programming}
\label{sec:linear-programming}
Let $n,m$ be positive integers, $c\in\real^{n}$ and $b\in\real^{m}$ be vectors
of real numbers, and $A \in\real^{n\times m}$ be a matrix with real entries. 
Then a \emph{linear program} is defined by the triple $(c,b,A)$ and by the 
following pair of optimization problems.
\begin{center}
  \begin{minipage}{2in}
    \centerline{\underline{Primal linear program}}\vspace{-7mm}
    \begin{align*}
      \text{maximize:}\quad & \ip{c}{x}\\
      \text{subject to:}\quad & A x = b,\\
      & x \geq 0, x\in\real^{n}.
    \end{align*}
  \end{minipage}
  \hspace*{1.5cm}
  \begin{minipage}{2.4in}
    \centerline{\underline{Dual linear program}}\vspace{-7mm}
    \begin{align*}
      \text{minimize:}\quad & \ip{b}{y}\\
      \text{subject to:}\quad & A^{\t}y \geq c,\\
      & y\in\real^{m}.
    \end{align*}
  \end{minipage}
\end{center}


\subsection*{Semidefinite programming}
\label{sec:semidefinite-programming}

Let $\X$ and $\Y$ be complex Euclidean spaces, $A\in\Herm(\X)$ and $B\in\Herm(\Y)$
be Hermitian operators, and $\Phi:\Lin(\X)\to\Lin(\Y)$ be a Hermiticity preserving mapping.
A \emph{semidefinite program} is defined by the triple $(A,B,\Phi)$ and by 
the following pair of optimization problems.
\begin{center}
  \begin{minipage}{2in}
    \centerline{\underline{Primal semidefinite program}}\vspace{-7mm}
    \begin{align*}
      \text{maximize:}\quad & \ip{A}{X}\\
      \text{subject to:}\quad & \Phi(X) = B,\\
      & X \in \Pos(\X).
    \end{align*}
  \end{minipage}
  \hspace*{1.5cm}
  \begin{minipage}{2.4in}
    \centerline{\underline{Dual semidefinite program}}\vspace{-7mm}
    \begin{align*}
      \text{minimize:}\quad & \ip{B}{Y}\\
      \text{subject to:}\quad & \Phi^{\ast}(Y) \geq A,\\
      & Y\in\Herm(\Y).
    \end{align*}
  \end{minipage}
\end{center}

\subsection*{Cone programming}
\label{sec:cone-programming}
For the purposes of the present thesis, it is sufficient to consider only cone
programs defined over spaces of Hermitian operators (with the Hilbert-Schmidt
inner product).
In particular, let $\Z$ and $\W$ be complex Euclidean spaces and let 
$\K\subseteq\Herm(\Z)$ be a closed, convex cone.
For any choice of a linear map
$\Phi:\Herm(\Z)\rightarrow\Herm(\W)$ and
Hermitian operators $A\in\Herm(\Z)$ and $B\in\Herm(\W)$, one has a \emph{cone
program} defined by $(A,B,\Phi)$ and represented by the following pair of 
optimization problems.
\begin{center}
  \begin{minipage}{2in}
    \centerline{\underline{Primal cone program}}\vspace{-7mm}
    \begin{align*}
      \text{maximize:}\quad & \ip{A}{X}\\
      \text{subject to:}\quad & \Phi(X) = B,\\
      & X \in \K.
    \end{align*}
  \end{minipage}
  \hspace*{1.5cm}
  \begin{minipage}{2.4in}
    \centerline{\underline{Dual cone program}}\vspace{-7mm}
    \begin{align*}
      \text{minimize:}\quad & \ip{B}{Y}\\
      \text{subject to:}\quad & \Phi^{\ast}(Y) - A \in \K^{\ast},\\
      & Y\in\Herm(\W).
    \end{align*}
  \end{minipage}
\end{center}

Here, $\K^{\ast}$ denotes the \emph{dual cone} to $\K$, defined as
\begin{equation}
\label{eq:dual-cone}
  \K^{\ast} = \{Y\in\Herm(\Z)\,:\,\ip{X}{Y} \geq 0\;\:\text{for all $X\in\K$}\},
\end{equation}
and $\Phi^{\ast}:\Herm(\W)\rightarrow\Herm(\Z)$ is the adjoint mapping to
$\Phi$.

Notice that the above programs are often presented in different (although equivalent) 
ways in most convex optimization textbooks.
In fact, the way the programs are presented in this thesis differs from 
the so-called \emph{standard form}.
This choice is due to the fact that the standard form is less suitable for
programs that describe quantum information problems. 

In order to see how semidefinite programming is a special case of cone programming, 
let us observe the following elementary fact that comes from the definition of 
positive semidefinite operators.
\begin{fact}
\label{fact:pos-self-dual}
The cone of positive semidefinite operators is self-dual, that is, 
\begin{equation}
\Pos(\X) = (\Pos(\X))^{\ast},
\end{equation}
for any complex Euclidean space $\X$.
\end{fact}
In light of this, we have that $\K = \K^{\ast} = \Pos(\X)$ and we can write the
constraint from the cone programming dual problem as
$\Phi^{\ast}(Y) - A \in \Pos(\X)$, that is, $\Phi^{\ast}(Y) \geq A$.

Most of the definitions we introduce in the rest of the section holds for all linear, 
semidefinite, and more general cone programs.
For a cone program defined by $(A,B,\Phi)$, one defines the 
\emph{feasible sets} $\A$ and $\B$ of the primal and dual problems as
\begin{equation}
  \A = \bigl\{ X \in \K : \Phi(X) = B\bigr\} 
  \qquad \text{and} \qquad 
  \B = \bigl\{ Y \in \Herm(\W) : \Phi^{\ast}(Y) - A \in \K^{\ast} \bigr\}.
\end{equation}
One says that the associated cone program is \emph{primal feasible} if 
$\A \neq \emptyset$, and is \emph{dual feasible} if $\B \neq \emptyset$. 
The function $X \mapsto \ip{A}{X}$ from $\Herm(\Z)$ to $\real$ is called the 
\emph{primal objective function}, and the function $Y \mapsto \ip{B}{Y}$ from 
$\Herm(\W)$ to $\real$ is called the \emph{dual objective function}.
The \emph{optimal values} associated with the primal and dual problems are
defined as
\begin{equation}
  \label{eq:alpha-and-beta}
  \alpha = \sup \bigl\{ \ip{A}{X} : X \in \A \bigr\} 
  \qquad \text{and} \qquad 
  \beta = \inf \bigl\{ \ip{B}{Y} : Y \in \B \bigr\},
\end{equation}
respectively.
(It is conventional to interpret that $\alpha = -\infty$ when $\A = \emptyset$
and $\beta = \infty$ when $\B = \emptyset$.)
The property of \emph{weak duality}, which holds for all cone programs, is
that the primal optimum can never exceed the dual optimum.

\begin{prop}[Weak duality for cone programs]
\label{prop:weak-duality-cone}
  For any choice of complex Euclidean spaces $\Z$ and $\W$, a closed, convex
  cone $\K\subseteq\Herm(\Z)$, Hermitian operators $A\in\Herm(\Z)$ and
  $B\in\Herm(\W)$, and a linear map $\Phi:\Herm(\Z)\rightarrow\Herm(\W)$, it
  holds that $\alpha \leq \beta$, for $\alpha$ and $\beta$ as defined in
  \eqref{eq:alpha-and-beta}.
\end{prop}

\begin{proof}
The proposition is trivial in case $\A = \emptyset$ (which implies that 
$\alpha = -\infty)$ or $\B = \emptyset$ (which implies that $\beta = \infty$), 
so we will restrict our attention to the case that both $\A$ and $\B$ are 
nonempty. 
For any choice of $X \in \A$ and $Y \in \B$, one must have $X \in \K$ and
$\Phi^{\ast}(Y) - A \in \K^{\ast}$, and therefore
$\ip{\Phi^{\ast}(Y) - A}{X} \geq 0$.
It follows that
\begin{equation}
  \ip{A}{X} = \ip{\Phi^{\ast}(Y)}{X} - \ip{\Phi^{\ast}(Y) - A}{X}
  \leq \ip{Y}{\Phi(X)} = \ip{B}{Y}.
\end{equation}
Taking the supremum over all $X \in \A$ and the infimum over all 
$Y \in \B$ establishes that $\alpha \leq \beta$.
\end{proof}

Weak duality implies that every dual feasible operator $Y \in \B$ provides an
upper bound of $\ip{B}{Y}$ on the value $\ip{A}{X}$ that is achievable over all
choices of a primal feasible operator $X \in \A$, and likewise every primal feasible 
operator $X \in \A$ provides a lower bound of $\ip{A}{X}$ on the value 
$\ip{B}{Y}$
that is achievable over all choices of a dual feasible solution $Y \in \B$. 
In other words, it holds that
$\ip{A}{X} \leq \alpha \leq \beta \leq \ip{B}{Y}$,
for every $X \in \A$ and $Y \in \B$. 

Some cone programs also satisfy 
the property of \emph{strong duality}, which holds when
the optimal values of the primal program and of the dual program are equal, and 
the optimal value of the dual program is attained.
We abstain from a formal treatment of the conditions that guarantee
strong duality. Even though all cone programs described in the following chapters 
satisfy strong duality, none of our results depend on that.