# Generalized spectral characterization of signed trees

Yizhe Jia Wei Wanga Hao Zhangb
aSchool of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an
710049, P. R. China
bSchool of Mathematics, Hunan University, Changsha 410082, P. R. China
Corresponding author<EMAIL_ADDRESS>
###### Abstract

Let $T$ be a tree with an irreducible characteristic polynomial $\phi(x)$ over
$\mathbb{Q}$. Let $\Delta(T)$ be the discriminant of $\phi(x)$. It is proved
that if $2^{-\frac{n}{2}}\sqrt{\Delta(T)}$ (which is always an integer) is odd
and square free, then every signed tree with underlying graph $T$ is
determined by its generalized spectrum.

Keywords: Graph spectra; Cospectral graphs; Determined by spectrum; Rational
orthogonal matrix; Signed graph
Mathematics Subject Classification: 05C50

##  1 Introduction

It is well known that the spectra of graphs encode a lot of combinatorial
information about the given graphs. A major unsolved question in spectral
graph theory is: “What kinds of graphs are determined (up to isomorphism) by
their spectrum (DS for short)?”. The problem originates from chemistry and was
raised in 1956 by Günthard and Primas [1], which relates Hückle’s theory in
chemistry to graph spectra. The above problem is also closely related to a
famous problem of Kac [12]: “Can one hear the shape of a drum?” Fisher [11]
modelled the drum by a graph, and the frequency of the sound was characterized
by the eigenvalues of the graph. Hence, the two problems are essentially the
same.

It was commonly believed that every graph is DS until the first counterexample
(a pair of cospectral but non-isomorphic trees) was found by Collatz and
Sinogowitz [2] in 1957. Another famous result on cospectral graphs was given
by Schwenk [16], which states that almost every tree is not DS. For more
constructions of cospectral graphs, see, e.g., [10, 13, 17]. However, it turns
out that showing a given graph to be DS is generally very hard and
challenging. Up to now, only a few graphs with very special structures are
known to be DS. We refer the reader to [7, 8] for more background and known
results.

In recent years, Wang and Xu [19] and Wang [20, 21] considered a variant of
the above problem. For a simple graph $G$, they defined the _generalized
spectrum_ of $G$ as the spectrum of $G$ together with that of its complement
$\bar{G}$. A graph $G$ is said to be _determined by its generalized spectrum_
(DGS for short), if any graph having the same generalized spectrum as $G$ is
necessarily isomorphic to $G$.

Let $G$ be a graph on $n$ vertices with adjacency matrix $A=A(G)$. The _walk-
matrix_ of $G$ is defined as

$W(G)=[e,Ae,\ldots,A^{n-1}e],$

where $e$ is the all-one vector. Wang [20, 21] proved the following theorem.

######  Theorem 1.1 ([20, 21]).

If $2^{-\lfloor\frac{n}{2}\rfloor}\det(W)$ is odd and square-free, then $G$ is
DGS.

The problem of spectral determination of ordinary graphs naturally extends to
signed graphs. This paper is a continuation along this line of research for
signed graphs in the flavour of Theorem 1.1.

Let $\Delta(T)$ be the discriminant of a tree $T$ (see Section 4 for the
definition). The main result of the paper is the following theorem.

######  Theorem 1.2.

Let $T$ be a tree on $n$ vertices with an irreducible characteristic
polynomial over $\mathbb{Q}$. If $2^{-\frac{n}{2}}\sqrt{\Delta(T)}$ (which is
always an integer) is odd and square free, then every signed tree with
underlying graph $T$ is DGS.

As an immediately consequence of Theorem 1.2, we have

######  Corollary 1.3.

Let $T$ and $T^{\prime}$ be two cospectral and non-isomorphic trees with a
common irreducible characteristic polynomial. Suppose
$2^{-\frac{n}{2}}\sqrt{\Delta(T)}$ is odd and square free. Then no two signed
trees with underlying graphs $T$ and $T^{\prime}$ respectively are generalized
cospectral.

######  Example 1.

Let $T$ and $T^{\prime}$ be two cospectral non-isomorphic trees on 14 vertices
(see Fig. 1) with a common irreducible characteristic polynomial

$\phi(T)=\phi(T^{\prime})=-1+16x^{2}-79x^{4}+157x^{6}-143x^{8}+63x^{10}-13x^{12}+x^{14}.$

It can be easily computed that
$2^{-7}\sqrt{\Delta(T)}=2^{-7}\sqrt{\Delta(T^{\prime})}=5\times 11\times
4754599$, which is odd and square-free. Thus, according to Theorem 1.2, every
signed tree with underlying graph $T$ (resp. $T^{\prime}$) are DGS. In
particular, no two signed trees with underlying graphs $T$ and $T^{\prime}$
respectively are generalized cospectral.

Figure 1: A pair of cospectral non-isomorphic trees on 14 vertices

Theorem 1.2 shows that whenever the underlying tree $T$ with $n$ vertices
satisfies a simple arithmetic condition, then all the $2^{n-1}$ signed trees
(including $T$ itself) whose underlying is $T$ is DGS. That is, the DGS
property of all these signed trees only depends on the underlying graph $T$.
This is somewhat unexpected, since given a pair of trees $T$ and $T^{\prime}$,
it seems time consuming even to check whether there exist two signed trees
with underlying graphs $T$ and $T^{\prime}$ respectively that are generalized
cospectral; see Example 1.

We mention that Theorem 1.2 is the best possible in the sense that it is no
longer true if $2^{-\frac{n}{2}}\sqrt{\Delta(T)}$ has a multiple odd prime
factor. Moreover, the irreducibility assumption of the characteristic
polynomial of the tree is essential which cannot be removed; see Remarks 1 and
2 in Section 4.

The rest of the paper is organized as follows. In Section 2, we give some
preliminary results that will be needed in the proof of Theorem 1.2. In
Section 3, we give a structure theorem, which plays a key role in the paper.
In Section 4, we present the proof of Theorem 1.2. Conclusions and future work
are given in Section 5.

##  2 Preliminaries

For the convenience of the reader, we give some preliminary results that will
be needed later in the paper. For more results in spectral graphs theory, we
refer to [4, 6]

Let $G=(V,E)$ be a simple graph. A _signed graph_ is a graph obtained from $G$
by assigning a sign $1$ or $-1$ to every edge according to a mapping
$\sigma:E\rightarrow\\{1,-1\\}$. We use $\Gamma=(G,\sigma)$ to denote a signed
graph with _underlying graph_ $G$ and sign function (signature) $\sigma$. We
call a signed graph a _signed bipartite graph_ , if its underlying graph is
bipartite.

Let $U$ be a subset of $V$ such that $(U,V\setminus U)$ is a partition of $V$.
A _switching_ w.r.t. $U$ (or $V\setminus U$) is an operation that changes all
the signs of edges between $U$ and $V\setminus U$, while keeps the others
unchanged. Two signed graphs $\Gamma$ and $\Gamma^{\prime}$ are _switching-
equivalent_ if $\Gamma^{\prime}$ can be obtained from $\Gamma$ by a switching
operation, or equivalently, there exists a diagonal matrix $D$ with all
diagonal entry $\pm 1$ such that $DA(\Gamma)D=A(\Gamma^{\prime})$. A signed
graph is _balanced_ if every cycle contains an even number of edges with sign
-1. It is well-known that a signed graph is balanced if and only it is
switching equivalent to a unsigned graph.

Let $\Gamma$ be a signed graph with adjacency matrix $A(\Gamma)$. The
_characteristic polynomial_ of $\Gamma$ is defined as the characteristic
polynomial of $A(\Gamma)$, i.e., $\phi(\Gamma;x)=\det(xI-A(\Gamma))$, where
$I$ is the identity matrix. Two signed graphs $\Gamma$ and $\Gamma^{\prime}$
with adjacency matrices $A(\Gamma)$ and $A(\Gamma^{\prime})$ respectively are
called _generalized cospectral_ if

$\det(xI-A(\Gamma))=\det(xI-A(\Gamma^{\prime}))~{}{\rm
and}~{}\det(xI-(J-I-A(\Gamma)))=\det(xI-(J-I-A(\Gamma^{\prime}))),$

where $J$ is the all-one matrix and $J-I-A(\Gamma)$ formally denotes the
complement of $\Gamma$ (it is indeed the complement of $\Gamma$ if every edge
of $\Gamma$ has been assigned a positive sign +1). A signed graph $\Gamma$ is
said to be _determined by the generalized spectrum_ (DGS for short), if any
signed graph that is generalized cospectral with $\Gamma$ is isomorphic to
$\Gamma$.

A polynomial $f(x)\in{\mathbb{Q}[x]}$ is _irreducible_ if it cannot be
factored into two polynomials with rational coefficients of lower degree. Let
$f(x)\in{\mathbb{Q}[x]}$ be an irreducible polynomial with degree $n$ and
$\alpha$ be one of its root. Then
$\mathbb{Q}(\alpha)=\\{c_{0}+c_{1}\alpha+\cdots+c_{n-1}\alpha^{n-1}:c_{i}\in{\mathbb{Q}},~{}0\leq
i\leq n-1\\}$ is a _number field_ which is isomorphic to
$\mathbb{Q}[x]/(f(x))$ and is obtained by adding $\alpha$ to $\mathbb{Q}$; see
e.g. [9].

An orthogonal matrix $Q$ is a square matrix such that $Q^{\textup{T}}Q=I_{n}$.
It is called _rational_ if every entry of $Q$ is a rational number, and
_regular_ if each row sum of $Q$ is $1$, i.e., $Qe=e$, where $e$ is the all-
one column vector. Denote by RO${}_{n}(\mathbb{Q})$ the set of all $n$ by $n$
regular orthogonal matrices with rational entries.

In 2006, Wang and Xu [19] initiated the study of the generalized spectral
characterization of graphs. For two generalized cospectral graphs $G$ and $H$,
they obtained the following result (see also [5]), which plays a fundamental
role in their method.

######  Theorem 2.1 ([5],[19]).

Let $G$ be a graph. Then there exists a graph $H$ such that $G$ and $H$ are
generalized cospectral if and only if there exists a regular orthogonal matrix
$Q$ such that

$Q^{\textup{T}}A(G)Q=A(H).$ (1)

Moreover, if $\det W(G)\neq 0$, then $Q\in\textup{RO}_{n}(\mathbb{Q})$ is
unique and $Q=W(G)W^{-1}(H)$.

A graph $G$ with $\det W(G)\neq 0$ is called _controllable_ (see [14]),
denoted by $\mathcal{G}_{n}$ the set of all controllable graphs on $n$
vertices. For a graph $G\in\mathcal{G}_{n}$, define

$\mathcal{Q}(G):=\\{Q\in\textup{RO}_{n}(\mathbb{Q}):~{}Q^{\textup{T}}A(G)Q=A(H)~{}{\rm
for~{}some~{}graph}~{}H\\}.$

Then according to Theorem 2.1, it is easy to obtain the following

######  Theorem 2.2 ([19]).

Let $G$ be a controllable graph. Then $G$ is DGS if and only if the set
$\mathcal{Q}(G)$ contains only permutation matrices.

The above theorems extend naturally to signed graphs. By Theorem 2.2, finding
out the possible structure of all $Q\in\mathcal{Q}(G)$ is a key to determine
whether a (signed) graph $G$ is DGS.

Notations: We use $e_{n}$ (or $e$ if there is no confusion arises) to denote
an $n$-dimensional column all-one vector, and $J$ the all-one matrix. For a
vector $\alpha=(a_{1},a_{2},\ldots,a_{n})^{\textup{T}}\in{\mathbb{R}^{n}}$, we
use $||\alpha||_{2}=(a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2})^{1/2}$ to denote
the Euclidean norm of $\alpha$.

##  3 A structure theorem for $Q$

The key observation of this paper is the following theorem which shows that
for two generalized cospectral signed bipartite graphs with a common
irreducible characteristic polynomial, the regular rational orthogonal matrix
carried out the similarity of their adjacency matrices has a special
structure.

######  Theorem 3.1.

Let $\Gamma$ and $\tilde{\Gamma}$ be two generalized cospectral signed
bipartite graphs with a common irreducible characteristic polynomial $\phi(x)$
over $\mathbb{Q}$. Suppose that the adjacency matrices of $\Gamma$ and
$\tilde{\Gamma}$ are given as follows, respectively:

$A=A(\Gamma)=\left[\begin{matrix}O&M\\\ M^{\rm
T}&O\end{matrix}\right],~{}\tilde{A}=A(\tilde{\Gamma})=\left[\begin{matrix}O&\tilde{M}\\\
\tilde{M}^{\rm T}&O\end{matrix}\right].$

Then there exists a regular orthogonal matrix $Q$ such that $Q^{\rm
T}AQ=\tilde{A}$, where

$Q=\left[\begin{matrix}Q_{1}&O\\\ O&Q_{2}\end{matrix}\right]~{}{\rm
or}~{}Q=\left[\begin{matrix}O&Q_{1}\\\ Q_{2}&O\end{matrix}\right]$

with $Q_{1}$ and $Q_{2}$ being regular rational orthogonal matrices,
respectively.

######  Corollary 3.2.

The matrix $Q$ in Theorem 3.1 is the unique rational orthogonal matrix such
that $Q^{\textup{T}}AQ=\tilde{A}$.

###### Proof.

The irreducibility assumption of the characteristic polynomial of $A$ implies
that $\Gamma$ is controllable. Then the corollary follows immediately from
Theorem 2.1.

∎

To give the proof of Theorem 3.1, we need several lemmas below.

######  Lemma 3.3.

Let $\Gamma$ and $\tilde{\Gamma}$ be two generalized cospectral signed graphs
with adjacency matrices $A$ and $\tilde{A}$, respectively. Then $e^{\rm
T}(\lambda I-A)^{-1}e=e^{\rm T}(\lambda I-\tilde{A})^{-1}e$.

###### Proof.

It can be easily computed that

$\displaystyle\det(\lambda I-(A+tJ))$ $\displaystyle=$
$\displaystyle\det(\lambda I-A)\det(I-t(\lambda I-A)^{-1}ee^{\rm T})$
$\displaystyle=$ $\displaystyle\det(\lambda I-A)(1-te^{\rm T}(\lambda
I-A)^{-1}e).$

Similarly, $\det(\lambda I-(\tilde{A}+tJ))=\det(\lambda I-\tilde{A})(1-te^{\rm
T}(\lambda I-\tilde{A})^{-1}e)$. Thus, the lemma follows.

∎

######  Lemma 3.4 ([15]).

$(\lambda I-A)^{-1}=\sum_{i=1}^{n}\frac{\xi_{i}\xi_{i}^{\rm
T}}{\lambda-\lambda_{i}}$, where $\xi_{i}$’s are normalized eigenvectors of
$A$ associated with $\lambda_{i}$, for $\leq i\leq n$.

######  Lemma 3.5 ([18]).

Let $A=(a_{ij})$ be a symmetric integral matrix with an irreducible
characteristic polynomial $\phi(x)$. Let $\lambda_{1},\ldots,\lambda_{n}$ be
the distinct eigenvalues of $A$. Then there exist polynomials
$\phi_{i}(x)\in{\mathbb{Q}[x]}$ with $\deg\phi_{i}<n$ such that the
eigenvectors $\xi_{i}$ of $A$ associated with $\lambda_{i}$ can be expressed
as

${\xi}_{i}=(\phi_{1}(\lambda_{i}),\phi_{2}(\lambda_{i}),\ldots,\phi_{n}(\lambda_{i}))^{\rm
T}$

for $1\leq i\leq n$.

###### Proof.

Let $\lambda_{1}$ be an eigenvalue of $A$ with corresponding eigenvector
$\xi_{1}$. Consider the linear system of equations
$(\lambda_{1}I-A)\xi_{1}=0$. By Gaussian elimination, there exist
$x_{i}\in{\mathbb{Q}(\lambda_{1})}$ such that
$\xi_{1}=(x_{1},x_{2},\ldots,x_{n})^{\textup{T}}$. Note
$\mathbb{Q}(\lambda_{1})$ is a number field. There exist polynomials
$\phi_{i}(x)\in{\mathbb{Q}[x]}$ with $\deg\phi_{i}<n$ such that
$x_{i}=\phi_{i}(\lambda_{1})$.

By the $k$-th equation of $(\lambda_{1}I-A)\xi_{1}=0$, we have
$\psi(\lambda_{1}):=\sum_{j=1}^{n}a_{k,j}\phi_{j}(\lambda_{1})-\lambda_{1}\phi_{j}(\lambda_{1})=0$,
for $1\leq k\leq n$. Note $\psi(x)\in{\mathbb{Q}[x]}$ and
$\psi(\lambda_{1})=0$. By the irreducibility of $\phi(x)$, we have $\phi(x)$
divides $\psi(x)$. Thus, $\psi(\lambda_{i})=0$ for for $1\leq i\leq n$, and
${\xi}_{i}=(\phi_{1}(\lambda_{i}),\phi_{2}(\lambda_{i}),\ldots,\phi_{n}(\lambda_{i}))^{\rm
T}$ is an eigenvector associated with $\lambda_{i}$.

