1 Introduction↩︎

Quantum state distinguishability is a central topic in the theory of quantum communication. A core problem in the subject is to determine the distinguishability (or indistinguishability) of sets of quantum states shared amongst multiple parties. Of particular interest, in both theory and applications, is the paradigm in which each party can implement local (quantum) measurements but only classical communication is available between the parties. This restricted type of communication is denoted LOCC [1]–[4] and includes key topics such as quantum teleportation, data hiding, and several of their derivations [5]–[7].

Entanglement is the most famous example of quantum weirdness, but it is not necessary to observe quantum phenomena. Quantum (tensor) product states are precisely those pure states that are not entangled, and so, at least in principle, are easier to handle mathematically. Nevertheless, as demonstrated in the seminal quantum communication work [1], there exist sets of orthogonal product states, including complete product bases, that cannot be perfectly distinguished with LOCC. This phenomenon is known as ‘quantum nonlocality without entanglement’. This implies that there exist sets of quantum states that can be encoded using only classical communication followed by local quantum operations but which cannot then be decoded using only LOCC. This counter-intuitive phenomenon has motivated interest in determining whether or not a given set of product states is locally distinguishable since the earliest days of quantum information.

Recently, techniques from graph theory have been brought to the table for this problem [8]–[10]. The basic idea is that, in the case of quantum product states distributed over multiple parties, there is an orthogonal representation of the graph assigned to each party by the orthogonality relations on their parts of the states. In a bipartite system, with two parties called Alice and Bob, the product states define orthogonal representations of graphs for Alice’s (with graph denoted by \(G_A\)) and Bob’s (with graph denoted by \(G_B\)) parts of the states. One-way LOCC is a special case of interest that has received considerable attention [11]–[19], which in a bipartite system is defined by the requirement that Alice must complete her measurement before Bob can start his. In [10], results were obtained for one-way LOCC in a bipartite system, with chordal graphs identified as a key graph structure associated with guaranteeing one-way distinguishability. It was also shown that the graphs on their own do not determine distinguishability for the general case.

In this paper, we undertake the first comprehensive effort to extend this graph theoretic approach to full two-way LOCC in the bipartite case; that is, scenarios in which Alice and Bob can make local partial measurements and communicate as much as they like. Thus, the basic motivating question we consider in this work is the following:

We will expand on this question and surrounding details in the next section, which includes relevant preliminaries and an extended background discussion on LOCC state distinguishability. In Section 3, we briefly revisit the one-way case, with an eye toward extending it, and then we define the relevant set of graphs for full LOCC, what we call the distinguishable graphs, and determine some of its easily identifiable subsets. Section 4 includes our main results and observations on the structure of the set of distinguishable graphs, with an emphasis on identifying its closure properties and related important classes of graphs. We also present several examples throughout the work, and in Section 5 we conclude with some forward looking remarks.

2 Preliminaries and Background↩︎

In this section, we introduce the necessary background material and notation, and then we refine the above motivating question as part of a short introductory discussion on LOCC distinguishability of product states and graph theory.

2.1 Quantum Measurements and LOCC↩︎

The quantum systems we consider will be represented by a finite-dimensional Hilbert space \(\mathcal{H}\), which is made up of two subsystems representing the quantum state space of two physically separated parties, call them Alice and Bob. Mathematically, we have the joint system \(\mathcal{H}=\mathcal{H}_A\otimes \mathcal{H}_B\) where \(\mathcal{H}_A\) and \(\mathcal{H}_B\) are finite-dimensional complex vector spaces. A positive operator valued measure (POVM) is a set of positive (semidefinite) operators \(E_k\) that sum to the identity. Local operations and classical communication (LOCC) is a natural subclass of quantum operations whereby the parties involved in the communication are restricted to act locally on their respective subsystems (i.e., Alice can only act on \(\mathcal{H}_A\) and similarly for Bob) by performing measurements and quantum operations, and the parties are free to communicate any classical data [20].

Quantum states are unit length vectors, written in Dirac ket form \(| \psi \rangle\) (with dual functionals written in bra form as \(\langle \psi |\)). Product states in \(\mathcal{H}\) can be written as tensor products of states on the individual systems: \(| \psi \rangle=| \psi_A \rangle\otimes | \psi_B \rangle\). The basic setup in the LOCC state distinguishability framework is that the system \(\mathcal{H}\) has been prepared in a pure state \(| \psi_k \rangle\) from a known set of states \(\mathcal{S}=\{\psi_i\}\subseteq \mathcal{H}\). Alice and Bob would like to determine the value of \(k\) using only LOCC.

