# Entanglement witness and multipartite quantum state discrimination

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 multipartite quantum state discrimination and show that the
minimum-error discrimination by separable measurements is closely related to
the concept of entanglement witness. Based on the properties of entanglement
witness, we establish some necessary and/or sufficient conditions on minimum-
error discrimination by separable measurements. We also provide some
conditions on the upper bound of the maximum success probability over all
possible separable measurements. Our results are illustrated by examples of
multidimensional multipartite quantum states. Finally, we provide a systematic
way in terms of the entanglement witness to construct multipartite quantum
state ensembles showing nonlocality in state discrimination.

##  I Introduction

Quantum state discrimination is one of the fundamental concepts used in
various quantum information and computation theory[1, 2, 3, 4]. In general, we
can always perfectly discriminate orthogonal quantum states using appropriate
measurement. However, nonorthogonal quantum states cannot be perfectly
discriminated by means of any measurement. For this reason, various state
discrimination strategies have been studied for optimal discrimination of
nonorthogonal quantum states, such as minimum-error discrimination,
unambiguous discrimination and maximum-confidence discrimination[5, 6, 7, 8,
9].

_Entanglement witness_(EW) is an important tool to detect the existence of
entanglement inherent in a multipartite quantum state[10, 11, 12, 13].
Mathematically, EW is a Hermitian operator having non-negative mean value for
every separable state, but negative for some entangled states. As EW provides
an useful methodology to detect entanglement that is an important quantum
nonlocality, it is natural to ask whether EW can also be used to characterize
other nonlocal phenomenon of multipartite quantum states.

Quantum nonlocal phenomenon also arises in discriminating multipartite quantum
states; quantum nonlocality occurs when optimal state discrimination cannot be
realized only by _local operations and classical communication_(LOCC)[14, 15,
16, 17, 18, 19, 20]. However, characterizing local discrimination of quantum
states is a hard task and very little is known due to the lack of good
mathematical structure for LOCC.

Here, we establish a specific relation between the properties of EW and
separable measurements, a mathematically well-structured set of measurements
having LOCC measurements as a special case. We show that the minimum-error
discrimination of multipartite quantum states using separable measurements
strongly depends on the existence of EW. More precisely, we establish
conditions on minimum-error discrimination by separable measurements in terms
of EW. We also provide conditions on the upper bound of the maximum success
probability over all possible separable measurements. We illustrate our
results using examples of multidimensional multipartite quantum states.
Finally, we provide a systematic way in terms of EW to construct multipartite
quantum state ensembles showing nonlocality in state discrimination.

This paper is organized as follows. In Section II, we first recall the
definitions and some properties about separable measurements and EW. We also
recall the definition of minimum-error discrimination as well as some useful
properties of the optimal measurements. In Section III, we provide conditions
on the upper bound of the maximum success probability over all possible
separable measurements (Theorems 1 and 2). In Section IV, we provide
conditions on minimum-error discrimination by separable measurements in terms
of EW (Theorems 3 and 4). Our results are illustrated by examples of
multidimensional multipartite quantum states. In Section V, we provide a
systematic way in terms of EW to construct multipartite quantum state
ensembles showing nonlocality in state discrimination. We conclude our results
in Section VI.

##  II Preliminaries

For a multipartite Hilbert space
$\mathcal{H}=\bigotimes_{k=1}^{m}\mathbb{C}^{d_{k}}$ with $m\geqslant 2$ and
positive integers $d_{k}$ for $k=1,\ldots,m$, let $\mathbb{H}$ be the set of
all Hermitian operators acting on $\mathcal{H}$. We use $\mathbb{H}_{+}$ to
denote the set of all positive-semidefinite operators in $\mathbb{H}$, that
is,

$\mathbb{H}_{+}=\\{E\in\mathbb{H}\,|\,\bra{v}E\ket{v}\geqslant
0~{}~{}\forall\ket{v}\in\mathcal{H}\\}.$ (1)

A multipartite quantum state is expressed by a density operator $\rho$, that
is, $\rho\in\mathbb{H}_{+}$ with $\operatorname{Tr}\rho=1$. A measurement is
represented by a positive operator-valued measure $\\{M_{i}\\}_{i}$, that is,
$\\{M_{i}\\}_{i}\subseteq\mathbb{H}_{+}$ satisfying
$\sum_{i}M_{i}=\mathbbm{1}$, where $\mathbbm{1}$ is the identity operator in
$\mathbb{H}$. For the quantum state $\rho$, the probability of obtaining the
measurement outcome corresponding to $M_{j}$ is $\operatorname{Tr}(\rho
M_{j})$.

Figure 1: The relationship of the subsets of $\mathbb{H}$. The shaded area
$\mathbb{SEP}^{*}\setminus\mathbb{H}_{+}$ is the set of all EWs.

###  II.1 Entanglement witness

######  Definition 1.

$E\in\mathbb{H}_{+}$ is called _separable_ if it can represented as a sum of
positive-semidefinite product operators, that is,

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

where $\\{E_{l,k}\\}_{l}$ is a set of positive-semidefinite operators acting
on $\mathbb{C}^{d_{k}}$ of $\mathcal{H}$ for each $k=1,\ldots,m$. Similarly,
we say that the set $\\{E_{i}\\}_{i}\subseteq\mathbb{H}_{+}$ is _separable_ if
$E_{i}$ is separable for all $i$.

We denote the set of all _separable_ operators in $\mathbb{H}_{+}$ as

$\mathbb{SEP}=\\{E\in\mathbb{H}_{+}\,|\,E:\mbox{separable}\\},$ (3)

and its dual set as $\mathbb{SEP}^{*}$, that is,

$\mathbb{SEP}^{*}=\\{E\in\mathbb{H}\,|\,\operatorname{Tr}(EF)\geqslant
0~{}\forall F\in\mathbb{SEP}\\}.$ (4)

A Hermitian operator in $\mathbb{SEP}^{*}$ is also called _block positive_.
Because $\mathbbm{1}\in\mathbb{SEP}$, we have

$\operatorname{Tr}E\geqslant 0$ (5)

for all $E\in\mathbb{SEP}^{*}$, where the equality holds if and only if $E$ is
the zero operator in $\mathbb{H}$ [21].

######  Definition 2.

$W\in\mathbb{H}$ is called an _EW_ if it is block positive but not positive
semidefinite, that is,

$W\in\mathbb{SEP}^{*}\setminus\mathbb{H}_{+}.$ (6)

For each EW $W$, it is known that there exists an entangled operator
$E\in\mathbb{H}_{+}\setminus\mathbb{SEP}$ satisfying

$\operatorname{Tr}(WE)<0,$ (7)

thus the term _entanglement witness_. Figure 1 illustrates the relationship of
the subsets of $\mathbb{H}$.

###  II.2 Minimum-error discrimination of multipartite quantum states

For a _multipartite_ quantum state ensemble,

$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n},$ (8)

let us consider the situation that the state $\rho_{i}$ is prepared with the
probability $\eta_{i}$. To guess the prepared state, we use the decision rule
in terms of a measurement $\\{M_{i}\\}_{i=1}^{n}$ such that the detection of
$M_{i}$ means that the prepared state is guessed to be $\rho_{i}$. The average
probability of correctly guessing the prepared state from $\mathcal{E}$ in Eq.
(8) with respect to a measurement $\\{M_{i}\\}_{i=1}^{n}$ is

$\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i}).$ (9)

The _minimum-error discrimination_ of $\mathcal{E}$ is to achieve the optimal
success probability,

$p_{\rm G}(\mathcal{E})=\max_{\rm
Measurement}\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i}),$ (10)

where the maximum is taken over all possible measurements [5]. We note that a
measurement $\\{M_{i}\\}_{i=1}^{n}$ provides the optimal success probability
$p_{\rm G}(\mathcal{E})$ if and only if it satisfies the following condition
[22, 23, 24, 25],

$\sum_{j=1}^{n}\eta_{j}\rho_{j}M_{j}-\eta_{i}\rho_{i}\in\mathbb{H}_{+}~{}\forall
i=1,\ldots,n.$ (11)

A measurement $\\{M_{i}\\}_{i}$ is called a _separable measurement_ if
$\\{M_{i}\\}_{i}\subseteq\mathbb{SEP}$, and a measurement is called a _LOCC
measurement_ if it can be realized by LOCC. It is known that every LOCC
measurement is a separable measurement [26]. When the available measurements
are limited to separable measurements, we denote the maximum success
probability by

$p_{\rm SEP}(\mathcal{E})=\max_{\begin{subarray}{c}\rm Separable\\\ \rm
measurement\end{subarray}}\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i}),$
(12)

where the maximum is taken over all possible separable measurements.
Similarly, we denote

$p_{\rm L}(\mathcal{E})=\max_{\begin{subarray}{c}\rm LOCC\\\ \rm
measurement\end{subarray}}\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i}),$
(13)

where the maximum is taken over all possible LOCC measurements. From the
definitions, we trivially have

$p_{\rm L}(\mathcal{E})\leqslant p_{\rm SEP}(\mathcal{E})\leqslant p_{\rm
G}(\mathcal{E}).$ (14)

##  III Separable measurements and quantum state discrimination

For a multipartite quantum state ensemble $\mathcal{E}$ in Eq. (8), we define
$\mathbb{H}_{\rm SEP}(\mathcal{E})$ as

$\mathbb{H}_{\rm
SEP}(\mathcal{E})=\\{H\in\mathbb{H}\,|\,H-\eta_{i}\rho_{i}\in\mathbb{SEP}^{*}~{}\forall
i=1,\ldots,n\\},$ (15)

where $\mathbb{SEP}^{*}$ is defined in Eq. (4). In other words,
$\mathbb{H}_{\rm SEP}(\mathcal{E})$ is the set of all $H$ such that
$H-\eta_{i}\rho_{i}$ is block positive in $\mathbb{H}$, for all
$i=1,\ldots,n$. We further define

$\mathbb{H}_{\rm EW}(\mathcal{E})=\\{H\in\mathbb{H}_{\rm
SEP}(\mathcal{E})\,|\,H-\eta_{j}\rho_{j}\notin\mathbb{H}_{+}~{}\mbox{for
some}~{}j\in\\{1,\ldots,n\\}\\},$ (16)

that is, $\mathbb{H}_{\rm EW}(\mathcal{E})$ is the set of all
$H\in\mathbb{H}_{\rm SEP}(\mathcal{E})$ such that $H-\eta_{j}\rho_{j}$ is an
EW for some $j\in\\{1,\ldots,n\\}$. From Definition 2, we can see that

$H\in\mathbb{H}_{\rm SEP}(\mathcal{E})\setminus\mathbb{H}_{\rm
EW}(\mathcal{E})$ (17)

if and only if

$H-\eta_{i}\rho_{i}\in\mathbb{H}_{+}~{}\forall i=1,\ldots,n.$ (18)

Now, let us consider the minimum quantity

$q_{\rm SEP}(\mathcal{E})=\min_{H\in\mathbb{H}_{\rm
SEP}(\mathcal{E})}\operatorname{Tr}H,$ (19)

which is an upper bound of $p_{\rm SEP}(\mathcal{E})$[27], that is,

$p_{\rm SEP}(\mathcal{E})\leqslant q_{\rm SEP}(\mathcal{E}).$ (20)

The following theorem shows that $p_{\rm SEP}(\mathcal{E})$ in Eq. (12) is
equal to $q_{\rm SEP}(\mathcal{E})$ in Eq. (19).

######  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}).$ (21)

###### Proof.

As we already have Inequality (20), it is enough to show that

$p_{\rm SEP}(\mathcal{E})\geqslant q_{\rm SEP}(\mathcal{E}).$ (22)

Let us consider the set,

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

where $\mathbb{R}$ is the set of all real numbers. We note that
$\mathcal{S}(\mathcal{E})$ is a convex set due to the convexity of
$\mathbb{SEP}$ in Eq. (3). Moreover, $\mathcal{S}(\mathcal{E})$ does not have
the origin $(0,0_{\mathbb{H}})$ of $\mathbb{R}\times\mathbb{H}$ otherwise
there is a separable measurement $\\{M_{i}\\}_{i=1}^{n}$ with

