# Vector Representations of Graphs and Distinguishing Quantum Product States
with One-Way LOCC

David W. Kribs1,2, Comfort Mintah1, Michael Nathanson3, Rajesh Pereira1
1Department of Mathematics & Statistics, University of Guelph, Guelph, ON,
Canada N1G 2W1  2Institute for Quantum Computing and Department of Physics &
Astronomy, University of Waterloo, Waterloo, ON, Canada N2L 3G1  3Department
of Mathematics and Computer Science, Saint Mary’s College of California,
Moraga, CA, USA 94556

###### Abstract.

Distinguishing sets of quantum states shared by two parties using only local
operations and classical communication measurements is a fundamental topic in
quantum communication and quantum information theory. We introduce a graph-
theoretic approach, based on the theory of vector representations of graphs,
to the core problem of distinguishing product states with one-way LOCC. We
establish a number of results that show how distinguishing such states can be
framed in terms of properties of the underlying graphs associated with a set
of vector product states. We also present a number of illustrative examples.

###### Key words and phrases:

quantum communication, quantum states, product states, local operations and
classical communication, simple graph, graph clique cover, chordal graph,
domino states.

###### 2010 Mathematics Subject Classification:

47L90, 46B28, 81P15, 81P45, 81R15

##  1\. Introduction

In quantum information theory, we frequently attempt to recover classical
information that has been encoded into quantum states. If our quantum system
consists of multiple physical subsystems, we encounter instances where the
information can be recovered with joint measurements on the subsystems but not
with local measurements [7, 18, 20, 10]. This paradigm makes use of local
quantum operations and classical communication (LOCC) and includes many topics
such as quantum teleportation and data hiding [6, 29, 14]. There is also a
growing body of work on the more restricted problem of one-way LOCC, in which
parties must perform their measurements in a prescribed order [30, 26, 17, 27,
12, 31, 21, 23, 22].

The corresponding linear algebra problem involves attempting to identify an
unknown vector $|\psi\rangle$ from an orthonormal set of vectors
$\\{|\psi_{k}\rangle\\}$ in a composite (tensor product) Hilbert space
${\mathcal{H}}={\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$. In the current
discussion, we assume that ${\mathcal{H}}_{A}$ and ${\mathcal{H}}_{B}$ are
finite-dimensional complex inner product spaces; and the initial measurement
is a set of rank one operators that sum to the identity operator on
${\mathcal{H}}_{A}$. The exploration of connections with linear algebra goes
back to the origins of quantum information theory, and all of the citations
above can be seen in this light. Our recent work to relate one-way LOCC to
operator systems and algebras [21, 23, 22] is a continuation of this
exploration.

One of the most unexpected phenomena in quantum information is that of
“nonlocality without entanglement,” originally identified by Bennett et al.
[7]. It says that a set of states $\\{|\psi_{k}\rangle\\}$ in
${\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$ can fail to be locally
distinguishable even if each of them is a product state, i.e. for each $k$, we
have
$|\psi_{k}\rangle=|\psi_{k}^{A}\rangle\otimes|\psi_{k}^{B}\rangle\in{\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$.
This implies that quantum entanglement is not the only way to take advantage
of the peculiarities of quantum information. For any set of product states, we
can ask whether it exhibits this phenomenon. The local relationships between
product states are modeled using the confusability graph (as identified in
[13]), which arises in the study of vector representations of graphs [24, 25,
16, 9, 15, 3, 8, 4].

In this paper, we apply graph-theoretic techniques, including those associated
with vector representations of graphs, to the study of LOCC quantum state
distinguishability. We specifically focus on the core problem of one-way LOCC
distinguishability of product states, identifying and clarifying new structure
for the distinguishability of such sets of states based on associated vector
graph representations.

The paper is organized as follows. In the next section we present requisite
preliminaries from graph theory, along with the vector representations of
graphs that arise from sets of quantum product states and an illustrative one-
way LOCC example. We then initiate our analysis in Section 3, establishing
that one-way distinguishability is equivalent to the existence of a graph
clique cover with nice properties. Building on this result, in Section 4 we
show that under certain conditions if a set of product states can be
distinguished by one way LOCC with either party going first then it can be
distinguished with product measurements. We also provide an example to show
that this is false in general. In Section 5 we consider one-way LOCC
implications when the underlying graphs have extra properties as identified in
graph theory; in particular, chordal or tree structures. The final section
includes an extended analysis for the important special case of domino states
[7, 11, 32, 33]. Examples are included throughout our presentation, as are
discussions on the differences encountered when different parties go first in
a one-way LOCC protocol.

##  2\. Alice and Bob, and Vector Representations of Graphs

We begin by recalling basic notation and nomenclature from graph theory,
drawing on various entrance points into the literature on the subject [24, 25,
16, 9, 15, 3, 8, 4].

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}\\}$.

Some fundamental graphs for fixed $n\geq 1$ include: the path graph
$P_{n}=(\\{v_{1},\dots,v_{n}\\},E)$ such that $E=\\{\\{v_{i},v_{i+1}\\}:1\leq
i\leq n-1\\}$; the cycle graph $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}\\}$; and the
complete graph on $n$-vertices, $K_{n}=(\\{v_{1},\dots,v_{n}\\},E)$ such that
$E=\\{\\{v,w\\}:v\neq w\in V\\}$.

######  Definition 1.

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$,

(1) $\displaystyle v_{i}\not\sim
v_{j}\iff\langle\phi(v_{i}),\phi(v_{j})\rangle=0.$

The minimum vector rank of $G$, denoted ${\rm mvr}(G)$, is the smallest $d$
such that $G$ has an orthogonal representation in $\mathbb{C}^{d}$.

Orthogonal representations were discussed in, e.g., [16, 24]. The requirement
that $\phi(v)\neq 0$ distinguishes the minimum vector rank from the minimum
semidefinite rank of the graph [9, 8]. If every vertex of $G$ is part of at
least one edge, then these two quantities coincide, and we will be applying
the existing literature of minimum semidefinite rank to prove our results.
Note that these quantities are defined with respect to the underlying field
${\mathbb{C}}$, and there are examples where the minimum rank increases if we
restrict ourselves to real vectors. Note also the biconditional built into the
definition, which is stronger than conditions for graph colouring. This allows
us to uniquely define the graph associated with a function $\phi$.