One-way LOCC, for example, refers to schemes for which the classical information can only flow in one direction, and full multi-directional LOCC entails no restrictions on the classical communication flows. More precisely, a one-way LOCC measurement with Alice going first (i.e., only Alice can communicate classical information of the two parties) is of the form \(\mathbb{M} = \{ A_k \otimes B_{k,j} \}_{k,j}\), with the \(A_k\)’s and \(B_{k,j}\)’s being positive operators satisfying \(\sum_k A_k = I_A\) and \(\sum_{j} B_{k,j} = I_B\) for each \(k\) [10]. Without loss of generality, each of the \(A_k\) and \(B_{k,j}\) can be assumed to be rank-one [14]. The operators define the one-way protocol as follows: Alice performs her measurement, communicates the result \(k\) to Bob, who then performs his measurement associated with the classical index \(k\). Within that measurement, the outcome \(j\) allows him to identify the state.

2.2 Graph Theory Basics↩︎

A graph \(G=(V, E)\) consists of a set \(V\) of vertices and a set \(E\) of edges (pairs of vertices). If \((u,v)\in E\), we say that vertices \(u\) and \(v\) are adjacent in \(G\), and we write \(u\sim v\in G\). Here, we consider only simple graphs: unweighted (edges are all assigned the number 1), undirected (edges are unordered pairs) graphs with no loops (edges \((u,v)\) satisfy \(u\neq v\)). The complement of a graph \(G\) is \(\overline{G}=(V, \overline{E})\) where \((u,v)\in \overline{E}\) if and only if \((u,v)\notin E\). A graph \(G' = (V',E')\) is a subgraph of \(G\), denoted \(G'\leq G\), provided \(V'\subseteq V\), \(E'\subseteq E\), and \((u,v)\in E'\) implies \(u,v\in V'\). An induced subgraph \(G'\) of a graph \(G\) is a subgraph for which \(u,v, \in V'\) and \((u,v)\in E\) implies that \((u,v) \in E'\) (all edges in \(E\) connecting vertices in \(V'\) are also edges in \(E'\)) and is written \(G' = G[V']\). A spanning subgraph \(G'\) of \(G\) satisfies \(V'=V\) (but not necessarily \(E'=E\)). Vertices \(u\) and \(v\) are neighbours in \(G\) if \((u,v) \in E\); the set of neighbours of \(u\) (excluding \(u\)) is denoted \(N_G(u)\); if we wish to include \(u\) in its set of neighbours, this is called the closed neighbourhood of \(u\), denoted \(N_G[u]\). The complete graph on \(n\) vertices is the graph \(K_n=(\{v_1, \dots v_n\}, E)\) where \((u,v)\in E\) provided \(u\neq v\) (i.e., there is an edge between every pair of vertices). The path on \(n\) vertices is a graph \(P_n=(\{v_1, \dots, v_n\}, E)\) for which the \(v_i\) are distinct and \(E=\{(v_i, v_{i+1})\,:\, 1\leq i\leq n-1\}\). Two vertices \(u\) and \(v\) in a graph \(G\) are connected if \(G\) contains a path from \(u\) to \(v\). A graph is connected if there is a path between every pair of vertices. If a graph is not connected then it is disconnected. A totally disconnected graph is a graph whose edge set is empty (note that the totally disconnected graph on \(n\) vertices, often written as \(O_n\), can also be written as \(\overline{K_n}\)). The cycle on \(n\) vertices is a graph \(C_n=(\{v_1, \dots, v_n\}, E)\) for which \(E=\{(v_i, v_{i+1})\,:\, 1\leq i\leq n-1\}\cup \{(v_n, v_1)\}\). A chord of a cycle is an edge \((u,v)\) that does not belong to the edge set of the cycle, but \(u\) and \(v\) are in the vertex set of the cycle. A chordal graph \(G\) is a graph in which every cycle \(C_n\leq G\) with \(n\geq 4\) has a chord.

A clique \(C\) of a graph \(G\) is a subset of vertices of \(G\) (i.e., \(C\subseteq V\)) such that \(u, v\in C\), \(u\neq v\), implies \((u,v)\in E\). Equivalently, the subgraph of \(G\) induced by \(C\) is a complete graph. A coclique, also called an independent set, is a subset \(S\) of the vertices of a graph \(G\) such that \(u, v\in S\), \(u\neq v\), implies \((u,v)\notin E\). A split graph is a graph for which the vertices can be partitioned into a clique and a coclique. It can easily be seen that any split graph is chordal. The converse is known to be false; the path on five vertices is a chordal graph which is not a split graph. A clique separating set of \(G\) is a subset of vertices such that the induced subgraph defined by the vertices forms a clique and the removal from \(G\) of the vertices and the edges that connect to them is a disconnected graph. 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 (i.e., a 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 with the condition that every edge is contained in at least one of the cliques.

2.3 Orthogonal Representations and LOCC Protocols↩︎

We now explicitly connect quantum measurements and graph theory:

Any set of bipartite product states \(\{ | \psi^A_k \rangle\otimes | \psi^B_k \rangle \}_{k=1}^r\) on \(\mathcal{H}_A \otimes \mathcal{H}_B\) can be associated with a pair of graphs. The orthogonality graph from Alice’s perspective, called Alice’s graph, 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\). Bob’s graph \(G_B\) can be defined similarly. Observe that the product states are mutually orthogonal if and only if \(G_A \le \overline{G_B}\), or equivalently vice-versa.

