Indian Institute of Science, Bengaluru<EMAIL_ADDRESS>Institute of
Science<EMAIL_ADDRESS>John Q. Public and Joan R. Public
[500]Mathematics of computing Discrete mathematics John Q. Open and Joan R.
Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT
2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Graph-theoretic insights on the constructability of complex entangled states

L. Sunil Chandran  Rishikesh Gajjala

###### Abstract

The most efficient automated way to construct a large class of quantum
photonic experiments is via abstract representation of graphs with certain
properties. While new directions were explored using Artificial intelligence
and SAT solvers to find such graphs, it becomes computationally infeasible to
do so as the size of the graph increases. So, we take an analytical approach
and introduce the technique of local sparsification on experiment graphs,
using which we answer a crucial open question in experimental quantum optics,
namely whether certain complex entangled quantum states can be constructed.
This provides us with more insights into quantum resource theory, the
limitation of specific quantum photonic systems and initiates the use of
graph-theoretic techniques for designing quantum physics experiments.

###### keywords:

Perfect matchings, Graph colourings, Quantum entanglement

###### category:

##  1 Introduction

Recent years have seen dramatic advances in quantum optical technology [16,
17] as photons are at the core of many quantum technologies and in the
experimental investigation of fundamental questions about our universe’s local
and realistic nature. Due to the peculiar behaviour of multi-particle
interference, designing experimental setups to generate multi-partite
entanglement in photonics is challenging. The most efficient automated way to
construct a large class of such quantum photonic experiments is via abstract
representation of graphs with certain properties [6, 10, 7] allowing new
possibilities for quantum technology [13, 5, 1]. The construction of such
graphs has been a challenging mathematical open problem as one needs to
carefully tune the edge weights to satisfy exponentially many equations [9].

Recently, new directions were explored using Artificial intelligence and SAT
solvers to find such graphs, which could be used to design quantum photonic
experiments [11, 15, 3]. However, using these methods, it is computationally
infeasible to find solutions in large graphs as the search space grows
exponentially. Therefore, more advanced analytical methods are necessary. In
this work, we introduce the technique of local sparsification on experiment
graphs, using which we answer a crucial open question in experimental quantum
optics, namely whether certain complex entangled quantum states can be
constructed. The two main ideas behind our technique are:
1) To develop an edge pruning algorithm which helps to construct quantum
optical experiments with as few resources as possible.
2) Detect a special sparse subgraph in the pruned experiment graph whose edge
count bounds the dimension of some multi-particle entangled quantum states

Our ideas are general and might be useful to understand the experimental
designs to construct several other quantum states like NOON states, cluster
states, W states and Dickes states. With more structural insights into the
graphs used for creating high-dimensional multi-particle entanglement, we
believe our techniques can be used to resolve a conjecture on the
constructability of certain complex entangled quantum states by Cervera-
Lierta, Krenn, and Aspuru-Guzik [3]. This would give us more insights into
quantum resource theory and the limitation of specific quantum photonic
systems.

##  2 Graph representation of quantum optics experiments

In 2017, Krenn, Gu and Zeilinger [10] have discovered (and later extended [7,
6]) a bridge between experimental quantum optics and graph theory. Here, large
classes of quantum optics experiments (including those containing
probabilistic photon pair sources, deterministic photon sources and linear
optics elements) can be represented as an edge-coloured edge-weighted graph.
Additionally, every edge-coloured edge-weighted graph can be translated into a
concrete experimental setup. This technique has led to the discovery of new
quantum interference effects and connections to quantum computing [6].
Furthermore, it has been used as the representation of efficient AI-based
design methods for new quantum experiments [11, 15].

###  2.1 Mathematical formulation of the problem

Figure 1: An edge-coloured edge-weighted graph. The edges
$\\{1,2\\},\\{3,4\\},\\{5,6\\},\\{3,6\\}$ are of colour green (mode number
$1$) and $\\{1,6\\},\\{2,3\\},\\{4,5\\}$ are of colour red (mode number $0$).
The edges $\\{4,6\\}$ and $\\{3,5\\}$ are bi-chromatic, where the halves
starting at the vertices $4,5$ are of the colour red, and the remaining halves
are of the colour green.

Figure 2: The vertex colourings induced by the perfect matchings of Figure 1.

We first define some commonly used graph-theoretic terms. For a graph $G$, let
$V(G),E(G)$ denote the set of vertices and edges, respectively. For
$S\subseteq V(G)$, $G[S]$ denotes the induced subgraph of $G$ on $S$.
$\mathbb{N},\mathbb{C}$ denote the set of natural and complex numbers,
respectively. The cardinality of a set $\cal{S}$ is denoted by $|\cal{S}|$.
For a positive integer $r$, $[r]$ denotes the set $\\{1,2\ldots,r\\}$.