∎

Next, we collect some simple facts about the relationships of
eigenvalues/eigenvectors between the adjacency matrix $A$ of a signed
bipartite graph $\Gamma$ and its bipartite-adjacency matrix $M$.

######  Lemma 3.6.

Let $\Gamma$ be a signed bipartite graph with an irreducible characteristic
polynomial over $\mathbb{Q}$. Let the adjacency matrix of $\Gamma$ be
$A=A(\Gamma)=\left[\begin{matrix}O&M\\\ M^{\textup{T}}&O\end{matrix}\right]$.
Suppose that $\left[\begin{matrix}u\\\ v\end{matrix}\right]$ is an eigenvector
of $A$ associated with an eigenvalue $\lambda$. Then

  1. 1.

$\lambda^{2}$ is an eigenvalue of $MM^{\textup{T}}$ and $M^{\textup{T}}M$ with
corresponding eigenvectors $u$ and $v$, respectively;

  2. 2.

$u$ and $v$ have the same length, i.e., $||u||_{2}=||v||_{2}$;

  3. 3.

$\left[\begin{matrix}u\\\ -v\end{matrix}\right]$ (resp.
$\left[\begin{matrix}-u\\\ v\end{matrix}\right]$) is an eigenvector of $A$
associated with eigenvalue $-\lambda$;

  4. 4.

The characteristic polynomials of $MM^{\textup{T}}$ (resp. $M^{\textup{T}}M$)
is irreducible over $\mathbb{Q}$.

###### Proof.

Note that the characteristic polynomial $\phi(x)$ of $A$ is irreducible, it
follows that zero can never be an eigenvalue of $A$, and hence $M$ must be a
square matrix of order $m:=n/2$.

Let $\lambda\neq 0$ be any eigenvalue of $A$ with corresponding eigenvector
$\left[\begin{matrix}u\\\ v\end{matrix}\right]$. Then

$A\left[\begin{matrix}u\\\ v\end{matrix}\right]=\left[\begin{matrix}Mv\\\
M^{\textup{T}}u\end{matrix}\right]=\lambda\left[\begin{matrix}u\\\
v\end{matrix}\right]\Longleftrightarrow\left\\{\begin{aligned} Mv=\lambda
u,\\\ M^{\textup{T}}u=\lambda v.\end{aligned}\right.$ (2)

Thus, we have $u\neq 0$ and $v\neq 0$, for otherwise we would have $u=v=0$,
since $\lambda\neq 0$. It follows that

$MM^{\textup{T}}u=\lambda^{2}u,~{}M^{\textup{T}}Mv=\lambda^{2}v.$

It follows from $Mv=\lambda u$ that $u^{\textup{T}}Mv=\lambda
u^{\textup{T}}u$. By $M^{\textup{T}}u=\lambda v$ we get
$v^{\textup{T}}M^{\textup{T}}u=\lambda v^{\textup{T}}v$. Note
$u^{\textup{T}}Mv=(u^{\textup{T}}Mv)^{\textup{T}}=v^{\textup{T}}M^{\textup{T}}u$.
It follows that $\lambda u^{\textup{T}}u=\lambda v^{\textup{T}}v$, and hence
$u^{\textup{T}}u=v^{\textup{T}}v$ since $\lambda\neq 0$.

Note that

$A\left[\begin{matrix}u\\\ -v\end{matrix}\right]=\left[\begin{matrix}-Mv\\\
M^{\textup{T}}u\end{matrix}\right]=-\lambda\left[\begin{matrix}u\\\
-v\end{matrix}\right].$

Hence, $\left[\begin{matrix}u\\\ -v\end{matrix}\right]$ is an eigenvector of
$A$ associated with eigenvalue $-\lambda$. Since the characteristic polynomial
of $A$ is irreducible, the set of all the eigenvalues of $A$ can be written as
$\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{m},-\lambda_{1},-\lambda_{2},\ldots,\lambda_{m}\\}.$

Hence, the set of all the eigenvalues of $MM^{\textup{T}}$ (or
$M^{\textup{T}}M$) can be write as
$\\{\lambda_{1}^{2},\lambda_{2}^{2},\ldots,\lambda_{m}^{2}\\}$. Since
$\phi(A;x)=(x^{2}-\lambda_{1}^{2})\cdots(x^{2}-\lambda_{m}^{2})$ is
irreducible over $\mathbb{Q}$,
$\phi(MM^{\textup{T}};x)=\phi(M^{\textup{T}}M;x)=(x-\lambda_{1}^{2})\cdots(x-\lambda_{m}^{2})$
is also irreducible $\mathbb{Q}$. ∎

Now, we present the proof of Theorem 3.1.

###### Proof of Theorem 3.1.

Set $m:=n/2$. By Lemma 3.6, let
$\lambda_{1},\lambda_{2},\ldots,\lambda_{m},-\lambda_{1},-\lambda_{2},\ldots,-\lambda_{m}$
be the eigenvalues of $A$ and $\tilde{A}$ with corresponding normalized
eigenvectors

$\displaystyle\frac{1}{\sqrt{2}}\left[\begin{matrix}u_{1}\\\
v_{1}\end{matrix}\right],\ldots,\frac{1}{\sqrt{2}}\left[\begin{matrix}u_{m}\\\
v_{m}\end{matrix}\right],\frac{1}{\sqrt{2}}\left[\begin{matrix}u_{1}\\\
-v_{1}\end{matrix}\right],\ldots,\frac{1}{\sqrt{2}}\left[\begin{matrix}u_{m}\\\
-v_{m}\end{matrix}\right],$ (3)
$\displaystyle\frac{1}{\sqrt{2}}\left[\begin{matrix}\tilde{u}_{1}\\\
\tilde{v}_{1}\end{matrix}\right],\ldots,\frac{1}{\sqrt{2}}\left[\begin{matrix}\tilde{u}_{m}\\\
\tilde{v}_{m}\end{matrix}\right],\frac{1}{\sqrt{2}}\left[\begin{matrix}\tilde{u}_{1}\\\
-\tilde{v}_{1}\end{matrix}\right],\ldots,\frac{1}{\sqrt{2}}\left[\begin{matrix}\tilde{u}_{m}\\\
-\tilde{v}_{m}\end{matrix}\right],$ (4)

respectively, where
$u_{i},\tilde{u}_{i},v_{i},\tilde{v}_{i}\in{\mathbb{R}^{n}}$ are
$m$-dimensional unit vectors.

By Lemma 3.3, we have
$e^{\textup{T}}(xI-A)^{-1}e=e^{\textup{T}}(xI-\tilde{A})^{-1}e$. It follows
from Lemma 3.4 that

$\sum_{i=1}^{m}\frac{(\frac{1}{\sqrt{2}}e_{2m}^{\textup{T}}\left[\begin{matrix}u_{i}\\\
v_{i}\end{matrix}\right])^{2}}{x-\lambda_{i}}+\sum_{i=1}^{m}\frac{(\frac{1}{\sqrt{2}}e_{2m}^{\textup{T}}\left[\begin{matrix}u_{i}\\\
-v_{i}\end{matrix}\right])^{2}}{x+\lambda_{i}}=\sum_{i=1}^{m}\frac{(\frac{1}{\sqrt{2}}e_{2m}^{\textup{T}}\left[\begin{matrix}\tilde{u}_{i}\\\
\tilde{v}_{i}\end{matrix}\right])^{2}}{x-\lambda_{i}}+\sum_{i=1}^{m}\frac{(\frac{1}{\sqrt{2}}e_{2m}^{\textup{T}}\left[\begin{matrix}\tilde{u}_{i}\\\
-\tilde{v}_{i}\end{matrix}\right])^{2}}{x+\lambda_{i}}.$ (5)

Hence, we have that for each $1\leq i\leq m$,