Continuing our discussion from above, note that given any pair of graphs \((G_A, G_B)\) with \(G_A \le \overline{G_B}\), there always exist corresponding sets of product states that can be distinguished with local operations and no mid-measurement communication: we can see this by constructing a vertex clique cover of \(G_A\) and identifying each clique with an element of the standard basis. We then let Alice’s states be the characteristic vectors of each vertex. We can build a similar representation for Bob’s graph. If Alice and Bob each measure in the standard basis, then their pair of outcomes \((a,b)\) uniquely determines the original state. (This process can be easily extended to multipartite systems.)

As a result of this observation, we can refine Question 1 in the context of full LOCC.

For the benefit of readers with limited exposure to the topic, we discuss LOCC protocols in more detail, at the level of explicit measurement steps and classical communication. Our aim is to give an intuitive understanding of how one-way and two-way LOCC discrimination proceeds in practice, via presentation of an example, before introducing formal criteria. Recall that a set of product states \(\{\,| \psi_k^A \rangle \otimes | \psi_k^B \rangle\,\}_{k=1}^r\) is distinguishable by LOCC if Alice and Bob can identify the given state with certainty using only local measurements and classical communication. Further, Alice and Bob are assumed to know the entire set of states in advance and to agree beforehand on a fixed LOCC protocol, including the order of measurements and all conditional measurement choices based on classical outcomes. The set is said to be distinguishable if, for every \(k\), the protocol identifies the state \(| \psi_k^A \rangle \otimes | \psi_k^B \rangle\) with probability \(1\).

Example 1.

Consider the following five orthogonal product states in \(\mathbb{C}^2 \otimes \mathbb{C}^3\), where \(| \pm \rangle = (| 0 \rangle \pm | 1 \rangle)/\sqrt{2}\): \[\begin{align} \psi_1 = | 1 \rangle &\otimes | 1 \rangle, \quad \psi_2 = | 0 \rangle \otimes | + \rangle, \quad \psi_3 = | 0 \rangle \otimes | - \rangle, \\ &\psi_4 = | + \rangle \otimes | 2 \rangle, \quad \psi_5 = | - \rangle \otimes | 2 \rangle . \end{align}\] Alice and Bob are given one of these states and must identify it using only LOCC.

As we have discussed above, we may associate graphs to Alice and Bob in which vertices correspond to indices of product states (or local states) and edges represent local non-orthogonality relations among them. See Figure 1 for a graph representation of the example. As noted in the next section, the resulting pair of graphs captures which pairs of states can or cannot be distinguished locally. Before turning to that discussion, let us explicitly describe the different types of distinguishability that apply in this example.

This set can be distinguished by a Bob-first one-way LOCC protocol. Bob first performs a local projective measurement in the basis \(\{| + \rangle,| - \rangle,| 2 \rangle\}\). If the outcome is \(| 2 \rangle\), the remaining possible states are \(\psi_4\) and \(\psi_5\), which Alice can distinguish by measuring in the basis \(\{| + \rangle,| - \rangle\}\). If the outcome is \(| + \rangle\), the remaining possible states are \(\psi_1\) and \(\psi_2\); if the outcome is \(| - \rangle\), the remaining possible states are \(\psi_1\) and \(\psi_3\). In either case, Alice can distinguish the remaining states by measuring in the computational basis \(\{| 0 \rangle,| 1 \rangle\}\).

This set can also be distinguished via a Bob-first two-way LOCC protocol. Bob first performs a local projective measurement with outcomes corresponding to the operators \(| 2 \rangle\langle 2 |\) and \(| 0 \rangle\langle 0 | + | 1 \rangle\langle 1 |\) (from Bob’s perspective, this measurement leaves all states unchanged; other measurements could change the post-measurement states). Bob then communicates the outcome to Alice. If Bob’s outcome corresponds to \(| 2 \rangle\langle 2 |\), the state must be either \(\psi_4\) or \(\psi_5\), which Alice distinguishes by measuring in the basis \(\{| + \rangle,| - \rangle\}\). If Bob’s outcome instead corresponds to the subspace spanned by \(| 0 \rangle\) and \(| 1 \rangle\), the remaining possible states are \(\psi_1\), \(\psi_2\), and \(\psi_3\). Alice then measures in the basis \(\{| 0 \rangle,| 1 \rangle\}\). The outcome \(| 1 \rangle\) identifies \(\psi_1\), while the outcome \(| 0 \rangle\) leaves \(\psi_2\) and \(\psi_3\) indistinguishable to Alice. In this case, Alice communicates her outcome to Bob, who performs a final measurement in the basis \(\{| + \rangle,| - \rangle\}\) to distinguish \(\psi_2\) from \(\psi_3\).