We can now introduce a graph perspective to the setting of LOCC through
orthogonal representations. In the LOCC state distinguishability context, we
typically have two parties, called Alice and Bob, each with a Hilbert space
$\mathcal{H}_{A}$, $\mathcal{H}_{B}$, and a set of states in
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ that they wish to distinguish only
using local (quantum) measurement operations on their respective systems and
classical communication between them. Here we will focus on the important case
of one-way LOCC, where Alice and Bob measure in a prescribed order, with one
party communicating the results of their measurement to the other, allowing
for the second party to complete the measurement based on that result. We also
consider the situation in which the states are all product states; that is,
states of the form $|\psi^{A}_{k}\rangle\otimes|\psi^{B}_{k}\rangle$.
Measurements will thus be given for Alice by the (rank-one) projections onto
the states $\\{|\psi^{A}_{k}\rangle\\}_{k}$, with measurement outcomes
corresponding to these states, and similarly for Bob and the states
$\\{|\psi^{B}_{k}\rangle\\}_{k}$. (Such measurements are rank-one versions of
von Neumann positive operator valued measures, or POVM’s.)

######  Definition 2.

Suppose we are given a set of product states
$\\{|\psi^{A}_{k}\rangle\otimes|\psi^{B}_{k}\rangle\\}_{k=1}^{r}$ 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}$.

Consider the following illustrative example, which we also analyze from the
one-way LOCC perspective as a prelude to what follows. We will always use the
standard notation $\\{|0\rangle,|1\rangle,\ldots,|d-1\rangle\\}$ for a fixed
orthonormal basis of ${\mathbb{C}}^{d}$.

######  Example 1.

Consider the following set of five (unnormalized) states in
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}={\mathbb{C}}^{4}\otimes{\mathbb{C}}^{3}:$

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

Looking at the set of Alice’s vectors, we can see it as an orthogonal
representation of the graph $G_{A}=P_{5}$ in ${\mathbb{C}}^{4}$; with
$|\psi_{1}^{A}\rangle=|0\rangle$, $|\psi_{2}^{A}\rangle=|0\rangle+|1\rangle$,
$|\psi_{3}^{A}\rangle=|1\rangle+|2\rangle$,
$|\psi_{4}^{A}\rangle=|2\rangle+|3\rangle$, $|\psi_{5}^{A}\rangle=|3\rangle$.
The set of Bob’s vectors is an orthogonal representation of the ‘house’ graph
$G_{B}=\overline{P}_{5}$ in ${\mathbb{C}}^{3}$ depicted in Figure 1.

$|\psi_{1}^{B}\rangle$$|\psi_{2}^{B}\rangle$$|\psi_{3}^{B}\rangle$$|\psi_{4}^{B}\rangle$$|\psi_{5}^{B}\rangle$
Figure 1. Complement of $P_{5}$, represented in $\mathbb{C}^{3}$ in Example 1.

Notice that these states can be distinguished with one-way LOCC with Alice
going first: If Alice measures in the standard basis given by
$\\{|0\rangle,|1\rangle,|2\rangle,|3\rangle\\}$, then for each of her possible
outcomes from this set, there are only two remaining possibilities; and these
are orthogonal from Bob’s perspective. In general, in order to distinguish our
states with one-way LOCC, every measurement outcome of Alice’s needs to
eliminate possibilities so that the remaining possible states are mutually
orthogonal on Bob’s side. For instance, in this example if Alice gets a
measurement outcome of $|0\rangle$, Bob is left to distinguish between the
vectors $\\{|0\rangle+|2\rangle,|1\rangle\\}$, which are mutually orthogonal.

Note that this analysis does not tell us whether we can distinguish with Bob
measuring first. We will discover in the next section that this is not
possible.

##  3\. Graph Clique Covers and One-Way LOCC

We will now attempt to categorize the one-way LOCC distinguishability of
states in terms of their corresponding graphs. We begin with the notion of a
clique cover.

######  Definition 3.

Given a graph $G=(V,E)$. A set of graphs $\\{G_{i}=(V_{i},E_{i})\\}$ covers
$G$ 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 complete graph
(clique).

The clique cover number $\mathrm{cc}(G)$ is the smallest possible number of
subgraphs contained in a clique cover of $G$.

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.

In the example of the previous section, the only clique cover of $P_{5}$ is
the set of edges; while the complement $\overline{P_{5}}$ can be clique
covered with a three-cycle and three individual edges, as seen in Figure 2.
Hence, $\mathrm{cc}(P_{5})=\mathrm{cc}(\overline{P_{5}})=4$.

$|\psi_{1}^{B}\rangle$$|\psi_{2}^{B}\rangle$$|\psi_{3}^{B}\rangle$$|\psi_{4}^{B}\rangle$$|\psi_{5}^{B}\rangle$$|\psi_{4}^{B}\rangle$$|\psi_{5}^{B}\rangle$$|\psi_{1}^{B}\rangle$$|\psi_{2}^{B}\rangle$
Figure 2. Clique cover of $\overline{P_{5}}$ with labels as represented in
Example 1.

Our first result shows that a set of product states can be perfectly
distinguished with one-way LOCC precisely when there is a clique cover with
nice properties.

######  Theorem 1.