$\displaystyle\left\\{\begin{aligned}
(e_{m}^{\textup{T}}u_{i}+e_{m}^{\textup{T}}v_{i})^{2}&=&(e_{m}^{\textup{T}}\tilde{u}_{i}+e_{m}^{\textup{T}}\tilde{v}_{i})^{2},\\\
(e_{m}^{\textup{T}}u_{i}-e_{m}^{\textup{T}}v_{i})^{2}&=&(e_{m}^{\textup{T}}\tilde{u}_{i}-e_{m}^{\textup{T}}\tilde{v}_{i})^{2}.\end{aligned}\right.$
(6)

For a fixed $i$, we distinguish the following two cases:

Case 1. $e_{m}^{\textup{T}}u_{i}+e_{m}^{\textup{T}}v_{i}$ and
$e_{m}^{\textup{T}}\tilde{u}_{i}+e_{m}^{\textup{T}}\tilde{v}_{i}$ have the
same sign (resp. opposite sign), and
$e_{m}^{\textup{T}}u_{i}-e_{m}^{\textup{T}}v_{i}$ and
$e_{m}^{\textup{T}}\tilde{u}_{i}-e_{m}^{\textup{T}}\tilde{v}_{i}$ have the
same sign (resp. opposite sign). It follows from (6) that

$\displaystyle\left\\{\begin{aligned}
e_{m}^{\textup{T}}u_{i}+e_{m}^{\textup{T}}v_{i}&=&e_{m}^{\textup{T}}\tilde{u}_{i}+e_{m}^{\textup{T}}\tilde{v}_{i},\\\
e_{m}^{\textup{T}}u_{i}-e_{m}^{\textup{T}}v_{i}&=&e_{m}^{\textup{T}}\tilde{u}_{i}-e_{m}^{\textup{T}}\tilde{v}_{i},\end{aligned}\right.~{}{\rm
or}~{}\left\\{\begin{aligned}
e_{m}^{\textup{T}}u_{i}+e_{m}^{\textup{T}}v_{i}&=&-(e_{m}^{\textup{T}}\tilde{u}_{i}+e_{m}^{\textup{T}}\tilde{v}_{i}),\\\
e_{m}^{\textup{T}}u_{i}-e_{m}^{\textup{T}}v_{i}&=&-(e_{m}^{\textup{T}}\tilde{u}_{i}-e_{m}^{\textup{T}}\tilde{v}_{i}),\end{aligned}\right.$

which implies that either i)
$e_{m}^{\textup{T}}u_{i}=e_{m}^{\textup{T}}\tilde{u}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=e_{m}^{\textup{T}}\tilde{v}_{i}$; or ii)
$e_{m}^{\textup{T}}u_{i}=-e_{m}^{\textup{T}}\tilde{u}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=-e_{m}^{\textup{T}}\tilde{v}_{i}$.

Case 2. $e_{m}^{\textup{T}}u_{i}+e_{m}^{\textup{T}}v_{i}$ and
$e_{m}^{\textup{T}}\tilde{u}_{i}+e_{m}^{\textup{T}}\tilde{v}_{i}$ have the
same sign (resp. opposite sign), and
$e_{m}^{\textup{T}}u_{i}-e_{m}^{\textup{T}}v_{i}$ and
$e_{m}^{\textup{T}}\tilde{u}_{i}-e_{m}^{\textup{T}}\tilde{v}_{i}$ have the
opposite sign (resp. same sign). Then

$\displaystyle\left\\{\begin{aligned}
e_{m}^{\textup{T}}u_{i}+e_{m}^{\textup{T}}v_{i}&=&e_{m}^{\textup{T}}\tilde{u}_{i}+e_{m}^{\textup{T}}\tilde{v}_{i},\\\
e_{m}^{\textup{T}}u_{i}-e_{m}^{\textup{T}}v_{i}&=&-(e_{m}^{\textup{T}}\tilde{u}_{i}-e_{m}^{\textup{T}}\tilde{v}_{i}),\end{aligned}\right.~{}{\rm
or}~{}\left\\{\begin{aligned}
e_{m}^{\textup{T}}u_{i}+e_{m}^{\textup{T}}v_{i}&=&-(e_{m}^{\textup{T}}\tilde{u}_{i}+e_{m}^{\textup{T}}\tilde{v}_{i}),\\\
e_{m}^{\textup{T}}u_{i}-e_{m}^{\textup{T}}v_{i}&=&e_{m}^{\textup{T}}\tilde{u}_{i}-e_{m}^{\textup{T}}\tilde{v}_{i},\end{aligned}\right.$

which implies that either i)
$e_{m}^{\textup{T}}u_{i}=e_{m}^{\textup{T}}\tilde{v}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=e_{m}^{\textup{T}}\tilde{u}_{i}$; or ii)
$e_{m}^{\textup{T}}u_{i}=-e_{m}^{\textup{T}}\tilde{v}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=-e_{m}^{\textup{T}}\tilde{u}_{i}$.

Thus, for a fixed $i$, we may assume that either
$e_{m}^{\textup{T}}u_{i}=\tau_{i}e_{m}^{\textup{T}}\tilde{u}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=\tau_{i}e_{m}^{\textup{T}}\tilde{v}_{i}$ or
$e_{m}^{\textup{T}}u_{i}=\sigma_{i}e_{m}^{\textup{T}}\tilde{v}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=\sigma_{i}e_{m}^{\textup{T}}\tilde{u}_{i}$, where
$\tau_{i},\sigma_{i}\in\\{1,-1\\}$. Next, we show that uniformly, either
$e_{m}^{\textup{T}}u_{i}=\tau_{i}e_{m}^{\textup{T}}\tilde{u}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=\tau_{i}e_{m}^{\textup{T}}\tilde{v}_{i}$ for all
$1\leq i\leq m$ or
$e_{m}^{\textup{T}}u_{i}=\sigma_{i}e_{m}^{\textup{T}}\tilde{v}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=\sigma_{i}e_{m}^{\textup{T}}\tilde{u}_{i}$ for all
$1\leq i\leq m$. This is the key technical part of the proof, which highly
depends on the irreducibility assumption of $\phi$.

According to Lemma 3.5, the eigenvectors of $MM^{\textup{T}}$ associated with
eigenvalues $\lambda_{i}^{2}$ can be expressed as
$\xi_{i}=(\phi_{1}(\lambda_{i}),\phi_{2}(\lambda_{i}),\ldots,\phi_{m}(\lambda_{i}))^{\textup{T}}$,
where $\phi_{j}(x)\in{\mathbb{Q}[x]}$ with $\deg\phi_{j}<n$.

By Lemma 3.6, $u_{i}$ is an eigenvector of $MM^{\textup{T}}$ associated with
$\lambda_{i}^{2}$. Note $u_{i}$ is a unit vector. It follows that $u_{i}$ and
$\xi_{i}/||\xi_{i}||_{2}$ differ by at most a sign, i.e., there exists a
$\epsilon_{i}\in\\{1,-1\\}$ such that
$u_{i}=\epsilon_{i}\frac{\xi_{i}}{||\xi_{i}||_{2}}$, and

$\displaystyle v_{i}$ $\displaystyle=$
$\displaystyle\frac{1}{\lambda_{i}}M^{\textup{T}}u_{i}$ $\displaystyle=$
$\displaystyle\frac{\epsilon_{i}}{\lambda_{i}}M^{\textup{T}}(\phi_{1}(\lambda_{i}),\phi_{2}(\lambda_{i}),\ldots,\phi_{m}(\lambda_{i}))^{\textup{T}}/||\xi_{i}||_{2}$
$\displaystyle=$
$\displaystyle\epsilon_{i}(\varphi_{1}(\lambda_{i}),\varphi_{2}(\lambda_{i}),\ldots,\varphi_{m}(\lambda_{i}))^{\textup{T}}/||\xi_{i}||_{2},$

for some $\varphi_{j}(x)\in{\mathbb{Q}[x]}$ with degree less than $n$, for
$1\leq j\leq m$. The last equality follows since the entries of the vector
$\frac{1}{\lambda_{i}}M^{\textup{T}}(\phi_{1}(\lambda_{i}),\phi_{2}(\lambda_{i}),\ldots,\phi_{m}(\lambda_{i}))^{\textup{T}}$
belong to $\mathbb{Q}(\lambda_{i})$, which is a number field. Further note
that $||u_{i}||_{2}=||v_{i}||_{2}=1$, we have
$\varphi_{1}(\lambda_{i})^{2}+\varphi_{2}(\lambda_{i})^{2}+\cdots+\varphi_{m}(\lambda_{i})^{2}=||\xi_{i}||^{2},$
for $1\leq i\leq m$.

The above discussions apply similarly to the signed bipartite graph
$\tilde{\Gamma}$ with adjacency matrix $\tilde{A}$. Then we have
$\tilde{u}_{i}=\tilde{\epsilon_{i}}\frac{\tilde{\xi}_{i}}{||\tilde{\xi}_{i}||_{2}}$
for $\tilde{\epsilon_{i}}\in\\{1,-1\\}$, where
$\tilde{\xi}_{i}=(\tilde{\phi_{1}}(\lambda_{i}),\tilde{\phi}_{2}(\lambda_{i}),\ldots,\tilde{\phi}_{m}(\lambda_{i}))^{\textup{T}}$,
$\tilde{\phi}_{j}(x)\in{\mathbb{Q}[x]}$ with $\deg\tilde{\phi}_{j}<n$.
Moreover,
$\tilde{v}_{i}=\tilde{\epsilon}_{i}(\tilde{\varphi}_{1}(\lambda_{i}),\tilde{\varphi}_{2}(\lambda_{i}),\ldots,\tilde{\varphi}_{m}(\lambda_{i}))^{\textup{T}}/||\tilde{\xi}_{i}||_{2}$
with $\tilde{\varphi}_{j}(x)\in{\mathbb{Q}[x]}$ with degree less than $n$, and
$\tilde{\varphi}_{1}(\lambda_{i})^{2}+\tilde{\varphi}_{2}(\lambda_{i})^{2}+\cdots+\tilde{\varphi}_{m}(\lambda_{i})^{2}=||\tilde{\xi}_{i}||^{2}$.

######  Claim 1.

If $e_{m}^{\textup{T}}u_{1}=\tau_{1}e_{m}^{\textup{T}}\tilde{u}_{1}$ and
$e_{m}^{\textup{T}}v_{1}=\tau_{1}e_{m}^{\textup{T}}\tilde{v}_{1}$ with
$\tau_{1}\in\\{1,-1\\}$, then
$e_{m}^{\textup{T}}u_{i}=\tau_{i}e_{m}^{\textup{T}}\tilde{u}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=\tau_{i}e_{m}^{\textup{T}}\tilde{v}_{i}$ for some
$\tau_{i}\in\\{1,-1\\}$, for all $2\leq i\leq m$.

###### Proof.

Actually, it follows from
$e_{m}^{\textup{T}}u_{1}=\tau_{1}e_{m}^{\textup{T}}\tilde{u}_{1}$ that

$\epsilon_{1}\frac{\sum_{j=1}^{m}\phi_{j}(\lambda_{1})}{\sqrt{\sum_{j=1}^{m}\phi_{j}^{2}(\lambda_{1})}}=\tau_{1}\tilde{\epsilon_{1}}\frac{\sum_{j=1}^{m}\tilde{\phi}_{j}(\lambda_{1})}{\sqrt{\sum_{j=1}^{m}\tilde{\phi}_{j}^{2}(\lambda_{1})}}.$
(7)

Taking squares on both sides of (7), it follows that

$\Phi(\lambda_{1}):=(\sum_{j=1}^{m}\phi_{j}(\lambda_{1}))^{2}\sum_{j=1}^{m}\tilde{\phi}_{j}^{2}(\lambda_{1})-(\sum_{j=1}^{m}\tilde{\phi}_{j}(\lambda_{1}))^{2}\sum_{j=1}^{m}\phi_{j}^{2}(\lambda_{1})=0.$

Note that $\phi(x)$ is irreducible and $\Phi(x)\in{\mathbb{Q}[x]}$. It follows
that $\phi(x)\mid\Phi(x)$. Hence $\Phi(\lambda_{i})=0$ and
$e_{m}^{\textup{T}}u_{i}=\tau_{i}e_{m}^{\textup{T}}\tilde{u}_{i}$ for some
$\tau_{i}\in\\{1,-1\\}$, for $2\leq i\leq m$. Similarly, we have
$e_{m}^{\textup{T}}v_{i}=\tilde{\tau}_{i}e_{m}^{\textup{T}}\tilde{v}_{i}$ for
some $\tilde{\tau}_{i}\in\\{1,-1\\}$, for $2\leq i\leq m$. Next, we show that
$\tau_{i}$ and $\tilde{\tau}_{i}$ coincide, i.e.,
$\tau_{i}=\tilde{\tau}_{i}=\pm 1$, for all $2\leq i\leq m$.

In fact, it follows from
$e_{m}^{\textup{T}}v_{1}=\tau_{1}e_{m}^{\textup{T}}\tilde{v}_{1}$ that

$\epsilon_{1}\frac{\sum_{j=1}^{m}\varphi_{j}(\lambda_{1})}{\sqrt{\sum_{j=1}^{m}\phi_{j}^{2}(\lambda_{1})}}=\tau_{1}\tilde{\epsilon_{1}}\frac{\sum_{j=1}^{m}\tilde{\varphi}_{j}(\lambda_{1})}{\sqrt{\sum_{j=1}^{m}\tilde{\phi}_{j}^{2}(\lambda_{1})}}.$
(8)

It is easy to see that all the numerators in Eqs. (7) and (8) are non-zero.
For example, if $\sum_{j=1}^{m}\phi_{j}(\lambda_{1})=0$, then
$\sum_{j=1}^{m}\phi_{j}(\lambda_{i})=0$ for $1\leq i\leq m$ by the
irreducibility of $\phi$. That is, $e_{m}^{\textup{T}}\xi_{i}=0$ for $1\leq
i\leq m$, which is ridiculous since $\xi_{i}$ ($1\leq i\leq m$) are
eigenvectors of $MM^{\textup{T}}$ constituting a basis of $\mathbb{R}^{m}$.

Eq. (8) divides Eq. (7), it follows that

$\frac{\sum_{j=1}^{m}\phi_{j}(\lambda_{1})}{\sum_{j=1}^{m}\varphi_{j}(\lambda_{1})}=\frac{\sum_{j=1}^{m}\tilde{\phi}_{j}(\lambda_{1})}{\sum_{j=1}^{m}\tilde{\varphi}_{j}(\lambda_{1})},$
(9)

or equivalently,
$\Psi(\lambda_{1}):=\sum_{j=1}^{m}\phi_{j}(\lambda_{1})\sum_{j=1}^{m}\tilde{\varphi}_{j}(\lambda_{1})-\sum_{j=1}^{m}\varphi_{j}(\lambda_{1})\sum_{j=1}^{m}\tilde{\phi}_{j}(\lambda_{1})=0$.
By the irreducibility of $\phi(x)$, we obtain that $\phi(x)\mid\Psi(x)$, and
hence $\Psi(\lambda_{i})=0$ for $2\leq i\leq m$. So Eq. (9) still holds if we
replace $\lambda_{1}$ with any $\lambda_{i}$, i.e.,

$\frac{\sum_{j=1}^{m}\phi_{j}(\lambda_{i})}{\sum_{j=1}^{m}\varphi_{j}(\lambda_{i})}=\frac{\sum_{j=1}^{m}\tilde{\phi}_{j}(\lambda_{i})}{\sum_{j=1}^{m}\tilde{\varphi}_{j}(\lambda_{i})},~{}{\rm
for}~{}2\leq i\leq m.$ (10)

By the previous discussions, we get that

$\epsilon_{i}\frac{\sum_{j=1}^{m}\phi_{j}(\lambda_{i})}{\sqrt{\sum_{j=1}^{m}\phi_{j}^{2}(\lambda_{i})}}=\tau_{i}\tilde{\epsilon_{i}}\frac{\sum_{j=1}^{m}\tilde{\phi}_{j}(\lambda_{i})}{\sqrt{\sum_{j=1}^{m}\tilde{\phi}_{j}^{2}(\lambda_{i})}},~{}{\rm
for}~{}{\rm for}~{}2\leq i\leq m.$ (11)
$\epsilon_{i}\frac{\sum_{j=1}^{m}\varphi_{j}(\lambda_{i})}{\sqrt{\sum_{j=1}^{m}\phi_{j}^{2}(\lambda_{i})}}=\tilde{\tau}_{i}\tilde{\epsilon_{i}}\frac{\sum_{j=1}^{m}\tilde{\varphi}_{j}(\lambda_{i})}{\sqrt{\sum_{j=1}^{m}\tilde{\phi}_{j}^{2}(\lambda_{i})}},~{}{\rm
for}~{}2\leq i\leq m.$ (12)

Eq. (12) divides Eq. (11), we obtain
$\frac{\sum_{j=1}^{m}\phi_{j}(\lambda_{i})}{\sum_{j=1}^{m}\varphi_{j}(\lambda_{i})}=\frac{\tau_{i}}{\tilde{\tau}_{i}}\frac{\sum_{j=1}^{m}\tilde{\phi}_{j}(\lambda_{i})}{\sum_{j=1}^{m}\tilde{\varphi}_{j}(\lambda_{i})},$
together with Eq. (10), we get the conclusion that
$\tau_{i}=\tilde{\tau}_{i}=\pm 1$ for $2\leq i\leq m$. ∎

######  Claim 2.

: If $e_{m}^{\textup{T}}u_{1}=\sigma_{1}e_{m}^{\textup{T}}\tilde{v}_{1}$ and
$e_{m}^{\textup{T}}v_{1}=\sigma_{1}e_{m}^{\textup{T}}\tilde{u}_{1}$ with
$\sigma_{1}\in\\{1,-1\\}$, then
$e_{m}^{\textup{T}}u_{i}=\sigma_{i}e_{m}^{\textup{T}}\tilde{v}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=\sigma_{i}e_{m}^{\textup{T}}\tilde{u}_{i}$ for some
$\sigma_{i}\in\\{1,-1\\}$, for all $2\leq i\leq m$.

###### Proof.

This follows by using the same argument as Claim 1; we omit the details here.
∎

Write

$U=[u_{1},u_{2},\ldots,u_{m}],~{}V=[v_{1},v_{2},\ldots,v_{m}],$
$\tilde{U}=[\tilde{u}_{1},\tilde{u}_{2},\ldots,\tilde{u}_{m}],~{}\tilde{V}=[\tilde{v}_{1},\tilde{v}_{2},\ldots,\tilde{v}_{m}].$

If the condition of Claim 1 holds, we may replace $u_{i}$ and $v_{i}$ with
$-u_{i}$ and $-v_{i}$ respectively, whenever $\tau_{i}=-1$ for $1\leq i\leq
m$. Then we have $e_{m}^{\textup{T}}u_{i}=e_{m}^{\textup{T}}\tilde{u}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=e_{m}^{\textup{T}}\tilde{v}_{i}$ for $1\leq i\leq m$.
Let $R=\frac{1}{\sqrt{2}}\left[\begin{matrix}U&U\\\ V&-V\end{matrix}\right]$
and $\tilde{R}=\frac{1}{\sqrt{2}}\left[\begin{matrix}\tilde{U}&\tilde{U}\\\
\tilde{V}&-\tilde{V}\end{matrix}\right].$ Define

$Q:=R\tilde{R}^{\textup{T}}=\left[\begin{matrix}U\tilde{U}^{\textup{T}}&O\\\
O&V\tilde{V}^{\textup{T}}\end{matrix}\right].$ (13)

Then $Q$ is an orthogonal matrix and

$R^{\textup{T}}AR=\tilde{R}^{\textup{T}}\tilde{A}\tilde{R}={\rm
diag}(\lambda_{1},\ldots,\lambda_{m},-\lambda_{1},\ldots,-\lambda_{m}).$

Thus, $Q^{\textup{T}}AQ=\tilde{A}$. Next, it remains to show that $Q$ is
regular, i.e., $Qe_{2m}=e_{2m}$, which is equivalent to
$\tilde{U}^{\textup{T}}e_{m}=U^{\textup{T}}e_{m}$ and
$\tilde{V}^{\textup{T}}e_{m}=V^{\textup{T}}e_{m}$. That is,
$e_{m}^{\textup{T}}u_{i}=e_{m}^{\textup{T}}\tilde{u}_{i},~{}e_{m}^{\textup{T}}v_{i}=e_{m}^{\textup{T}}\tilde{v}_{i},~{}{\rm
for}~{}1\leq i\leq m,$ which are precisely that we have obtained before, as
desired.

If the condition of Claim 2 holds, similarly, we may replace $u_{i}$ and
$v_{i}$ with $-u_{i}$ and $-v_{i}$ respectively, whenever $\sigma_{i}=-1$.
Then $e_{m}^{\textup{T}}u_{i}=e_{m}^{\textup{T}}\tilde{v}_{i}$ and
$e_{m}^{\textup{T}}v_{i}=e_{m}^{\textup{T}}\tilde{u}_{i}$, for $1\leq i\leq
m$. Now let $R=\frac{1}{\sqrt{2}}\left[\begin{matrix}U&U\\\
V&-V\end{matrix}\right]$ and
$\tilde{R}=\frac{1}{\sqrt{2}}\left[\begin{matrix}\tilde{U}&-\tilde{U}\\\
\tilde{V}&\tilde{V}\end{matrix}\right].$ Define

$Q:=R\tilde{R}^{\textup{T}}=\left[\begin{matrix}O&U\tilde{V}^{\textup{T}}\\\
V\tilde{U}^{\textup{T}}&O\end{matrix}\right].$ (14)

Then $Q$ is an orthogonal matrix and still $Q^{\textup{T}}AQ=\tilde{A}$ holds.
Moreover, it is easy to verify that $Qe_{2m}=e_{2m}$. So $Q$ is regular.

The proof is complete.

∎

##  4 Proof of Theorem 1.2

In this section, we present the proof of Theorem 1.2.

Recall that for a monic polynomial $f(x)\in{\mathbb{Z}[x]}$ with degree $n$,
the _discriminant_ of $f(x)$ is defined as:

$\Delta(f)=\prod_{1\leq i<j\leq n}(\alpha_{i}-\alpha_{j})^{2},$

where $\alpha_{1},\alpha_{2},\ldots,\alpha_{n}$ are all the roots of $f(x)$.

Then it is clear that $\Delta(f)$ is always an integer for
$f(x)\in{\mathbb{Z}[x]}$, and $\Delta(f)=0$ if and only if $f$ has a multiple
root. Define the _discriminant_ of a matrix $A$, denoted by $\Delta(A)$, as
the discriminant of its characteristic polynomial, i.e.,
$\Delta(A):=\Delta(\det(xI-A))$. The _discriminant_ of a graph $G$, denoted by
$\Delta(G)$, is defined to be the discriminant of its adjacency matrix.

In [22], Wang and Yu give the following theorem, which is our main tool in
proving Theorem 1.2.

######  Theorem 4.1 ([22]).

Let $A$ be a symmetric integral matrix. Suppose there exists a rational
orthogonal matrix $Q$ such that $Q^{\rm T}AQ$ is an integral matrix. If
$\Delta(A)$ is odd and square-free, then $Q$ must be a signed permutation
matrix.

However, Theorem 4.1 cannot be used directly, since the $\Delta(\Gamma)$ is
always a perfect square for a signed bipartite graph $\Gamma$ with an equal
size of bipartition, as shown by the following lemma.

######  Lemma 4.2.

Let $\Gamma$ be a signed bipartite graph with bipartite-adjacency matrix $M$,
where $M$ is a square matrix of order $m:=n/2$. Then
$\Delta(\Gamma)=2^{n}\det^{2}(M)\Delta^{2}(M^{\rm T}M)$.

###### Proof.

Let the eigenvalues of $\Gamma$ be
$\pm\lambda_{1},\pm\lambda_{2},\ldots,\pm\lambda_{m}.$ Then the eigenvalues of
$M^{\textup{T}}M$ are
$\lambda_{1}^{2},\lambda_{2}^{2},\ldots,\lambda_{m}^{2}.$ So we have

$\displaystyle\Delta(\Gamma)$ $\displaystyle=$ $\displaystyle\prod_{1\leq
i<j\leq m}(\lambda_{i}-\lambda_{j})^{2}\prod_{1\leq i,j\leq
m}(\lambda_{i}+\lambda_{j})^{2}\prod_{1\leq i<j\leq
m}(-\lambda_{i}+\lambda_{j})^{2}$ $\displaystyle=$ $\displaystyle
2^{n}\lambda_{1}^{2}\lambda_{2}^{2}\cdots\lambda_{m}^{2}\prod_{1\leq i<j\leq
m}(\lambda_{i}^{2}-\lambda_{j}^{2})^{4}$ $\displaystyle=$ $\displaystyle
2^{n}\det(M^{\textup{T}}M)\Delta^{2}(M^{\textup{T}}M)$ $\displaystyle=$
$\displaystyle 2^{n}(\det(M))^{2}\Delta^{2}(M^{\rm T}M).$

This completes the proof. ∎

Let $a_{0}$ be the constant term of the characteristic polynomial of $G$
defined as above. Then

$a_{0}=(-1)^{m}\det(M^{\textup{T}}M)=(-1)^{m}\det{{}^{2}}(M).$

Note that for a tree with an irreducible characteristic polynomial $\phi(x)$,
the constant term of $\phi(x)$ is always $\pm 1$. Thus we have

######  Corollary 4.3.

Let $T$ be a tree with an irreducible characteristic polynomial. Then
$\Delta(T)=2^{n}\Delta^{2}(M^{\rm T}M)$.

Finally, we are ready to present the proof of Theorem 1.2.

###### Proof of Theorem 1.2..

Let $\tilde{\Gamma}$ be any signed graph that is generalized cospectral with
$\Gamma=(T,\sigma)$. We shall show that $\tilde{\Gamma}$ is isomorphic to
$\Gamma$. Note that $\tilde{\Gamma}$ has the same number of edges as $\Gamma$
and moreover, the assumption that $\phi(\tilde{\Gamma})=\phi(\Gamma)$ is
irreducible forces $\tilde{\Gamma}$ to be connected. Thus, $\tilde{\Gamma}$ is
signed graph whose underlying graph is a tree (say $\tilde{T}$), and
$\tilde{\Gamma}=(\tilde{T},\tilde{\sigma})$.

Note that both $T$ and $\tilde{T}$ are balanced as signed graphs, we have
$\phi(T)=\phi(\Gamma)$ and $\phi(\tilde{T})=\phi(\tilde{\Gamma})$. Let
$A(\Gamma)=D_{1}A(T)D_{1}$ and $A(\tilde{\Gamma})=D_{2}A(\tilde{T})D_{2}$,
where $D_{1}$ and $D_{2}$ are diagonal matrices whose diagonal entries are
$\pm 1$.

By Theorem 2.1, the fact that $\Gamma$ and $\tilde{\Gamma}$ are generalized
cospectral implies that there exists a regular rational orthogonal matrix $Q$
such that

$Q^{\rm T}A(\Gamma)Q=A(\tilde{\Gamma}),$ (15)

i.e., $Q^{\rm T}(D_{1}A(T)D_{1})Q=D_{2}A(\tilde{T})D_{2}$, which is equivalent
to $\hat{Q}^{\rm T}A(T)\hat{Q}=A(\tilde{T}),$ where $\hat{Q}=D_{1}QD_{2}$ is a
rational orthogonal matrix.

Let

$A(T)=\left[\begin{matrix}O&M\\\ M^{\rm
T}&O\end{matrix}\right],A(\tilde{T})=\left[\begin{matrix}O&\tilde{M}\\\
\tilde{M}^{\rm T}&O\end{matrix}\right].$

By Theorem 3.1, assume without loss of generality that
$Q=\left[\begin{matrix}Q_{1}&O\\\ O&Q_{2}\end{matrix}\right]$ and
$\hat{Q}=\left[\begin{matrix}\hat{Q}_{1}&O\\\
O&\hat{Q}_{2}\end{matrix}\right].$ Then we have $\hat{Q}_{1}^{\rm
T}M\hat{Q}_{2}=\tilde{M}$. It follows that

$\hat{Q}_{1}^{\rm T}MM^{\rm T}\hat{Q}_{1}=\tilde{M}\tilde{M}^{\rm T}~{}{\rm
and}~{}\hat{Q}_{2}^{\rm T}M^{\rm T}M\hat{Q}_{2}=\tilde{M}^{\rm T}\tilde{M}.$

Note that $\Delta(M^{\rm T}M)=\Delta(MM^{\rm T})=2^{-n/2}\sqrt{\Delta(T)}$,
which is odd and square-free. Thus, according to Theorem 4.1, both
$\hat{Q}_{1}$ and $\hat{Q}_{2}$ are signed permutation matrices. It follows
that $Q=D_{1}\hat{Q}Q_{2}$ is a signed permutation matrix. Moreover, note that
$Q$ is regular. Therefore, $Q$ is a permutation matrix, and by Eq. (15), we
conclude that $\tilde{\Gamma}$ is isomorphic to $\Gamma$. The proof is
complete.

∎

######  Remark 1.

The condition of Theorem 1.2 is tight in the sense that Theorem 1.2 is no
longer true if $2^{-\frac{n}{2}}\sqrt{\Delta(T)}$ has a multiple odd prime
factor. Let the signed bipartite-adjacency matrices of two signed trees $T$
and $\tilde{T}$ be given as follows, respectively:

${\tiny M=\left(\begin{array}[]{ccccccccc}-1&0&0&0&0&0&0&0&0\\\
-1&-1&0&0&0&0&0&0&0\\\ 1&0&-1&0&0&0&0&0&0\\\ 0&0&1&-1&0&0&0&0&0\\\
0&-1&0&0&-1&1&0&0&0\\\ 0&0&0&0&-1&0&0&0&0\\\ 0&0&0&0&-1&0&-1&1&0\\\
0&0&0&0&0&0&-1&0&0\\\ 0&0&0&0&0&-1&0&0&-1\\\
\end{array}\right),\tilde{M}=\left(\begin{array}[]{ccccccccc}0&0&0&0&0&0&0&1&-1\\\
0&0&0&-1&-1&0&1&0&0\\\ 0&0&0&-1&0&0&0&0&0\\\ -1&-1&0&0&0&0&0&0&0\\\
0&-1&-1&0&0&0&0&0&0\\\ -1&0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&-1&0&0\\\
0&0&0&0&0&0&0&-1&0\\\ -1&0&0&0&0&-1&0&0&1\\\ \end{array}\right).}$

Then

$\phi(T)=\phi(\tilde{T})=-1+22x^{2}-162x^{4}+538x^{6}-897x^{8}+809x^{10}-410x^{12}+116x^{14}-17x^{16}+x^{18},$

which is irreducible over $\mathbb{Q}$. However,
$2^{-9}\sqrt{\Delta(T)}=7^{2}\times 347\times 357175051$, i.e.,
$2^{-9}\sqrt{\Delta(T)}$ has a multiple factor 7 and the condition of Theorem
1.2 is not satisfied. Actually, there indeed exists a regular rational
orthogonal matrix $Q\in\mathcal{Q}(G)$ such that $\tilde{A}=Q^{\textup{T}}AQ$,
where $Q={\rm diag}(Q_{1},Q_{2})$ and $Q_{1}$ and $Q_{2}$ are given as follows
respectively.

${\tiny
Q_{1}=\frac{1}{7}\left(\begin{array}[]{ccccccccc}-1&-1&-2&-2&4&3&3&2&1\\\
-2&-2&3&3&1&-1&-1&4&2\\\ 2&2&4&-3&-1&1&1&3&-2\\\ 4&-3&1&1&-2&2&2&-1&3\\\
-3&4&1&1&-2&2&2&-1&3\\\ 3&3&-1&-1&2&-2&-2&1&4\\\ 1&1&2&2&3&4&-3&-2&-1\\\
2&2&-3&4&-1&1&1&3&-2\\\ 1&1&2&2&3&-3&4&-2&-1\\\
\end{array}\right),Q_{2}=\frac{1}{7}\left(\begin{array}[]{ccccccccc}2&2&4&-3&-1&1&1&3&-2\\\
2&2&-3&4&-1&1&1&3&-2\\\ -2&-2&3&3&1&-1&-1&4&2\\\ 4&-3&1&1&-2&2&2&-1&3\\\
1&1&2&2&3&4&-3&-2&-1\\\ -3&4&1&1&-2&2&2&-1&3\\\ 3&3&-1&-1&2&-2&-2&1&4\\\
-1&-1&-2&-2&4&3&3&2&1\\\ 1&1&2&2&3&-3&4&-2&-1\\\ \end{array}\right).}$

######  Remark 2.

Theorem 3.1 does not hold without the assumption that the characteristic
polynomial of $\Gamma$ is irreducible over $\mathbb{Q}$, even if $\Gamma$ is
controllable. Let $\Gamma$ and $\tilde{\Gamma}$ be two signed trees with
bipartite-adjacency matrices $M$ and $\tilde{M}$ given as follows
respectively:

${\tiny M=\left(\begin{array}[]{ccccccccc}1&0&0&0&0&0&0&0&0\\\
-1&1&0&0&0&0&-1&0&0\\\ 0&-1&-1&0&0&0&0&0&0\\\ 0&0&-1&1&0&0&0&0&0\\\
0&1&0&0&1&-1&0&0&0\\\ 0&0&0&0&1&0&0&0&0\\\ 0&0&0&0&0&0&-1&0&0\\\
0&0&0&0&0&0&1&1&0\\\ 0&0&0&0&0&0&0&-1&-1\\\
\end{array}\right),~{}\tilde{M}=\left(\begin{array}[]{ccccccccc}1&0&0&0&0&0&0&0&0\\\
-1&1&-1&0&0&0&0&0&0\\\ 0&0&-1&0&0&0&0&0&0\\\ 0&0&1&1&0&0&0&0&0\\\
0&0&0&-1&-1&0&0&0&0\\\ 0&-1&0&0&0&1&0&0&0\\\ 0&1&0&0&0&0&1&0&1\\\
0&0&0&0&0&-1&0&-1&0\\\ 0&0&0&0&0&0&0&0&-1\\\ \end{array}\right).}$

${\tiny
Q=\frac{1}{5}\left(\begin{array}[]{cccccccccccccccccc}5&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&5&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&3&-2&1&-1&0&0&0&0&0&1&-1&2&2\\\
0&0&0&0&0&-1&-1&-2&2&0&0&0&0&0&3&2&1&1\\\
0&0&0&0&0&-2&3&1&-1&0&0&0&0&0&1&-1&2&2\\\
0&0&0&0&0&1&1&2&-2&0&0&0&0&0&2&3&-1&-1\\\
0&0&5&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\ 0&0&0&5&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&5&0&0&0&0&0&0&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0&5&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&5&0&0&0&0&0&0&0\\\
0&0&0&0&0&-1&-1&3&2&0&0&0&0&0&-2&2&1&1\\\
0&0&0&0&0&2&2&-1&1&0&0&0&0&0&-1&1&3&-2\\\
0&0&0&0&0&2&2&-1&1&0&0&0&0&0&-1&1&-2&3\\\
0&0&0&0&0&1&1&2&3&0&0&0&0&0&2&-2&-1&-1\\\
0&0&0&0&0&0&0&0&0&0&0&5&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0&0&0&0&5&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&5&0&0&0&0\\\ \end{array}\right).}$
It is easy to verify that

$\phi(\Gamma;x)=(-1+x)(1+x)(-1-x+x^{2})(-1+x+x^{2})(1-21x^{2}+95x^{4}-119x^{6}+60x^{8}-13x^{10}+x^{12}),$

which is reducible over $\mathbb{Q}$ and $\Gamma$ is controllable.
Nevertheless, the unique regular rational orthogonal matrix $Q$ (shown as
above) such that $Q^{\textup{T}}A(\Gamma)Q=A(\tilde{\Gamma})$ is not the form
as in Theorem 3.1.

##  5 Conclusions and Future Work

In this paper, we have given a simple arithmetic condition on a tree $T$ with
an irreducible characteristic polynomial, under which every signed tree with
underlying graph $T$ is DGS. This is a little bit surprising in contrast with
Schwenk’s remarkable result stating almost every tree has a cospectral mate.

However, there are several questions remained to be answered. We end the paper
by proposing the following questions:

######  Question 1.

How can Theorem 1.2 be generalized to signed bipartite graphs?

######  Question 2.

Is it true that every tree with an irreducible characteristic polynomial is
DGS?

######  Question 3.

Is Theorem 3.1 true for controllable bipartite graphs?

For Question 1, the difficulty lies in the fact that for a signed bipartite
graph $\Gamma$, a signed graph $\tilde{\Gamma}$ generalized cospectral with
$\Gamma$ is not necessarily bipartite. For Question 2, we know that it is not
true for signed trees. For Question 3, we know that it is not true for
controllable signed bipartite graphs. But generally we do not know any single
counterexample to Questions 2 and 3. The above questions need further
investigations in the future.

## Acknowledgments

The research of the second author is supported by National Natural Science
Foundation of China (Grant Nos. 11971376 and 12371357) and the third author is
supported by Fundamental Research Funds for the Central Universities (Grant
No. 531118010622).

The authors would like to thank Professor Huiqiu Lin from East China
University of Science and Technology for useful discussions.

## References

  * [1] H.H. Günthard, H. Primas, Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen, _Helvetica Chimica Acta_ , 39 (1956) 1645-1653.
  * [2] L. Collatz, U. Sinogowitz, Spektren endlicher Grafen, _Abh. Math. Sem. Univ. Hamburg_ , 1957 (21): 63-77.
  * [3] W.H. Haemers, X. Liu, Y. Zhang, Spectral characterizations of lollipop graphs, _Linear Algebra Appl_. 428 (2008) 2415-2423.
  * [4] A.E. Brouwer and W.H. Haemers, Spectra of Graphs, _Springer_ , 2012.
  * [5] C. R. Johnson, M. Newman, A note on cospectral graphs, _J. Combin. Theory, Ser. B_ , 28 (1980) 96-103.
  * [6] D. M. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, _Academic Press, NewYork_ , 1982.
  * [7] E. R. van Dam, W. H. Haemers, Which graphs are determined by their spectrum? _Linear Algebra Appl_. 373 (2003) 241-272.
  * [8] E. R. van Dam, W. H. Haemers, Developments on spectral characterizations of graphs, _Discrete Mathematics_ , 309 (2009) 576-586.
  * [9] S. Lang, Algebra, _Springer-Verlag, New York_ , 2002.
  * [10] J. H. van Lint and J. J. Seidel, Equilateral point sets in elliptic geometry, _Proc. Nederl. Akad. Wetenschappen A_ , 1966 (69): 335-348.
  * [11] M. Fisher, On hearing the shape of a drum, _J. Combin. Theory_ , 1 (1966) 105-125.
  * [12] M. Kac, Can one hear the shape of a drum? _J. Amer. Math. Monthly_ , 73 (1966) 1-23.
  * [13] C.D. Godsil, B.D. McKay, Constructing cospectral graphs, _Aequation Mathematicae_ , 25 (1982) 257-268.
  * [14] C.D. Godsil, Controllable subsets in graphs, _Annals of Combinatorics_ , 16 (2012) 733-744.
  * [15] C.D. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics (GTM), volume 207, _Springer, New York_ , 2001.
  * [16] A.J. Schwenk, Almost all trees are cospectral, _in: F. Harary (Ed.), New Directions in the Theory of Graphs, Academic Press, NewYork_ , 1973, pp. 275-307.
  * [17] T. Sunada, Riemannian coverings and isospectral manifolds, _Ann. Math._ 1985 (121):169-186.
  * [18] W. Wang, A uniqueness theorem on matrices and reconstruction, _J. Combin. Theory, Ser. B_ , 99 (2009) 261-265.
  * [19] W. Wang, C. X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra, _Eur. J. Combin._ 27 (2006) 826-840.
  * [20] W. Wang, Generalized spectral characterization revisited, _Electron. J. Combin._ 20 (4) (2013), $\sharp$ P4.
  * [21] W. Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, _J. Combin. Theory, Ser. B_ , 122 (2017) 438-451.
  * [22] W. Wang, T. Yu, Square-free discriminants of matrices and the generalized spectral characterizations of graphs, _arXiv:1608.01144_


# Bound on optimal local discrimination of multipartite quantum states

Donghoon Ha  Department of Applied Mathematics and Institute of Natural
Sciences, Kyung Hee University, Yongin 17104, Republic of Korea  Jeong San Kim
<EMAIL_ADDRESS>Department of Applied Mathematics and Institute of Natural
Sciences, Kyung Hee University, Yongin 17104, Republic of Korea

###### Abstract

We consider the unambiguous discrimination of multipartite quantum states and
provide an upper bound for the maximum success probability of optimal local
discrimination. We also provide a necessary and sufficient condition to
realize the upper bound. We further establish a necessary and sufficient
condition for this upper bound to be saturated. Finally, we illustrate our
results using examples in multidimensional multipartite quantum systems.

## INTRODUCTION

Quantum nonlocality is a quintessential phenomenon of multipartite quantum
systems which does not have any classical counterpart. Entanglement is one of
the most representative nonlocal quantum correlations which cannot be realized
only by _local operations and classical communication_ (LOCC)chit20142 ;
horo2009 . It is known that the nonlocal property of quantum entanglement can
be used as a resource in many quantum information processing taskschit2019 .
Quantum nonlocal phenomenon can also arise in multipartite quantum state
discrimination, which is an essential process for efficient information
transfer in quantum communication. In general, orthogonal quantum states can
be discriminated with certainty, whereas such discrimination is impossible for
nonorthogonal quantum states. Along this line, state discrimination strategies
are needed to discriminate nonorthogonal quantum states at least with some
nonzero probabilitychef2000 ; barn20091 ; berg2010 ; bae2015 . However, some
orthogonal states of multipartite quantum systems cannot be discriminated with
certainty when the available measurements are limited to LOCC
measurementsbenn19991 . As orthogonal states can always be discriminated with
certainty when there is no limitation of possible measurement, this limited
discrimination ability of LOCC measurement reveals the nonlocal phenomenon
inherent in quantum state discrimination.
Nonlocal phenomenon of quantum state discrimination can also arise in
discriminating nonorthogonal states of multipartite quantum systems; it is
known that some nonorthogonal states cannot be optimally discriminated using
only LOCCpere1991 ; duan2007 ; chit2013 . For this reason, much attention has
been shown for the optimal local discrimination of multipartite quantum states
ghos2001 ; walg2002 ; fan2004 ; duan2009 ; chit20141 ; band2015 ; band2021 ;
zhan2020 . Nevertheless, realizing optimal local discrimination still remains
a challenging task because it is hard to have a good mathematical
characterization of LOCC.
One efficient way to overcome this difficulty is to investigate possible upper
bounds for the maximum success probability of optimal local discrimination.
For a better understanding of optimal local discrimination, it is also
important to establish good conditions realizing such upper bounds. Recently,
an upper bound of maximum success probability was established in local
minimum-error discrimination of bipartite quantum states. Moreover, a
necessary and sufficient condition was also provided for this upper bound to
be saturatedha2022 .
Here, we consider _unambiguous discrimination_ (UD)ivan1987 ; pere1988 ;
diek1988 ; zhan2022  among multipartite quantum states of arbitrary dimensions
and provide an upper bound for the maximum success probability of optimal
local discrimination. Moreover, we provide a necessary and sufficient
condition to realize this upper bound. We also establish a necessary and
sufficient condition for this upper bound to be saturated. Finally, we
illustrate our results using examples in multidimensional multipartite quantum
systems.
This paper is organized as follows. In the “Results” Section, we first recall
the definition and some properties about separable operators and separable
measurements in multipartite quantum systems. We further recall the definition
of UD and provide some useful properties of optimal UD (Proposition 1). As the
main results of this paper, we provide an upper bound for the maximum success
probability of optimal local discrimination by using a certain class of
Hermitian operators acting on multipartite Hilbert space (Theorem 1).
Moreover, we provide a necessary and sufficient condition for the Hermitian
operator to realize this upper bound (Theorem 2 and Corollary 1). We also
establish a necessary and sufficient condition for this upper bound to be
saturated (Corollary 2). We illustrate our results by examples in
multidimensional multipartite quantum systems (Examples 1 and 2). In the
“Methods” Section, we provide a detail proof of Theorem 1. In the “Discussion”
Section, we summarize our results and discuss possible future works related to
our results.

## RESULTS

In multipartite quantum systems, a state is described by a density operator
$\rho$ acting on a multipartite Hilbert space
$\mathcal{H}=\bigotimes_{k=1}^{m}\mathcal{H}_{k}$ consisting of the subsystems
$\mathcal{H}_{k}\cong\mathbb{C}^{d_{k}}$ with $m\geqslant 2$ and positive
integers $d_{k}$ for $k=1,\ldots,m$. A measurement is expressed by a _positive
operator-valued measure_ $\\{M_{i}\\}_{i}$ that is a set of positive-
semidefinite operators $M_{i}\succeq 0$ on $\mathcal{H}$ satisfying
completeness relation $\sum_{i}M_{i}=\mathbbm{1}$, where $\mathbbm{1}$ is the
identity operator on $\mathcal{H}$. The probability of obtaining the
measurement outcome corresponding to $M_{j}$ is $\mathrm{Tr}(\rho M_{j})$ for
the prepared state $\rho$.
A positive-semidefinite operator $E$ (not necessarily a state) on
$\mathcal{H}$ is called _separable_ if it can be represented as a summation of
positive-semidefinite product operators, that is,

$E=\sum_{l}\bigotimes_{k=1}^{m}E_{l,k},$ (1)

where $E_{l,k}$ is a positive-semidefinite operator on $\mathcal{H}_{k}$ for
each $k=1,\ldots,m$. We denote the set of all positive-semidefinite
_separable_ operators on $\mathcal{H}$ as

$\mathrm{SEP}=\big{\\{}E\,\big{|}\,\mbox{$E$: a positive-semidefinite
separable operator acting on $\mathcal{H}$}\big{\\}}.$ (2)

A measurement $\\{M_{i}\\}_{i}$ is called a _LOCC measurement_ if it can be
implemented by LOCC, and it is called _separable_ if $M_{i}\in\mathrm{SEP}$
for all $i$. It is known that every LOCC measurement is separablechit20142 .
A simple example of LOCC measurement is $\\{M_{1,i_{1}}\otimes\cdots\otimes
M_{m,i_{m}}\\}_{i_{1},\ldots,i_{m}}$ where $\\{M_{l,i_{l}}\\}_{i_{l}}$ is a
measurement on the $l$th subsystem for each $l=1,\ldots,m$. This separable
measurement can be implemented by local measurements and classical
communication; For each $l=1,\ldots,m$, a local measurement
$\\{M_{l,i_{l}}\\}_{i_{l}}$ is performed on the $l$th subsystem; If it is
confirmed through classical communication that the measurement result of the
$l$th subsystem is $M_{l,i_{l}}$ for each $l=1,\ldots,m$, the measurement
result of the whole system becomes $M_{1,i_{1}}\otimes\cdots\otimes
M_{m,i_{m}}$. Thus, $\\{M_{1,i_{1}}\otimes\cdots\otimes
M_{m,i_{m}}\\}_{i_{1},\ldots,i_{m}}$ is a LOCC measurement.
Here, we consider the situation of discriminating _multipartite_ quantum
states $\rho_{1},\ldots,\rho_{n}$ where the state $\rho_{i}$ is prepared with
the probability $\eta_{i}$. We denote this situation as an ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$. Moreover, we consider the
discrimination of the multipartite state ensemble $\mathcal{E}$ using a
measurement $\\{M_{i}\\}_{i=0}^{n}$ where $M_{0}$ gives inconclusive results
about the prepared state and $M_{i}$ provides conclusive results of $\rho_{i}$
for each $i=1,\ldots,n$. For the conclusive results to be unambiguous, so-
called _no-error condition_ is required;

$\mathrm{Tr}(\rho_{i}M_{j})=0~{}~{}\forall
i,j=1,\ldots,n~{}\mbox{with}~{}i\neq j.$ (3)

By defining

$\mathrm{Pos}_{i}(\mathcal{E})=\\{E\succeq
0\,|\,\mathrm{Tr}(\rho_{j}E)=0~{}\forall j=1,\ldots,n~{}\text{with}~{}j\neq
i\\},$ (4)

Eq. (3) can be rewritten as

$M_{i}\in\mathrm{Pos}_{i}(\mathcal{E})~{}~{}\forall i=1,\ldots,n.$ (5)

We say that a measurement $\\{M_{i}\\}_{i=0}^{n}$ is _unambiguous_ if it
satisfies the no-error condition in Eq. (5).
The _optimal UD_ of $\mathcal{E}$ is to minimize the probability of obtaining
inconclusive results. Equivalently, the optimal UD of $\mathcal{E}$ is to
achieve the optimal success probability of
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$ defined as

$p_{\rm G}(\mathcal{E})=\max_{\begin{subarray}{c}\rm Measurement\\\ \rm
with~{}\mbox{\scriptsize\eqref{eq:nec}}\end{subarray}}\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i}),$
(6)

