# Chordal Graphs and Distinguishability of Quantum Product States

David W. Kribs1, Comfort Mintah2, Michael Nathanson3, Rajesh Pereira1
1Department of Mathematics & Statistics, University of Guelph, Guelph, ON,
Canada N1G 2W1  2Centre for Education in Mathematics and Computing, University
of Waterloo, Waterloo, ON, Canada N2L 3G1  3Department of Mathematics, Harvard
University, Cambridge, MA, USA 02138

###### Abstract.

We investigate a graph-theoretic approach to the problem of distinguishing
quantum product states in the fundamental quantum communication framework
called local operations and classical communication (LOCC). We identify
chordality as the key graph structure that drives distinguishability in one-
way LOCC, and we derive a one-way LOCC characterization for chordal graphs
that establishes a connection with the theory of matrix completions. We also
derive minimality conditions on graph parameters that allow for the
determination of indistinguishability of states. We present a number of
applications and examples built on these results.

###### Key words and phrases:

quantum state distinguishability, product states, local operations and
classical communication, chordal graphs, graph clique cover, simplicial
vertex, graph parameters, Gram matrix, positive semidefinite matrix, operator
system.

###### 2010 Mathematics Subject Classification:

15A83, 18A10, 47L25, 47L90, 81P15, 81P45

##  1\. Introduction

One of the most important quantum communication frameworks is referred to as
local (quantum) operations and classical communication, and is denoted LOCC.
It includes many basic quantum communication protocols such as quantum
teleportation and data hiding [3, 29, 11]. The subclass of LOCC protocols
called one-way LOCC, wherein the communicating parties perform their
measurements in a prescribed order, still encapsulates many of the important
cases and has been studied from the early days of LOCC investigations [30, 25,
14, 26, 9, 31].

A central focal point of the subject, of relevance to many LOCC applications,
is the development of techniques to distinguish amongst known sets of quantum
states using only one-way LOCC operations. Our work on LOCC quantum state
distinguishability began with the application and development of techniques
from matrix and operator theory [18, 19, 20]. Most importantly for this work,
we recently introduced an orthogonal graph representation approach to the
problem of distinguishing sets of quantum product states [21, 22].

In this paper, we deepen this investigation with a number of results and
applications that further strengthen the connections between graph theory,
LOCC, and linear algebra and operator theory. Specifically, we begin by
formulating a notion of a distinguishability set and prove its equivalence to
certain decompositions of positive semidefinite matrices. We identify
chordality as the main graph structure that drives distinguishability, and we
establish a characterization of chordal graphs in terms of one-way LOCC
distinguishability of bipartite product states. Our key technical device in
linking these two notions comes from matrix completion theory. We then turn
our focus to decidedly non-chordal graphs, and derive results that allow for
determination of indistinguishability of states. We identify minimality
conditions in terms of standard graph parameters imply the
indistinguishability of sets of states. Throughout the work we also present a
number of illustrative examples and applications of our main results,
including further new results in special cases as consequences, improvements
and new proofs for some previous results, and new graph-theoretic perspectives
for some seminal examples in the subject.

This paper is organized as follows. In the next section we include the
necessary background material from quantum information and graph theory.
Section 3 contains the main results on distinguishability and chordal graphs,
and Section 4 flips the focus to indistinguishability and other relevant graph
structures. Applications and examples for each part are included as
subsections.

##  2\. Preliminaries

We use standard quantum information notation, including the Dirac notation of
ket’s $|\psi\rangle$ for pure states (unit vectors) in a given Hilbert space
and bra’s $\langle\psi|$ for the dual vectors. The standard orthonormal basis
for $\mathbb{C}^{d}$ is denoted by
$\\{|0\rangle,|1\rangle,\ldots,|d-1\rangle\\}$, and the corresponding basis
for $\mathbb{C}^{d}\otimes\mathbb{C}^{n}$ is written in shorthand as
$|ij\rangle=|i\rangle\otimes|j\rangle$.

Our basic setting is a situation in which two parties, called Alice and Bob,
each in control of a quantum system represented on finite-dimensional Hilbert
spaces $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$, are physically separated so
that their measurement protocols are restricted to those only using local
quantum operations and classical communications (LOCC). Their joint system
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ has been prepared in a pure state from
a known set of states $\mathcal{S}=\\{|\psi_{i}\rangle\\}$, and Alice and Bob
would like to determine the value of $i$ only using LOCC. We consider the sub-
paradigm called one-way LOCC, wherein Alice can perform a measurement on her
system and then communicate (classically) the result to Bob, who can then
perform a measurement on his system. Mathematically, a one-way LOCC
measurement is of the form ${\mathbb{M}}=\\{A_{k}\otimes B_{k,j}\\}$, with the
positive operators making up the measurement outcomes satisfying
$\sum_{k}A_{k}=I_{A}$ and $\sum_{j}B_{k,j}=I_{B}$ for each $k$. If the outcome
$A_{k}\otimes B_{k,j}$ is obtained for any $k$, the conclusion is that the
prepared state was $|\psi_{j}\rangle$. More generally, a positive operator
valued measure (POVM) is a set of operators $E_{k}\geq 0$ such that
$\sum_{k}E_{k}=I$.

As in [21], we shall focus on the problem of distinguishing sets of quantum
product states, which are tensor products of states on the individual
subsystems, $|\psi\rangle=|\psi^{A}\rangle\otimes|\psi^{B}\rangle$. It is this
class of quantum states that allows for a link with graph theory. See [23, 24,
13, 7, 12, 1, 6, 2, 15, 28] as entrance points into the literature on graphs
and their uses in linear algebra. Here we present the basic notions that will
be used throughout the paper, with additional definitions introduced as needed
in subsequent sections.

Let $G=(V,E)$ be a (simple) graph with vertex set $V$ and edge set $E$. For
$v,w\in V$, we write $v\sim w$ if the edge $(v,w)\in E$. The complement of $G$
is the graph $\overline{G}=(V,\overline{E})$, where the edge set
$\overline{E}$ consists of all two-element sets from $V$ that are not in $E$.
Another graph $G^{\prime}$ is a subgraph of $G$, written $G^{\prime}\leq G$,
if $V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$ with $v,w\in
V^{\prime}$ whenever $(v,w)\in E^{\prime}$. For a subset of the vertices
$V^{\prime}\subset V$, $G^{\prime}=(V^{\prime},E^{\prime})$ is the induced
subgraph of $G$ on $V^{\prime}$ when $E^{\prime}=\\{(v,w)\in E:v,w\in
V^{\prime}\\}$. The complete graph on $n$-vertices, is
$K_{n}=(\\{v_{1},\dots,v_{n}\\},E)$ such that $E=\\{(v,w):v\neq w\in V\\}$.
The cycle graph on $n$-vertices is $C_{n}=(\\{v_{1},\dots,v_{n}\\},E)$ such
that $E=\\{(v_{i},v_{i+1}):1\leq i\leq n-1\\}\cup\\{(v_{n},v_{1})\\}$.

A set of graphs $\\{G_{i}=(V_{i},E_{i})\\}$ covers a graph $G=(V,E)$ if
$V=\cup_{i}V_{i}$ and $E=\cup_{i}E_{i}$. A collection of graphs $\\{G_{i}\\}$
is a clique cover for $G$ if $\\{G_{i}\\}$ covers $G$ and if each of the
$G_{i}$ is a ‘clique’; i.e., a complete graph. The clique cover number
$\mathrm{cc}(G)$ is the smallest possible number of subgraphs contained in a
clique cover of $G$. Note that a clique cover can be thought of as a
collection of (not necessarily disjoint) induced subgraphs of $G$, each of
which is a complete graph. It is a cover if every edge is contained in at
least one of the cliques. A simplicial vertex in $G$ is a vertex whose
neighbor vertices form a clique; i.e., any two neighbors of a simplicial
vertex are adjacent in the graph.

The following class of graphs is central to our analysis.

######  Definition 1.

A graph $G$ is _chordal_ if it possesses no chordless cycles of length four or
greater; i.e., all cycles in $G$ of four or more vertices have a cycle chord.
Equivalently, every induced cycle of $G$ must have exactly three vertices.

The link we make use of between graph theory and Hilbert space structure is
the following. Given a graph $G=(V,E)$, a function
$\phi:V\rightarrow\mathbb{C}^{d}\backslash\\{0\\}$ is an orthogonal
representation of $G$ if for all vertices $v_{i}\neq v_{j}\in V$,
$v_{i}\not\sim v_{j}$ if and only if
$\langle\phi(v_{i})|\phi(v_{j})\rangle=0$. For more details on orthogonal
representations of graphs we point the reader to [13, 23, 7, 6].