Given a set of product states in ${\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$,
let $G_{A}$ and $G_{B}$ be the graphs of the states from Alice and Bob’s
perspectives, respectively. Let $\phi:V_{A}\rightarrow{\mathcal{H}}_{A}$ be
the association of vertices with Alice’s states and assume that the set
$\\{\phi(v):v\in V\\}$ spans ${\mathcal{H}}_{A}$.

Then the states are distinguishable with one-way LOCC with Alice measuring
first if and only if there exists

  * (1)

a graph $G$ satisfying $G_{A}\leq G\leq\overline{G_{B}}$,

  * (2)

a clique cover $\\{V_{j}\\}_{j=1}^{k}$ of $G$, and,

  * (3)

a direct sum decomposition
${\mathcal{H}}_{A}=\oplus_{j=1}^{k}{\mathcal{S}}_{j}$ with the property that
for all $v\in V_{A}$, the support of $\phi(v)$ is contained in
$\oplus_{\\{j:v\in V_{j}\\}}{\mathcal{S}}_{j}$.

###### Proof.

One direction of the proof is straightforward: suppose we have a graph $G$
with $G_{A}\leq G\leq G_{B}$, a clique cover $\\{V_{j}\\}_{j=1}^{k}$ of $G$,
and the decomposition ${\mathcal{H}}_{A}=\oplus_{j=1}^{k}{\mathcal{S}}_{j}$
along with the support assumption of (3). For each $j$ define $Q_{j}$ as the
projection of $\mathcal{H}_{A}$ onto ${\mathcal{S}}_{j}$, so $\\{Q_{j}\\}$ is
a (von Neumann) POVM on ${\mathcal{H}}_{A}$. If Alice gets the outcome $j$
from the associated measurement, then $Q_{j}\phi(v)\neq 0$, which implies that
$v\in V_{j}$. Since the vertices in $V_{j}$ form a clique in
$G\leq\overline{G_{B}}$, they form a disconnected set in $G_{B}$, reflecting
the fact that they are mutually orthogonal. Hence, Bob can distinguish them
once he knows Alice’s outcome.

The other direction of the proof requires more care. Let
$\\{Q_{j}\\}_{j=1}^{k}$ be a measurement on Alice’s system that allows Bob to
complete a perfect discrimination of their states. Then for each $Q_{j}$, we
define $V_{j}=\\{v\in V:Q_{j}|\phi(v)\rangle\neq 0\\}$. It is necessary that
the vertices in $V_{j}$ form a clique in $\overline{G}_{B}$ for Bob to be able
to distinguish the remaining possibilities. Define $G$ to be the union (both
vertices and edges) of the cliques induced by the $V_{j}$. By construction,
this is a subgraph of $\overline{G}_{B}$ and the $V_{j}$ form a clique cover
of $G$.

On the other hand, if $\langle\phi(u)|\phi(v)\rangle\neq 0$, then
$\langle\phi(u)|Q_{j}|\phi(v)\rangle\neq 0$ for some $j$, which means that $u$
and $v$ are both in $V_{j}$. Hence every edge in Alice’s graph $G_{A}$ is
contained in one of the cliques determined by some $V_{j}$. Thus we see that
$G_{A}$ is a subgraph of $G$, and we get $G_{A}\leq G\leq\overline{G}_{B}$ as
desired.

For each measurement operator $Q_{j}$, define ${\mathcal{R}}_{j}$ to be the
range of $Q_{j}$. Then we can define ${\mathcal{S}}_{1}={\mathcal{R}}_{1}$ and
for all $j>1$,

$\displaystyle{\mathcal{S}}_{j}={\mathcal{R}}_{j}\cap\left(\bigcap_{i=1}^{j-1}{\mathcal{R}}_{i}^{\perp}\right).$

By definition, this means that if $i<j$ then ${\mathcal{S}}_{j}$ is a subspace
of ${\mathcal{R}}_{i}^{\perp}$ and ${\mathcal{S}}_{i}$ is a subspace of
${\mathcal{R}}_{i}$, and so the subspaces are mutually orthogonal. Also, by
construction, each
${\mathcal{R}}_{j}\subseteq\oplus_{i=1}^{j}{\mathcal{S}}_{i}$. Hence
${\mathcal{R}}_{j}\subseteq\oplus_{i=1}^{k}{\mathcal{S}}_{i}$ for every $j$.
Since $\sum_{j}Q_{j}=I$, the linear span of the $\\{{\mathcal{R}}_{j}\\}$ is
all of ${\mathcal{H}}_{A}$, which implies that

$\displaystyle{\mathcal{H}}_{A}=\oplus_{j=1}^{k}{\mathcal{S}}_{j}.$

Finally, we see that for each vertex $v$, if $\phi(v)$ has a nontrivial
component in ${\mathcal{S}}_{j}$ then it has a component in
${\mathcal{R}}_{j}$, implying that $v\in V_{j}$. Thus, the support of
$\phi(v)$ is contained in $\oplus_{j:v\in V_{j}}{\mathcal{S}}_{j}$. ∎

######  Example 2.

Returning to our example from the previous section in light of the theorem,
the graph $G$ is the path $P_{5}$, and $G_{A}=P_{5}=\overline{G_{B}}$. The
clique cover is simply the collection of edges, with corresponding subspaces
of $\mathcal{H}_{A}$ as in the theorem given by:

$\displaystyle V_{0}=\\{v_{1},v_{2}\\}$
$\displaystyle{\mathcal{S}}_{0}=\\{\left(|1\rangle+|2\rangle\right),\left(|2\rangle+|3\rangle\right),|3\rangle\\}^{\perp}=\operatorname{span}\\{|0\rangle\\}$
$\displaystyle V_{1}=\\{v_{2},v_{3}\\}$
$\displaystyle{\mathcal{S}}_{1}=\\{|0\rangle,\left(|2\rangle+|3\rangle\right),|3\rangle\\}^{\perp}=\operatorname{span}\\{|1\rangle\\}$
$\displaystyle V_{2}=\\{v_{3},v_{4}\\}$
$\displaystyle{\mathcal{S}}_{2}=\\{|0\rangle,\left(|0\rangle+|1\rangle\right),|3\rangle\\}^{\perp}=\operatorname{span}\\{|2\rangle\\}$
$\displaystyle V_{3}=\\{v_{4},v_{5}\\}$
$\displaystyle{\mathcal{S}}_{3}=\\{|0\rangle,\left(|0\rangle+|1\rangle\right),\left(|1\rangle+|2\rangle\right)\\}^{\perp}=\operatorname{span}\\{|3\rangle\\}.$

This tells us that we should measure in the standard basis, matching our
earlier strategy. Note that if instead we have Bob measure first, we can see
right away that this is not possible. The graph corresponding to Bob’s states
is the house graph; and a minimum clique cover contains four cliques. Since we
are in ${\mathbb{C}}^{3}$, there is no clique cover of size less than or equal
to $d$ and it is not possible to meet the conditions of the theorem. In
conclusion, if we are to distinguish the states in Example 1 using one-way
LOCC, it must be with Alice measuring first.

Let us point out a consequence of the construction in the proof of the
theorem; namely, that Alice can use any measurement which respects the
decomposition ${\mathcal{H}}_{A}=\oplus_{j=1}^{k}{\mathcal{S}}_{j}$. In
particular, she can measure in an orthonormal basis for each of the
${\mathcal{S}}_{j}$.

######  Corollary 1.

If Alice and Bob have a set of product states that can be distinguished with
one-way LOCC with Alice going first, then it is possible to distinguish them
by projecting onto on orthonormal basis of the Hilbert space
${\mathcal{H}}_{A}$.

As a consequence of Theorem 1, we thus have graph-theoretical necessary
conditions for one-way LOCC with product states. As a one-way LOCC measurement
by Alice corresponds to a clique cover of a subgraph $\overline{G}_{B}$, this
creates interest in its clique cover number.

######  Corollary 2.

If a set of product states in $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ are
distinguishable with one-way LOCC with Alice measuring first, and suppose
further that $G_{A}=\overline{G_{B}}$, then

$\displaystyle\mathrm{cc}(\overline{G_{B}})\leq\dim({\mathcal{H}}_{A})$

###### Proof.

If we let $d_{A}=\dim({\mathcal{H}}_{A})$, then Theorem 1 states that if Alice
can initiate a one-way LOCC measurement, then there exists graph $G$ and a
clique cover of size $k$ that corresponds to a decomposition of
${\mathcal{H}}_{A}$. This means that $k$ is at most the dimension of the
space. Since $\mathrm{cc}(G)$ is the size of the smallest clique cover of $G$,
we have

$\displaystyle\mathrm{cc}(G)\leq k\leq\dim({\mathcal{H}}_{A}).$

Since $G_{A}=\overline{G_{B}}$ and $G_{A}\leq G\leq\overline{G_{B}}$, this
implies that

$\mathrm{cc}(\overline{G_{B}})=\mathrm{cc}(G)\leq\text{dim}\mathcal{H}_{A}$

. ∎

##  4\. Product Measurements and One-Way LOCC

We can build on Theorem 1 to derive the following important and intuitive
consequence, in the case that order of the parties does not matter in a one-
way LOCC protocol with an extra condition on the states.

######  Theorem 2.

Suppose we have a set of product states
$\\{|\psi_{i}^{A}\rangle\otimes|\psi_{i}^{B}\rangle\\}$ in
${\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}$, and let $G_{A}$ and $G_{B}$ be
the graphs for Alice and Bob, respectively. Suppose further that
$G_{A}=\overline{G_{B}}$; that is, for every $i\neq j$,

$\langle\psi_{i}^{A}|\psi_{j}^{A}\rangle=0\iff\langle\psi_{i}^{B}|\psi_{j}^{B}\rangle\neq
0.$

Then it is possible to distinguish the states with one-way LOCC with Alice
going first as well as with one-way LOCC with Bob going first if and only if
it is possible to distinguish the states with a product measurement.

###### Proof.

The states can automatically be distinguished with one-way LOCC in either
direction if the states can be distinguished with a product measurement.

For the other direction, suppose it is possible to distinguish the states with
one-way LOCC with Alice going first as well as with one-way LOCC with Bob
going first. Then from two applications of Theorem 1, we have that
${\mathcal{H}}_{A}=\oplus_{j}{\mathcal{S}}_{j}$ and similarly,
${\mathcal{H}}_{B}=\oplus_{i}{\mathcal{O}}_{i}$. This implies that the entire
Hilbert space has a product decomposition
${\mathcal{H}}={\mathcal{H}}_{A}\otimes{\mathcal{H}}_{B}=\oplus_{i,j}({\mathcal{S}}_{j}\otimes{\mathcal{O}}_{i})$,
with the corresponding graph implications of the result.

Suppose that Alice and Bob each perform their one-way measurements and receive
the outcomes ${\mathcal{S}}_{j}$ and ${\mathcal{O}}_{i}$. This means that
$v\in V_{j}\cap W_{i}$, where $V_{j}$ induces a clique in $\overline{G_{B}}$
and $W_{i}$ induces a clique in $\overline{G_{A}}$. Suppose that two vertices
are each contained in $V_{j}\cap W_{i}$. Then they are connected by an edge in
both $\overline{G}_{B}$ and $\overline{G}_{A}=G_{B}$, which is a
contradiction. Hence for each pair $i,j$, we have $|V_{j}\cap W_{i}|\leq 1$,
which means that Alice and Bob can determine the identity of their state
without further communication. ∎

The example below shows that the assumption $\overline{G}_{A}=G_{B}$ is
necessary in the statement of Theorem 2. If $\overline{G}_{A}\neq G_{B}$ ,
then Alice and Bob have extra flexibility, which weakens the assumption of
one-way LOCC in both directions.

######  Example 3.

Consider the following states in ${\mathbb{C}}^{3}\otimes{\mathbb{C}}^{3}$:

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

Observe in this case that $G_{A}=G_{B}=C_{3}\cup C_{4}$ is the disjoint union
of two cycle graphs, with respective labelling determined by the ordered sets:

$\\{|\psi^{A}_{1}\rangle,|\psi^{A}_{4}\rangle,|\psi^{A}_{5}\rangle\\},\quad\\{|\psi^{A}_{2}\rangle,|\psi^{A}_{6}\rangle,|\psi^{A}_{3}\rangle,|\psi^{A}_{7}\rangle\\},$

and

$\\{|\psi^{B}_{1}\rangle,|\psi^{B}_{2}\rangle,|\psi^{B}_{3}\rangle\\},\quad\\{|\psi^{B}_{4}\rangle,|\psi^{B}_{6}\rangle,|\psi^{B}_{5}\rangle,|\psi^{B}_{7}\rangle\\}.$

On the other hand, $\overline{G_{A}}$ is a graph not isomorphic to this graph,
given by the disjoint union of three isolated vertices
$(\\{1\\},\\{4\\},\\{5\\})$ and two isolated edges $(\\{2,3\\},\\{6,7\\})$.

These states are distinguishable with one-way LOCC: Alice measures in the
basis $\\{|0\rangle,\left(|1\rangle\pm|2\rangle\right)\\}$. If she gets the
outcome $|0\rangle$, then Bob completes the measurement using the same
measurement that Alice did; but if she gets either of the remaining outcomes,
Bob should measure in the standard basis. It is clear that these states are
symmetric with respect to Alice and Bob, so they can also be distinguished
with one-way LOCC with Bob going first and corresponding measurement
adjusments.

######  Proposition 1.

The 7 states described in Example 3 cannot be distinguished with a product
measurement, even though they can be distinguished with one-way LOCC in both
directions.

###### Proof.

This fact follows from the observation that Alice’s initial measurement for
one-way LOCC is unique. Her measurement operators must eliminate at least four
possibilities so that Bob has only three orthogonal possibilities remaining.
This means that the span of these four vectors cannot be all of
${\mathbb{C}}^{3}$, since they are in the kernel of a nonzero operator. There
are only 5 sets of 4 of the $|\psi_{i}\rangle$ that do not span all of
${\mathbb{C}}^{3}$. It must also be true that the complementary sets of 3
vectors must be mutually orthogonal on Bob’s side. This eliminates 2 of the
sets, leaving us with the following three sets of vectors:

$\displaystyle\\{|\psi_{4}\rangle,|\psi_{5}\rangle,|\psi_{6}\rangle,|\psi_{7}\rangle\\},\,\,\,\\{|\psi_{1}\rangle,|\psi_{2}\rangle,|\psi_{3}\rangle,|\psi_{5}\rangle\\},\,\,\,\\{|\psi_{1}\rangle,|\psi_{2}\rangle,|\psi_{3}\rangle,|\psi_{4}\rangle\\}.$

These correspond to the measurement
$\\{|0\rangle,\left(|1\rangle+|2\rangle\right),\left(|1\rangle-|2\rangle\right)\\}$
described above. There are no other options for Alice’s initial measurement or
for Bob’s. As we noted, the second measurement is dependent on the outcome of
the first; there is no way to accomplish this without knowing the other
outcome. ∎

In table form, we can see the possibilities with Example 3. The rows and
columns represent Alice and Bob’s measurements, respectively. The table
entries correspond to the possible states obtained amongst
$\\{|\psi_{1}\rangle,\ldots,|\psi_{7}\rangle\\}$:

$\displaystyle\begin{array}[]{c|c|c|c|c}&|0\rangle&|1\rangle+|2\rangle&|1\rangle-|2\rangle&\cr\hline\cr|0\rangle&1&4&5&\\{1,4,5\\}\cr\hline\cr|1\rangle+|2\rangle&2&6,7&6,7&\\{2,6,7\\}\cr\hline\cr|1\rangle-|2\rangle&3&6,7&6,7&\\{3,6,7\\}\cr\hline\cr&\\{1,2,3\\}&\\{4,6,7\\}&\\{5,6,7\\}&\end{array}$

This implies that Theorem 2 is not true without the assumption that
$G_{A}=\overline{G_{B}}$. As noted above, for this example
$G_{A}=G_{B}=C_{3}\cup C_{4}$, the union of a triangle with a four-cycle. This
has a clique cover number of 5. However, if you add a single diagonal to the
four-cycle, you get an intermediate graph which is a subgraph of
$\overline{G}_{B}$ and which has clique cover number 3, and it is this
measurement that corresponds to the one-way LOCC measurement. Crucially, this
diagonal edge is the same from both Alice’s and Bob’s perspective
(corresponding in both cases to states $|\psi_{6}\rangle$ and
$|\psi_{7}\rangle$); it must be part of the initial clique cover, which is why
the product measurement does not work.

##  5\. Chordal Graphs and One-Way LOCC

We next conduct further one-way LOCC analysis on some special cases considered
in graph theory.

######  Definition 4.

A graph $G$ is chordal if it contains no induced cycles $C_{n}$ of size
greater than three.

A vertex $v$ in a graph $G$ is simplicial if its neighbourhood forms a clique.

We note that the class of chordal graphs includes trees. Also, in connected
chordal graphs, the clique cover number is equal to the minimum vector rank
[19].

######  Proposition 2.

Suppose that Alice and Bob have a set of mutually orthogonal product states,
and let $G_{B}$ be the graph corresponding to Bob’s side. If the graph
$G=\overline{G}_{B}$ is chordal, then the states can be distinguished with
one-way LOCC with Alice going first.

###### Proof.

The proof of the proposition uses the fact that every chordal graph has a
simplicial vertex and that every induced subgraph of a chordal graph is
chordal. This implies the existence of a perfect elimination ordering of the
vertices [28], which was used by Hackney, et al. [19] to construct an OS-set
for chordal graphs. We model our proof on their algorithmic set-up,
constructing a direct sum decomposition corresponding to Alice’s measurement
as in the proof of Theorem 1. The algorithm is outlined below. As before, we
let $\phi:V_{A}\rightarrow{\mathcal{H}}_{A}$ be the association of vertices
with Alice’s states.

  * •

Initialize $j=1$ and put $V_{1}=V$. While $V_{j}\neq\emptyset$, do the
following:

  * •

Let $G_{j}$ be the induced subgraph of $G$ on vertices $V_{j}$. $G_{j}$ is an
induced subgraph of a chordal graph, so it is chordal.

  * •

Since $G_{j}$ is chordal, it has a simplicial vertex, which we call $v_{j}$.

  * •

Define ${\mathcal{K}}_{j}=\operatorname{span}\\{\phi(v):v\in V_{j},v\not\sim
v_{j}\\}$ to be the span of the nonneighbours of $v_{j}$ in $G_{j}$.

  * •

If $j=1$, set ${\mathcal{S}}_{1}={\mathcal{K}}_{1}^{\perp}$. Otherwise, set
${\mathcal{S}}_{j}={\mathcal{K}}_{j}^{\perp}\cap\left(\bigcap_{i=1}^{j-1}{\mathcal{S}}_{i}^{\perp}\right)$
as in the proof of Theorem 1. Since $\phi(v_{j})\in{\mathcal{K}}_{j}^{\perp}$
and $\phi(v_{j})$ has a nonzero component in
$\left(\oplus_{i=1}^{j-1}{\mathcal{S}}_{i}\right)^{\perp}$, this space is non-
trivial.

  * •

Let $V_{j+1}$ be the set of vertices $v\in V$ such that $\phi(v)$ has a
nonzero component in $\left(\oplus_{i=1}^{j}{\mathcal{S}}_{i}\right)^{\perp}$.

  * •

Increase $j$ and iterate.

When the process terminates, $V_{j}=\emptyset$ and
$\phi(v)\in\oplus_{i=1}^{j}{\mathcal{S}}_{i}$ for all $v\in V$. Hence,

$\displaystyle\oplus_{i=1}^{j}{\mathcal{S}}_{i}=\operatorname{span}\\{\phi(v):v\in
V_{j},v\not\sim v_{j}\\}={\mathcal{H}}_{A}.$

If two vertices $u$ and $v$ have $\phi(u),\phi(v)$ each with nonzero
components in ${\mathcal{S}}_{i}$, then both are neighbours of $v_{i}$ in
$G_{i}$. Since $v_{i}$ is simplicial in $G_{i}$, $u\sim v$ in $G_{i}$,
implying that $u\sim v$ in $G$.

This implies that we have constructed a measurement for Alice that will enable
Bob to distinguish his states. ∎

Consider the following example to help illustrate this proof.

######  Example 4.

Let $\phi:V_{A}\rightarrow{\mathcal{H}}_{A}$ be the association of vertices
with Alice’s states in $\mathbb{C}^{4}$ given as follows:

$\displaystyle\phi(v_{1})$ $\displaystyle=|0\rangle$
$\displaystyle\phi(v_{2})$ $\displaystyle=|1\rangle$
$\displaystyle\phi(v_{3})$ $\displaystyle=|0\rangle+|2\rangle+|3\rangle$
$\displaystyle\phi(v_{4})$ $\displaystyle=|1\rangle+|3\rangle$
$\displaystyle\phi(v_{5})$ $\displaystyle=|2\rangle.$

Then Alice’s graph $G_{A}$ is given as in Figure 3, and suppose that
$\overline{G_{B}}$ is the graph shown in Figure 4. Note that
$\overline{G_{B}}$ is chordal.

We have labeled the vertices to correspond to the order in which they will be
selected by the algorithm.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Figure 3. Alice’s graph, $G_{A}$.
$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Figure 4. Complement of Bob’s graph,
$\overline{G_{B}}$.

Now follow the algorithm above:

  * •

Iteration $j=1$: $V_{1}=V\neq\emptyset$.

$G_{1}=G=\overline{G_{B}}$, and $G_{1}$ has three simplicial vertices,
$v_{1},v_{2}$, and $v_{5}$. We choose our first vertex $v_{1}$. The non-
neighbours of $v_{1}$ in $G_{1}$ are $v_{2}$ and $v_{4}$. So
$K_{1}=\text{span}\\{\phi(v_{2}),\phi(v_{4})\\}$. Set
$S_{1}=K_{1}^{\perp}=\operatorname{span}{\\{|0\rangle,|2\rangle\\}}$. Then
$S_{1}^{\perp}=\operatorname{span}{\\{|1\rangle,|3\rangle\\}}$, and $V_{2}$ is
the set of vertices such that $\phi(v_{j})$ have a nonzero component in
$S_{1}^{\perp}$, so $V_{2}=\\{v_{2},v_{3},v_{4}\\}$.

  * •

Iteration $j=2$: $V_{2}\neq\emptyset$, so we continue.

$G_{2}$ is the induced graph on $V_{2}$, which is simply the path shown in the
figures on these vertices. The simplicial vertices are the leaves $v_{2}$ and
$v_{3}$. We choose our second vertex $v_{2}$. The non-neighbour of $v_{2}$ in
$G_{2}$ is $v_{3}$, so $K_{2}=\text{span}\\{\phi(v_{3})\\}$. Set
$S_{2}=K_{2}^{\perp}\cap S_{1}^{\perp}=\operatorname{span}{\\{|1\rangle\\}}$,
and then observe that $(S_{1}\oplus
S_{2})^{\perp}=\operatorname{span}{\\{|3\rangle\\}}$, so
$V_{3}=\\{v_{3},v_{4}\\}$.

  * •

Iteration $j=3$: $V_{3}\neq\emptyset$, so we continue.

$G_{3}$ is simply the edge $\\{v_{3},v_{4}\\}$. Both vertices are simplicial,
and we choose $v_{3}$. But $G_{3}$ is a complete graph, so $K_{3}=\\{0\\}$.
This means that $S_{3}={\mathbb{C}}^{4}\cap S_{1}^{\perp}\cap
S_{2}^{\perp}=\operatorname{span}{\\{|3\rangle\\}}$.

Now we have $(S_{1}\oplus S_{2}\oplus S_{3})^{\perp}=\\{0\\}$, so
$V_{4}=\emptyset$ and the process terminates on the next iteration.

This gives the decomposition
${\mathcal{H}}_{A}={\mathbb{C}}^{4}=\operatorname{span}{\\{|0\rangle,|2\rangle\\}}\oplus\operatorname{span}{\\{|1\rangle\\}}\oplus\operatorname{span}{\\{|3\rangle\\}}$.
The projections onto these three subspaces give a clique cover of
$\overline{G_{B}}:\\{\\{v_{1},v_{5},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{3},v_{4}\\}\\}$;
and the decomposition of ${\mathcal{H}}_{A}$ tells Alice how to make her
measurement with respect to this clique cover.

An argument similar to that used in the proposition above can be used to
extend the result to graphs that are $k$-trees, as defined below. We first
introduce the concept of perfect elimination orderings which we will use in
our definition of a $k$-tree.

######  Definition 5.

A perfect elimination ordering of a graph $G$ is an ordering
$\\{v_{1},v_{2},...,v_{n}\\}$ of the vertices of $G$ with the property that
for all $i$, $v_{i}$ is a simplicial vertex in the subgraph of $G$ induced by
the vertices $\\{v_{i},v_{i+1},...,v_{n-1},v_{n}\\}$.

It was first shown in [28] that a graph has a perfect elimination ordering if
and only if it is a chordal graph.

We now introduce the class of graphs known as $k$-trees first defined in [5]
which have been studied extensively, see for example [1, 28, 2].

######  Definition 6.

A graph $G$ is a $k$-tree if and only if it has a perfect elimination ordering
$\\{v_{1},v_{2},...,v_{n}\\}$ with two added properties:

  1. (1)

For all $i<n-k$, $v_{i}$ has degree $k$ in the subgraph of $G$ induced by the
vertices $\\{v_{i},v_{i+1},...,v_{n-1},v_{n}\\}.$

  2. (2)

The subgraph of $G$ induced by vertices
$\\{v_{n-k},v_{n-k+1},...,v_{n-1},v_{n}\\}$ is a $k+1$ clique.

$G$ is a partial $k$-tree if it is a subgraph of a $k$-tree.

It is clear from this definition that every $k$-tree is chordal and that every
vertex in a $k$-tree has degree at least $k$.

######  Proposition 3.

Suppose that Alice and Bob have a set of mutually orthogonal product states,
and let $G_{B}$ be the graph corresponding to Bob’s side. If there exists a
graph $G$ such that $G_{A}\leq G\leq\overline{G_{B}}$ and $G$ is a $k$-tree,
then the states can be distinguished with one-way LOCC with Alice going first.

###### Proof.

We prove this by induction on the number of vertices in $G$. If $G$ has $k+1$
vertices, then $G=K_{k+1}$ and Alice’s measurement is irrelevant; Bob can
distinguish the states by himself.

Now suppose that the result is true for all $k$-trees with fewer than $n$
vertices and let $G$ be a $k$-tree on $n$ vertices. Let $v_{1}$ be the vertex
in the perfect elimination ordering from Definition 6. Let
$|\psi\rangle=\phi(v_{1})$, recalling that $\phi$ is an orthogonal
representation of $G$, and let Alice measure with
$\\{|\psi\rangle\\!\langle\psi|,I-|\psi\rangle\\!\langle\psi|\\}$. If Alice
gets the first outcome, then she knows that the state is in the closed
neighbourhood of $v_{1}$. These are states that can be distinguished by Bob.

If Alice gets the second outcome, her state is now in the state
$\phi^{\prime}(v)=\left(I-|\psi\rangle\\!\langle\psi|\right)\phi(v)$ for some
$v$. Let $G^{\prime}=G-v$ be the induced subgraph of $G$ formed by deleting
$v$. Let $u$ be any neighbour of $v_{1}$. Then $u$ has at least $k$ other
neighbours in $G$, which means that there exists a vertex in $V$ that is
adjacent to $u$ but not $v_{1}$. This implies that $\phi(u)\neq\phi(v)$, which
implies that $\phi^{\prime}(u)\neq 0$. Hence $\phi^{\prime}$ is an orthogonal
representation of $G^{\prime}$. But $G^{\prime}$ is a $k$-tree by definition,
and so by our inductive assumption, Alice can complete her measurement to put
Bob in a position to determine their state. ∎

##  6\. The Graph of a Domino State Diagram

The original quantum ‘domino’ states were an orthonormal basis of
$\mathbb{C}^{3}\otimes\mathbb{C}^{3}$ consisting entirely of product states.
They were constructed in [7] as an example of a set of orthogonal product
states that cannot be distinguished by LOCC. A domino diagram was constructed
in [7] to help readers better picture this construction, wherein the
orthogonal basis states are represented by dominos and laid on a grid similar
to a chessboard (more details are given below). This has motivated
generalizations of domino states in larger Hilbert spaces; examples of these
can be found in [11, 32, 33]. We will focus on sets of domino states that form
a complete product basis of $\mathbb{C}^{m}\otimes\mathbb{C}^{n}$; but one can
also consider subsets of these bases, such as in Example 3.

We will define the set of generalized domino states on
$\mathbb{C}^{m}\otimes\mathbb{C}^{n}$ in terms of the associated domino
diagram. We define a domino diagram to be a partition of the $m\times n$
rectangular chessboard into a set of generalized dominos. The generalized
dominos each have positive integer length and width one and are placed either
horizontally or vertically on the chessboard aligned to the $m\times n$ grid.
We assume that the chessboard is on a torus, so that dominos which exit off an
edge simply continue on the other side.

Label the rows on the chessboard $0,1,2,...,m-1$ from top to bottom and the
columns $0,1,2,...,n-1$. This identifies each square on the board with an
element of ${\mathbb{Z}}_{m}\times{\mathbb{Z}}_{n}$. We can then construct a
bijection from ${\mathbb{Z}}_{m}\times{\mathbb{Z}}_{n}$ to a set of
generalized domino states in ${\mathbb{C}}^{m}\otimes{\mathbb{C}}^{n}$ as
follows: If there is a horizontal domino on row $r$ whose endpoints are the
$(r,b+1)$ and $(r,b+s)$ squares, then the point $(r,b+j)$ with $1\leq j\leq s$
gets mapped to $\sum_{k=1}^{s}\alpha_{r}^{k}\omega^{jk}|r\rangle|b+k\rangle$
where $\omega$ is the primitive $s$th root of unity and $\alpha_{r}\neq 0$ is
an arbitrary phase associated with row $r$. If there is a vertical domino on
column $c$ whose endpoints are the $(b+1,c)$ and $(b+s,c)$ squares, then the
$(b+j,c)$ square with $1\leq j\leq s$ gets mapped to
$\sum_{k=1}^{s}\beta_{c}^{k}\omega^{jk}|b+k\rangle|c\rangle$ where $\omega$ is
again the primitive $s$th root of unity and now $\beta_{c}$ is an arbitrary
phase associated with column $c$.

We can obtain the graphs $G_{A}$ and $G_{B}$ of a set of generalized domino
states directly from its associated domino diagram.

######  Definition 7.

Let $\mathcal{D}$ be an $m\times n$ domino diagram. Then the row (respectively
column) graph of $\mathcal{D}$ is the graph whose vertex set is the set of
$mn$ unit squares on the rectangular chessboard. Two distinct squares are
adjacent if and only if one or both of the following two conditions are
satisfied:

  1. (1)

The two squares lie in the same row (respectively column) on the chessboard.

  2. (2)

The two squares each lie in two different dominoes $D_{1}$ and $D_{2}$ and
there exists at least one row (respectively column) of $\mathcal{D}$ which
intersects both $D_{1}$ and $D_{2}$.

It is an easy exercise to show that the row and column graphs of a domino
diagram are the graphs $G_{A}$ and $G_{B}$, respectively, of the set of
generalized domino states corresponding to the domino diagram. Since $G_{A}$
and $G_{B}$ can never have an edge in common, $G_{A}\leq\overline{G_{B}}$ and
$G_{B}\leq\overline{G_{A}}$. We get equality ($G_{A}=\overline{G_{B}}$ and
$G_{B}=\overline{G_{A}}$ ) if and only if any two dominoes in the diagram have
either a common row or a common column that intersects them.

The row and column graphs of domino diagrams have a nice structure that allows
us to bound the clique cover number from below:

######  Proposition 4.

Let $G_{A}$ and $G_{B}$ be the row and column graphs of an $m\times n$ domino
diagram. Then $\mathrm{cc}(\overline{G_{A}})\geq n$ and
$\mathrm{cc}(\overline{G_{B}})\geq m$.

If in addition we know that $G_{A}=\overline{G_{B}}$, then
$\mathrm{cc}(\overline{G_{B}})\geq m-v+v^{2}$ and
$\mathrm{cc}(\overline{G_{A}})\geq n-h+h^{2}$, where $v$ and $h$ are the
lengths of the longest vertical and horizontal dominoes in the diagram.

###### Proof.

Without loss of generality, assume that the largest horizontal domino lies in
row 0, and recall the association of domino states with elements of
$\mathbb{Z}_{m}\times\mathbb{Z}_{n}$. The $n$ states of the form $\\{(0,j)\\}$
lie in the first row and thus form a clique in $G_{A}$ and an independent set
in $\overline{G_{A}}$. Since the clique cover number of a graph is at least
its independence number, we have $\mathrm{cc}(\overline{G_{A}})\geq n$. This
proves the first bound.

For the second bound, let $H$ be the induced subgraph of $\overline{G_{A}}$ on
the $2n$ vertices $\\{(i,j):i\in\\{0,1\\}\\}$. Because the set of states
associated with each row form an independent set in $\overline{G_{A}}$, the
graph $H$ is bipartite. This implies that the clique cover number of $H$ is
simply the number of edges in $H$, which is the sum of the degrees of the
vertices in a single partition.

If we assume that $G_{B}=\overline{G_{A}}$, then each vertex $(0,j)$ is
adjacent to $(1,j)$ in $H$, since they are in the same column. This implies
that the degree of vertex $(0,j)$ is at least one. If there is a horizontal
domino of length $h$ in row zero, then the degree of each of those
corresponding vertices is at least $h$, since they are connected to each of
the columns they appear in. This implies that if $G_{B}=\overline{G_{A}}$,

$\displaystyle\mathrm{cc}(\overline{G_{A}})\geq\mathrm{cc}(H)=\sum_{j}\deg(0,j)\geq
h(h)+(n-h)(1)=n-h+h^{2}.$

The proofs bounding $\mathrm{cc}(\overline{G_{B}})$ are similar, and the
result follows. ∎

We can obtain the following one-way LOCC consequence based on this graph
analysis and our earlier results.

######  Corollary 3.

Suppose we have a domino diagram covering an $m\times n$ grid, and consider
the set of generalized domino states in
${\mathbb{C}}^{m}\otimes{\mathbb{C}}^{n}$ associated with the diagram as
defined above. Suppose further that the corresponding graphs have
$G_{A}=\overline{G_{B}}$.

If the grid contains a vertical domino of length at least 2, then the states
cannot be distinguished with one-way LOCC with Alice going first; and if the
grid contains a horizontal domino of length at least 2, then the states cannot
be distinguished with one-way LOCC with Bob going first.

###### Proof.

Note that by Corollary 2, if the states can be distinguished with one-way LOCC
with Alice going first, then necessarily
$\mathrm{cc}(\overline{G_{B}})\leq\dim(\mathcal{H}_{A})=m$. But by Proposition
4, if $v>1$, then here we have
$\mathrm{cc}(\overline{G_{B}})=\mathrm{cc}(G_{A})\geq m-v+v^{2}>m$, and thus
the states cannot be distinguished with Alice going first. An analogous
argument can be used when $h>1$ for one-way LOCC distinguishability with Bob
going first. ∎

######  Remark 1.

This observation can be used to show that the states described by many of the
domino diagrams in the literature cannot be distinguished by one way LOCC. For
instance, the original $3\times 3$ domino diagram from [7] has two distinct
vertical dominoes of length two that intersect in a row; hence
$\mathrm{cc}(G_{A})\geq 4$. This diagram also has two distinct horizontal
dominoes that intersect in one column; hence $\mathrm{cc}(G_{B})\geq 4$. Since
$G_{A}=\overline{G_{B}}$ and $G_{B}=\overline{G_{A}}$, these states cannot be
distinguished by one-way LOCC by either Alice or Bob going first by Corollary
2 as well.

Acknowledgements. D.W.K. was partly supported by NSERC and a University
Research Chair at Guelph. C.M. was partly supported by Mitacs and the African
Institute for Mathematical Sciences. R.P. was partly supported by NSERC. M.N.
acknowledges the ongoing support of the Saint Mary’s College Office of Faculty
Development.

## References

  * [1] Fatemeh Alinaghipour, Shaun Fallat, and Karen Meagher.  On the relationship between zero forcing number and certain graph coverings.  Special Matrices, 2:30–45, 2014.
  * [2] Stefan Arnborg and Andrzej Proskurowski.  Linear time algorithms for NP-hard problems restricted to partial $k$-trees.  Discrete applied mathematics, 23(1):11–24, 1989.
  * [3] 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.
  * [4] 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.
  * [5] Lowell W Beineke and Raymond E Pippert.  The number of labeled $k$-dimensional trees.  Journal of Combinatorial Theory, 6(2):200–205, 1969.
  * [6] 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.
  * [7] 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.
  * [8] 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.
  * [9] Matthew Booth, Philip Hackney, Benjamin Harris, Charles R Johnson, Margaret Lay, Lon H Mitchell, Sivaram K Narayan, Amanda Pascoe, Kelly Steinmetz, Brian D Sutton, and Wendy Wang.  On the minimum rank among positive semidefinite matrices with a given graph.  SIAM Journal on Matrix Analysis and Applications, 30(2):731–740, 2008.
  * [10] Anthony Chefles.  Condition for unambiguous state discrimination using local operations and classical communication.  Physical Review A, 69(5):050307, 2004.
  * [11] Scott M Cohen.  General approach to quantum channel impossibility by local operations and classical communication.  Physical Review Letters, 118(2):020501, 2017.
  * [12] Alessandro Cosentino and Vincent Russo.  Small sets of locally indistinguishable orthogonal maximally entangled states.  Quantum Information & Computation, 14:1098–1106, 2014.
  * [13] Runyao Duan, Simone Severini, and Andreas Winter.  Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number.  IEEE Transactions on Information Theory, 59(2):1164–1174, 2013\.
  * [14] Tilo Eggeling and Reinhard F Werner.  Hiding classical data in multipartite quantum states.  Physical Review Letters, 89(9):097905, 2002.
  * [15] Shaun Fallat and Leslie Hogben.  Variants on the minimum rank problem: A survey II.  arXiv preprint arXiv:1102.5142, 2011.
  * [16] 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.
  * [17] Heng Fan.  Distinguishability and indistinguishability by local operations and classical communication.  Physical Review Letters, 92(17):177905, 2004.
  * [18] Sibasish Ghosh, Guruprasad Kar, Anirban Roy, and Debasis Sarkar.  Distinguishability of maximally entangled states.  Physical Review A, 70(2):022304, 2004.
  * [19] 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.
  * [20] Michał Horodecki, Aditi Sen, Ujjwal Sen, and Karol Horodecki.  Local indistinguishability: More nonlocality with less entanglement.  Physical Review Letters, 90(4):047902, 2003.
  * [21] 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.
  * [22] David W Kribs, Comfort Mintah, Michael Nathanson, and Rajesh Pereira.  One-way LOCC indistinguishable lattice states via operator structures.  Submitted for publication, 2019.
  * [23] 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.
  * [24] László Lovász, Michael Saks, and Alexander Schrijver.  Orthogonal representations and connectivity of graphs.  Linear Algebra and its Applications, 114:439–454, 1989.
  * [25] 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.
  * [26] Michael Nathanson.  Distinguishing bipartitite orthogonal states using LOCC: Best and worst cases.  Journal of Mathematical Physics, 46(6):062103, 2005.
  * [27] 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.
  * [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.
  * [32] Zhi-Chao Zhang, Fei Gao, Guo-Jing Tian, Tian-Qing Cao, and Qiao-Yan Wen.  Nonlocality of orthogonal product basis quantum states.  Physical Review A, 90(2):022313, 2014.
  * [33] Huijuan Zuo, Shuxia Liu, and Yinghui Yang.  New constructions of orthogonal product basis quantum states.  International Journal of Theoretical Physics, 57(5):1597–1603, 2018\.