where the maximum is taken over all possible unambiguous measurements. The
following proposition provide a necessary and sufficient condition of an
_optimal_ unambiguous measurement realizing $p_{\rm G}(\mathcal{E})$elda2004 .

######  Proposition 1.

For given ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, an
unambiguous measurement $\\{M_{i}\\}_{i=0}^{n}$ provides the optimal success
probability $p_{\rm G}(\mathcal{E})$ if and only if there is a Hermitian
operator $K$ satisfying the following condition,

$\displaystyle K\succeq 0,$ (7a) $\displaystyle\mathrm{Tr}(M_{0}K)=0,$ (7b)
$\displaystyle
K-\eta_{i}\rho_{i}\in\mathrm{Pos}_{i}^{*}(\mathcal{E})~{}\forall
i=1,\ldots,n,$ (7c)
$\displaystyle\mathrm{Tr}[M_{i}(K-\eta_{i}\rho_{i})]=0~{}\forall
i=1,\ldots,n,$ (7d)

where $\mathrm{Pos}_{i}^{*}(\mathcal{E})$($i=1,\ldots,n$) is the dual set of
$\mathrm{Pos}_{i}(\mathcal{E})$ defined as

$\mathrm{Pos}_{i}^{*}(\mathcal{E})=\\{A\,|\,A^{\dagger}=A,~{}\mathrm{Tr}(AB)\geqslant
0~{}\forall B\in\mathrm{Pos}_{i}(\mathcal{E})\\}.$ (8)