In an Alice-first one-way LOCC protocol, each outcome of Alice’s measurement must leave Bob with states that are perfectly distinguishable. Since \(\psi_4\) and \(\psi_5\) have identical states on Bob’s subsystem, no outcome can contain both, so each outcome must exclude either \(| + \rangle\) or \(| - \rangle\) on Alice’s side. Moreover, since Bob cannot distinguish \(| 1 \rangle\) from \(| + \rangle\) or \(| - \rangle\), Alice cannot allow \(| 0 \rangle\) and \(| 1 \rangle\) to appear together in any outcome. However, any outcome that contains \(| 1 \rangle\) while excluding \(| 0 \rangle\) necessarily contains both \(| + \rangle\) and \(| - \rangle\). This forces \(\psi_4\) and \(\psi_5\) to remain in the same outcome, a contradiction. Hence, Alice-first one-way LOCC is impossible for this set. Nevertheless, as noted above, the set is distinguishable by Alice-first two-way LOCC since Bob can initiate a one-way protocol while Alice takes no initial action.

3 From One-Way to Full LOCC Distinguishability↩︎

In this section, we first present some recent results and a series of examples on one-way LOCC distinguishability, with an eye toward extending the graph theory approach to full LOCC. We then define and obtain initial results on the set of distinguishable graphs.

3.1 Structural Conditions for One-Way LOCC↩︎

As described above, orthogonal (bipartite) quantum product states can be described by graph representations that capture non-orthogonality relations on Alice’s and Bob’s subsystems. This raised a structural question: given only the associated graphs, can we determine whether the set of states is perfectly distinguishable without specifying the concrete states? This has been studied in the context of one-way LOCC distinguishability [8]–[10], where the answer was found at the highest level to be: sometimes.

An early result in LOCC distinguishability [21]–[24] 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. As proved in [22], the states can always be written in a form in terms of orthogonality on Alice’s side versus the corresponding orthogonalities on Bob’s side that allow for distinguishability. On the other hand, for one-way LOCC this ‘single-qubit sender’ scenario can result in states that are indistinguishable as well. In fact, this case is one in which we have a complete graph theoretic characterization.

Let us return to the example above and observe how the distinguishability conclusions there follow readily from this result.

More generally, the following graph-theoretic description has been obtained, linking chordal graph structure with one-way distinguishability of all orthogonal representations for which the graph lies between the associated Alice and Bob (complement) graphs.

This result has a number of consequences, such as the previous theorem which can be derived from it. However, we note that the result has some embedded subtleties, associated jointly with the graphs and the state representations, that warrant further investigation even just in the one-way case. For instance, the following example shows that one-way LOCC distinguishability can still hold even when the associated graph is not chordal.

We also have access to a number of results that tell us states are one-way indistinguishable when certain graph constraints are satisfied. As an example, we note the following result.

Let \(G\) be a graph with \(n = |G|\). We write \(S_G\) for the set of \(n \times n\) matrices whose zero–nonzero pattern is constrained by the adjacency structure of \(G\). The positive semidefinite minimum rank of \(G\) was defined in [10] by \[\eta_{+}(G) := \min \{ \mathrm{rk}(M) : M \in S_G, M \textrm{ is positive semidefinite with invertible diagonal}\}.\] Recall that a simplicial vertex in a graph is a vertex whose neighbours form a clique.

The following is an illustrative example of this phenomenon.

Example 4.

Consider the following set of (unnormalized) states on \(\mathbb{C}^3 \otimes \mathbb{C}^3\):

\[\begin{align} \psi_1 = | 0 \rangle \otimes & | 0+1 \rangle,\quad \psi_2 = | 0 \rangle \otimes | 0-1 \rangle, \quad \psi_3= | 2 \rangle \otimes | 1+2 \rangle,\quad \psi_4 = | 2 \rangle \otimes | 1-2 \rangle, \\ & \psi_5 = | 1-2 \rangle \otimes | 0 \rangle, \quad \psi_6 = | 0+1 \rangle \otimes | 2 \rangle,\quad \psi_7 = | 0-1 \rangle \otimes | 2 \rangle . \end{align}\]

Observe that \(G = \overline{G_B}\) has no simplicial vertices. Here we have \(\dim\mathcal{H}_A= \dim\mathcal{H}_B=3\), and one can show (by considering basic graph parameter inequalities) that \(\eta_+(G)=3\). Hence, Theorem 3 implies that the states are not distinguishable via one-way LOCC with Alice going first. Applying the same reasoning to \(\overline{G_A}\) shows that one-way LOCC distinguishability with Bob going first is also impossible. We will revisit this example in the next section, showing how the states are in fact distinguishable with full LOCC.

We point the reader to [10] for various other examples of the fact that there are many graphs with representations that can always be distinguished with two-way LOCC but not always with one-way.

3.2 Full LOCC Distinguishability and Graph Theory↩︎

We next extend the graph-theoretic framework adapted to full LOCC. To this end, let us conceptually illustrate how an LOCC protocol can be described via a tree representation that is often used to describe LOCC protocols, making use of the example above.

Example 5. Returning to Example 4, recall the states are not distinguishable via one-way LOCC, regardless of which party goes first. They can, however, be perfectly distinguished using a multi-round LOCC protocol. The full LOCC protocol is depicted in Figure 3 as a measurement tree, following the construction in [1].