We assume all graphs to be simple throughout unless otherwise mentioned.
Usually, in an edge colouring, each edge is associated with a natural number.
But in such edge colourings, the edges are assumed to be monochromatic. But in
the experiment graph, we are allowed to have bi-coloured edges, i.e. one half
coloured by a certain colour and the other half coloured by a different colour
(as shown in Figure 1). So, we develop some new notation to describe bi-
coloured edges.

An edge colouring $c$ associates a coloured edge $\\{(v_{1},i),(v_{2},j)\\}$
to an uncoloured edge $\\{v_{1},v_{2}\\}$ for some $i,j\in\mathbb{N}$. For an
edge $e=\\{(v_{1},i),(v_{2},j)\\}$, we say that $\\{i,j\\}$ is the colour of
$e$. We will use the notation $c(e,v_{1})$ to denote $i$ and $c(e,v_{2})$ to
denote $j$ in this case. When $c(e,v_{2})=c(e,v_{1})$, we call the edge to be
monochromatic and represent the colour of the edge by $c(e)$. If
$c(e,v_{2})\neq c(e,v_{1})$, we call the edge to be a bi-chromatic edge. The
colour degree of $u$ with respect to the colour $i$, $d(u,i)$ is the number of
edges $e$ incident on $u$ such that $c(e,u)=i$. A weight assignment $w$
assigns every edge $e$ a weight $w(e)\in\mathbb{C}\setminus\\{0\\}$.

We call a subset $P$ of edges in a graph a perfect matching if each vertex in
the graph has exactly one edge in $P$ incident on it.

######  Definition 2.1.

The weight of this perfect matching $P$, $w(P)$ is the product of the weights
of all its edges $\prod\limits_{e\in P}w(e)$

A vertex colouring $vc$ associates a colour $i$ to each vertex in the graph
for some $i\in\mathbb{N}$. We use $vc(v)$ to denote the colour of vertex $v$
in the vertex colouring $vc$. We say that each perfect matching $P$ induces a
vertex colouring $vc$ if for each vertex $v$, $vc(v)$ is equal to $c(e,v)$,
where $e$ is the unique edge in $P$ incident on $v$. We say that this vertex
colouring $vc$ is induced by $P$. Note that different perfect matchings can
induce the same vertex colouring. A vertex colouring is defined to be feasible
if it is induced by at least one perfect matching.

######  Definition 2.2.

The weight of a vertex colouring $vc$, $w(vc)$ is the sum of the weights of
all perfect matchings $P$ inducing $vc$.

The weight of a vertex colouring which is not feasible, is zero by default.

######  Definition 2.3.

An experiment graph is said to be valid, if:

  1. 1.

All feasible monochromatic vertex colourings have a weight of $1$.

  2. 2.

All non-monochromatic vertex colourings have a weight of $0$.

An example of a valid experiment graph is shown in Figure 1

######  Definition 2.4.

The dimension of a valid experiment graph $G$, $\mu(G)$ is the number of
feasible monochromatic vertex colourings having a weight of $1$.

In graph theoretic terms, Theorem 2.6 is equivalent to stating that
$\mu(G)\leq\dfrac{|V(G)|}{\sqrt{2}}$. The reader may note that the number of
particles and the dimension of a GHZ state corresponds to the number of
vertices and dimensions in the valid experiment graph, respectively. For a
detailed description of the quantum physical meaning of this setup, refer to
[9].

###  2.2 Progress on the problem

Krenn and Gu conjectured that physically it is not possible to generate a GHZ
state of dimension $d>2$ with more than $n=4$ photons with perfect quality and
finite count rates without additional resources [9], that is, when $G$ is not
isomorphic to $K_{4}$, then $\mu(G)\leq 2$. While proving their conjecture
would immediately lead to new insights into resource theory in quantum optics,
finding a counter-example would uncover new peculiar quantum interference
effects of a multi-photonic quantum system.

However, when multi-edges and bi-chromatic edges are allowed, even for a valid
experiment graph with just $4$ vertices, the question of whether the dimension
is bounded or not looks surprisingly challenging. So a general bound on the
dimension as the function of the number of vertices of the experiment graph
remains elusive. This motivated researchers to look at the problem by
restricting the presence of bi-chromatic edges and multi-edges.