As introduced in [21], every set of product states naturally defines
orthogonal graph representations as follows.

######  Definition 2.

Let
$\mathcal{S}=\\{|\psi^{A}_{k}\rangle\otimes|\psi^{B}_{k}\rangle\\}_{k=1}^{r}$
be a set of product states on $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. The
graph of these states from Alice’s perspective is the unique graph $G_{A}$
with vertex set $V=\\{1,2,\ldots,r\\}$ such that the map
$k\mapsto|\psi^{A}_{k}\rangle$ is an orthogonal representation of $G_{A}$.
Likewise, the graph of the states from Bob’s perspective is the graph $G_{B}$
with vertex set $V$ such that $k\mapsto|\psi^{B}_{k}\rangle$ is an orthogonal
representation of $G_{B}$.

Observe that a set of product states are mutually orthogonal precisely when
Alice’s graph is a subgraph of the complement of Bob’s graph; i.e.,
$G_{A}\leq\overline{G_{B}}$.

##  3\. Distinguishability Sets and Chordal Graphs

We begin by recalling a pair of notions from matrix theory. Let $M$ be a
positive definite matrix, then the support of $M$ is the set $\\{i:m_{ii}\neq
0\\}$. Let $\mathcal{S}=\\{|\phi_{i}\rangle\\}_{i=1}^{n}$ be a collection of
pure states all on a Hilbert space $\mathcal{H}$, then the Gram matrix of
$\mathcal{S}$ is the $n$ by $n$ (positive semidefinite) matrix whose $(i,j)$th
entry is the inner product $\langle\phi_{i}|\phi_{j}\rangle$.

######  Definition 3.

Let $\mathcal{S}=\\{|\phi_{i}\rangle\\}_{i=1}^{n}$ be a collection of pure
states on the Hilbert space $\mathcal{H}$, and let $\\{A_{k}\\}_{k=1}^{m}$ be
a collection of subsets of $\mathcal{S}$. Then $\\{A_{k}\\}_{k=1}^{m}$ is said
to be a distinguishability set for $\mathcal{S}$ if there exists a POVM
$\\{E_{k}\\}_{k=1}^{m}$ on $\mathcal{H}$ with $m$ outcomes with the property
that if we perform the measurement on $|\phi\rangle\in\mathcal{S}$ and we can
get outcome number $k$, then $|\phi\rangle$ must be in $A_{k}$; i.e.,
$|\phi_{i}\rangle\notin A_{k}$ implies that $E_{k}|\phi_{i}\rangle=0$.

As an illustrative special case, if the states $|\phi_{i}\rangle$ are mutually
orthogonal and the sets $A_{k}$ are disjoint with union equal to the set
$\\{1,\ldots,n\\}$, then $E_{k}=\sum_{j\in
A_{k}}|\phi_{j}\rangle\\!\langle\phi_{j}|$ defines such a POVM. In general,
the distinguishability sets of $\mathcal{S}$ and the Gram matrix of
$\mathcal{S}$ can be related in the following result.

######  Theorem 1.

Let $\mathcal{S}=\\{|\phi_{i}\rangle\\}_{i=1}^{n}$ be a collection of pure
states on the Hilbert space $\mathcal{H}$ and let $M$ be the Gram matrix of
$\mathcal{S}$. Let $\\{T_{k}\\}_{k=1}^{m}$ be a collection of subsets of
$\\{1,2,...,n\\}$ and let $A_{k}=\\{|\phi_{i}\rangle\\}_{i\in T_{k}}$ for
$1\leq j\leq m$. Then the following are equivalent:

  1. (1)

$\\{A_{k}\\}_{k=1}^{m}$ is a distinguishability set for $S$.

  2. (2)

There exists a set of non-zero $n$ by $n$ positive semidefinite matrices
$\\{M_{k}\\}_{k=1}^{m}$ such that $\sum_{k=1}^{m}M_{k}=M$ and $M_{k}$ is
supported on $T_{k}$ for $1\leq k\leq m$.

###### Proof.

Without loss of generality let us assume that the states
$\\{|\phi_{i}\rangle\\}_{i=1}^{n}$ span $\mathcal{H}$ (so
$d:=\dim{\mathcal{H}}\leq n$). Let $X$ be the rank-$d$ linear operator from
$\mathbb{C}^{n}$ to $\mathcal{H}$ which maps the standard basis vector
$|j\rangle$ to $|\phi_{j}\rangle$ for all $j$. That is,
$X=\sum_{j=1}^{n}|\phi_{j}\rangle\\!\langle j|$. It is immediate to see that
$M=X^{*}X$.

To prove that (1) implies (2): Let $\\{E_{k}\\}_{k=1}^{m}$ be the POVM that
implements this distinguishability set $\\{A_{k}\\}$. For each $1\leq k\leq
m$, we can define the positive semidefinite matrix $M_{k}=X^{*}E_{k}X$. That
is, $M_{k}$ is the $n$ by $n$ matrix whose $(i,j)$th entry is
$\langle\phi_{i}|E_{k}|\phi_{j}\rangle$. We can check that
$\sum_{k}M_{k}=\sum_{k}X^{*}E_{k}X=X^{*}X=M$, since the elements of the POVM
sum to the identity.

By Definition 3, $\langle\phi_{i}|E_{k}|\phi_{j}\rangle\neq 0$ implies that
$|\phi_{i}\rangle$ and $|\phi_{j}\rangle$ are both in $A_{k}$. Hence $M_{k}$
is supported on $T_{k}$.

For the converse (2) implies (1): We are given the decomposition
$M=\sum_{k=1}^{m}M_{k}$, with each $M_{k}$ supported on $T_{k}$, and we wish
to construct a POVM to distinguish the sets $\\{A_{k}\\}$, with each
$A_{k}=\\{|\phi_{i}\rangle\\}_{i\in T_{k}}$. We can write each
$M_{k}=\sum_{i}v_{k,i}v_{k,i}^{*}$ for unnormalized vectors
$v_{k,i}\in{\mathbb{C}}^{n}$. Since $0\leq M_{k}\leq M$, we see that each
$v_{k,i}$ is in the image of $M=X^{*}X$, and hence in the image of $X^{*}$.
Thus, there exists a state $|\varphi_{k,i}\rangle$ and a positive constant
$\mu_{k,i}$ such that $X^{*}|\varphi_{k,i}\rangle=\frac{1}{\mu_{k,i}}v_{k,i}$,
for each $k$ and $i$.

We can now explicitly define
$E_{k}=\sum_{i}\mu_{k,i}^{2}|\varphi_{k,i}\rangle\\!\langle\varphi_{k,i}|$. We
claim that $\\{E_{k}\\}$ is a POVM that implements $\\{A_{k}\\}$ as a
distinguishability set.

Firstly, each $E_{k}\geq 0$ by construction, so showing it is a POVM requires
only that $\sum_{k}E_{k}=I_{d}$. We calculate:

(1)
$X^{*}\left(\sum_{k}E_{k}\right)X=\sum_{k}X^{*}E_{k}X=\sum_{k}M_{k}=M=X^{*}X.$

Hence, $X^{*}\left(I_{d}-\sum_{k}E_{k}\right)X=0$, which implies that
$\sum_{k}E_{k}=I_{d}$ (since the rank of $X$ is the dimension $d$ of
${\mathcal{H}}$ and the nullity of $X^{*}$ is 0).

Lastly, we show that this POVM distinguishes $\\{A_{k}\\}$. Given our
definition of $X$, we see that for each $i$ and $k$,

(2) $\langle i|M_{k}|i\rangle=\langle
i|X^{*}E_{k}X|i\rangle=\langle\phi_{i}|E_{k}|\phi_{i}\rangle.$

Since $|\phi_{i}\rangle\notin A_{k}$ implies that $\langle
i|M_{k}|i\rangle=0$, it also implies
$\langle\phi_{i}|E_{k}|\phi_{i}\rangle=0$, and so our POVM distinguishes the
$\\{A_{k}\\}$. ∎

For one-way LOCC on product states, we can define a variant of the Gram matrix
that uses only the component of the state that we are going to measure first.

######  Definition 4.

