# A Direct Reduction from the Polynomial to the Adversary Method

Aleksandrs Belovs Faculty of Computing, University of Latvia

###### Abstract

The polynomial and the adversary methods are the two main tools for proving
lower bounds on query complexity of quantum algorithms. Both methods have
found a large number of applications, some problems more suitable for one
method, some for the other.

It is known though that the adversary method, in its general negative-weighted
version, is tight for bounded-error quantum algorithms, whereas the polynomial
method is not. By the tightness of the former, for any polynomial lower bound,
there ought to exist a corresponding adversary lower bound. However, direct
reduction was not known.

In this paper, we give a simple and direct reduction from the polynomial
method (in the form of a dual polynomial) to the adversary method. This shows
that any lower bound in the form of a dual polynomial is actually an adversary
lower bound of a specific form.

##  1 Introduction

Proving lower bounds on quantum query complexity is a task that has attained
significant attention. The reason is that it is essentially the only known way
to prove limitations on the power of quantum algorithms. For instance,
Bennett, Bernstein, Brassard, and Vazirani [14] proved a quantum query lower
bound for the OR function using what later became known as the hybrid method.
This demonstrates that there is no way to attain a better than Grover’s [20]
quadratic speed-up for an NP-search problem if we treat the latter as a black-
box (an oracle). Powerful tools for proving quantum query lower bounds have
been developed consequently: the polynomial method, and the adversary method,
both in its original (positive-weighted) and improved (negative-weighted)
formulations.

The polynomial method is due to Beals, Buhrman, Cleve, Mosca, and de Wolf [9],
and it was inspired by a similar method used by Nisan and Szegedy [26, 27] to
prove lower bounds on randomized query complexity. The method builds on the
following observation: if $\mathcal{A}$ is a $T$-query quantum algorithm, then
its acceptance probability on input $x$ can be expressed as a degree-$2T$
multivariate polynomial in the input variables $x_{i}$. Beals et al. [9] used
this method to re-prove the lower bound for the OR function from [14], and
establish other results like a tight lower bound for all total symmetric
Boolean functions. A landmark result obtained by this method is the lower
bound for the collision problem by Aaronson and Shi [3]. Similarly as Bennett
et al.’s result [14], it shows that a black-box approach to finding a
collision in a hash function by a quantum computer is doomed as well. This
method has been popular ever after.

The original adversary method is due to Ambainis [4], and it is an improvement
on the aforementioned hybrid method. The bound was strengthened by Ambainis
himself [5] and Zhang [34] shortly afterwards. One of the appealing features
of this method is its convenient combinatorial formulation, which resulted in
a number of applications [7, 19, 15, 18]. However, the original formulation of
the adversary bound was subject to several important limitations [34].

Partly in order to overcome these limitations, Høyer, Lee, and Špalek
generalised the adversary bound in [21]. Departing from the semidefinite
formulation of the original adversary bound by Barnum, Saks, and Szegedy [8],
Høyer et al. showed that the same expression still yields a lower bound if one
replaces non-negative entries by arbitrary real numbers. This _negative-
weighted_ formulation of the bound is strictly more powerful than the
positive-weighted one, but it lacks the combinatorial convenience of the
latter. The bound turned out to be useful for composed functions [21] and sum-
problems [13, 12]. In a series of papers [30, 28, 29], Reichardt et al.
surprisingly proved that the negative-weighted version of the bound is tight
for bounded-error algorithms!

The polynomial method, on the other hand, is known to be non-tight. Ambainis
[5] constructed a first super-linear separation between the two for total
Boolean functions. This was later improved to an almost quartic separation by
Aaronson, Ben-David, and Kothari [1], which is essentially tight [2]. For
partial functions, the separations can be even more impressive [6].

The history of relationship between the adversary and the polynomial methods
is rather interesting. For instance, the AND of ORs function allows for a very
simple adversary lower bound [4], but its polynomial lower bound is more
complicated and was only obtained more than a decade later. It was achieved
independently by Sherstov [32], and Bun and Thaler [17] using the technique of
dual polynomials [31]. The latter is the dual of an approximating polynomial
is the sense of linear programming. Therefore, by strong duality, their
optimal values are exactly equal, and every polynomial lower bound can, in
principle, be stated as a dual polynomial. The technique of dual polynomials
has been used by Bun, Kothari, and Thaler [16] to prove strong lower bounds
for a number of problems like $k$-distinctness, image size testing, and
surjectivity. The first of them was later improved in [25]. Similarly strong
adversary lower bounds for these problems are not known.

Since the adversary method is tight, for every polynomial lower bound, there
ought to exist a similarly good adversary lower bound. However, a direct
reduction was not known. In this paper, we prove a simple direct reduction,
giving a mechanical way of converting every dual polynomial into an adversary
lower bound of a specific form. We hope that this connection will give a
better understanding of both techniques, and should enable their combined use,
which could result in better lower bounds. Contrary to the majority of papers
dealing with the general adversary method, all proofs in this paper are fairly
elementary.

A related result is a direct reduction from the polynomial method to
_multiplicative_ adversary by Magnin and Roland [24], while we give a
reduction to a more widely-used _additive_ adversary. We also note that our
construction has similarities to a recent powerful lower bound technique by
Zhandry [33, 23]. It would be interesting to understand the connection between
the two better.

The following result is the cornerstone of our reduction.

######  Theorem 1.

Let $X$ and $Y$ be sets of inputs, and $\mu$ and $\nu$ be probability
distributions on $X$ and $Y$, respectively. Assume that, for any assignment
$\alpha$ of size $\leq 2m$, we have

$\Pr_{x\leftarrow\mu}[x\sim\alpha]=\Pr_{y\leftarrow\nu}[y\sim\alpha].$ (1)

Then, the quantum query complexity of distinguishing $X$ and $Y$ is
$\Omega(m)$.

The result itself is actually known. To represent this, we will give two
proofs in this paper. The first one in Section 2 uses the method of dual
polynomials and it is purely for illustrative purposes. The second proof is
the main technical contribution of this paper, and it is done using the
adversary method. Let us give an short outline here. The proof uses the
following collection of vectors:

$v^{X}_{\alpha}=\sum_{x\in
X:x\sim\alpha}\sqrt{\mu_{x}}\mathopen{}\mathclose{{}\left|x}\right>_{\mathsf{}}\qquad\text{and}\qquad
v^{Y}_{\alpha}=\sum_{y\in
Y:y\sim\alpha}\sqrt{\nu_{y}}\mathopen{}\mathclose{{}\left|y}\right>_{\mathsf{}},$

where $\alpha$ is an assignment of the input variables. By the
indistinguishability, for every $k\leq m$, there exists a linear isometry
$W_{\leq k}$ that maps each $v^{X}_{\alpha}$ with $|\alpha|\leq k$ into
$v^{Y}_{\alpha}$ and is zero on the orthogonal complement of these vectors.
Informally, $W_{\leq k}$ gives a binding between $X$ and $Y$ for an algorithm
that has made $k$ queries. The adversary matrix is
$\Gamma=\sum_{k=0}^{m-1}W_{\leq k}$. It is easy to see it has norm $m$, and we
prove that $\|\Gamma\circ\Delta_{j}\|\leq 1$ for all $j$. This proof is
contained in Sections 3 and 4. In Section 3, we only consider the space
$\mathbb{R}^{X}$, and in Section 4, we substitute $\mathbb{R}^{X}$ with
$\mathbb{R}^{Y}$ using indistinguishability.

In Section 5, we show how to use this result to transform a dual polynomial
into an adversary bound. The idea is that a dual polynomial gives probability
distributions $\mu$ and $\nu$ on two sets $\widetilde{X}$ and $\widetilde{Y}$
that are “close” to $X$ and $Y$ and that satisfy the promise of Theorem 1. We
first prove the lower bound in the form of the adversary for distinguishing
two probability distributions from [11], as we think it is conceptually closer
to the dual polynomial. Obtaining a standard worst-case adversary bound is
also easy. It is just the restriction $\widetilde{\Gamma}[\\![X,Y]\\!]$ of the
matrix $\widetilde{\Gamma}$ obtained in the second proof of Theorem 1 for
$\widetilde{X}$ and $\widetilde{Y}$.

##  2 Preliminaries

For a positive integer $m$, let $[m]$ denote the set $\\{1,2,...,m\\}$. For a
predicate $P$, we write $1_{P}$ to denote the indicator variable that is 1 is
$P$ is true, and 0 otherwise.

We consider partial functions $f\colon D\to\\{0,1\\}$ with
$D\subseteq[q]^{n}$. We denote $X=f^{-1}(1)$ and $Y=f^{-1}(0)$. Thus, the
function $f$ distinguishes $X$ and $Y$. An element
$x=(x_{1},x_{2},\dots,x_{n})\in[q]^{n}$, is called an _input_ , the set $[q]$
is called the _input alphabet_ , and $x_{j}\in[q]$ are individual input
symbols.

A _measure_ on a finite set $X$ is a function $\mu$ from $X$ to the set of
non-negative real numbers. We denote the value of $\mu$ on $x\in X$ by
$\mu_{x}$. The measure is a _probability distribution_ if $\sum_{x\in
X}\mu_{x}=1$. We use $x\leftarrow\mu$ to denote that $x$ is sampled from the
probability distribution $\mu$.

An _assignment_ is a function $\alpha\colon S\to[q]$ defined on a subset $S$
of the set of indices $[n]$. We write $x\sim\alpha$ if $x\in X$ _agrees_ with
the assignment $\alpha$, that is, $x_{j}=\alpha(j)$ for all $j\in S$. The
weight $|\alpha|$ of the assignment is the size of $S$. It is possible to have
an empty assignment $\emptyset$ of zero weight, in which case, every input
string agrees to it.

#### Linear Algebra

An $X\times Y$ matrix is a matrix with rows labelled by the elements of $X$
and columns by the elements of $Y$. The element of an $X\times Y$ matrix $A$
at the intersection of the $x$-th row and the $y$-th column is denoted by
$A[\\![x,y]\\!]$. For $X^{\prime}\subseteq X$ and $Y^{\prime}\subseteq Y$, the
matrix $A[\\![X^{\prime},Y^{\prime}]\\!]$ is the restriction of $A$ to the
rows in $X^{\prime}$ and the columns in $Y^{\prime}$. We identify a subspace
and the corresponding orthogonal projector, which we usually denote by $\Pi$
with additional decorations. An _isometry_ is a linear operator that preserves
inner product. We need the following well-known result:

######  Lemma 2.

Assume $\mathcal{H}$ and $\mathcal{K}$ are two inner-product spaces. Let
$(v_{i})_{i\in A}\subseteq\mathcal{H}$ and $(w_{i})_{i\in
A}\subseteq\mathcal{K}$ be two collections of vectors indexed by the same
index set $A$. Assume $\mathopen{}\mathclose{{}\left\langle
v_{i},v_{j}}\right\rangle=\mathopen{}\mathclose{{}\left\langle
w_{i},w_{j}}\right\rangle$ for all $i,j\in A$. Then, there exists an isometry
$T\colon\operatorname*{span}_{i}v_{i}\to\operatorname*{span}_{i}w_{i}$ such
that $Tv_{i}=w_{i}$ for all $i$.

#### Adversary Bound

We use two different flavours of the negative-weighted adversary bound. Here
we give the canonical version from [21] and later we state the distributional
version from [11].

Assume we want to distinguish two sets of inputs $X,Y\subseteq[q]^{n}$ as
above. Let $\Gamma$ be a real $X\times Y$ matrix. For $j\in[n]$, denote by
$\Gamma\circ\Delta_{j}$ the matrix of the same dimensions as $\Gamma$ whose
$(x,y)$-th entry is given by $\Gamma[\\![x,y]\\!]\cdot 1_{x_{j}\neq y_{j}}$.
In other words, the entries with $x_{j}=y_{j}$ are being erased (replaced by
zeroes).

######  Theorem 3 ([21]).

Assume that $\Gamma$ is an $X\times Y$ real matrix such that
$\|\Gamma\circ\Delta_{j}\|\leq 1$ for all $j\in[n]$. Then, the (bounded-error)
quantum query complexity of evaluating $f$ is $\Omega(\|\Gamma\|)$.

The matrix $\Gamma$ from Theorem 3 is called the _adversary matrix_ , and it
is known that the bound of this theorem is tight [29].

As it can be guessed from the notation, the mapping
$\Gamma\mapsto\Gamma\circ\Delta_{j}$ is usually expressed as an Hadamard
product with a 01-matrix $\Delta_{j}$ of dimensions $X\times Y$. However, we
find it more convenient to think of it as a mapping. In particular, we don’t
have to formally re-define the matrix $\Delta_{j}$ for matrices $\Gamma$ of
different dimensions, and the matrix $\Delta_{j}$ almost never appears by
itself.

The norm of the matrix $\Gamma\circ\Delta_{j}$ is not always easy to estimate.
The following trick from [22] is of help here. With some stretch of notation,
we write $\Gamma\stackrel{{\scriptstyle\Delta_{j}}}{{\longmapsto}}B$ if
$(\Gamma-B)\circ\Delta_{j}=0$. In other words, we are allowed to arbitrary
change the $(x,y)$-entries of $\Gamma$ with $x_{j}=y_{j}$ in order to obtain
$B$. The idea is as follows:

######  Proposition 4.