Absence of destructive interference. When destructive interference is absent,
the problem reduces to a simpler problem on unweighted coloured graphs.
Bogdanov [2] proved that the dimension of a $4$ vertex experiment graph is at
most $3$, and an $n\geq 6$ vertex graph is at most $2$. Chandran and Gajjala
[4] gave a structural classification of experiment graphs of dimension $2$.
They also proved that if the maximum dimension achievable on a graph without
destructive interference is not one, the maximum dimension achievable remains
the same even if destructive interference is allowed. Vardi and Zhang [18, 19]
proposed new colouring problems which are inspired by these experiments and
investigated their computational complexity.

Absence of multi-edges. Chandran and Gajjala [4] proved that the dimension of
an $n$ vertex experiment graph is at most $n-3$ even when bi-chromatic edges
are present for simple graphs. Their techniques can be extended to get the
same bound when multi-edges are present and bi-chromatic edges are absent.

Absence of bi-chromatic edges. Ravsky [14] proposed a claim connecting this
problem to rainbow matchings. Using a result of Kostochka and Yancey [8], he
showed that the dimension of an $n$ vertex experiment graph is at most $n-2$.
Neugebauer [12] used these ideas and did computational experiments. For valid
experiment graphs with a small number of vertices, Cervera-Lierta, Krenn, and
Aspuru-Guzik [3] translated this question into a boolean equation system and
found that the system does not have a solution using SAT solvers. In
particular, they show that for graphs with monochromatic edges, GHZ states
with $n=6$, $d\geq 3$ and $n=8$, $d\geq 4$ cannot exist. The authors further
conjectured the following more general claim

######  Conjecture 2.5.

It is not possible to generate an $n>4$ vertex experiment graph with dimension
$d\geq\dfrac{n}{2}$.

In a simple valid experiment graph with $n$ vertices, as every vertex has at
most $n-1$ neighbours and each colour has at least one monochromatic edge
incident on each vertex (from 3.3), a trivial bound of $n-1$ can be obtained
on the dimension. A more careful argument would also give the same bound when
multi-edges are allowed and bi-chromatic edges are absent [12]. So far, all
results either improve an additive factor over this trivial bound or work only
on graphs with at most $8$ vertices. In this work, using the technique of
local sparsification for experiment graphs, we overcome this barrier.

######  Theorem 2.6.

It is not possible to generate an $n>4$ vertex experiment graph with dimension
$d\geq\dfrac{n}{\sqrt{2}}$.

This translates to saying that it is not possible to produce a GHZ state of
$n$ particles, with $\geq\dfrac{n}{\sqrt{2}}$ dimensions using this graph
approach without additional quantum resources (such as auxiliary photons).
Note that our bound holds even when bi-chromatic edges are allowed.

##  3 Edge pruning

We introduce the concept of an edge minimum valid experiment graph. A valid
experiment graph $G$ is said to be edge minimum if there is no other graph
$G^{\prime}$ such that $|V(G^{\prime})|=|V(G)|$, $\mu(G)=\mu(G^{\prime})$ and
$|E(G^{\prime})|<|E(G)|$. Such graphs correspond to the experiments to create
GHZ states with minimum resources and are of interest to experimental
physicists. The reader may notice that proving Theorem 2.6 for Edge minimum
valid experiment graphs implies Theorem 2.6 is true for all valid experiment
graphs.

If the monochromatic vertex colouring of colour $i$ is not feasible, then all
edges with at least half of it coloured $i$ can be discarded as such a mode
number $i$ would not help in increasing the dimension of the corresponding GHZ
state. So, in the edge minimum valid experiment graphs, all monochromatic
vertex colourings are feasible

A graph is matching covered if every edge of it is part of at least one
perfect matching. If an edge $e$ is not part of any perfect matching $M$, then
we call the edge $e$ to be redundant. By removing all redundant edges from the
given graph $G$, we get its unique maximum matching covered sub-graph.

######  Observation 3.1.

Edge minimum valid experiment graphs are matching covered.

######  Proof 3.2.

Suppose that there is an edge minimum valid experiment graph $G$ which is not
matching covered. Consider its matching covered subgraph $H$. By definition,
every perfect matching of $G$ is contained in $H$. Therefore, the weight of a
vertex colouring in $H$ and $G$ are equal; hence, $H$ is also a valid
experiment graph and $\mu(G)=\mu(H)$. Since $G$ is not matching covered, we
know that $|E(H)|<|E(G)|$. This contradicts the edge minimality of $G$.

######  Observation 3.3.

In a valid experiment graph $G$, for any vertex $v\in V(G)$ and colour
$i\in[\mu(G)]$, there exists a monochromatic edge $e$ incident on $v$ such
that $c(e)=i$.

######  Proof 3.4.