Regarding the labels in Figure 3, the notation A\((\cdot)\) and B\((\cdot)\) indicate measurements by Alice and Bob, respectively. A label such as A\(0/1\) means that the \(| 0 \rangle\) and \(| 1 \rangle\) outcomes are not distinguished. Bold-faced numbers at the leaves indicate states inferred from the measurement chain. Branches at each node correspond to POVM outcomes, so outcomes with zero support (e.g., \(| 2 \rangle\) in Alice’s Level 3 measurement in the basis \(\{| 0 \rangle,| 1 \rangle,| 2 \rangle\}\)) is omitted. Note that after Alice’s first projective measurement, \(\psi_5 = | 1-2 \rangle\otimes | 0 \rangle\) is projected onto \(| 1 \rangle \otimes | 0 \rangle\) in the \(\{0,1\}\) branch.

Explicitly, the protocol works as follows: Alice first performs a projective measurement separating the subspaces \(\mathrm{span}\{| 0 \rangle,| 1 \rangle\}\) and \(\mathrm{span}\{| 2 \rangle\}\). Conditioned on the outcome, Bob applies a measurement adapted to the remaining candidate states. In the \(\{0,1\}\) branch, further rounds of local measurements are required, whereas the \(\{2\}\) branch is done immediately. The tree encodes the complete sequence of conditional measurements leading to discrimination.

In general, 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 set is perfectly distinguishable via a multi-round LOCC protocol if the associated measurement tree satisfies:

• Each leaf corresponds to a singleton set of states.

• For every state, there exists a path from the root to a leaf labelled by that state.

The tree description is conceptually useful for visualizing LOCC protocols. Turning now to our investigation, we recall the content of Theorem 2, namely that every set of bipartite product states represented by the graphs \(G_A, G_B\) can be distinguished with one-way LOCC if and only if there exists a graph \(G\) such that \(G_A \le G \le \overline{G_B}\) and \(G\) is chordal. This motivates our starting point for full LOCC as follows.

Note that if we have a set of bipartite product states \(\mathcal{S}\) represented by graphs \(G_A\) and \(G_B\), then the number of vertices in \(G_A\) and in \(G_B\) are equal to \(|\mathcal{S}|\). The fact that \(|G_A| = |G_B|\) combined with the inequality \(G_A \le G \le \overline{G_B}\) implies that \(|G| = |G_A|\) and that every vertex in \(G\) is also a vertex in \(G_A\). In other words, \(G_A\) is a spanning subgraph of \(G\) and, similarly, \(G_B\) is a spanning subgraph of \(\overline{G}\).

We begin by showing that the sets \(\mathcal{G}_0\) and \({\mathcal{G}}_{1}\) can be identified with well-known classes of graphs.

Before continuing deeper into the graph structures that belong to the set of distinguishable graphs, we show cycles with five or more vertices do not belong to the set. Recall that an unextendible product basis is a set of pairwise orthogonal product vectors that does not span all of \(\bigotimes_{i = 1}^m \mathcal{H}_i\) and whose orthogonal complement contains no product vector. It is well-known that an unextendible product basis cannot be distinguished even with separable measurements. This means that any graph that admits an unextendible product basis is not in \(\mathcal{G}\).

We note that [21] gives a condition on the dimension of the local spans that determines whether a basis is extendible as follows.

In the bipartite case, we need to be able to partition our states into \(S = S_1 \cup S_2\) such that the dimension of Alice’s states in \(S_1\) is strictly less than Alice’s dimension and the dimension of Bob’s states in \(S_2\) is strictly less than Bob’s dimension in order for these states to be extendible. In particular, a simple counting argument shows that a set of \(n\) product states in \(\mathbb{C}^{d_1}\otimes\mathbb{C}^{d_2}\), with \(n\geq \max\{d_1,d_2\}\), is unextendible if every set of \(d_1\) Alice states is linearly independent, every set of \(d_2\) Bob states is linearly independent, and \(d_1 + d_2 \le n +1\).

Relatedly, we note that Alon and Lovasz [25] looked at the connectivity of graphs in terms of guaranteeing a representation in general position (i.e., any subset of the represented states with cardinality equal to the dimension of the Hilbert space is linearly independent), though their definition of a representation is slightly different.

The unextendible product basis viewpoint and the dimension related observations above allow us to prove the following.

4 Structure of the set of Distinguishable Graphs↩︎

In previous work, the set of graphs associated with one-way LOCC distinguishability was identified to be exactly the set of chordal graphs [10]. In this section, we investigate closure properties of the set of distinguishable graphs and relate \(\mathcal{G}\) to well-known graph classes.

We start with some easily derived closure properties, which will be useful in what follows. Recall that for two graphs \(G_1 = (V_1,E_1)\) and \(G_2 = (V_2,E_2)\), the disjoint union \(G = G_1 \sqcup G_2\) is the graph with vertices \(V = V_1 \cup V_2\) and edges \(E = E_1 \cup E_2\). The join \(G = G_1 \vee G_2\) is the disjoint union of \(G_1\) and \(G_2\) together with all edges joining \(V_1\) and \(V_2\).