For any $B$ with $\Gamma\stackrel{{\scriptstyle\Delta_{j}}}{{\longmapsto}}B$,
we have $\|\Gamma\circ\Delta_{j}\|\leq 2\|B\|$. Moreover, if $f$ is a Boolean
function, i.e., $D\subseteq\\{0,1\\}^{n}$, then
$\|\Gamma\circ\Delta_{j}\|\leq\|B\|$.

Hence, we can bound $\|\Gamma\circ\Delta_{j}\|$ from above by estimating
$\|B\|$, which is often easier.

#### Distributional Adversary

We also use the version of the adversary bound for distinguishing two
probability distributions. This version is rather versatile as it allows the
probability distributions to overlap and to have arbitrary acceptance
probabilities.

######  Theorem 5 ([11]).

Let $D=[q]^{n}$. Assume $\mathcal{A}$ is a quantum algorithm that makes $T$
queries to the input string $x=(x_{1},\dots,x_{n})\in D$, and performs a
measurement at the end with two outcomes ’accept’ or ’reject’. Let $\mu$ and
$\nu$ be two probability distributions on $D$, and denote by $s_{\mu}$ and
$s_{\nu}$ the acceptance probability of $\mathcal{A}$ when $x$ is sampled from
$\mu$ and $\nu$, respectively. Then,

$T=\Omega\mathopen{}\mathclose{{}\left(\min_{j\in[n]}\frac{\delta_{\mu}^{*}\Gamma\delta_{\nu}^{\phantom{*}}-\tau(s_{\mu},s_{\nu})\|\Gamma\|}{\|\Gamma\circ\Delta_{j}\|}}\right),$
(2)

for any $D\times D$ matrix $\Gamma$ with real entries. Here,

$\delta_{\mu}[\\![x]\\!]=\sqrt{\mu_{x}}\qquad\text{and}\qquad\delta_{\nu}[\\![y]\\!]=\sqrt{\nu_{y}}$
(3)

are unit vectors in $\mathbb{R}^{D}$, and

$\tau(s_{\mu},s_{\nu})=\sqrt{s_{\mu}s_{\nu}}+\sqrt{(1-s_{\mu})(1-s_{\nu})}\leq
1-\frac{|s_{\mu}-s_{\nu}|^{2}}{8}.$ (4)

#### Polynomials

In the polynomial method, we have to assume that the function $f\colon
D\to\\{0,1\\}$ is Boolean: $D\subseteq\\{0,1\\}^{n}$. If this does not hold,
one has to make the function Boolean. A popular option is to introduce new
variables $\widetilde{x_{i,a}}$ with $i\in[n]$ and $a\in[q]$, defined by
$\widetilde{x_{i,a}}=1_{x_{i}=a}$.

For $S\subseteq[n]$, the corresponding _character_ is the function
$\chi_{S}\colon\\{0,1\\}^{n}\to\\{\pm 1\\}$ defined by
$\chi_{S}(x)=\prod_{i}(-1)^{x_{i}}$. The characters form a basis of the space
of functions $\mathbb{R}^{\\{0,1\\}^{n}}$. Hence, every function
$f\colon\\{0,1\\}^{n}\to\mathbb{R}$ has a unique representation as a
_polynomial_ : $f=\sum_{S\subseteq[n]}\alpha_{S}\chi_{S}$. The size of the
largest $S$ with non-zero $\alpha_{S}$ is called the _degree_ of $f$.

A degree-$d$ _polynomial_ is any function $p\colon\\{0,1\\}^{n}\to\mathbb{R}$
of degree at most $d$. A degree-$d$ _dual polynomial_ is a function
$\phi\colon\\{0,1\\}^{n}\to\mathbb{R}$ satisfying

$\sum_{x\in\\{0,1\\}^{n}}\mathopen{}\mathclose{{}\left\lvert\phi(x)}\right\rvert=1\qquad\text{and}\qquad\sum_{x\in\\{0,1\\}^{n}}\phi(x)\chi_{S}(x)=0\quad\text{for
all $|S|\leq d$}.$

It is easy to check that the second condition above is equivalent to the
following one:

$\sum_{x\sim\alpha}\phi(x)=0\quad\text{for all assignments $\alpha$ with
$|\alpha|\leq d$.}$ (5)

Dual polynomials [31] can be used to show inapproximability for real-valued
total functions. We may assume $d<n$, since every function can be represented
by a degree-$d$ polynomial.

######  Theorem 6.

Let $d<n$. For any function $f\colon\\{0,1\\}^{n}\to\mathbb{R}$, we have

$\min_{p}\max_{x\in\\{0,1\\}^{n}}|f(x)-p(x)|=\max_{\phi}\sum_{x\in\\{0,1\\}^{n}}\phi(x)f(x),$
(6)

where $p$ ranges over all degree-$d$ polynomials and $\phi$ ranges over all
degree-$d$ dual polynomials.

Let us now turn to the case of partial functions $f\colon D\to\\{0,1\\}$ with
$D\subseteq\\{0,1\\}^{n}$. Again, we let $X=f^{-1}(1)$ and $Y=f^{-1}(0)$.

######  Definition 7.

We say that a polynomial $p\colon\\{0,1\\}^{n}\to\mathbb{R}$
$\varepsilon$-approximates a partial function $f\colon D\to\\{0,1\\}$ with
$D\subseteq\\{0,1\\}^{n}$ if

  * •

for every $x\in D$, we have $|p(x)-f(x)|\leq\varepsilon$;

  * •

for every $x\in\\{0,1\\}^{n}$, we have $0\leq p(x)\leq 1$.

The importance of this definition stems from the following result:

######  Theorem 8 ([9]).

If a partial function $f\colon D\to\\{0,1\\}$ with $D\subseteq\\{0,1\\}^{n}$
can be evaluated by a $T$-query quantum algorithm with error at most
$\varepsilon$, then $f$ can be $\varepsilon$-approximated by a polynomial of
degree at most $2T$.

The corresponding analogue of Theorem 6 is slightly more involved.

######  Theorem 9.

The best approximation distance $\varepsilon$ as in Definition 7 of the
function $f$ by a degree-$d$ polynomial is given by

$\max\mathopen{}\mathclose{{}\left\\{\max_{\phi}\biggl{(}\sum_{x\in
X}\phi^{+}(x)-\sum_{x\notin Y}\phi^{-}(x)\biggr{)},0}\right\\},$ (7)

where the maximisation is over functions
$\phi\colon\\{0,1\\}^{n}\to\mathbb{R}$ satisfying

$\sum_{x\in X}\phi^{+}(x)+\sum_{x\in
Y}\phi^{-}(x)=1\qquad\text{and}\qquad\sum_{x\in\\{0,1\\}^{n}}\phi(x)\chi_{S}(x)=0\quad\text{for
all $|S|\leq d$}.$ (8)

Here $\phi^{+}(x)=\max\\{0,\phi(x)\\}$ and $\phi^{-}(x)=\max\\{0,-\phi(x)\\}$
are the positive and the negative parts of $\phi$, respectively.

The proofs of Theorems 6 and 9 are based on linear programming duality. They
are given in Appendix A for completeness.

###### Proof of Theorem 1 using Dual Polynomials.

We may assume the function $f$ is Boolean. It suffices to show that it cannot
be approximated a polynomial of degree less than $2m$. Let

$\phi(x)=\begin{cases}\mu_{x}/2,&\text{if $x\in X$;}\\\ -\nu_{x}/2,&\text{if
$x\in Y$;}\\\ 0,&\text{otherwise.}\end{cases}$

This function satisfies (8) with $d=2m$. Indeed, the first condition follows
from $\mu$ and $\nu$ being probability distributions, and the second one
follows from (5) since

$\sum_{x\sim\alpha}\phi(x)=\frac{1}{2}\Pr_{x\leftarrow\mu}[x\sim\alpha]-\frac{1}{2}\Pr_{y\leftarrow\nu}[y\sim\alpha]=0$

by (1). The value of (7) is $1/2$, meaning it is impossible to get a better
than trivial approximation. ∎

##  3  $\Delta$-decomposition of $\mathbb{R}^{X}$

Let $X\subseteq[q]^{n}$ be a set of inputs, and let $\mu$ be some measure on
$X$. The goal of this section is to develop a decomposition of the space
$\mathbb{R}^{X}$ convenient for the $\Delta_{i}$ operation and that takes into
account the measure $\mu$.

#### Definition of subspaces.

For each assignment $\alpha$, define the following vector in $\mathbb{R}^{X}$:

$v_{\alpha}=\sum_{x\sim\alpha}\sqrt{\mu_{x}}\mathopen{}\mathclose{{}\left|x}\right>_{\mathsf{}}.$

Based on these vectors, we define a number of subspaces. First, for
$k\in\\{0,1,\dots,n\\}$:

$\Pi_{\leq k}=\operatorname*{span}_{\alpha\colon|\alpha|=k}v_{\alpha}.$

######  Claim 10.

We have $\Pi_{\leq k-1}\subseteq\Pi_{\leq k}$ and $\Pi_{\leq
n}=\mathbb{R}^{X}$.

###### Proof.

Let $\alpha$ be an assignment of weight $k-1$, and $i$ be an element of $[n]$
outside the domain of $\alpha$. Then,

$v_{\alpha}=\sum_{a\in[q]}v_{\alpha\cup\\{i\mapsto a\\}},$

proving the first claim.

For the second claim, note that an assignment $\alpha$ of weight $n$ defines
an individual input. ∎

This gives an orthogonal decomposition of $\mathbb{R}^{X}$ into subspaces

$\Pi_{k}=\Pi_{\leq k}\cap\Pi_{\leq k-1}^{\perp}=\Pi_{\leq k}-\Pi_{\leq k-1}.$

#### Example.

A simple example is $X=[q]^{n}$ with the uniform distribution $\mu_{x}$.
Define two orthogonal projectors on $\mathbb{R}^{q}$: $E_{0}=J_{q}/q$ and
$E_{1}=I_{q}-E_{0}$, where $J_{q}$ is the all-1 matrix. Then,

$\Pi_{k}=\sum_{s\in\\{0,1\\}^{n}:|s|=k}E_{s_{1}}\otimes
E_{s_{2}}\otimes\cdots\otimes E_{s_{n}},$

where $|s|$ is the Hamming weight. These operators are similar to the ones
used in the construction of the adversary lower bound for element distinctness
[10] and sum-problems [12].

#### Action of $\Delta_{1}$.

Let us consider the action of $\Delta_{1}$, the remaining $\Delta_{j}$ being
analogous. For that, we define the following variant of the above subspaces:

$\Pi_{\leq
k}^{\prime}=\operatorname*{span}_{\alpha\colon|\alpha|=k,\,\text{$\alpha$
defined on 1}}v_{\alpha}.$

In particular, we again have $\Pi_{\leq n}^{\prime}=\mathbb{R}^{X}$. However,
this time $\Pi_{\leq 0}^{\prime}$ is the empty subspace.

######  Claim 11.

We have the following:

  * (a)

$\Pi_{\leq k-1}^{\prime}\subseteq\Pi_{\leq k}^{\prime}$;

  * (b)

$\Pi_{\leq k-1}\subseteq\Pi_{\leq k}^{\prime}\subseteq\Pi_{\leq k}$;

  * (c)

$\Delta_{1}\circ\Pi_{\leq k}^{\prime}=0$.

###### Proof.

The proof of (a) is analogous to the proof of Claim 10.

The second inclusion of (b) holds because $\Pi_{\leq k}^{\prime}$ is a span of
a subset of vectors of $\Pi_{\leq k}$. To prove the first inclusion of (b), it
suffices to show that an arbitrary $v_{\alpha}$ with $|\alpha|=k-1$ is
contained in $\Pi_{\leq k}^{\prime}$. The proof of that is analogous to the
proof of Claim 10. However, this time we take $i=1$ if $\alpha$ is not defined
on 1 (and an arbitrary $i$ as before, otherwise).

Now let us prove (c). Note that $\Pi^{\prime}_{\leq k}$ can be written as a
direct sum

$\Pi^{\prime}_{\leq k}=\bigoplus_{b\in[q]}\Pi^{\prime}_{\leq
k,b}\vspace{-\bigskipamount}$

of orthogonal projectors

$\Pi^{\prime}_{\leq
k,b}=\operatorname*{span}_{\alpha\colon|\alpha|=k,\;\alpha(1)=b}v_{\alpha}.$

Each $\Pi^{\prime}_{\leq k,b}$ acts on the subspace spanned by $x\in X$ with
$x_{1}=b$. Hence, $\Delta_{1}\circ\Pi^{\prime}_{\leq k,b}=0$. By linearity,
$\Delta_{1}\circ\Pi^{\prime}_{\leq k}=0$. ∎

#### Standard Form of Adversary

As a warm-up for the next sections, we describe the following “standard” form
of the “adversary” matrix on $\mathbb{R}^{X}$:

$\sum_{k=0}^{m-1}\Pi_{\leq k}=\sum_{k=0}^{m}(m-k)\Pi_{k}.$ (9)

Clearly, the norm of this matrix is $m$. The action of $\Delta_{1}$ is defined
as

$\sum_{k=0}^{m-1}\Pi_{\leq
k}\stackrel{{\scriptstyle\Delta_{1}}}{{\longmapsto}}\sum_{k=0}^{m-1}\bigl{(}\Pi_{\leq
k}-\Pi^{\prime}_{\leq k}\bigr{)},$ (10)