By definition, the weight of the monochromatic vertex colouring with colour
$i$ is non-zero. Therefore, there must be a monochromatic perfect matching $P$
in which all edges are of colour $i$. By the definition of perfect matching,
an edge $e\in P$ exists, which is incident on $v$. Therefore, $e$ must be of
colour $i$.

######  Definition 3.5.

If an edge $e=\\{u,v\\}$ is monochromatic and $d(u,c(e))=d(v,c(e))=1$, then
$e$ is said to be colour isolated.

######  Lemma 3.6.

For an edge $e\in E(G)$ incident on $u\in V(G)$, if $d(u,c(e))=1$, then $e$ is
a colour-isolated edge.

######  Proof 3.7.

Let $e=\\{u,v\\}$. From 3.3, we know that $e$ must be a monochromatic edge and
hence $d(v,c(e))\geq 1$. Towards a contradiction, suppose $e$ is not a colour-
isolated edge. It follows that $d(v,c(e))\geq 2$. We now construct
$G^{\prime}$, a subgraph of $G$, by removing each edge $e^{\prime}\neq e$,
which is incident on $v$ and has $c(e^{\prime},v)=c(e)$. We show that
$G^{\prime}$ is a valid experiment graph by showing that the weight of any
feasible vertex colouring $vc$ in $G^{\prime}$ is equal to the weight of $vc$
in $G$.

######  Observation 3.8.

$G^{\prime}$ is a valid experiment graph.

######  Proof 3.9.

Since $G^{\prime}$ is a subgraph of $G$, every perfect matching in
$G^{\prime}$ would also be contained in $G$. Consider a perfect matching $P$
of $G$, which is not contained in $G^{\prime}$. Let $vc$ be the vertex
colouring induced by $P$. We now claim that $vc$ is not feasible in
$G^{\prime}$.

We first prove that $vc(v)=c(e)$ and $vc(u)\neq c(e)$. As $P$ is not contained
in $G^{\prime}$, there must be an edge $e^{\prime}\in P$ such that
$e^{\prime}\in G$ and $e^{\prime}\notin G^{\prime}$. By construction, such an
$e^{\prime}\neq e$, must be incident on $v$ and has $c(e^{\prime},v)=c(e)$.
Therefore, $P$ induces the colour $c(e)$ on $v$ and hence $vc(v)=c(e)$. Since
$e^{\prime}$ is already incident on $v$, it must be the case that $e\notin P$.
As $d(u,c(e))=1$ and $e\notin P$, it follows that $vc(u)\neq c(e)$.

We now claim that a vertex colouring $vc$ with $vc(u)\neq c(e)$ and
$vc(v)=c(e)$ is infeasible in $G^{\prime}$. Suppose not. We know that there
must be a perfect matching $P^{\prime}$ inducing the vertex colouring $vc$. By
construction, $e$ is the only edge of colour $c(e)$ incident on $v$ in
$G^{\prime}$. Therefore, $e\in P^{\prime}$. As $e$ is also incident on $u$,
$P^{\prime}$ induces the colour $c(e)$ on $u$. It follows that $vc(u)=c(e)$.
Contradiction.

Therefore, if a vertex colouring $vc$ is feasible in $G^{\prime}$, then $vc$
is induced by the same set of perfect matchings in both $G$ and $G^{\prime}$.
It follows that the weight of any feasible vertex colouring $vc$ in
$G^{\prime}$ is equal to the weight of the $vc$ in $G$; hence, $G^{\prime}$ is
a valid experiment graph.

Observe that none of the removed edges could have been part of a monochromatic
perfect matching in $G$. Therefore, the monochromatic vertex colouring of
colour $i$ in $G^{\prime}$ has a weight equal to the weight of monochromatic
vertex colouring of colour $i$ in $G$, which is $1$ for all $i\in[\mu]$. It
follows that $\mu(G)=\mu(G^{\prime})$. This contradicts the edge minimality of
$G$ as $G^{\prime}$ is a valid experiment graph with $n$ vertices,
$\mu(G)=\mu(G^{\prime})$ and has fewer edges than $G$.

##  4 Proof of the Theorem 2.6

###  4.1 Proof sketch

Towards a contradiction, suppose there is exists an edge minimum simple valid
experiment graph $G$ with $n$ vertices and dimension
$\mu(G)=\mu>\dfrac{n}{\sqrt{2}}$.

