text:
\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsmath}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{theorem}{Theorem}
\newtheorem{example}{Example}
\newtheorem{condition}{Condition}
\newtheorem{proposition}{Proposition}

\newtheorem{lemma}{Lemma}
\usepackage{color}
\usepackage{comment}
\usepackage{calrsfs}
\usepackage{latexsym}
\usepackage{tikz}
\usepackage{tikz-qtree}
\usepackage{mathrsfs}
\usepackage{url}
\usepackage{titlesec}
\usepackage[colorlinks=true]{hyperref}
\hypersetup{
    colorlinks,
    citecolor=black,
    filecolor=black,
    linkcolor=blue,
    urlcolor=blue
}
\usepackage{alltt}
\usepackage{ulem}
\def\st{\noindent}
\renewcommand\em{\it}
\renewcommand\emph{\textit}
\newcommand\red[1]{{\color{red}#1}}
\newcommand\blue[1]{{\color{blue}#1}}
\newcommand\cancelr[1]{{\color{red}\sout{#1}}}

% define subsubsubsection
\titleclass{\subsubsubsection}{straight}[\subsection]

\newcounter{subsubsubsection}[subsubsection]
\renewcommand\thesubsubsubsection{\thesubsubsection.\arabic{subsubsubsection}}
\renewcommand\theparagraph{\thesubsubsubsection.\arabic{paragraph}} % optional; useful if paragraphs are to be numbered

\titleformat{\subsubsubsection}
  {\normalfont\normalsize\bfseries}{\thesubsubsubsection}{1em}{}
\titlespacing*{\subsubsubsection}
{0pt}{3.25ex plus 1ex minus .2ex}{1.5ex plus .2ex}

\makeatletter
\renewcommand\paragraph{\@startsection{paragraph}{5}{\z@}%
  {3.25ex \@plus1ex \@minus.2ex}%
  {-1em}%
  {\normalfont\normalsize\bfseries}}
\renewcommand\subparagraph{\@startsection{subparagraph}{6}{\parindent}%
  {3.25ex \@plus1ex \@minus .2ex}%
  {-1em}%
  {\normalfont\normalsize\bfseries}}
\def\toclevel@subsubsubsection{4}
\def\toclevel@paragraph{5}
\def\toclevel@paragraph{6}
\def\l@subsubsubsection{\@dottedtocline{4}{7em}{4em}}
\def\l@paragraph{\@dottedtocline{5}{10em}{5em}}
\def\l@subparagraph{\@dottedtocline{6}{14em}{6em}}
\makeatother

\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4}

%\newcommmand{\red}[1]{\textcolor{red}{#1}}
%\renewcommand\red[1]{{\color{red}#1}}
%opening
\title{AST generator specification}
\author{Evgenii Balai}
\def\no{{\bf not}\;}
\begin{document}

\maketitle
\st

\tableofcontents
\section{Vocabulary}

\begin{itemize}
\item \textit{identifier} -  a sequence of alphanumeric or underscore characters starting with a letter.
\item \textit{numeral} - a sequence of characters used to represent a number. Numerals can be in one of the following forms:
\begin{enumerate}
\item $d_1\ldots d_k$
\item $d_1\ldots d_n.d_1\ldots d_m$
\end{enumerate}
possible preceded by a minus sign,
where each $d_i$ is a digit, $k > 0, n\ge 0$ and $m >0$.
\end{itemize}

\section{Input Specification}
The input consists of the following:
\begin{enumerate}
\item lexicon file (defined in section \ref{lf})
\item grammar file (defined in section \ref{gf})
\item source file (defined in section \ref{sf})
\end{enumerate}

\subsection{Lexicon file}\label{lf}

A lexicon file is an ASCII file that contains a specification of types of terminal symbols (\textit{lexems}) that may occur in a program file.
Each lexem type is declared as
\begin{equation}\label{lexdef}
lexem\_type\_name = regex
\end{equation}
where $lexem\_type\_name$ is an identifier and $regex$ is a regular expression following python syntax\cite{pythonre} whose special characters are limited to $.$, $*$, $+$, $?$, $\{m\}$, $\{m,n\}$, $[]$, $\wedge$(only inside$[]$), $\backslash$,  or $|$.

We will say that statement (\ref{lexdef}) \textit{defines} a lexem type named $lexem\_type\_name$.

Lexicon file may contain multiple declarations of the form (\ref{lexdef}), one per line, where no lexem type name occurs in the left hand side of a statement more than once, and no lexem type name is a member of the set $\{id, num, space\}  $.

\subsection{Grammar File}\label{gf}
A grammar file is an ASCII file that contains a specification of non-terminals occurring in the produced abstract syntax tree as well as the desired structure of the tree. Every grammar file must be associated with a lexicon file. We will refer to the set of lexem type names defined in the file as $S_L$.

Non-terminals are specified  by  statements of the form

\begin{equation}\label{nontd}
nt(\beta_1~\ldots~\beta_m) ::= \alpha_1(\tau_1)~\ldots~\alpha_n(\tau_n)
\end{equation}
where
\begin{enumerate}
\item $nt$ is an identifier which is not a member of the set $\{id, num, space\}\cup S_L$ sometimes referred to as a \textit{non-terminal symbol}, or simply \textit{non-terminal};
\item $n\ge 1$;
\item each $\alpha_i$  is an identifier;
\item each $\tau_i$ is an identifier;
\item $\beta_1~\ldots~\beta_m$ ($m \ge 1$) is a sequence  where
 each  $\beta_1$  is an identifier and each $\beta_i$ for $i>1$
is in one of the following forms:
\begin{enumerate}
\item an identifier that is an element of the sequence   $\tau_1\ldots \tau_n$;
\item $f(c)$, where $f$ is a member of the set of identifiers $\{cut\_root\}$ and c is an element of  the sequence   $\tau_1\ldots \tau_n$.
If $f = cut\_root$, $c$ must not be a lexeme type name;
\end{enumerate}
\item  if $\beta_i$ is of one of the forms $\tau_j$ or $f(\tau_j)$, then  $\tau_j$ must occur in the sequence  $\tau_1\ldots \tau_n$ exactly once;
\item if $\beta_1$ is of one of the forms $\tau_j$ or $f(\tau_j)$, then $m$ must be equal to $1$, otherwise $\beta_1$ is an identifier also referred to as \textit{a label}.
\end{enumerate}

An informal reading of the rule \ref{nontd} is given below.
\begin{enumerate}

\item  Suppose $\beta_1 \in \{\tau_1,...,\tau_m\}$ .
In this case $n = 1$, and the rule is of the form:

$$nt (\tau_i) ::= \alpha_1(\tau_1) ... \alpha_m(\tau_m)$$.

where $\tau_i \in \{\tau_1,\ldots,\tau_m\}$

The reading of the rule is:

An expression of type $nt$ with tree $\tau_i$ can be written by writing an expression of type $\alpha_1$ with tree $\tau_1$, followed by an expression of type $\alpha_2$ with tree $\tau_2$, \ldots, followed by an expression of type $\alpha_n$ with tree $\tau_n$.

For a terminal symbol $t$ the phrase \textit{expression of type $t$} should be understood as $t$ itself.

For example, the reading of the rule
$$T2(M) = T3(M)$$
is \textit{an expression of type $T2$ with tree $M$ can be written by writing an expression of type $T3$ with tree $M$.}

\item  Suppose  $\beta_1 \not\in \{\tau_1,...,\tau_m\}$ .

In this case the reading is:

An expression of type $nt$ with the tree corresponding to the list $(\beta_1,...,\beta_n)$ (see section \ref{treesec}) can be written by writing an expression of type $\alpha_1$ with tree $\tau_1$, followed by an expression of type $\alpha_2$ with tree $\tau_2$, \ldots, followed by an expression of type $\alpha_n$ with tree $\tau_n$.

For example, the reading of the rule
$$T1(add~M1~M2)~::=~T2(M1)~add\_op(A)~T1(M2)$$
is \textit{an expression of type $T1$ with tree~$(add~M1~M2)$ can be written by writing an expression of type $T2$ with tree $M1$, followed by an expression of type $add\_op$ with tree $A$, followed by an expression of type $T1$ with tree $M2$.}

\end{enumerate}

We allow a shorthand $\alpha$ that stands for $\alpha(\alpha)$ to be an element of the sequence on the right hand side of the statement (\ref{nontd}).

We will refer to the sequence of statements of the form(2) as \textit{a grammar}, if each $\alpha_i$ is a  non-terminal  name occurring on the left hand side of another statement in the sequence, or a member of the set$\{id, num, space\}\cup S_L$ . The non-terminal symbols occurring in the statements of the grammar are referred to as the \textit{non-terminal symbols} (or the \textit{non-terminals}) \textit{of the grammar}.
The non-terminal symbol occurring on the left hand side of the first statement of $G$ is referred to as the \textit{starting symbol of the grammar}. The members of $S_L$ are referred to as the \textit{terminal symbols} (or the \textit{terminals}) \textit{of the grammar}.  Both terminals and non-terminals of a grammar are referred to as \textit{symbols of the grammar}.
Finally, the labels occurring in the statements of a grammar are referred to as the \textit{labels of the grammar}.

Let $G$ be a grammar.
We define a leveling function $|\ |$ of $G$ that maps non-terminals of $G$ onto a set of non-negative integers in the range [0..n].
A leveling function is called reasonable if for each statement of the form
$$nt(\beta_1~\ldots~\beta_m) ::= \alpha_1(\tau_1)$$
such that  $\alpha_1$ is a non-terminal, $|nt|> |\alpha_1|$.
$G$ is called \textit{stratified}, if there exists a reasonable leveling of $G$.

A grammar file contains a stratified grammar, one  statement per line.

\subsection{Source File}\label{sf}
A source file is a file containing arbitrary collection of ASCII characters.

\subsection{Input Examples}\label{ie}
\subsubsection{Arithmetic Expression}
In this example we will define an arithmetic expression whose operands are integer numbers  by means of lexicon and grammar defined in sections \ref{lf} and \ref{gf} and give an example of an arithmetic expression that can be used as contents of a source file.

\subsubsubsection{Lexicon File}\label{alex}
\begin{verbatim}
num = -?([1-9][0-9]+|0)
add_op = \+|-
mult_op = :|\*
left_paren = \(
right_paren = \)
\end{verbatim}
\subsubsubsection{Grammar File}\label{agram}

\begin{verbatim}
expr(T1) ::= T1
T1(T2) ::= T2
T1(add M1 M2) ::= T2(M1) add_op T1(M2)
T2(mult Op1 Op2) ::= T3(Op1) mult_op T2(Op2)
T2(T3) ::= T3
T3(expr) ::= left_paren expr right_paren
T3(num) ::= num
\end{verbatim}

\subsubsubsection{Source File}\label{asf}
\begin{verbatim}
1+2*3
\end{verbatim}
\subsubsection{Chess Notation}
In this example we will define Algebraic Chess Notation \cite{chess} by means of lexicon and grammar defined in sections \ref{lf} and \ref{gf} and give an example of a game described in this notation.
\subsubsubsection{Lexicon file}\label{clex}
\begin{verbatim}
figure = K|Q|R|B|N
file = [a-h]
rank = [1-8]
cell = [a-h][1-8]
capture_char = x
space = \s
dot = \.
en_passant = e\.p\.
natural_number = [1-9][0-9]+
move_id = [1-9][0-9]+\.
long_castling = 0-0-0
short_castling = 0-0
plus = \+
pound_sign = #
end = 1-0|1/2-1/2|0-1
\end{verbatim}
\subsubsubsection{Grammar file}\label{cgram}
\begin{verbatim}
game(game move_d) ::= move_d
game(game move_d cut_root(G)) ::= move_d   game(G)
move_d(move move_id M1 M2) ::= move_id  move(M1) move(M2)
move_d(game_over  move_id move) ::= move_id move end
move_d(game_over  move_id checkmate) ::= move_id checkmate
move(pawn_move cell) ::= cell
move(move figure_spec cell) ::= figure_spec cell
move(capture figure_spec cell) ::= figure_spec capture_char cell
move(pawn_capture file cell) ::= file capture_char cell
move(pawn_special_capture) ::= file capture_char cell en_passant
move(promotion cell figure) ::= cell figure
move(castling long_castling) ::= long_castling
move(castling short_castling) ::= short_castling
move(checkmate c) ::= checkmate(c)
move(check c) ::= check(c)
check(check move) ::= move plus
checkmate(checkmate move) ::= move pound_sign
figure_spec(fig figure) ::= figure
figure_spec(fig figure file) ::= figure file
figure_spec(fig figure rank) ::= figure rank
figure_spec(fig figure cell) ::= figure cell
\end{verbatim}

\subsubsubsection{Source File}\label{csf}
\begin{comment}
\begin{verbatim}

1. e4 c5 2. Nf3 d6 3. Bb5 Bd7 4. Bxd7 Qxd7 5. c4 Nc6 6. Nc3 Nf6
7. 0-0 g6 8. d4 cxd4 9. Nxd4 Bg7 10. Nde2 Qe6  11. Nd5 Qxe4
12. Nc7+ Kd7 13. Nxa8 Qxc4 14. Nb6+ axb6 15. Nc3 Ra8 16. a4 Ne4
17. Nxe4 Qxe4 18. Qb3 f5 19. Bg5 Qb4 20. Qf7 Be5 21. h3 Rxa4
22. Rxa4 Qxa4 23. Qxh7 Bxb2 24. Qxg6 Qe4 25. Qf7 Bd4 26. Qb3 f4
27. Qf7 Be5 28. h4 b5 29. h5 Qc4 30. Qf5+ Qe6 31. Qxe6+ Kxe6
32. g3 fxg3 33. fxg3 b4 34. Bf4 Bd4
35. Kh1! b3 36. g4 Kd5 37. g5 e6 38. h6 Ne7 39. Rd1 e5 40. Be3 Kc4
41. Bxd4 exd4 42. Kg2 b2 43. Kf3 Kc3 44. h7 Ng6 45. Ke4 Kc2
46. Rh1 d3 47. Kf5 b1=Q 48. Rxb1 Kxb1 49. Kxg6 d2 50. h8=Q d1=Q
51. Qh7 b5 52. Kf6 Kb2 53. Qh2 Ka1 54. Qf4 b4 55. Qxb4 Qf3+
56. Kg7 d5 57. Qd4 Kb1 58. g6 Qe4 59. Qg1 Kb2 60. Qf2+ Kc1
61. Kf6 d4 62. g7 1-0
\end{verbatim}
\end{comment}

\begin{verbatim}
1. e4 e5 2. Qh5 Nc6 3. Bc4 Nf6 4. Qxf7#
\end{verbatim}

\section{Output specification}
The output is obtained in two steps
\begin{enumerate}
\item \textit{Lexing}.  \textit{Lexer Module} takes a source file and lexicon file and outputs a sequence of annotated lexemes as specified in section \ref{lex}.
\item \textit{Parsing}. \textit{Parser Module} takes an output of the lexer module and grammar file as an input and returns an abstract tree as specified in section \ref{pars}.
\end{enumerate}

\subsection{Lexing}\label{lex}
In addition to thee  set of lexeme types  declared in the lexicon file, denoted by $S_L$, we introduce two more lexemes: $id$, $num$ and $spaces$.  For each lexeme $l$, we define a regular expression $\mathcal{R}_L(l)$ as follows:

\begin{enumerate}
\item if $l \in S_L$, $\mathcal{R}_L(l) = expr$, where $expr$ is the regular expression  on the right hand side of the statement
$$l = expr$$
appearing in the lexicon file;
\item if $l$ is $id$, $\mathcal{R}_L(l)$ is
                               $$[a-zA-Z]\backslash w^*$$
\item if $l$ is $num$, $\mathcal{R}_L(l)$ is
                $$-?[1-9][0-9]* |-?0?\backslash.[0-9]+ | -?[1-9][0-9]*\backslash.[0-9]+$$
\item if $l$ is $spaces$, $\mathcal{R}_L(l)$ is
                $$\backslash s+$$
\end{enumerate}

We will say that a string $S$ \textit{matches} a regular expression $E$ if $S$ is a member of the set of strings specified by  the python regular expression
$$\wedge (E) \backslash Z $$
In other words, $S$ matches $E$ if the following python code prints \texttt{True}, when being run on a   python3.4 interpreter:
\begin{alltt}
import re
regex = re.compile(r"^\((E)\)\textbackslash{}Z")
print(regex.match("\(S\)") != None)
\end{alltt}

The symbols $\wedge$ and $\$$ are added to $E$ to ensure that the whole string, but not its prefix or suffix are matched. More details on  the syntax and semantics of python regular expressions can be found in \cite{pythonre}.

Let $I$ be the string that represents the contents of the input file.
The \textit{lexing sequence} of $I$ with respect to the lexicon file $L$ is a sequence of pairs $(l_1,s_1),\ldots (l_n,s_n)$, such that:

\begin{enumerate}
\item each $l_i$ is a lexeme which is a member of the set $S_L \cup \{id,num\}$;
\item each $s_i$ is a string;
\item $s_1+\ldots+s_n$ = $I$ (where + denotes concatenation);
\item for each $1 \le i  \le n$, $s_i$ matches $\mathcal{R}_L(l_i)$;
\item for each $1 \le i \le n$, $s_i$ is the longest prefix of $s_i+\ldots+s_n$ such that $s_i$ matches  $\mathcal{R}_L(l)$ for some  $l \in  S_L \cup \{id,num\}$
\end{enumerate}

We will refer to each element of the lexing sequence as an \textit{annotated lexeme}.

\subsection{Parsing}\label{pars}
Given a sequence of annotated lexemes  $(l_1,s_1),\ldots, (l_n,s_n)$ and a grammar $G$  the goal of parsing is to produce an abstract syntax tree  as defined in this section.

\subsection{Abstract Syntax Trees for a  Grammar}

 We say that $T$ is \textit{an abstract syntax tree for a grammar $G$} if $T$ is a finite rooted ordered\footnote{A finite tree  is \textit{ordered} if the children of each node of the tree are pairwise distinct and totally ordered. That is, we can define a correspondence between the children of a node $V$ of the tree and the set of natural numbers \{1,\ldots,\ldots,$n$\}, and refer to the children of $V$  as $1^{st}, 2^{nd}, \ldots, n^{th}$ child of $V$.}  tree  whose non-leaf nodes are labeled by  labels of $G$ and whose leafs are labeled by terminals of $G$.

Let $T_1$ and $T_2$ be two trees of $G$. We say $T_1$ is a \textit{subtree} of $T_2$ if the following three conditions hold:

\begin{enumerate}
\item the root of $T_2$ is a node of $T_1$;
\item the nodes of $T_2$  different from $r$ are the descendants of $r$ in $T_1$;
\item every edge of $T_2$ is an edge of $T_1$.
\end{enumerate}

\begin{example}\label{ex1}
Consider the tree $T$ shown below\footnote{The children of nodes in the tree are shown from left to right according to their order.} :
\begin{center}
\Tree [.$add$ $(num,1)$ [.$mult$ $(num,2)$  $(num,3)$ ]  [.$mult$ $(num,4)$  $(num,5)$ ]]
\end{center}

The tree $T$ has 8 subtrees: $T$ itself, the five trees containing only one node which is a leaf of $T$ and two trees rooted at the nodes labeled by $mult$ shown below:

\begin{center}
\Tree [.$mult$ $(num,2)$  $(num,3)$ ]    \Tree [.$mult$ $(num,4)$  $(num,5)$ ]
\end{center}

\end{example}
If $T$ is an abstract tree of $G$, by $cut\_root$ we define a sequence of trees i-th of which is rooted at i-th child of the root of $T$.

\begin{example}
If $T$ is a tree given in example \ref{ex1}, $cut\_root$ is a sequence of three trees shown below (from left to right):
\begin{center}
\Tree [.$(num,1)$ ]  \Tree [.$mult$ $(num,2)$  $(num,3)$ ]  \Tree [.$mult$ $(num,4)$  $(num,5)$ ]
 \end{center}
\end{example}

\subsection{Parsing output specification}

Let $G$ be a stratified grammar with a symbol $S$,  $(l_1,s_1),\ldots, (l_n,s_n)$ be a lexing sequence denoted by $L$, $b$ and $e$ be two natural numbers such that $1 \le b \le e \le n$.

 By $R_{G,L}(S,b,e)$ we denote an abstract syntax tree for $G$ satisfying one of the following two conditions:
\begin{enumerate}
\item if $b = e$ and $S$ is  $l_b$,
 $R_{G,L}(S,b,e)$ contains only one node labeled by $(l_b, s_b)$

\item if S is a non-terminal of $G$, and there is a statement in $G$ of the form
$$ S(\beta_1 \ldots \beta_m) = \alpha_1(\tau_1) \ldots  \alpha_n(\tau_n)  $$
where
\begin{itemize}
\item $l_b \dots l_e = l^1_1,l^1_2 \ldots l^1_{k_1} \ldots l^n_1 \ldots l^n_{k_n}$ for some  $1 \le k_1,\ldots,k_n \le (e-b+1)$,
\item for each $1\le i \le n$ there exists a tree denoted by $$R_{G,L}(\alpha_i,k_1+ \ldots + k_{i-1}+1, k_1+ \ldots + k_{i})$$
\end{itemize}
then
\begin{itemize}
\item if $\beta_1 = \tau_j$ for some $ 1\le j \le n$, then

  $R_{G,L}(S,b,e)$ is $R_{G,L}(\alpha_j,k_1+ \ldots + k_{j-1}+1, k_1+ \ldots + k_{j})$

\item if $\beta_1 \not= \tau_j$ and  $\beta_1 \not= cut\_root(\tau_j)$   for all $ 1\le j \le n$,

  then $R_{G,L}(S,b,e)$ is a tree whose root $r$ is labeled by $\beta_1$ and the tree $T_i$ whose root is the $i^{th}$ child of $r$ is obtained as follows:
 \begin{enumerate}
 \item Let $f:\{2..m\} \to \{1..n\}$ be a function such that for any $j \in \{2..m\}$ $\beta_j = \tau_{f(j)}$ or  $\beta_j = cut\_root(\tau_{f(j)})$.
 \item For each $1\le j \le n$ let $A_j$ be an abstract syntax tree denoted by $R(\alpha_j,k_1+ \ldots + k_{j-1}+1, k_1+ \ldots + k_{j})$
 \item Let $c:\{2..m\} \to \mathbb{N}$ be a function defined as follows:

\[
c(u) =
\begin{cases}
             1,& \beta_u \in \{\tau_1 \dots \tau_n\} \\
  \text{the number of children of the root of } T_{f(u)},          & \text{otherwise}
\end{cases}
\]
\item Let $p$ be the largest number in the range $[1..m]$ such that $$c(2) + \ldots + c(p) < i$$
\item if $\beta_{p+1}$ is of the form $cut\_root(\tau_j)$, $T_i$ is the $(i - (c(2) + \ldots + c(p)))^{th}$ child of $A_p$;
      otherwise $T_i$ is $A_p$

 \end{enumerate}
 \end{itemize}
 \end{enumerate}

We will refer  $R_{G,L}(S,b,e)$ as  an abstract syntax tree of $G$ \textit{matching the lexing sequence $l_b, \ldots, l_e$ on $S$}.
The result of the parsing is defined to be the abstract syntax tree matching the lexing sequence $l_1, \ldots, l_n$ on the starting symbol of $G$.

\subsection{Trees Representation}\label{treesec}
Let $T$ be an abstract syntax tree .
In the implementation, $T$ is  represented as follows:
\begin{enumerate}
\item if $T$ is empty, it is represented by an empty list;
\item if $T$ consists of only one node labeled by $l$, it is represented the label $l$;
\item if a tree consists of more then one node, it is represented by the list $[r,t_1,\ldots,t_n]$, where $r$ is a label of the root of $T$ and  $t_i$ is the representation of the subtree of $T$ rooted at $i^{th}$ child of $T$
\end{enumerate}

\subsection{Examples}
\subsubsection{Arithmetic Expression Tree}

The lexing sequence for the  lexicon file given in section \ref{alex} and source file given in section \ref{asf} is:
\begin{verbatim}
(num '1'), (add_op, '+'), (num, '2'), (mult_op,'*'), (num, '3')
\end{verbatim}

Given the grammar file in section \ref{agram}, the corresponding abstract syntax tree is represented by the list:
\begin{verbatim}
[add, (num,'1'),[mult,(num,'2'),(num,'3')]]
\end{verbatim}
\subsubsection{Chess Game Tree}

The lexing sequence for the  lexicon file given in section \ref{clex} and source file given in section \ref{csf} is:

\begin{verbatim}
(move_id, '1.'), (spaces, ' ') (cell, 'e4'), (spaces, ' '),
(cell, 'e5'), (spaces, ' '), (move_id, '2.'), (spaces, ' '),
(figure, 'Q'), (cell, 'h5'), (space, ' '), (figure, 'B'),
(cell, 'c6'), (spaces, ' '), (move_id, '3.'), (spaces, ' '),
(figure, 'B'), (cell, 'c4'), (spaces, ' '),  (figure, 'N'),
(cell, 'f6'), (spaces, ' '), (move_id, '4.'), (spaces, ' '),
(figure, 'Q'), (capture_char, 'x'), (cell, 'f7'),
(pound_sign, '#')
\end{verbatim}

\st
Given the grammar file in section \ref{cgram}, the corresponding abstract syntax tree  is represented by the list\footnote{All lexemes annotated as spaces are dropped from the lexing sequence before parsing is done}:

\begin{verbatim}
[ game,
      [move, [(move_id '1.')], [pawn_move [(cell 'e4')] ],
                                [pawn_move [(cell 'e5')] ] ],

      [move, [(move_id '2.')], [move [fig [(figure 'Q')]]
                                     [(cell 'h5')] ],
                                     [move, [fig [(figure 'N')]],
                                     [(cell 'c6')]]],

      [move, [(move_id '3.')], [move [fig [(figure 'B')]],
                                               [(cell 'c4')] ],
                                         [move, [fig [(figure 'N') ]],
                                         [(cell 'f6')]]],

      [checkmate   [move, [(move_id '4.')],
                                       [capture [fig [(figure 'Q')] ],
                                       [(cell 'f7')] ] ] ]

]
\end{verbatim}

\bibliography{mylib}
\bibliographystyle{plain}
\end{document}

ext: tex

max_stars_repo_name: iensen/genparser

max_issues_repo_name: iensen/genparser

max_forks_repo_name: iensen/genparser


text:
\documentclass[12pt,a4paper]{article}

\usepackage{amssymb}
\usepackage{amsmath}
% These packages give access to frequently used mathematical
% symbols, such as blackboard bold for real and complex numbers.
%\usepackage{graphicx}

%\usepackage[dvips]{graphicx} % For postscript figures under latex.

\usepackage[pdftex]{graphicx} % For jpg etc figures under pdflatex.

\linespread{1.6}
% gives double-spacing

\numberwithin{equation}{section}

\tolerance = 10000
% this allows wider interword spaces without complaints

\setlength{\oddsidemargin}{8mm}
\setlength{\evensidemargin}{8mm}
\setlength{\topmargin}{-5mm}

\setlength{\textwidth}{145mm}
\setlength{\textheight}{220mm}

\begin{document}

\vglue 1cm

\begin{center}
{\Huge
\bf
Characterisation of
\\
\vspace{5mm}
Multipartite Entanglement}

\vskip 1cm

{\Large
G14PJA
\\
Mathematics 3rd Year Project
\\
Autumn
2012/2013}
\\

\vskip 5mm

{\large
\it
School of Mathematical Sciences
\\
University of Nottingham
}

\vskip 15mm

{\Large
\bf
Thomas MacLean}

\vskip 5mm

{\large
Supervisor: Dr.~Adesso}
% or Professor NN

{\large
Division: Mathematical Physics}
% Supervisor's Division: Pure or Applied or Statistics

{\large
Project code: GA P1}
% From Project Book.
% If the project is not from the book, delete the line.

{\large
Assessment type: Investigation}
% Review or Investigation

\vskip 5mm

{\large
January 2013}
% hand-in month and year

\end{center}

\vskip 1 cm

\noindent
{\it I~have read and understood the School and University guidelines
on plagiarism. I~confirm that this work is my own, apart from the
acknowledged references.}

\newpage

\vglue 1cm

\begin{center}
{\bf Abstract}
\end{center}

\vskip 1cm

\begin{center}
\begin{minipage}[c]{5in}
We investigate whether the monogamy which can be found in three qubit systems holds in mixed-state systems of four qubits. We construct a relevant system and find, from the definitions of the tangle, that it exhibits the expected behaviour. We also show that the four qubit Werner and GHZ states exhibit this monogamy whilst finding an analytical expression for the latter.
\end{minipage}
\end{center}

\newpage

\tableofcontents

\newpage

\section{Introduction}
\label{sec:intro}

Much research has been done on measures of entanglement in recent years and quantum information theory is just one are which uses this work. Books such as \cite{NielsenChuang} have been written on the subject but there is still a lot to learn. Since the publication of a well-known paper \cite{CKW}, research has been extensive on the so-called tangle \cite{OV} \cite{LOSU}. However, whilst papers are being published on certain systems \cite{EOSU} very little is known about larger systems. This paper attempts to help in answering whether properties of the smaller systems, such as monogamy and symmetry, transfer to the larger ones.

Using the definitions of the tangle and various properties discovered by other researchers, we show that monogamy holds for a few specific quantum systems, but find it difficult to discover anything certain about the symmetry.

We start in section \ref{sec:background} with the basics of quantum information theory and definitions which will later be used. In section \ref{sec:mainSection}, the most important and relevant definitions for this paper are given, ending with a background of the previous type of work done on this subject. Section \ref{sec:fourQubits} contains the various attempts made on the problem, with a successful outcome, whilst section \ref{sec:extra} gives two more supporting examples before the work is summarised in section \ref{sec:conclusions}. Appendix \ref{app:calculations} contains some supporting material for section \ref{sec:fourQubits} and finally, appendix \ref{app:Matlab} gives the code used in section \ref{sec:fourQubits}

\newpage

\section{Background Material and Definitions}
\label{sec:background}

Before any progress could be made on the project, it was necessary to learn the fundamental concepts of quantum mechanics along with a variety of techniques from linear algebra. In this section, I introduce some of the concepts which are used later on and others which I have learned. The definitions are widely accepted as common knowledge to quantum theorists, but most of what I describe below has been learned from \cite{NielsenChuang}.

\vskip 5mm

A {\bf state space} is a Hilbert space (a complex vector space with an inner product) which is assigned to a physical system, such that the system can be described by a unit {\bf state vector} in it

\vskip 2mm

We define complex conjugation and then the transpose operation (or the other way round) as {\bf Hermitian conjugation} so we have that $A^\dagger = (A^*)^T = (A^T)^*$. We also note that $(A^\dagger)^\dagger = A$

\vskip 2mm

We denote a general state vector in an $n$-dimensional Hilbert space $\mathcal{H}_n$ by its {\bf ket vector} $|\psi\rangle$. This can be more easily understood by thinking of $|\psi\rangle$ as an $n \times 1$ column vector

\vskip 2mm

To form the {\bf bra vector} $\langle\psi|$, we can apply Hermitian conjugation to $|\psi\rangle$, so we may then think of the bra vector as a $1 \times n$ row vector. So if we had, $|\psi\rangle = \begin{pmatrix} a \\ b \\c \end{pmatrix}$, then $\langle\psi| = \begin{pmatrix} a^* & b^* & c^* \end{pmatrix}$

\vskip 2mm

{\bf Computational basis} kets in the $n$-dimensional Hilbert space are the $n$ ket vectors where, for the $i$th vector, all rows have entry $0$ except row $i$ which has entry $1$. For example, in $\mathcal{H}_2$ we have that $|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ and $|1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$. Naturally, these vectors are all pairwise orthogonal

\vskip 2mm

The {\bf tensor product} is a means of forming larger vector spaces from smaller ones. It gives us a way of dealing with multipartite systems of qubits effectively. Perhaps the easiest way to think of it is in matrix form where we have, for $A$ as an $m$ by $n$ matrix and $B$ as a $p$ by $q$ matrix, then $A \otimes B$ is an $mp$ by $nq$ matrix, \begin{center} $A \otimes B = \begin{pmatrix} A_{11}B & A_{12}B & \cdots & A_{1n} \\ A_{21}B & A_{22}B & \cdots & A_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ A_{m1}B & A_{m2}B & \cdots & A_{mn}B \end{pmatrix}$ \end{center}
We write the tensor product of two state vectors $|\phi\rangle \in \mathcal{H}_m$ and $|\psi\rangle \in \mathcal{H}_n$ as either $|\phi\rangle|\psi\rangle$ or just $|\phi\psi\rangle \in \mathcal{H}_{m}\otimes\mathcal{H}_{n}$

\vskip 2mm

Because of the way we defined bra and ket vectors, we automatically have a definition for the outer product $|\psi\rangle\langle\phi|$ in terms of matrices. If the dimension of $|\psi\rangle$ is $n$ and the dimension of $\langle\phi|$ is $m$ then we call this outer product an {\bf operator} which takes a vector from $\mathcal{H}_m$ to $\mathcal{H}_n$. As these operators can be considered simply as matrices, they obey the usual laws of linear algebra

\vskip 2mm

The {\bf Pauli sigma matrices} are defined as follows: \begin{center} $\begin{matrix}
\sigma_0 = I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} & \sigma_1 = \sigma_x = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \\ \sigma_2 = \sigma_y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} & \sigma_3 = \sigma_z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \end{matrix}$ \end{center}
and as an example, here I show that the outer product representation in the computational basis as defined previously is $\sigma_y = -i|0\rangle\langle1| + i|1\rangle\langle0|$. As a check, $|0\rangle\langle1| = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$  and also $|1\rangle\langle0| = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ and so $-i|0\rangle\langle1| + i|1\rangle\langle0| = \begin{pmatrix} 0 & -i \\ 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 \\ i & 0 \end{pmatrix} = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} = \sigma_y$ as required

\vskip 2mm

If a system could be in one of several quantum (orthonormal) states $\{|\psi_i\rangle\}$, each with probability $\{p_i\}$  (which sum to $1$) then we describe the system by its {\bf density matrix} $\rho = \sum_{i} p_i{|\psi_i\rangle}{\langle\psi_i|}$. These density matrices have the properties:

1) $\rho^\dagger = \rho$ so it is Hermitian

2) The trace of $\rho$ is $1$, where the {\bf trace} of $\rho$ is $tr(\rho) = \sum_{j} \langle j| \rho | j\rangle$ with ${|j\rangle}$ as an orthonormal basis set. We can see straight away that in the computational basis, this is just the sum of the elements along the leading diagonal

3) $\rho$ is positive, so all of its eigenvalues are positive

\vskip 2mm

If there is only one $\{p_i\}$ (obviously equal to $1$), so the density matrix is simply given by $\rho = |\psi\rangle\langle\psi|$ then we say that $|\psi\rangle$ is a {\bf pure state}. If there is more than one probability, then the state described by the density matrix is said to be {\bf mixed}. In matrix form, if $tr(\rho^2) = 1$ then we have a pure state, but if $tr(\rho^2) < 1$ then we are dealing with a mixed state. There are other measures, such as the {\bf Von Neumann entropy}, defined as $S(\rho) = -tr(\rho \ln(\rho))$ which gives a value of $0$ only for pure states

\vskip 2mm

The {\bf partial trace} of a density matrix in a tensored Hilbert space is the operation of reducing the state by "tracing out" one of the subsystems, leaving us with the reduced density matrix in a reduced Hilbert space. For example, $\rho_{ABC}$ is in the space $\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{C}$ and if we trace out subsystem B, we have $tr_{B}(\rho_{ABC}) = \rho_{AC}$ which is now in the space $\mathcal{H}_{A}\otimes\mathcal{H}_{C}$

Using our bra and ket notation, the partial trace is an easy operation to perform and is best shown by example as below. We effectively just move the subsystem we are tracing outside of the density matrix. So if we have $\rho_{ABC} = \frac{1}{2}\left(|000\rangle\langle000| + |010\rangle\langle100| + |001\rangle\langle000| + |011\rangle\langle011| \right)$ then we have $\rho_{AB} = \frac{1}{2}\left(tr_C(\rho_{ABC}) = |00\rangle\langle00|\langle0|0\rangle + |01\rangle\langle10|\langle0|0\rangle + |00\rangle\langle00|\langle1|0\rangle + |01\rangle\langle01|\langle1|1\rangle\right) = \frac{1}{2}\left(|00\rangle\langle00| + |01\rangle\langle10| + |00\rangle\langle00| + |01\rangle\langle01|\right)$ due to orthogonality of $|0\rangle$ and $|1\rangle$

\newpage

\section{The Concurrence and the Tangle}
\label{sec:mainSection}

\subsection{Two More Important Concepts}
\label{subsec:moreDefinitions}

\subsubsection{Superposition}
\label{subsubsec:superposition}

One of the defining principles of quantum mechanics is {\bf superposition}. Whereas in classical physics a bit can be either in the state $0$ or the state $1$, in quantum mechanics, a quantum bit, or a qubit, can be in the state $|0\rangle$, the state $|1\rangle$ or a superposition of the two. So we denote this as $|\phi\rangle = a|0\rangle + b|1\rangle$, where $a,b \in \mathbb{C}$ and $|a|^2 + |b|^2 = 1$.

However, when we perform a measurement on such a system, the systems is said to collapse from its superposition to a definite state. From this comes the idea of Schr\"{o}dinger's cat \cite{SCat}: that a system is in an indefinite state, such as our superposition, until we measure it at which point we disturb the system and force it into a known state.

\vskip 2mm

\subsubsection{Entanglement}
\label{subsubsec:entanglement}

Also, one of, if not \emph{the} most noteworthy traits of quantum mechanics is the concept of {\bf entanglement}. This is why it has been appropriate to assign its discussion a whole separate section. Entanglement is the idea that two or more quantum systems can interact to become entangled so that they share some information between them. This then means that none of the systems can be (fully) described without reference to the others involved.

As an example, we consider the Bell state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle)$. We note that if we try to reduce this pure state, we get that $tr_{A}(\Phi^+) = tr_{B}(\Phi^+) = \frac{1}{2}\mathbb{I}_{2}$ which is the maximally mixed state. So we see that the reduction does not give us a pure state, so the original state must be entangled. As it happens, this Bell state (and the 3 others) are the maximally entangled states.

The physical interpretation of this state is as follows: The state $|\Phi^+\rangle$ is in a quantum superposition of states at the start and we are unable to say anything about subsystem $A$ or $B$ separately. However, if Alice makes a measurement on system $A$, then if she finds that her measurement gives the outcome $|0\rangle$ then we know with absolute certainty that if Bob makes a measurement on system $B$, he will find the state $|1\rangle$ as the state will have collapsed into $|01\rangle$. Similarly, if Alice finds $|1\rangle$ then we know that the system will have collapsed into $|10\rangle$ and so Bob will certainly find that his measurement gives him the outcome $|0\rangle$.

\subsection{Introducing the Concurrence and the Tangle}
\label{subsec:introducing}

In this section, I follow through the start of the paper by Coffman, Kundu and Wooters \cite{CKW} and review their definitions of the tangle for a measure of entanglement between first two, then multiple qubits.

For a pair of qubits $A$ and $B$, we define the "spin-flipped" density matrix to be $\tilde{\rho}_{AB} = (\sigma_y\otimes\sigma_y)\rho_{AB}^*(\sigma_y\otimes\sigma_y)$ where $\rho_{AB}$ is the original density matrix, expressed in terms of the computational basis.

Then we define the square roots of the eigenvalues (in decreasing order) of the matrix $\rho_{AB}\tilde{\rho}_{AB}$ as $\lambda_1$, $\lambda_2$, $\lambda_3$ and $\lambda_4$. Then the concurrence of the matrix $\rho_{AB}$ is $C(\rho_{AB}) = $max$\{\lambda_1-\lambda_2-\lambda_3-\lambda_4,0\}$ and then the tangle of the matrix is $\tau(\rho_{AB}) = (C(\rho_{AB}))^2$

Also written in the paper is that if the state $\rho_{AB}$ is pure, then it can be shown that the tangle of the state is simply $\tau_{AB} = \tau(\rho_{AB}) = 4\det(\rho_A)$ where we have $\rho_A$ as the partial trace of $\rho_{AB}$ over qubit $B$

\subsection{The Three Qubit Case}
\label{subsec:threeQubits}

The next section of paper \cite{CKW} is devoted to the definition of the tangle for three qubits. For a pure state $\rho_{ABC}$, we introduce some more notation and define $\tau_{A(BC)}$ as the tangle between qubit $A$ and the pair of qubits $BC$. As described in the paper, we may consider the pair $BC$ as a single qubit as, though it is in a higher dimensional state space, it can still be fully described by just two eigenstates with non-zero eigenvalues.

For mixed states, we encounter more of a problem, in that $\tau_{A(BC)}$ is not defined due to the fact that the reduced density matrix for just qubits $BC$ may require $4$ eigenstates to describe it, so we may no longer consider the pair as a single qubit. So the authors of the paper have defined the quantity $\tau_{A(BC)}^{min}$ instead. This is done by considering all pure-state decompositions of $\rho$, so all $\{(\psi_i,p_i)\}$ such that $\rho = \sum_{i}p_i|\psi_i\rangle\langle\psi_i|$ and then taking the minimum of the average value $\langle\tau_{A(BC)}\rangle = \sum_{i}p_i\tau_{A(BC)}(\psi_i)$

After some algebra which is explained in the paper, we are given the equation $\tau_{AB} + \tau_{AC} \leq \tau_{A(BC)}$. This says that the entanglement of qubit $A$ with the pair $BC$ is an upper bound for the entanglement which $A$ has with both $B$ and $C$ separately. The difference between the two sides of the inequality is then considered to be the amount of entanglement between $A$ and the pair which does not come from entanglement with the separate qubits. This entanglement is inherently tripartite and is called the residual tangle, denoted $\tau_{ABC}$.

The rest of the paper discovers properties of the residual tangle, such that it is monogamous and symmetric, so $\tau_{ABC} \geq 0$ and that the residual tangle is (at least for $3$ qubits) invariant under permutations: we find that $\tau_{A(BC)} - \tau_{AB} - \tau_{AC} = \tau_{ABC} = \tau_{B(CA)} - \tau_{BC} - \tau_{BA}$ and the same for if we construct the residual tangle around qubit $C$.

\newpage

\section{The Four Qubit Case}
\label{sec:fourQubits}

\subsection{Problem Statement}
\label{subsec:fourStatement}

The question that this paper tries to answer is whether the same properties hold for the so-called four-tangle. We want to find whether $\tau_{ABCD} \geq 0$ for all density matrices $\rho$, so that we can say that the four tangle is {\bf monogamous}. We would also like to see if the four-tangle is {\bf symmetric} so that if we construct the four-tangle around either of the four qubits, we get the same value.

We shall start by investigating $|\psi_{pure}\rangle = a\sqrt{p}|0000\rangle + b\sqrt{p}|1110\rangle + c\sqrt{1-p}|0011\rangle + d\sqrt{1-p}|0101\rangle + f\sqrt{1-p}|1001\rangle$ as one of the reduced density matrices \ref{app:purification} has already had a full analysis and this could be useful.

\subsection{Monogamy Attempts (Chronologically)}
\label{subsec:fourMonogamy}

\subsubsection{Starting Point}
\label{subsubsec:fourStart}

We start with the monogamy of the four-tangle:

$\tau_{A(BCD)} = \tau_{AB} + \tau_{AC} + \tau_{AD} + \tau_{ABC} + \tau_{ABD} + \tau_{ACD} + \tau_{ABCD}$

\noindent and then by using the definition in \cite{CKW} that $\tau_{ABC} = \tau_{A(BC)} - \tau_{AB} - \tau_{AC}$ and rearranging, we get that

$\tau_{ABCD} = \tau_{A(BCD)} - \tau_{A(BC)} - \tau_{A(BD)} - \tau_{A(CD)} + \tau_{AB} + \tau_{AC} + \tau_{AD}$

\vskip 2mm

As we know that $\tau_{A(BCD)}$ for a pure state is just $4det(\rho_{A})$, we find $\rho_{A}$ using the method described in \ref{app:redDensMat} and find that $\rho_{A} = (p|a|^2 + (1-p)|c|^2 + (1-p)|d|^2)|0\rangle\langle0| + (p|b|^2 + (1-p)|f|^2)|1\rangle\langle1|$. From this, it is obvious that $4det(\rho_{A}) = 4p^2|a|^2|b|^2 + 4p(1-p)(|a|^2|f|^2+|b|^2|c|^2+|b|^2|d|^2) + 4(1-p)^2(|c|^2|f|^2+|d|^2|f|^2)$

\vskip 2mm

Next, we consider the pairwise tangles as these are calculable from the reduced density matrices

\newpage

\subsubsection{The Pairwise Tangles}
\label{subsubsec:fourPairwise}

Here, we shall calculate $\tau_{AC}$ as an example, but a similar method is used to calculate the other pairwise tangles and the results shall simply be given.

$\rho_{AC} = \begin{pmatrix} p|a|^2+|d|^2(1-p) & 0 & 0 & 0 \\ 0 & |c|^2(1-p) & fc^*(1-p) & 0 \\ 0 & cf^*(1-p) & |f|^2(1-p) & 0 \\ 0 & 0 & 0 & p|b|^2 \end{pmatrix}$

To generalise the method (so that it may be used for $\tau_{AB}$ as well as making the algebra clearer) we rename the elements of the matrix:

\begin{center}
$\rho_{AC} = \begin{pmatrix} \alpha & 0 & 0 & 0 \\ 0 & \beta & \epsilon & 0 \\ 0 & \epsilon^* & \gamma & 0 \\ 0 & 0 & 0 & \delta \end{pmatrix}$ and from \ref{app:spinFlip} we have $\tilde{\rho}_{AC} = \begin{pmatrix} \delta^* & 0 & 0 & 0 \\ 0 & \gamma^* & \epsilon & 0 \\ 0 & \epsilon^* & \beta^* & 0 \\ 0 & 0 & 0 & \alpha^* \end{pmatrix}$
\end{center}

Then we note that $\alpha = \alpha^*$, $\beta = \beta^*$, $\gamma = \gamma^*$, $\delta = \delta^*$ and $|\epsilon|^2 = \beta\gamma$ so that

\begin{center}
$\rho_{AC}\tilde{\rho}_{AC} = \begin{pmatrix} \alpha\delta & 0 & 0 & 0 \\ 0 & 2\beta\gamma & 2\beta\epsilon & 0 \\ 0 & 2\gamma\epsilon^* & 2\beta\gamma & 0 \\ 0 & 0 & 0 & \alpha\delta \end{pmatrix}$
\end{center}

To find the eigenvalues, we use $\det(\rho_{AC}\tilde{\rho}_{AC} - I\lambda) = 0$

$(\alpha\delta - \lambda)[(2\beta\gamma - \lambda)(2\beta\gamma - \lambda)(\alpha\delta - \lambda) - 2\beta\epsilon(2\gamma\epsilon^*(\alpha\delta - \lambda))] = 0$

$(\alpha\delta - \lambda)^2[(2\beta\gamma - \lambda)^2 - 4\beta\gamma|\epsilon|^2] = 0$ and then as $|\epsilon|^2 = \beta\gamma$

$(\alpha\delta - \lambda)^2[\lambda^2 - 4\beta\gamma\lambda] = 0$

$\lambda(\alpha\delta - \lambda)^2(\lambda - 4\beta\gamma) = 0$

Giving the eigenvalues as $\lambda = 0$, $\lambda = \alpha\delta$ (twice) and $\lambda = 4\beta\gamma$

From here, we can create conditions from the definition of the concurrence/tangle and then give the tangle of the matrix exactly.

$C(\rho_{AC}) = $max$\{\lambda_1-\lambda_2-\lambda_3-\lambda_4,0\}$ where the $\lambda$ are the square roots of $\rho_{AC}\tilde{\rho}_{AC}$ in decreasing order. As we only have two unique, nonzero eigenvalues, we have three cases:

\noindent 1) $\alpha\delta > 4\beta\gamma$

$C(\rho_{AC}) = $max$\{\sqrt{\alpha\delta} - \sqrt{\alpha\delta} - 2\sqrt{\beta\gamma} - 0,0\} = 0$

and so naturally $\tau_{AC} = 0$ as well

\noindent 2) $\alpha\delta = 4\beta\gamma$

$C(\rho_{AC}) = $max$\{\sqrt{\alpha\delta} - \sqrt{\alpha\delta} - \sqrt{\alpha\delta} - 0,0\} = 0$

and again $\tau_{AC} = 0$

\noindent 3) $\alpha\delta < 4\beta\gamma$