In this case, we have

$p_{\rm
G}(\mathcal{E})=\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\mathrm{Tr}K.$
(9)

For each $\mathrm{Pos}_{i}(\mathcal{E})$ in Eq. (4), we denote the subset of
separable operators,

$\mathrm{SEP}_{i}(\mathcal{E})=\mathrm{Pos}_{i}(\mathcal{E})\cap\mathrm{SEP}=\\{E\in\mathrm{SEP}\,|\,\mathrm{Tr}(\rho_{j}E)=0~{}\forall
j=1,\ldots,n~{}\text{with}~{}j\neq i\\}.$ (10)

The unambiguous measurement $\\{M_{i}\\}_{i=0}^{n}$ is called separable if

$M_{0}\in\mathrm{SEP},~{}M_{i}\in\mathrm{SEP}_{i}(\mathcal{E})~{}\forall
i=1,\ldots,n,$ (11)

where $\mathrm{SEP}$ is defined in Eq. (2).
When the available measurements are limited to separable unambiguous
measurements, we denote the maximum success probability by

$p_{\rm SEP}(\mathcal{E})=\max_{\begin{subarray}{c}\rm Measurement\\\ \rm
with~{}\mbox{\scriptsize\eqref{eq:sepm}}\end{subarray}}\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i}).$
(12)

We use $p_{\rm L}(\mathcal{E})$ to denote the maximum of success probability
that can be obtained using LOCC unambiguous measurements, that is,

$p_{\rm L}(\mathcal{E})=\max_{\begin{subarray}{c}\rm LOCC\\\ \rm
measurement\\\ \rm
with~{}\mbox{\scriptsize\eqref{eq:nec}}\end{subarray}}\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i}).$
(13)

For a given ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, we
define $q_{\rm SEP}(\mathcal{E})$ as the minimum quantity

$q_{\rm SEP}(\mathcal{E})=\min\mathrm{Tr}H$ (14)

over all possible Hermitian operator $H$ satisfying

$\displaystyle H\in\mathrm{SEP}^{*},$ (15a) $\displaystyle
H-\eta_{i}\rho_{i}\in\mathrm{SEP}_{i}^{*}(\mathcal{E})~{}\forall
i=1,\ldots,n,$ (15b)

where $\mathrm{SEP}^{*}$ and
$\mathrm{SEP}_{i}^{*}(\mathcal{E})$($i=1,\ldots,n$) are the dual sets of
$\mathrm{SEP}$ and $\mathrm{SEP}_{i}(\mathcal{E})$ in Eqs. (2) and (10),
respectively, that is,

$\begin{array}[]{rcl}\mathrm{SEP}^{*}&=&\\{A\,|\,A^{\dagger}=A,~{}\mathrm{Tr}(AB)\geqslant
0~{}\forall B\in\mathrm{SEP}\\},\\\\[2.84526pt]
\mathrm{SEP}_{i}^{*}(\mathcal{E})&=&\\{A\,|\,A^{\dagger}=A,~{}\mathrm{Tr}(AB)\geqslant
0~{}\forall B\in\mathrm{SEP}_{i}(\mathcal{E})\\}.\end{array}$ (16)

Note that $\mathrm{SEP}^{*}$ contains all positive-semidefinite operators
because every element of $\mathrm{SEP}$ is positive semidefinite. Due to the
similar reason, $\mathrm{SEP}_{i}^{*}(\mathcal{E})$($i=1,\ldots,n$) contains
all positive-semidefinite operators.
The following theorem shows that $q_{\rm SEP}(\mathcal{E})$ is equal to
$p_{\rm SEP}(\mathcal{E})$ in Eq. (12). The proof of Theorem 1 is provided in
the “Methods” Section.

######  Theorem 1.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$,

$p_{\rm SEP}(\mathcal{E})=q_{\rm SEP}(\mathcal{E}).$ (17)

For a given ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, the
following theorem provides a necessary and sufficient condition on a Hermitian
operator $H$ to realize $q_{\rm SEP}(\mathcal{E})$.

######  Theorem 2.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, a Hermitian operator $H$
satisfying Condition (15) gives $q_{\rm SEP}(\mathcal{E})$ if and only if
there is a separable unambiguous measurement $\\{M_{i}\\}_{i=0}^{n}$ such that

$\displaystyle\mathrm{Tr}(M_{0}H)=0,$ (18a)
$\displaystyle\mathrm{Tr}[M_{i}(H-\eta_{i}\rho_{i})]=0~{}~{}\forall
i=1,\ldots,n.$ (18b)

In this case, we have

$q_{\rm
SEP}(\mathcal{E})=\mathrm{Tr}H=\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i}).$
(19)

###### Proof.

For the necessity, suppose that $H$ is a Hermitian operator providing $q_{\rm
SEP}(\mathcal{E})$. We also denote $\\{M_{i}\\}_{i=0}^{n}$ as a separable
unambiguous measurement giving $p_{\rm SEP}(\mathcal{E})$. From Conditions
(11) and (15), we have

$\mathrm{Tr}(M_{0}H)\geqslant
0,~{}\mathrm{Tr}[M_{i}(H-\eta_{i}\rho_{i})]\geqslant 0~{}\forall
i=1,\ldots,n.$ (20)

We also note that

$\mathrm{Tr}(M_{0}H)+\sum_{i=1}^{n}\mathrm{Tr}[M_{i}(H-\eta_{i}\rho_{i})]=\mathrm{Tr}H-\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=q_{\rm
SEP}(\mathcal{E})-p_{\rm SEP}(\mathcal{E})=0,$ (21)

where the first equality follows from $\sum_{i=0}^{n}M_{i}=\mathbbm{1}$, the
second equality is due to the assumption of $H$ and $\\{M_{i}\\}_{i=0}^{n}$,
and the last equality is by Theorem 1. Inequality (20) and Eq. (21) lead us to
Condition (18). Therefore, $\\{M_{i}\\}_{i=0}^{n}$ is a separable unambiguous
measurement satisfying Condition (18).
For the sufficiency, we assume that $\\{M_{i}\\}_{i=0}^{n}$ is a separable
unambiguous measurement and $H$ is a Hermitian operator satisfying Conditions
(15) and (18). This assumption implies

$q_{\rm SEP}(\mathcal{E})=p_{\rm
SEP}(\mathcal{E})\geqslant\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})+\mathrm{Tr}(M_{0}H)+\sum_{i=1}^{n}\mathrm{Tr}[M_{i}(H-\eta_{i}\rho_{i})]=\mathrm{Tr}H\geqslant
q_{\rm SEP}(\mathcal{E}),$ (22)

where the first equality follows from Theorem 1, the second equality is from
Condition (18), the last equality is due to $\sum_{i=0}^{n}M_{i}=\mathbbm{1}$,
and the first and second inequalities are from the definitions of $p_{\rm
SEP}(\mathcal{E})$ and $q_{\rm SEP}(\mathcal{E})$, respectively. Inequality
(22) leads us to $\mathrm{Tr}H=q_{\rm SEP}(\mathcal{E})$. Therefore, $H$ is a
Hermitian operator giving $q_{\rm SEP}(\mathcal{E})$. ∎

From Theorems 1 and 2, we have the following corollary providing a necessary
and sufficient condition on a separable unambiguous measurement
$\\{M_{i}\\}_{i=0}^{n}$ to realize $p_{\rm SEP}(\mathcal{E})$.

######  Corollary 1.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, a separable unambiguous
measurement $\\{M_{i}\\}_{i=0}^{n}$ gives $p_{\rm SEP}(\mathcal{E})$ if and
only if there is a Hermitian operator $H$ satisfying Conditions (15) and (18).
In this case, we have

$p_{\rm
SEP}(\mathcal{E})=\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\mathrm{Tr}H.$
(23)

Moreover, we have the following corollary that provides the relative ordering
between $p_{\rm L}(\mathcal{E})$ and $q_{\rm SEP}(\mathcal{E})$.

######  Corollary 2.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$,

$p_{\rm L}(\mathcal{E})\leqslant q_{\rm SEP}(\mathcal{E}),$ (24)

where the equality holds if and only if there is a LOCC unambiguous
measurement $\\{M_{i}\\}_{i=0}^{n}$ and a Hermitian operator $H$ satisfying
Conditions (15) and (18).

###### Proof.

Since every LOCC measurement is separable, $p_{\rm L}(\mathcal{E})\leqslant
p_{\rm SEP}(\mathcal{E})$. Moreover, $p_{\rm L}(\mathcal{E})=p_{\rm
SEP}(\mathcal{E})$ if and only if there is a LOCC unambiguous measurement
realizing $p_{\rm SEP}(\mathcal{E})$. Thus, we can show from Theorem 1 and
Corollary 1 that our statement is true. ∎

Here, we provide the following example of two-qubit state ensemble
$\mathcal{E}$ to illustrate how our results can be used to obtain $p_{\rm
G}(\mathcal{E})$, $q_{\rm SEP}(\mathcal{E})$, and $p_{\rm L}(\mathcal{E})$.

Example 1. Let us consider the two-qubit state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{3}$ consisting of three product
states with equal prior probabilities,