If the dimension of the graph $\mu=n-1$, then it must be the case that on each
vertex $v$, $d(v,i)=1$ for every $i\in[n-1]$ (from 3.3). Similarly, as shown
in 4.1, if the dimension is $\mu$, it must be the case that $d(v,i)=1$ for at
least $2\mu-n+1$ values of $i\in[\mu]$. We then use Lemma 3.6 to guarantee
that at least $2\mu-n+1$ colour isolated edges are incident on $v$. As there
are at least $2\mu-n+1$ colour-isolated edges incident on each vertex $v$, we
get that there must be at least $0.5n(2\mu-n+1)$ colour-isolated edges in $G$.
A simple averaging argument over $\mu$ colours would now guarantee that for
some $i\in[\mu]$, there must be a large matching $M$ with
$\dfrac{(2\mu-n)n}{2\mu}$ $i$-coloured isolated edges.

In Figure 3, we find some structural properties over a special subgraph on the
vertices spanned by $M$, called the representative sparse graph. Using this,
we prove that $\mu\leq n-|M|$. Since we already know that
$|M|\geq\dfrac{(2\mu-n)n}{2\mu}$, we get that $\mu\leq\dfrac{n}{\sqrt{2}}$.
This is a contradiction. Therefore, $\mu\leq\dfrac{n}{\sqrt{2}}$.

###  4.2 Existence of a large special matching

######  Observation 4.1.

For all $v\in V(G)$, $d(v,i)=1$ for at least $2\mu-n+1$ values of $i\in[\mu]$.

######  Proof 4.2.

Suppose not. Then there are $2\mu-n-i$ colours whose colour degree is exactly
one for some vertex $v\in V(G)$ for some $i\in[0,2\mu-n]$. Therefore, there
are $n-\mu+i$ colours with a colour degree of at least $2$ on $v$. It follows
that there are $2\mu-n-i+2(n-\mu+i)=n+i\geq n$ neighbours to $v$. But since
$G$ is a simple graph, $v$ can have at most $n-1$ neighbours. Contradiction.

######  Observation 4.3.

$G$ has at least $(2\mu-n+1)\dfrac{n}{2}$ colour isolated edges.

######  Proof 4.4.

From Lemma 3.6, we know that for every colour $i$ with $d(u,i)=1$, there is a
colour isolated edge of colour $i$ incident on $u$. Along with 4.1, this
implies that there are at least $2\mu-n+1$ colour isolated edges are incident
on each vertex. Therefore, there are at least $(2\mu-n+1)\dfrac{n}{2}$ colour
isolated edges in $G$.

######  Theorem 4.5.

For some $i\in[\mu]$, there exist at least $\dfrac{(2\mu-n)n}{2\mu}$
$i$-coloured isolated edges.

######  Proof 4.6.

From 4.3, we know that there are at least $(2\mu-n+1)\dfrac{n}{2}$ colour
isolated edges. Since there are $\mu$ colours, by a simple averaging argument,
we get that for some colour $i\in[\mu]$, there exist at least
$\dfrac{(2\mu-n)n}{2\mu}$ $i$-coloured isolated edges.

###  4.3 Detecting a sparse subgraph

(a) Coloured graph $H$ where red is colour $1$

(b) Representative sparse graph $\chi(H)$

Figure 3: Constructing a representative sparse graph:
$E(\chi_{u})=\\{\\{u,1\\},\\{u,3\\},\\{u,v\\}\\}$ and
$E(\chi_{v})=\\{\\{v,4\\},\\{u,v\\}\\}$

We will assume that the large matching exhibited in Theorem 4.5 has colour $1$
for the remainder of this section. Let $R$ represent the set of vertices whose
colour degree with respect to the colour $1$ is one. Let $U$ be the set of
vertices whose colour degree with respect to the colour $1$ is at least two.

######  Observation 4.7.

$|R|\geq\dfrac{(2\mu-n)n}{\mu}$ and $|U|\leq\dfrac{n^{2}}{\mu}-n$.

######  Proof 4.8.

From Lemma 3.6, there are exactly $\dfrac{|R|}{2}$ $1$-coloured isolated edges
forming a perfect matching in the induced subgraph $G[R]$. Along with Theorem
4.5, this would imply that $|R|\geq\dfrac{(2\mu-n)n}{\mu}$ . Since
$|R|+|U|=n$, we know that $|U|\leq\dfrac{n^{2}}{\mu}-n$.

Note that since $n\geq 6$, we have
$|R|\geq\dfrac{(2\mu-n)n}{\mu}=(2-\dfrac{n}{\mu})n\geq(2-\sqrt{2})n\geq 3.5$.
Since $|R|$ must be integral, $|R|\geq 4$. Therefore, there exists at least
two $1$-coloured isolated edges.

We now pick an arbitrary $1$-coloured isolated edge $\\{u,v\\}$. For the
remainder of this section, we base our analysis on the edges incident on the
vertices $u,v$. We now construct a special subgraph on $G[R]$ called the
representative sparse graph $\chi$ using the edges incident on $u,v$.