$C(\rho_{AC}) = $max$\{2\sqrt{\beta\gamma} - \sqrt{\alpha\delta} - \sqrt{\alpha\delta} - 0,0\} = $max$\{2\sqrt{\beta\gamma} - 2\sqrt{\alpha\delta},0\}$

We note that this condition can be furthered to $\alpha\delta < \beta\gamma$

So we can put this all together and say the tangle is $0$ unless $\alpha\delta < \beta\gamma$ in which case $\tau_{AC} = 4\beta\gamma - 8\sqrt{\alpha\beta\gamma\delta} + 4\alpha\delta$

Then in terms of the original problem, we have that the tangle is $0$ unless $p^2|a|^2|b|^2 + p(1-p)|b|^2|d|^2 < (1-p)^2|c|^2|f|^2$ in which case we have a result that $\tau_{AC} = 4(1-p)^2|c|^2|f|^2 - 8(1-p)|b||c||f|\sqrt{p^2|a|^2 + p(1-p)|d|^2} +4p^2|a|^2|b|^2 + 4p(1-p)|b|^2|d|^2$

\vskip 2mm

The other cases are fairly similar and the results are given below:

\vskip 2mm

For $\tau_{AB}$, the tangle is $0$ unless $p^2|a|^2|b|^2 + p(1-p)|b|^2|c|^2 < (1-p)^2|d|^2|f|^2$ in which case $\tau_{AB} = 4(1-p)^2|d|^2|f|^2 - 8(1-p)|b||d||f|\sqrt{p^2|a|^2 + p(1-p)|c|^2} +4p^2|a|^2|b|^2 + 4p(1-p)|b|^2|c|^2$