where we use point (c) of Claim 11.

######  Claim 12.

The norm of the operator on the right-hand side of (10) is 1.

###### Proof.

The operator in question is a sum of projectors $\Pi_{\leq k}-\Pi_{\leq
k}^{\prime}$. By point (b) of Claim 11, we know that $\Pi_{\leq k}$ is
contained in $\Pi_{\leq k+1}^{\prime}$. Hence, these projectors are pairwise
orthogonal, and the norm of the operator is 1. ∎

In the following section, we will mimic this construction but $X\times
Y$-matrices.

##  4 Second Proof of Theorem 1

In this section, we give a proof of Theorem 1, which is based on the adversary
method.

We use $v^{X}_{\alpha}$ and $v^{Y}_{\alpha}$ to denote vectors defined on the
input sets $X$ and $Y$:

$v^{X}_{\alpha}=\sum_{x\in
X:x\sim\alpha}\sqrt{\mu_{x}}\mathopen{}\mathclose{{}\left|x}\right>_{\mathsf{}}\qquad\text{and}\qquad
v^{Y}_{\alpha}=\sum_{y\in
Y:y\sim\alpha}\sqrt{\nu_{y}}\mathopen{}\mathclose{{}\left|y}\right>_{\mathsf{}},$

and similarly for $\Pi_{\leq k}^{X}$, $\Pi_{\leq k}^{Y}$, $\Pi_{\leq
k}^{\prime X}$ and $\Pi_{\leq k}^{\prime Y}$.

Let $\alpha$ and $\beta$ be assignments of weight at most $m$. Note that

$\mathopen{}\mathclose{{}\left\langle
v^{X}_{\alpha},v^{X}_{\beta}}\right\rangle=\Pr_{x\sim\mu}[x\sim\alpha\wedge
x\sim\beta]=\Pr_{y\sim\nu}[y\sim\alpha\wedge
y\sim\beta]=\mathopen{}\mathclose{{}\left\langle
v^{Y}_{\alpha},v^{Y}_{\beta}}\right\rangle.$

Indeed, either $\alpha$ and $\beta$ contradict each other, in which case the
both sides of the above equality are zero, or they can be merged into one
assignment of size at most $2m$, in which case (1) applies.

Hence, by Lemma 2, there exists a linear operator $W$ that maps
$v^{Y}_{\alpha}$ into $v^{X}_{\alpha}$ for each $|\alpha|\leq m$. It is an
isometry from $\Pi_{\leq m}^{Y}$ onto $\Pi_{\leq m}^{X}$, and it induces the
following isometries:

$W_{\leq k}\colon\Pi_{\leq k}^{Y}\to\Pi_{\leq k}^{X}\qquad\text{and}\qquad
W^{\prime}_{\leq k}\colon\Pi_{\leq k}^{\prime Y}\to\Pi_{\leq k}^{\prime X}$

for all $k\leq m$.

######  Claim 13.

We have $\Delta_{1}\circ W^{\prime}_{\leq k}=0$.

###### Proof.

The proof is similar to the point (c) of Claim 11. ∎

We use the adversary matrix similar to (9), but this time this is an $X\times
Y$ matrix

$\Gamma=\sum_{k=0}^{m-1}W_{\leq k}=W\Biggl{(}{\sum_{k=0}^{m-1}\Pi^{Y}_{\leq
k}}\Biggr{)}.$ (11)

Since $W$ is an isometry, the norm of $\Gamma$ is $m$. Again, the action of
$\Delta_{1}$ is defined by

$\Gamma\stackrel{{\scriptstyle\Delta_{1}}}{{\longmapsto}}\sum_{k=0}^{m}\bigl{(}W_{\leq
k}-W^{\prime}_{\leq k}\bigr{)}=W\Biggl{(}{\sum_{k=0}^{m}\bigl{(}\Pi^{Y}_{\leq
k}-\Pi^{\prime Y}_{\leq k}\bigr{)}}\Biggr{)},$

and the norm of the latter matrix is 1 by Claim 12 and using that $W$ is an
isometry again. At this point, we can use Theorem 3.

The preceding derivation also works in the case when $\mu$ and $\nu$ have
overlapping supports, or not totally concentrated on $X$ and $Y$. In this
case, it could be easier to prove quantum indistinguishability of $\mu$ and
$\nu$ directly using Theorem 5. For this theorem, the following result is
useful:

######  Proposition 14.

If $\mu$ and $\nu$ are probability distributions, and $\Gamma$ is defined as
in (11), then

$\|\Gamma\|=\delta_{\mu}^{*}\Gamma\delta_{\nu}^{\phantom{*}}=m,$

where $\delta_{\mu}$ and $\delta_{\nu}$ are defined in (3).

###### Proof.

Observing the right-hand side of (9) and the definition of $\Gamma$, we see
that the maximal singular value of $\Gamma$ is $m$, with the corresponding
left and right singular vectors lying in $\Pi^{X}_{0}$ and $\Pi^{Y}_{0}$,
respectively. By definition, $\Pi^{X}_{0}=\Pi_{\leq 0}^{X}$ projects onto
$v^{X}_{\emptyset}=\delta_{\mu}$ and $\Pi^{Y}_{0}=\Pi_{\leq 0}^{Y}$ projects
onto $v^{Y}_{\emptyset}=\delta_{\nu}$, where $\emptyset$ denotes the empty
assignment. ∎

##  5 Polynomial Lower Bounds

In this section, we demonstrate a direct conversion of a polynomial lower
bound into an adversary lower bound. We do so by taking a dual polynomial that
witnesses degree at least $d$ and convert it into an adversary bound of value
$\Omega(d)$.

For warm-up, we consider the case of total functions in Section 5.1, and then
the general case of partial functions in Section 5.2. In both cases, we use
the distributional version of the adversary bound, Theorem 5, which we find
conceptually more appropriate in this case. However, it is not hard to reduce
to the usual version of the bound, Theorem 3, as well, which we do in Section
5.3.

###  5.1 Total Functions

We start with the case when $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a total
Boolean function. Assume it cannot be $1/3$-approximated by a polynomial of
degree $d$. In this case, we can use Theorem 6. Let $\phi$ be a degree-$d$
dual polynomial attaining the maximum in (6). Thus,

$\sum_{x\in\\{0,1\\}^{n}}\phi(x)f(x)\geq 1/3.$ (12)

Our goal is to prove an adversary lower bound of $\Omega(d)$.

Let us define

$\widetilde{X}=\\{x\in\\{0,1\\}^{n}\mid\phi(x)\geq
0\\}\qquad\text{and}\qquad\widetilde{Y}=\\{y\in\\{0,1\\}^{n}\mid\phi(y)<0\\},$
(13)

and two measures

$\mu\colon\widetilde{X}\to\mathbb{R},\,x\mapsto
2\phi(x)\qquad\text{and}\qquad\nu\colon\widetilde{Y}\to\mathbb{R},\,y\mapsto-2\phi(y).$

From (5) applied to empty $\alpha$, we get that $\sum_{x}\phi(x)=0$. Also,
$\sum_{x}|\phi(x)|=1$. Hence,

$\sum_{x\in\widetilde{X}}\mu_{x}=\sum_{y\in\widetilde{Y}}\nu_{y}=1,$ (14)

that is, both $\mu$ and $\nu$ are probability distributions.

Using (5) again, we get that for each assignment $\alpha$ of weight at most
$d$, we have

$\Pr_{x\leftarrow\mu}[x\sim\alpha]=\Pr_{y\leftarrow\nu}[y\sim\alpha].$ (15)

Thus, by Theorem 1, the quantum query complexity of distinguishing
$\widetilde{X}$ and $\widetilde{Y}$ is $\Omega(d)$. This is a nice
development, but we would really like to prove the same result for the sets
$X=f^{-1}(1)$ and $Y=f^{-1}(0)$. Luckily, by condition (12), these sets are
sufficiently well correlated.

Take $\widetilde{\Gamma}$ as in (11) with sets $\widetilde{X}$ and
$\widetilde{Y}$ and distributions $\mu$ and $\nu$. By the results of Section
4, we get that

$\|\widetilde{\Gamma}\|=\delta_{\mu}^{*}\widetilde{\Gamma}\delta_{\nu}^{\phantom{*}}=d/2,\qquad\text{and}\qquad\|\widetilde{\Gamma}\circ\Delta_{j}\|\leq
1\quad\text{for all $j\in[n]$}.$ (16)

Let $\mathcal{A}$ be a quantum algorithm that evaluates the function $f$. We
apply Theorem 5 on this algorithm and distributions $\mu$ and $\nu$. Note that
(12) is equivalent to

$\sum_{x\in f^{-1}(1)}\mu_{x}-\sum_{y\in f^{-1}(1)}\nu_{y}\geq 2/3.$

This is the difference between the “ideal” acceptance probabilities of
$\mathcal{A}$ on $\mu$ and $\nu$, i.e, in the hypothetical case when the
algorithm never errs. Assuming the actual error of the algorithm $\mathcal{A}$
is at most 1/6, we get that

$s_{\mu}-s_{\nu}\geq 1/3$

in notations of Theorem 5. From (4), we get that $\tau(s_{\mu},s_{\nu})\leq
1-\Omega(1)$. Pluging this and (16) into (2), we get that the query complexity
of $\mathcal{A}$ is $\Omega(d)$.

###  5.2 Partial Functions

Now let us consider the case of partial functions, for which we have to use
Theorem 9. Again, assume that $\phi$ is optimal. Then we have from (7):

$\sum_{x\in X}\phi^{+}(x)-\sum_{x\notin Y}\phi^{-}(x)\geq 1/3.$ (17)

The sets $\widetilde{X}$ and $\widetilde{Y}$ are still defined as in (13). In
order to define $\mu$ and $\nu$, we have to choose a different scaling factor.

By (8), we still have that
$\sum_{x\in\\{0,1\\}^{n}}\phi^{+}(x)=\sum_{x\in\\{0,1\\}^{n}}\phi^{-}(x).$
Also

$\sum_{x\in\\{0,1\\}^{n}}\phi^{-}(x)=\sum_{x\in Y}\phi^{-}(x)+\sum_{x\notin
Y}\phi^{-}(x)\leq\sum_{x\in Y}\phi^{-}(x)+\sum_{x\in X}\phi^{+}(x)-1/3=2/3,$

where we used (17) and the first condition from (8). Let us denote the left-
hand side of the above inequality by $M$. Then, we can define probability
distributions

$\mu\colon\widetilde{X}\to\mathbb{R},\,x\mapsto\phi(x)/M\qquad\text{and}\qquad\nu\colon\widetilde{Y}\to\mathbb{R},\,y\mapsto-\phi(y)/M.$

So that (17) becomes

$\sum_{x\in X}\mu_{x}-\sum_{y\notin Y}\nu_{y}\geq 1/2.$ (18)

The equation (15) still holds, and we use the same construction of
$\widetilde{\Gamma}$, which still satisfies (16).

Let $\mathcal{A}$ be an algorithm that evaluates $f$ with error $\varepsilon$.
Denote by $p_{x}$ the acceptance probability of the algorithm on input
$x\in\\{0,1\\}^{n}$. So, we have $p_{x}\geq 1-\varepsilon$ for $x\in X$,
$p_{x}\leq\varepsilon$ for $x\in Y$, and $0\leq p_{x}\leq 1$ for all $x$.
Thus,

$\displaystyle s_{\mu}-s_{\nu}$ $\displaystyle=\sum_{x\in
X}\mu_{x}p_{x}+\sum_{x\notin X}\mu_{x}p_{x}-\sum_{y\in
Y}\nu_{y}p_{y}-\sum_{y\notin Y}\nu_{y}p_{y}$
$\displaystyle\geq(1-\varepsilon)\sum_{x\in X}\mu_{x}-\varepsilon\sum_{y\in
Y}\nu_{y}-\sum_{y\notin Y}\nu_{y}\geq\sum_{x\in X}\mu_{x}-\sum_{y\notin
Y}\nu_{y}-2\varepsilon\geq 1/2-2\varepsilon\geq 1/4,$

assuming $\varepsilon\leq 1/8$.

In the same way as in Section 5.1, Theorem 5 implies that the query complexity
of $\mathcal{A}$ is $\Omega(d)$.

###  5.3 Usual Version of the Adversary

Here we give the same proof using the usual formulation of the adversary
bound, Theorem 3. Assume we are in the general case of partial functions of
Section 5.2. We define

$\Gamma=\widetilde{\Gamma}[\\![X,Y]\\!].$

As $\Gamma$ is a sub-matrix of $\widetilde{\Gamma}$, we get
$\|\Gamma\circ\Delta_{j}\|\leq 1$ for all $j$ from (16). It suffices to show
that $\|\Gamma\|=\Omega\bigl{(}\|\widetilde{\Gamma}\|\bigr{)}$.

We know that
$\widetilde{\Gamma}\delta_{\nu}=\|\widetilde{\Gamma}\|\delta_{\mu}$ by
Proposition 14. This gives us

$\mathopen{}\mathclose{{}\left\lVert\widetilde{\Gamma}[\\![X,\\{0,1\\}^{n}]\\!]\;\delta_{\nu}}\right\rVert=\bigl{\lVert}\widetilde{\Gamma}\bigr{\rVert}\cdot\bigl{\lVert}\delta_{\mu}[\\![X]\\!]\bigr{\rVert}.$