Let $\mathcal{S}=\\{|\psi_{i}^{A}\rangle\otimes|\psi_{i}^{B}\rangle\\}$ be a
collection of product states on the Hilbert space
$\mathcal{H}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Then the Alice Gram
matrix of $\mathcal{S}$ is the $n$ by $n$ matrix whose $(i,j)$th entry is
$\langle\phi_{i}^{A}|\phi_{j}^{A}\rangle$, and the Bob Gram matrix of
$\mathcal{S}$ is the $n$ by $n$ matrix whose $(i,j)$th entry is
$\langle\phi_{i}^{B}|\phi_{j}^{B}\rangle$.

We shall follow the notation from [27] in the following. If $G=(V,E)$ is a
graph, then let

$\mathcal{S}_{G}=\\{[a_{ij}]:a_{ij}=0\,\,\mathrm{if}\,\,(i,j)\notin E\\}$

be the operator system defined by the graph, where the matrix sizes are given
by the cardinality of the vertex set (and non-zero diagonal entries are
allowed). Observe that $G_{1}\leq G_{2}$ implies $S_{G_{1}}\subseteq
S_{G_{2}}$. We note that the notation $\mathcal{S}_{G}$ has more restrictive
meaning in the minimum rank literature; but this will not be significant in
what follows.

######  Corollary 1.

Let $\mathcal{S}$ be a collection of orthonormal product states with Alice
Gram matrix $M$. Then $\mathcal{S}$ is distinguishable with one way LOCC with
Alice going first if and only if $M$ is the sum of rank one positive
semidefinite matrices in $\mathcal{S}_{\overline{G_{B}}}$.

###### Proof.

Let $M$ be the Alice Gram matrix of $\mathcal{S}$ and suppose we have rank one
positive semidefinite elements $M_{k}$ of $\mathcal{S}_{\overline{G_{B}}}$ for
all $k$, such that $M=\sum_{k=1}^{m}M_{k}$. Then there exists a set of
(possibly overlapping) cliques $\\{T_{k}\\}_{k=1}^{m}$ that define a graph
$G\subseteq\bigcup_{k=1}^{m}T_{k}$ with $G\leq\overline{G_{B}}$, such that
$M_{k}$ is supported on $T_{k}$. (The graph $T_{k}$ is determined by the
support of $M_{k}$, and the fact it is a clique follows since $M_{k}$ is rank
one.) By Theorem 1, there is a POVM on $\mathcal{H}_{A}$ corresponding to this
clique cover of $G$. If Alice applies this POVM (which acts on her component
of the states) and gets say outcome $k$, then she can restrict the state to be
determined to those corresponding to elements of $T_{k}$, which is a clique in
$G$ and hence in $\overline{G_{B}}$. As the corresponding vertices are
mutually disconnected in $G_{B}$, Bob is left with an orthonormal set of
states that he can then distinguish.

Conversely, if $\mathcal{S}$ is distinguishable by one-way LOCC with Alice
going first, then there must be a clique cover $\\{T_{k}\\}_{k=1}^{m}$ of
$\overline{G_{B}}=G$ which corresponds to a distinguishability set for the
Alice components of the set of states. By Theorem 1, this means that there
exists positive semidefinite matrices $\\{M_{k}\\}_{k=1}^{m}$ such that
$\sum_{k=1}^{m}M_{k}=M$ and $M_{k}$ is supported on $T_{k}$ for $1\leq k\leq
m$. Each $M_{k}$ can be written as a sum of rank-one positive semidefinite
matrices (the total number of which equals the rank of $M_{k}$). The diagonal
entries of any of these rank one matrices must be less than or equal to the
corresponding diagonal entries of $M_{k}$. Hence these rank one matrices must
necessarily be supported on $T_{k}$, which means they are all members of
$\mathcal{S}_{\overline{G_{B}}}$. ∎

We can use this result to derive an LOCC-based characterization of graph
chordality. In doing so, we link this LOCC condition with other matrix
theoretic conditions via the main result from [27]. We state the relevant part
of [27, Theorem 2.4] for our purposes as the following lemma.

######  Lemma 1.

Let $G$ be a graph. Then every positive semidefinite matrix in
$\mathcal{S}_{G}$ is the sum of rank one positive semidefinite matrices in
$\mathcal{S}_{G}$ if and only if $G$ is a chordal graph.

We can now prove our main result.

######  Theorem 2.

Let $G$ be a graph with $n$ vertices. Then $G$ is chordal if and only if every
collection of $n$ product states having Alice graph $G_{A}$ and Bob graph
$G_{B}$ with $G_{A}\leq G\leq\overline{G_{B}}$ is distinguishable with one-way
LOCC with Alice going first.

###### Proof.

Suppose $G$ is chordal and we have a collection of $n$ product states with
$G_{A}\leq G\leq\overline{G_{B}}$. Let $M$ be the Gram Matrix of the Alice
components of the product states. Then $M\in\mathcal{S}_{G}$. Since $G$ is
chordal, Lemma 1 implies that $M$ can be written as a sum of rank one positive
semidefinite matrices in
$\mathcal{S}_{G}\subseteq\mathcal{S}_{\overline{G_{B}}}$. Hence $\mathcal{S}$
is distinguishable by one-way LOCC with Alice going first by Corollary 1.

Now suppose $G$ is not chordal. Let $M\in\mathcal{S}_{G}$ be a positive
semidefinite matrix in $S_{G}$ which is not the sum of rank one positive
semidefinite matrices in $\mathcal{S}_{G}$, as is given by Lemma 1. We can
assume without loss of generality that $M$ has all its non-zero diagonal
entries equal to 1; indeed, any general $M$ is similar to such a matrix via a
positive diagonal similarity matrix, which will not disrupt the matrix
belonging to $S_{G}$ or it not being a sum of rank one matrices in $S_{G}$. We
now construct a set of product states as follows. The Alice components of the
states are chosen so as to have Gram matrix $M$ (a matrix $X$ can be
constructed using the entries of $M$ with $X^{*}X=M$, similar to the proof of
Theorem 1). The Bob components of the states are chosen so that
$\overline{G_{B}}=G$. By Corollary 1, this set of states is not
distinguishable by one-way LOCC with Alice going first. ∎

######  Remark 1.

This result has a number of consequences for distinguishability, some of which
we will explore below. We note this result subsumes Proposition 3 of [21],
which proved the forward direction of the result for the subclass of chordal
graphs called $k$-trees. We also note that a weaker converse of the result is
also relatively simple to show: Let $G_{A}=\overline{G_{B}}$ be any graph for
which the minimum vector rank is strictly less than the clique cover number
$\mathrm{cc}(G_{A})$. Then there exist representations of $G_{A}$ that cannot
be distinguished with one-way LOCC. This follows immediately from looking at
representations in the minimum dimension.

###  3.1. Applications and Examples

The results above show how one-way distinguishability is linked with chordal
graph structure. Here we present some examples that illustrate this connection
and its limitations. As applications we also derive a new distinguishability
result, an improvement of a previous result, and a new proof for another.

######  Example 1.

Consider the (unnormalized) set of qubit-qutrit product states
$|\psi_{i}\rangle\in\mathbb{C}^{2}\otimes\mathbb{C}^{3}$, for $1\leq i\leq 4$,
defined as follows:

$\displaystyle|\psi_{1}\rangle$ $\displaystyle=|0\rangle\otimes|0\rangle$
$\displaystyle|\psi_{2}\rangle$
$\displaystyle=\left(|0\rangle+|1\rangle\right)\otimes|1\rangle$
$\displaystyle|\psi_{3}\rangle$
$\displaystyle=\left(|0\rangle-|1\rangle\right)\otimes|1\rangle$
$\displaystyle|\psi_{4}\rangle$
$\displaystyle=\left(|0\rangle+|1\rangle\right)\otimes|2\rangle$

Here we have Alice graph as the four cycle $C_{4}$ with the edge $(3,4)$
removed and the edge $(1,4)$ added. The Bob graph is the graph with four
vertices and a single edge $(2,3)$. Thus, $G_{A}\lneq\overline{G_{B}}$ and
both of these graphs are chordal.

Observe these states are one-way distinguishable with Alice going first.
Indeed, she can measure in her $\\{|+\rangle,|-\rangle\\}$ basis, then
communicate the result to Bob, which will tell him the state is either from
the set $\\{1,2,4\\}$ (in the case of a $+$ result), or the set $\\{1,3\\}$
(in the case of a $-$ result). Bob then can measure in his
$\\{|0\rangle,|1\rangle,|2\rangle\\}$ basis to determine which state they
have.

######  Example 2.