$\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})>p_{\rm
SEP}(\mathcal{E}),$ (24)

and this contradicts the optimality of $p_{\rm SEP}(\mathcal{E})$ in Eq. (12).
Here, $0_{\mathbb{H}}$ is the zero operator in $\mathbb{H}$. 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+\operatorname{Tr}(AB)$ (25)

for $(a,A),(b,B)\in\mathbb{R}\times\mathbb{H}$.

Since $\mathcal{S}(\mathcal{E})$ and the single-element set
$\\{(0,0_{\mathbb{H}})\\}$ are disjoint convex sets, it follows from
separating hyperplane theorem[28, 29] that there is
$(\gamma,\Gamma)\in\mathbb{R}\times\mathbb{H}$ satisfying

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

Suppose

$\displaystyle\operatorname{Tr}\Gamma\leqslant\gamma p_{\rm
SEP}(\mathcal{E}),$ (28)
$\displaystyle\Gamma-\gamma\eta_{i}\rho_{i}\in\mathbb{SEP}^{*}~{}\forall
i=1,\ldots,n,$ (29) $\displaystyle\gamma>0.$ (30)

From Conditions (29) and (30), the Hermitian operator $H=\Gamma/\gamma$ is an
element of $\mathbb{H}_{\rm SEP}(\mathcal{E})$ in Eq. (15). Thus, the
definition of $q_{\rm SEP}(\mathcal{E})$ in Eq. (19) leads us to

$q_{\rm SEP}(\mathcal{E})\leqslant\operatorname{Tr}H.$ (31)

Moreover, Condition (28) implies

$\operatorname{Tr}H\leqslant p_{\rm SEP}(\mathcal{E}).$ (32)

Inequalities (31) and (32) imply Inequality (22).

To complete the proof, we show the validity of (28), (29) and (30).

Proof of (28). From Eq. (25), Inequality (27) can be rewritten as

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

for all $p>p_{\rm SEP}(\mathcal{E})$ and all
$\\{M_{i}\\}_{i=1}^{n}\subseteq\mathbb{SEP}$. If $M_{i}=0_{\mathbb{H}}$ for
all $i=1,\ldots,n$, Inequality (33) becomes Inequality (28) by taking the
limit of $p$ to $p_{\rm SEP}(\mathcal{E})$.

Proof of (29). For each $j\in\\{1,\ldots,n\\}$, let us consider an arbitrary
$M_{j}\in\mathbb{SEP}$ and $M_{i}=0_{\mathbb{H}}$ for all $i=1,\ldots,n$ with
$i\neq j$. In this case, $\\{M_{i}\\}_{i=1}^{n}$ is clearly a subset of
$\mathbb{SEP}$, and Inequality (33) becomes

$\operatorname{Tr}\Gamma-\operatorname{Tr}[M_{j}(\Gamma-\gamma\eta_{j}\rho_{j})]\leqslant\gamma
p_{\rm SEP}(\mathcal{E})$ (34)

by taking the limit of $p$ to $p_{\rm SEP}(\mathcal{E})$.

Suppose $\Gamma-\gamma\eta_{j}\rho_{j}\notin\mathbb{SEP}^{*}$, then there is
$M\in\mathbb{SEP}$ with
$\operatorname{Tr}[M(\Gamma-\gamma\eta_{j}\rho_{j})]<0$. We note that
$M\in\mathbb{SEP}$ implies $tM\in\mathbb{SEP}$ for any $t>0$. Thus,
$\\{M_{i}\\}_{i=1}^{n}$ consisting of $M_{j}=tM$ for $t>0$ and $M_{i}=0$ for
all $i=1,\ldots,n$ with $i\neq j$ is also a subset of $\mathbb{SEP}$.

Now, Inequality (34) can be rewritten as

$\operatorname{Tr}\Gamma-\operatorname{Tr}[tM(\Gamma-\gamma\eta_{j}\rho_{j})]\leqslant\gamma
p_{\rm SEP}(\mathcal{E}).$ (35)

Since Inequality (35) 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\mathbb{SEP}^{*}$, which completes the proof
of (29).

Proof of (30). Suppose $\gamma<0$ and consider $\\{M_{i}\\}_{i=1}^{n}$ with
$M_{i}=0_{\mathbb{H}}$ for all $i=1,\ldots,n$. Since
$\\{M_{i}\\}_{i=1}^{n}\subseteq\mathbb{SEP}$, Inequality (33) becomes

$\operatorname{Tr}\Gamma\leqslant-\infty$ (36)

by taking the limit of $p$ to $\infty$. This contradicts that $\Gamma$ is
bounded, therefore $\gamma\geqslant 0$.

Now, let us suppose $\gamma=0$. In this case, Conditions (28) and (29) become

$\operatorname{Tr}\Gamma\leqslant 0,~{}~{}\Gamma\in\mathbb{SEP}^{*}.$ (37)

From Condition (37) and the argument with Inequality (5), we have

$\Gamma=0_{\mathbb{H}},$ (38)

which contradicts Condition (26). Thus, $\gamma>0$. ∎

For a given ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, the
following theorem provides a necessary and sufficient condition for a
separable measurement $\\{M_{i}\\}_{i=1}^{n}$ and $H\in\mathbb{H}_{\rm
SEP}(\mathcal{E})$ to realize $p_{\rm SEP}(\mathcal{E})$ and $q_{\rm
SEP}(\mathcal{E})$, respectively.

######  Theorem 2.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, a separable measurement
$\\{M_{i}\\}_{i=1}^{n}$ and $H\in\mathbb{H}_{\rm SEP}(\mathcal{E})$,
$\\{M_{i}\\}_{i=1}^{n}$ realizes $p_{\rm SEP}(\mathcal{E})$ and $H$ provides
$q_{\rm SEP}(\mathcal{E})$ if and only if

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

###### Proof.

Let us suppose that $\\{M\\}_{i=1}^{n}$ and $H$ give $p_{\rm
SEP}(\mathcal{E})$ and $q_{\rm SEP}(\mathcal{E})$, respectively. Because
$M_{i}\in\mathbb{SEP}$ and $H-\eta_{i}\rho_{i}\in\mathbb{SEP}^{*}$ for all
$i=1,\ldots,n$, we have

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

Moreover, we have

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

where the first equality is from $\sum_{i=1}^{n}M_{i}=\mathbbm{1}$, the second
equality is due to the assumption of $H$ and $\\{M_{i}\\}_{i=1}^{n}$, and the
last equality is by Theorem 1. Inequality (40) and Eq. (41) lead us to
Condition (39).

Conversely, let us assume that $\\{M_{i}\\}_{i=1}^{n}$ and $H$ satisfy
Condition (39). 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})+\sum_{i=1}^{n}\mathrm{Tr}[M_{i}(H-\eta_{i}\rho_{i})]=\mathrm{Tr}H\geqslant
q_{\rm SEP}(\mathcal{E}),$ (42)

where the first equality is by Theorem 1, the second equality is from
Condition (39), the last equality follows from
$\sum_{i=1}^{n}M_{i}=\mathbbm{1}$, and the first and second inequalities are
due to the definitions of $p_{\rm SEP}(\mathcal{E})$ and $q_{\rm
SEP}(\mathcal{E})$, respectively. Inequality (42) leads us to

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

Thus, $\\{M_{i}\\}_{i=1}^{n}$ and $H$ provide $p_{\rm SEP}(\mathcal{E})$ and
$q_{\rm SEP}(\mathcal{E})$, respectively. ∎

We note that $H\in\mathbb{H}_{\rm SEP}(\mathcal{E})$ providing $q_{\rm
SEP}(\mathcal{E})$ is generally not unique (see Example 2 in Section IV.2).
However, the following corollary states the case that $H\in\mathbb{H}_{\rm
SEP}(\mathcal{E})$ providing $q_{\rm SEP}(\mathcal{E})$ is unique.

######  Corollary 1.

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

$p_{\rm SEP}(\mathcal{E})=\eta_{1},$ (44)

if and only if

$\eta_{1}\rho_{1}-\eta_{i}\rho_{i}\in\mathbb{SEP}^{*}~{}~{}\forall
i=2,\ldots,n.$ (45)

In this case, $\eta_{1}\rho_{1}$ is the only element of $\mathbb{H}_{\rm
SEP}(\mathcal{E})$ providing $q_{\rm SEP}(\mathcal{E})$.

###### Proof.

Let $\\{M_{i}\\}_{i=1}^{n}$ be the measurement such that

$M_{1}=\mathbbm{1},~{}~{}M_{2}=\cdots=M_{n}=0_{\mathbb{H}}.$ (46)

We first assume Eq. (44) and consider $H\in\mathbb{H}_{\rm SEP}(\mathcal{E})$
giving $q_{\rm SEP}(\mathcal{E})$. Since $\\{M_{i}\\}_{i=1}^{n}$ is obviously
a separable measurement providing $p_{\rm SEP}(\mathcal{E})$, it follows from
Theorem 2 that $\operatorname{Tr}(H-\eta_{1}\rho_{1})=0$. From
$H-\eta_{1}\rho_{1}\in\mathbb{SEP}^{*}$ and the argument with Inequality (5),
we have $H=\eta_{1}\rho_{1}$. Thus, $H\in\mathbb{H}_{\rm SEP}(\mathcal{E})$
together with the definition of $\mathbb{H}_{\rm SEP}(\mathcal{E})$ leads us
to Condition (45).

Conversely, let us suppose Condition (45) and consider

$H=\eta_{1}\rho_{1},$ (47)

which is in $\mathbb{H}_{\rm SEP}(\mathcal{E})$ by Condition (45). The
separable measurement $\\{M_{i}\\}_{i=1}^{n}$ in Eq. (46) and
$H\in\mathbb{H}_{\rm SEP}(\mathcal{E})$ in Eq. (47) satisfy Condition (39).
Therefore, we have

$p_{\rm
SEP}(\mathcal{E})=\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})=\eta_{1},$
(48)

where the first equality is by Theorem 2. ∎

When Eq. (44) of Corollary 1 holds, the maximum success probability $p_{\rm
SEP}(\mathcal{E})$ can be achieved without the help of measurement, simply by
guessing $\rho_{1}$ is prepared. As we can check in the proof of Corollary 1,
the choice of $\rho_{1}$ in Corollary 1 can be arbitrary. That is, any of
$\\{\rho_{i}\\}_{i=1}^{n}$ can be used to play the role of $\rho_{1}$ in
Corollary 1.

##  IV Minimum-error discrimination by separable measurements

For a quantum state ensemble $\mathcal{E}$ in Eq. (8), the minimum-error
discrimination can be realized by separable measurements if and only if

$p_{\rm SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E}),$ (49)

where $p_{\rm G}(\mathcal{E})$ and $p_{\rm SEP}(\mathcal{E})$ are defined in
Eqs. (10) and (12), respectively. In this section, we provide some necessary
and/or sufficient conditions for Eq. (49) in terms of EW.

###  IV.1 Necessary condition for $p_{\rm SEP}(\mathcal{E})=p_{\rm
G}(\mathcal{E})$

######  Theorem 3.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, if there exists separable
measurement $\\{M_{i}\\}_{i=1}^{n}$ satisfying

$\sum_{i=1}^{n}\eta_{i}\rho_{i}M_{i}\in\mathbb{H}_{\rm EW}(\mathcal{E}),$ (50)

where $\mathbb{H}_{\rm EW}(\mathcal{E})$ is defined in Eq. (16), then

$p_{\rm
SEP}(\mathcal{E})=\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})<p_{\rm
G}(\mathcal{E}).$ (51)

Thus, non-existence of such separable measurement $\\{M_{i}\\}_{i=1}^{n}$
satisfying Condition (50) is a necessary condition for $p_{\rm
SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E})$.

###### Proof.

Let us suppose $\\{M_{i}\\}_{i=1}^{n}$ is a separable measurement satisfying
Condition (50), and consider

$H=\sum_{i=1}^{n}\eta_{i}\rho_{i}M_{i}.$ (52)

Equation (51) holds because

$\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})\leqslant p_{\rm
SEP}(\mathcal{E})=q_{\rm
SEP}(\mathcal{E})\leqslant\operatorname{Tr}H=\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i}),$
(53)