On the other hand,

$\mathopen{}\mathclose{{}\left\lVert\widetilde{\Gamma}[\\![X,\\{0,1\\}^{n}]\\!]\;\delta_{\nu}}\right\rVert\leq\mathopen{}\mathclose{{}\left\lVert\widetilde{\Gamma}[\\![X,Y]\\!]\;\delta_{\nu}[\\![Y]\\!]}\right\rVert+\mathopen{}\mathclose{{}\left\lVert\widetilde{\Gamma}[\\![X,\overline{Y}]\\!]\;\delta_{\nu}[\\![\overline{Y}]\\!]}\right\rVert\leq\bigl{\lVert}\widetilde{\Gamma}[\\![X,Y]\\!]\bigr{\rVert}+\bigl{\lVert}\widetilde{\Gamma}\bigr{\rVert}\cdot\mathopen{}\mathclose{{}\left\lVert\delta_{\nu}[\\![\overline{Y}]\\!]}\right\rVert,$

where $\overline{Y}=\\{0,1\\}^{n}\setminus Y$. Thus,

$\bigl{\lVert}\widetilde{\Gamma}[\\![X,Y]\\!]\bigr{\rVert}\geq\bigl{\lVert}\widetilde{\Gamma}\bigr{\rVert}\Bigl{(}\bigl{\lVert}\delta_{\mu}[\\![X]\\!]\bigr{\rVert}-\mathopen{}\mathclose{{}\left\lVert\delta_{\nu}[\\![\overline{Y}]\\!]}\right\rVert\Bigr{)}=\bigl{\lVert}\widetilde{\Gamma}\bigr{\rVert}\frac{\bigl{\lVert}\delta_{\mu}[\\![X]\\!]\bigr{\rVert}^{2}-\mathopen{}\mathclose{{}\left\lVert\delta_{\nu}[\\![\overline{Y}]\\!]}\right\rVert^{2}}{\bigl{\lVert}\delta_{\mu}[\\![X]\\!]\bigr{\rVert}+\mathopen{}\mathclose{{}\left\lVert\delta_{\nu}[\\![\overline{Y}]\\!]}\right\rVert}.$

From (18), we get that

$\bigl{\lVert}\delta_{\mu}[\\![X]\\!]\bigr{\rVert}^{2}-\mathopen{}\mathclose{{}\left\lVert\delta_{\nu}[\\![\overline{Y}]\\!]}\right\rVert^{2}=\sum_{x\in
X}\mu_{x}-\sum_{y\notin Y}\nu_{y}\geq 1/2.$

Also,
$\bigl{\lVert}\delta_{\mu}[\\![X]\\!]\bigr{\rVert}+\mathopen{}\mathclose{{}\left\lVert\delta_{\nu}[\\![\overline{Y}]\\!]}\right\rVert\leq
2$, hence, we obtain

$\bigl{\lVert}\widetilde{\Gamma}[\\![X,Y]\\!]\bigr{\rVert}\geq\frac{1}{4}\bigl{\lVert}\widetilde{\Gamma}\bigr{\rVert},$

as required.

## Acknowledgements

The author is thankful to Shalev Ben-David for the suggestion to apply this
construction to the polynomial method.

This work has been supported by the ERDF project number 1.1.1.5/18/A/020
“Quantum algorithms: from complexity theory to experiment.”

## References

  * [1] S. Aaronson, S. Ben-David, and R. Kothari.  Separations in query complexity using cheat sheets.  In Proc. of 48th ACM STOC, pages 863–876, 2016.  arXiv:1511.01937.
  * [2] S. Aaronson, S. Ben-David, R. Kothari, S. Rao, and A. Tal.  Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem.  In Proc. of 53rd ACM STOC, pages 1330–1342, 2021.  arXiv:2010.12629.
  * [3] S. Aaronson and Y. Shi.  Quantum lower bounds for the collision and the element distinctness problems.  Journal of the ACM, 51(4):595–605, 2004.
  * [4] A. Ambainis.  Quantum lower bounds by quantum arguments.  Journal of Computer and System Sciences, 64(4):750–767, 2002.  Earlier: STOC’00, arXiv:quant-ph/0002066.
  * [5] A. Ambainis.  Polynomial degree vs. quantum query complexity.  In Proc. of 44th IEEE FOCS, pages 230–239, 2003.  arXiv:quant-ph/0305028.
  * [6] A. Ambainis and A. Belovs.  An exponential separation between quantum query complexity and the polynomial degree.  arXiv:2301.09218, 2023.
  * [7] H. Barnum and M. Saks.  A lower bound on the quantum query complexity of read-once functions.  Journal of Computer and System Sciences, 69(2):244–258, 2004.  arXiv:quant-ph/0201007.
  * [8] H. Barnum, M. Saks, and M. Szegedy.  Quantum decision trees and semi-definite programming.  In Proc. of 18th IEEE CCC, pages 179–193, 2003.
  * [9] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM, 48(4):778–797, 2001.  Earlier: FOCS’98, arXiv:quant-ph/9802049.
  * [10] A. Belovs.  Adversary lower bound for element distinctness.  arXiv:1204.5074, 2012.
  * [11] A. Belovs, G. Brassard, P. Høyer, M. Kaplan, S. Laplante, and L. Salvail.  Provably secure key establishment against quantum adversaries.  In Proc. of 12th TQC, volume 73 of LIPIcs, pages 3:1–3:17. Dagstuhl, 2018\.  arXiv:1704.08182.
  * [12] A. Belovs and A. Rosmanis.  On the power of non-adaptive learning graphs.  Computational Complexity, 23(2):323–354, 2014.  Earlier: CCC’13, arXiv:1210.3279.
  * [13] A. Belovs and R. Špalek.  Adversary lower bound for the $k$-sum problem.  In Proc. of 4th ACM ITCS, pages 323–328, 2013.  arXiv:1206.6528.
  * [14] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani.  Strengths and weaknesses of quantum computing.  SIAM Journal on Computing, 26(5):1510–1523, 1997.  arXiv:quant-ph/9701001.
  * [15] H. Buhrman and R. Špalek.  Quantum verification of matrix products.  In Proc. of 17th ACM-SIAM SODA, pages 880–889, 2006.  arXiv:quant-ph/0409035.
  * [16] M. Bun, R. Kothari, and J. Thaler.  The polynomial method strikes back: Tight quantum query bounds via dual polynomials.  In Proc. of 50th ACM STOC, pages 297–310, 2018.  arXiv:1710.09079.
  * [17] M. Bun and J. Thaler.  Dual lower bounds for approximate degree and Markov-Bernstein inequalities.  Information and Computation, 243:2–25, 2015.  Earlier: ICALP’13, arXiv:1302.6191.
  * [18] S. Dörn and T. Thierauf.  The quantum query complexity of algebraic properties.  In Proc. of 16th FCT, volume 4639 of LNCS, pages 250–260. Springer, 2007\.  arXiv:0705.1446.
  * [19] C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla.  Quantum query complexity of some graph problems.  In Proc. of 31st ICALP, volume 3142 of LNCS, pages 481–493. Springer, 2004\.  arXiv:quant-ph/0401091.
  * [20] L. K. Grover.  A fast quantum mechanical algorithm for database search.  In Proc. of 28th ACM STOC, pages 212–219, 1996.  arXiv:quant-ph/9605043.
  * [21] P. Høyer, T. Lee, and R. Špalek.  Negative weights make adversaries stronger.  In Proc. of 39th ACM STOC, pages 526–535, 2007.  arXiv:quant-ph/0611054.
  * [22] T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy.  Quantum query complexity of state conversion.  In Proc. of 52nd IEEE FOCS, pages 344–353, 2011.  arXiv:1011.3020.
  * [23] Q. Liu and M. Zhandry.  On finding quantum multi-collisions.  In Proc. of 38th EUROCRYPT, volume 11478 of LNCS, pages 189–218, 2019.  arXiv:1811.05385.
  * [24] L. Magnin and J. Roland.  Explicit relation between all lower bound techniques for quantum query complexity.  In Proc. of 30th STACS, volume 20 of LIPIcs, pages 434–445. Dagstuhl, 2013\.  arXiv:1209.2713.
  * [25] N. S. Mande, J. Thaler, and S. Zhu.  Improved approximate degree bounds for k-distinctness.  In Proc. of 15th TQC, volume 158 of LIPIcs, pages 2:1–2:22, 2020.  arXiv:2002.08389.
  * [26] N. Nisan.  CREW PRAMs and decision trees.  SIAM Journal on Computing, 20(6):999–1007, 1991.  Earlier: STOC’89.
  * [27] N. Nisan and M. Szegedy.  On the degree of Boolean functions as real polynomials.  Computational Complexity, 4(4):301–313, 1994.  Earlier: STOC’92.
  * [28] B. W. Reichardt.  Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function.  In Proc. of 50th IEEE FOCS, pages 544–551, 2009.  arXiv:0904.2759.
  * [29] B. W. Reichardt.  Reflections for quantum query algorithms.  In Proc. of 22nd ACM-SIAM SODA, pages 560–569, 2011.  arXiv:1005.1601.
  * [30] B. W. Reichardt and R. Špalek.  Span-program-based quantum algorithm for evaluating formulas.  Theory of Computing, 8:291–319, 2012.  Earlier: STOC’08, arXiv:0710.2630.
  * [31] A. A. Sherstov.  The pattern matrix method.  SIAM Journal on Computing, 40(6):1969, 2011.  Earlier: STOC’08, arXiv:0906.4291.
  * [32] A. A. Sherstov.  Approximating the and-or tree.  Theory of Computing, 9(20):653–663, 2013.  ECCC:2013/023.
  * [33] M. Zhandry.  How to record quantum queries, and applications to quantum indifferentiability.  In Proc. of 39th CRYPTO, volume 11693 of LNCS, pages 239–268, 2019.  ePrint:2018/276.
  * [34] S. Zhang.  On the power of Ambainis lower bounds.  Theoretical Computer Science, 339(2):241–256, 2005.  arXiv:quant-ph/0311060.

##  Appendix A Linear Programming for Dual Polynomials

###  A.1 Proof of Theorem 6

The left-hand side of (6) is equal to the optimal value of the following
linear optimisation problem:

minimise $\displaystyle\varepsilon$ subject to $\displaystyle
f(x)-\sum_{S}\alpha_{S}\chi_{S}(x)$ $\displaystyle\leq\varepsilon$ for all
$x\in\\{0,1\\}^{n}$; (19a) $\displaystyle f(x)-\sum_{S}\alpha_{S}\chi_{S}(x)$
$\displaystyle\geq-\varepsilon$ for all $x\in\\{0,1\\}^{n}$; (19b)
$\displaystyle\alpha_{S}$ $\displaystyle\in\mathbb{R}$ for all
$S\subseteq[n],\;|S|\leq d$; $\displaystyle\varepsilon$
$\displaystyle\in\mathbb{R}.$

Let us write the Lagrangian with the dual variables $a_{x}\geq 0$ for (19a)
and $b_{x}\geq 0$ for (19b):

$\varepsilon-\sum_{x}a_{x}\biggl{(}\varepsilon-f(x)+\sum_{S}\alpha_{S}\chi_{S}(x)\biggr{)}-\sum_{x}b_{x}\biggl{(}\varepsilon+f(x)-\sum_{S}\alpha_{S}\chi_{S}(x)\biggr{)}$
(20)

Let us denote $\phi(x)=a_{x}-b_{x}$, so that we can rewrite the last
expression as

$\sum_{x}\phi(x)f(x)+\varepsilon\biggl{(}1-\sum_{x}a_{x}-\sum_{x}b_{x}\biggr{)}-\sum_{S}\alpha_{S}\biggl{(}\sum_{x}\phi(x)\chi_{S}(x)\biggr{)}.$
(21)

In the dual optimisation problem, all of the brackets in (21) must be zero.

We can turn any dual polynomial into a feasible solution to the dual (21) by
taking $a_{x}=\phi^{+}(x)$ and $b_{x}=\phi^{-}(x)$.

For the opposite direction, consider optimal primal and dual solutions, whose
values are equal due to strong duality. If $\varepsilon>0$, then, by
complementary slackness, at most one of $a_{x}$ and $b_{x}$ is non-zero for
each $x$, therefore, $|\phi(x)|=a_{x}+b_{x}$. Hence, $\phi$ is a dual
polynomial satisfying $\sum_{x}\phi(x)f(x)=\varepsilon$. If $\varepsilon=0$,
we can take $\phi$ equal to the normalised parity function.

###  A.2 Proof of Theorem 9

In this case, we have the following linear programming problem:

minimise $\displaystyle\varepsilon$ subject to
$\displaystyle\sum_{S}\alpha_{S}\chi_{S}(x)$ $\displaystyle\geq 1-\varepsilon$
for all $x\in X$; (22a) $\displaystyle\sum_{S}\alpha_{S}\chi_{S}(x)$
$\displaystyle\leq\varepsilon$ for all $x\in Y$; (22b)
$\displaystyle\sum_{S}\alpha_{S}\chi_{S}(x)$ $\displaystyle\geq 0$ for all
$x\notin X$; (22c) $\displaystyle\sum_{S}\alpha_{S}\chi_{S}(x)$
$\displaystyle\leq 1$ for all $x\notin Y$; (22d) $\displaystyle\alpha_{S}$
$\displaystyle\in\mathbb{R}$ for all $S\subseteq[n],\;|S|\leq d$;
$\displaystyle\varepsilon$ $\displaystyle\in\mathbb{R}.$