Many natural classes of graphs are closed under taking of induced subgraphs. We would like to show that the set of distinguishable graphs \(\mathcal{G}\) has this property. This is not entirely trivial. If \(H\) is an induced subgraph of \(G\), any representation of \(G\) can be restricted to a representation of \(H\), but we will generally not get every representation of \(H\) this way. In order to prove this result, we will focus on local measurements that respect the structure of \(G\), motivating the following definition.

We do not require the measurement to respect all orthogonal pairs, only those needed to remain a subgraph of \(G\).

While Lemma 7 started with a large graph \(G \in \mathcal{G}\) and showed that its induced subgraphs remain in \(\mathcal{G}\), it is frequently useful to be able to go in the other direction, to build up larger graphs from smaller ones. In Example 4, Alice’s graph has a cut vertex \(v_5\), and the initial projective measurement in Figure 3 produces two branches that are separated by this cut vertex. This is an example of a more general phenomenon in which useful quantum measurements are suggested by separating sets of vertices that induce a clique.

Going in the other direction, we can build a graph \(G\) from smaller graphs \(G_1\) and \(G_2\) by identifying the vertices of a clique in \(G_1\) with the vertices of a clique in \(G_2\). This graph operation is called a clique sum (a notion that goes back almost a century [27]), and is written \(G = G_1 \oplus G_2\) when the cliques and the identifications are clear. Note that in some contexts, clique sums allow the removal of edges from the shared clique, but in what follows no such deletion is not permitted. For emphasis, we will frequently call it an edge-preserving clique sum.

We establish the fact that \(\mathcal{G}\) is closed under edge-preserving clique sums. As with induced subgraphs, any representation of \(G_1, G_2, \ldots, G_r\) can be concatenated to create a representation of \(G = \oplus G_i\), but not all representations of \(G\) are obtained this way.

We construct an example in which we generate an LOCC measurement for a clique sum as described in Lemma 8.

Example 6.

Let \(H = \overline{P_5}\) be the house graph on 5 vertices. This is a 4-cycle attached to a 3-cycle, and it is the complement of a path on 5 vertices. Since its complement is chordal, \(H \in \mathcal{G}\).

Define the graph \(G = H \oplus H\) to be the clique sum of two copies of \(H\) joined along a 3-cycle such that the simplicial vertices are not identified with each other. In Figure 4, we note that the induced subgraphs on the first five vertices and on the last five vertices are each isomorphic to \(H\).

We claim that any product state representation with \(G = G_A = \overline{G_B}\) of \(G\) can be distinguished with LOCC by building on an existing protocol associated with the graph \(H\). One such representation of (unnormalized) states is given below. Note that the specifics of Bob’s representation are not needed to reduce the problem from \(G\) to \(H\). \[\begin{align} | \psi_{1} \rangle& = | 0 \rangle_A \otimes| 1 + 2 \rangle_B & | \psi_{2} \rangle &= | 0 + 1 \rangle_A\otimes| 0+3 \rangle_B \\ | \psi_{3} \rangle &= | 1+2 \rangle_A \otimes| 2 \rangle_B & | \psi_{4} \rangle &= | 0 - 1 + 4 \rangle_A\otimes| 0 \rangle_B\\ | \psi_{5} \rangle &= | 2 - 3 + 4 \rangle_A\otimes| 1 \rangle_B & | \psi_{6} \rangle &= | 3 \rangle_A \otimes| 2+3 \rangle_B \\ | \psi_{7} \rangle &= | 2+3 \rangle_A\otimes| 1+3 \rangle_B \end{align}\] We claim that any protocol to locally distinguish states associated with \(H\) can be incorporated into a protocol to distinguish all the states associated with \(G\). We follow the procedure in the proof of Lemma 8, setting \(V_0 = \{v_3, v_4,v_5\}\), which induces a clique. Then \(V_1 = \{ v_1, v_2 \}\) and \(V_2 = \{v_6,v_7\}\). Alice performs the measurement \(\{ P_1, P_2, P_0\}\), where \(P_i\) projects onto the span of the states corresponding to \(V_i\) for \(i = 1,2\) and \(P_0\) is everything else; that is, \[\begin{align} P_1 = |0\rangle\!\langle 0 |_A + |1\rangle\!\langle 1 |_A, \qquad P_2 = |2\rangle\!\langle 2 |_A + |3\rangle\!\langle 3 |_A, \qquad P_0 = |4\rangle\!\langle 4 |_A . \end{align}\]