We first construct the graph $\chi_{u}$ in the following way over $R$: For
every colour $i\in[\mu]$, if there is no vertex $w\in U$ such that
$c(\\{u,w\\},u)=i$, then add an arbitrary monochromatic edge of colour $i$
(its existence is guaranteed from 3.3) to $E(\chi_{u})$.

Similarly, we construct the graph $\chi_{v}$ in the following way over $R$:
For every colour $i\in[\mu]$, if there is no vertex $w\in U$ such that
$c(\\{v,w\\},v)=i$, then add an arbitrary monochromatic edge of colour $i$
(its existence is guaranteed from 3.3) to $E(\chi_{v})$.

We define the graph $\chi$ over $R$ with the edge set $E(\chi)=E(\chi_{u})\cup
E(\chi_{v})$. An example graph and its representative sparse graph are
presented in Figure 3.

######  Lemma 4.9.

$2\mu\leq 2|U|+|E(\chi)|+1$

######  Proof 4.10.

For any colour $i\in[\mu]$, there is either a vertex $w\in U$ such that
$c(u,\\{u,w\\})=i$ or there is a monochromatic edge of colour $i$ in
$\chi_{u}$. Therefore,

$\mu\leq|U|+|E(\chi_{u})|$

Similarly,

$\mu\leq|U|+|E(\chi_{v})|$

It is easy to see that $E(\chi_{u})\cap E(\chi_{v})=\\{\\{u,v\\}\\}$ and hence
$|E(\chi)|=|E(\chi_{u})|+|E(\chi_{v})|-1$. It follows that

$2\mu\leq 2|U|+|E(\chi_{u})|+|E(\chi_{v})|=2|U|+|E(\chi)|+1$

Since every edge in $\chi$ is incident either on $u$ or on $v$, it easy to see
that $|E(\chi)|\leq 2|R|-3$. But this can be strengthened by using the
following structural observation.

######  Lemma 4.11.

If $\\{u^{\prime},v^{\prime}\\}$ is a $1$-coloured isolated edge in $G[R]$
distinct from $\\{u,v\\}$, then

$|\\{\\{u,u^{\prime}\\},\\{u,v^{\prime}\\},\\{v,u^{\prime}\\},\\{v,v^{\prime}\\}\\}\bigcap
E(\chi)|\leq 2$

######  Proof 4.12.

Suppose
$|\\{\\{u,u^{\prime}\\},\\{u,v^{\prime}\\},\\{v,u^{\prime}\\},\\{v,v^{\prime}\\}\\}\bigcap\chi|\geq
3$. Without loss of generality, let the edges
$\\{u,u^{\prime}\\},\\{u,v^{\prime}\\},\\{v,v^{\prime}\\}$ be present in
$E(\chi)$ with colours $i,j,k$. By definition of the representative sparse
graph, we know that $i\neq j$ and $i,j,k$ are not equal to $1$. Note that $k$
might be equal to $i$ or $j$.

Consider the vertex colouring $vc$ in which $u,u^{\prime}$ get the colour $i$,
$v,v^{\prime}$ get the colour $k$, and the vertices in
$V(G)\setminus\\{u,u^{\prime},v,v^{\prime}\\}$ are coloured $1$. Note that
$V(G)\setminus\\{u,u^{\prime},v,v^{\prime}\\}$ is non-empty as $|V(G)|>4$. Let
$vc^{\prime}$ be the vertex colouring in which every vertex in $V(G)$ gets the
colour $1$.

######  Observation 4.13.

$\dfrac{w(vc)}{w(vc^{\prime})}=\dfrac{w(\\{u,u^{\prime}\\})w(\\{v,v^{\prime}\\})}{w(\\{u,v\\})w(\\{u^{\prime},v^{\prime}\\})}$

######  Proof 4.14.

Let $M$ be the set of all $1$-coloured isolated edges. As every vertex in $R$
has exactly one $1$-coloured edge incident on it, every perfect matching
$P^{\prime}$ inducing $vc^{\prime}$ must contain all edges in $M$. Let $W$
denote the weight of the monochromatic vertex colouring of colour $1$ on
$G[U]$. As the vertices in $U$ match with themselves in every perfect matching
$P^{\prime}$, it is easy to see that

$w(vc^{\prime})=W\times\prod\limits_{e\in M}w(e)$