Let us write the Lagrangian with the dual variables
$a_{x},b_{x},c_{x},d_{x}\geq 0$ for (22a)—(22d), respectively:

$\displaystyle\varepsilon$ $\displaystyle-$ $\displaystyle\sum_{x\in
X}a_{x}\biggl{(}\sum_{S}\alpha_{S}\chi_{S}(x)-1+\varepsilon\biggr{)}$
$\displaystyle-$ $\displaystyle\sum_{x\in
Y}b_{x}\biggl{(}\varepsilon-\sum_{S}\alpha_{S}\chi_{S}(x)\biggr{)}$ (23)
$\displaystyle-$ $\displaystyle\sum_{x\notin
X}c_{x}\biggl{(}\sum_{S}\alpha_{S}\chi_{S}(x)\biggr{)}$ $\displaystyle-$
$\displaystyle\sum_{x\notin
Y}d_{x}\biggl{(}1-\sum_{S}\alpha_{S}\chi_{S}(x)\biggr{)}$

Let us define

$\phi(x)=\begin{cases}a_{x}-d_{x}&\text{if $x\in X$;}\\\ c_{x}-b_{x}&\text{if
$x\in Y$;}\\\ c_{x}-d_{x}&\text{if $x\notin X\cup Y$.}\\\ \end{cases}$

Then, we can rewrite (23) as

$\sum_{x\in X}a_{x}-\sum_{x\notin Y}d_{x}+\varepsilon\biggl{(}1-\sum_{x\in
X}a_{x}-\sum_{x\in
Y}b_{x}\biggr{)}-\sum_{S}\alpha_{S}\biggl{(}\sum_{x\in\\{0,1\\}^{n}}\phi(x)\chi_{S}(x)\biggr{)}.$
(24)

Again, in the dual optimisation problem, all the brackets in (24) must be
zero.

If $\phi$ satisfies (8), then we can take $a_{x}=\phi^{+}(x)$ for $x\in X$,
$b_{x}=\phi^{-}(x)$ for $x\in Y$, $c_{x}=\phi^{+}(x)$ for $x\notin X$, and
$d_{x}=\phi^{-}(x)$ for $x\notin Y$, and get a feasible solution to the dual.

For the opposite direction, consider optimal primal and dual solutions, whose
values are equal by strong duality. We may assume $\varepsilon>0$. By
complementary slackness, for each $x$, at most one of the dual variables is
non-zero, except for the case when $\varepsilon=1/2$, in which case both
$a_{x}$ and $b_{x}$ can be non-zero. Either way, we get $a_{x}=\phi^{+}(x)$
for $x\in X$, $b_{x}=\phi^{-}(x)$ for $x\in Y$, and $d_{x}=\phi^{-}(x)$ for
$x\notin Y$. Thus we obtain the required dual formulation of Theorem 9.

Let us note that maximisation with 0 is required in (7). For example, consider
the case $d=n-1$, and $X$ and $Y$ are of size 1. The function can be
approximated by a polynomial of degree at most 1, thus $\varepsilon=0$. On the
other hand, by the second condition of (8), $\phi$ must be equal to a multiple
of the parity function. It is easy to see that $\sum_{x\in
X}\phi^{+}(x)-\sum_{x\notin Y}\phi^{-}(x)$ is actually negative in this case.


# Identify 46 New Open Clusters Candidates In Gaia EDR3 Using pyUPMASK and
Random Forest Hybrid Method

Huanbin Chi (gbsn迟焕斌) School of Management and Economics, Faculty of
Information Engineering And Automation,
Kunming University of Science and Technology, Kunming 650500, China  Shoulin
Wei (gbsn卫守林) School of Management and Economics, Faculty of Information
Engineering And Automation,
Kunming University of Science and Technology, Kunming 650500, China  Feng Wang
(gbsn王锋) Center for Astrophysics and Great Bay Center of National Astronomical
Data Center,
Guangzhou University, Guangzhou 510006 , China  Peng Cheng Laboratory,
Shenzhen, 518000, China  Zhongmu Li (gbsn李忠木) Institute of Astronomy, Dali
University, Dali, 671003, China

###### Abstract

Open clusters (OCs) are regarded as tracers to understand stellar evolution
theory and validate stellar models. In this study, we presented a robust
approach to identifying OCs. A hybrid method of pyUPMASK and RF is first used
to remove field stars and determine more reliable members. An identification
model based on the RF algorithm built based on 3714 OC samples from Gaia DR2
and EDR3 is then applied to identify OC candidates. The OC candidates are
obtained after isochrone fitting, the advanced stellar population synthesis
(ASPS) model fitting, and visual inspection. Using the proposed approach, we
revisited 868 candidates and preliminarily clustered them by the friends-of-
friends algorithm in Gaia EDR3. Excluding the open clusters that have already
been reported, we focused on the remaining 300 unknown candidates. From high
to low fitting quality, these unrevealed candidates were further classified
into Class A (59), Class B (21), and Class C (220), respectively. As a result,
46 new reliable open cluster candidates among classes A and B are identified
after visual inspection.

open cluster — GaiaEDR3 — FoF — pyUPMASK — Random Forest

††journal: ApJS

##  1 Introduction

Open clusters (OCs) were simultaneously formed from the same molecular cloud,
and gravitationally bound stellar systems were born in the same starburst.
Therefore, OCs are a kind of natural laboratory and valuable tracers for
studying galaxies’ structure, chemical composition, and dynamical evolution,
as well as providing validation and constraints on the model of evolutionary
astrophysical (Spina et al., 2022). For example, young OCs are often assigned
to analyze the structure of galaxies. They are also used as testbeds to study
stellar evolution, allowing us to investigate the boundary conditions
necessary for new star formation (Cantat-Gaudin et al., 2018a). Besides
providing information about the height and radial extension of the galactic
disk, old OCs also provide information about the chemical history of the
galaxy, e.g., the relationship between age and metallicity, mixing processes,
and cluster destruction processes caused by interactions with other clusters.

However, due to the limitations of Galactic dust extinction and contamination
of field stars (foreground and background stars), identifying OCs is still a
challenging issue (Deb et al., 2022). Many efforts have been made to hunt OC
candidates from the Gaia Second Data Release (Gaia DR2, Gaia Collaboration et
al. (2018)) and Gaia (Early) Data Release 3 (Gaia (E)DR3, Gaia Collaboration
et al. (2021)).

Various methods based on an unsupervised machine learning clustering algorithm
have been used to search for OCs. One of the most successful searching methods
is the Density-Based Spatial clustering of Applications with Noise algorithm
(DBSCAN) (Ester, 1996). A series of DBSCAN variants based on DBSCAN is capable
of effectively identifying OCs (Castro-Ginard et al., 2018, 2019, 2020; He et
al., 2021; Castro-Ginard et al., 2022). In addition, Kounkel & Covey (2019);
Kounkel et al. (2020); Hunt & Reffert (2021) used the improved method
Hierarchical Density-Based Spatial Clustering of Applications with Noise
(HDBSCAN) based on DBSCAN to detect many new clusters. Cantat-Gaudin et al.
(2018b) applied an unsupervised membership assignment code (UPMASK) to the
Gaia DR2 data contained within the fields of those clusters. Gao (2018);
Xinhua & Gao (2020) identified cluster members using a Gaussian mixture model
(GMM) clustering method.

Besides DBSCAN and its variants, the friends-of-friends (FoF) algorithm (Yang
et al., 2008) is also applied to identify OCs. Liu & Pang (2019) found 76
candidate star clusters from Gaia DR2 using the FoF algorithm. Li et al.
(2022) also used the FoF algorithm to perform a blind search for OCs in Gaia
EDR3 within 25 degrees of the Galactic plane. As a result, 61 new OCs were
reported among the 868 candidates. The advantage of the FoF algorithm to group
stars is that clustering considers a five-dimensional weighted parameter space
of parallax, position, and velocity. However, its disadvantage is that it is
not sensitive to the size of the cluster radius and the uneven distribution of
star density which changes at different distances $b_{FoF}$ is a unique
hyperparameter of the FoF algorithm, significantly impacting the clustering
results.

Liu & Pang (2019) proposed a high-performance approach (i.e., SHiP) to
calculate $b_{FoF}$ in each data region, which has been successful in finding
many open clusters (Li et al., 2022). $b_{FoF}$ is defined as

$b_{FoF}=0.2\times\left(\frac{1}{N_{star}}\right)^{0.2}$

where ${N_{star}}$ is the number of stars in each region. However, the
approach has some minor deficiencies. For example, it is relatively
ineffective in searching for member stars in some sparse spaces of star
clusters. On the other hand, the minimum number of clusters is set to a
predetermined fixed value, e.g. 50. This may lead to some member stars being
incorrectly included in a cluster during the merging process of the method.

In this study, we referred to the study of Li et al. (2022) to obtain a data
set of open cluster candidates using the FoF algorithm. We then presented an
improved hybrid algorithm to identify OCs from open cluster candidates found
by FoF more robustly. The rest of the paper is organized as follows. We
described the method in Section 2, including the membership determination
method and identification model for OCs. The results are presented in Section
3, which includes sample handling, isochrone-fitting, cross-matching, and
visual inspection. We discussed the results in Section 4. Finally, a
conclusion is covered in Section 5.

##  2 An Improved Identification Method For Open Cluster

In light of the previous literature mentioned in the first section, we
realized that improving OC recognition accuracy with machine learning methods
faces two problems. One is improving the quality of samples, and the other is
optimizing the final OC identification model. Therefore, we presented a robust
identification approach for OCs and showed the flow chart in Figure 1.

Figure 1: Flowchart of the hybrid identification approach. The process of this
approach consists of 3 stages. Stage 1 deals with rough FoF clustering within
Gaia EDR3. Then, each OC’s membership is identified in stage 2. After refining
the star member, we implement recognition of OCs, including a submodule of
modeling for identifying OCs, isochrone fitting, and visual inspection in
stage 3.

###  2.1 Member Star Determination Method

Determining which of the stars in a cluster candidate are member stars and
which are field stars is a challenging task. We presented a hybrid algorithm
based on pyUPMASK (Pera et al., 2021) and random forest (RF) to eliminate
false member stars (field stars) among those star clusters. We created a
dataset for each cluster candidate, respectively. Each star in the dataset was
labeled as a member star or field star using PyUPMASK. RF algorithm modeled
star data to predict more credible member stars.

1.pyUPMASK is a Python package for Unsupervised Photometric Membership
Assignment in Stellar Clusters (UPMASK) Krone-Martins & Moitinho (2014) used
to estimate the membership probability of each input star. pyUPMASK has been
widely used in the determination of member stars of OC based on astrometric
parameters (Cantat-Gaudin et al., 2019; He et al., 2022b; Bai et al., 2022;
Dias et al., 2022).

The essence of the UPMASK algorithm is to calculate the kernel density
estimation likelihood (KDE) of the member stars of the OC candidates. The
membership probability of stars is iteratively calculated by

$P_{star}=\dfrac{KDE_{m}}{\left(KDE_{m}+KDE_{nm}\right)}$,

where $P_{star}$, $KDE_{m}$, and $KDE_{nm}$ are the membership probability of
star, KDE of the members, and field star, respectively. In general, besides
coordinates, pyUPMASK requires at least two dimensions of data of any type to
estimate membership probabilities. We chose coordinates and proper motion as
the input of pyUPMASK for some distant open cluster candidates (excluding
parallax and photometric data), which has been confirmed effective in Perren
et al. (2022). To speed up the computing process, we performed parallel
computing using Mpi4py (Dalcin et al., 2008). It allows us to process a volume
of data that does not fit in the memory of a single machine as well.

After the pyUPMASK calculation, we refer to the Gao (2018) and set the value
of membership probability as 0.8. The stars with a membership probability
greater than 0.8 are labeled member stars, and others are labeled field stars,
which is different from the practices of He et al. (2021).

2\. Based on the label and eight parameters extracted from the catalog, i.e.,
$l,b,\varpi,\mu_{a^{*}},\mu_{\delta},G,G_{RP}$, and $G_{BP}$, we built an RF
model for each OC. We regarded the identification of cluster members as a
supervised binary classification problem. The RF model predicted the final
member stars for each OC.

###  2.2 Identification model for Open Cluster

We applied an RF classifier to detect the OCs among the potential candidates.
An RF classifier model was built with 1229 positive OC samples collected from
Gaia DR2 (Cantat-Gaudin & Anders, 2020) and 628 positive OC samples collected
from Gaia EDR3 (Castro-Ginard et al., 2018, 2019, 2020, 2021, 2022). The
negative OC samples, which have the same number of positive OC samples, are
synthesized with stars, assuming their spatial distribution is a random
uniform distribution. We finally obtained a trainset of 3714 OC samples for
modeling.

We calculated a confusion matrix (see Figure 2) as evaluation metrics to
evaluate the model. The precision of the model is 99.35%.

Figure 2: The confusion matrix.

##  3 Identification of Open Cluster And Results

###  3.1 Data Preparation For Open Cluster Candidates