$\begin{array}[]{lll}\eta_{1}=\frac{1}{3},~{}~{}\rho_{1}=|0\rangle\\!\langle
0|\otimes|0\rangle\\!\langle 0|,&\\\\[2.84526pt]
\eta_{2}=\frac{1}{3},~{}~{}\rho_{2}=|\nu_{+}\rangle\\!\langle\nu_{+}|\otimes|\nu_{+}\rangle\\!\langle\nu_{+}|,~{}~{}|\nu_{+}\rangle=\frac{1}{2}|0\rangle+\frac{\sqrt{3}}{2}|1\rangle,\\\\[2.84526pt]
\eta_{3}=\frac{1}{3},~{}~{}\rho_{3}=|\nu_{-}\rangle\\!\langle\nu_{-}|\otimes|\nu_{-}\rangle\\!\langle\nu_{-}|,~{}~{}|\nu_{-}\rangle=\frac{1}{2}|0\rangle-\frac{\sqrt{3}}{2}|1\rangle.\end{array}$
(25)

To obtain $p_{\rm G}(\mathcal{E})$, we use the unambiguous measurement
$\\{M_{i}\\}_{i=0}^{3}$ with

$\begin{array}[]{ll}M_{0}=\frac{1}{2}|\Phi_{+}\rangle\\!\langle\Phi_{+}|+|\Psi_{-}\rangle\\!\langle\Psi_{-}|,\\\\[2.84526pt]
M_{1}=\frac{5}{6}|\Phi_{1}\rangle\\!\langle\Phi_{1}|,~{}|\Phi_{1}\rangle=\frac{3}{\sqrt{10}}|00\rangle-\frac{1}{\sqrt{10}}|11\rangle,\\\\[2.84526pt]
M_{2}=\frac{5}{6}|\Phi_{2}\rangle\\!\langle\Phi_{2}|,~{}|\Phi_{2}\rangle=\sqrt{\frac{3}{10}}|01\rangle+\sqrt{\frac{3}{10}}|10\rangle+\frac{2}{\sqrt{10}}|11\rangle,\\\\[2.84526pt]
M_{3}=\frac{5}{6}|\Phi_{3}\rangle\\!\langle\Phi_{3}|,~{}|\Phi_{3}\rangle=\sqrt{\frac{3}{10}}|01\rangle+\sqrt{\frac{3}{10}}|10\rangle-\frac{2}{\sqrt{10}}|11\rangle,\end{array}$
(26)

and Hermitian operator

$K=\frac{3}{8}|\Phi_{-}\rangle\\!\langle\Phi_{-}|+\frac{3}{8}|\Psi_{+}\rangle\\!\langle\Psi_{+}|,$
(27)

where

$|\Phi_{\pm}\rangle=\frac{1}{\sqrt{2}}|00\rangle\pm\frac{1}{\sqrt{2}}|11\rangle,~{}|\Psi_{\pm}\rangle=\frac{1}{\sqrt{2}}|01\rangle\pm\frac{1}{\sqrt{2}}|10\rangle$
(28)

are the Bell states in two-qubit systems. We will show the unambiguous
measurement $\\{M_{i}\\}_{i=0}^{3}$ and the Hermitian operator $K$ satisfy the
conditions of Proposition 1 for the ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{3}$ in Eq. (25).
For $K$ of Eq. (27), Condition (7a) is obvious and Condition (7b) is also true
due to the orthogonality of Bell states. For Condition (7c), we first note
$|\Psi_{-}\rangle\\!\langle\Psi_{-}|$ is orthogonal to each $\rho_{i}$, that
is, $\mathrm{Tr}(|\Psi_{-}\rangle\\!\langle\Psi_{-}|\rho_{i})=0$, $i=1,2,3$.
Moreover, $|\Phi_{i}\rangle\\!\langle\Phi_{i}|$ is orthogonal to $\rho_{j}$
for all $i,j=1,2,3$ with $i\neq j$. Thus, we have

$\mathrm{Pos}_{i}(\mathcal{E})=\\{E\succeq 0\,|\,\mbox{ $E$ acting on the
subspace spanned by $|\Phi_{i}\rangle$ and $|\Psi_{-}\rangle$}\\}~{}~{}\forall
i=1,2,3,$ (29)

for the ensemble $\mathcal{E}$ of Eq. (25). Now, a straightforward calculation
leads us to

$\langle\Phi_{i}|(K-\eta_{i}\rho_{i})|\Phi_{i}\rangle=\langle\Phi_{i}|(K-\eta_{i}\rho_{i})|\Psi_{-}\rangle=\langle\Psi_{-}|(K-\eta_{i}\rho_{i})|\Psi_{-}\rangle=0~{}~{}\forall
i=1,2,3,$ (30)

and this implies

$\mathrm{Tr}[(K-\eta_{i}\rho_{i})E]=0$ (31)

for all $E$ in $\mathrm{Pos}_{i}(\mathcal{E})$. From the definition of
$\mathrm{Pos}_{i}^{*}(\mathcal{E})$ in Eq. (8), we have
$K-\eta_{i}\rho_{i}\in\mathrm{Pos}_{i}^{*}(\mathcal{E})$ for each $i=1,2,3$,
and this shows the validity of Condition (7c). Finally, Condition (7d)
naturally follows from Eqs. (26) and (30). From Proposition 1, the optimal
success probability $p_{\rm G}(\mathcal{E})$ in Eq. (6) is

$p_{\rm
G}(\mathcal{E})=\sum_{i=1}^{3}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\mathrm{Tr}K=\frac{3}{4}.$
(32)

To obtain $q_{\rm SEP}(\mathcal{E})$ in Eq. (14), let us consider the
Hermitian operator

$H=\frac{1}{2}|\Psi_{-}\rangle\\!\langle\Psi_{-}|,$ (33)

and the separable unambiguous measurement $\\{M_{i}\\}_{i=0}^{3}$ consisting
of

$\begin{array}[]{l}M_{0}=\frac{4}{9}|1\rangle\\!\langle
1|\otimes|1\rangle\\!\langle
1|+\frac{4}{9}|\mu_{+}\rangle\\!\langle\mu_{+}|\otimes|\mu_{+}\rangle\\!\langle\mu_{+}|+\frac{4}{9}|\mu_{-}\rangle\\!\langle\mu_{-}|\otimes|\mu_{-}\rangle\\!\langle\mu_{-}|,\\\\[2.84526pt]
M_{1}=\frac{4}{9}|\mu_{+}\rangle\\!\langle\mu_{+}|\otimes|\mu_{-}\rangle\\!\langle\mu_{-}|+\frac{4}{9}|\mu_{-}\rangle\\!\langle\mu_{-}|\otimes|\mu_{+}\rangle\\!\langle\mu_{+}|,\\\\[2.84526pt]
M_{2}=\frac{4}{9}|\mu_{+}\rangle\\!\langle\mu_{+}|\otimes|1\rangle\\!\langle
1|+\frac{4}{9}|1\rangle\\!\langle
1|\otimes|\mu_{+}\rangle\\!\langle\mu_{+}|,\\\\[2.84526pt]
M_{3}=\frac{4}{9}|\mu_{-}\rangle\\!\langle\mu_{-}|\otimes|1\rangle\\!\langle
1|+\frac{4}{9}|1\rangle\\!\langle
1|\otimes|\mu_{-}\rangle\\!\langle\mu_{-}|,\end{array}$ (34)

where

$|\mu_{\pm}\rangle=\frac{\sqrt{3}}{2}|0\rangle\pm\frac{1}{2}|1\rangle.$ (35)

We will show the Hermitian operator $H$ and the separable unambiguous
measurement $\\{M_{i}\\}_{i=0}^{3}$ satisfy the conditions of Theorem 2 for
the ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{3}$ in Eq. (25).
For $H$ of Eq. (33), Condition (15a) holds due to the argument after Eq. (16)
and Condition (18a) is also true from the fact that $|\Psi_{-}\rangle$ is
orthogonal to
$|1\rangle\otimes|1\rangle$,$|\mu_{+}\rangle\otimes|\mu_{+}\rangle$,$|\mu_{-}\rangle\otimes|\mu_{-}\rangle$.
For Condition (15b), we first note every positive-semidefinite product
operator orthogonal to $\rho_{2}$ and $\rho_{3}$ is proportional to
$|\mu_{+}\rangle\\!\langle\mu_{+}|\otimes|\mu_{-}\rangle\\!\langle\mu_{-}|$ or
$|\mu_{-}\rangle\\!\langle\mu_{-}|\otimes|\mu_{+}\rangle\\!\langle\mu_{+}|$.
Moreover, every positive-semidefinite product operator orthogonal to
$\rho_{1}$ and $\rho_{3(2)}$ is proportional to
$|\mu_{+(-)}\rangle\\!\langle\mu_{+(-)}|\otimes|1\rangle\\!\langle 1|$ or
$|1\rangle\\!\langle 1|\otimes|\mu_{+(-)}\rangle\\!\langle\mu_{+(-)}|$. Thus,
we have

$\begin{array}[]{l}\mathrm{SEP}_{1}(\mathcal{E})=\\{a|\mu_{+}\rangle\\!\langle\mu_{+}|\otimes|\mu_{-}\rangle\\!\langle\mu_{-}|+b|\mu_{-}\rangle\\!\langle\mu_{-}|\otimes|\mu_{+}\rangle\\!\langle\mu_{+}|~{}|~{}a,b\geqslant
0\\},\\\\[2.84526pt]
\mathrm{SEP}_{2}(\mathcal{E})=\\{a|\mu_{+}\rangle\\!\langle\mu_{+}|\otimes|1\rangle\\!\langle
1|+b|1\rangle\\!\langle
1|\otimes|\mu_{+}\rangle\\!\langle\mu_{+}|~{}|~{}a,b\geqslant
0\\},\\\\[2.84526pt]
\mathrm{SEP}_{3}(\mathcal{E})=\\{a|\mu_{-}\rangle\\!\langle\mu_{-}|\otimes|1\rangle\\!\langle
1|+b|1\rangle\\!\langle
1|\otimes|\mu_{-}\rangle\\!\langle\mu_{-}|~{}|~{}a,b\geqslant
0\\},\end{array}$ (36)

for the ensemble $\mathcal{E}$ of Eq. (25). Now, a straightforward calculation
leads us to

$\begin{array}[]{l}\langle
v|(H-\eta_{1}\rho_{1})|v\rangle=0~{}~{}\forall|v\rangle=|\mu_{+}\rangle\otimes|\mu_{-}\rangle,|\mu_{-}\rangle\otimes|\mu_{+}\rangle,\\\\[2.84526pt]
\langle
v|(H-\eta_{2}\rho_{2})|v\rangle=0~{}~{}\forall|v\rangle=|\mu_{+}\rangle\otimes|1\rangle,|1\rangle\otimes|\mu_{+}\rangle,\\\\[2.84526pt]
\langle
v|(H-\eta_{3}\rho_{3})|v\rangle=0~{}~{}\forall|v\rangle=|\mu_{-}\rangle\otimes|1\rangle,|1\rangle\otimes|\mu_{-}\rangle,\end{array}$
(37)

and this implies

$\mathrm{Tr}[(H-\eta_{i}\rho_{i})E]=0$ (38)

for all $E$ in $\mathrm{SEP}_{i}(\mathcal{E})$($i=1,2,3$). From the definition
of $\mathrm{SEP}_{i}^{*}(\mathcal{E})$($i=1,2,3$) in Eq. (16), we have
$H-\eta_{i}\rho_{i}\in\mathrm{SEP}_{i}^{*}(\mathcal{E})$ for each $i=1,2,3$,
and this shows the validity of Condition (15b). Finally, Condition (18b)
naturally follows from Eqs. (34) and (37). From Theorem 2, the minimum
quantity $q_{\rm SEP}(\mathcal{E})$ in Eq. (14) is

$q_{\rm
SEP}(\mathcal{E})=\mathrm{Tr}H=\sum_{i=1}^{3}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\frac{1}{2}.$
(39)

We also note that the measurement $\\{M_{i}\\}_{i=0}^{3}$ with Eq. (34) is a
LOCC measurement because it can be implemented by performing the same local
measurement $\\{\frac{2}{3}|1\rangle\langle
1|,\frac{2}{3}|\mu_{+}\rangle\\!\langle\mu_{+}|,\frac{2}{3}|\mu_{-}\rangle\\!\langle\mu_{-}|\\}$
on two subsystems. Thus, Corollary 2 and Eq. (39) lead us to

$p_{\rm L}(\mathcal{E})=q_{\rm SEP}(\mathcal{E})=\frac{1}{2}.$ (40)

Now, we provide another example of mixed-state ensemble in multipartite high-
dimensional quantum systems to illustrate the application of our results in
obtaining $p_{\rm G}(\mathcal{E})$, $q_{\rm SEP}(\mathcal{E})$, and $p_{\rm
L}(\mathcal{E})$.

Example 2. For any integer $d\geqslant 3$, let us consider the following
($d-1$)-qu$d$it state ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{d}$
consisting of $d$ mixed states with equal prior probabilities,

$\displaystyle\eta_{i}=\frac{1}{d},~{}\rho_{i}=\frac{1}{d^{d-1}-2(d-1)}\Bigg{[}\mathbbm{1}-\sum_{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}^{d}(|\Lambda_{j}\rangle\\!\langle\Lambda_{j}|+|\Omega_{j}\rangle\\!\langle\Omega_{j}|)\Bigg{]},~{}i=1,\ldots,d,$
(41)
$\displaystyle|\Lambda_{j}\rangle=|j-1\rangle^{\otimes(d-1)},~{}|\Omega_{j}\rangle=\frac{1}{\sqrt{d-1}}\sum_{\begin{subarray}{c}k=0\\\
k\neq j-1\end{subarray}}^{d-1}\bigotimes_{\begin{subarray}{c}l=0\\\ k\oplus
l\neq j-1\end{subarray}}^{d-1}|k\oplus l\rangle,~{}~{}j=1,\ldots,d,$

where $\oplus$ denotes modulo-$d$ addition. To obtain $p_{\rm
G}(\mathcal{E})$, we use the unambiguous measurement $\\{M_{i}\\}_{i=0}^{d}$
with

$M_{0}=\mathbbm{1}-\sum_{j=1}^{d}(|\Lambda_{j}\rangle\\!\langle\Lambda_{j}|+|\Omega_{j}\rangle\\!\langle\Omega_{j}|),~{}M_{i}=|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|+|\Omega_{i}\rangle\\!\langle\Omega_{i}|,~{}i=1,\ldots,d,$
(42)

and Hermitian operator

$K=\frac{1}{d^{d}-2d(d-1)}\sum_{j=1}^{d}(|\Lambda_{j}\rangle\\!\langle\Lambda_{j}|+|\Omega_{j}\rangle\\!\langle\Omega_{j}|).$
(43)

We will show the unambiguous measurement $\\{M_{i}\\}_{i=0}^{d}$ and the
Hermitian operator $K$ satisfy the conditions of Proposition 1 for the
ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{d}$ in Eq. (41).
For $K$ of Eq. (43), Condition (7a) is obvious and Condition (7b) is also true
due to the orthogonality of
$\\{|\Lambda_{i}\rangle,|\Omega_{i}\rangle\\}_{i=1}^{d}$. For Condition (7c),
we first note both $|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|$ and
$|\Omega_{i}\rangle\\!\langle\Omega_{i}|$ are orthogonal to $\rho_{j}$, that
is,
$\mathrm{Tr}(|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|\rho_{j})=\mathrm{Tr}(|\Omega_{i}\rangle\\!\langle\Omega_{i}|\rho_{j})=0$,
for all $i,j=1,\ldots,d$ with $i\neq j$.
Let $O_{1}$ be the set of all positive semidefinite operators orthogonal to
$\rho_{1}$. From the definition of $\rho_{i}$ in Eq. (41), we have

$O_{1}=\\{E\succeq 0\,|\,\mbox{$E$ acting on the subspace spanned by
$|\Lambda_{2}\rangle,\ldots,|\Lambda_{d}\rangle$ and
$|\Omega_{2}\rangle,\ldots,|\Omega_{d}\rangle$}\\}.$ (44)

Now, let $O_{j}$ be the set of all positive semidefinite operators orthogonal
to $\rho_{j}$ for each $j=2,\ldots,d$. Similarly, we have

$\begin{array}[]{l}O_{j}=\\{E\succeq 0\,|\,\mbox{$E$ acting on the subspace
spanned by
$|\Lambda_{1}\rangle,\ldots,\widehat{|\Lambda_{j}\rangle},\ldots,|\Lambda_{d}\rangle$
and
$|\Omega_{1}\rangle,\ldots,\widehat{|\Omega_{j}\rangle},\ldots,|\Omega_{d}\rangle$}\\},\end{array}$
(45)

where