where the first inequality is due to the definition of $p_{\rm
SEP}(\mathcal{E})$, the second inequality follows from the definition of
$q_{\rm SEP}(\mathcal{E})$ together with the condition that
$H\in\mathbb{H}_{\rm EW}(\mathcal{E})\subseteq\mathbb{H}_{\rm
SEP}(\mathcal{E})$, the first equality is from Theorem 1, and the second
equality is by Eq. (52). This proves the equality of (51).

If we assume $p_{\rm SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E})$ in (51),
$\\{M_{i}\\}_{i=1}^{n}$ gives the optimal success probability $p_{\rm
G}(\mathcal{E})$. From the optimality condition in Eq. (11) and the argument
with Eq. (17), we have

$\sum_{i=1}^{n}\eta_{i}\rho_{i}M_{i}\in\mathbb{H}_{\rm
SEP}(\mathcal{E})\setminus\mathbb{H}_{\rm EW}(\mathcal{E}),$ (54)

which contradicts Condition (50). Thus, we have the inequality of (51). ∎

Example 1. For any integers $m,d\geqslant 2$, let us consider the $m$-qu$d$it
state ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{d+2}$ consisting of
$d+2$ states,

$\displaystyle\eta_{i}=\frac{1}{d^{m}+d},~{}\rho_{i}=\ket{i-1}\\!\bra{i-1}^{\otimes
m},~{}i=1,\ldots,d,$
$\displaystyle\eta_{d+1}=\frac{d^{m}-d}{d^{m}+d},~{}\rho_{d+1}=\frac{1}{d^{m}-d}\Big{(}\mathbbm{1}-\sum_{j=0}^{d-1}\ket{j}\\!\bra{j}^{\otimes
m}\Big{)},$ (55)
$\displaystyle\eta_{d+2}=\frac{d}{d^{m}+d},~{}\rho_{d+2}=\ket{\Phi}\\!\bra{\Phi},$

where

$\ket{\Phi}=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}\ket{i}^{\otimes m}.$ (56)

For a separable measurement $\\{M_{i}\\}_{i=1}^{d+2}$ with

$M_{i}=\ket{i-1}\\!\bra{i-1}^{\otimes
m},~{}i=1,\ldots,d,~{}M_{d+1}=\mathbbm{1}-\sum_{j=0}^{d-1}\ket{j}\\!\bra{j}^{\otimes
m},~{}M_{d+2}=0_{\mathbb{H}},$ (57)

we show that Condition (50) holds with respect to the ensemble in Eq. (IV.1).

It is straightforward to verify that

$\displaystyle\sum_{j=1}^{d+2}\eta_{j}\rho_{j}M_{j}-\eta_{i}\rho_{i}=\frac{1}{d^{m}+d}\big{(}\mathbbm{1}-\ket{i-1}\\!\bra{i-1}^{\otimes
m}\big{)}\in\mathbb{H}_{+},~{}i=1,\ldots,d,$
$\displaystyle\sum_{j=1}^{d+2}\eta_{j}\rho_{j}M_{j}-\eta_{d+1}\rho_{d+1}=\frac{1}{d^{m}+d}\sum_{j=0}^{d-1}\ket{j}\\!\bra{j}^{\otimes
m}\in\mathbb{H}_{+},$ (58)
$\displaystyle\sum_{j=1}^{d+2}\eta_{j}\rho_{j}M_{j}-\eta_{d+2}\rho_{d+2}=\frac{1}{d^{m}+d}\big{(}\mathbbm{1}-d\ket{\Phi}\\!\bra{\Phi}\big{)}\in\mathbb{SEP}^{*},$

where the last inclusion is from the fact that

$d\operatorname{Tr}(\ket{\Phi}\\!\bra{\Phi}E)\leqslant\operatorname{Tr}E~{}~{}\forall
E\in\mathbb{SEP}.$ (59)

To show the validity of Inequality (59), we assume that
$\\{\ket{e_{i}^{(k)}}\\}_{i=1}^{d}$ is an orthonormal basis of
$\mathbb{C}^{d}$ for each $k=1,\ldots,m$. Since
$\\{\ket{e_{i_{1}}^{(1)}}\otimes\cdots\otimes\ket{e_{i_{m}}^{(m)}}\\}_{i_{1},\ldots,i_{m}}$
is an orthonormal basis of the multipartite Hilbert space $\mathcal{H}$, there
is a set of complex numbers
$\\{c_{i_{1},\ldots,i_{m}}\\}_{i_{1},\ldots,i_{m}}$ such that

$\ket{\Phi}=\sum_{i_{1},\ldots,i_{m}=1}^{d}c_{i_{1},\ldots,i_{m}}\ket{e_{i_{1}}^{(1)}}\otimes\cdots\otimes\ket{e_{i_{m}}^{(m)}}.$
(60)

For each $i_{1}\in\\{1,\ldots,d\\}$, we have

$\sum_{i_{2},\ldots,i_{m}=1}^{d}|c_{i_{1},\ldots,i_{m}}|^{2}=\bra{\Phi}\Big{[}\ket{e_{i_{1}}^{(1)}}\\!\bra{e_{i_{1}}^{(1)}}\otimes\big{(}\sum_{j=0}^{d-1}\ket{j}\\!\bra{j}\big{)}^{\otimes
m-1}\Big{]}\ket{\Phi}=\frac{1}{d},$ (61)

where the first equality follows from Eq. (60) and the second equality is due
to Eq. (56). Equation (61) leads us to

$|c_{i_{1},\ldots,i_{m}}|^{2}\leqslant\frac{1}{d}~{}~{}\forall
i_{1},\ldots,i_{m}=1,\ldots,d.$ (62)

Since the choice of $\\{\ket{e_{i}^{(k)}}\\}_{i=1}^{d}$ can be arbitrary for
each $k=1,\ldots,m$, we have

$d\operatorname{Tr}(|\Phi\rangle\\!\langle\Phi|e\rangle\\!\langle
e|)\leqslant\langle e|e\rangle$ (63)

for any product vector $\ket{e}\in\mathcal{H}$. Therefore, Inequality (59)
holds.

Now, the inclusions in (IV.1) together with
$\mathbb{H}_{+}\subseteq\mathbb{SEP}^{*}$ imply

$\sum_{j=1}^{d+2}\eta_{j}\rho_{j}M_{j}-\eta_{i}\rho_{i}\in\mathbb{SEP}^{*}~{}~{}\forall
i=1,\ldots,d+2.$ (64)

Furthermore, a straightforward calculation leads us to

$\bra{\Phi}\Big{(}\sum_{j=1}^{d+2}\eta_{j}\rho_{j}M_{j}-\eta_{d+2}\rho_{d+2}\Big{)}\ket{\Phi}=-\frac{d-1}{d^{m}+d}<0.$
(65)

From Eq. (65), we have

$\sum_{j=1}^{d+2}\eta_{j}\rho_{j}M_{j}-\eta_{d+2}\rho_{d+2}\notin\mathbb{H}_{+}.$
(66)

From Eqs. (64) and (66), the ensemble in Eq. (IV.1) and the measurement in Eq.
(57) satisfy Condition (50). Thus, Theorem 3 leads us to

$p_{\rm
SEP}(\mathcal{E})=\sum_{i=1}^{d+2}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})=\frac{d^{m}}{d^{m}+d}<p_{\rm
G}(\mathcal{E}).$ (67)

We also note that the separable measurement in Eq. (57) is a LOCC measurement
because it can be implemented by performing the same local measurement
$\\{\ket{l}\\!\bra{l}\\}_{l=0}^{d-1}$ on each party. Thus, we have

$p_{\rm L}(\mathcal{E})=p_{\rm SEP}(\mathcal{E})=\frac{d^{m}}{d^{m}+d}.$ (68)

###  IV.2 Necessary and sufficient condition for $p_{\rm
SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E})$

######  Theorem 4.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$, $p_{\rm
SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E})$ if and only if there exists
$H\in\mathbb{H}_{\rm SEP}(\mathcal{E})$ such that it provides $q_{\rm
SEP}(\mathcal{E})$ but does not satisfy

$H\in\mathbb{H}_{\rm EW}(\mathcal{E}),$ (69)

or equivalently, there is $H\in\mathbb{H}$ satisfying Condition (17) and
$\operatorname{Tr}H=q_{\rm SEP}(\mathcal{E})$.

###### Proof.

Let $\\{M_{i}\\}_{i=1}^{n}$ be a separable measurement giving $p_{\rm
SEP}(\mathcal{E})$. We first suppose $p_{\rm SEP}(\mathcal{E})=p_{\rm
G}(\mathcal{E})$ and consider

$H=\sum_{i=1}^{n}\eta_{i}\rho_{i}M_{i}.$ (70)

Since the measurement $\\{M_{i}\\}_{i=1}^{n}$ gives the optimal success
probability $p_{\rm G}(\mathcal{E})$, the optimality condition in Eq. (11)
leads us to

$H-\eta_{i}\rho_{i}=\sum_{j=1}^{n}\eta_{j}\rho_{j}M_{j}-\eta_{i}\rho_{i}\in\mathbb{H}_{+}~{}~{}\forall
i=1,\ldots,n.$ (71)

Therefore, $H$ satisfies Condition (17). Moreover, we have

$\operatorname{Tr}H=\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})=p_{\rm
SEP}(\mathcal{E})=q_{\rm SEP}(\mathcal{E}),$ (72)

where the first equality is from Eq. (70), the second equality is by the
assumption of $\\{M_{i}\\}_{i=1}^{n}$, and the last equality is due to Theorem
1.

Conversely, let us assume $H$ is an element of $\mathbb{H}$ satisfying
Condition (17) and $\operatorname{Tr}H=q_{\rm SEP}(\mathcal{E})$. Thus, the
positivenesses in (18) is satisfied in term of $H$. For each $i=1,\ldots,n$,
the positive-semidefinite operators $M_{i}$ and $H-\eta_{i}\rho_{i}$ are
orthogonal since they satisfy Condition (39) from Theorem 2.

The optimality condition in Eq. (11) holds for the measurement
$\\{M_{i}\\}_{i=1}^{n}$ because

$\sum_{j=1}^{n}\eta_{j}\rho_{j}M_{j}-\eta_{i}\rho_{i}=\sum_{j=1}^{n}\eta_{j}\rho_{j}M_{j}+\sum_{k=1}^{n}(H-\eta_{k}\rho_{k})M_{k}-\eta_{i}\rho_{i}=H-\eta_{i}\rho_{i}\in\mathbb{H}_{+}~{}~{}\forall
i=1,\ldots,n,$ (73)

where the first equality is from the orthogonality of $M_{i}$ and
$H-\eta_{i}\rho_{i}$ for each $i=1,\ldots,n$ and the second equality is from
$\sum_{i=1}^{n}M_{i}=\mathbbm{1}$. Thus, we have

$p_{\rm
G}(\mathcal{E})=\sum_{i=1}^{n}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})=p_{\rm
SEP}(\mathcal{E}),$ (74)

where the second equality is due to the assumption of $\\{M_{i}\\}_{i=1}^{n}$.
∎

If $p_{\rm SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E})$, Theorem 4 implies that
there must exist $H\in\mathbb{H}_{\rm
SEP}(\mathcal{E})\setminus\mathbb{H}_{\rm EW}(\mathcal{E})$ providing $q_{\rm
SEP}(\mathcal{E})$. In this case, there possibly exists another Hermitian
operator $H^{\prime}$ satisfying $H^{\prime}\in\mathbb{H}_{\rm
EW}(\mathcal{E})$ and $\operatorname{Tr}H^{\prime}=q_{\rm SEP}(\mathcal{E})$,
which is illustrated in the following example.

Example 2. For any integers $m,d\geqslant 2$, let us consider the $m$-qu$d$it
state ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{d^{m}-d+1}$
consisting of $d^{m}-d+1$ states,

$\eta_{1}=\frac{d}{d^{m}},~{}\rho_{1}=\ket{\Phi}\\!\bra{\Phi},~{}\eta_{i}=\frac{1}{d^{m}},~{}\rho_{i}=\ket{\beta_{i}}\\!\bra{\beta_{i}},~{}i=2,\ldots,d^{m}-d+1,$
(75)