\vskip 2mm

For $\tau_{AD}$, the tangle is $0$ unless $|b|^2(|c|^2 + |d|^2) < |a|^2|f|^2$ in which case $\tau_{AD} = 4p(1-p)|a|^2|f|^2 - 8p(1-p)|a||b||f|\sqrt{|c|^2 + |d|^2} + 4p(1-p)|b|^2|c|^2 + 4p(1-p)|b|^2|d|^2$

\vskip 2mm

So we now have only to find the tripartite tangles

\newpage

\subsubsection{The Tripartite Tangle - Approach 1}
\label{subsubsec:fourTripartite1}

One of the first approaches attempted was using the inequality from \cite{CKW} which says $\tau_{AB} + \tau_{AC} \leq \tau_{A(BC)}$. This can also be written as an equality, as is done in the paper as well: $\tau_{AB} + \tau_{AC} + \tau_{ABC} = \tau_{A(BC)}$

We start with $\tau_{ABCD} = \tau_{A(BCD)} - \tau_{A(BC)} - \tau_{A(BD)} - \tau_{A(CD)} + \tau_{AB} + \tau_{AC} + \tau_{AD}$

\noindent By substituting all of the tripartite tangles for the other side of the equality, we get $\tau_{ABCD} = \tau_{A(BCD)} - \tau_{AB} - \tau_{AC} - \tau_{AB} - \tau_{AD} - \tau_{AC} - \tau_{AD} + \tau_{AB} + \tau_{AC} + \tau_{AD} - \tau_{ABC} - \tau_{ABD} - \tau_{ACD}$ which simplifies to $\tau_{ABCD} = \tau_{A(BCD)} - \tau_{AB} - \tau_{AC} - \tau_{AD} - \tau_{ABC} - \tau_{ABD} - \tau_{ACD}$