We strictly followed the data preparation method of Li et al. (2022) to
generate the OC candidate dataset. First, we filter suitable samples to
exclude observational artifacts due to faintness in Gaia EDR3 based on the
stellar position, self, and parallax parameters ($\varpi$ between 0.2 mas and
0.7 mas, $G$ $<$ 18 mags and $\mu_{\alpha}cos\delta$ $<$ 30 mas yr-1,
$\mu_{\delta}$ $<$ 30 mas yr-1). Meanwhile, considering most OCs are centered
near the galactic disc, we set $\left|b\right|<$ 25 degrees.

Second, based on 180 million sources extracted, to facilitate this procedure,
we divide the entire search volume into multiple data regions, we roughly
divided the data into many data regions according to galactic longitude ($l$),
galactic latitude ($b$), and parallax ($\varpi$). The number of divisions for
$\varpi$, $b$, and $l$ are 8, 8, and 64, respectively. To avoid splitting the
clusters into different regions as much as possible, each of the data regions
must not be smaller than two times the typical cluster size (20 pc) (Portegies
Zwart et al., 2010). To deal with potential clusters located at the boundaries
of the region, we set an overlapping region for the two adjacent regions with
size ($\varpi$ size 0.2 mas, $l$, and $b$ size 10 pc). After carrying out the
above scheme, the whole search volume is divided into 4091 data regions.

We used FoF clustering for each data region to find local clusters and
aggregate them to obtain 3597 candidate clusters. After cross-matching, we got
807 new candidates for the cluster. Using the membership determination RF
model, we removed the field stars from each of these 807 candidates. We then
classified these 807 candidates using an identification RF model. 801
candidates were classified as open clusters, and the model rejected the other
6 candidates.

###  3.2 Validation Of Open Cluster Candidates

After obtaining 801 open cluster candidates, we cross-matched our candidates
with open cluster catalogs published. We consider an OC to be positionally
matched to a cataloged one if their centers lie within a circle of radius r =
0.5 degrees and the rest of the astrometric mean parameters are compatible
within 5$\sigma$, which is consistent with Hunt & Reffert (2021); Castro-
Ginard et al. (2021). Here, $\sigma$ is the uncertainties quoted in both
catalogs for each quantity.

We gathered most of the known star cluster catalogues and labelled them as
MWSC, CG2017, Hao3794, UBC series, CWNU, Dias1743, and Hao704, respectively.
The pre-Gaia cluster catalogs (MWSC) contain 3006 star clusters gathered by
Dias et al. (2012); Kharchenko et al. (2013). CG20 and CG series include 2017
OCs (Cantat-Gaudin & Anders, 2020). Hao et al. (2021) reports a much more
extensive catalog containing 3794 OCs (Hao3794). Moreover, the UBC series,
hunted by Castro-Ginard et al. (2018, 2019, 2020, 2021), totally reported 1274
OCs so far. The CWNU (He et al., 2022c) has reported 541 newly discovered open
cluster candidates found on Galactic Disk Using Gaia DR2/EDR3 Data. Dias et
al. (2021) had reported a catalog that updated the parameters of 1743 open
clusters based on Gaia DR2 in 2021 (Dias1743). Hao et al. (2022) reported 704
newly detected open clusters in the Galactic disk using Gaia EDR3 (Hao704).

Similarly, we have the same cross-match method to some previous catalogs,
i.e., Liu & Pang (2019), Ferreira et al. (2020), Hao et al. (2020), Hunt &
Reffert (2021), Li et al. (2021). In particular, using the same method, we
performed an integral crossover of 46 recently reported star clusters by He et
al. (2022b). The 46 newly discovered clusters are located in high-Galactic
latitude regions with $\left|b\right|>$20 degrees. In contrast, ours are
located at $\left|b\right|<$25 degrees. Therefore, there cannot be any match
between our cluster and any of the 46 newly discovered clusters. MWSC catalogs
contain 2976 cataloged objects local to galactic latitude 25 degrees gathered
from different data sources. Because they do not allow for sufficiently
accurate comparisons in proper motion space, we only performed a 0.5 degree
positional cross-match based on sky coordinates.

After cross-matching, 501 of the 801 candidates were already identified. We
obtained 300 candidate clusters that have not been identified and reported,
which is the data set for subsequent OC identification.

###  3.3 Color-Magnitude Diagrams fitting

The color-magnitude diagrams (CMDs) were fitted by two independent approaches,
i.e., the fitting based on isochrone models (Bressan et al., 2012) and the
fitting based on the advanced stellar population synthesis (ASPS) model (Li et
al., 2016, 2017). We first fitted CMDs by isochrone fitting method and then
validated the results with ASPS.

The isochrone fitting method is a mature and classic fitting method. In
theory, member stars in the OCs are born from the same gas cloud in a single
episode of star formation. Most of them are expected to follow a single
isochrone in color-magnitude diagrams (CMDs) and have the same metallicity and
age. Therefore, we used the isochrone-fitting method with the PARSEC
theoretical isochrone models (Bressan et al., 2012) updated by the Gaia EDR3
passbands using the photometric calibrations from ESA/Gaia to derive their
physical parameters (age and metallicity). We applied a log-normal initial
mass function Chabrier (2003) to generate an isochrone library from
$log(\dfrac{t}{yr})=$ 6.0 to 11.13 at steps of $\Delta(logt)=0.03$ while metal
fractions from 0.002 to 0.042 with a step of 0.002. Table 1 presents
parameters ranges and steps for isochrone fitting. An objective fitting
function

$\bar{d}^{2}=\dfrac{\sum_{k=1}^{n}\left(\mathbf{x}_{k}-\mathbf{x}_{k,nn}\right)^{2}}{n}$

was applied to 300 OC candidates, where $n$ is the number of selected members
in a cluster candidate, and ${x}_{k}$ and ${x}_{k,nn}$ are the positions of
the member stars and the points on the isochrone that are closest to the
member stars, respectively.

ASPS is a model that contains different kinds of stellar populations,
including single-star simple stellar populations (ssSSP); binary star stellar
populations (bsSSP); single-star composite stellar populations (ssCSP);
binary-star composite stellar populations (bsCSP); the simple stellar
population of single, binary, and rotating stars (sbrSSP); and composite
stellar population of single, binary, and rotating stars (sbrCSP). ASPS can be
used to fit the CMDs and determine the cluster properties. Due to the large
number of parameters considered, the fit of ASPS for CMDs takes a longer time.

Figure 3: Preliminary data check for our 801 OCs. ID 3093, 3066, 3096, and
3595 are listed, respectively. Leftmost plots: position of the OC in
($\alpha$, $\delta$). Inner left plots: ($\varpi$ , $\mu_{a^{*}}$ )
distribution, whilst inner right plots: ($\mu_{a^{*}}$, $\mu_{\delta}$ )
distribution. Rightmost plots: CMD of OC.

###  3.4 Maunal Verification And Final Results

After isochrone fitting, we classified OC candidates based on their CMD
morphology and isochrone fitting results to facilitate our manual visual
inspection. Referring to some previous literature (Liu & Pang, 2019; Castro-
Ginard et al., 2020; He et al., 2022b, c), we applied the following parameters
to the classification.

1\. $n\\_{star}$: Number of member stars that brighter than $G<17$ mag.

2\. ${d}^{2}$: The average square of the distance between cluster stars and an
isochrone used to measure the isochrone-fitting error.

3\. $r_{\mathrm{n}}$: The narrowness of the MS in the CMD calculated as
$\left|\dfrac{v_{1}}{v_{2}}\right|$. $v_{1}$ and $v_{2}$ are the two
eigenvalues of the covariance matrix of the distribution of stars in the CMD.

We classified 300 open cluster candidates into three classes:

1\. Class $A:n_{star}\geqslant 20,r_{\mathrm{n}}<0.1,\bar{d}^{2}<0.05$;

2\. Class $B:n_{star}\geqslant 20,r_{\mathrm{n}}<0.1$

3\. Class $C:$ other cases.

As a result, class A (20%, 59/300) has a sufficient number of member stars and
clear CMDs. The examples of class A are shown in the first row of Figure See
Figure A.1 in Appendix)). Class B (7%, 21/300) includes candidates with
unclear isochrone fitting and loose CMD distribution (see examples second row
in Figure A.1 of Appendix ). Some candidates of class C are shown in the third
row of Figure A.1 of Appendix. Given parameters of age and metallicity, class
C obtained by isochrone fitting has a large uncertainty.

We performed a manual visual inspection of each of these candidates using the
distribution of position distribution (PD), vector point diagram (VPD), CMD,
and parallax with $\mu_{a^{*}}$ as in Figure 3. Among the 80 candidates (Class
A and Class B) mentioned above, 46 candidates were finally considered as
possible real OCs (see Table 1). Parts of these 46 candidates are shown in
Figure ( See Figure A.2 in Appendix).

To further validate the results, we fitted the CMDs of these 46 OC candidates
using the ASPS model. Comparing the results of ASPS-based fitting and
isochrone fitting, 42 OCs are consistent (see Figure 3-6 in Appendix A).

4 cluster candidates with the ID of 3512, 3526, 3567, and 3595 are not well
suited to ASPS models. However, these four cluster candidates give very
reasonable results in isochrone fitting and also have a high probability of
being clusters. Figure A.7 in Appendix shows the results of isochrone fitting.

Figure 4: Distribution of matched and new OCs in the Galactic $X-Y$ plane with
an indication of spiral arms. Images viewed from the north pole of the galaxy,
from which it rotates clockwise. We adopted the Reid et al. (2019) recommended
values of $R\odot=8.15$ kpc and $Z\odot=5.5$ pc. The red point represents the
position of the Sun. Figure 5: Same as Figure 4, but with an edge-on view.

Figure 4 and 5 indicate most new candidates distributed between the Norma and
Near arms. Figure 6 shows the distributions of age and metallicity of the
newly identified OCs. We found that these OCs are younger than 3.0 Gyr (see
Figure 6 (b)). Additionally, most of them are metal-poor ( see Figure 6 (a)).

(a) Metallicity (Z) distribution of 46 newly identified cluster. Age unit:
$log(Z/Z\odot)$

(b) Age distribution of 46 newly identified clusters. Unit: $log(age/yr)$

Figure 6: Hisogram of Z and age for 46 OCs. Table 1:  Parameters of the final
46 New OCs in this work. Some of the best-fit and observed CMDs are compared
in Figure A.3 of Appendix