As a variant on the previous example, consider the two-qubit states
$|\psi_{i}\rangle\in\mathbb{C}^{2}\otimes\mathbb{C}^{2}$, for $1\leq i\leq 4$,
defined as follows:

$\displaystyle|\psi_{1}\rangle$ $\displaystyle=|0\rangle\otimes|0\rangle$
$\displaystyle|\psi_{2}\rangle$
$\displaystyle=\left(|0\rangle+|1\rangle\right)\otimes|1\rangle$
$\displaystyle|\psi_{3}\rangle$
$\displaystyle=\left(|0\rangle-|1\rangle\right)\otimes|1\rangle$
$\displaystyle|\psi_{4}\rangle$ $\displaystyle=|1\rangle\otimes|0\rangle$

These states cannot be distinguished via one-way LOCC with Alice going first,
as Bob can only distinguish amongst the first pair or the second pair of
states, and Alice cannot reduce the problem to those pairs no matter what her
measurement is.

Note in this case that the Alice graph is just the four cycle $C_{4}$, which
is not chordal. The Bob graph is the graph with four vertices and two edges
$\\{(2,3),(1,4)\\}$. So we have $G_{A}=\overline{G_{B}}$, and this graph is
not chordal.

These examples exhibit the role of chordal graphs in one-way
distinguishability as given in the theorem above, and they may be viewed as
special cases of the following consequence of that result.

######  Corollary 2.

Let $\mathcal{S}$ be a collection of orthonormal product states. If $G_{A}$ or
$\overline{G_{B}}$ is a chordal graph, then the states in $\mathcal{S}$ are
one-way distinguishable with Alice going first.

###### Proof.

This is a straightforward consequence of the forward direction of Theorem 2,
applied with $G$ equal to a chordal choice amongst the graph set
$\\{G_{A},\overline{G_{B}}\\}$. ∎

This result improves on Proposition 2 of [21] (which just proved the result
for the Bob complement graph). The converse of this result does not hold, as
shown by the following example; and indeed this owes to the fact that graph
chordality as characterized in the theorem depends on all possible sets of
product states (and not just one) with Alice-Bob graphs sandwiched around the
graph to be distinguishable.

######  Example 3.

Consider the (unnormalized) set of states
$|\psi_{i}\rangle\in\mathbb{C}^{4}\otimes\mathbb{C}^{2}$, for $1\leq i\leq 4$,
defined as follows:

$\displaystyle|\psi_{1}\rangle$
$\displaystyle=\left(|0\rangle+|1\rangle\right)\otimes|0\rangle$
$\displaystyle|\psi_{2}\rangle$
$\displaystyle=\left(|1\rangle+|2\rangle\right)\otimes|1\rangle$
$\displaystyle|\psi_{3}\rangle$
$\displaystyle=\left(|0\rangle+|3\rangle\right)\otimes|1\rangle$
$\displaystyle|\psi_{4}\rangle$
$\displaystyle=\left(|2\rangle+|3\rangle\right)\otimes|0\rangle$

As in Example 2, the Alice graph is the four cycle $C_{4}$, and the Bob graph
is its complement with four vertices and edges $\\{(1,4),(2,3)\\}$. So
$G_{A}=\overline{G_{B}}$ and this graph is not chordal, but nevertheless the
states are distinguishable. Indeed, Alice can measure in her
$\\{|0\rangle,|1\rangle,|2\rangle,|3\rangle\\}$ basis, the result of which
will (respectively) tell Bob the state is amongst the pairs
$\\{1,3\\},\\{1,2\\},\\{2,4\\},\\{3,4\\}$, and he can then determine the state
from the given pairing by measuring in his $\\{|0\rangle,|1\rangle\\}$ basis.

So the converse of the corollary does not hold. Also note that there is no
contradiction with the theorem statement here, as, for instance, Example 2
gives a set of states with the same (non-chordal) graph that are not
distinguishable.

The realization of the LOCC connection with chordal graphs also allows us to
prove the following result, which covers a broad class of product state sets.

######  Corollary 3.

Let $n,d>1$. Suppose we have a set of orthonormal product states in
$\mathbb{C}^{n}\otimes\mathbb{C}^{d}$ such that Alice’s graph or Bob’s
complement graph have clique cover number less than or equal to two; that is,

$\min\\{\mathrm{cc}(G_{A}),\mathrm{cc}(\overline{G_{B}})\\}\leq 2.$

Then the states are distinguishable via one-way LOCC with Alice going first.

###### Proof.

Note that a graph $G$ with clique cover number less than or equal to 2 is
necessarily chordal. Indeed, if it was not chordal, then we could find a cycle
within the graph with four (or more) vertices such that the graph includes no
edges between the cycle vertices other than on the cycle. Hence, given a
clique cover of $G$, any three consecutive edges on the cycle must belong to
different cliques, which means the clique cover number for the graph must be
at least three. Thus, we have $G_{A}$ or $\overline{G_{B}}$ is a chordal
graph, and so the result follows from Theorem 2 applied to a chordal graph
from the set $\\{G_{A},\overline{G_{B}}\\}$. ∎

For illustrative purposes, let us explicitly describe how a one-way LOCC
measurement can be constructed in the special case of the previous result,
where the clique cover number of Bob’s complement graph is either one or two.

######  Example 4.

Let $\\{|\psi_{k}^{A}\rangle\otimes|\psi_{k}^{B}\rangle\\}_{k\in I}$ be a set
of orthonormal product states in $\mathbb{C}^{n}\otimes\mathbb{C}^{d}$ and let
$\overline{G}_{B}$ be a the complement of the corresponding Bob graph. If
$\mathrm{cc}(\overline{G}_{B})=1$ then $\\{|\psi_{k}^{B}\rangle\\}_{k\in I}$
is an orthogonal set and Bob can distinguish the states without Alice
performing any measurements. So suppose $\mathrm{cc}(\overline{G}_{B})=2$,
corresponding to cliques $V_{1}$ and $V_{2}$. We can then partition our index
set $I$ into disjoint subsets $I=I_{1}\cup I_{2}\cup I_{3}$, where
$I_{1}=V_{1}\cap\overline{V_{2}}$, $I_{2}=V_{2}\cap\overline{V_{1}}$ and
$I_{3}=V_{1}\cap V_{2}$ (possibly empty). Both
$\\{|\psi_{k}^{B}\rangle\\}_{k\in I_{1}\cup I_{3}}$ and
$\\{|\psi_{k}^{B}\rangle\\}_{k\in I_{2}\cup I_{3}}$ are orthogonal subsets of
$\mathbb{C}^{d}$ and with $\langle\psi_{j}^{B}|\psi_{k}^{B}\rangle\neq 0$ if
$j\in I_{1}$ and $k\in I_{2}$. Since the product states are orthogonal,
$\langle\psi_{j}^{A}|\psi_{k}^{A}\rangle=0$ if $j\in I_{1}$ and $k\in I_{2}$.
Therefore $S_{1}=\mathrm{span}\\{|\psi_{k}^{A}\rangle:k\in I_{1}\\}$ and
$S_{2}=\mathrm{span}\\{|\psi_{k}^{A}\rangle:k\in I_{2}\\}$ are two mutually
orthogonal subspaces of $\mathbb{C}^{n}$. Alice can thus perform corresponding
projection-valued measurement which will leave Bob with an orthogonal subset
of either $\\{|\psi_{k}^{B}\rangle\\}_{k\in I_{1}\cup I_{3}}$ and
$\\{|\psi_{k}^{B}\rangle\\}_{k\in I_{2}\cup I_{3}}$ or
$\\{|\psi_{k}^{B}\rangle\\}_{k\in I_{3}}$, which he can then distinguish.

We finish by providing a new proof of a result from [22] (which in turn built
on a result from [21]) that identified a case, that of the ‘single qubit
sender’, in which distinguishability is completely described by graph
conditions.

######  Corollary 4.

A set of orthonormal product states in $\mathbb{C}^{2}\otimes\mathbb{C}^{d}$,
for $d\geq 2$, is distinguishable via one-way LOCC with Alice going first if
and only if there is some graph between the two graphs $G_{A}$ and
$\overline{G_{B}}$ with clique cover number at most two; that is, there is a
graph $G$ such that

(3) $G_{A}\leq G\leq\overline{G_{B}}\quad\mathit{and}\quad\mathrm{cc}\,(G)\leq
2.$

###### Proof.

As noted in Theorem 7 of [22], if the states are one-way distinguishable with
Alice going first, then the existence of such a $G$ and a clique cover that
satisfies $\mathrm{cc}(G)\leq 2$ follows from Theorem 1 of [21] restricted to
the case $\dim\mathcal{H}_{A}=2$.