In \cite{CKW}, it is conjectured that $\tau_{12} + \tau_{13} + ... + \tau_{1n} \leq \tau_{1(23...n)}$ but not proved. However, there is another paper, \cite{OV} in which the above is proved. So the first part of the equation, $\tau_{A(BCD)} - (\tau_{AB} + \tau_{AC} + \tau_{AD})$ is definitely greater than or equal to $0$. Then it remains to calculate these tripartite tangles, which is difficult for mixed states, due to its construction.

\subsubsection{The Tripartite Tangle - Approach 2}
\label{subsubsec:fourTripartite2}

In \cite{EOSU}, a complete analysis is given for the three-tangle of a mixture of a generalised GHZ state and a generalised W state, so we have that the density matrix is given by $\rho = p|gGHZ_{a,b}\rangle\langle gGHZ_{a,b}| + (1-p)|gW_{c,d,f}\rangle\langle gW_{c,d,f}|$

\noindent with the generalised GHZ state: $|gGHZ_{a,b}\rangle = a|000\rangle + b|111\rangle$

\noindent and the generalised W state: $|gW_{c,d,f}\rangle = c|001\rangle + d|010\rangle + f|100\rangle$

\noindent and the conditions $|a|^2 + |b|^2 = 1$ and similarly $|c|^2 + |d|^2 + |f|^2 = 1$

The paper gives results for this state, but also mentions that some of the authors had written another paper, \cite{LOSU} which is where the methods came from. In this paper is outlined a method to calculate the three-tangle for any three qubit, rank-2 density matrices of the form $\rho = p|1\rangle\langle1| + (1-p)|2\rangle\langle2|$ where $|1\rangle$ and $|2\rangle$ are orthogonal states

This has potential to be useful for calculating the three-tangle for such parts as $\rho_{ACD}$ if they are in the right form. In density matrix form, $\rho_{ACD}$ turns out to be:

\noindent $\begin{pmatrix} p|a|^2 & 0 & 0 & \sqrt{p(1-p)}ac^* & 0 & \sqrt{p(1-p)}af^* & 0 & 0 \\ 0 & (1-p)|d|^2 & 0 & 0 & 0 & 0 & \sqrt{p(1-p)}db^* & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \sqrt{p(1-p)}ca^* & 0 & 0 & (1-p)|c|^2 & 0 & (1-p)cf^* & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \sqrt{p(1-p)}fa^* & 0 & 0 & (1-p)fc^* & 0 & (1-p)|f|^2 & 0 & 0 \\ 0 & \sqrt{p(1-p)}bd^* & 0 & 0 & 0 & 0 & p|b|^2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

\vskip 2mm

which is of the form $\rho_{ACD} = |1\rangle\langle1| + |2\rangle\langle2|$ where we have

\vskip 2mm

$|1\rangle = \begin{pmatrix} \sqrt{p}a^* \\ 0 \\ 0 \\ \sqrt{1-p}c^* \\ 0 \\ \sqrt{1-p}f^* \\ 0 \\ 0 \end{pmatrix}$ and $|2\rangle = \begin{pmatrix} 0 \\ \sqrt{1-p}d^* \\ 0 \\ 0 \\ 0 \\ 0 \\ \sqrt{p}b^* \\ 0 \end{pmatrix}$ which are orthogonal

\vskip 2mm

These can be rewritten in the form $\rho_{ACD} = q|3\rangle\langle3| + (1-q)|4\rangle\langle4|$ via some rescaling, where $q$ is some function of $p$, which would allow them to be analysed in a similar way to \cite{LOSU} but this was only realised at the end of the project after the answer had been found. However, this method may be useful for different types of states.

\newpage

\subsubsection{The Tripartite Tangle - An Idea}
\label{subsubsec:fourTripartiteIdea}

Further in the paper \cite{LOSU}, the authors outline an approach to find a polyhedron in the Bloch Sphere within which the three-tangle of a state is zero, but non-zero otherwise. If there do exist states which break the monogamy constraint, a possible way of finding them would be to calculate states in which $\tau_{A(BCD)} - (\tau_{AB} + \tau_{AC} + \tau_{AD}) = 0$ and where the three-tangle of any of the reduced density matrices lie outside the simplex. This non-zero three-tangle would make $\tau_{ABCD}$ negative and thus break the constraint. However, due to time constraints on this project, I have been unable to take this idea further.

\subsubsection{The Tripartite Tangle - Approach 3}
\label{subsubsec:fourTripartite3}

As all other approaches seemed not to be going anywhere, it was decided that using MATLAB to try and get some numerical results would be best. So it remained to try to write code to find the $\tau_{A(BC)}$ for mixed states. In \cite{CKW}, this is defined as the minimum average value of the tangle over all possible pure-state decompositions of the original state.

So we are trying to find the minimum of $\sum_{i}p_{i}\tau_{A(BC)}(\psi_{i})$ whilst considering all sets $\{(\psi_{i},p_{i})\}$ such that $\rho = \sum_{i}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$

Naturally, this is a difficult problem computationally, due to the infinite number of ways that we can find a pure-state decomposition, along with a lack of mathematical papers on how one would go about finding any. However, there is a paper by Uhlmann \cite{U} which says that if $\rho$ is a rank($\omega$) state, then a maximum of $\omega^2$ pure states are needed for the optimal decomposition of $\rho$. As the states we are considering are rank-2 states, it suffices to find ensembles of only up to 4 pure states.

Unfortunately, even with this information, I was unable to think of a way to code a program.

\newpage