If we get the outcome \(P_0\), the remaining states (possible fewer than three) induce a clique in \(G\) and form an independent set in \(\overline{G} \ge G_B\), so Bob can distinguish them perfectly. Suppose we get either outcome \(P_1\) or \(P_2\). In this case only four possible states remain, forming a copy of \(C_4\) on \((v_1,v_2,v_3,v_4)\) or \((v_3,v_5,v_6,v_7)\). Since \(C_4\) is an induced subgraph of \(H\) and we assumed that \(H \in \mathcal{G}\), we know that \(C_4 \in \mathcal{G}\) from Lemma 7 and we can complete the measurement using any specified protocol for \(H\), restricting Alice’s first measurement to the span of the remaining states.

By combining Lemma 6, Lemma 7, and Lemma 8, we obtain the following result.

Theorem 5 has immediate application in terms of where the set \(\mathcal{G}\) of distinguishable graphs fits in terms of common graph classes.

A cograph [28] is a graph that can be generated from an isolated vertex (that is, a vertex with no incident edges) by repeated use of graph complementation and disjoint union. Seven equivalent conditions for a graph to be a cograph are given by [28]. The simplest and best known of these is that a graph is a cograph if and only if it has no induced subgraph that is isomorphic to \(P_4\) (the path graph on 4 vertices). Since \(K_1 \in \mathcal{G}\) and \(\mathcal{G}\) is closed under complements and disjoint unions, we have the following result.

The set of cographs that are also split graphs is known as the set of threshold graphs; see, e.g. [29]. Threshold graphs can be constructed from a one-vertex graph through repeated additions of a single vertex of two possible types: an isolated vertex or a dominating vertex (that is, a single vertex that is connected to all other vertices). In particular, the sets of split graphs and cographs are not subsets of one another, but both are subsets of \(\mathcal{G}\) (by Theorem 4 and Corollary 9).

Let us point out that \(\mathcal{G}\) is not closed under every natural graph operation. Recall that the tensor product \(G_1\times G_2\) of graphs \(G_1\) and \(G_2\) is a graph having vertex set equal to the cartesian product \(V(G_1) \times V(G_2)\), where vertices \((v_1,v_2)\) and \((v_1',v_2')\) are adjacent in \(G_1\times G_2\) if and only if \(v_1\) is adjacent to \(v_1'\) in \(G_1\) and \(v_2\) is adjacent to \(v_2'\) in \(G_2\). If \(G_1\) and \(G_2\) have adjacency matrices \(A_1\) and \(A_2\), then the adjacency matrix of \(G_1 \times G_2\) is \(A_1 \otimes A_2\). Similarly, the cartesian product \(G_1\square G_2\) of graphs \(G_1\) and \(G_2\) is a graph having vertex set equal to the cartesian product \(V(G_1) \times V(G_2)\), where vertices \((v_1,v_2)\) and \((v_1',v_2')\) are adjacent in \(G_1\square G_2\) if and only if \(v_1\) is adjacent to \(v_1'\) in \(G_1\) and \(v_2=v_2'\) , or \(v_2\) is adjacent to \(v_2'\) in \(G_2\) and \(v_1=v_1'\).

Finally, we show that the set of distinguishable graphs is properly contained inside a particular set of graphs.

Weakly chordal graphs were first defined and studied in [30].

Proof. Fix \(n \ge 5\). From Proposition 5, we know that \(C_n \notin \mathcal{G}\). Since \(\mathcal{G}\) is closed under induced subgraphs and complements, \(G \in \mathcal{G}\) implies that neither \(G\) or \(\overline{G}\) contains an induced cycle \(C_n\). Since this is true for all \(n\ge 5\), \(G\) is weakly chordal.

On the other hand, the states in Example 4 are a subset of the nonlocality without entanglement states in [1], where it is shown that the first eight states cannot be perfectly distinguished with any finite number of rounds of LOCC, hence the graph representing them is not in \(\mathcal{G}\). This graph \(G\) is given in Figure 5 and is easily seen to be weakly chordal despite not being in \(\mathcal{G}\). Hence the inclusion is proper.

 ◻

We indicate the known graph class relationships in Figure 6.

5 Conclusion and Outlook↩︎

This work opens up several new lines of investigation. Most obvious is a direct continuation of the work we have begun on determining the structure of the class of distinguishable graphs for full LOCC. The current work is largely concerned with determining and deriving the basic graph closure properties of the set, along with relating the set of distinguishable graphs to other well-known graph classes. Natural next steps in this direction would be to conduct a deeper analysis on the distinguishability properties of specific subclasses of graphs, including those that arise in LOCC communication applications. Moreover, the results in [10] on one-way LOCC established links between local quantum measurements, graph theory, and the theory of matrix completions, and all of these directions can now be pursued in depth for full LOCC by building on this work.