For the converse direction, a direct constructive proof based on the different
possible clique cover sizes was presented in [22]. Here we simply note that
$\mathrm{cc}(G)\leq 2$ implies that $G$ is chordal (as in the previous result
proof), and hence this direction follows from the corresponding implication of
Theorem 2. ∎

Note that the distinguishability (or not) of Examples 1 and 2 can also be seen
as a direct consequence of the graph condition of this result.

##  4\. LOCC and Graph Representations of Minimum Rank

Our main theorem builds an association between decompositions of matrices in
$\mathcal{S}_{G}$ and POVMs that initiate an LOCC discrimination protocol, and
it establishes that the chordality of $G$ is equivalent to the existence of a
distinguishable set of cliques for any representation of $G$. As a contrast,
here we will consider graphs that are as non-chordal as possible and
investigate non-distinguishability in more detail.

In [22], we built an explicit POVM to distinguish chordal graphs using an
elimination ordering. This suggests that perhaps the “least chordal” graphs
will be those with no simplicial vertices. This includes cycles. Any vector
representation of a cyclic graph $C_{n}$ must have dimension at least $(n-2)$.
Our first result in this section relates minimum-rank representations and the
distinguishability of the cycle’s edges. Note that $(n-2)$ is the minimum
vector rank of the graph $C_{n}$, meaning that the Hilbert space dimension is
as small as possible for an orthogonal representation of $G$.

######  Lemma 2.

Let $G=C_{n}$ be a cyclic graph with $n\geq 4$, and let
$\mathcal{S}=\\{|\phi_{i}\rangle\\}_{i=1}^{n}\subset{\mathcal{H}}$ be an
orthogonal representation of $G$ with $\dim{\mathcal{H}}=n-2$.

If $\\{A_{k}\\}$ corresponds to the collection of edges of $G$, then
$\\{A_{k}\\}$ is not a distinguishability set and, hence, the Gram matrix $M$
cannot be decomposed as a sum of matrices $\\{M_{k}\\}$ with support on
$\\{A_{k}\\}$.

###### Proof.

We first note that every induced subgraph of $C_{n}$ with $(n-1)$ vertices is
the path $P_{n-1}$, and any orthogonal representation of $P_{n-1}$ has the
property that any $(n-2)$ of the states are linearly independent. This follows
from Corollary 3.9 of [15], which states that any $|T|-1$ vertices in a tree
$T$ form an OS-set, which implies that the corresponding vertex states must be
linearly independent. (It was also stated in [1] that any one vertex in a tree
forms a positive semidefinite zero-forcing set, implying that the complement
must form an OS-set.)

For completeness, we include a proof that vectors representing any $(|T|-1)$
vertices of a tree $T$ must be linearly independent. Suppose we have a minimal
linear dependence among the $\\{\phi(v)\\}$, $\sum_{i}k_{i}\phi(v_{i})=0$, and
let $H$ be the subgraph of the tree induced by the $v_{i}$ for which the
corresponding $k_{i}$ is nonzero. Since the states from different connected
components of $H$ would be mutually orthogonal to one another, $H$ must be
connected by minimality. Now let $u$ be a vertex adjacent to $H$ but not in
$H$. Then there is a unique $w$ in $H$ adjacent to $u$. So let $\mathcal{V}$
be the orthogonal complement of $\phi(u)$. Then $\phi(w)$ is not in
$\mathcal{V}$ but $\phi(v_{i})$ is in $\mathcal{V}$ for all the other vertex
states $v_{i}$ in $H$, which means $\phi(w)$ cannot be part of the linear
dependence, a contradiction.

Returning to our cycle $C_{n}$: Suppose $A_{1}=\\{v_{1},v_{2}\\}$ corresponds
to the edge $(v_{1},v_{2})$. By the above argument, the $(n-2)$ states
corresponding to the remaining vertices are linearly independent and hence
span ${\mathcal{H}}$. If a POVM could distinguish $A_{1}$, then
$E_{1}|\phi_{i}\rangle=0$ for all $i>2$. Since these states span
${\mathcal{H}}$, this implies that $E_{1}=0$. The same applies to every
operator that makes up the POVM, and so no such POVM exists. Hence the edge
sets are not distinguishable.

The fact the $M$ cannot be decomposed follows from Theorem 1. ∎

This suggests a generalization. To make it easier to state, we set the
following definitions.

######  Definition 5.

For a graph $G$, let

$\mathcal{S}_{G}^{+}:=\\{M\in\mathcal{S}_{G}:M\geq 0,\,\,\Delta(M)\mbox{ is
invertible}\\},$

where $\Delta$ maps the matrix $M$ to its diagonal, and define

$\eta_{+}(G):=\min\\{{\rm rk}(M):M\in\mathcal{S}_{G}^{+}\\}.$

In other words, if $n=|G|$, $\mathcal{S}_{G}^{+}$ is the set of $n\times n$
positive semidefinite matrices in $\mathcal{S}_{G}$ whose support is all of
$[n]$. Every element of $\mathcal{S}_{G}^{+}$ can be written as $X^{*}X$,
where the columns of $X$ define an orthogonal representation of a subgraph of
$G$ that includes all the vertices of $G$.

Because $\mathcal{S}_{G}^{+}$ no longer contains the zero matrix, we can
consider the minimum rank $\eta_{+}(G)$ as a possibly meaningful graph
parameter. Our minimum rank parameter is similar to the Haemers number of the
graph $G$[16], originally introduced as an upper bound of the Shannon capacity
$\Theta(G)$ and equivalent to the minimum rank over matrices in
$\mathcal{S}_{G}$ with no zeroes on the diagonal. Following the notation of
[17], the Haemers number of $G$ is written $\eta(G)$, so here we adopt the
notation $\eta_{+}(G)$ as the minimum rank when restricted to positive
semidefinite matrices.

This allows us to state our results in more graph theoretical terms. Recall
that $\alpha(G)$ is the size of the largest independent set in $G$; that is,
subsets of vertices of $G$ such that no two of which are connected by edges of
$G$ (so independent sets in $G$ form cliques in the complement of $G$). If $G$
has an independent set of size $\alpha=\alpha(G)$, then every
$M\in{\mathcal{S}}_{G}^{+}$ can be written with an $\alpha\times\alpha$
diagonal matrix as its upper left block, perhaps after relabelling the
vertices, which implies that ${\rm rk}(M)\geq\alpha$. On the flip side, every
legal coloring of $\overline{G}$ of size $k$ corresponds to a rank $k$ element
of ${\mathcal{S}}_{G}^{+}$ (an explicit construction is given in [16]); so the
graph coloring (chromatic) number $\chi(\overline{G})$ is an upper bound for
$\eta_{+}(G)$.

This gives the following lemma, where the first inequality follows from the
definition of $\Theta(G)$, the second is a result from [16], the third is
trivial, and the fourth follows from the discussion above.

######  Lemma 3.

For any graph $G$,

$\alpha(G)\leq\Theta(G)\leq\eta(G)\leq\eta_{+}(G)\leq\chi(\overline{G}).$

We use this notation in the following. Note that Lemma 2 addresses this
situation in the case that $G$ is a cycle.

######  Theorem 3.