\subsection{Monogamy Solution Attempt for Specific States}
\label{subsec:fourSolution}

\subsubsection{Key Parts to Approach 4}
\label{subsubsec:keyParts}

Again in this section, we concentrate on the previously mentioned mixture of states $|\psi_{pure}\rangle = a\sqrt{p}|0000\rangle + b\sqrt{p}|1110\rangle + c\sqrt{1-p}|0011\rangle + d\sqrt{1-p}|0101\rangle + f\sqrt{1-p}|1001\rangle$ and set $\rho_{ABCD} = |\psi_{pure}\rangle\langle\psi_{pure}|$

\vskip 2mm

For the basis of this argument, the equation given in the previous section is used: $\tau_{ABCD} = \tau_{A(BCD)} - \tau_{A(BC)} - \tau_{A(BD)} - \tau_{A(CD)} + \tau_{AB} + \tau_{AC} + \tau_{AD}$

\vskip 2mm

We also need the definition $\tau_{A(BC)}^{min} = \min[\sum_{i}p_{i}\tau_{A(BC)}(\psi_{i})]$ for all sets $\{(\psi_{i},p_{i})\}$ such that $\rho = \sum_{i}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$

\vskip 2mm

We recall from earlier, that $4det(\rho_{A}) = 4p^2|a|^2|b|^2 + 4p(1-p)(|a|^2|f|^2+|b|^2|c|^2+|b|^2|d|^2) + 4(1-p)^2(|c|^2|f|^2+|d|^2|f|^2)$ which is the tangle between qubit $A$ and all the others, denoted $\tau_{A(BCD)}$

Finally we recall from \ref{subsubsec:fourPairwise}:

For $\tau_{AB}$, the tangle is $0$ unless $p^2|a|^2|b|^2 + p(1-p)|b|^2|c|^2 < (1-p)^2|d|^2|f|^2$ in which case $\tau_{AB} = 4(1-p)^2|d|^2|f|^2 - 8(1-p)|b||d||f|\sqrt{p^2|a|^2 + p(1-p)|c|^2} +4p^2|a|^2|b|^2 + 4p(1-p)|b|^2|c|^2$

\vskip 2mm

For $\tau_{AC}$, the tangle is $0$ unless $p^2|a|^2|b|^2 + p(1-p)|b|^2|d|^2 < (1-p)^2|c|^2|f|^2$ in which case $\tau_{AC} = 4(1-p)^2|c|^2|f|^2 - 8(1-p)|b||c||f|\sqrt{p^2|a|^2 + p(1-p)|d|^2} +4p^2|a|^2|b|^2 + 4p(1-p)|b|^2|d|^2$

\vskip 2mm

For $\tau_{AD}$, the tangle is $0$ unless $|b|^2(|c|^2 + |d|^2) < |a|^2|f|^2$ in which case $\tau_{AD} = 4p(1-p)|a|^2|f|^2 - 8p(1-p)|a||b||f|\sqrt{|c|^2 + |d|^2} + 4p(1-p)|b|^2|c|^2 + 4p(1-p)|b|^2|d|^2$

\newpage