where $\ket{\Phi}$ is defined in Eq. (56) and
$\\{\ket{\beta_{i}}\\}_{i=2}^{d^{m}-d+1}$ is a set of orthonormal product
vectors orthogonal to $\ket{j}^{\otimes m}$ for all $j=0,\ldots,d-1$.

For a separable measurement $\\{M_{i}\\}_{i=1}^{d^{m}-d+1}$ with

$M_{1}=\sum_{j=0}^{d-1}\ket{j}\\!\bra{j}^{\otimes
m},~{}M_{i}=\ket{\beta_{i}}\\!\bra{\beta_{i}},~{}i=2,\ldots,d^{m}-d+1,$ (76)

we can easily see that the success probability obtained from the separable
measurement in discriminating the states from the ensemble $\mathcal{E}$ in
Eq. (75) is one, that is,

$\sum_{i=1}^{d^{m}-d+1}\eta_{i}\operatorname{Tr}(\rho_{i}M_{i})=1.$ (77)

The success probability in Eq. (77) is a lower bound of $p_{\rm
SEP}(\mathcal{E})$ in Eq. (12), therefore

$p_{\rm SEP}(\mathcal{E})\geqslant 1.$ (78)

Since $p_{\rm G}(\mathcal{E})$ is bounded above by 1, Inequalities (14) and
(78) imply

$p_{\rm SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E})=1.$ (79)

Furthermore, we have

$q_{\rm SEP}(\mathcal{E})=p_{\rm SEP}(\mathcal{E})=1,$ (80)

where the first equality is by Theorem 1 and the second equality is from Eq.
(79).

Let us first consider the Hermitian operator

$H=\sum_{i=1}^{d^{m}-d+1}\eta_{i}\rho_{i}.$ (81)

Equations (80) and (81) imply

$\operatorname{Tr}H=1=q_{\rm SEP}(\mathcal{E}).$ (82)

Moreover, a straightforward calculation leads us to

$H-\eta_{i}\rho_{i}=\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{d^{m}-d+1}\eta_{j}\rho_{j}\in\mathbb{H}_{+}~{}\forall
i=1,\ldots,n.$ (83)

Due to Eqs. (82) and (83), $H$ is an element of $\mathbb{H}_{\rm
SEP}(\mathcal{E})\setminus\mathbb{H}_{\rm EW}(\mathcal{E})$ giving $q_{\rm
SEP}(\mathcal{E})$. Thus, we have $H$ satisfying the conditions of Theorem 4.

Now, let us consider the Hermitian operator

$H_{t}=t\sum_{i=1}^{d^{m}-d+1}\eta_{i}\rho_{i}+\frac{1-t}{d^{m}}\mathbbm{1},$
(84)

where $0\leqslant t<1$. Equations (80) and (84) imply

$\operatorname{Tr}H_{t}=1=q_{\rm SEP}(\mathcal{E})$ (85)

for $0\leqslant t<1$. Moreover, a straightforward calculation leads us to

$\displaystyle
H_{t}-\eta_{1}\rho_{1}=t\sum_{j=2}^{d^{m}-d+1}\eta_{j}\rho_{j}+\frac{1-t}{d^{m}}(\mathbbm{1}-d\ket{\Phi}\\!\bra{\Phi})\in\mathbb{SEP}^{*},$
$\displaystyle H_{t}-\eta_{i}\rho_{i}=t\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{d^{m}-d+1}\eta_{j}\rho_{j}+\frac{1-t}{d^{m}}(\mathbbm{1}-\ket{\beta_{i}}\\!\bra{\beta_{i}})\in\mathbb{H}_{+}~{}\forall
i\neq 1,$ (86)

where the first inclusion follows from Inequality (59). Due to Eq. (IV.2)
together with $\mathbb{H}_{+}\subseteq\mathbb{SEP}^{*}$, we have

$H_{t}\in\mathbb{H}_{\rm SEP}(\mathcal{E}).$ (87)

We also note that

$\bra{\Phi}(H_{t}-\eta_{1}\rho_{1})\ket{\Phi}=-\frac{(1-t)(d-1)}{d^{m}}<0$
(88)

for $0\leqslant t<1$. Equations (85), (87) and Inequality (88) imply that
$H_{t}$ is an element of $\mathbb{H}_{\rm EW}(\mathcal{E})$ giving $q_{\rm
SEP}(\mathcal{E})$. By letting $H^{\prime}=H_{t}$, we have another Hermitian
operator $H^{\prime}$, besides $H$ in Eq. (81), satisfying
$H^{\prime}\in\mathbb{H}_{\rm EW}(\mathcal{E})$ and
$\operatorname{Tr}H^{\prime}=q_{\rm SEP}(\mathcal{E})$.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$ where $H$ is the only element
of $\mathbb{H}_{\rm SEP}(\mathcal{E})$ providing $q_{\rm SEP}(\mathcal{E})$,
Theorem 4 tell us that $p_{\rm SEP}(\mathcal{E})<p_{\rm G}(\mathcal{E})$ if
and only if there exists an EW in $\\{H-\eta_{i}\rho_{i}\\}_{i=1}^{n}$. From
Corollary 1, $\eta_{1}\rho_{1}$ is the only element of $\mathbb{H}_{\rm
SEP}(\mathcal{E})$ providing $q_{\rm SEP}(\mathcal{E})$ when Condition (45)
holds. Thus, we have the following corollary.

######  Corollary 2.

For a multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$ with Condition (45), $p_{\rm
SEP}(\mathcal{E})<p_{\rm G}(\mathcal{E})$ if and only if there exists an EW in
$\\{\eta_{1}\rho_{1}-\eta_{i}\rho_{i}\\}_{i=2}^{n}$.

Example 3. For any integers $m,d\geqslant 2$, let us consider the $m$-qu$d$it
state ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{d+1}$ consisting of
$d+1$ states,

$\eta_{1}=\frac{1}{2},~{}\rho_{1}=\frac{1}{d^{m}}\mathbbm{1},~{}\eta_{i}=\frac{1}{2d},~{}\rho_{i}=\frac{d^{2}-d}{d^{m}-d}\ket{\Phi_{i}}\\!\bra{\Phi_{i}}+\frac{d^{m}-d^{2}}{d^{m}(d^{m}-d)}\mathbbm{1},~{}i=2,\ldots,d+1,$
(89)

where

$\ket{\Phi_{j}}=\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1}\exp\Big{(}\frac{{\rm i}2\pi
jk}{d}\Big{)}\ket{k}^{\otimes m}.$ (90)

For each $i=2,\ldots,d+1$, a straightforward calculation leads us to

$\eta_{1}\rho_{1}-\eta_{i}\rho_{i}=\frac{d-1}{2d(d^{m}-d)}(\mathbbm{1}-d\ket{\Phi_{i}}\\!\bra{\Phi_{i}})\in\mathbb{SEP}^{*},$
(91)

where the inclusion is from the fact that

$d\operatorname{Tr}(\ket{\Phi_{i}}\\!\bra{\Phi_{i}}E)\leqslant\operatorname{Tr}E~{}~{}\forall
E\in\mathbb{SEP}.$ (92)

We can show the validity of Inequality (92) in a similar way to that of
Inequality (59).

Now, the inclusion in (91) together with Corollary 1 imply

$p_{\rm SEP}(\mathcal{E})=\eta_{1}=\frac{1}{2}.$ (93)

Furthermore, a straightforward calculation leads us to

$\bra{\Phi_{i}}\Big{(}\eta_{1}\rho_{1}-\eta_{i}\rho_{i}\Big{)}\ket{\Phi_{i}}=-\frac{(d-1)^{2}}{2d(d^{m}-d)}<0~{}~{}\forall
i=2,\ldots,d+1.$ (94)

From Eq. (94), we have

$\eta_{1}\rho_{1}-\eta_{i}\rho_{i}\notin\mathbb{H}_{+}~{}~{}\forall
i=2,\ldots,d+1.$ (95)

From Eqs. (91) and (95), $\eta_{1}\rho_{1}-\eta_{i}\rho_{i}$ is an EW for any
$i=2,\ldots,d+1$. Thus, Corollary 2 leads us to

$p_{\rm SEP}(\mathcal{E})=\frac{1}{2}<p_{\rm G}(\mathcal{E}).$ (96)

##  V Construction of nonlocal quantum state ensemble

In this section, we provide a systematic way in terms of EW to construct
multipartite quantum state ensembles showing nonlocality in state
discrimination, that is, $p_{\rm L}(\mathcal{E})<p_{\rm G}(\mathcal{E})$. For
a given EW $W$, let us consider the multipartite quantum state ensemble
$\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{2}$ where

$\eta_{1}=\frac{\operatorname{Tr}(P+W)}{\operatorname{Tr}(2P+W)},~{}\rho_{1}=\frac{P+W}{\operatorname{Tr}(P+W)},~{}\eta_{2}=\frac{\operatorname{Tr}P}{\operatorname{Tr}(2P+W)},~{}\rho_{2}=\frac{P}{\operatorname{Tr}P},$
(97)

with any $P\in\mathbb{H}_{+}$ satisfying

$P+W\in\mathbb{H}_{+}.$ (98)

Since $\eta_{1}\rho_{1}-\eta_{2}\rho_{2}$ is proportional to the EW $W$,
$p_{\rm SEP}(\mathcal{E})<p_{\rm G}(\mathcal{E})$ holds from Corollary 2.
Thus, Inequality (14) leads us to $p_{\rm L}(\mathcal{E})<p_{\rm
G}(\mathcal{E})$.

Corollary 2 can also be used to construct a multipartite quantum state
ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$ with $n>2$ showing
nonlocality in quantum state discrimination. For a set of EWs
$\\{W_{i}\\}_{i=2}^{n}$, let us consider the multipartite quantum state
ensemble $\mathcal{E}=\\{\eta_{i},\rho_{i}\\}_{i=1}^{n}$ where

$\eta_{1}=\frac{\operatorname{Tr}\mathbbm{1}}{\operatorname{Tr}(n\mathbbm{1}-\sum_{j=2}^{n}\lambda_{j}W_{j})},~{}\rho_{1}=\frac{\mathbbm{1}}{\operatorname{Tr}\mathbbm{1}},~{}\eta_{i}=\frac{\operatorname{Tr}(\mathbbm{1}-\lambda_{i}W_{i})}{\operatorname{Tr}(n\mathbbm{1}-\sum_{j=2}^{n}\lambda_{j}W_{j})},~{}\rho_{i}=\frac{\mathbbm{1}-\lambda_{i}W_{i}}{\operatorname{Tr}(\mathbbm{1}-\lambda_{i}W_{i})},~{}i=2,\ldots,n,$
(99)

with any set of positive real numbers $\\{\lambda_{i}\\}_{i=2}^{n}$ satisfying

$\mathbbm{1}-\lambda_{i}W_{i}\in\mathbb{H}_{+}~{}~{}\forall i=2,\ldots,n.$
(100)

Because $\eta_{1}\rho_{1}-\eta_{i}\rho_{i}$ is proportional to $W_{i}$ for any
$i\in\\{2,\ldots,n\\}$, $p_{\rm SEP}(\mathcal{E})<p_{\rm G}(\mathcal{E})$
holds from Corollary 2. Thus, Inequality (14) leads us to $p_{\rm
L}(\mathcal{E})<p_{\rm G}(\mathcal{E})$.

##  VI Conclusions

We have considered multipartite quantum state discrimination and shown that
the minimum-error discrimination by separable measurements strongly depends on
the existence of EW. We have established the necessary and/or sufficient
conditions on minimum-error discrimination by separable measurements, that is,
$p_{\rm SEP}(\mathcal{E})=p_{\rm G}(\mathcal{E})$, in terms of EW (Theorems 3
and 4). We have also provided the conditions on the upper bound of the maximum
success probability over all possible separable measurements (Theorems 1 and
2). Our results have been illustrated by examples of multidimensional
multipartite quantum states. Finally, we have provided a systematic way in
terms of EW to construct multipartite quantum state ensembles showing
nonlocality in state discrimination.