| ID | ra | std_ra | dec | std_dec | … | pmdec | std_pmdec | N_mem | $N_{17}$ | Z | age | class
---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  | [deg] | [deg] | [deg] | [deg] | … | [mas $yr^{-1}$ ] | [mas $yr^{-1}$] |  |  |  | [Gyr] |
0 | 0976 | 102.651 | 0.105 | 29.270 | 0.072 | … | -1.971 | 0.349 | 27 | 21 | 0.0300 | 0.7000 | A
1 | 1144 | 115.668 | 0.066 | -26.113 | 0.085 | … | 3.367 | 0.561 | 31 | 22 | 0.0300 | 0.7000 | B
2 | 1161 | 123.797 | 0.087 | -37.456 | 0.105 | … | 3.199 | 0.417 | 71 | 28 | 0.0001 | 0.6000 | A
3 | 1275 | 177.764 | 0.082 | -63.818 | 0.021 | … | 0.860 | 0.335 | 40 | 21 | 0.0200 | 0.4000 | B
4 | 1382 | 12.025 | 0.223 | 61.186 | 0.023 | … | -0.576 | 0.371 | 65 | 34 | 0.0001 | 1.2000 | B
5 | 1384 | 11.851 | 0.149 | 61.115 | 0.028 |  | -0.469 | 0.507 | 45 | 27 | 0.0100 | 0.9000 | A
6 | 1428 | 110.273 | 0.049 | -14.385 | 0.094 | … | 1.429 | 0.574 | 81 | 49 | 0.0300 | 0.5000 | A
7 | 1438 | 116.845 | 0.051 | -24.774 | 0.098 | … | 1.908 | 0.603 | 72 | 37 | 0.0040 | 0.9000 | A
8 | 1460 | 118.543 | 0.051 | -28.847 | 0.102 | … | 2.833 | 0.430 | 54 | 26 | 0.0300 | 0.6000 | A
9 | 1481 | 122.233 | 0.080 | -33.798 | 0.097 | … | 3.071 | 0.520 | 80 | 43 | 0.0100 | 0.8000 | A
10 | 1500 | 122.701 | 0.081 | -35.461 | 0.061 | … | 2.890 | 0.472 | 45 | 26 | 0.0200 | 0.8000 | A
11 | 1746 | 225.492 | 0.032 | -60.023 | 0.015 | … | -2.792 | 0.181 | 32 | 21 | 0.0360 | 0.040 | A
12 | 1991 | 90.700 | 0.067 | 27.281 | 0.086 | … | -1.286 | 0.537 | 49 | 25 | 0.0040 | 2.3000 | A
13 | 2009 | 98.861 | 0.061 | 12.457 | 0.140 | … | -0.503 | 0.437 | 52 | 28 | 0.0080 | 0.7000 | B
14 | 2060 | 118.380 | 0.041 | -24.904 | 0.082 | … | 2.612 | 0.312 | 56 | 31 | 0.0040 | 0.5000 | A
15 | 2073 | 116.970 | 0.096 | -24.682 | 0.061 | … | 2.117 | 0.500 | 42 | 25 | 0.0200 | 0.6000 | B
16 | 2075 | 116.885 | 0.048 | -24.181 | 0.104 | … | 2.268 | 0.507 | 66 | 43 | 0.0300 | 0.8000 | A
17 | 2083 | 115.650 | 0.022 | -21.430 | 0.044 | … | 2.733 | 0.406 | 35 | 27 | 0.0300 | 0.4000 | A
18 | 2084 | 115.716 | 0.078 | -21.029 | 0.057 | … | 2.656 | 0.700 | 55 | 40 | 0.0040 | 0.1000 | B
19 | 2091 | 120.071 | 0.042 | -24.196 | 0.103 | … | 1.799 | 0.638 | 72 | 41 | 0.0080 | 1.4000 | A
20 | 2100 | 119.923 | 0.107 | -24.668 | 0.066 | … | 2.694 | 0.575 | 45 | 24 | 0.0100 | 0.4000 | A
21 | 2110 | 121.050 | 0.052 | -26.050 | 0.067 | … | 2.961 | 0.572 | 39 | 24 | 0.0080 | 0.6000 | A
22 | 2130 | 119.134 | 0.069 | -26.984 | 0.057 | … | 3.061 | 0.391 | 50 | 24 | 0.0040 | 1.2000 | B
23 | 2239 | 147.722 | 0.073 | -52.375 | 0.060 | … | 3.398 | 0.391 | 54 | 25 | 0.0010 | 1.8000 | B
24 | 2324 | 171.305 | 0.080 | -59.957 | 0.086 | … | 1.912 | 0.429 | 67 | 40 | 0.0080 | 1.2000 | B
25 | 2457 | 271.006 | 0.029 | -21.275 | 0.047 | … | -1.940 | 0.366 | 47 | 35 | 0.0300 | 0.1000 | B
26 | 2761 | 344.905 | 0.131 | 60.889 | 0.078 | … | -1.710 | 0.255 | 59 | 30 | 0.0300 | 0.3000 | B
27 | 2942 | 80.027 | 0.083 | 40.160 | 0.091 | … | -1.703 | 0.633 | 49 | 24 | 0.0003 | 0.9000 | A
28 | 2944 | 77.990 | 0.116 | 40.402 | 0.130 | … | -1.509 | 0.513 | 75 | 43 | 0.0010 | 1.0000 | B
29 | 2971 | 100.312 | 0.032 | 14.030 | 0.109 | … | -1.002 | 0.358 | 48 | 29 | 0.0080 | 1.9000 | A
30 | 2972 | 107.696 | 0.054 | -3.101 | 0.106 | … | 0.243 | 0.466 | 61 | 32 | 0.0300 | 0.4000 | A
31 | 2986 | 118.648 | 0.108 | -20.539 | 0.073 | … | 1.891 | 0.530 | 55 | 31 | 0.0040 | 1.1000 | A
32 | 2987 | 120.702 | 0.060 | -25.329 | 0.090 | … | 2.731 | 0.538 | 81 | 50 | 0.0300 | 0.3000 | B
33 | 2999 | 126.065 | 0.076 | -31.786 | 0.089 | … | 2.781 | 0.539 | 53 | 22 | 0.0300 | 0.4000 | A
34 | 3012 | 294.733 | 0.072 | 29.585 | 0.051 | … | -5.352 | 0.794 | 77 | 33 | 0.0300 | 1.1000 | A
35 | 3019 | 299.549 | 0.071 | 36.770 | 0.029 | … | -4.633 | 0.734 | 71 | 30 | 0.0300 | 0.8000 | A
36 | 3078 | 71.701 | 0.087 | 60.871 | 0.041 | … | -0.083 | 0.164 | 38 | 24 | 0.0080 | 1.4000 | A
37 | 3079 | 99.408 | 0.209 | 34.733 | 0.082 | … | -1.757 | 0.468 | 41 | 23 | 0.0100 | 2.8000 | A
38 | 3082 | 102.310 | 0.231 | 29.745 | 0.114 | … | -1.657 | 0.535 | 52 | 38 | 0.0100 | 2.9000 | A
39 | 3086 | 83.970 | 0.187 | 55.647 | 0.075 | … | -1.304 | 0.486 | 46 | 21 | 0.0040 | 0.9000 | A
40 | 3093 | 94.860 | 0.101 | 41.919 | 0.141 | … | -1.893 | 0.397 | 53 | 36 | 0.0080 | 1.9000 | A
41 | 3095 | 94.462 | 0.284 | 44.190 | 0.082 | … | -1.812 | 0.444 | 48 | 29 | 0.0040 | 3.1000 | A
42 | 3512 | 80.643 | 0.378 | -1.214 | 0.746 | … | -0.443 | 0.369 | 135 | 99 | 0.014 | 0.1700 | A
43 | 3526 | 118.280 | 1.352 | -47.348 | 1.316 | … | 8.762 | 0.455 | 520 | 358 | 0.016 | 0.1480 | A
44 | 3567 | 277.912 | 0.136 | -3.912 | 0.206 | … | -9.011 | 0.268 | 50 | 38 | 0.022 | 0.0980 | A
45 | 3595 | 282.582 | 0.337 | 33.407 | 0.381 | … | -3.878 | 0.204 | 51 | 22 | 0.026 | 0.2750 | A

  * •

Note: For each cluster, age and metallicity (Z) are determined. The $N_{mem}$
means the total number of member star in each cluster. The $N_{17}$ means the
total number of member star with G $<$ 17 mag each cluster. The member stars
of each OC can be downloaded online.

##  4 Discussions And Future Works

###  4.1 Approach Limitations

We only use pyUPMASK on the 2-dimensional proper motion parameters space on
the higher dimensional feature space instead of using the member star
probability census for most clusters. This is because as the distance of the
star increases, the uncertainty of its parameters, such as parallax, will
increase significantly, introducing more uncertainty.

During the member stars census, not all the member stars of the cluster are
identified by the RF model. Because in some cases, the membership probability
after the census is greater than the threshold we set after running pyUPMASK.
For such star clusters, we do not use the RF model. Instead, we use pyUPMASK
for membership probability filtering in a 5-dimensional
($l,b,\varpi,\mu_{a^{*}},\mu_{\delta}$) space. In another case, for those star
clusters whose number of member stars is less than 10 after the calculation of
the member probability satisfies the filtered condition of the probability
threshold, we consider these star clusters as false and discard them.

A point that needs to be explained is that when training the RF model for the
recognition of member stars, we adopt the weighted RF algorithm. This is
because the training set of label samples is unbalanced, produced by pyUPMASK.

Table 2: Parameters Ranges and Steps for Isochrone Fitting Parameter | Range | Step | Unit
---|---|---|---
Age | 6.000 – 11.13 | 0.03 | log(t/yr)
Z | 0.002 – 0.042 | 0.002 | $[\mathrm{Fe}/\mathrm{H}]$

###  4.2 Performance Analysis Of Member stars Determination

To validate the proposed hybrid method, we first test it on a well-studied
open cluster, i.e., M67 (NGC 2682), which is a well-studied open cluster whose
members are publicly available in many studies Castro-Ginard et al. (2020);
Jadhav et al. (2021); Agarwal et al. (2021); Ghosh et al. (2022). We
downloaded sources from Gaia EDR3 in a cone around the open cluster center
within a radius of 50 pc (hereafter, all sources). And then, we applied our
method to detect the member of those OCs according to the step in Figure 1.
Jadhav et al. (2021) used combinations of astrometric, photometric, and
systematic parameters to train and supervise a machine learning algorithm
along with a Gaussian mixture model for the determination of cluster
membership of M67 using the Ultra Violet Imaging Telescope (UVIT) aboard
ASTROSAT and Gaia EDR3 (hereafter VV21). Since this is the latest
representative research result, we mainly focus on this result for comparative
analysis.

Compared with the other three studies, i.e., 766 member stars found by FoF,
484 member stars in CG20, and 746 member stars in VV21, we obtained 1131 M67
member stars from all sources. Figure 10 shows that our results agree with
VV21 and FoF for the most part.

We further tested the robustness of our method in smaller known clusters. We
chose two clusters that were smaller in size. One cluster is UBC1029 with 40
members (Castro-Ginard et al., 2022). Another is OC0033 with 47 members (Hao
et al., 2022). From left to right, Figure 7, 8 and 9 show the experimental
results of equatorial coordinates spatial distribution, proper motion
distribution, CMD, and parallax distribution hist, respectively. The mean and
variance of each astrometric value (position, parallax, and proper motion) and
the number of member stars are presented in Table 3. The results show that the
proposed method could accurately identify nearby massive and smaller distant
clusters. Compared with other OC studies using Gaia EDR3 data, the member
stars we identified are significantly more concentrated. This is because they
have a more focused spatial distribution, a clear isochrone feature, and more
member stars.

Some discrepancies in the results for the member stars are reasonable. This is
because the performance is poor for clusters smaller than 50 Myr, which tend
to be embedded in their star-forming regions. On the other hand, clusters at
distances larger than 1.5 kpc have larger astrometric errors, which makes the
member star analysis less reliable (Tarricq et al., 2022).

Figure 7: The CMDs of members identified for the cluster M67 compared with CG20. Table 3: Comparison Statistic Information of M67, UBC1029 and OC0033. ID | ra | std_ra | dec | dec_std | plx | std_plx | pmra | pmra_std | pmdec | std_pmdec | Nmember
---|---|---|---|---|---|---|---|---|---|---|---
M67 (CG20) | 132.846 | - | 11.814 | - | 1.135 | 0.051 | -10.986 | 0.193 | -2.964 | 0.201 | 598
M67 (This Work) | 132.853 | 0.215 | 11.819 | 0.218 | 1.151 | 0.0866 | -10.954 | 0.305 | -2.913 | 0.320 | 1131
UBC1029 (CG22) | 281.0 | 0.07 | -10.78 | 0.06 | 0.61 | 0.03 | -1.08 | 0.07 | -2.68 | 0.06 | 47
UBC1029 (This Work) | 281.003 | 0.048 | -10.803 | 0.0418 | 0.568 | 0.119 | -1.181 | 0.312 | 2.791 | 0.420 | 84
OC0033 (Hao22) | 276.773 | 0.03180 | -12.034 | 0.0245 | 0.372 | 0.0182 | -0.3193 | 0.0935 | -2.981 | 0.104 | 47
OC0033 (This Work) | 276.778 | 0.016 | -12.036 | 0.0166 | 0.380 | 0.0614 | -0.374 | 0.205 | -2.942 | 0.245 | 62
Figure 8: The CMDs of members identified for the cluster UBC1029 compared with
CG22. Figure 9: The CMDs of members identified for the cluster OC0033 compared
with Hao22 and FoF method.

Figure 10: The spatial distribution of M67 cluster members compared to VV21
and FoF methods. It should be noted that VV21 appears to have a more
comprehensive census. This is because VV21 uses the Ultraviolet Imaging
Telescope 210 (UVIT) on ASTROSAT and Gaia EDR3 to determine a combination of
astrometric, photometric, and systematic parameters of the M67 cluster members
(Jadhav et al., 2021). While our work only used the astrometric and
photometric data from Gaia EDR3. The Venn diagram of members is shown in the
rightmost subplot. VV21 and ours have 460 identical member stars (over 61%),
while FoF and VV21 only have 355 identical members ( 47.5 percent). Our
approach resulted in a 14.5 percent increase in joint membership, suggesting
that our method is valuable.

###  4.3 PDs, Parallax and proper motion dispersions

We compared the newly discovered cluster candidates with known ones based on
CG20 (Cantat-Gaudin & Anders, 2020). Figure 11 shows the distribution of OC
candidates proposed in the study, including 46 newly identified OCs, and over
500 matched OCs. The location of the proposed candidates matches that of the
previous OCs. The vast majority of the new OC candidates (except one) are
located at $\left|b\right|<15$ degree, and 95 % of them within
$\left|b\right|<10$ degree.

Figure 11: Comparison of distribution of the OC population in $l$, $b$
Galactic coordinates. The black circles present the OCs known prior to this
study, reported in Castro-Ginard et al. (2020). Blue triangles represent the
OCs found in this work matched with known. Red points represent the new OCs
found in this work using Gaia EDR3.

As shown in Figure 12, the distribution of our OC candidates indicated that
the parallaxes of them are mostly in the range of 0.16 and 0.42, which is
consistent with the results of previous work.

Figure 12: Hisogram of parallaxes for the OCs. Black ones represent the OCs
reported in Cantat-Gaudin et al. Cantat-Gaudin & Anders (2020). Blue ones
represent the 46 new OCs found in this work using Gaia EDR3.

In addition, we also compared the proper motion dispersions of our new OCs
with those of CG20. Figure 13 shows the distribution of OC candidates
identified in the study have similar smaller dispersions to the known OCs,
which is the characteristics of a real cluster (Cantat-Gaudin & Anders, 2020;
Dias et al., 2022).

Figure 13: Total observed proper motion dispersion using Gaia EDR3 vs.
parallax.The x-axis is a log scale for known OCs from the homogeneous OC
catalog of CG20 (black dots) compared with the new candidates in this study
(red dots).

###  4.4 Classification And Result Analysis

As a result of our high classification criteria, the number of OCs in Class A
and Class B is relatively low in the final classification results. Meanwhile,
the fitted models used are more considerate of multi-family situations such as
binary stars, stellar rotation, and multiple starbursts. The parameters of the
generative theory isochrone used in the fit are sparse, resulting in some
potential star clusters not being fitted.

