# Operator and Graph Theoretic Techniques for Distinguishing Quantum States via One-Way LOCC
## 4 Graph Theory and Distinguishing Product States
#### Single-Qubit Sender and Graph Theory  
A basic result in LOCC theory [29; 30; 31] shows that any set of orthogonal product states in \(\mathbb{C}^{2}\otimes\mathbb{C}^{d}\) for arbitrary \(d\geq 2\) can be distinguished via full (two-way) LOCC. This is readily seen to not be the case for one-way LOCC. As a simple example, consider the two-qubit set \(\{|00\rangle,|10\rangle,|+1\rangle,|-1\rangle\}\) where \(|+\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\) and \(|-\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\). This set of four two-qubit states cannot be distinguished by one-way LOCC with [PERSON] going first; they can however be distinguished by one-way LOCC with [PERSON] going first and hence also by two-way LOCC. Nevertheless, one can characterize when one-way distinguishability is possible in the single-qubit sender case. As proved in [32] (Theorem 1), the states must take an appropriate form in terms of orthogonality on [PERSON]'s side versus the corresponding orthogonalities on [PERSON]'s side. That said, one could argue that the condition from [32] is perhaps not so operationally simple to apply to easily identify when states are distinguishable, if the set is large for example. Here we show how, in the case of product states, Theorem 4.2 can be refined for a single-qubit sender to yield an entire graph-theoretic set of testable conditions for one-way distinguishability. 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 [PERSON] going first if and only if there is some graph between the two graphs \(G_{A}\) and \(\overline{G_{B}}\) with a clique cover number of at most two; that is, there is a graph \(G\) such that  
\[G_{A}\leq G\leq\overline{G_{B}}\quad\text{and}\quad\operatorname{cc}\left(G \right)\leq 2. \tag{1}\]  
For the forward direction, our previous theorem gives the existence of \(G\) with a clique cover and POVM \(\{Q_{j}\}\) such that \(\phi(v_{1})^{*}\phi(v_{2})=0\) implies \(\phi(v_{1})^{*}Q_{j}\phi(v_{2})=0\) for all \(j\). This implies that either \(\operatorname{cc}\left(G\right)=1\) or else each \(Q_{j}\) is diagonal on the \(\{\phi(v_{1}),\phi(v_{2})\}\) basis. It follows that \(\operatorname{cc}\left(G\right)\leq 2\). For the backward direction, assume a graph \(G\) exists that satisfies the conditions of Equation (1). We shall consider the two cases as determined by the clique cover number of \(G\). Firstly, if \(\operatorname{cc}\left(G\right)=1\), then \(G\) is a complete graph. Since \(|G_{A}|=|G_{B}|\), \(G\) must contain all the vertices of \(G_{B}\), \(\overline{G_{B}}\) is a complete graph and all the vertices of \(G\) are disconnected pairwise in the graph \(G_{B}\). Thus, it follows that all of [PERSON]'s states are pairwise orthogonal in \(\mathcal{H}_{B}=\mathbb{C}^{d}\) (whether or not [PERSON]'s states are orthogonal). Hence, the full set of product states on \(\mathcal{H}_{A}\otimes\mathcal{H}_{B}=\mathbb{C}^{2}\otimes\mathbb{C}^{d}\) are one-way distinguishable, simply by a measurement that [PERSON] can perform on his states, independent of what [PERSON] does or communicates to [PERSON]. Now suppose that \(\operatorname{cc}\left(G\right)=2\). Let \(\{G_{1},G_{2}\}\) be a clique cover of \(G\) and let \(V_{0}=V(G_{1})\cap V(G_{2})\) be the set of vertices in \(G\) that are connected to one (and hence every) vertex in \(G_{1}\) and \(G_{2}\). Note that \(V_{0}\) is a proper subset of \(V(G_{i})\), for \(i=1,2\), as otherwise \(G_{1}\) would be a subgraph of \(G_{2}\), or vice-versa, and this would incorrectly imply that \(\operatorname{cc}\left(G\right)=1\). If \(V_{0}\) is empty, then \(G_{1}\) and \(G_{2}\) are disconnected and each is a subgraph of \(\overline{G_{B}}\). As such, [PERSON]'s states corresponding to vertices in \(G_{1}\) are mutually orthogonal, and the same is true of his states corresponding to vertices in \(G_{2}\).