Quantum nonlocality is a key ingredient making quantum states outperform the
classical ones in various quantum information processing tasks such as quantum
teleportation and quantum cryptography[30, 31]. It is also known that quantum
nonlocality plays an important role in quantum algorithms which are more
powerful than any classical ones[32, 33]. As the violation of the conditions
in Theorem 4 implies $p_{\rm SEP}(\mathcal{E})<p_{\rm G}(\mathcal{E})$, which
consequently means $p_{\rm L}(\mathcal{E})<p_{\rm G}(\mathcal{E})$, our
results provides a useful methodology to guarantee the occurrence of
nonlocality in state discrimination.

Our results establish a specific relation between the properties of EW and
minimum-error discrimination by separable measurements, therefore it is
natural to investigate the relationship between EW and other measurements. It
is also an interesting future work to construct good conditions, in terms of
EW, for optimal state discrimination in other state discrimination strategies.

## 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] A. Chefles, Quantum state discrimination, Contemp. Phys. 41, 401 (2000).
  * [2] S. M. Barnett and S. Croke, Quantum state discrimination, Adv. Opt. Photon. 1, 238 (2009).
  * [3] J. A. Bergou, Discrimination of quantum states, J. Mod. Opt. 57, 160 (2010).
  * [4] J. Bae and L.-C. Kwek, Quantum state discrimination and its applications, J. Phys. A: Math. Theor. 48, 083001 (2015).
  * [5] C. W. Helstrom, Quantum detection and estimation theory, J. Stat. Phys. 1, 231 (1969).
  * [6] I. D. Ivanovic, How to differentiate between nonorthogonal states, Phys. Lett. A 123, 257 (1987).
  * [7] D. Dieks, Overlap and distinguishability of quantum states, Phys. Lett. A 126, 303 (1988).
  * [8] A. Peres, How to differentiate between nonorthogonal states, Phys. Lett. A 128, 19 (1988).
  * [9] S. Croke, E. Andersson, S. M. Barnett, C. R. Gilson, and J. Jeffers, Maximum Confidence Quantum Measurements, Phys. Rev. Lett. 96, 070401 (2006).
  * [10] M. Horodecki, P. Horodecki, and R. Horodecki, Separability of mixed states: necessary and sufficient conditions, Phys. Lett. A 223, 1 (1996).
  * [11] B. M. Terhal, Bell inequalities and the separability criterion, Phys. Lett. A 271, 319 (2000).
  * [12] M. Lewenstein, B. Kraus, J. I. Cirac, and P. Horodecki, Optimization of entanglement witnesses, Phys. Rev. A 62, 052310 (2000).
  * [13] D. Chruściński and G. Sarbicki, Entanglement witnesses: construction, analysis and classification, J. Phys. A: Math. Theor. 47, 483001 (2014).
  * [14] A. Peres and W. K. Wootters, Optimal detection of quantum information, Phys. Rev. Lett. 66, 1119 (1991).
  * [15] C. H. Bennett, D. P. DiVincenzo, C. A. Fuchs, T. Mor, E. Rains, P. W. Shor, J. A. Smolin, and W. K. Wootters, Quantum nonlocality without entanglement, Phys. Rev. A 59, 1070 (1999).
  * [16] S. Ghosh, G. Kar, A. Roy, A. Sen(De), and U. Sen, Distinguishability of Bell States, Phys. Rev. Lett. 87, 277902 (2001).
  * [17] E. Chitambar and M.-H. Hsieh, Revisiting the optimal detection of quantum information, Phys. Rev. A 88, 020302(R) (2013).
  * [18] D.-H. Jiang and G.-B. Xu, Nonlocal sets of orthogonal product states in an arbitrary multipartite quantum system, Phys. Rev. A 102, 032211 (2020).
  * [19] H.-J. Zuo, J.-H. Liu, X.-F. Zhen, and S.-M. Fei, Nonlocal sets of orthogonal multipartite product states with less members, Quantum Inf. Process. 20, 382 (2021).
  * [20] Y.-L. Wang, W. Chen, and M.-S. Li, Small set of orthogonal product states with nonlocality, Quantum Inf. Process. 22, 15 (2023).
  * [21] D. Ha and J. S. Kim, Bound on optimal local discrimination of multipartite quantum states, Sci. Rep. 12, 14130 (2022).
  * [22] A. S. Holevo, Remarks on Optimal Quantum Measurements, Probl. Peredachi Inf. 10, 51 (1974).
  * [23] H. Yuen, R. Kennedy, and M. Lax, Optimum testing of multiple hypotheses in quantum detection theory, IEEE Trans. Inf. Theory 21, 125 (1975).
  * [24] S. M. Barnett and S. Croke, On the conditions for discrimination between quantum states with minimum error, J. Phys. A: Math. and Theor. 42, 062001 (2009).
  * [25] J. Bae, Structure of minimum-error quantum state discrimination, New J. Phys. 15, 073037 (2013).
  * [26] E. Chitambar, D. Leung, L. Mančinska, M. Ozols, and A. Winter, Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask), Commun. Math. Phys. 328, 303 (2014).
  * [27] S. Bandyopadhyay, A. Cosentino, N. Johnston, V. Russo, J. Watrous, and N. Yu, Limitations on Separable Measurements by Convex Optimization, IEEE Trans. Inf. Theory 61, 3593 (2015).
  * [28] S. Boyd and L. Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, 2004).
  * [29] 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$.
  * [30] A. K. Ekert, Quantum cryptography based on Bell’s theorem, Phys. Rev. Lett. 67, 661 (1991).
  * [31] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels, Phys. Rev. Lett. 70, 1895 (1993).
  * [32] D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. Lond. A 439, 553 (1992).
  * [33] P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.