In terms of matrix completions, we note that the set of representations of a graph corresponds via Gram matrices contained in the cone of positive semidefinite matrices with a given zero pattern, matching that of the graph’s adjacency matrix. Thus, every result about classes of graphs has a corresponding result in terms of adjacency matrices and their associated cones. We showed that \(\mathcal{G}\) was closed under complements and disjoint unions. Recall the fact that \(A(\overline{G})=J-I-A(G)\), where \(A(G)\) is the adjacency matrix of \(G\) and \(J\) is the all 1’s matrix, and \(A(G_1\sqcup G_2)=A(G_1)\oplus A(G_2)\). One can see how the roles of \(G_A\) and \(G_B\) are interchanged in \(A(\overline{G})\) since all the off-diagonal entries get “flipped”—0’s become 1’s and 1’s become 0’s. One can also see that the adjacency matrix \(A(G_1\sqcup G_2)\) is block-diagonal, leading to the orthogonal subspaces argument used herein. The final two operations simply reduce the adjacency matrix of the original graph; such reductions do not change the LOCC-distinguishability of the graph, as we saw in Section 4. Similarly, to construct the adjacency matrix of an induced subgraph, we simply delete the appropriate rows/columns: \(A(G')=A(G)_{(-i,-i)}\), and the adjacency matrix of an edge-preserving clique sum is constructed by combining \(A(G_1)\) and \(A(G_2)\) by merging the rows and columns that correspond to the identified pairs of vertices in the shared \(k\)-clique. We showed that \(\mathcal{G}\) is closed under all of these operations.

We also showed that \(\mathcal{G}\) is not closed under tensor and cartesian products. Looking at the adjacency matrices, we see that \(A(G_1\times G_2)=A(G_1)\otimes A(G_2)\) and \(A(G_1\square G_2)=A(G_1)\otimes I+I\otimes A(G_2)\), operations which distort the adjacency matrices in a manner that does not preserve LOCC-distinguishability. Another possible graph operation to explore is the \(\ltimes\) product defined in [31] as a generalization of the double cover operation, for which graphs \(G_1\) and \(G_2\) on the same vertex set generate a new graph with adjacency matrix \(A(G_1 \ltimes G_2)=\begin{pmatrix} A(G_1)& A(G_2)\\ A(G_2)& A(G_1) \end{pmatrix}\). A characterization of when \(\mathcal{G}\) is closed or not in terms of the adjacency matrices would prove useful, especially in cases when the graph operation, e.g., \(\ltimes\), is defined via its adjacency matrix.

On another topic, when we move the conversation from full quantum state discrimination to LOCC, deciding whether states are distinguishable is equivalent to finding a sequence of local measurements that eliminate some states but do not disturb the remaining states too much. In the case of one-way LOCC, in general each local measurement must eliminate the complement of a clique, and for one-way bipartite LOCC we know this is always possible if and only if the corresponding graph is chordal. This follows from the general result that any set of quantum states whose orthogonality graph is chordal can be reduced to an induced clique with a quantum measurement. As we move to two-way LOCC, we need to consider a sequence of nontrivial steps that accomplish discrimination. Each of these steps should, in general, be an orthogonality-preserving quantum measurement, and we can require that it be a nontrivial measurement so that our set of possible states post-measurement is strictly smaller than what we started with. This description is essentially the same whether we are talking about bipartite or multipartite discrimination. It only depends on the collection of local graphs. Thus, it would be natural to pursue an extension of the approach introduced here to multipartite LOCC. One can easily generalize from a two-party system \(\mathcal{H}=\mathcal{H}_A\otimes \mathcal{H}_B\) to a \(d\)-party system \(\mathcal{H}=\bigotimes_{i=1}^d \mathcal{H}_i\). A multipartite product state would then be of the form \(| \psi \rangle=| \psi_1 \rangle\otimes | \psi_2 \rangle\otimes \cdots \otimes | \psi_d \rangle\). If we have \(d\) parties and a set of multipartite product states, let \(G_i = (V,E_i)\) be the local orthogonality graph associated with the \(i\)th party. The states are orthogonal if and only if \(\bigcap_{i = 1}^d E_i\) is empty. The interplay between these graphs and the implications for distinguishability can then be considered. LOCC in a multipartite context is frequently quite challenging, but we think it should be possible to extend at least some of the graph theory approach to the problem of locally distinguishing sets of multipartite product states.

One could also consider this work in the context of general quantum state discrimination, which is equivalent to asking how much one local party can discover without communication from anyone else. The problem of distinguishing among a set of quantum states is one of the oldest problems in quantum information theory. A set of pure states can be distinguished perfectly if and only if they are mutually orthogonal; but outside of this special circumstance, there are many possible ways to define optimal discrimination. The results in [10] incorporated the problem of identifying subsets of pure quantum states, but other paradigms exist such as minimum error, unambiguous, antidiscrimination, and orthogonality-preserving discrimination. Although some of these conditions have been demonstrated using graphs, there does not appear to have been attempts to classify graphs that always work as we have considered in this work.

We plan to undertake some of these investigations elsewhere, and we invite other interested researchers to do the same.

D.W.K.was supported by NSERC Discovery Grant number 400160. R.P. was supported by NSERC Discovery Grant number 400550. S.P.was supported by NSERC Discovery Grant number 1174582, the Canada Foundation for Innovation (CFI) grant number 35711, and the Canada Research Chairs (CRC) Program grant number 231250.

References↩︎