$\begin{array}[]{l}\\{|\Lambda_{1}\rangle,\ldots,\widehat{|\Lambda_{j}\rangle},\ldots,|\Lambda_{d}\rangle\\}=\\{|\Lambda_{1}\rangle,\ldots,|\Lambda_{j-1}\rangle,|\Lambda_{j+1}\rangle,\ldots,|\Lambda_{d}\rangle\\},\\\\[2.84526pt]
\\{|\Omega_{1}\rangle,\ldots,\widehat{|\Omega_{j}\rangle},\ldots,|\Omega_{d}\rangle\\}=\\{|\Omega_{1}\rangle,\ldots,|\Omega_{j-1}\rangle,|\Omega_{j+1}\rangle,\ldots,|\Omega_{d}\rangle\\}.\end{array}$
(46)

From the definition of $\mathrm{Pos}_{i}(\mathcal{E})$ in Eq. (4), we have

$\mathrm{Pos}_{i}(\mathcal{E})=\bigcap_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{d}O_{j}=\\{E\succeq 0\,|\,\mbox{ $E$ acting on the subspace
spanned by $|\Lambda_{i}\rangle$ and $|\Omega_{i}\rangle$}\\}~{}~{}\forall
i=1,\ldots,d,$ (47)

for the ensemble $\mathcal{E}$ of Eq. (41). Moreover, a straightforward
calculation leads us to

$\langle\Lambda_{i}|(K-\eta_{i}\rho_{i})|\Lambda_{i}\rangle=\langle\Lambda_{i}|(K-\eta_{i}\rho_{i})|\Omega_{i}\rangle=\langle\Omega_{i}|(K-\eta_{i}\rho_{i})|\Omega_{i}\rangle=0~{}\forall
i=1,\ldots,d.$ (48)

This implies Eq. (31) for all $E$ in
$\mathrm{Pos}_{i}(\mathcal{E})$($i=1,\ldots,d$). From the definition of
$\mathrm{Pos}_{i}^{*}(\mathcal{E})$ in Eq. (8), we have
$K-\eta_{i}\rho_{i}\in\mathrm{Pos}_{i}^{*}(\mathcal{E})$ for each
$i=1,\ldots,d$, and this shows the validity of Condition (7c). Finally,
Condition (7d) naturally follows from Eqs. (42) and (48). Therefore, the
optimal success probability $p_{\rm G}(\mathcal{E})$ in Eq. (6) is

$p_{\rm
G}(\mathcal{E})=\sum_{i=1}^{d}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\mathrm{Tr}K=\frac{2}{d^{d-1}-2(d-1)}.$
(49)

To obtain $q_{\rm SEP}(\mathcal{E})$ in Eq. (14), let us consider the
Hermitian operator

$H=\frac{1}{d^{d}-2d(d-1)}\sum_{j=1}^{d}|\Lambda_{j}\rangle\\!\langle\Lambda_{j}|,$
(50)

and the separable unambiguous measurement $\\{M_{i}\\}_{i=0}^{d}$ consisting
of

$M_{0}=\mathbbm{1}-\sum_{j=1}^{d}|\Lambda_{j}\rangle\\!\langle\Lambda_{j}|,~{}M_{i}=|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|,~{}i=1,\ldots,d,$
(51)

where $\\{|\Lambda_{j}\rangle\\}_{j=1}^{d}$ is defined in Eq. (41). We will
show the Hermitian operator $H$ and the separable unambiguous measurement
$\\{M_{i}\\}_{i=0}^{d}$ satisfy the conditions of Theorem 2 for the ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{d}$ in Eq. (41).
For $H$ of Eq. (50), Condition (15a) is satisfied from the argument after Eq.
(16) and Condition (18a) is also true due to the orthogonality of
$\\{|\Lambda_{i}\rangle\\}_{i=1}^{d}$. For Condition (15b), we first note that
$|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|$ is obviously separable for all
$i=1,\ldots,d$. However, $|\Omega_{i}\rangle\\!\langle\Omega_{i}|$ is not
separable for each $i=1,\ldots,d$ because the reduced density operator of
$|\Omega_{i}\rangle\\!\langle\Omega_{i}|$ onto any qu$d$it subsystem is not
rank one.
For each $i=1,\ldots,d$, we also note that
$|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|$ is the only pure product state
acting on the subspace spanned by $|\Lambda_{i}\rangle$ and
$|\Omega_{i}\rangle$. To see this, let us consider any pure state
$(c_{1}|\Lambda_{i}\rangle+c_{2}|\Omega_{i}\rangle)(c_{1}^{*}\langle\Lambda_{i}|+c_{2}^{*}\langle\Omega_{i}|)$
on the subspace spanned by $|\Lambda_{i}\rangle$ and $|\Omega_{i}\rangle$ with
complex numbers $c_{1}$ and $c_{2}$ such that $|c_{1}|^{2}+|c_{2}|^{2}=1$. Due
to the definitions of $|\Lambda_{i}\rangle$ and $|\Omega_{i}\rangle$ in Eq.
(41), it is straightforward to show that any partial trace of
$|\Lambda_{i}\rangle\\!\langle\Omega_{i}|$ is the zero operator. Thus, the
reduced density operator of
$(c_{1}|\Lambda_{i}\rangle+c_{2}|\Omega_{i}\rangle)(c_{1}^{*}\langle\Lambda_{i}|+c_{2}^{*}\langle\Omega_{i}|)$
is

$\mathrm{Tr}_{\mathbb{S}}[(c_{1}|\Lambda_{i}\rangle+c_{2}|\Omega_{i}\rangle)(c_{1}^{*}\langle\Lambda_{i}|+c_{2}^{*}\langle\Omega_{i}|)]=|c_{1}|^{2}\,|\mathrm{Tr}_{\mathbb{S}}(|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|)+|c_{2}|^{2}\,|\mathrm{Tr}_{\mathbb{S}}(|\Omega_{i}\rangle\\!\langle\Omega_{i}|),$
(52)

where $\mathbb{S}$ is any $\alpha$-qu$d$it subsystem with $\alpha<d-1$. If
$c_{2}$ is nonzero, then the reduced density operator in Eq. (52) is not rank
one because $|\Omega_{i}\rangle\\!\langle\Omega_{i}|$ is not separable, which
implies that
$(c_{1}|\Lambda_{i}\rangle+c_{2}|\Omega_{i}\rangle)(c_{1}^{*}\langle\Lambda_{i}|+c_{2}^{*}\langle\Omega_{i}|)$
is not separable. Thus, $|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|$ is the
only pure product state acting on the subspace spanned by
$|\Lambda_{i}\rangle$ and $|\Omega_{i}\rangle$.
Now, let us consider $\mathrm{SEP}_{i}(\mathcal{E})$ of the ensemble
$\mathcal{E}$ in Eq. (41) for each $i=1,\ldots,d$. From Eq. (47) and the
definition of $\mathrm{SEP}_{i}(\mathcal{E})$ in Eq. (10), we have

$\mathrm{SEP}_{i}(\mathcal{E})=\\{E\in\mathrm{SEP}\,|\,\mbox{ $E$ acting on
the subspace spanned by $|\Lambda_{i}\rangle$ and $|\Omega_{i}\rangle$}\\}.$
(53)

Because any separable state is a convex combination of pure product states and
$|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|$ is the only pure product state
acting on the subspace spanned by $|\Lambda_{i}\rangle$ and
$|\Omega_{i}\rangle$, we have

$\mathrm{SEP}_{i}(\mathcal{E})=\big{\\{}a|\Lambda_{i}\rangle\\!\langle\Lambda_{i}|~{}\big{|}~{}a\geqslant
0\big{\\}}.$ (54)

Moreover, a straightforward calculation leads us to

$\langle\Lambda_{i}|(H-\eta_{i}\rho_{i})|\Lambda_{i}\rangle=0,$ (55)

which implies $\mathrm{Tr}[(H-\eta_{i}\rho_{i})E]=0$ for all $E$ in
$\mathrm{SEP}_{i}(\mathcal{E})$. Thus, we have
$H-\eta_{i}\rho_{i}\in\mathrm{SEP}_{i}^{*}(\mathcal{E})$, and this shows the
validity of Condition (15b) for each $i=1,\ldots,d$. Finally, Condition (18b)
naturally follows from Eqs. (51) and (55).
From Theorem 2, the minimum quantity $q_{\rm SEP}(\mathcal{E})$ in Eq. (14) is

$q_{\rm
SEP}(\mathcal{E})=\mathrm{Tr}H=\sum_{i=1}^{d}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\frac{1}{d^{d-1}-2(d-1)}.$
(56)

Moreover, the measurement $\\{M_{i}\\}_{i=0}^{d}$ with Eq. (51) is a LOCC
measurement since it can be implemented by performing the same local
measurement $\\{|i\rangle\\!\langle i|\\}_{i=0}^{d-1}$ on all subsystems.
Thus, Corollary 2 and Eq. (56) lead us to

$p_{\rm L}(\mathcal{E})=q_{\rm SEP}(\mathcal{E})=\frac{1}{d^{d-1}-2(d-1)}.$
(57)

Examples 1 and 2 are special cases that $p_{\rm L}(\mathcal{E})=p_{\rm
SEP}(\mathcal{E})$, or equivalently $p_{\rm L}(\mathcal{E})=q_{\rm
SEP}(\mathcal{E})$. We also note that there exist separable-state ensembles
with $p_{\rm L}(\mathcal{E})<q_{\rm SEP}(\mathcal{E})$, therefore $p_{\rm
L}(\mathcal{E})<p_{\rm SEP}(\mathcal{E})$. A well-known example with $p_{\rm
L}(\mathcal{E})<p_{\rm SEP}(\mathcal{E})$ is the domino state ensemble which
can be perfectly discriminated by separable measurements but not by LOCC
measurements benn19991 .

## DISCUSSION

In this paper, we have considered the situation of unambiguously
discriminating multipartite quantum states, and provided an upper bound
$q_{\rm SEP}(\mathcal{E})$ for the maximum success probability of optimal
local discrimination $p_{\rm L}(\mathcal{E})$. We have further established a
necessary and sufficient condition for the Hermitian operator $H$ to realize
$q_{\rm SEP}(\mathcal{E})$. Moreover, we have provided a necessary and
sufficient condition for the upper bound $q_{\rm SEP}(\mathcal{E})$ to be
saturated. Finally, we have illustrated our results by examples in
multidimensional multipartite quantum systems.
We remark that finding $p_{\rm G}(\mathcal{E})$ and $q_{\rm SEP}(\mathcal{E})$
in unambiguously discriminating separable quantum states can be useful in
studying the phenomenon of _nonlocality without entanglement_(NLWE)benn19991 .
For the optimal UD of a separable-state ensemble
$\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, the NLWE phenomenon occurs when $p_{\rm
G}(\mathcal{E})$ cannot be realized only by LOCC, that is, $p_{\rm
L}(\mathcal{E})<p_{\rm G}(\mathcal{E})$. Due to Corollary 2, $q_{\rm
SEP}(\mathcal{E})<p_{\rm G}(\mathcal{E})$ means $p_{\rm L}(\mathcal{E})<p_{\rm
G}(\mathcal{E})$, therefore the occurrence of NLWE. It is a natural future
work to find good bounds on optimal local discrimination in other generalized
state discrimination strategies such as an optimal discrimination with a fixed
rate of inconclusive resultschef1998 ; zhan1999 ; fiur2003 ; baga2012 ;
herz2015 .

## METHODS

In this section, we prove Theorem 1 by showing that

$\displaystyle p_{\rm SEP}(\mathcal{E})\leqslant q_{\rm SEP}(\mathcal{E}),$
(58a) $\displaystyle p_{\rm SEP}(\mathcal{E})\geqslant q_{\rm
SEP}(\mathcal{E}).$ (58b)

### Proof of Inequality (58a)

Let us assume that $\\{M_{i}\\}_{i=0}^{n}$ is a separable unambiguous
measurement realizing $p_{\rm SEP}(\mathcal{E})$ and $H$ is a Hermitian
operator giving $q_{\rm SEP}(\mathcal{E})$. Since this assumption implies
Conditions (11) and (15), we have

$\mathrm{Tr}(M_{0}H)\geqslant
0,~{}\mathrm{Tr}[M_{i}(H-\eta_{i}\rho_{i})]\geqslant 0~{}\forall
i=1,\ldots,n,$ (59)

which lead us to

$p_{\rm
SEP}(\mathcal{E})=\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})\leqslant\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})+\mathrm{Tr}(M_{0}H)+\sum_{i=1}^{n}\mathrm{Tr}[M_{i}(H-\eta_{i}\rho_{i})]=\mathrm{Tr}H=q_{\rm
SEP}(\mathcal{E}),$ (60)

where the second equality is due to $\sum_{i=0}^{n}M_{i}=\mathbbm{1}$.
Therefore, Inequality (58a) holds.

### Proof of Inequality (58b)

We first prove Inequality (58b) when $p_{\rm SEP}(\mathcal{E})=0$. In this
case, we claim that every $M\in\mathrm{SEP}_{j}(\mathcal{E})$ satisfies
$\mathrm{Tr}(\rho_{j}M)=0$ for each $j=1,\ldots,n$. To see this, suppose that
there is a positive-semidefinite product operator
$E\in\mathrm{SEP}_{j}(\mathcal{E})$ with $\mathrm{Tr}(\rho_{j}E)>0$. Since
$\mathbbm{1}-E/\mathrm{Tr}E$ is obvious separable, the following measurement
$\\{M_{i}\\}_{i=0}^{n}$ is a separable unambiguous measurement:

$M_{0}=\mathbbm{1}-\frac{1}{\mathrm{Tr}E}E,~{}~{}M_{j}=\frac{1}{\mathrm{Tr}E}E,~{}~{}M_{i}=0_{\mathcal{H}}~{}~{}\forall
i=1,\ldots,n~{}~{}\mbox{with}~{}~{}i\neq j,$ (61)

where $0_{\mathcal{H}}$ is the zero operator on $\mathcal{H}$.
Moreover, the measurement of (61) gives

$\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})=\eta_{j}\mathrm{Tr}(\rho_{j}E)>0.$
(62)

From Inequality (62) and the definition of $p_{\rm SEP}(\mathcal{E})$, we have
$p_{\rm SEP}(\mathcal{E})>0$, a contradiction. Therefore, there is no
positive-semidefinite product operator $E\in\mathrm{SEP}_{j}(\mathcal{E})$
with $\mathrm{Tr}(\rho_{j}E)>0$. Since every positive-semidefinite separable
operator can be represented as a summation of positive-semidefinite product
operators, we have

$\mathrm{Tr}(\rho_{j}M)=0$ (63)

for all $M\in\mathrm{SEP}_{j}(\mathcal{E})$. Equation (63) together with the
definition of $\mathrm{SEP}_{j}^{*}(\mathcal{E})$ in Eq. (16) imply that

$a\rho_{j}\in\mathrm{SEP}_{j}^{*}(\mathcal{E})$ (64)

for any real number $a$ and $j\in\left\\{1,\ldots,n\right\\}$.
By letting $H=0_{\mathcal{H}}$, we trivially have

$H\in\mathrm{SEP}^{*}.$ (65)

For each $i=1,\ldots,n$, we also have

$H-\eta_{i}\rho_{i}=-\eta_{i}\rho_{i}\in\mathrm{SEP}_{i}^{*}(\mathcal{E})$
(66)

where the inclusion is from Eq. (64). Equations (65) and (66) imply that
$H=0_{\mathcal{H}}$ satisfies Condition (15), therefore

$q_{\rm SEP}(\mathcal{E})\leqslant\mathrm{Tr}H=0,$ (67)

where the inequality is due to the definition of $q_{\rm SEP}(\mathcal{E})$.
Thus, Inequality (67) and the assumption $p_{\rm SEP}(\mathcal{E})=0$ lead us
to Inequality (58b).
Now, we prove Inequality (58b) when $p_{\rm SEP}(\mathcal{E})>0$.

######  Lemma 1.

If $E\in\mathrm{SEP}^{*}$ and $E\neq 0_{\mathcal{H}}$, then $\mathrm{Tr}E>0$,
where $0_{\mathcal{H}}$ is the zero operator on $\mathcal{H}$.

###### Proof.

The proof is by contradiction. We first note that
$\mathrm{Tr}E=\mathrm{Tr}(\mathbbm{1}E)\geqslant 0$ because
$E\in\mathrm{SEP}^{*}$ and the identity operator $\mathbbm{1}$ is obviously
separable. Thus, let us suppose $\mathrm{Tr}E=0$.
For an arbitrary orthonormal product basis $\\{|e_{i}\rangle\\}_{i=1}^{D}$ of
the multipartite Hilbert space
$\mathcal{H}=\bigotimes_{k=1}^{m}\mathcal{H}_{k}$, we have

$\sum_{i=1}^{D}\mathrm{Tr}(E|e_{i}\rangle\\!\langle
e_{i}|)=\mathrm{Tr}(E\mathbbm{1})=\mathrm{Tr}E=0,$ (68)

where $D$ is the dimension of $\mathcal{H}$. From $E\in\mathrm{SEP}^{*}$ and
$|e_{i}\rangle\\!\langle e_{i}|\in\mathrm{SEP}$ for all $i=1,\ldots,D$, we
have