* [5] S.N. Artemov.  Logic of Proofs.  Annals of Pure and Applied Logic, 67:25–59, 1994.
  * [6] S.N. Artemov.  Kolmogorov and G’́odel’s approach to intuitionistic logic: current developments.  Russian Mathematical Surveys, 59(2):203–229, 2004.
  * [7] S.N. Artemov.  The Logic of Justification.  The Review of Symbolic Logic, 4(4):477–513, 2008.
  * [8] S.N. Artemov and L.D. Beklemeshev.  Provability Logic.  in: D. Gabbay and F. Guenthner, (eds.) Handbook of Philosophical Logic, Second Edition, Dordrecht: Kluwer, 13:229–403, 2004.
  * [9] M. Balaguer.  Fictionalism in the Philosophy of Mathematics.  Stanford Encyclopedia of Philosophy (https://plato.stanford.edu/entries/fictionalism-mathematics/), 2018.
  * [10] S.S. Basu and S.G. Simpson.  Mass Problems and Intuitionistic Higher-Order Logic.  Computability, 5(1):29–47, 2016.
  * [11] P. Benacerraf.  What Numbers Could Not Be.  Philosophical Review, 74:47–73, 1965.
  * [12] L.E.J. Brouwer.  Collected Works (ed. by A. Heyting), vol. 1.  North Holland, 1975.
  * [13] L.E.J. Brouwer.  Does Every Real Number Have a Decimal Expansion?  P. Mancosu (ed.) From Brouwer to Hilbert. The Debate of the Foundations of Mathematics in the 1920s. Oxford University Press, pages 28–35, 1998.
  * [14] L.E.J. Brouwer.  Mathematica, Science, and Language.  P. Mancosu (ed.) From Brouwer to Hilbert. The Debate of the Foundations of Mathematics in the 1920s. Oxford University Press, pages 45–53, 1998.
  * [15] U. Buchholz.  Higher-Order Structures in Homotopy Type Theory.  S. Centrone, D. Kant and D. Sarikaya (eds.) Reflections on the Foundations of Mathematics: Univalent Foundations, Set Theory and General Thoughts, Springer, Synthese Library vol.407, pages 151–172, 2019.
  * [16] Th. Coquand.  Kolmogorov’s Contribution to Intuitionistic Logic.  in: E. Charpentier, A. Lesne and N.K. Nikolski (eds). Kolmogorov’s Heritage in Mathematics, pages 19–40, 2007.
  * [17] M. Fairtlough and M. Walton.  Quantified lax logic.  Tech. report CS-97-11, Univ. of Sheffield, Dept. of Computer Science, 1997.
  * [18] G. Frege.  Grundgesetze der Arithmetik, Band 2.  Olms, 1962.
  * [19] R.M. Friedberg.  The Solution of Post’s Problem.  Bulletin of American Mathematical Society, 62(3):49–59, 1956.
  * [20] K. Gödel.  Zur intuitionistischen Arithmetik und Zahlentheorie.  Ergebnisse eines Math. Kolloquimus, 4:34–38, 1933.
  * [21] K. Gödel.  Eine Interpretation des intuitionistischen Aussagenkalkuls.  Ergebnisse eines Math. Kolloquimus, 14:39–40, 1933a.
  * [22] K. Godel.  Collected Works, ed. Feferman et al., Vol. 1, Publications 1929-1936.  Oxford University Press, 1986.
  * [23] D. Grayson.  An Introduction of Univalent Foundations for Mathematicians.  Bulletin of American Mathematical Society (New Series), 55(4):427–450, 2018.
  * [24] Univalent Foundations Group.  Homotopy Type Theory: Univalent Foundations of Mathematics.  Institute for Advanced Study (Princeton); available at http://homotopytypetheory.org/book/, 2013.
  * [25] A. Heyting.  Die formalen Regeln der intuitionistischen Logik I.  Sitzungsberichte der Preussischen Akademie der Wissenschaften, pages 42–56, 1930.
  * [26] A. Heyting.  Sur la logique intuitionniste.  Académie Royale de Belgique, Bulletin de la Classe des Sciences, 16:957–963, 1930.
  * [27] A. Heyting.  Die intuitionistische Grundlegung der Mathematik.  Erkenntnis, 2:106–115, 1931.
  * [28] A. Heyting.  Mathematische Grundlagenforschung, Intuitionismus, Beweistheorie.  Springer, 1934.
  * [29] A. Heyting.  Intuitionism: and introduction.  North Holland, 1956.
  * [30] A. Heyting.  Intuitionism in Mathematics.  R. Klibansky (ed.), La philosophie au milieu du vingtième siècle, Firenze: La nuova Italia, pages 101–115, 1958.
  * [31] A. Heyting.  The intuitionist foundations of mathematics.  P. Benaceraff and H. Putnam (eds.), Philosophy of Mathematics. Selected Readings. Cambridge University Press, pages 52–60, 1983.
  * [32] A. Heyting.  On Formal Rules of Intuitionistic Logic.  P. Mancosu (ed.) From Brouwer to Hilbert. The Debate of the Foundations of Mathematics in the 1920s. Oxford University Press, pages 311–327, 1998.
  * [33] A. Heyting.  On Intuitionistic Logic.  P. Mancosu (ed.) From Brouwer to Hilbert. The Debate of the Foundations of Mathematics in the 1920s. Oxford University Press, pages 306–310, 1998.
  * [34] A. Heyting.  On the Formal Rules of Intuitionistic Logic.  P. Mancosu (ed.) From Brouwer to Hilbert. The Debate of the Foundations of Mathematics in the 1920s. Oxford University Press, pages 311–327, 1998.
  * [35] D. Hilbert.  Grundlagen der Geometrie.  Leipzig, 1899.
  * [36] D. Hilbert.  Die Grundlagen der Mathematik.  Abhandlungen aus dem Seminar der Hamburgischen Universität, 6:65–85, 1928.
  * [37] D. Hilbert.  Foundations of Mathematics.  J. van Heijenoort (ed.), From Frege to Gödel: A Source Book in the Mathematical Logic, 2:464–480, 1967.
  * [38] D. Hilbert and P. Bernays.  Grundlagen der Mathematik.  Springer, 1934-1939.
  * [39] D. Jacquette.  On defoliating meinong’s jungle.  Axiomathes, 7:17–42, 1996.
  * [40] G. Japaridze.  Introduction to computability logic.  Annals of Pure and Applied Logic, 123:1–99, 2003.
  * [41] G. Japaridze.  Intuitionistic computability logic.  Acta Cybernetica, 18(1):77–113, 2007.
  * [42] A.Ya. Khinchin.  Idei intuitsionizma i bor’ba za predmet v sovremennoi matematike [ideas of intuitionism and the struggle over subject matter in contemporary mathematics](Russian).  Vestnik Kommunisticheskoi akademii [Messenger of Communist Academy], pages 184–192, 1926.
  * [43] S.C. Kleene.  On the Interpretation of Intuitionistic Number Theory.  The Journal of Symbolic Logic, 10(4):109–124, 1945.
  * [44] S.C. Kleene.  Realizability: a Retrospective Survey.  in: A.R.D. Mathias and H. Rogers (eds.) Cambridge Summer School in Mathemamtical Logic 1971 (Lecture Notes in Mathematics), pages 95–112, 1973\.
  * [45] A. Kolmogoroff.  Zur Deutung der Intuitionistischen Logik.  Mathematische Zeitschrift, 35:58–65, 1932.
  * [46] A. Kolmogoroff.  Review of “zur intuitionistische Deutung logischer Formeln” by H. Fredeuntal and “Bemerkungen zu dem Augsatz von Herrn Fredeuntal ’Zur intuitionistische Deutung logischer Formeln’ by A. Heyting”.  Zentralblatt für Mathematik und ihre Grenzgebiete, page 0015.24201, 1937.
  * [47] A.N. Kolmogorov.  O principe tertium non datur (Russian).  Matematiceskij Sbornik, 32:646–667, 1925.
  * [48] A.N. Kolmogorov.  Contemporary Debates on the Nature of Mathematics (Russian).  Novoe Slovo, 6:41–54, 1929.
  * [49] A.N. Kolmogorov.  Preface (Russian).  Russian edition of ’Mathematische Grundlagenforschung, Intuitionismus, Beweistheorie’ by A. Heyting, Springer 1934, pages 3–4, 1936\.
  * [50] A.N. Kolmogorov.  Letters of A.N. Kolmogorov to A. Heyting, transl. and comm. V.E. Plisko.  Russian Math. Surveys, 43(6):89–93, 1988.
  * [51] A.N. Kolmogorov.  On the papers on Intuitionistic Logic.  V.M. Tikhomirov (ed.) Selected Works of A.N. Kolmogorov, Springer, 1:451–452, 1991.
  * [52] A.N. Kolmogorov.  On the tertium non datur principle.  V.M. Tikhomirov (ed.) Selected Works of A.N. Kolmogorov, Springer, 1:40–68, 1991.
  * [53] A.N. Kolmogorov.  On the Interpretation of Intuitionistic Logic.  P. Mancosu (ed.) From Brouwer to Hilbert. The Debate of the Foundations of Mathematics in the 1920s. Oxford University Press, pages 328–334, 1998.
  * [54] A.N. Kolmogorov.  Contemporary Debates on the Nature of Mathematics.  Problems of Information Transmission, 42(4):379–389, 2006.
  * [55] D.C. Kozen.  Theory of Computation.  Springer, 2006.
  * [56] P. Martin-Löf.  Intuitionistic Type Theory (Notes by Giovanni Sambin of a series of lectures given in Padua, June 1980).  Napoli: BIBLIOPOLIS, 1984.
  * [57] Yu. T. Medvedev.  Degrees of difficulty of the mass problems.  Doklady Academii Nauk SSSR (Russian), 104(4):501–504, 1955.
  * [58] Yu. T. Medvedev.  Finitary Problems.  Doklady Academii Nauk SSSR (Russian), 142(5):1015–1018, 1962.
  * [59] Yu. T. Medvedev.  Interpretation of Logical Formulas with Finitary Problems and Its Relation to the Realisability Theory.  Doklady Academii Nauk SSSR (Russian), 148(4):771–774, 1963.
  * [60] Yu. T. Medvedev.  On the Interpretation of Logical Formulas with Finitary Problems.  Doklady Academii Nauk SSSR (Russian), 169(1):20–23, 1966.
  * [61] A. Meinong.  über Gegenstandstheorie.  in A. Meinong (Ed.) Untersuchungen zur Gegenstandstheorie und Psychologie, Leipzig, Verlag von Johann Ambrosius Barth 1904, pages 1–50, 1904\.
  * [62] A. Meinong.  Über die Stellung der Gegenstandstheorie im System der Wissenschaften.  Lepzig: R. Voigtländer, 1907.
  * [63] A. Meinong.  The Theory of Objects.  in R. Chisholm, Realism and the Background of Phenomenology, Free Press of Glencoe, Illinois, 1960, pages 76–117, 1960.
  * [64] S.A. Melikhov.  Mathematical Semantics of Intuitionistic Logic.  https://arxiv.org/abs/1504.03380, 2017.
  * [65] S.A. Melikhov.  A Galois connection between classical and intuitionistic logics. I: Syntax.  https://arxiv.org/abs/1504.03380, 2022.
  * [66] S.A. Melikhov.  A Galois connection between classical and intuitionistic logics. II: Semantics.  https://arxiv.org/abs/1504.03380, 2022.
  * [67] S.A. Melikhov.  A Joint Logic of Problems and Propositions.  Doklady Mathematics, in press, 2023.
  * [68] A. Mostowski.  Review of ’Degrees of difficulty of the mass problem’ by Yu.T. Medvedev,.  Journal of Symbolic Logic, 21(3):320–321, 1956.
  * [69] A.A. Muchnik.  The insolubility of the reduction problem in the theory of algorithms.  Doklady Academii Nauk SSSR (Russian), 108(2):194–197, 1956.
  * [70] A.A. Muchnik.  The Problem of Reducibility for Recursive sets.  Mathematical Enlightment (Russian), 4:233–236, 1959.
  * [71] A.A. Muchnik.  Strong and weak reducibility of algorithmic problems.  Siberian Mathematical Journal (Russian), 4:1328–1341, 1963.
  * [72] A.A. Muchnik.  Strong and weak reducibility of algorithmic problems.  Computability, 5(1):49–59, 2016.
  * [73] A.A. Onoprienko.  Kripke-type semantics for a logic of problems and propositions.  Sbornik Mathematics, 211:709–732, 2020.
  * [74] A.A. Onoprienko.  Topological models of propositional logic of problems and propositions.  Moscow University Mathematics Bulletin, 77(5):236–241, 2022.
  * [75] A. Rodin.  Axiomatic Method and Category Theory (Synthese Library vol. 364).  Springer, 2014.
  * [76] R. Routley and V. Routley.  Rehabilitating Meinong’s Theory of Objects.  Revue Internationale de Philosophie, 27(104/105):224–254, 1973\.
  * [77] S.G. Simpson.  Weak Counter-Examples.  Notre Dame Journal of of Formal Logic, 49:127–136, 2008.
  * [78] D.P. Skvortsov.  Logic of Infinitary Problems and Kripke Models on Atomic Semi-Lattices of Sets.  Doklady Academii Nauk SSSR (Russian), 245(4):798–801, 1979.
  * [79] D.P. Skvortsov.  Two Generalisations of the Concept of Finitary Problem.  in: A.I. Mikhailov (ed.) Studies in Non-Classical Logics and Set Theory, Nauka Publishing, 1979 (Russian), pages 201–240, 1979.
  * [80] M. Stone.  Revolution in Mathematics.  American Mathematical Monthly, 68(8):715–734, 1961.
  * [81] G. Sundholm.  Constructions, Proofs, and the Meaning of Logical Constants.  Journal of Philosophical Logic, 12(2):151–172, 1983.
  * [82] G. Sundholm.  On the Philosophical Work of Per Martin-Löf.  Preface to: Dybjer P. et al. (Eds.), Epistemology versus Ontology Essays on the Philosophy and Foundations of Mathematics in Honour of Per Martin-Löf. Logic, Epistemology, and the Unity of Science no. 27. Dordrecht: Springer Netherlands, pages xvii–xxiv, 2012.
  * [83] A.S. Troelstra.  On the Early History of Intuitionistic Logic.  P.P. Petkov (ed.) Mathematical Logic, New York: Plenum Press, pages 3–17, 1990.
  * [84] V.A. Uspenskii.  Kolmogorov as I Remember Him (russian).  A.N. Shiryaev (ed.), Kolmogorov in the Memories of his Pupils (Russian), Moscow Centre of Continuous Mathematical Education, pages 272–371, 2006.
  * [85] V.A. Uspenskii and V.E. Plisko.  Intuitionistic Logic.  V.M. Tikhomirov (ed.) Selected Works of A.N. Kolmogorov, Springer, 1:452–465, 1991.
  * [86] M. van Atten.  Weak Counter-Examples.  Stanford Encyclopedia of Philosophy (https://plato.stanford.edu/entries/brouwer/weakcounterex.html), Supplement to the main entry ’Luitzen Egbertus Jan Brouwer’, https://plato.stanford.edu/entries/brouwer/index.html, 2020.
  * [87] M. van Atten.  The Development of Intuitionistic Logic.  Stanford Encyclopedia of Philosophy (https://plato.stanford.edu/entries/intuitionistic-logic-development/), 2022\.
  * [88] W.P. van Stigt.  Brouwer’s Intuitionism.  North Holland, 1990.
  * [89] L.M. Verburgt and O. Hoppe-Kondrikova.  On A.Ya. Khinchin’s paper ‘ideas of intuitionism and the struggle for a subject matter in contemporary mathematics’ (1926): A translation with introduction and commentary.  Historia Mathematica, 43(4):369–398, 2006.
  * [90] V.A. Voevodsky.  Foundations of Mathematics and Homotopy Theory (lecture at the Princeton institute of Advanced Studies on march 22, 2006), 2006.  slides available online via https://www.math.ias.edu/vladimir/Lectures.
  * [91] V.A. Voevodsky.  Univalent Foundations (lecture at the Princeton institute of Advanced Studies on December 10, 2010), 2010.  video available online at https://www.ias.edu/video/univalent/voevodsky.
  * [92] V.A. Voevodsky.  Univalent Foundations (lecture in Bonn on September 8, 2010), 2010\.  slides available online via https://www.math.ias.edu/vladimir/Lectures.

## Appendix: A.N. Kolmogorov, _Preface_ to Russian edition [49] of
_Mathematische Grundlagenforschung, Intuitionismus, Beweistheorie_ by Arend
Heyting [28]. Translation from Russian by Andrei Rodin.

In the Introduction to his book Heyting quite rightly states that the purpose
of research in the foundations of mathematics is not limited to the
verification of their firmness, the abolishing of ill-founded parts of
mathematics and the elimination of emerging contradictions but also includes a
positive analysis of the subject-matter of mathematics, of its methods and
ways of its development. Nevertheless, since the efforts of mathematicians
researching the foundations of their science during the last years were
focused mostly on the former goal, Heyting in the present review pays little
attention to the second goal. Thus one should keep firmly in mind that
Heyting’s book is not an introduction into a positive philosophy of
mathematics. It is, by and large, an exposition of various directions and ways
of critique concerning some [theoretical] constructions used by working
mathematicians, and of attempts to mitigate the destructive results of this
critique. Heyting does not limit his exposition to an analysis of the two
major trends in this area of research (Intuitionism and Formalism) but also
makes interesting remarks pointing to their possible synthesis.

The destructive, critical parts of both these trends are essentially related
to the principles of Subjective Idealism. This is why Heyting’s review cannot
give any indication to how the result of critique of basic mathematical
concepts would look like if the critique proceeds on the materialistic
grounds. But the constructive side of the two trends (development of
mathematics without using the Law of Excluded Middle in the case of
Intuitionism, and methods of proving consistency in the case of Formalism)
comes down to a concrete mathematical work, which is often admirably sharp and
smart. In spite of their [erroneous] philosophical subjective idealistic
assumptions, the two schools [of mathematical thought] discovered in the
course of this work a number of extraordinarily deep and interesting facts.

We cannot agree with the intuitionists when they claim that mathematical
objects are products of the constructive activity of our spirit. For us,
mathematical objects are abstractions from existing forms of reality, which is
independent from our spirit. We know that the constructive solutions of
problems are as much important in mathematics as the pure proofs of
theoretical sentences. This constructive aspect of mathematics does not
conceal for us its other and more fundamental aspect, namely, its epistemic
aspect. But the laws of mathematical construction discovered by Brouwer and
systematized by Heyting under the appearance of new intuitionistic logic, so
understood, preserve for us their fundamental significance (see my article
[45]).

We equally reject the tenets of the formalistic school. We believe that
mathematics does not reduce to its formalised part, and that [mathematical]
problems that cannot be solved on the basis of axioms formulated so far, [may]
nevertheless have a well-determined real sense and admit unambiguous
solutions. This view, however, does not diminish our interest to studying the
structure of formalised mathematical theories.

Every _accomplished_ mathematical theory should be formalised because the
final goal of every such theory is building an algorithm for an automatic
solution of the related problems. It is moreover interesting that the studies
made by the formalists themselves lead one to the conclusion that, first, the
formalisation [of mathematics] can never be completed and, second, that the
formalisation needs some contentual (not formal) mathematics (under the name
of “metamathematics”, if one wishes) as its prerequisite.

A danger of using Heyting’s review lies in its extreme density. This density
makes it neccessary for the reader to consult the primary sources listed in
the Bibliography, which is carefully composed and complete ([for publications
made] before 1933). This density also makes the task of translator [of
Heyting’s book into Russian] very difficult. This difficult task was
accomplished by the translator (A.P. Yushkevich) perfectly. He always aimed at
the precise translation of the author’s thoughts, even at the price of some
additional length. When this is needed, the newly introduced Russian
equivalents of some terms are accompanied by the original [German] words in
parentheses.


# Bottleneck Matching in the Plane††thanks: Work by Matthew Katz was partially
supported by Grant 2019715/CCF-20-08551 from the US-Israel Binational Science
Foundation/US National Science Foundation. Work by Micha Sharir was partially
supported by ISF Grant 260/18.

Matthew J. Katz Department of Computer Science, Ben Gurion University, Beer
Sheva, Israel<EMAIL_ADDRESS>Micha Sharir School of Computer Science, Tel
Aviv University, Tel Aviv Israel<EMAIL_ADDRESS>
###### Abstract

We present an algorithm for computing a bottleneck matching in a set of
$n=2\ell$ points in the plane, which runs in $O(n^{\omega/2}\log n)$
deterministic time, where $\omega\approx 2.37$ is the exponent of matrix
multiplication.

Let $P$ be a set of $n=2\ell$ points in the plane, and let $G=(P,E)$ denote
the complete Euclidean graph over $P$, which is an undirected weighted graph
with $P$ as its set of vertices, and the weight of an edge $e=(p,q)\in E$ is
${\sf dist}(p,q)$, where ${\sf dist}$ denotes the Euclidean distance. For a
perfect matching $M$ in $G$, let $\lambda(M)$ denote the length of a longest
edge in $M$. A perfect matching $M$ is a _bottleneck matching_ of $P$ if
$\lambda(M)\leq\lambda(M^{\prime})$, for any other perfect matching
$M^{\prime}$ in $G$.

In this note, we present an algorithm for computing a bottleneck matching
$M^{*}$ of $P$, with running time $O(n^{\omega/2}\log n)=O(n^{1.187})$, where
$\omega<2.3728596$ is the exponent of matrix multiplication [4, 10]. All
previous algorithms for computing $M^{*}$ are based on the algorithm of Gabow
and Tarjan [9], which computes a bottlenck maximum matching in a (general)
graph with $n$ vertices and $m$ edges in time $O((n\log n)^{1/2}m)$. These
algorithms apply Gabow and Tarjan’s algorithm to a subgraph $G^{\prime}$ of
$G$, with only $O(n)$ edges, that is guaranteed to contain $M^{*}$. The
running time of these algorithms is therefore $O(T(n)+n^{3/2}\log^{1/2}n)$,
where $T(n)$ is the time needed to compute some suitable subgraph
$G^{\prime}$. In the work of Chang et al. [7], $T(n)=O(n^{2})$, and in the
subsequent work of Su and Chang [11], $T(n)=O(n^{5/3}\log n)$, which is the
best previously-known bound for computing $M^{*}$; see below for further
details concerning possible choices of $G^{\prime}$. In contrast to the
previous algorithms, we replace the algorithm of Gabow and Tarjan (which
immediately sets a lower bound of $\Omega(n^{3/2}\log^{1/2}n)$ on the running
time) by an algorithm of Bonnet et al. [5] for computing a maximum matching
(not necessarily bottleneck) in an intersection graph of geometric objects in
the plane, and use it as a _decision_ procedure in our search for $M^{*}$.

We first observe that $\lambda^{*}\coloneqq\lambda(M^{*})$ is the distance
between some pair of points in $P$. For a real number $r>0$, let $G_{r}$
denote the graph that is obtained from $G$ by retaining only the edges of
length at most $r$. That is, $G_{r}=(P,E_{r})$, where

$E_{r}=\\{(p,q)\in P\times P\mid p\neq q\text{ and }{\sf dist}(p,q)\leq r\\}.$

$G_{r}$ is also the intersection graph of the set of disks of radius $r/2$
centered at the points of $P$, and by suitably scaling the configuration, it
is the _unit-disk graph_ over $P$ (see [8]). Bonnet et al. [5] presented an
$O(n^{\omega/2})$-time algorithm for computing a maximum matching in $G_{r}$.
Their algorithm can therefore also be used to determine whether $G_{r}$
contains a perfect matching, which is the case if and only if the number of
edges in the returned maximum matching is $\ell$. Let $r^{*}>0$ be the
smallest value for which $G_{r^{*}}$ contains a perfect matching. Then, by
applying the algorithm of Bonnet et al. to $G_{r^{*}}$, we obtain a bottleneck
matching $M^{*}$ of $P$ (with $\lambda^{*}=r^{*}$).

Since $r^{*}$ is the distance between some pair of points in $P$, we can
perform a binary search in the (implicit) set of the $n\choose 2$ distances
determined by pairs of points in $P$, using the algorithm of Bonnet et al. to
resolve comparisons, thereby obtaining $r^{*}$ and $M^{*}$. To perform the
binary search, we use a distance selection algorithm (such as in [2]), whose
running time is $O^{*}(n^{4/3})$ (where the $O^{*}(\cdot)$ notation hides
subpolynomial factors), to find the next distance to test. Since
$\omega/2<4/3$, we obtain a bottleneck matching algorithm for $n=2\ell$ points
in the plane with running time $O^{*}(n^{4/3})$, which is already
significantly faster than the best known such algorithm.

However, we can do better. If we are given a set $D$ of $m$ candidate
distances that includes $r^{*}$, we can obtain, in total time
$O(m+n^{\omega/2}\log m)$, a bottleneck matching of $P$, by performing a
binary search in $D$. Our goal is, therefore, to find such a candidate set $D$
of size $m=O(n^{\omega/2})$ (in fact, our set will be of size $O(n)$) that can
also be generated efficiently. A natural choice of $D$ is the set of lengths
of a suitable subgraph $G^{\prime}$ of $G$ that can be shown to contain a
bottleneck matching of $P$.

Chang et al. [7] proved that the _17-relative neighborhood graph_ of $P$,
denoted as ${\rm 17RNG}(P)$, contains a bottleneck matching of $P$. This is a
graph over $P$, where $(p,q)$ is an edge if and only if the number of points
of $P$ whose distance from both $p$ and $q$ is smaller than ${\sf dist}(p,q)$
is at most 16. As shown in [7], the number of edges in ${\rm 17RNG}(P)$ is
$O(n)$, so we could use the set of distances corresponding to these edges as
our candidate set $D$. However, we do not know how to compute ${\rm 17RNG}(P)$
efficiently. The best known algorithm for computing the $k$RNG, for any fixed
integer $k$, of a set of $n$ points, is due to Su and Chang [11], and it runs
in $O(n^{5/3}\log n)$ time (with the constant of proportionality depending on
$k$). This bound can be improved, using more recent range searching
techniques,111The best improvement we have found runs in $O^{*}(n^{7/5})$
time. but it seems unlikely that such an improvement will be near the bound we
are after.

Instead, we consider another graph, known as the _17-geographic neighborhood
graph_ of $P$, denoted as ${\rm 17GNG}(P)$, which has also been studied in [7]
and is defined as follows. Partition the plane into six closed wedges
$W_{1},\ldots,W_{6}$, each with opening angle $60^{\circ}$, by the three lines
through the origin with slopes $0$, $\pm\sqrt{3}$. The graph ${\rm 17GNG}(P)$
consists of all the edges $(p,q)\in P\times P$, with $p\neq q$, for which
there exists $1\leq i\leq 6$ such that $q\in p+W_{i}$, where $p+W_{i}$ is
$W_{i}$ translated by $p$, so that there are at most $16$ points
$q^{\prime}\in p+W_{i}$ with ${\sf dist}(p,q^{\prime})<{\sf dist}(p,q)$. (When
the slope of the line through $p$ and $q$ is in $\\{0,\pm\sqrt{3}\\}$ there
are two such wedges $W_{i}$.) See Figure 1 for an illustration. As shown in
[7], ${\rm 17GNG}(P)$ is a supergraph of ${\rm 17RNG}(P)$, and the number of
its edges is still $O(n)$. We show below that ${\rm 17GNG}(P)$ can be computed
in $O(n\log^{3}n)$ time. Once we have computed ${\rm 17GNG}(P)$, we perform a
binary search on the set of distances corresponding to its edge set, as
described above, to obtain $M^{*}$, in total time $O(n^{\omega/2}\log n)$.

Before continuing, we remark that there is actually no need to compute ${\rm
17GNG}(P)$. All we need is the set of lengths of its edges, over which we will
run binary search to find $M^{*}$ using the algorithm of [5]. Nevertheless,
for the sake of completeness, and since this is a result of independent
interest, we present an algorithm that actually constructs ${\rm 17GNG}(P)$
efficiently. The algorithm is relatively simple when the points of $P$ are in
general position, but is somewhat more involved when this is not the case.

Figure 1: The wedges $p+W_{1},\ldots,p+W_{6}$ and the edges that are added to
2GNG$(P)$ ‘due’ to $p$.

## Computing ${\rm 17GNG}(P)$ in general position.

Begin by assuming that $P$ is in general position. Actually, the only
condition that we require is that no three points form an isosceles triangle.
Computing ${\rm 17GNG}(P)$ in this case is relatively simple, since
informally, the ranges that arise in computing ${\rm 17GNG}(P)$ are wedges
with fixed orientations of their bounding rays. In contrast, the ranges that
arise in computing ${\rm 17RNG}(P)$ are lenses formed by the intersection of
two congruent disks, which are more expensive to process.

For each $p\in P$, we compute the set $N_{i}^{17}(p)$, for $i=1,\ldots,6$,
which consists of the points that have at most 16 other points in
$P\cap(p+W_{i})$ that are closer to $p$. When $P$ is in general position,
these are the 17 closest points to $p$ in $P\cap(p+W_{i})$, see Figure 1.
However, when this is not the case, $|N_{i}^{17}(p)|$ could be much larger,
see Figure 2. (If $|P\cap(p+W_{i})|\leq 17$, then
$N_{i}^{17}(p)=P\cap(p+W_{i})$.) We will later discuss the extension of the
algorithm and analysis to degenerate situations.

We construct six similar data structures, where the $i$’th structure is used
to compute the collection of sets $\\{N_{i}^{17}(p)\mid p\in P\\}$. The $i$’th
structure is an augmented two-level ‘orthogonal’ range searching structure,
where each level stores the points of (suitable canonical subsets of) $P$ in
their order in the direction perpendicular to a bounding ray of $W_{i}$. For
each node $v$ in the second level of the structure, we compute the 17th-order
Voronoi diagram ${\rm Vor}_{17}(Q_{v})$ of $Q_{v}$, the canonical set of $v$,
and store it at $v$ as a point-location structure. (Recall that ${\rm
Vor}_{17}(Q_{v})$ partitions the plane into maximal regions, each with a fixed
_set_ of 17 closest sites.) The total size of the data structure is thus
$O(n\log^{2}n)$, and it can be computed in total time $O(n\log^{3}n)$, where
the Voronoi diagrams are computed by the algorithm of Chan and Tsakalidis [6],
which takes $O(|Q_{v}|\log|Q_{v}|)$ deterministic time per diagram. (See also
the earlier algorithm of Agarwal et al. [3], which is randomized and slightly
less efficient.) In fact, since 17 is a constant, we can compute the diagram
in a simpler incremental manner, starting with the standard diagram and adding
one index at a time. This also takes $O(|Q_{v}|\log|Q_{v}|)$ time per diagram.

Figure 2: When $P$ is not in general position $|N_{i}^{2}(p)|$ could be larger
than 2. Here, $|N_{1}^{2}(p)|=2$, $|N_{2}^{2}(p)|=5$, and $|N_{3}^{2}(p)|=3$.

Now, for each $p\in P$, we perform a query in the $i$’th structure to obtain
the set $N_{i}^{17}(p)$. We initialize this set to be empty. We then identify
the $O(\log^{2}n)$ second-level nodes, such that $P\cap(p+W_{i})$ is the
disjoint union of their canonical sets. Next, we visit these nodes, one at a
time, and at each node $v$ we perform a query with $p$ in ${\rm
Vor}_{17}(Q_{v})$, and update $N_{i}^{17}(p)$ accordingly, in constant time. A
query thus takes $O(\log^{3}n)$ time for each $p\in P$, for a total of
$O(n\log^{3}n)$ time. (The latter bound follows since, in general position,
each set $N_{i}^{17}(p)$ is of constant size (at most $17$)). The overall
output of this procedure is the desired graph ${\rm 17GNG}(P)$.

## Handling degeneracies.

When $P$ is not in general position, some modifications are required. As
already observed, in this case $|N_{i}^{17}(p)|$ might be much larger than 17
(it could be even as large as $n-1$), although the total number of edges in
${\rm 17GNG}(P)$ remains $O(n)$ [7]. The problematic situation is when, for
some $p\in P$ and some $1\leq i\leq 6$, and for some canonical set $Q$ of
$P\cap(p+W_{i})$, there exists a large subset $Q^{\prime}$ of $Q$, all of
whose points lie on a circle centered at $p$, with at most 16 points of $Q$
inside the circle. In that case all points of $Q^{\prime}$ form with $p$
potential edges of ${\rm 17GNG}(P)$, but to retain the aforementioned running
time, we cannot afford to spend more than $O(\log n)$ time while processing
$Q$ (when querying with $p$), unless they are indeed edges of ${\rm
17GNG}(P)$, in which case we may spend additional $O(|Q^{\prime}|)$ time.
However, at this point we do not know whether they are edges of ${\rm
17GNG}(P)$, because other canonical sets might generate with $p$ shorter edges
that exclude the potentially numerous longest edges involving $Q$ from the
graph.222This issue disappears if we only maintain the lengths of the edges of
${\rm 17GNG}(P)$, as all these longest edges have the same length.

To address this issue, we modify the query with $p$ in the $i$’th structure as
follows. As before, we first identify the $O(\log^{2}n)$ second-level nodes of
the structure, such that $P\cap(p+W_{i})$ is the disjoint union of their
canonical sets. The next stage consists of two rounds, where in each round we
process each of these $O(\log^{2}n)$ nodes. The sole purpose of the first
round is to find the distances $d_{1}<d_{2}<\cdots<d_{k}$, where $k\leq 17$,
between $p$ and the $17$ closest points to $p$ among the points in
$P\cap(p+W_{i})$. (We write $k\leq 17$, since the same distance may be
attained by several points.) More precisely, if we were to sort the points in
$P\cap(p+W_{i})$ by their distance from $p$, resolving ties arbitrarily, then
$d_{1},\ldots,d_{k}$ would be the distinct distances corresponding to the
first 17 points in the sequence. We now describe how to implement the first
round in total $O(\log^{3}n)$ time, for each fixed $p$ and $i$, that is, in
overall $O(n\log^{3}n)$ time.

We use the following notation. For a (two-dimensional open) cell $C$ of ${\rm
Vor}_{17}(Q_{v})$, for some second-level node $v$, denote by $P(C)$ the set of
the (uniquely defined) 17 closest points of $Q_{v}$ to any point in $C$.
Moreover, for any point $p$ in the closure of $C$, put $d_{p}(C)=\max\\{{\sf
dist}(p,q)\mid q\in P(C)\\}$.

For fixed $p$ and $i$, we maintain a sorted sequence $A=A_{p,i}$ of the 17
closest points to $p$ among the points of $P\cap(p+W_{i})$ that were
encountered so far; initially $A$ is empty. (Ties are broken arbitrarily, and
we limit the length of $A$ to 17 even when there are additional points, not in
$A$, whose distance from $p$ is equal to that between $p$ and the last point
in $A$.) At each second-level node $v$ of the structure, we locate $p$ in
${\rm Vor}_{17}(Q_{v})$, and proceed as follows. Let $C$ be a cell of the
diagram such that $p$ lies in the closure of $C$ (the cell is not unique when
$p$ lies on an edge or is a vertex of the diagram). Obtaining $C$ from the
point location query is straightforward in all cases, and takes constant time.
We update $A$ (or initialize it, if $v$ is the first visited node) by
examining the points in $P(C)$. Specifically, we sort the set $P(C)$ by
distance to $p$, and either copy the resulting sequence into $A$, when $v$ is
the first processed node, or otherwise merge it with $A$, retaining only the
first 17 elements.

Put $\Delta_{p,i}=\\{{\sf dist}(p,q)\mid q\in A\\}$, and note that
$|\Delta_{p,i}|\leq 17$, where a strict inequality is possible. We have:

######  Lemma.

After processing all the $O(\log^{2}n)$ canonical sets that form
$P\cap(p+W_{i})$, $\Delta_{p,i}$ is the set of distances between $p$ and the
$17$ closest points to $p$ in $P\cap(p+W_{i})$.

Proof. We argue, by induction, that after processing some of the canonical
sets, $\Delta_{p,i}$ is the set of distances between $p$ and the 17 closest
points to $p$ in the union of these sets. The claim holds trivially initially,
so assume that it holds just before processing some canonical set $Q$.

Let $C$ be the cell of ${\rm Vor}_{17}(Q)$ that is obtained from the point
location query, so $p$ lies in the closure of $C$. The claim is easy to argue
when $p$ lies in the interior of $C$, so the interesting case is when
$p\in{\partial}C$. We observe that in this case, if $C^{\prime}$ is any other
cell that contains $p$ (necessarily on its boundary) then
$d_{p}(C^{\prime})=d_{p}(C)$ and

$P(C^{\prime})\setminus\\{q\in P(C^{\prime})\mid{\sf
dist}(p,q)<d_{p}(C^{\prime})\\}=P(C)\setminus\\{q\in P(C)\mid{\sf
dist}(p,q)<d_{p}(C)\\}.$

This follows directly from the definition of the diagram, since otherwise,
either $P(C)$ or $P(C^{\prime})$ (or both) would not be the correct answer to
the query with $p$. In other words, in this case it does not matter which of
the cells that are adjacent to $p$ we use to update $A$. This property implies
that the invariant is preserved after processing $Q$, and it therefore
completes the induction step in this case too. $\Box$

In the second round,333The second round is not needed if we are interested
only in the lengths of the edges of ${\rm 17GNG}(P)$. we iterate again over
all points $p$ and indices $i$. For a fixed pair $p$ and $i$, we retrieve the
$O(\log^{2}n)$ canonical sets that form $P\cap(p+W_{i})$. For each of these
sets $Q$, we locate $p$ in ${\rm Vor}_{17}(Q)$ and compute $d_{p}(C)$ in
constant time, for some (single) cell $C$ of the diagram whose closure
contains $p$ (recall that this value is independent of $C$). We then compute
the set $\Delta_{p,i}(C)$ of distances between $p$ and the points of $P(C)$
that belong to $\Delta_{p,i}$, i.e., $\Delta_{p,i}(C)=\\{d\in\Delta_{p,i}\mid
d={\sf dist}(p.q)\text{ for some }q\in P(C)\\}$. Two cases can arise:

(i) $d_{p}(C)\notin\Delta_{p,i}(C)$. In this case the subset $P_{p}(C)$ of
$P(C)$ of the points whose distances to $p$ are in $\Delta_{p,i}(C)$ is
independent of the cell $C$ (as long as $C$ contains $p$ in its closure). We
then simply find $P_{p}(C)$ and add to ${\rm 17GNG}(P)$ all the (at most 16)
edges $(p,q)$ for $q\in P_{p}(C)$.

(ii) $d_{p}(C)\in\Delta_{p,i}(C)$. In this case we iterate over _all_ the
cells $C$ incident to $p$, and add all the edges $(p,q)$, for
$q\in\bigcup_{C}P(C)$. This does not affect the asymptotic bound on the
running time: if there are $k$ such cells, we process $O(k)$ points but add
$\Theta(k)$ edges to ${\rm 17GNG}(P)$, as is easily checked. (If $p$ is
adjacent to $k$ cells then there are $k$ points in $Q$ at distance $d_{p}(C)$
from $p$, and all of them form with $p$ edges of ${\rm 17GNG}(P)$.)

By applying this procedure to each $p$ and $i$ and to each corresponding
canonical set $Q$, we obtain the desired graph ${\rm 17GNG}(P)$.

## Wrapping it up.

We have shown that one can compute ${\rm 17GNG}(P)$ in $O(n\log^{3}n)$ time.
Having computed ${\rm 17GNG}(P)$, we continue as before, running a binary
search over its $O(n)$ edge lengths, using the algorithm of Bonnet et al. [5]
to guide the search. In summary, we obtain:

######  Theorem.

A bottleneck matching of a set of $n=2\ell$ points in the plane can be
computed in $O(n^{\omega/2}\log n)$ deterministic time.

Abu-Affash et al. [1] presented an algorithm that, given a perfect matching
$M$ of $P$, returns in $O(n\log n)$ time a _non-crossing_ perfect matching $N$
of $P$, such that $\lambda(N)\leq 2\sqrt{10}\lambda(M)$. We thus obtain:

######  Corollary.

A non-crossing perfect matching $N$ of a set of $n=2\ell$ points in the plane
with $\lambda(N)\leq 2\sqrt{10}\lambda^{*}$ can be computed in
$O(n^{\omega/2}\log n)$ deterministic time, where $\lambda^{*}$ is the length
of a longest edge in a bottleneck matching of $P$.

## References

  * [1] A. K. Abu-Affash, P. Carmi, M. J. Katz and Y. Trabelsi, Bottleneck non-crossing matching in the plane, Comput. Geom. 47 (2014), 447–457.
  * [2] P. K. Agarwal, B. Aronov, M. Sharir and S. Suri, Selecting distances in the plane, Algorithmica 9 (1993), 495–514.
  * [3] P. K. Agarwal, M. de Berg, J. Matoušek and O. Schwarzkopf, Constructing levels in arrangements and higher-order Voronoi diagrams, SIAM J. Comput. 27 (1998), 654–667.
  * [4] J. Alman and V. Vassilevska Williams, A refined laser method and faster matrix multiplication, Proc. ACM-SIAM Sympos. on Discrete Algorithms (SODA), 2021, 522–539.
  * [5] É. Bonnet, S. Cabello and W. Mulzer, Maximum matchings in geometric intersection graphs, Proc. 37th Internat. Sympos. on Theoretical Aspects of Computer Science (STACS), 2020, 31:1–31:17. See also, arXiv:1910.02123.
  * [6] T. M. Chan and K. Tsakalidis, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Discrete Comput. Geom. 56 (2016), 866–881.
  * [7] M. S. Chang, C. Y. Tang and R. C. T. Lee, Solving the Euclidean bottleneck matching problem by $k$-relative neighborhood graphs, Algorithmica 8 (1992), 177–194.
  * [8] B. N. Clark, C. J. Colbourn and D. S. Johnson, Unit disk graphs, Discrete Math. 86 (1990), 165–177.
  * [9] H. N. Gabow and R. E. Tarjan, Algorithms for two bottleneck optimization problems, J. Algorithms 9 (1988), 411–417.
  * [10] F. Le Gall, Powers of tensors and fast matrix multiplication, Proc. 39th Internat. Sympos. on Symbolic and Algebraic Computation (ISSAC), 2014, 296–303.
  * [11] T.-H. Su and R.-C. Chang, Computing the _k_ -relative neighborhood graphs in Euclidean plane, Pattern Recognition 24 (1991), 231–239.