As every vertex in $R\setminus\\{u,v,u^{\prime},v^{\prime}\\}$ has exactly one
$1$-coloured edge incident on it, every perfect matching $P$ inducing $vc$
must contain all edges in
$M\setminus\\{\\{u,v\\},\\{u^{\prime},v^{\prime}\\}\\}$. By definition of the
representative sparse graph, the vertex $u$ can obtain the colour $i$ only
through an edge $\\{u,w\\}$ such that $w\in R$. But the vertices
$R\setminus\\{u,v,u^{\prime},v^{\prime}\\}$ are already matched and
$c(\\{u,v\\},u)=1\neq i$ and $c(\\{u,v^{\prime}\\},u)=j\neq i$. Therefore, the
edge $\\{u,u^{\prime}\\}$ must be present in every perfect matching $P$ that
induces $vc$. Again, by definition of the representative sparse graph, the
vertex $v$ can obtain the colour $k$ only through an edge $\\{v,w\\}$ such
that $w\in R$. But all the vertices in $R\setminus\\{v,v^{\prime}\\}$ are
already matched. Therefore, the edge $\\{v,v^{\prime}\\}$ must be present in
every perfect matching $P$. The remaining vertices in $U$ should match among
themselves in every perfect matching $P$ that induces $vc$. It is now easy to
see that the weight of the vertex colouring $vc$ is

$w(vc)=W\times w(\\{u,u^{\prime}\\})\times
w(\\{v,v^{\prime}\\})\times\prod\limits_{e\in
M\setminus\\{\\{u,v\\},\\{u^{\prime},v^{\prime}\\}\\}}w(e)$

$=\dfrac{w(\\{u,u^{\prime}\\})w(\\{v,v^{\prime}\\})}{w(\\{u,v\\})w(\\{u^{\prime},v^{\prime}\\})}\times
W\times\prod\limits_{e\in M}w(e)$

It follows that

$\dfrac{w(vc)}{w(vc^{\prime})}=\dfrac{w(\\{u,u^{\prime}\\})w(\\{v,v^{\prime}\\})}{w(\\{u,v\\})w(\\{u^{\prime},v^{\prime}\\})}$

Since $vc^{\prime}$ is a monochromatic vertex colouring, $w(vc^{\prime})=1$.
Recall that all edge weights are non-zero by definition. Therefore, $w(vc)$ is
non-zero. But $vc$ is a non-monochromatic vertex colouring and should have
weight $0$ by definition. Contradiction.

######  Lemma 4.15.

$|E(\chi)|\leq|R|-1$

######  Proof 4.16.

From Lemma 4.11, we know that $\chi$ can contain at most two edges between
$\\{u,v\\}$ and any other $1$-coloured isolated edge. Therefore, the total
number of edges in $\chi$ is

$E(\chi)\leq 2(\dfrac{|R|-2}{2})+1=|R|-1$

######  Theorem 4.17.

$\mu\leq\dfrac{n}{\sqrt{2}}$

######  Proof 4.18.

From Lemma 4.9, we have

$2\mu\leq 2|U|+|E(\chi)|+1$

Using Lemma 4.15, we get

$2\mu\leq 2|U|+|R|$

As $|U|+|R|=n$ by definition,

$2\mu\leq 2n-|R|$

It follows from Theorem 4.5 that $|R|$ is at least $\dfrac{(2\mu-n)n}{\mu}$
and hence

$2\mu\leq 2n-\dfrac{(2\mu-n)n}{\mu}=\dfrac{n^{2}}{\mu}$

Therefore, $\mu\leq\dfrac{n}{\sqrt{2}}$.

This is a contradiction to our assumption that $\mu>\dfrac{n}{\sqrt{2}}$ and
hence, $\mu\leq\dfrac{n}{\sqrt{2}}$.