$\mathrm{Tr}(E|e_{i}\rangle\\!\langle e_{i}|)\geqslant 0~{}~{}\forall
i=1,\ldots,D.$ (69)

Equation (68) and Inequality (69) lead us to
$\mathrm{Tr}(E|e_{i}\rangle\\!\langle e_{i}|)=0$ for all $i=1,\ldots,D$. Since
the choice of $\\{|e_{i}\rangle\\}_{i=1}^{D}$ can be arbitrary,
$\mathrm{Tr}(E|e\rangle\\!\langle e|)=0$ for any product vector
$|e\rangle\in\mathcal{H}$, therefore

$\mathrm{Tr}(EF)=0~{}~{}\forall F\in\mathrm{SEP}.$ (70)

We note that $\mathrm{SEP}$ spans the set of all Hermitian operators on
$\mathcal{H}$. To see this, we first note that the set of all positive-
semidefinite operators on $\mathcal{H}_{k}$ spans the set of all Hermitian
operators on $\mathcal{H}_{k}$ for each $k=1,\ldots,m$. Moreover, every
Hermitian operator $A$ on $\mathcal{H}$ can be represented as a summation of
product Hermitian operators,

$A=\sum_{l}\bigotimes_{k=1}^{m}A_{l,k},$ (71)

where $A_{l,k}$ is a Hermitian operator on $\mathcal{H}_{k}$ for each
$k=1,\ldots,m$. Therefore, Eq. (70) leads us to $\mathrm{Tr}(EF)=0$ for any
Hermitian operator $F$ on $\mathcal{H}$. This means $E=0_{\mathcal{H}}$, a
contradiction. Thus, $\mathrm{Tr}E>0$. ∎

Let us consider the set

$S(\mathcal{E})=\big{\\{}\big{(}\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})-p,\mathbbm{1}-\sum_{i=0}^{n}M_{i}\big{)}\in\mathbb{R}\times\mathbb{H}\,\big{|}\,p>p_{\rm
SEP}(\mathcal{E}),~{}M_{0}\in\mathrm{SEP},~{}M_{i}\in\mathrm{SEP}_{i}(\mathcal{E})~{}\forall
i=1,\ldots,n\big{\\}},$ (72)

where $\mathbb{R}$ is the set of all real numbers and $\mathbb{H}$ is the set
of all Hermitian operators on the multipartite Hilbert space $\mathcal{H}$. We
note that $S(\mathcal{E})$ is a convex set due to the convexity of
$\mathrm{SEP}$ and $\mathrm{SEP}_{i}(\mathcal{E})$($i=1,\ldots,n$) in Eqs. (2)
and (10). Moreover, $S(\mathcal{E})$ does not have the origin
$(0,0_{\mathcal{H}})$ of $\mathbb{R}\times\mathbb{H}$ otherwise there exists a
separable unambiguous measurement $\\{M_{i}\\}_{i=0}^{n}$ with
$\sum_{i=1}^{n}\eta_{i}\mathrm{Tr}(\rho_{i}M_{i})>p_{\rm SEP}(\mathcal{E})$,
and this contradicts the optimality of $p_{\rm SEP}(\mathcal{E})$ in Eq. (12).
We also note that the Cartesian product $\mathbb{R}\times\mathbb{H}$ can be
considered as a real vector space with an inner product defined as

$\langle(a,A),(b,B)\rangle=ab+\mathrm{Tr}(AB),~{}~{}(a,A),(b,B)\in\mathbb{R}\times\mathbb{H}.$
(73)

Since $S(\mathcal{E})$ in Eq. (72) and the single-element set
$\\{(0,0_{\mathcal{H}})\\}$ are disjoint convex sets, it follows from
separating hyperplane theoremboyd2004 ; sht  that there is
$(\gamma,\Gamma)\in\mathbb{R}\times\mathbb{H}$ such that

$\displaystyle(\gamma,\Gamma)\neq(0,0_{\mathcal{H}}),$ (74a)
$\displaystyle\langle(\gamma,\Gamma),(r,G)\rangle\leqslant
0~{}~{}\forall(r,G)\in S(\mathcal{E}).$ (74b)

Suppose

$\displaystyle\mathrm{Tr}\Gamma\leqslant\gamma p_{\rm SEP}(\mathcal{E}),$
(75a) $\displaystyle\Gamma\in\mathrm{SEP}^{*},$ (75b)
$\displaystyle\Gamma-\gamma\eta_{i}\rho_{i}\in\mathrm{SEP}_{i}^{*}(\mathcal{E})~{}\forall
i=1,\ldots,n,$ (75c) $\displaystyle\gamma>0,$ (75d)

where $\mathrm{SEP}^{*}$ and $\mathrm{SEP}_{i}^{*}(\mathcal{E})$ are defined
in Eq. (16). From Conditions (75b), (75c), and (75d), the Hermitian operator
$H=\Gamma/\gamma$ satisfies Condition (15). Thus, the definition of $q_{\rm
SEP}(\mathcal{E})$ in Eq. (14) leads us to

$q_{\rm SEP}(\mathcal{E})\leqslant\mathrm{Tr}H.$ (76)

Moreover, Condition (75a) and the definition of $H=\Gamma/\gamma$ imply

$\mathrm{Tr}H\leqslant p_{\rm SEP}(\mathcal{E}).$ (77)

Inequalities (76) and (77) complete the proof of Inequality (58b).
The rest of this section is to prove Conditions (75a), (75b), (75c), and
(75d).

###### Proof of (75a).

From Eq. (73), Inequality (74b) can be rewritten as

$\mathrm{Tr}\Gamma-\mathrm{Tr}(M_{0}\Gamma)-\sum_{i=1}^{n}\mathrm{Tr}[M_{i}(\Gamma-\gamma\eta_{i}\rho_{i})]\leqslant\gamma
p$ (78)

for all $p>p_{\rm SEP}(\mathcal{E})$ and all $\\{M_{i}\\}_{i=0}^{n}$
satisfying Condition (11). If $M_{i}=0_{\mathcal{H}}$ for all
$i=0,1,\ldots,n$, Inequality (78) becomes Inequality (75a) by taking the limit
of $p$ to $p_{\rm SEP}(\mathcal{E})$. ∎

###### Proof of (75b).

For an arbitrary $M_{0}\in\mathrm{SEP}$ and $M_{i}=0$ for all $i=1,\ldots,n$,
$\\{M_{i}\\}_{i=0}^{n}$ clearly satisfies Condition (11). In this case,
Inequality (78) becomes

$\mathrm{Tr}\Gamma-\mathrm{Tr}(M_{0}\Gamma)\leqslant\gamma p_{\rm
SEP}(\mathcal{E})$ (79)

by taking the limit of $p$ to $p_{\rm SEP}(\mathcal{E})$.
Suppose $\Gamma\notin\mathrm{SEP}^{*}$, then there exists $M\in\mathrm{SEP}$
with $\mathrm{Tr}(M\Gamma)<0$. We note that $M\in\mathrm{SEP}$ implies
$tM\in\mathrm{SEP}$ for any $t>0$. Thus, $\\{M_{i}\\}_{i=0}^{n}$ with
$M_{0}=tM$ for $t>0$ and $M_{i}=0$ for all $i=1,\ldots,n$ also satisfies
Condition (11). Now, Inequality (79) can be rewritten as

$\mathrm{Tr}\Gamma-\mathrm{Tr}(tM\Gamma)\leqslant\gamma p_{\rm
SEP}(\mathcal{E}).$ (80)

Since Inequality (80) is true for arbitrary large $t>0$, $\gamma p_{\rm
SEP}(\mathcal{E})$ can also be arbitrary large. However, this contradicts that
both $\gamma$ and $p_{\rm SEP}(\mathcal{E})$ are finite. Thus,
$\Gamma\in\mathrm{SEP}^{*}$, which completes the proof of (75b). ∎

###### Proof of (75c).

The proof method is analogous to that of (75b). For each
$j\in\\{1,\ldots,n\\}$, let us consider an arbitrary
$M_{j}\in\mathrm{SEP}_{j}(\mathcal{E})$ and $M_{i}=0_{\mathcal{H}}$ for all
$i=0,1,\ldots,n$ with $i\neq j$. In this case, $\\{M_{i}\\}_{i=0}^{n}$ clearly
satisfies Condition (11) and Inequality (78) becomes

$\begin{array}[]{ll}\mathrm{Tr}\Gamma-\mathrm{Tr}[M_{j}(\Gamma-\gamma\eta_{j}\rho_{j})]\leqslant\gamma
p_{\rm SEP}(\mathcal{E})\end{array}$ (81)

by taking the limit of $p$ to $p_{\rm SEP}(\mathcal{E})$.
Suppose
$\Gamma-\gamma\eta_{j}\rho_{j}\notin\mathrm{SEP}_{j}^{*}(\mathcal{E})$, then
there exists $M\in\mathrm{SEP}_{j}(\mathcal{E})$ with
$\mathrm{Tr}[M(\Gamma-\gamma\eta_{j}\rho_{j})]<0$. We note that
$M\in\mathrm{SEP}_{j}(\mathcal{E})$ implies
$tM\in\mathrm{SEP}_{j}(\mathcal{E})$ for any $t>0$. Thus,
$\\{M_{i}\\}_{i=0}^{n}$ consisting of $M_{j}=tM$ for $t>0$ and $M_{i}=0$ for
all $i=0,1,\ldots,n$ with $i\neq j$ also satisfies Condition (11). Now,
Inequality (81) can be rewritten as

$\begin{array}[]{ll}\mathrm{Tr}\Gamma-\mathrm{Tr}[tM(\Gamma-\gamma\eta_{j}\rho_{j})]\leqslant\gamma
p_{\rm SEP}(\mathcal{E})\end{array}$ (82)

Since Inequality (82) is true for arbitrary large $t>0$, $\gamma p_{\rm
SEP}(\mathcal{E})$ can also be arbitrary large. However, this contradicts that
both $\gamma$ and $p_{\rm SEP}(\mathcal{E})$ are finite. Thus,
$\Gamma-\gamma\eta_{j}\rho_{j}\in\mathrm{SEP}_{j}^{*}(\mathcal{E})$, which
completes the proof of (75c). ∎

###### Proof of (75d).

Suppose $\Gamma\neq 0_{\mathcal{H}}$. From Lemma 1 together with Inequality
(75b), we have $\mathrm{Tr}\Gamma>0$. Thus, Inequality (75a) and the fact that
$\mathrm{Tr}\Gamma>0$ guarantee $\gamma>0$.
Now, suppose $\Gamma=0_{\mathcal{H}}$. We have $\gamma\neq 0$, otherwise a
contradiction to Condition (74a). The strict positivity of $\gamma$ follows
from Inequality (75a) with $\mathrm{Tr}\Gamma=0$ and $p_{\rm
SEP}(\mathcal{E})>0$. Thus, Inequality (75d) holds regardless of $\Gamma$. ∎

## ACKNOWLEDGEMENTS

This work was supported by Basic Science Research
Program(NRF-2020R1F1A1A010501270) and Quantum Computing Technology Development
Program(NRF-2020M3E4A1080088) through the National Research Foundation of
Korea(NRF) grant funded by the Korea government(Ministry of Science and ICT).

## References

  * (1) Chitambar, E., Leung, D., Mančinska, L., Ozols, M. & Winter, A. Everything you always wanted to know about LOCC (but were afraid to ask). Commun. Math. Phys. 328, 303 (2014).
  * (2) Horodecki, R., Horodecki, P., Horodecki, M. & Horodecki, K. Quantum entanglement. Rev. Mod. Phys. 81, 865 (2009).
  * (3) Chitambar, E. & Gour, G., Quantum resource theories, Rev. Mod. Phys. 91, 025001 (2019).
  * (4) Chefles, A. Quantum state discrimination, Contemporary Physics 41, 401 (2000).
  * (5) Barnett, S. M. & Croke, S. Quantum state discrimination. Adv. Opt. Photon. 1, 238 (2009).
  * (6) Bergou, J. A. Discrimination of quantum states. J. Mod. Opt. 57, 160 (2010).
  * (7) Bae, J. & Kwek, L.-C. Quantum state discrimination and its applications. J. Phys. A: Math. Theor. 48, 083001 (2015).
  * (8) Bennett, C. H., DiVincenzo, D. P., Fuchs, C. A., Mor, T., Rains, E., Shor, P. W., Smolin, J. A. & Wootters, W. K. Quantum nonlocality without entanglement. Phys. Rev. A 59, 1070 (1999).
  * (9) Peres A. & Wootters, W. K. Optimal detection of quantum information. Phys. Rev. Lett. 66, 1119 (1991).
  * (10) Duan, R., Feng, Y., Ji, Z. & Ying, M. Distinguishing arbitrary multipartite basis unambiguously using local operations and classical communication. Phys. Rev. Lett. 98, 230502 (2007).
  * (11) Chitambar, E. & Hsieh, M.-H. Revisiting the optimal detection of quantum information. Phys. Rev. A 88, 020302(R) (2013).
  * (12) S. Ghosh, G. Kar, A. Roy, Sen(De), A. & Sen, U. Distinguishability of Bell states. Phys. Rev. Lett. 87, 277902 (2001).
  * (13) Walgate, J. & Hardy, L. Nonlocality, asymmetry, and distinguishing bipartite states. Phys. Rev. Lett. 89, 147901 (2002).
  * (14) Fan, H. Distinguishability and indistinguishability by local operations and classical communication. Phys. Rev. Lett. 92, 177905 (2004).
  * (15) Duan, R., Feng, Y., Xin, Y. & Ying, M. Distinguishability of quantum states by separable operations. IEEE Trans. Inf. Theory 55, 1320 (2009).
  * (16) Chitambar, E., Duan, R. & Hsieh, M.-H. When do local operations and classical communication suffice for two-qubit state discrimination?. IEEE Trans. Inf. Theory 60, 1549 (2014).
  * (17) Bandyopadhyay, S., Cosentino, A., Johnston, N., Russo, V., Watrous, J. & Yu, N. Limitations on separable measurements by convex optimization. IEEE Trans. Inf. Theory 61, 3593 (2015).
  * (18) Bandyopadhyay, S. & Russo, V. Entanglement cost of discriminating noisy Bell states by local operations and classical communication. Phys. Rev. A 104, 032429 (2021).
  * (19) Zhang, J.-H., Zhang, F.-L., Wang, Z.-X., Lai, L.-M. & Fei, S.-M. Discriminating bipartite mixed states by local operations. Phys. Rev. A 101, 032316 (2020).
  * (20) Ha, D. & Kim, J. S. Bound on local minimum-error discrimination of bipartite quantum states. Phys. Rev. A 105, 032421 (2022).
  * (21) Ivanovic, I. D. How to differentiate between non-orthogonal states. Phys. Lett. A 123, 257 (1987).
  * (22) Peres, A. How to differentiate between non-orthogonal states. Phys. Lett. A 128, 19 (1988).
  * (23) Dieks, D. Overlap and distinguishability of quantum states. Phys. Lett. A 126, 303 (1988).
  * (24) Zhang, J.-H., Zhang, F.-L., Wang, Z.-X. Yang, H. & Fei, S.-M. Unambiguous State Discrimination with Intrinsic Coherence. Entropy 24, 18 (2022).
  * (25) Eldar, Y. C., Stojnic, M. & Hassibi, B. Optimal quantum detectors for unambiguous detection of mixed states. Phys. Rev. A 69, 062318 (2004).
  * (26) Chefles, A. & Barnett, S. M. Strategies for discriminating between non-orthogonal quantum states. J. Mod. Opt. 45, 1295-1302 (1998).
  * (27) Zhang, C.-W., Li, C.-F. & Guo, G.-C. General strategies for discrimination of quantum states. Phys. Lett. A 261, 25-29 (1999).
  * (28) Fiurášek, J. & Ježek, M. Optimal discrimination of mixed quantum states involving inconclusive results. Phys. Rev. A 67, 012321 (2003).
  * (29) Bagan, E., Muñoz-Tapia, R., Olivares-Rentería, G. A. & Bergou, J. A. Optimal discrimination of quantum states with a fixed rate of inconclusive outcomes. Phys. Rev. A 86, 040303 (2012).
  * (30) Herzog, U. Optimal measurements for the discrimination of quantum states with a fixed rate of inconclusive results. Phys. Rev. A 91, 042338 (2015).
  * (31) Boyd, S. & Vandenberghe, L. Convex Optimization (Cambridge University Press, Cambridge, 2004).
  * (32) When $A$ and $B$ are disjoint convex sets in a real vector space $V$ with an inner product $\langle\cdot,\cdot\rangle$, there exist $x\in\mathbb{R}$ and $\vec{v}\in V$ such that $\vec{v}\neq\vec{0}$ and $\langle\vec{a},\vec{v}\rangle\leqslant x\leqslant\langle\vec{b},\vec{v}\rangle$ for all $\vec{a}\in A$ and all $\vec{b}\in B$.