However, analyzed in a different way, the FoF and our identification model
yielded 801 candidates. There are 501 cross-matched and 46 newly identified
sources, which means that 68.16 percent (547/801) of these sources are
successfully identified by our proposed method, which shows its value.

###  4.5 Discussion of CMD fitting

To validate our isochrone fitting method, we randomly selected 4 clusters from
Bossini et al. (2019), which have a similar size to our reported 46 OCs. We
fitted them with isochrones and methods presented by Bossini et al. (2019),
respectively. Fig 14 show the fitted results. Overall, the fitting results of
two methods are consistent. The error between two methods is within acceptable
limits. Two methods may use different isochrone libraries, resulting in
errors. While Bossini et al. (2019) used the isochrones library based on Gaia
DR2, our method uses the isochrones library updated by Gaia EDR3 passbands
using the photometric calibrations. The fitted parameters of two methods are
shown in Table 4.

Figure 14:  Blue points represent cluster members. The red dotted curve is the
best-fitting isochrone.  Table 4: Comparison Parameters Information of 2
fitting method.

OC_ID | IC2714 | NGC2547 | NGC1039 | IC4665 | Unit
---|---|---|---|---|---
Bossini2019 | age:8.550, z:0.02 | age:7.432, z:0.00 | age:8.101, z:0.00 | age:7.581, z:-0.03 | age(Gyr), z($[\mathrm{Fe}/\mathrm{H}]$)
This Work | age:8.760, z:0.01 | age:7.740, z:0.018 | age:7.890, z:0.02 | age:7.590, z:0.012 | age(Gyr), z($[\mathrm{Fe}/\mathrm{H}]$)
Error Range | age:1.26%, z:0.01 | age:3.97%, z:0.018 | age:2.67%, z:0.02 | age:0.11%, z:0.048 | z($[\mathrm{Fe}/\mathrm{H}]$)

  * •

Parameters information of Bossini2019 are derived from Bossini et al. (2019).

We further inspected the CMD fit results. We noticed that some parameters in
the fitting results were not reasonable (e.g., the age of ID1746 was only the
age of 4 dex). According to the method of He et al. (2022a), we also selected
the member stars with small errors and re-fitted them using the isochrone-
fitting method, and obtained reasonable results.

###  4.6 Future works

We identified 46 reliable clusters among 300 OC candidates. However, we cannot
regard the rest of the 254 candidates are not open clusters. It can only be
said that the method we proposed in the study cannot accurately identify these
254 candidates. We still suspect that there are Open Cluster samples among
these 254 candidates. We need to find other methods in the future.

In addition, multi-view learning should be further introduced in the future.
We supposed that the member star consists of three basic sub-views: 2D proper
motion, the three-dimensional position, and the magnitude (photometric) sub-
view. We completed the probability census in one sub-view, which can be
expanded to multiple views and then integrated with complementary information
to improve the accuracy of star member identification in the future.

##  5 Conclusions

In this study, we proposed a robust approach to identifying OCs. For the given
OC sample data, a pyUPMASK and RF hybrid method is first used to remove field
stars. Then an identification model based on the RF algorithm and Gaia EDR3
data is used to identify OC candidates. Finally, open cluster candidates are
obtained after isochrone fitting and manual visual inspection. Based on the
proposed approach, we obtained 46 new reliable open cluster candidates that
have not been reported before, which proved that the method proposed in the
study is reasonable.

This work is supported by the National SKA Program of China No 2020SKA0110300,
Joint Research Fund in Astronomy (U1831204) under cooperative agreement
between the National Natural Science Foundation of China (NSFC) and the
Chinese Academy of Sciences (CAS). Funds for International Cooperation and
Exchange of the National Natural Science Foundation of China (11961141001).
National Natural Science Foundation of China (No. 11863002), Yunnan
Academician Workstation of Wang Jingxiu (202005AF150025),China Manned Space
Project with NO.CMS-CSST-2021-A08 and Sino-German Cooperation Project (No. GZ
1284). This work is also supported by Astronomical Big Data Joint Research
Center, co-founded by National Astronomical Observatories, Chinese Academy of
Sciences and Alibaba Cloud, and Yunnan Ten Thousand Talents Plan Young and
Elite Talents Project.

## References

  * Agarwal et al. (2021) Agarwal, M., Rao, K. K., Vaidya, K., & Bhattacharya, S. 2021, MNRAS, 502, 2582, doi: 10.1093/mnras/stab118
  * Bai et al. (2022) Bai, L., Zhong, J., Chen, L., Li, J., & Hou, J. 2022, Research in Astronomy and Astrophysics, 22, 055022, doi: 10.1088/1674-4527/ac60d2
  * Bossini et al. (2019) Bossini, D., Vallenari, A., Bragaglia, A., et al. 2019, A&A, 623, A108, doi: 10.1051/0004-6361/201834693
  * Bressan et al. (2012) Bressan, A., Marigo, P., Girardi, L., et al. 2012, MNRAS, 427, 127, doi: 10.1111/j.1365-2966.2012.21948.x
  * Cantat-Gaudin & Anders (2020) Cantat-Gaudin, T., & Anders, F. 2020, A&A, 633, A99, doi: 10.1051/0004-6361/201936691
  * Cantat-Gaudin et al. (2018a) Cantat-Gaudin, T., Jordi, C., Vallenari, A., et al. 2018a, A&A, 618, A93, doi: 10.1051/0004-6361/201833476
  * Cantat-Gaudin et al. (2018b) —. 2018b, A&A, 618, A93, doi: 10.1051/0004-6361/201833476
  * Cantat-Gaudin et al. (2019) Cantat-Gaudin, T., Krone-Martins, A., Sedaghat, N., et al. 2019, A&A, 624, A126, doi: 10.1051/0004-6361/201834453
  * Castro-Ginard et al. (2019) Castro-Ginard, A., Jordi, C., Luri, X., Cantat-Gaudin, T., & Balaguer-Núñez, L. 2019, A&A, 627, A35, doi: 10.1051/0004-6361/201935531
  * Castro-Ginard et al. (2020) Castro-Ginard, A., Jordi, C., Luri, X., Cid-Fuentes, J. L., & Badia, R. 2020, Astronomy and Astrophysics, 635
  * Castro-Ginard et al. (2018) Castro-Ginard, A., Jordi, C., Luri, X., Julbe, F., & Cantat-Gaudin, T. 2018, Astronomy and Astrophysics, 618
  * Castro-Ginard et al. (2021) Castro-Ginard, A., Jordi, C., Luri, X., et al. 2021, arXiv e-prints
  * Castro-Ginard et al. (2022) Castro-Ginard, A., Jordi, C., Luri, X., et al. 2022, A&A, 661, A118, doi: 10.1051/0004-6361/202142568
  * Chabrier (2003) Chabrier, G. 2003, ApJ, 586, L133, doi: 10.1086/374879
  * Dalcin et al. (2008) Dalcin, L., Paz, R., Storti, M., & D’Elia, J. 2008, Journal of Parallel and Distributed Computing, 68, 655
  * Deb et al. (2022) Deb, S., Baruah, A., & Kumar, S. 2022, MNRAS, 515, 4685, doi: 10.1093/mnras/stac2116
  * Dias et al. (2022) Dias, W. S., Monteiro, H., Caetano, T., et al. 2022, MNRAS, 512, 4464, doi: 10.1093/mnras/stac718
  * Dias et al. (2012) Dias, W. S., Monteiro, H., Caetano, T. C., & Oliveira, A. F. 2012, A&A, 539, A125, doi: 10.1051/0004-6361/201118206
  * Dias et al. (2021) Dias, W. S., Monteiro, H., Moitinho, A., et al. 2021, MNRAS, 504, 356, doi: 10.1093/mnras/stab770
  * Ester (1996) Ester, M. 1996, Proc.int.conf.knowledg Discovery and Data Mining
  * Ferreira et al. (2020) Ferreira, F. A., Corradi, W. J. B., Maia, F. F. S., Angelo, M. S., & Santos, J. F. C., J. 2020, MNRAS, 496, 2021, doi: 10.1093/mnras/staa1684
  * Gaia Collaboration et al. (2018) Gaia Collaboration, Brown, A. G. A., Vallenari, A., et al. 2018, A&A, 616, A1, doi: 10.1051/0004-6361/201833051
  * Gaia Collaboration et al. (2021) Gaia Collaboration, Luri, X., Chemin, L., et al. 2021, A&A, 649, A7, doi: 10.1051/0004-6361/202039588
  * Gao (2018) Gao, X. 2018, AJ, 156, 121, doi: 10.3847/1538-3881/aad690
  * Ghosh et al. (2022) Ghosh, E. M., Sulistiyowati, Tucio, P., & Fajrin, M. 2022, in Journal of Physics Conference Series, Vol. 2214, Journal of Physics Conference Series, 012009, doi: 10.1088/1742-6596/2214/1/012009
  * Hao et al. (2020) Hao, C., Xu, Y., Wu, Z., He, Z., & Bian, S. 2020, PASP, 132, 034502, doi: 10.1088/1538-3873/ab694d
  * Hao et al. (2022) Hao, C. J., Xu, Y., Wu, Z. Y., et al. 2022, A&A, 660, A4, doi: 10.1051/0004-6361/202243091
  * Hao et al. (2021) Hao, C. J., Xu, Y., Hou, L. G., et al. 2021, A&A, 652, A102, doi: 10.1051/0004-6361/202140608
  * He et al. (2022a) He, Z., Wang, K., Luo, Y., et al. 2022a, ApJS, 262, 7, doi: 10.3847/1538-4365/ac7c17
  * He et al. (2022b) He, Z., Li, C., Zhong, J., et al. 2022b, ApJS, 260, 8, doi: 10.3847/1538-4365/ac5cbb
  * He et al. (2022c) —. 2022c, ApJS, 260, 8, doi: 10.3847/1538-4365/ac5cbb
  * He et al. (2021) He, Z.-H., Xu, Y., Hao, C.-J., Wu, Z.-Y., & Li, J.-J. 2021, Research in Astronomy and Astrophysics, 21, 093, doi: 10.1088/1674-4527/21/4/93
  * Hunt & Reffert (2021) Hunt, E. L., & Reffert, S. 2021, A&A, 646, A104, doi: 10.1051/0004-6361/202039341
  * Jadhav et al. (2021) Jadhav, V. V., Pennock, C. M., Subramaniam, A., Sagar, R., & Nayak, P. K. 2021, MNRAS, 503, 236, doi: 10.1093/mnras/stab213
  * Kharchenko et al. (2013) Kharchenko, N. V., Piskunov, A. E., Schilbach, E., Röser, S., & Scholz, R. D. 2013, A&A, 558, A53, doi: 10.1051/0004-6361/201322302
  * Kounkel & Covey (2019) Kounkel, M., & Covey, K. 2019, AJ, 158, 122, doi: 10.3847/1538-3881/ab339a
  * Kounkel et al. (2020) Kounkel, M., Covey, K., & Stassun, K. G. 2020, AJ, 160, 279, doi: 10.3847/1538-3881/abc0e6
  * Krone-Martins & Moitinho (2014) Krone-Martins, A., & Moitinho, A. 2014, A&A, 561, A57, doi: 10.1051/0004-6361/201321143
  * Li et al. (2021) Li, Z., Deng, Y., & Chen, J. 2021, ApJS, 253, 38, doi: 10.3847/1538-4365/abeb68
  * Li et al. (2016) Li, Z., Mao, C., Zhang, L., et al. 2016, Astrophysical Journal Supplement, 225, 7
  * Li et al. (2022) Li, Z., Deng, Y., Chi, H., et al. 2022, ApJS, 259, 19, doi: 10.3847/1538-4365/ac3c49
  * Li et al. (2017) Li, Z.-M., Mao, C.-Y., Luo, Q.-P., et al. 2017, Research in Astronomy and Astrophysics, 17, 071, doi: 10.1088/1674-4527/17/7/71
  * Liu & Pang (2019) Liu, L., & Pang, X. 2019, ApJS, 245, 32, doi: 10.3847/1538-4365/ab530a
  * Pera et al. (2021) Pera, M. S., Perren, G. I., Moitinho, A., Navone, H. D., & Vazquez, R. A. 2021, A&A, 650, A109, doi: 10.1051/0004-6361/202040252
  * Perren et al. (2022) Perren, G. I., Pera, M. S., Navone, H. D., & Vázquez, R. A. 2022, A&A, 663, A131, doi: 10.1051/0004-6361/202243288
  * Portegies Zwart et al. (2010) Portegies Zwart, S. F., McMillan, S. L., & Gieles, M. 2010, Annual review of astronomy and astrophysics, 48, 431
  * Reid et al. (2019) Reid, M. J., Menten, K. M., Brunthaler, A., et al. 2019, ApJ, 885, 131, doi: 10.3847/1538-4357/ab4a11
  * Spina et al. (2022) Spina, L., Magrini, L., & Cunha, K. 2022, Universe, 8, 87, doi: 10.3390/universe8020087
  * Tarricq et al. (2022) Tarricq, Y., Soubiran, C., Casamiquela, L., et al. 2022, A&A, 659, A59, doi: 10.1051/0004-6361/202142186
  * Xinhua & Gao (2020) Xinhua, & Gao. 2020, Astrophysics and Space Science, 365, 1
  * Yang et al. (2008) Yang, X., Mo, H. J., Bosch, F., et al. 2008, Astrophysical Journal, 671, 153