\subsubsection{Upper Bounds of the Reduced Density Matrices' Three-tangles}
\label{subsubsec:upperBound}

We start by considering $\rho_{ACD}$ (shown in matrix form in \ref{subsubsec:fourTripartite2} as $\rho_{ACD}^{(1)} + \rho_{ACD}^{(2)}$ where we have:

\vskip 2mm

\noindent $\rho_{ACD}^{(1)} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & (1-p)|d|^2 & 0 & 0 & 0 & 0 & \sqrt{p(1-p)}db^* & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \sqrt{p(1-p)}bd^* & 0 & 0 & 0 & 0 & p|b|^2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

\vskip 2mm

\noindent and

\vskip 2mm

$\rho_{ACD}^{(2)} = \begin{pmatrix} p|a|^2 & 0 & 0 & \sqrt{p(1-p)}ac^* & 0 & \sqrt{p(1-p)}af^* & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \sqrt{p(1-p)}ca^* & 0 & 0 & (1-p)|c|^2 & 0 & (1-p)cf^* & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \sqrt{p(1-p)}fa^* & 0 & 0 & (1-p)fc^* & 0 & (1-p)|f|^2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

\vskip 2mm

\noindent and we notice that both $\rho_{ACD}^{(1)}$ and $\rho_{ACD}^{(2)}$ are pure states if we factor out their trace. We also note that $tr(\rho_{ACD}^{(1)}) + tr(\rho_{ACD}^{(2)}) = p|a|^2 + p|b|^2 + (1-p)|c|^2 + (1-p)|d|^2 + (1-p)|f|^2 = 1$ from the state's definition.

So a pure-state decomposition for $\rho_{ACD}$ is $tr(\rho_{ACD}^{(1)})\hat{\rho}_{ACD}^{(1)} + tr(\rho_{ACD}^{(2)})\hat{\rho}_{ACD}^{(2)}$ where $\hat{\rho}_{ACD}^{(1)}$ is the normalised version of $\rho_{ACD}^{(1)}$. However, as our next operation is linear, we may leave the trace in and consider the un-normalised version

We may now calculate $\sum_{i}p_{i}\tau_{A(CD)}(\psi_{i})$ as we know that each pure state has a tangle of $4\det(\rho_{A})$. After reducing the density matrices, we get that $\rho_{A}^{(1)} = \begin{pmatrix} (1-p)|d|^2 & 0 \\ 0 & p|b|^2 \end{pmatrix}$ and so $4\det(\rho_{A}^{(1)}) = 4p(1-p)|b|^2|d|^2$.

Similarly, $\rho_{A}^{(2)} = \begin{pmatrix} p|a|^2 + (1-p)|c|^2 & 0 \\ 0 & p|f|^2 \end{pmatrix}$ and so we get that $4\det(\rho_{A}^{(2)}) = 4p(1-p)|a|^2|f|^2 + 4(1-p)^2|c|^2|f|^2$

So we have, but only with respect to the decomposition we have used, that $\tau_{A(CD)} = 4p(1-p)|b|^2|d|^2 + 4p(1-p)|a|^2|f|^2 + 4(1-p)^2|c|^2|f|^2$

By finding this value, we know that this is an upper bound for $\tau_{A(CD)}^{min}$

\vskip 2mm

Next we see that $\rho_{A(CD)}$ is very similar to $\rho_{A(BD)}$ (as shown below) except that the $d$ and $c$ parts are the other way round:

\vskip 2mm

\noindent $\begin{pmatrix} p|a|^2 & 0 & 0 & \sqrt{p(1-p)}ad^* & 0 & \sqrt{p(1-p)}af^* & 0 & 0 \\ 0 & (1-p)|c|^2 & 0 & 0 & 0 & 0 & \sqrt{p(1-p)}cb^* & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \sqrt{p(1-p)}da^* & 0 & 0 & (1-p)|d|^2 & 0 & (1-p)df^* & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \sqrt{p(1-p)}fa^* & 0 & 0 & (1-p)fd^* & 0 & (1-p)|f|^2 & 0 & 0 \\ 0 & \sqrt{p(1-p)}bc^* & 0 & 0 & 0 & 0 & p|b|^2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

\vskip 2mm

so a similar analysis can take place and we get our upper bound for $\tau_{A(BD)}^{min}$ as $\tau_{A(BD)} = 4p(1-p)|b|^2|c|^2 + 4p(1-p)|a|^2|f|^2 + 4(1-p)^2|d|^2|f|^2$

From \cite{EOSU}, we are given that the three-tangle for a generalised Werner state is $0$ and for a GHZ state, is $4|a|^2|b|^2$, so by applying the same technique as we have just done for the above, we find that our upper bound for $\tau_{A(BC)}^{min}$ is $\tau_{A(BC)} = 4p^2|a|^2|b|^2$

\newpage

\subsubsection{Putting it all Together}
\label{subsubsec:comingTogether}

Let us first consider $\tau_{A(BCD)} - (\tau_{A(BC)} + \tau_{A(BD)} + \tau_{A(CD)})$. From what we found in \ref{subsubsec:upperBound} we know that a lower bound for this would be attained when we use the individual upper bounds for each of $\tau_{A(BC)}$, $\tau_{A(BD)}$ and $\tau_{A(CD)}$. Whether it is possible to find a state with these values at the same time is irrelevant. If we somehow did so, we get that our lower bound is:

\noindent $4p^2|a|^2|b|^2 + 4p(1-p)(|a|^2|f|^2+|b|^2|c|^2+|b|^2|d|^2) + 4(1-p)^2(|c|^2|f|^2+|d|^2|f|^2) - 4p^2|a|^2|b|^2 - 4p(1-p)|b|^2|c|^2 - 4p(1-p)|a|^2|f|^2 - 4(1-p)^2|d|^2|f|^2 - 4p(1-p)|b|^2|d|^2 - 4p(1-p)|a|^2|f|^2 - 4(1-p)^2|c|^2|f|^2$ which is simply equal to $-4p(1-p)|a|^2|f|^2$

At this point, I created the code in appendix \ref{app:bipartiteCode} to check if indeed it was the case that $\tau_{AB} + \tau_{AC} + \tau_{AD} \geq 4p(1-p)|a|^2|f|^2$, though it turned out not to be true in general.

\subsection{Monogamy Solution for Specific States}
\label{subsec:actualFourSolution}

This section is actually a follow-on from the first approach in section \ref{subsubsec:fourTripartite1} and finds the tripartite tangles, whilst using the bipartite information from \ref{subsubsec:fourPairwise}.

In the paper \cite{LOSU}, the authors obtain the three-tangle of the state which is denoted $\rho_{ABC}$ here. They do this by considering the superposition of the two pure states (in actual fact, one minus the other) and use the wavefunction coefficients (as below) to get an expression before analysing it when the expression evaluates to less than zero.

$\tau_3 = 4|d_1 - 2d_2 + 4d_3|$

$d_1 = \psi_{000}^2\psi_{111}^2 + \psi_{001}^2\psi_{110}^2 + \psi_{010}^2\psi_{101}^2 + \psi_{100}^2\psi_{011}^2$

$d_2 = \psi_{000}\psi_{111}\psi_{011}\psi_{100} + \psi_{000}\psi_{111}\psi_{101}\psi_{010} + \psi_{000}\psi_{111}\psi_{110}\psi_{001} + \psi_{011}\psi_{100}\psi_{101}\psi_{010} + \psi_{011}\psi_{100}\psi_{110}\psi_{001} + \psi_{101}\psi_{010}\psi_{110}\psi_{001}$

$d_3 = \psi_{000}\psi_{110}\psi_{101}\psi_{011} + \psi_{111}\psi_{001}\psi_{010}\psi_{100}$

Then we use the pure states we have found and find that (in a more general case than in \cite{LOSU}:

$\tau_{ABC} = 4(p^2a^2b^2 + 4\sqrt{p(1-p)^3}bcdf)$ (for $p_0 < p < p_1$, with more information in \cite{EOSU}). Note that this is the only density matrix which, when analysed this way, has a negative part and so requires extra attention.

However, we must remember to normalise the two density matrices first, (whereas the one above is already normalised) and so we end up with the two formulae:

$\tau_{ABD} = 4tr(\rho_{ABD}^{(1)})tr(\rho_{ABD}^{(2)})(p(1-p)c^2b^2 + 4p(1-p)abdf)$

$\tau_{ACD} = 4tr(\rho_{ACD}^{(1)})tr(\rho_{ACD}^{(2)})(p(1-p)d^2b^2 + 4p(1-p)abcf)$

At this point, with little time remaining, I decided it would be best to test these formulae in MATLAB and the code is shown in \ref{app:fullCode}.
Below is the graphical output to demonstrate that the results showed that $0 \leq \tau_{ABCD} \leq 1$ as we were hoping for. There were a few results which were actually below zero, but this was almost certainly down to rounding errors in the calculations.

\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{Figure.jpg}
\caption{States and their four-tangle}
\label{fig1}
\end{figure}

\newpage

\section{The Four-tangle of Two Other States}
\label{sec:extra}

\subsection{General GHZ State}
\label{subsec:GHZ}

For a general GHZ state with $n$ qubits, $|GHZ\rangle = a|0000\rangle + b |1111\rangle$. So we have $|GHZ\rangle\langle GHZ| = |a|^2|0000\rangle\langle0000| + ab^*|0000\rangle\langle1111| + ba^*|1111\rangle\langle0000| + |b|^2|1111\rangle\langle1111|$

As this is a pure state, we know that $\tau_{A(BCD)} = 4\det(\rho_{A})$ and as $\rho_{A} = |a|^2|0\rangle\langle0| + |b|^2|1\rangle\langle1|$ we get that $\tau_{A(BCD)} = 4|a|^2|b|^2$

For this state, $\rho_{AB} = \rho_{AC} = \rho_{AD} = |a|^2|00\rangle\langle00| + |b|^2|11\rangle\langle11|$ or in matrix form,

$\begin{pmatrix} |a|^2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & |b|^2 \end{pmatrix}$ with the spin-flipped version as $\begin{pmatrix} |b|^2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & |a|^2 \end{pmatrix}$

When multiplied together, this gives a diagonal matrix with the same two non-zero elements. Thus from our definition of the tangle for two qubits, we get that the bipartite tangles are all zero.

Again, for this state, $\rho_{ABC} = \rho_{ACD} = \rho_{ABD} = |a|^2|000\rangle\langle000| + |b|^2|111\rangle\langle111|$ which can be written as:

$|a|^2 \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} + |b|^2 \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

By noting that the two matrices are pure states, that $|a|^2 + |b|^2 = 1$ and that the reduced density matrix will be simply $\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$ or $\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$, both of which have determinant $0$, then this, in a similar way to \ref{subsubsec:upperBound} gives the tripartite tangles an upper bound of $|a|^2 \times 0 + |b|^2 \times 0 = 0$

As the tripartite tangle has been shown to be monogamous previously, $0$ is also a lower bound and thus the tripartite tangles are all $0$.

This then leaves  $\tau_{A(BCD)} = \tau_{ABCD}$ and so we finally get $\tau_{ABCD} = 4|a|^2|b|^2$

\subsection{General Werner State}
\label{subsec:Werner}

We start with $|W\rangle = a|0001\rangle + b|0010\rangle + c|0100\rangle + d|1000\rangle$ as our general Werner state. Then from \cite{CKW} we are given that $\tau_{AB} + \tau_{AC} + \tau_{AD} = \tau_{A(BCD)}$.

This being the case, the equation $\tau_{A(BCD)} = \tau_{AB} + \tau_{AC} + \tau_{AD} + \tau_{ABC} + \tau_{ABD} + \tau_{ACD} + \tau_{ABCD}$ reduces to $\tau_{ABCD} = -(\tau_{ABC} + \tau_{ABD} + \tau_{ACD})$

Then by using, $\tau_{ABC} = \tau_{A(BC)} - \tau_{AB} - \tau_{AC}$ on all three tripartite tangles, we obtain $\tau_{ABCD} = (\tau_{AB} + \tau_{AC} - \tau_{A(BC)}) + (\tau_{AC} + \tau_{AD} - \tau_{A(CD)}) + (\tau_{AB} + \tau_{AD} - \tau_{A(BD)})$

Also from \cite{CKW} we have the inequality $\tau_{AB} + \tau_{AC} \leq \tau_{A(BC)}$, and so each bracket above is less than or equal to zero.

From here, we focus on $\tau_{A(BC)}$ with the understanding that the others will be fairly similar. To find $\rho_{ABC}$, we simply form $\rho_{ABCD} = |W\rangle\langle W|$ and then take the partial trace over qubit D. This leaves us with a matrix which can again be separated in the way we did with the purification.

$\begin{pmatrix} |a|^2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & |b|^2 & bc^* & 0 & bd^* & 0 & 0 & 0 \\ 0 & cb^* & |c|^2 & 0 & cd^* & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & db^* & dc^* & 0 & |d|^2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

\vskip 2mm

The matrix is then split by taking the $|a|^2$ part as its own matrix, which is then factorised out, again leaving a matrix with a $1$ in the top left and $0$s elsewhere, having tangle $0$.

The remaining matrix involving only $b, c, d$ is also pure and reducing it gives $\begin{pmatrix} |b|^2 + |c|^2 & 0 \\ 0 & |d|^2 \end{pmatrix}$, so that $4\det(\rho_{A}) = 4|b|^2|d|^2 + 4|c|^2|d|^2$. So now we have our upper bound for $\tau_{A(BC)}$

We can figure out $\tau_{AB}, \tau_{AC}$ and similar others via the normal method. The aforementioned have values of $4|c|^2|d|^2$ and $4|b|^2|d|^2$ respectively.

\vskip 2mm

To bring everything together, we have that $\tau_{AB} + \tau_{AC} - \tau_{A(BC)} \leq 0$. We can substitute in our known values to get $4|c|^2|d|^2 + 4|b|^2|d|^2 - \tau_{A(BC)} \leq 0$. As we know that $\tau_{A(BC)} \leq 4|c|^2|d|^2 + 4|b|^2|d|^2$, the only way to satisfy all the conditions is if $\tau_{A(BC)} = 4|c|^2|d|^2 + 4|b|^2|d|^2$, so this must be the case.

The other brackets are computed the same way and so finally we have them all as $0$, giving $\tau_{ABCD} = 0 + 0 + 0 = 0$

\newpage

\section{Conclusions}
\label{sec:conclusions}

We have seen that for a purification of a mixture of a generalised GHZ state with a generalised Werner state, $|\psi_{pure}\rangle = a\sqrt{p}|0000\rangle + b\sqrt{p}|1110\rangle + c\sqrt{1-p}|0011\rangle + d\sqrt{1-p}|0101\rangle + f\sqrt{1-p}|1001\rangle$ the monogamy of the residual $4$-tangle holds, that is to say that for this state $\tau_{ABCD} \geq 0$ for all choices of $a, b, c, d, f$ such that $|a|^2 + |b|^2 = 1 = |c|^2 + |d|^2 + |f|^2$

We have also managed to show that a general GHZ state with four qubits will have a four-tangle of $4|a|^2|b|^2$, and that for four qubit systems, monogamy holds for the general Werner state as well. More specifically, it is shown that the four-tangle of a  four qubit Werner state is $0$.

Unfortunately time did not allow for an attempt to check if the four-tangle is symmetrical, though the methods used may give a clue. However, I hope that this work will push others to study the symmetry of the 4-tangle and also whether the monogamy condition holds for states other than the few studied here. Also, I hope that someone will analyse the expression for $\tau_{ABCD}$ fully, accounting for the conditions on the bipartite tangles, to check that the numerics do hold up.

\newpage

\appendix

\section{Calculations for section \ref{sec:fourQubits}}
\label{app:calculations}

\subsection{Purification of the Generalized W and GHZ States}
\label{app:purification}

In this appendix we verify that the state $|\psi_{pure}\rangle = a\sqrt{p}|0000\rangle + b\sqrt{p}|1110\rangle + c\sqrt{1-p}|0011\rangle + d\sqrt{1-p}|0101\rangle + f\sqrt{1-p}|1001\rangle$ is in fact a purification we can use by showing that by tracing out qubit D, we arrive at the mixture of generalized GHZ and Werner states we wanted.

\vskip 5mm

So we have that the density matrix is given by: $|\psi_{pure}\rangle\langle\psi_{pure}| =
 p|a|^2|0000\rangle\langle0000| + pab^*|0000\rangle\langle1110| + ac^*\sqrt{p(1-p)}|0000\rangle\langle0011| + ad^*\sqrt{p(1-p)}|0000\rangle\langle0101| + af^*\sqrt{p(1-p)}|0000\rangle\langle1001| + pba^*|1110\rangle\langle0000| + p|b|^2|1110\rangle\langle1110| + bc^*\sqrt{p(1-p)}|1110\rangle\langle0011| + bd^*\sqrt{p(1-p)}|1110\rangle\langle0101| + bf^*\sqrt{p(1-p)}|1110\rangle\langle1001| + ca^*\sqrt{p(1-p)}|0011\rangle\langle0000| + cb^*\sqrt{p(1-p)}|0011\rangle\langle1110| + |c|^2(1-p)|0011\rangle\langle0011| + cd^*(1-p)|0011\rangle\langle0101| + cf^*(1-p)|0011\rangle\langle1001| + da^*\sqrt{p(1-p)}|0101\rangle\langle0000| + db^*\sqrt{p(1-p)}|0101\rangle\langle1110| + dc^*(1-p)|0101\rangle\langle0011| + |d|^2(1-p)|0101\rangle\langle0101| + df^*(1-p)|0101\rangle\langle1001| + fa^*\sqrt{p(1-p)}|1001\rangle\langle0000| + fb^*\sqrt{p(1-p)}|1001\rangle\langle1110| + fc^*(1-p)|1001\rangle\langle0011| + fd^*(1-p)|1001\rangle\langle0101| + |f|^2(1-p)|1001\rangle\langle1001|$

\vskip 5mm

From here, we could simply note that when we trace out qubit D, all the terms with which involve a $\sqrt{p(1-p)}$ will disappear because of the way the state has been constructed and that the last qubits are different in all of these parts, but the same whenever the terms are simply multiplied by $p$ or $1-p$. Hence we will be left with just the GHZ and Werner state mixture. However, on the next page, this shall be shown explicitly.

\newpage

So we take the partial trace over qubit D:

\vskip 5mm

$tr_D(|\psi_{pure}\rangle\langle\psi_{pure}|) = p|a|^2|000\rangle\langle000|\langle0|0\rangle + pab^*|000\rangle\langle111|\langle0|0\rangle + ac^*\sqrt{p(1-p)}|000\rangle\langle001|\langle0|1\rangle + ad^*\sqrt{p(1-p)}|000\rangle\langle010|\langle0|1\rangle + af^*\sqrt{p(1-p)}|000\rangle\langle100|\langle0|1\rangle + pba^*|111\rangle\langle000|\langle0|0\rangle + p|b|^2|111\rangle\langle111|\langle0|0\rangle + bc^*\sqrt{p(1-p)}|111\rangle\langle001|\langle0|1\rangle + bd^*\sqrt{p(1-p)}|111\rangle\langle010|\langle0|1\rangle + bf^*\sqrt{p(1-p)}|111\rangle\langle100|\langle0|1\rangle + ca^*\sqrt{p(1-p)}|001\rangle\langle000|\langle1|0\rangle + cb^*\sqrt{p(1-p)}|001\rangle\langle111|\langle1|0\rangle + |c|^2(1-p)|001\rangle\langle001|\langle1|1\rangle + cd^*(1-p)|001\rangle\langle010|\langle1|1\rangle + cf^*(1-p)|001\rangle\langle100|\langle1|1\rangle + da^*\sqrt{p(1-p)}|010\rangle\langle000|\langle1|0\rangle + db^*\sqrt{p(1-p)}|010\rangle\langle111|\langle1|0\rangle + dc^*(1-p)|010\rangle\langle001|\langle1|1\rangle + |d|^2(1-p)|010\rangle\langle010|\langle1|1\rangle + df^*(1-p)|010\rangle\langle100|\langle1|1\rangle + fa^*\sqrt{p(1-p)}|100\rangle\langle000|\langle1|0\rangle + fb^*\sqrt{p(1-p)}|100\rangle\langle111|\langle1|0\rangle + fc^*(1-p)|100\rangle\langle001|\langle1|1\rangle + fd^*(1-p)|100\rangle\langle010|\langle1|1\rangle + |f|^2(1-p)|100\rangle\langle100|\langle1|1\rangle$

\vskip 5mm

And then by noting that $\langle0|1\rangle = \langle1|0\rangle = 0$ and $\langle0|0\rangle = \langle1|1\rangle = 1$ we can simplify to:

\vskip 5mm

$tr_D(|\psi_{pure}\rangle\langle\psi_{pure}|) =
p|a|^2|000\rangle\langle000| + pab^*|000\rangle\langle111| + pba^*|111\rangle\langle000| + p|b|^2|111\rangle\langle111| + |c|^2(1-p)|001\rangle\langle001| + cd^*(1-p)|001\rangle\langle010| + cf^*(1-p)|001\rangle\langle100| + dc^*(1-p)|010\rangle\langle001| + |d|^2(1-p)|010\rangle\langle010| + df^*(1-p)|010\rangle\langle100| + fc^*(1-p)|100\rangle\langle001| + fd^*(1-p)|100\rangle\langle010| + |f|^2(1-p)|100\rangle\langle100|$

\vskip 5mm

Which, when written as a state vector, we can straight away see is what we were hoping for, which was $|\Psi\rangle = p|\psi\rangle + (1-p)|\phi\rangle$ where we have defined the ket $|\psi\rangle = a|000\rangle + b|111\rangle$ as a generalized GHZ state and $|\phi\rangle = c|001\rangle + b|010\rangle + c|100\rangle$ as a generalized Werner state

\newpage

\subsection{Finding the Reduced Density Matrices}
\label{app:redDensMat}

In this section, we demonstrate how the partial trace operation is performed on $\rho_{ABCD}$ to give us $\rho_{AC}$. This method is also used to find $\rho_{A}$, $\rho_{AB}$, $\rho_{AD}$, $\rho_{ABD}$ and $\rho_{ACD}$ (with $\rho_{ABC}$ already found in the first appendix) but these are not shown.

\vskip 5mm

We start again with $\rho_{ABCD}$ and note that instead of tracing out qubits B and D separately, we may trace them both out at the same time and then use the facts that $|00\rangle\langle00| = |01\rangle\langle01| = |10\rangle\langle10| = |11\rangle\langle11| = 1$ whereas all other combinations are equal to $0$. For example, $|00\rangle\langle10| = |01\rangle\langle10| = |00\rangle\langle11| = 0$

\vskip 5mm

So $tr_{BD}(|\psi_{pure}\rangle\langle\psi_{pure}|) =
p|a|^2|00\rangle\langle00|\langle00|00\rangle + pab^*|00\rangle\langle11|\langle00|10\rangle + ac^*\sqrt{p(1-p)}|00\rangle\langle01|\langle00|01\rangle + ad^*\sqrt{p(1-p)}|00\rangle\langle00|\langle00|11\rangle + af^*\sqrt{p(1-p)}|00\rangle\langle10|\langle00|01\rangle + pba^*|11\rangle\langle00|\langle10|00\rangle + p|b|^2|11\rangle\langle11|\langle10|10\rangle + bc^*\sqrt{p(1-p)}|11\rangle\langle01|\langle10|01\rangle + bd^*\sqrt{p(1-p)}|11\rangle\langle00|\langle10|11\rangle + bf^*\sqrt{p(1-p)}|11\rangle\langle10|\langle10|01\rangle + ca^*\sqrt{p(1-p)}|01\rangle\langle00|\langle01|00\rangle + cb^*\sqrt{p(1-p)}|01\rangle\langle11|\langle01|10\rangle + |c|^2(1-p)|01\rangle\langle01|\langle01|01\rangle + cd^*(1-p)|01\rangle\langle00|\langle01|11\rangle + cf^*(1-p)|01\rangle\langle10|\langle01|01\rangle + da^*\sqrt{p(1-p)}|010\rangle\langle00|\langle11|00\rangle + db^*\sqrt{p(1-p)}|00\rangle\langle111|\langle11|10\rangle + dc^*(1-p)|00\rangle\langle01|\langle11|01\rangle + |d|^2(1-p)|00\rangle\langle00|\langle11|11\rangle + df^*(1-p)|00\rangle\langle10|\langle11|01\rangle + fa^*\sqrt{p(1-p)}|10\rangle\langle00|\langle01|00\rangle + fb^*\sqrt{p(1-p)}|10\rangle\langle11|\langle01|10\rangle + fc^*(1-p)|10\rangle\langle01|\langle01|01\rangle + fd^*(1-p)|10\rangle\langle00|\langle01|11\rangle + |f|^2(1-p)|10\rangle\langle10|\langle01|01\rangle$

\vskip 5mm

And we get that $\rho_{AC} = p|a|^2|00\rangle\langle00| + |d|^2(1-p)|00\rangle\langle00| + |c|^2(1-p)|01\rangle\langle01| + |f|^2(1-p)|10\rangle\langle10| + p|b|^2|11\rangle\langle11| + cf^*(1-p)|01\rangle\langle10| + fc^*(1-p)|10\rangle\langle01|$

\newpage

\subsection{Effect of Spin-Flipping a Matrix}
\label{app:spinFlip}

Here, we take a general $4 \times 4$ matrix and spin-slip it. From the definition, $\tilde{\rho}_{ab} = (\sigma_y\otimes\sigma_y)\rho_{ab}^*(\sigma_y\otimes\sigma_y)$

So we start with $\rho_{ab} = \begin{pmatrix} a & b & c & d \\ e & f & g & h \\ i & j & k & l \\ m & n & p & q \end{pmatrix}$ and $\sigma_y\otimes\sigma_y = \begin{pmatrix} 0 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 0 \end{pmatrix}$

And we have that $(\sigma_y\otimes\sigma_y)\rho_{ab} = \begin{pmatrix} -m & -n & -p & -q \\ i & j & k & l \\ e & f & g & h \\ -a & -b & -c & -d \end{pmatrix}$

And then $(\sigma_y\otimes\sigma_y)\rho_{ab}(\sigma_y\otimes\sigma_y) = \begin{pmatrix} q & -p & -n & m \\ -l & k & j & -i \\ -h & g & f & -e \\ d & -c & -b & a \end{pmatrix}$

Finally $(\sigma_y\otimes\sigma_y)\rho_{ab}^*(\sigma_y\otimes\sigma_y) = \begin{pmatrix} q^* & -p^* & -n^* & m^* \\ -l^* & k^* & j^* & -i^* \\ -h^* & g^* & f^* & -e^* \\ d^* & -c^* & -b^* & a^* \end{pmatrix} = \tilde{\rho}_{ab}$

\newpage

\section{Matlab Code}
\label{app:Matlab}

\subsection{The Sum of the Bipartite Tangles}
\label{app:bipartiteCode}

Here is the code I used to check the sum $\tau_{AB} + \tau_{AC} + \tau_{AD}$. I checked whether it was greater than or equal to $4p(1-p)|a|^2|f|^2$ which was not always the case.

{\small
\begin{verbatim}
clear
clc
n = 8;
i = 1;
for p = linspace(0,1,n)
for b = linspace(0,1,n)
for c = linspace(0,1,n)
for d = linspace(0,1,n)
if abs(c)^2+abs(d)^2 <= 1
disp(i)
A(i,1) = p;
A(i,2) = b;
A(i,3) = c;
A(i,4) = d;
Tabcd = 4*p^2*abs(b)^2*(1-abs(b)^2)
+ 4*p*(1-p)*((1-abs(b)^2)*(1-abs(c)^2-abs(d)^2)
+ abs(b)^2*abs(c)^2 + abs(b)^2*abs(d)^2)
+ 4*(1-p)^2*(abs(c)^2*(1-abs(c)^2-abs(d)^2)+abs(d)^2*(1-abs(c)^2-abs(d)^2));
if (1-p)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2)
    > p^2*(1-abs(b)^2)*abs(b)^2 + p*(1-p)*abs(b)^2*abs(c)^2
    Tab = 4*(1-p)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2)
    - 4*sqrt(4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2)
    + 4*p*(1-p)^3*abs(b)^2*abs(c)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2))
    + 4*p^2*(1-abs(b)^2)*abs(b)^2 + 4*p*(1-p)*abs(b)^2*abs(c)^2;