## References

  * [1] Jueming Bao, Zhaorong Fu, Tanumoy Pramanik, Jun Mao, Yulin Chi, Yingkang Cao, Chonghao Zhai, Yifei Mao, Tianxiang Dai, Xiaojiong Chen, Xinyu Jia, Leshi Zhao, Yun Zheng, Bo Tang, Zhihua Li, Jun Luo, Wenwu Wang, Yan Yang, Yingying Peng, and Jianwei Wang.  Very-large-scale integrated quantum graph photonics.  Nature Photonics, pages 1–9, 04 2023.  doi:10.1038/s41566-023-01187-z.
  * [2] Ilya Bogdanov.  Solution to graphs with only disjoint perfect matchings.  bit.ly/3x8hUGQ.  Accessed: 09-02-2023.
  * [3] Alba Cervera-Lierta, Mario Krenn, and Alán Aspuru-Guzik.  Design of quantum optical experiments with logic artificial intelligence.  Quantum, 6:836, October 2022.  doi:10.22331/q-2022-10-13-836.
  * [4] L. Sunil Chandran and Rishikesh Gajjala.  Perfect matchings and quantum physics: Progress on krenn’s conjecture.  CoRR, abs/2202.05562, 2022.  URL: https://arxiv.org/abs/2202.05562/v1, arXiv:2202.05562.
  * [5] Lan-Tian Feng, Ming Zhang, Di Liu, Yu-Jie Cheng, Guo-Ping Guo, Dao-Xin Dai, Guang-Can Guo, Mario Krenn, and Xi-Feng Ren.  On-chip quantum interference between the origins of a multi-photon state.  Optica, 10(1):105–109, Jan 2023.  URL: https://opg.optica.org/optica/abstract.cfm?URI=optica-10-1-105, doi:10.1364/OPTICA.474750.
  * [6] Xuemei Gu, Lijun Chen, Anton Zeilinger, and Mario Krenn.  Quantum experiments and graphs. iii. high-dimensional and multiparticle entanglement.  Physical Review A, 99, 03 2019.  doi:10.1103/PhysRevA.99.032338.
  * [7] Xuemei Gu, Manuel Erhard, Anton Zeilinger, and Mario Krenn.  Quantum experiments and graphs ii: Quantum interference, computation, and state generation.  Proceedings of the National Academy of Sciences, 116(10):4147–4155, 2019.  doi:10.1073/pnas.1815884116.
  * [8] Alexandr V. Kostochka and Matthew P. Yancey.  Large rainbow matchings in edge-coloured graphs.  Combinatorics, Probability and Computing, 21:255 – 263, 2012.
  * [9] Mario Krenn, Xuemei Gu, and Daniel Soltész.  Questions on the structure of perfect matchings inspired by quantum physics.  arXiv preprint arXiv:1902.06023, 2019.
  * [10] Mario Krenn, Xuemei Gu, and Anton Zeilinger.  Quantum experiments and graphs: Multiparty states as coherent superpositions of perfect matchings.  Physical review letters, 119 24:240403, 2017.
  * [11] Mario Krenn, Jakob S. Kottmann, Nora Tischler, and Alán Aspuru-Guzik.  Conceptual understanding through efficient automated design of quantum optical experiments.  Phys. Rev. X, 11:031044, Aug 2021.  URL: https://link.aps.org/doi/10.1103/PhysRevX.11.031044, doi:10.1103/PhysRevX.11.031044.
  * [12] Aaron Neugebauer.  Rainbow matchings in color-spanned graphs.  Bachelor Thesis, Universität Würzburg, 2022.  Accessed: 09-02-2023.  URL: bit.ly/40CJCsV.
  * [13] Kaiyi Qian, Kai Wang, Leizhen Chen, Zhaohua Hou, Mario Krenn, Shining Zhu, and Xiao song Ma.  Multiphoton non-local quantum interference controlled by an undetected photon.  Nature Communications, 14(1), mar 2023.  URL: https://doi.org/10.1038%2Fs41467-023-37228-y, doi:10.1038/s41467-023-37228-y.
  * [14] Alex Ravsky.  A special perfect matching in a complete edge-coloured graph.  bit.ly/3E2JpW6.  Accessed: 13-02-2023.
  * [15] Carlos Ruiz-Gonzalez, Sören Arlt, Jan Petermann, Sharareh Sayyad, Tareq Jaouni, Ebrahim Karimi, Nora Tischler, Xuemei Gu, and Mario Krenn.  Digital discovery of 100 diverse quantum experiments with pytheus, 2022\.  arXiv:2210.09980.
  * [16] Christoph Schaeff, Robert Polster, Marcus Huber, Sven Ramelow, and Anton Zeilinger.  Experimental access to higher-dimensional entangled quantum systems using integrated optics.  Optica, 2(6):523, jun 2015.  URL: https://doi.org/10.1364%2Foptica.2.000523, doi:10.1364/optica.2.000523.
  * [17] Ravitej Uppu, Leonardo Midolo, Xiaoyan Zhou, Jacques Carolan, and Peter Lodahl.  Quantum-dot-based deterministic photon–emitter interfaces for scalable photonic quantum technology.  Nature Nanotechnology, 16, 10 2021.  doi:10.1038/s41565-021-00965-6.
  * [18] Moshe Y. Vardi and Zhiwei Zhang.  Quantum-inspired perfect matching under vertex-color constraints.  CoRR, abs/2209.13063, 2022.  arXiv:2209.13063, doi:10.48550/arXiv.2209.13063.
  * [19] Moshe Y. Vardi and Zhiwei Zhang.  Solving quantum-inspired perfect matching problems via tutte’s theorem-based hybrid boolean constraints.  CoRR, abs/2301.09833, 2023.  arXiv:2301.09833, doi:10.48550/arXiv.2301.09833.