Let $\mathcal{S}$ be a collection of orthonormal product states in
${\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$, with associated graphs $G_{A}$
and $G_{B}$, and suppose that $G=\overline{G_{B}}$ has no simplicial vertices.

If $\dim{\mathcal{H}}_{A}=\eta_{+}(G)$, then the product states of
$\mathcal{S}$ cannot be distinguished via one-way LOCC with Alice going first.

###### Proof.

We prove by contradiction. Suppose there exists a POVM with operator elements
$\\{a_{k}|\varphi_{k}\rangle\\!\langle\varphi_{k}|\\}_{k}$ operating on
Alice’s states $\\{|\psi_{j}^{A}\rangle\\}_{j}$ that forms the first step in a
one-way LOCC protocol to distinguish the states of $\mathcal{S}$. (The
operators can be assumed to be rank one without loss of generality.) We
construct a new graph $G^{\prime}$ by adding an additional vertex $w_{1}$ to
$G$ corresponding to $|\varphi_{1}\rangle$, with $w_{1}\sim v_{j}$ if and only
if $\langle\varphi_{1}|\psi_{j}^{A}\rangle\neq 0$. Because
$G_{B}=\overline{G}\geq G_{A}$, it follows that $w_{1}$ must be a simplicial
vertex in order to initiate a one-way LOCC discrimination; i.e., Bob must be
able to distinguish the states corresponding to the neighbor vertices of
$w_{1}$, as Alice gains no information on them.

Since no vertex in $G$ is simplicial, every vertex has a neighbor outside the
clique neighborhood of $w_{1}$, and hence each state has a component in the
orthogonal complement of $|\varphi_{1}\rangle$. We can perform an orthogonal
vertex removal of $w_{1}$ [15] by projecting onto the orthogonal complement of
$|\varphi_{1}\rangle$, getting a nonzero output for each
$|\psi_{j}^{A}\rangle$. This creates a new set of Alice states
$\\{|\phi_{j}^{A}\rangle\\}$ such that
$\langle\phi_{i}^{A}|\phi_{j}^{A}\rangle=\langle\psi_{i}^{A}|\psi_{j}^{A}\rangle$
unless both $v_{i}$ and $v_{j}$ are neighbors of $w_{1}$ and thus neighbors of
each other. This means that for any vertices in $G$ such that $v_{i}\not\sim
v_{j}$,
$\langle\phi_{i}^{A}|\phi_{j}^{A}\rangle=\langle\psi_{i}^{A}|\psi_{j}^{A}\rangle=0$.

We can now define the new Alice Gram matrix $M^{\prime}$ whose $(i,j)$ entry
is $\langle\phi_{i}^{A}|\phi_{j}^{A}\rangle$. It is clear that
$M^{\prime}\in{\mathcal{S}}_{G}^{+}$ and that ${\rm
rk}(M^{\prime})<\dim{\mathcal{H}}_{A}$. This contradicts our assumption that
${\rm rk}(M)$ was minimal and thus proves the result. ∎

Note that we never used the entire POVM, just the fact that there exists an
operator that selects one clique with the property that none of its vertices
are simplicial. If we extend this reasoning to the entire POVM, we see that a
minimum rank representation cannot be distinguished with one-way LOCC with
Alice going first unless $G$ contains a set of $\eta_{+}(G)$ simplicial
vertices that are pairwise non-adjacent. We use this idea and the fact that
$\eta_{+}(G_{A})\leq\eta_{+}(\overline{G_{B}})\leq\chi(G_{B})$ in the
following theorem, which is our main result in this section.

######  Theorem 4.

Let $\mathcal{S}$ be a collection of orthonormal product states in
${\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$, with associated graphs $G_{A}$
and $G_{B}$, such that $\dim{\mathcal{H}}_{A}=\chi(G_{B})$.

If the elements of $\mathcal{S}$ are distinguishable via one-way LOCC with
Alice going first, then:

  1. (1)

Alice’s measurement must consist of projections onto an orthogonal basis of
${\mathcal{H}}_{A}$.

  2. (2)

$\alpha(\overline{G_{B}})=\chi(G_{B})\leq\alpha(G_{A})$, and $G_{B}$ is a
weakly perfect graph.

  3. (3)

Alice’s measurement is unique.

  4. (4)

There exists a chordal graph $G$ with $G_{A}\leq G\leq\overline{G_{B}}$.

  5. (5)

Every set of product states represented by the graphs $G_{A}$ and $G_{B}$ is
distinguishable via one-way LOCC with Alice going first.

###### Proof.

Let $\\{a_{k}|\varphi_{k}\rangle\\!\langle\varphi_{k}|\\}_{k}$ be a POVM on
Alice’s system that is the first step in a one-way LOCC protocol to
distinguish the elements of $\mathcal{S}$. Let $d=\dim{\mathcal{H}}_{A}$ and
order the operators so that the first $d$ states in the list
$\\{|\varphi_{k}\rangle\\}_{k=1}^{d}$ form a basis for ${\mathcal{H}}_{A}$.

Let $V=\\{1,2,\ldots n\\}$ label the set of vertices of $G_{A}$. For each
$k\leq d$, the set of vertices
$V_{k}:=\\{i:\langle\varphi_{k}|\psi_{i}^{A}\rangle\neq 0\\}$ corresponds to
an independent set in $G_{B}$. Otherwise Bob would not be able to complete the
measurement given outcome $k$. Since $\\{|\varphi_{k}\rangle\\}_{k=1}^{d}$
spans ${\mathcal{H}}_{A}$, $\bigcup_{k=1}^{d}V_{k}=V$. These two facts imply
that the map $c(i):=\min\\{k:i\in V_{k}\\}$ is a legal coloring of $G_{B}$ of
size at most $d$.

Since $d=\chi(G_{B})$, $c$ is a minimal coloring and for any $k$,
$\bigcup_{j\neq k}V_{j}\neq V$. Hence, each $V_{k}$ contains a vertex that is
unique to $V_{k}$. Let us label Alice’s states so that for each $k\leq d$,
$|\psi_{k}^{A}\rangle$ corresponds to this vertex. Then for each $k$,
$|\psi_{k}^{A}\rangle$ is the unique state in the orthogonal complement of
$\\{|\varphi_{j}\rangle:j\leq d,j\neq k\\}$. We can use this fact to show that
Alice’s POVM is in fact a projection onto an orthonormal basis.

Suppose Alice’s POVM contains more than $d$ operators, and choose some
$|\varphi_{m}\rangle$ for $m>d$. We can write this in terms of our previous
basis:

$|\varphi_{m}\rangle=\sum_{k=1}^{d}\beta_{k}|\varphi_{k}\rangle.$

For any $k$ with $\beta_{k}\neq 0$, the set of states
$\\{|\varphi_{j}\rangle:j=m\mbox{ or }j\leq d,j\neq k\\}$ forms a basis of
${\mathcal{H}}_{A}$. By repeating the argument above, we can find a vertex
associated with $|\varphi_{m}\rangle$ so that $|\psi_{m}^{A}\rangle$ is the
unique state in the orthogonal complement of $\\{|\varphi_{j}\rangle:j\leq
d,j\neq k\\}$, which means that $|\langle\psi_{m}^{A}|\psi_{k}^{A}\rangle|=1$.

Since $\\{|\psi_{j}^{A}\rangle\\}_{j=1}^{d}$ is linearly independent, there
can only be one $k$ with $|\langle\psi_{m}^{A}|\psi_{k}^{A}\rangle|=1$, which
implies that there is only one nonzero $\beta_{k}$. Thus
$|\varphi_{m}\rangle\\!\langle\varphi_{m}|=|\varphi_{k}\rangle\\!\langle\varphi_{k}|$,
and the inclusion of $|\varphi_{m}\rangle\\!\langle\varphi_{m}|$ in the POVM
is redundant. This implies that Alice’s POVM contains exactly $d$ rank one
operators that add to the identity, which implies that they must be mutually
orthogonal.

Finally, we see that for each $k$,
$|\langle\varphi_{j}|\psi_{k}^{A}\rangle|=\delta_{jk}$, which implies that the
set $\\{|\psi_{k}^{A}\rangle\\}_{k=1}^{d}$ is mutually orthogonal and
corresponds to an independent set of size $d$ in $G_{A}$, hence
$\alpha(G_{A})\geq d$, and by construction it corresponds to an independent
set in $G_{B}$. Hence, $d\leq\alpha(\overline{G_{B}})\leq\chi(G_{B})=d$,
implying equality. The equality of the chromatic number and the clique number
of $G_{B}$ is the definition of a _weakly perfect graph_ in the literature.

To show that Alice’s measurement is unique: For each $k$, we can look at the
set of vertices $\\{i:i\notin\bigcup_{j\neq k}V_{j}\\}$, which must form a
clique in $G_{A}$. Since we have a set of $d$ mutually non-adjacent cliques,
it must be that there is a unique state associated with each clique and that
Alice’s measurement must project onto it.

Finally, we see that for any two neighbors in $G_{A}$, $v_{i}\sim v_{j}$
implies that $\langle\psi_{i}^{A}|\psi_{j}^{A}\rangle\neq 0$ and hence there
exists at least one $k$ such that
$\langle\psi_{i}^{A}|\varphi_{k}\rangle\langle\varphi_{k}|\psi_{j}^{A}\rangle\neq
0$, which implies that if $v_{i}\sim v_{j}$, there exists $k$ with $i,j\in
V_{k}$. Thus, if we let $G$ be the union of the complete graphs on the
$V_{k}$, then $G$ is a chordal graph with $G_{A}\leq G\leq\overline{G_{B}}$.
By Theorem 2, any representation of $G_{A}$ and $G_{B}$ must be
distinguishable with one-way LOCC. ∎

The theorem gives several conditions that are easy to identify and which
preclude one-way LOCC discrimination. In particular, the following is an
immediate consequence of conclusion (2) in the theorem.

######  Corollary 5.

Let $\mathcal{S}$ be a collection of orthonormal product states in
${\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$, with associated graphs $G_{A}$
and $G_{B}$, such that $\dim{\mathcal{H}}_{A}=\chi(G_{B})$.

If $\alpha(\overline{G_{B}})$ is strictly less than $\chi(G_{B})$, then the
states cannot be distinguished via one-way LOCC with Alice going first.

A second corollary gives us a biconditional that follows from combining
conclusion (4) in Theorem 4 with Theorem 2.

######  Corollary 6.

Let $\mathcal{S}$ be a collection of orthonormal product states in
${\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$, with associated graphs $G_{A}$
and $G_{B}$, such that $\dim{\mathcal{H}}_{A}=\chi(G_{B})$.

The elements of $\mathcal{S}$ are distinguishable via one-way LOCC with Alice
going first if and only if there exists a chordal graph $G$ with $G_{A}\leq
G\leq\overline{G_{B}}$.

###  4.1. Examples

We present a number of examples motivated by the results of this section, with
particular attention paid to the seminal work [4].

######  Example 5.

Recall that Example 2 gives a 4-cycle representation in dimension 2 for which
$G_{A}=\overline{G_{B}}$ is not chordal, and, in that case, we have
$\dim{\mathcal{H}}_{A}=\chi(\overline{G_{B}})=2$ and the states are
indistinguishable by Corollary 6. A more interesting graph-theoretical example
is the nonlocality without entanglement states from Bennett, et al. [4]. For
this well-known example of 9 states in
${\mathbb{C}}^{3}\otimes{\mathbb{C}}^{3}$, one can check that the graphs
satisfy $G=G_{A}=\overline{G_{B}}$, where $G$ is the graph below with vertex
states labeled corresponding to [4]:

$3$$9$$7$$5$$2$$8$$6$$4$$1$

This graph clearly has $\alpha(G)=3$, which is also the dimension of Alice’s
system, so $\eta_{+}(G)=3$ by Lemma 3. Since it has no simplicial vertices, we
can apply Theorem 3 and see immediately that it is not possible to distinguish
this basis of ${\mathbb{C}}^{3}\otimes{\mathbb{C}}^{3}$ with one-way LOCC. (We
note the result in [4] is stronger, that it is impossible to distinguish the
states with full LOCC operations.)

######  Example 6.

Looking at subsets of these states can only make the distinguishability
problem easier, and it is shown in [4] that removing any vertex (except “9”)
from the states in Example 5 results in coresponding states that are
distinguishable with general LOCC measurements. Our argument shows that one-
way LOCC is not sufficient to distinguish them. In fact, there exist subsets
of 5 of these states that are also not distinguishable with one-way LOCC. Two
such sets are given by the states that correspond to the graphs below, with
$G_{A}=\overline{G_{B}}$ given for both.

$9$$2$$8$$6$$4$

$9$$7$$2$$8$$6$

It is immediate in both cases that $\chi(G_{B})=3$. This, together with the
fact that $\dim{\mathcal{H}}_{A}=3$ and that neither of these graphs is
chordal, allows us to apply Corollary 6 and immediately conclude that neither
of these sets can be distinguished with one-way LOCC. (On the other hand, in
each case $G_{B}$ is chordal, so the states _can_ be distinguished if we alter
our convention and allow Bob to measure first.)

######  Example 7.

The size of our set in Example 6 is potentially significant, as 5 is the
minimum size of an unextendible product basis in
${\mathbb{C}}^{3}\otimes{\mathbb{C}}^{3}$, and no unextendible product basis
can be distinguished with separable measurements, which includes one-way LOCC.

Following shortly on the work in [4], there was work providing fundamental
examples of unextendible product bases. The authors in [5, 10] built examples
of unextendible product bases and demonstrated the usefulness of representing
product states with graphs. Their Tiles is a set of 5 states in
${\mathbb{C}}^{3}\otimes{\mathbb{C}}^{3}$ corresponding to the states
$\\{2,4,6,8\\}$ in Example 6 plus a stopper state that is adjacent to $2$ and
$4$. The corresponding graph is a $5$-cycle, which cannot be distinguished
with one-way LOCC by applying Corollary 5 and the logic in Lemma 2.
Unextendible product bases are not distinguishable with separable operations,
so these LOCC results are not new, but they show how the various results may
be applied in interesting cases.

######  Example 8.

The following is a generalization of Example 5, representing a set of $4d-3$
product states in $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$. For $d\geq 3$,
consider the graph $B_{d}$ represented below. Each circle represents a
complete graph or its complement, and heavy lines indicate that every vertex
inside one circle is adjacent to every vertex inside the other. Example 5 is
the case $d=3$.

$K_{d-1}$$K_{d-1}$$\overline{K_{d-1}}$$\overline{K_{d-1}}$

In general, this graph can be realized with the following states: Let $F$ be
the $(d-1)\times(d-1)$ Fourier matrix and define $\tilde{F}=F\oplus 1$ to be
the extension of $F$ to a $d$-dimensional space. Finally, let $X$ be a cyclic
permutation on the standard basis in dimension $d$:
$X=\sum_{k=0}^{d-1}|k+1\rangle\\!\langle k|\mod{d}$. Then we can define the
following states, where $k$ ranges from $0$ to $(d-2)$:

$\displaystyle|\psi_{1,k}\rangle$
$\displaystyle=\tilde{F}|0\rangle\otimes|k\rangle$
$\displaystyle\quad|\psi_{3,k}\rangle$
$\displaystyle=X\tilde{F}|k\rangle\otimes\tilde{F}|0\rangle$
$\displaystyle|\psi_{2,k}\rangle$ $\displaystyle=|k\rangle\otimes|d-1\rangle$
$\displaystyle\quad|\psi_{4,k}\rangle$ $\displaystyle=|d-1\rangle\otimes
X\tilde{F}|k\rangle$ $\displaystyle|\psi_{0}\rangle$
$\displaystyle=\tilde{F}|1\rangle\otimes\tilde{F}|1\rangle.$

It is straightforward to show that $\overline{B_{d}}$ is graph isomorphic to
$B_{d}$ and that $\alpha(B_{d})=\eta_{+}(B_{d})=\chi(\overline{B_{d}})=d$.
This implies that our representation of $B_{d}$ in dimension $d$ is the
smallest possible. Suppose Alice and Bob are working with a two-qudit system
with a product state graph representation $G_{A}=G_{B}=B_{d}$. Since $B_{d}$
contains no simplicial vertices, Theorem 4 implies that one-way LOCC
discrimination is not possible if Alice goes first; and the fact that the
graph is self-complementary implies that it is not possible if Bob goes first,
either.

It is also true that any subgraph of $B_{d}$ that has $\alpha=d$ will continue
to be indistinguishable with Alice going first, corresponding to this graph,
with ${a,b,c}\in[1,d-1]$:

$K_{a}$$K_{c}$$\overline{K_{d-1}}$$\overline{K_{b}}$

Finally, for odd values of $d$, we can extend the original set to a complete
basis of $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ by defining $G_{1}$ to be a
single point $K_{1}$ and then recursively letting $G_{d}$ be given by:

$K_{d-1}$$K_{d-1}$$\overline{K_{d-1}}$$\overline{K_{d-1}}$$G_{d}=$$G_{d-2}$

This is still self-complementary with minimum rank $d$ and $\alpha(G_{d})=d$,
so our theorems apply.

We can also represent these states using a domino diagram, as in, e.g., [4,
8]. The diagram below is for $d=5$, and gives motivation for calling this a
Bullseye Basis. The numbers show how many states correspond to each rectangle:

$4$$2$$4$$2$$4$$2$$2$$4$$1$

######  Example 9.

One simple example for which $G_{A}\lneq\overline{G_{B}}$ has $G_{B}=C_{5}$, a
5-cycle, while $G_{A}=P_{3}+P_{2}$, the union of an edge and a path of length
2. One can see that $G_{A}\leq\overline{G_{B}}$ and $\chi(G_{B})=3$.

The representations of these graphs in
${\mathbb{C}}^{3}\otimes{\mathbb{C}}^{3}$ is fairly prescribed, for instance
by the following 5 states:

$\displaystyle|\psi_{1}\rangle$ $\displaystyle=|0\rangle\otimes|0\rangle$
$\displaystyle\quad|\psi_{2}\rangle$
$\displaystyle=(|0\rangle+|1\rangle)\otimes|2\rangle$
$\displaystyle|\psi_{3}\rangle$
$\displaystyle=|1\rangle\otimes(|0\rangle+|1\rangle)$
$\displaystyle\quad|\psi_{4}\rangle$
$\displaystyle=|2\rangle\otimes(|0\rangle-|1\rangle+|2\rangle)$
$\displaystyle\quad|\psi_{5}\rangle$
$\displaystyle=|2\rangle\otimes(|1\rangle+|2\rangle).$

Theorem 4 states that any measurement to distinguish these sets starting with
Alice must project onto an orthogonal basis, in this case the standard basis;
and Corollary 6 shows that this must be possible, since $G_{A}$ is chordal.

##  5\. Conclusions and Future Work

We have built on our work from [21], extending the ways in which the areas of
graph theory, orthogonal representations, and LOCC distinguishability can
inform and enrich each other. In particular, in Section 3 we established a
characterization of chordal graphs in terms of one-way LOCC
distinguishability, and we provided a number of applications and examples. In
Section 4, we reversed this, showing how graph parameters imply limitations on
one-way LOCC measurements and providing graph-driven examples.

Many open questions remain, including consideration of how other families of
graphs might be characterized in terms of quantum operations; and how to
algorithmically build one-way LOCC measurements from the corresponding graphs.
It is also apparent that these ideas could be extended to two-way LOCC
measurements and to sets of multipartite product states. This work is an
invitation for researchers in disparate areas of mathematics to engage with
these quantum-inspired questions.

Acknowledgements. D.W.K. was partly supported by NSERC Discovery Grant 400160.
R.P. was partly supported by NSERC Discovery Grant 400550.

## References

  * [1] Francesco Barioli, Wayne Barrett, Shaun M Fallat, Tracy H Hall, Leslie Hogben, Bryan Shader, Pauline Van Den Driessche, and Hein Van Der Holst.  Zero forcing parameters and minimum rank problems.  Linear Algebra and its Applications, 433(2):401–411, 2010.
  * [2] Francesco Barioli, Shaun M Fallat, Lon H Mitchell, and Sivaram K Narayan.  Minimum semidefinite rank of outerplanar graphs and the tree cover number.  Electronic Journal of Linear Algebra, 22(2):10–21, 2011.
  * [3] Charles H Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K Wootters.  Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels.  Physical Review Letters, 70(13):1895, 1993.
  * [4] Charles H Bennett, David P DiVincenzo, Christopher A Fuchs, Tal Mor, Eric Rains, Peter W Shor, John A Smolin, and William K Wootters.  Quantum nonlocality without entanglement.  Physical Review A, 59(2):1070, 1999.
  * [5] Charles H Bennett, David P DiVincenzo, Tal Mor, Peter W Shor, John A Smolin, and Barbara M Terhal.  Unextendible product bases and bound entanglement.  Physical Review Letters, 82(26):5385, 1999.
  * [6] Matthew Booth, Philip Hackney, Benjamin Harris, Charles R Johnson, Margaret Lay, Terry D Lenker, Lon H Mitchell, Sivaram K Narayan, Amanda Pascoe, and Brian D Sutton.  On the minimum semidefinite rank of a simple graph.  Linear and Multilinear Algebra, 59(5):483–506, 2011.
  * [7] Matthew Booth, Philip Hackney, Benjamin Harris, Charles R Johnson, Margaret Lay, Lon H Mitchell, Sivaram K Narayan, Amanda Pascoe, Kelly Steinmetz, Brian D Sutton, et al.  On the minimum rank among positive semidefinite matrices with a given graph.  SIAM Journal on Matrix Analysis and Applications, 30(2):731–740, 2008.
  * [8] Scott M Cohen.  General approach to quantum channel impossibility by local operations and classical communication.  Physical Review Letters, 118(2):020501, 2017.
  * [9] Alessandro Cosentino and Vincent Russo.  Small sets of locally indistinguishable orthogonal maximally entangled states.  Quantum Information & Computation, 14:1098–1106, 2014.
  * [10] David P DiVincenzo, Tal Mor, Peter W Shor, John A Smolin, and Barbara M Terhal.  Unextendible product bases, uncompletable product bases and bound entanglement.  Communications in Mathematical Physics, 238:379–410, 2003.
  * [11] Tilo Eggeling and Reinhard F Werner.  Hiding classical data in multipartite quantum states.  Physical Review Letters, 89(9):097905, 2002.
  * [12] Shaun Fallat and Leslie Hogben.  Variants on the minimum rank problem: A survey II.  arXiv preprint arXiv:1102.5142, 2011.
  * [13] Shaun M Fallat and Leslie Hogben.  The minimum rank of symmetric matrices described by a graph: a survey.  Linear Algebra and its Applications, 426(2-3):558–582, 2007.
  * [14] Heng Fan.  Distinguishability and indistinguishability by local operations and classical communication.  Physical Review Letters, 92(17):177905, 2004.
  * [15] Philip Hackney, Benjamin Harris, Margaret Lay, Lon H Mitchell, Sivaram K Narayan, and Amanda Pascoe.  Linearly independent vertices and minimum semidefinite rank.  Linear Algebra and its Applications, 431(8):1105–1115, 2009.
  * [16] Willem Haemers et al.  An upper bound for the Shannon capacity of a graph.  In Colloq. Math. Soc. János Bolyai, volume 25, pages 267–272. Hungary, 1978.
  * [17] Leslie Hogben, editor.  Handbook of linear algebra, chapter 46.  CRC press, 2nd edition, 2013.
  * [18] David W Kribs, Comfort Mintah, Michael Nathanson, and Rajesh Pereira.  Operator structures and quantum one-way LOCC conditions.  Journal of Mathematical Physics, 58(9):092201, 2017.
  * [19] David W Kribs, Comfort Mintah, Michael Nathanson, and Rajesh Pereira.  Quantum error correction and one-way LOCC state distinguishability.  Journal of Mathematical Physics, 60(3):032202, 2019.
  * [20] David W Kribs, Comfort Mintah, Michael Nathanson, and Rajesh Pereira.  One-way LOCC indistinguishable lattice states via operator structures.  Quantum Information Processing, 19:1–8, 2020.
  * [21] David W Kribs, Comfort Mintah, Michael Nathanson, and Rajesh Pereira.  Vector representations of graphs and distinguishing quantum product states with one-way LOCC.  Linear Algebra and its Applications, 602:223–239, 2020.
  * [22] David W Kribs, Comfort Mintah, Michael Nathanson, and Rajesh Pereira.  Operator and graph theoretic techniques for distinguishing quantum states via one-way LOCC.  Applied Sciences, 11(20):9542, 2021.
  * [23] László Lovász, Michael Saks, and Alexander Schrijver.  Orthogonal representations and connectivity of graphs.  Linear Algebra and its Applications, 114:439–454, 1989.
  * [24] László Lovász, Michael Saks, and Alexander Schrijver.  A correction: orthogonal representations and connectivity of graphs.  Linear Algebra and its Applications, 313(1-3):101–105, 2000.
  * [25] Michael Nathanson.  Distinguishing bipartitite orthogonal states using LOCC: Best and worst cases.  Journal of Mathematical Physics, 46(6):062103, 2005.
  * [26] Michael Nathanson.  Three maximally entangled states can require two-way local operations and classical communication for local discrimination.  Physical Review A, 88(6):062316, 2013.
  * [27] Vern I Paulsen, Stephen C Power, and Roger R Smith.  Schur products and matrix completions.  Journal of Functional Analysis, 85(1):151–178, 1989.
  * [28] Donald J Rose.  Triangulated graphs and the elimination process.  Journal of Mathematical Analysis and Applications, 32(3):597–609, 1970.
  * [29] Barbara M Terhal, David P DiVincenzo, and Debbie W Leung.  Hiding bits in Bell states.  Physical Review Letters, 86(25):5807, 2001.
  * [30] Jonathan Walgate, Anthony J Short, Lucien Hardy, and Vlatko Vedral.  Local distinguishability of multipartite orthogonal quantum states.  Physical Review Letters, 85(23):4972, 2000.
  * [31] Nengkun Yu, Runyao Duan, and Mingsheng Ying.  Four locally indistinguishable ququad-ququad orthogonal maximally entangled states.  Physical Review Letters, 109(2):020506, 2012.