else
    Tab = 0;
end
if (1-p)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
    > p^2*(1-abs(b)^2)*abs(b)^2 + p*(1-p)*abs(b)^2*abs(d)^2
    Tac = 4*(1-p)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
    - 4*sqrt(4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
    + 4*p*(1-p)^3*abs(b)^2*abs(c)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2))
    + 4*p^2*(1-abs(b)^2)*abs(b)^2 + 4*p*(1-p)*abs(b)^2*abs(d)^2;
else
    Tac = 0;
end
if p*(1-p)*(1-abs(b)^2)*(1-abs(c)^2-abs(d)^2)
    > p*(1-p)*abs(b)^2*(abs(c)^2+abs(d)^2)
    Tad = 4*p*(1-p)*(1-abs(b)^2)*(1-abs(c)^2-abs(d)^2)
    - 4*sqrt(4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
    + 4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2))
    + 4*p*(1-p)*abs(b)^2*abs(c)^2 + 4*p*(1-p)*abs(b)^2*abs(d)^2;
else
    Tad = 0;
end

if Tab + Tac + Tad >= 4*p*(1-p)*(1-b^2)*(1-c^2-d^2)
    Answer = 2;
else
    Answer = 0;
end

A(i,5) = Answer;
i = i + 1;
else
end
end
end
end
end
A
[m F] = min(A(:,5))
\end{verbatim}
}

\newpage

\subsection{Numerical Proof of Monogamy}
\label{app:fullCode}

{\scriptsize
\begin{verbatim}

clear
clc
n = 6;
i = 1;
for p = linspace(0,1,n)
  for b = linspace(0,1,n)
    for c = linspace(0,1,n)
      for d = linspace(0,1,n)
        if abs(c)^2+abs(d)^2 <= 1
          disp(i)
          A(i,1) = p;
          A(i,2) = b;
          A(i,3) = c;
          A(i,4) = d;
          Tabcd = 4*p^2*abs(b)^2*(1-abs(b)^2)
          + 4*p*(1-p)*((1-abs(b)^2)*(1-abs(c)^2-abs(d)^2)
          + abs(b)^2*abs(c)^2 + abs(b)^2*abs(d)^2)
          + 4*(1-p)^2*(abs(c)^2*(1-abs(c)^2-abs(d)^2)+abs(d)^2*(1-abs(c)^2-abs(d)^2));
          if (1-p)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2)
          > p^2*(1-abs(b)^2)*abs(b)^2 + p*(1-p)*abs(b)^2*abs(c)^2 - 0.001
            Tab = 4*(1-p)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2)
            - 4*sqrt(4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2)
            + 4*p*(1-p)^3*abs(b)^2*abs(c)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2))
            + 4*p^2*(1-abs(b)^2)*abs(b)^2 + 4*p*(1-p)*abs(b)^2*abs(c)^2;
          else
            Tab = 0;
          end
          if (1-p)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
          > p^2*(1-abs(b)^2)*abs(b)^2 + p*(1-p)*abs(b)^2*abs(d)^2 - 0.001
            Tac = 4*(1-p)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
            - 4*sqrt(4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
            + 4*p*(1-p)^3*abs(b)^2*abs(c)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2))
            + 4*p^2*(1-abs(b)^2)*abs(b)^2 + 4*p*(1-p)*abs(b)^2*abs(d)^2;
          else
            Tac = 0;
          end
          if p*(1-p)*(1-abs(b)^2)*(1-abs(c)^2-abs(d)^2)
          > p*(1-p)*abs(b)^2*(abs(c)^2+abs(d)^2) - 0.001
            Tad = 4*p*(1-p)*(1-abs(b)^2)*(1-abs(c)^2-abs(d)^2)
            - 4*sqrt(4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(c)^2*(1-abs(c)^2-abs(d)^2)
            + 4*p^2*(1-p)^2*(1-abs(b)^2)*abs(b)^2*abs(d)^2*(1-abs(c)^2-abs(d)^2))
            + 4*p*(1-p)*abs(b)^2*abs(c)^2 + 4*p*(1-p)*abs(b)^2*abs(d)^2;
          else
            Tad = 0;
          end
          Tabc = tripart(p,b,c,d);
          Tabd = 4*abs(((p*(1-b^2)+(1-p)*d^2+(1-p)*(1-c^2-d^2))*(p*b^2+(1-p)*c^2))*p*(1-p)*c^2*b^2
+ 4*((p*(1-b^2)+(1-p)*d^2+(1-p)*(1-c^2-d^2))*(p*b^2+(1-p)*c^2))*p*(1-p)*sqrt(1-b^2)*b*d*sqrt(1-c^2-d^2));
          Tacd = 4*abs(((p*(1-b^2)+(1-p)*c^2+(1-p)*(1-c^2-d^2))*(p*b^2+(1-p)*c^2))*p*(1-p)*d^2*b^2
+ 4*((p*(1-b^2)+(1-p)*c^2+(1-p)*(1-c^2-d^2))*(p*b^2+(1-p)*c^2))*p*(1-p)*sqrt(1-b^2)*b*c*sqrt(1-c^2-d^2));

          A(i,5) = i;
          A(i,6) = real(Tabcd - Tab - Tac - Tad - Tabc - Tacd - Tabd);

          i = i + 1;
         else
       end
     end
   end
 end
end
max(A(:,6))
min(A(:,6))

plot(A(:,5),A(:,6))
xlabel('System number')
ylabel('Four-tangle')

\end{verbatim}
}

\newpage

\subsubsection{Tripartite code for $\rho_{ABC}$}
\label{app:tripartiteCode}

\begin{verbatim}

function Tabc = tripart(p,b,c,d)

if abs(c)^2+abs(d)^2 <= 1 && c ~= 0 && b ~= 0 && d~=0 &&
    1-abs(c)^2+abs(d)^2 ~= 0 && 1-abs(b)^2 ~=0

    s = 4*c*d*sqrt((1-abs(c)^2-abs(d)^2))/(b*(1-abs(b)^2));
    p0 = (s^(2/3))/(1+(s^(2/3)));
    p1 = max(p0,1/2 + 1/(2*sqrt(1+s^2)));
    if p <= p0
        Tabc = 0;
    elseif p <= p1
        Tabc = 4*abs(p^2*b^2*(1-b^2)
        - 4*b*c*d*sqrt(1-c^2-d^2)*sqrt(p*(1-p)^3));
    else
        Tabc = 4*abs(b^2*(1-b^2))*(p-p1)/(1-p1)
        + ((1-p)/(1-p1))*4*abs(b^2*(1-b^2))*(p1^2-s*sqrt(p1*(1-p1)^3));
    end

else
    Tabc = 0;

end

\end{verbatim}

\newpage

\begin{thebibliography}{99}

\bibitem{NielsenChuang}
M.~A. Nielsen
and
I.~L. Chuang,
{\it Quantum Computation and Quantum Information\/},
10th Anniversary Edition
(Cambridge University Press, Cambridge, 2010).

\bibitem{CKW}
V.~Coffman, J.~Kundu
and
W.~K.~Wooters,
``Distributed Entanglement'',
{\it Phys.\ Rev.\ A\ \bf 61}, 052306 (2000).
(arXiv:quant-ph/9907047v2)

\bibitem{SCat}
E.~Schr\"{o}dinger
``Die gegenwärtige Situation in der Quantenmechanik'',
{\it Die Naturwissenschaften, Volume 23, Issue 48, pp.807-812},
(DOI: 10.1007/BF01491891)

\bibitem{OV}
T.~J.~Osborne and F.~Verstraete,
``General Monogamy Inequality for Bipartite Qubit Entanglement'',
{\it Phys.\ Rev.\ Lett.\ \bf 96}, 220503 (2006).
(arXiv:quant-ph/0502176v5)

\bibitem{EOSU}
C.~Eltschka, A.~Osterloh, J.~Siewert and A.~Uhlmann,
``Three-tangle for Mixtures of Generalized GHZ and Generalized W States'',
{\it New J.\ Phys.\ \bf 10}, 043014 (2008).
(arXiv:quant-ph/0711.4477v1)

\bibitem{LOSU}
R.~Lohmayer, A.~Osterloh, J.~Siewert and A.~Uhlmann,
``Entangled Three-qubit States without Concurrence and Three-tangle'',
{\it Phys.\ Rev.\ Lett.\ \bf 97}, 260502 (2006).
(arXiv:quant-ph/0606071v2)

\bibitem{U}
A.~Uhlmann,
``Entropy and Optimal Decompositions of States Relative to a Maximal Commutative Subalgebra'',
{\it NTZ\ preprint,\ ZHS\ Leipzig\ \bf 9} (1997).
(arXiv:quant-ph/9704017v2)

\end{thebibliography}

\end{document}

max_stars_repo_path: Complete project/Report Final - Tom MacLean.tex


text:
\section{WGAN-GP}
To create a \gls{WGAN-GP} the architecture of the \gls{WGAN} can be modified to remove the weight clipping constraints from the critic, and its loss can be changed to have a gradient penalty term as described in \autoref{sub:wgan_gp}. The gradient penalty should offer a better alternative to weight clipping and in turn produce better results.

\subsection{MNIST}
Training the \gls{WGAN-GP} on the \gls{MNIST} dataset produced the results seen in \autoref{fig:wgan_gp_mnist_metrics}. Observe how the overall value of the metrics has improved significantly when compared to the \gls{WGAN} approach.
\begin{figure}[hbt]
    \centering
    \caption{Metrics when training a WGAN-GP on MNIST}
    \includegraphics[width=\textwidth]{chapters/Experiments/WGAN-GP/mnist_metrics.pdf}
    \fonte{From the author (2021)}
    \label{fig:wgan_gp_mnist_metrics}
\end{figure}

The same behaviour related to the number of iterations for the critic can be seen, that is, more critic iterations tend to perform less well. The \gls{lambda} term, which regulates the strength of the gradient penalty, seems to produce similar results for all values tested. Contrary to the case seen for the \gls{WGAN}, this actually agrees with the recommended value of 10 given by the authors of the \gls{WGAN-GP} paper \cite{wgan-gp2017}.

The samples produced by the overall best model (NCRIT=1  $\lambda$=10) are shown in \autoref{fig:wgan_gp_mnist_samples}.
\begin{figure}
    \centering
    \caption{Samples when training a WGAN-GP on MNIST}
    \includegraphics[width=0.6\textwidth]{chapters/Experiments/WGAN-GP/mnist_samples.png}
    \fonte{From the author (2021)}
    \label{fig:wgan_gp_mnist_samples}
\end{figure}

\subsection{Fashion MNIST}
Training the \gls{WGAN-GP} on the Fashion MNIST dataset produced the results seen in \autoref{fig:wgan_gp_fashion_metrics}. This gives very similar results and the same conclusions that were seen for the \gls{MNIST} experiments. \autoref{fig:wgan_gp_fashion_samples} shows the samples produced by the best model (\texttt{NCRIT=1 $\mathrm{\lambda}$=5}).
\begin{figure}[hbt]
    \centering
    \caption{Metrics when training a WGAN-GP on Fashion MNIST}
    \includegraphics[width=\textwidth]{chapters/Experiments/WGAN-GP/fashion_metrics.pdf}
    \fonte{From the author (2021)}
    \label{fig:wgan_gp_fashion_metrics}
\end{figure}

\begin{figure}
    \centering
    \caption{Samples when training a WGAN-GP on Fashion MNIST}
    \includegraphics[width=0.6\textwidth]{chapters/Experiments/WGAN-GP/fashion_samples.png}
    \fonte{From the author (2021)}
    \label{fig:wgan_gp_fashion_samples}
\end{figure}

\subsection{CIFAR-10}
For these experiments it was used a value of 10 for \gls{lambda} since it followed the recommendation of the original authors and has also proved to work well in all cases tested. Training the \gls{WGAN-GP} on the \gls{CIFAR}-10 dataset produced the results seen in \autoref{fig:wgan_gp_cifar_metrics}.

Once again \gls{CIFAR}-10 proves itself considerably harder to train, these results show a higher degree of instability and also produced significant less favorable results when compared to \gls{DCGAN} and \gls{CGAN}, except for the case which used \texttt{NCRIT=1}. This still agrees with the previous results and shows how consistent this technique is, making hyperparameter search easier.

\begin{figure}[hbt]
    \centering
    \caption{Metrics when training a WGAN-GP on CIFAR-10}
    \includegraphics[width=\textwidth]{chapters/Experiments/WGAN-GP/cifar_metrics.pdf}
    \fonte{From the author (2021)}
    \label{fig:wgan_gp_cifar_metrics}
\end{figure}

The best resulting model (\texttt{NCRIT=1 $\eta$=1e-4 $\beta_1$=0.0 UP=Nearest}) was able to produce the samples shown in \autoref{fig:wgan_gp_cifar_samples}.
\begin{figure}
    \centering
    \caption{Samples when training a WGAN-GP on CIFAR-10}
    \includegraphics[width=0.5\textwidth]{chapters/Experiments/WGAN-GP/cifar_samples.png}
    \fonte{From the author (2021)}
    \label{fig:wgan_gp_cifar_samples}
\end{figure}


text:
\documentclass[parskip=full,11pt]{scrartcl}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[german]{babel}

\usepackage[yyyymmdd]{datetime} % must be after babel
\renewcommand{\dateseparator}{-} % ISO8601 date format
\usepackage{hyperref}
\usepackage{listings}
\usepackage{textcomp}

\usepackage{float}
\usepackage{enumitem}
\renewcommand{\familydefault}{\sfdefault}
\usepackage{graphicx}
\usepackage{placeins}

\usepackage{lmodern}
\usepackage{courier}

\usepackage{enumitem}
\setitemize{itemsep=-8pt}
\usepackage{csquotes}

\usepackage{todonotes} % for todo notes - usage \todo{note}

\usepackage{linegoal,listings}
\newsavebox{\mylisting}
\makeatletter
\newcommand{\lstInline}[2][,]{%
	\begingroup%
	\lstset{#1}% Set any keys locally
	\begin{lrbox}{\mylisting}\lstinline!#2!\end{lrbox}% Store listing in \mylisting
	\setlength{\@tempdima}{\linegoal}% Space left on line.
	\ifdim\wd\mylisting>\@tempdima\hfill\\\fi% Insert line break
	\lstinline!#2!% Reset listing
	\endgroup%
}
\makeatother
\setlength{\parindent}{0pt}% Just for this example

\lstset{basicstyle=\footnotesize\ttfamily,breaklines=true}
\lstset{framextopmargin=50pt,frame=bottomline,showstringspaces=false,upquote=true,tabsize=4, numbers=left}

\RedeclareSectionCommand[style=section,indent=0pt,font=\usekomafont{partnumber}]{part}
\renewcommand*{\partformat}{\thepart\enskip}

\RedeclareSectionCommand[beforeskip=0pt ,afterskip=0pt]{subparagraph}

\usepackage[bottom = 3 cm, top = 3 cm]{geometry}

\newcommand{\class}[1]{\subsubsection*{\lstinline[basicstyle=\ttfamily\large]{#1}}}

% command for an attribute
\newcommand{\attr}[4]{\lstinline{[#3]} \textbf{\lstinline{#1 : #2}} \newline #4}

% command for a method
\newcommand{\method}[5]{\lstinline{[#4]} \textbf{\lstinline{#1(#3) : #2}} \newline #5}

% command for a constructor
\newcommand{\ctor}[4]{\lstinline{[#3]} \textbf{\lstinline{#1(#2)}} \newline #4}

\newcommand{\inlinecode}[1]{\lstInline[breaklines=true]{#1}}

% make the bullet symbol in lists a circle for level 2
\renewcommand{\labelitemii}{$\circ$}

% for double quotation marks in listings
\newcommand{\qq}[1]{``#1``}

\graphicspath{ {images/} }

\begin{document}
	\title{A quick guide to the implementation of analyses}
	\date{}

	\maketitle

	\section{The API}
	The package relevant for implementing analyses is \inlinecode{dfa.framework}.
	The important classes and interfaces are:

	\subsection*{LatticeElement}
	A \inlinecode{LatticeElement} represents an in- or out-state of any basic block at any given time.
	How the \inlinecode{LatticeElement} for any particular analysis looks like, entirely depends on the analysis.
	The only method a \inlinecode{LatticeElement} must provide is \inlinecode{String getStringRepresentation()}.
	This is used to create the text in the state-panel (for in- and out-states) on the right in the GUI.

	Although \inlinecode{getStringRepresentation()} is the only method that is mandatory to implement for a \inlinecode{LatticeElement}, great care should be taken when implementing \inlinecode{boolean} \inlinecode{equals(Object o)}.
	Since this method is used by the \inlinecode{DFAExecution} to determine, whether two \inlinecode{LatticeElements} are equal, incorrect implementation can easily lead to infinite loops during the precalculation of a \inlinecode{DFAExecution}.
	This is due to the fact that basic blocks are added to the worklist, whenever the out-state of one of its predecessors changes (according to \inlinecode{equals}).

	\subsection*{\inlinecode{DFAFactory<E extends LatticeElement>}}
	A \inlinecode{DFAFactory} is used to create analyses.
	Its name is determined by \inlinecode{getName()}, this is the name shown in the analyses selection box in the GUI.
	It also determines the direction (\inlinecode{DFADirection}, either forward or backward) of the analyses created from this \inlinecode{DFAFactory}.
	Finally a \inlinecode{DFAFactory} can create instances of \inlinecode{DataFlowAnalysis} from a \inlinecode{SimpleBlockGraph} with \inlinecode{DataFlowAnalysis<E>} \inlinecode{getAnalysis(SimpleBlockGraph blockGraph)}.

	\subsection*{\inlinecode{DataFlowAnalysis<E extends LatticeElement>}}
	This abstract class just combines the three interfaces \inlinecode{Initializer}, \inlinecode{Join} and \inlinecode{Transition}, each of which provides only one method:
	\begin{itemize}
		\item \inlinecode{Map<Block, BlockState<E>> getInitialStates()}: \\
		This determines the initial state for each \inlinecode{soot.toolkits.graph.Block}.
		For many analyses all blocks except the start block will be initialized with some default state.
		The in-state of the start block will sometimes require special initialization.
		E. g. for constant-folding in the initial in-state of the start block the values of all locals are set to 0.
		\item \inlinecode{E join(Set<E>)}: \\
		This method is used to join several \inlinecode{LatticeElement}s into one, whenever the control flow requires it.
		The join entirely depends on the particular \inlinecode{LatticeElement} and thus on the analysis.
		But for most analyses the join-operation is rather straightforward.
		\item \inlinecode{E transition(E element, Unit unit)}
		This method decides how a \inlinecode{soot.Unit} transforms a \inlinecode{LatticeElement}.
		Usually the most effort goes into the implementation of \inlinecode{transition} because there are a lot of different \inlinecode{Unit}s that have to be handled individually.
		If you are not familiar with Soot, this can be a bit scary at first.
		In addition to looking at the API-documentation of soot you will probably want to take a look at the source code of an existing analysis.
		A good point to start would probably be \inlinecode{ConstantFoldingTransition} since it is a functioning analysis and is still reasonably straightforward.
	\end{itemize}

	One last tip that may be helpful: when you encounter a \inlinecode{Unit} you don't want to handle, you can simply throw a subclass of \inlinecode{DFAException} (e. g. \inlinecode{UnsupportedStatementException}).
	In that case the precalculation of a \inlinecode{DFAExecution} will be aborted in an orderly fashion and an error message is shown in the GUI.
	But this also means, you can't analyze any code that produces those \inlinecode{Unit}s.
	There may also be cases, where you can safely ignore a particular \inlinecode{Unit}.
	For examples on this see the code of \inlinecode{ConstantFoldingTransition}.

	\subsection*{\inlinecode{CompositeDataFlowAnalysis<E extends LatticeElement>}}
	This is just a subclass of \inlinecode{DataFlowAnalysis} which takes one \inlinecode{Initializer}, one \inlinecode{Join} and one \inlinecode{Transition} in its constructor and delegates the calls \inlinecode{getInitialStates(...)}, \inlinecode{join(...)} and \inlinecode{transition(...)} to the given objects.
	So there are two ways of implementing a new analysis: You can extends \inlinecode{DataFlowAnalysis} and overwrite the three methods or you can implement three classes each of which implements one of the three interfaces and then just create a \inlinecode{CompositeDataFlowAnalysis} from them.
	Which one you choose is up to you, it doesn't really make a difference.
	We prefer the second approach since it naturally structures the analysis into several classes.
	If you chose to just implement the three methods in one class you will probably end up with a rather lengthy class.

	\clearpage

	\section{A minimal example}
	Previously the interfaces needed to implement a new analysis were introduced.
	Now a minimal example on how to implement an analysis is given.
	This example is not a useful analysis by any means.
	It only shows which methods must be implemented and how it could be done.
	For an example of a real analysis you could look at \inlinecode{ConstantFoldingAnalysis} (with all the classes used by it, especially \inlinecode{ConstantFoldingTransition}).

	\subsection*{\inlinecode{DFAFactory}}
	\begin{lstlisting}
package dfa.analyses.testanalyses;

import dfa.framework.DFADirection;
import dfa.framework.DFAFactory;
import dfa.framework.DataFlowAnalysis;
import dfa.framework.SimpleBlockGraph;

public class DummyFactory extends DFAFactory<DummyElement> {

	@Override
	public String getName() {
		// the name shown in the analysis selction
		return "Dummy Analysis";
	}

	@Override
	public DFADirection getDirection() {
		// let's make it a forwrad analysis
		return DFADirection.FORWARD;
	}

	@Override
	public DataFlowAnalysis<DummyElement> getAnalysis(SimpleBlockGraph blockGraph) {
		return new DummyAnalysis(blockGraph);
	}
}

	\end{lstlisting}

	\subsection*{\inlinecode{[Composite-]DataFlowAnalysis}}
	\begin{lstlisting}
package dfa.analyses.testanalyses;

import dfa.framework.CompositeDataFlowAnalysis;
import dfa.framework.SimpleBlockGraph;

public class DummyAnalysis extends CompositeDataFlowAnalysis<DummyElement> {
	public DummyAnalysis(SimpleBlockGraph blockGraph) {
		// since we extend a CompositeDataFlowAnalysis we use
		// its constructor and are done
		super(new DummyJoin(), new DummyTransition(), new DummyInitializer(blockGraph));
	}
}
	\end{lstlisting}

	\clearpage

	\subsection*{\inlinecode{LatticeElement}}
	\begin{lstlisting}
package dfa.analyses.testanalyses;

import dfa.framework.LatticeElement;

public class DummyElement implements LatticeElement {
	public final ValueType type;

	public DummyElement(ValueType type) {
		this.type = type;
	}

	@Override
	public boolean equals(Object o) {
		if (!(o instanceof DummyElement)) {
			return false;
		}

		DummyElement e = (DummyElement) o;

		// we make sure, that the same types are
		// treated as equal DummyElements
		return e.type == this.type;
	}

	@Override
	public String getStringRepresentation() {
		// here we craft the string representation of an element, this will be shown in the GUI
		switch (type) {
		case BOTTOM:
			return "B";
		case TOP:
			return "T";
		case SOMETHING:
			return "?";
		default:
			throw new IllegalStateException();
		}
	}

	enum ValueType {
		BOTTOM, TOP, SOMETHING
	}
}
	\end{lstlisting}

\clearpage

	\subsection*{\inlinecode{Initializer}}
	\begin{lstlisting}
package dfa.analyses.testanalyses;

import dfa.framework.BlockState;
import dfa.framework.Initializer;
import dfa.framework.SimpleBlockGraph;
import soot.toolkits.graph.Block;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DummyInitializer implements Initializer<DummyElement> {
	private SimpleBlockGraph blockGraph;

	public DummyInitializer(SimpleBlockGraph blockGraph) {
		this.blockGraph = blockGraph;
	}

	// this method will be used by the DFAExecution to initialize
	// the in- and out-states of all blocks
	@Override
	public Map<Block, BlockState<DummyElement>> getInitialStates() {
		List<Block> blocks = blockGraph.getBlocks();

		BlockState<DummyElement> defaultState = new BlockState<>(new DummyElement(DummyElement.ValueType.TOP), new DummyElement(DummyElement.ValueType.BOTTOM));

		Map<Block, BlockState<DummyElement>> initialMap = new HashMap<>();

		// each block simply gets the same initial in- and out-state
		for (Block b : blocks) {
			initialMap.put(b, defaultState);
		}

		return initialMap;
	}
}
	\end{lstlisting}

	\clearpage

	\subsection*{\inlinecode{Join}}
	\begin{lstlisting}
package dfa.analyses.testanalyses;

import dfa.framework.Join;

import java.util.Set;

public class DummyJoin implements Join<DummyElement> {

	// this method will be called whenever the (one ore more)
	// predecessors of one block need to be joined
	@Override
	public DummyElement join(Set<DummyElement> elements) {
		// a trivial join, for real analyses you will have to do a little more work
		return new DummyElement(DummyElement.ValueType.SOMETHING);
	}
}
	\end{lstlisting}

	\subsection*{\inlinecode{Transition}}
	\begin{lstlisting}
package dfa.analyses.testanalyses;

import dfa.framework.Transition;
import soot.Unit;

public class DummyTransition implements Transition<DummyElement> {

	// this method will be called to transition one state to another
	// over the given Unit
	@Override
	public DummyElement transition(DummyElement element, Unit unit) {
		// a trivial transition, for real analyses you will usually have to do
		// quite some work here (and at least respect the parameter unit)
		return new DummyElement(DummyElement.ValueType.SOMETHING);
	}
}
	\end{lstlisting}

	\clearpage

	\section{Deployment}
	Once you have written your own analysis, you surely want to use it.
	In order to do so you only need to put the class-files of your analysis into the right directory and upon the next start of the program it will be loaded.
	Let's assume you implemented your analysis in the package \inlinecode{dfa.analyses.myanalysis} (the package should be a subpackage of \inlinecode{dfa.analyses}), then you simply need to put the class-files into \inlinecode{root/dfa/analyses/myanalysis}, where \inlinecode{root} is the directory where the runnable jar of the main program resides.

	Note that you can also replace existing analyses like that.
	If you for example decide to write a more precise constant-bits-analysis, you can simply remove all the class-files of the old one and put in your new class-files.

\end{document}