# Identifying critical higher-order interactions in complex networks

Mehmet Emin Aktas
Department of Mathematics and Statistics
University of Central Oklahoma
Edmond, OK 73034
<EMAIL_ADDRESS>
Thu Nguyen
Department of Computer Science
University of Central Oklahoma
Edmond, OK 73034
<EMAIL_ADDRESS>
Sidra Jawaid
Department of Mathematics and Statistics
University of Central Oklahoma
Edmond, OK 73034
<EMAIL_ADDRESS>
Rakin Riza
Department of Computer Science
University of Central Oklahoma
Edmond, OK 73034
<EMAIL_ADDRESS>
Esra Akbas
Department of Computer Science
Oklahoma State University
Stillwater, OK 74078
<EMAIL_ADDRESS>

###### Abstract

Information diffusion on networks is an important concept in network science
observed in many situations such as information spreading and rumor
controlling in social networks, disease contagion between individuals,
cascading failures in power grids. The critical interactions in networks are
the ones that play critical roles in information diffusion and primarily
affect network structure and functions. Besides, interactions can occur
between not only two nodes as pairwise interactions, i.e., edges, but also
three or more nodes, described as higher-order interactions. This report
presents a novel method to identify critical higher-order interactions. We
propose two new Laplacians that allow redefining classical graph centrality
measures for higher-order interactions. We then compare the redefined
centrality measures using the Susceptible-Infected-Recovered (SIR) simulation
model. Experimental results suggest that the proposed method is promising in
identifying critical higher-order interactions.

_Keywords_ Hypergraphs $\cdot$ influential higher-order interactions $\cdot$
information diffusion $\cdot$ simplical Laplacian

##  1 Introduction

Information diffusion on networks is an important concept in network science
observed in many situations such as information spreading and rumor
controlling in social networks, disease contagion between individuals,
cascading failures in power grids. During the diffusion, some network
structures play critical roles and primarily affect network structure and
functions. For example, in social networks, one can spread messages in the
network quickly through the critical nodes Kempe et al. (2003); in epidemic
networks, one may reduce the diffusion of epidemic with controlling
influential nodes Wang et al. (2020). Therefore, identifying critical
(influential) nodes and edges has practical importance in network science.
There are many studies in the literature for the critical node detection
problem in networks. Typical methods are based on network topology. Some
studies use nodes’ degree, such as degree centrality Bonacich (1972) and
H-index Lü et al. (2016), some use paths in networks, such as closeness
centrality Freeman (1978) and betweenness centrality Freeman (1977), and some
use eigendecomposition of graphs, such as PageRank Brin and Page (1998) and
DFF centrality Aktas et al. . In addition, some researchers use node deletion
or contraction to distinguish the importance of nodes Arulselvan et al.
(2009); Yang et al. (2019).

Besides, critical edges in networks also play a critical role in information
diffusionGiuraniuc et al. (2005); Girvan and Newman (2002); Wang et al.
(2017); Zio et al. (2012); Saito et al. (2016); Wong et al. (2017); Hamers et
al. (1989); Yu et al. (2018); Cheng et al. (2010). For example, critical edges
give important transmission lines in complex power networks. As another
example, the identification of critical edges can be helpful to analyze the
vulnerability in electrical transmission networks. Recently, many researchers
focus on finding critical edges based on network topology. For example, the
authors in Giuraniuc et al. (2005) use the degree of the two nodes that an
edge connects to measure the importance of the edge. In Girvan and Newman
(2002); Wang et al. (2017); Zio et al. (2012), the authors use the betweenness
centrality of edges to detect critical edges. In other words, they assume that
edges connecting two connected components are important. There are also other
studies that use flow/reachabilitySaito et al. (2016); Wong et al. (2017),
bridgeness Cheng et al. (2010), neighbors Hamers et al. (1989), and clique
degrees Yu et al. (2018) to measure the edge importance.

On the other hand, as we see in different real-world applications, such as in
human communication, chemical reactions, and ecological systems, interactions
can occur between not only two nodes as pairwise interactions, i.e., edges,
but also three or more nodes Battiston et al. (2020) described as higher-order
interactions. Hypergraphs can be used to model higher-order interactions in
complex systems where entities are represented as nodes, and higher-order
interactions among them are represented as hyperedges. For example, in
coauthorship networks, nodes represent authors, and hyperedges represent
coauthorship between authors. As another example, in drug-drug interaction
networks, nodes are substances that make up the drug, and hyperedges
correspond to drugs. Besides, critical hyperedges also play a critical role in
information diffusion. For example, to find the most influential article in a
coauthorship network, we need to find the most influential hyperedge. As
another example, in a social network, manufacturers intend to detect
influential hyperedges for promoting their products to maximize the number of
influenced customers.

There are a few studies that explore the critical hyperedges in hypergraphs.
In Veremyev et al. (2017, 2019); Vogiatzis et al. (2015), the authors use the
betweenness centrality and cliques to find the influential higher-order
interactions with a fixed size, however they are only able to compare
interactions of the same size. In Nasirian et al. (2020); Zhao et al. (2017),
the authors find influential higher-order interactions based on closeness
centrality and are unable to apply other centrality measures.

In this paper, to address these limitations, we propose two new hypergraph
Laplacians based on the diffusion framework that allows us to find the
influential higher-order interactions in a hypergraph of any size and with any
desired classical centrality measure; one is based on diffusion between fixed
size hyperedges, and the other is based on diffusion between all hyperedges.
The previously developed hypergraph Laplacians are only defined for special
hypergraphs, and more importantly, neglect the relations between hyperedges.
Thanks to the proposed Laplacians, we can model the complete relations between
hyperedges of any size. Next, we redefine four graph centrality measures,
namely DFF, degree, betweenness, and closeness, to hypergraphs and rank
higher-order interactions based on these measures. One can also similarly
redefine other classical centrality measures, but we believe working with four
centralities would be enough to show the effectiveness of the proposed method.
For evaluation, we experiment on several undirected real-world network
datasets and evaluate the performance using the Susceptible-Infected-Recovered
(SIR) simulation modelNewman (2002). The experimental results suggest that our
methods are quite promising in finding influential higher-order interactions.

##  2 Methods

In this section, we start with defining the graph Laplacian. We then present
the two hypergraph Laplacians that allow detecting the influential higher-
order interactions. Lastly, we present the redefined graph centrality
measures. We conclude this section with an illustrative example.

Let $G$ be a weighted undirected graph. We define the graph Laplacian $L$ as
$L=D-A$, where $D$ is the weighted degree matrix and $A$ is the weighted
adjacency matrix. The graph Laplacian only uses pairwise interactions, i.e.,
edges, between vertices and ignores higher-order interactions. Furthermore, it
only allows to model diffusion between vertices, not higher-order structures.

To address these concerns, we first represent a complex network with a
hypergraph. A hypergraph $H$ denoted by $H=(V,E=(e_{i})_{i\in I})$ on the
finite vertex set $V$ is a family $(e_{i})_{i\in I}$ ($I$ is a finite set of
indexes) of subsets of $V$ called hyperedges. In a hypergraph, nodes represent
entities and hyperedges represent higher-order interactions in the network.
The size of a hyperedge is the number of the nodes in the corresponding
higher-order interaction.

We use the diffusion framework on hypergraphs, i.e., the patterns of who is
connected to whom, for identifying critical higher-order interactions. Similar
to this study Horak and Jost (2013), one can define the simplicial Laplacian
to model diffusion over a hypergraph with a simplicial complex structure,
i.e., subsets of hyperedges are also hyperedges. Let $D_{p}$ be the incidence
matrix that encodes which $p$-simplices are incident to which
$(p+1)$-simplices. It is defined as

$D_{p}(i,j)=\left\\{\begin{tabular}[]{ll}$1$&if $\sigma_{j}^{p}$ is on the
boundary of $\sigma_{i}^{p+1}$\\\ $0$&otherwise\end{tabular}\right.$

Let $W_{p}$ be the diagonal weight matrix of the simplices. Then, the
$i$-dimensional up Laplacian can be expressed as the matrix

$\pazocal{L}_{i}^{up}=W_{i}^{-1}D_{i}^{T}W_{i+1}D_{i}.$

Similarly, the $i$-dimensional down Laplacian can be expressed as the matrix

$\pazocal{L}_{i}^{down}=D_{i-1}W_{i-1}^{-1}D_{i-1}^{T}W_{i}.$

Lastly, the $i$-dimensional Laplacian in both directions is

$~{}\pazocal{L}_{i}^{both}=\pazocal{L}_{i}^{up}+\pazocal{L}_{i}^{down}.$

However, these Laplacians have three critical issues. First, it is defined
only for hypergraphs with the simplicial complex structure, which is often not
the case in real-world hypergraphs. For example, in a coauthorship network,
there may be an article with three coauthors (i.e., a triangle) where each
pair of the authors may not have coauthored an article (i.e., edges). Second,
for a hyperedge of size $k$, the simplicial Laplacian models the diffusion
only through the hyperedges of sizes $k-1$ and/or $k+1$. However, in the
diffusion framework, information on a hyperedge can diffuse through other
hyperedges regardless of their sizes. For example, these Laplacians assume
that information from a paper of three coauthors can only diffuse through
papers of two and four coauthors, which is not realistic. Third, when we use
the simplicial Laplacians in modeling diffusion, we need to assume that
information only diffuses between fixed size hyperedges. However, a hyperedge
can affect other hyperedges regardless of their sizes. For example, based on
these Laplacians, information can only diffuse between papers of three
coauthors, which is not realistic again.

To address these issues, we develop two hypergraph Laplacians; one is based on
diffusion between fixed size hyperedges, $\pazocal{L}_{k}$, and the other is
based on diffusion between hyperedges of any size in the hypergraph $H$,
$\pazocal{L}_{H}$ Aktas and Akbas (2021). In the simplicial Laplacian, a
hyperedge of size $k+1$ is called a $k$-simplex. For example, vertices are
called 0-simplices, edges are called 1-simplices and triangles are called
2-simplices. To be consistent with the simplicial Laplacian definition, we
prefer to call a hyperedge of size $k+1$ as $k$-simplex while defining our
Laplacians. We first update the incidence matrix for simplices of any
dimension as follows.

$D_{p,r}(i,j)=\left\\{\begin{tabular}[]{ll}$1$&if $\sigma_{j}^{p}$ is on the
boundary of $\sigma_{i}^{r}$\\\ $0$&otherwise\end{tabular}\right.$

with $\sigma^{p}$ being a $p$-simplex. Here, $D_{p,r}$ encodes which
$p$-simplices are incident to which $r$-simplices. Next, for a hypergraph with
the maximum simplex dimension of $n$ (i.e., hyperedge size of $n+1$),
Laplacian between $k$-simplices through other simplices is defined as

$\pazocal{L}_{k}=\pazocal{L}_{k,0}+\pazocal{L}_{k,1}+\cdots+\pazocal{L}_{k,n-1}+\pazocal{L}_{k,n}$

for $k\in\\{0,\dots,n\\}$, where

$\pazocal{L}_{k,l}=\left\\{\begin{tabular}[]{ll}$W_{l}^{-1}D_{k,l}^{T}W_{k}D_{k,l}$&if
$k\leq l$\\\ $D_{l,k}W_{k}^{-1}D_{l,k}^{T}W_{l}$&if $k>l$\end{tabular}\right.$

with $W$ being the diagonal simplex weight matrix. Here, $\pazocal{L}_{k}$
encodes how $k$-simplices are related to each other where the relations can be
through the shared neighboring simplices of any dimension. Next, we improve
this Laplacian by considering relations between simplices of any dimension.
Using the Laplacian $\pazocal{L}_{k}$, we define the generalized hypergraph
Laplacian, $\pazocal{L}_{H}$, as the following block matrix

$\pazocal{L}_{H}=\left(\begin{array}[]{c|c|c|c|c}\pazocal{L}_{0}&\pazocal{D}_{0,1}^{T}&\pazocal{D}_{0,2}^{T}&\cdots&\pazocal{D}_{0,n}^{T}\\\
\hline\cr\pazocal{D}_{0,1}&\pazocal{L}_{1}&\pazocal{D}_{1,2}^{T}&\cdots&\pazocal{D}_{1,n}^{T}\\\
\hline\cr\pazocal{D}_{0,2}&\pazocal{D}_{1,2}&\pazocal{L}_{2}&\cdots&\pazocal{D}_{2,n}^{T}\\\
\hline\cr\vdots&\vdots&\vdots&\ddots&\vdots\\\
\hline\cr\pazocal{D}_{0,n}&\pazocal{D}_{1,n}&\pazocal{D}_{2,n}&\cdots&\pazocal{L}_{n}\end{array}\right)$

where $\pazocal{D}_{p,r}=\sum_{i=0}^{n}D_{p,r}^{i}$ and $D_{p,r}^{q}(i,j)=s$,
and $s$ is the number of the $q$-simplices that are adjacent to both
$\sigma_{j}^{p}$ and $\sigma_{i}^{r}$ for $q\notin\\{p,r\\}$ and
$D_{p,r}^{p}=D_{p,r}^{r}=D_{p,r}$. Here, the blocks on the main diagonal are
the Laplacians we develop initially, i.e., they provide the relation between
simplices of fixed dimension through simplices of any dimension. Besides, the
off-diagonal blocks do the same thing but for different dimensions. Therefore,
$\pazocal{L}_{H}$ is able to capture the relations between all simplices
through simplices of any dimension, which addresses all the limitations.

To compute the influence of the higher-order interactions (i.e., hyperedges),
we redefine four graph centrality measures, namely diffusion Frechet function
(DFF) Aktas et al. ; Martínez et al. (2018), degree, betweenness, and
closeness Freeman (1978), which are originally defined for vertices, to
hyperedges, thanks to the generalized Laplacian $\pazocal{L}_{H}$. We use this
Laplacian to model relations between hyperedges, and define the centrality
measures accordingly.

DFF centrality employs the diffusion Fréchet function (DFF) defined as the
weighted sum of the diffusion distance between a hyperedge and the rest of the
network. The diffusion distance measures the similarity between two given
hyperedges by finding the similarity of the heat diffusion on a given time
interval when the heat source is located on these hyperedges. More formally,
let $\mathcal{E}=[\mathcal{E}_{1},...,\mathcal{E}_{n}]^{T}\in\mathbb{R}^{n}$
be a probability distribution on hyperedge set $E$ of a hypergraph $H$. For
$t>0$, the diffusion Fréchet function on hyperedge $e_{i}\in E$ is defined as

$F_{\mathcal{E},t}(i)=\sum_{j=1}^{n}d_{t}^{2}(i,j)\mathcal{E}_{j}.$

with

$d_{t}^{2}(i,j)=\sum_{k=1}^{n}e^{-2\lambda_{k}t}(\phi_{k}(i)-\phi_{k}(j))^{2}$

where $0\leq\lambda_{1}\leq...\leq\lambda_{n}$ are the eigenvalues of the
hypergraph Laplacian $\pazocal{L}_{H}$ with orthonormal eigenvectors
$\phi_{1},...,\phi_{n}$. A hyperedge with a smaller diffusion Fréchet function
value is considered an influential hyperedge in the network since the heat
diffusion centered at this hyperedge is similar to many hyperedges. The degree
centrality is the number of connections of each hyperedge. The degree can be
computed considering the connection weights. The betweenness centrality
measures how often each hyperedge appears on the shortest path between two
hyperedges in the hypergraph. Since there can be several shortest paths
between two hyperedges $s$ and $t$, the centrality of hyperedge $u$ is

$\displaystyle H_{Btw}(u)=\sum_{s,t\neq u}\frac{n_{st}(u)}{N_{st}}$

where $n_{st}(u)$ is the number of shortest paths from $s$ to $t$ that pass
through hyperedge $u$, and $N_{st}$ is the total number of shortest paths from
$s$ to $t$. Shortest paths can be computed by considering the connection
weights. Lastly, the closeness centrality uses the inverse sum of the distance
from a hyperedge to all other hyperedges in the hypergraph. The centrality of
a hyperedge $u$ is

$\displaystyle H_{Cls}(u)=\frac{1}{C_{u}}$

where $C_{u}$ is the sum of the distances from hyperedge $u$ to all other
hyperedges. The distance from a hyperedge to another hyperedge can be computed
by considering the connection weights.

Lastly, we model SIR on vertices of the hypergraph by utilizing the Laplacian
$\pazocal{L}_{0}$ for evaluation. As we mentioned before, $\pazocal{L}_{0}$
reveals how vertices are connected through hyperedges of any size.

We now provide an illustrative example of the proposed methods.

Figure 1: A hypergraph with six vertices (0-simplices), eight edges
(1-simplices) and three triangles (2-simplex).

###### Example 1

The hypergraph in Figure 1 has six vertices (0-simplices), eight edges
(1-simplices), and three triangles (2-simplices). Its Laplacian between
0-simplices, $\pazocal{L}_{0}$, and generalized Laplacian, $\pazocal{L}_{H}$,
are found below. In both Laplacians, the diagonal entries show the number of
neighboring simplices for each $k$-simplex (we also count each hyperedge as
its neighboring hyperedge in order to stress the importance of the direct
neighborhood relation), and the off-diagonal entries show the number of the
shared neighboring simplices with other simplices. The diffusion between
simplices happens based on the number of the shared neighboring simplices with
other simplices in these Laplacians.

$\pazocal{L}_{0}=\blockarray{ccccccc}&v_{1}v_{2}v_{3}v_{4}v_{5}v_{6}\\\
\block{c(cccccc)}v_{1}512200\\\ v_{2}120000\\\ v_{3}208332\\\ v_{4}203620\\\
v_{5}003262\\\ v_{6}002024\\\ ,\hskip
14.22636pt\pazocal{L}_{H}=\left(\begin{array}[]{cccccc|cccccccc|ccc}5&1&2&2&0&0&2&3&1&3&0&0&0&0&4&0&0\\\
1&2&0&0&0&0&2&0&0&0&0&0&0&0&0&0&0\\\ 2&0&8&3&3&2&0&3&4&1&3&1&1&4&4&4&4\\\
2&0&3&5&2&0&0&1&4&3&0&0&3&1&4&4&0\\\ 0&0&3&2&5&2&0&0&1&0&1&3&3&4&0&4&4\\\
0&0&2&0&2&4&0&0&0&0&3&3&0&1&0&0&4\\\ \hline\cr
2&2&0&0&0&0&3&1&0&1&0&0&0&0&1&0&0\\\ 3&0&3&1&0&0&1&4&2&2&1&0&0&1&4&1&1\\\
1&0&4&4&1&0&0&2&5&2&1&0&2&2&4&4&1\\\ 3&0&1&3&0&0&1&2&2&4&0&0&1&0&4&1&0\\\
0&0&3&0&1&3&0&1&1&0&4&2&0&2&1&1&4\\\ 0&0&1&0&3&3&0&0&0&0&2&4&1&2&0&1&4\\\
0&0&1&3&3&0&0&0&2&1&0&1&4&2&1&4&1\\\ 0&0&4&1&4&1&0&1&2&0&2&2&2&5&1&4&4\\\
\hline\cr 4&0&4&4&0&0&1&4&4&4&1&0&1&1&7&3&1\\\
0&0&4&4&4&0&0&1&4&1&1&1&4&4&3&7&3\\\ 0&0&4&0&4&4&0&1&1&0&4&4&1&4&1&3&7\\\
\end{array}\right).$

Table 1: The cells for the best result in each row is colored gray. | $\mathbf{H}_{DFF}$ | $\mathbf{H}_{Deg}$ | $\mathbf{H}_{Btw}$ | $\mathbf{H}_{Cls}$ | $\mathbf{R}_{s}$
---|---|---|---|---|---
Rank | Score | Rank | Score | Rank | Score | Rank | Score | Rank | Score
$e_{1}$ | 11 | 1.412 | 11 | 7 | 6 | 0.026 | 11 | 0.533 | 4 | 0.078
$e_{2}$ | 6 | 1.218 | 6 | 20 | 2 | 0.054 | 3 | 0.762 | 5 | 0.057
$e_{3}$ | 4 | 1.123 | 4 | 28 | 3 | 0.034 | 2 | 0.800 | 11 | 0.029
$e_{4}$ | 9 | 1.245 | 9 | 18 | 5 | 0.026 | 7 | 0.696 | 6 | 0.052
$e_{5}$ | 8 | 1.231 | 8 | 19 | 9 | 0.017 | 8 | 0.696 | 7 | 0.045
$e_{6}$ | 10 | 1.259 | 10 | 17 | 11 | 0.004 | 10 | 0.615 | 8 | 0.044
$e_{7}$ | 7 | 1.231 | 7 | 19 | 10 | 0.015 | 9 | 0.696 | 9 | 0.040
$e_{8}$ | 5 | 1.123 | 5 | 28 | 4 | 0.028 | 4 | 0.762 | 10 | 0.031
$t_{1}$ | 3 | 1.092 | 3 | 31 | 8 | 0.021 | 6 | 0.727 | 2 | 0.125
$t_{2}$ | 1 | 1.061 | 1 | 34 | 7 | 0.024 | 5 | 0.762 | 3 | 0.111
$t_{3}$ | 2 | 1.081 | 2 | 32 | 1 | 0.065 | 1 | 0.800 | 1 | 0.139

To find the influential higher-order interactions, we apply the SIR model and
calculate centralities using $\pazocal{L}_{0}$ and $\pazocal{L}_{H}$,
respectively. As we see in Table 1, $t_{1},t_{2},t_{3}$ are the most
influential higher-order interactions based on $H_{DFF}$ and $H_{Deg}$ and
these results are aligned with the corresponding diffusion index $R_{s}$.
Similarly, $t_{3}$ is the most influential based on $H_{Btw}$ and $H_{Cls}$.
On the other hand, although $e_{3}$ can be considered as one of the most
central and, as a result, influential higher-order interaction, its diffusion
index is relatively low. The reason for this is that its neighboring
simplices, $v_{3},v_{4},t_{2},t_{3}$, are of high degree; hence, its removal
relatively affects the diffusion.

##  3 Results

In this section, we first describe the datasets we use in our experiments.
Then, we explain how we model SIR on hypergraphs using the proposed Laplacians
for evaluation. Next, we redefine four classical graph centrality measures,
namely DFF, degree, betweenness, and closeness, to hypergraphs and present
results on the datasets.

Data Description. In our experiments, we use four undirected real-world
networks to evaluate the effectiveness of redefined centrality measures using
hypergraph Laplacians (see Table 2 for the networks’ statistics). (1) Enron:
each vertex represents the email address of a staff member at Enron. A simplex
or hyperedge represents all the recipients, including the sender, of an email
sent between the Enron staff. (2) High school: this dataset is made from a
network of high school students in Marseilles, France. A vertex is a student,
and a simplex is a set of students in close contact with each other. (3)
Primary school: this dataset is made from a network of primary school students
and teachers. A vertex is a student or a teacher, and a simplex is a set of
students and/or teachers in close contact with each other. (4) NDC-classes: a
vertex is a pharmaceutical class label used to classify a certain property of
a drug. The network of drugs is taken from the National Drug Code Directory. A
simplex is a set of several or many class labels assigned to a drug. These
datasets can be found in Benson et al. (2018).

Table 2: Basic properties of the real-world datasets we use are provided here. $\langle k\rangle$ is the average weighted degree, and $k_{max}$ is the maximum hyperedge size. $Dataset$ | $Vertices$ | $Hyperedges$ | $\langle k\rangle$ | $k_{max}$
---|---|---|---|---
Enron | 143 | 1630 | 106.3 | 19
High school | 327 | 8264 | 81.9 | 6
Primary school | 242 | 13041 | 197.2 | 6
NDC-classes | 1149 | 2330 | 62.5 | 25

Evaluation metrics. We use the Susceptible-Infected-Recovered (SIR) simulation
model as an evaluation metric to objectively analyze the effect of higher-
order interactions in diffusion between nodes. In the SIR model, each node is
classified as a Susceptible (S), Infected (I), or Recovered (R) at any given
moment. A selected node is initially infected, and the rest of the network is
susceptible to be infected. In each propagation, the infected node can infect
its neighboring nodes with probability $\mu$. As this process is repeated,
infected nodes can recover with probability $\beta$ and are not susceptible to
be infected again. The number of nodes that were infected in the network
measures the diffusion level. A greater number means a greater spreading
ability and a greater influence on diffusion.

In our experiments with the SIR models, we set infection rate based on
$\mu_{c}$, where $\mu_{c}=\frac{\langle k\rangle}{\langle k^{2}\rangle-\langle
k\rangle}$, as derived from Guo et al. (2020), and $\langle k\rangle$ is equal
to the average weighted degree of the network. Furthermore, for the infection
rate, we can also consider the weights of interactions. In this paper, we set
the infection rate of an interaction of weight $w>0$ to
$\mu_{w}=1-(1-\mu)^{w}$, following Sun et al. (2014). For simplicity, the
recovery rate is set as $\beta=1$. The experiment is run 100 times for each
dataset, and the average of the 100 trials is taken to obtain more reliable
results.

As Yu et al. (2018) suggests, we use the normalized final effected scale for
evaluation, which is defined as

$\displaystyle F(u)=\frac{n_{u}}{n}$

where $n_{u}$ is the number of affected nodes when node $u$ is infected, and
$n$ is the total number of nodes. To compute the influence of higher-order
interactions, we calculate the average influence of all nodes after removing a
certain fraction of hyperedges as the following diffusion index

$\displaystyle R_{s}=\frac{F_{1}-F_{2}}{F_{1}}$

where $F_{i}$ is the average final infected scale of all nodes, i.e.,
$F_{i}=\frac{1}{n}\sum_{u\in V}F(u)$ for $i\in\\{1,2\\}$, and $F_{1}$ and
$F_{2}$ are results of the original network and the network after removing $p$
of higher-order interactions respectively.

In our experiment, we obtain three different results. For the first result, we
first rank the higher-order interactions from the most influential to the
least based on the centralities and divide them into 50 parts. For each step,
we only remove one part and calculate the diffusion index. Finally, we sort
the diffusion indices of the 50 parts for each centrality and find its
spearman correlation coefficients to the centrality scores. As we see in Table
3, the proposed hypergraph centrality measures can find the influential
higher-order interactions in diffusion effectively. All the correlations are
high for the Enron dataset and are about 90%, except for 85% for $H_{DFF}$. In
the High school dataset, all of the centrality measures’ rankings are highly
correlated with the SIR findings: they are all about $98\%$. It is the same
for the Primary school dataset, except $H_{Btw}$. The correlations are a
little lower for the NDC-classes dataset than the other datasets (it is in
between %76-%80 for all but about %55 for $H_{Btw}$). The reason is that since
the ratio between the number of nodes and simplices is low in this dataset,
the infection rate becomes relatively small. This makes diffusion difficult in
the SIR simulations, and as a result, it makes it slightly more difficult to
see the effects of removing higher-order interactions. In general, $H_{DFF}$,
$H_{Deg}$, and $H_{Cls}$ provide similar effectiveness, and $H_{Btw}$ is
slightly less effective on the NDC-classes and Primary school datasets. We
should also note here that our main goal here is not to compare these proposed
hypergraph centralities but to show how effective they are in finding
influential higher-order interactions. As we see in Table 3, overall, they are
quite effective in finding influential higher-order interactions.

Table 3: Spearman correlation coefficients between the ranking scores and the diffusion indices. The results are averaged over 100 independent implementations with $\mu/\mu_{c}=1.5$. | $H_{DFF}$ | $H_{Deg}$ | $H_{Btw}$ | $H_{Cls}$
---|---|---|---|---
Enron | %85.87 | %90.25 | %90.67 | %90.55
High school | %98.93 | %97.79 | %98.39 | %98.54
Primary school | %97.64 | %98.05 | %83.64 | %95.58
NDC-classes | %79.43 | %76.84 | %54.32 | % 78.11

For the second result, we fix the infection rate at $\mu=1.5\mu_{c}$ and vary
the ratio of the removed influential higher-order interactions in Figure 2.
The graphs are plotted with the diffusion index $R_{s}$ on the $y$-axes and
the varying ratio of simplices ($p$) on the $x$-axes. When analyzing the graph
for the Enron dataset, it can be inferred that degree, betweenness, and
closeness are seen to overlap each other and possesses a higher diffusion
index $R_{s}$ in comparison to DFF centrality. Therefore, it can be concluded
that for the Enron dataset, degree, betweenness, and closeness centralities
can be considered to be almost equally effective due to a consistently high
$R_{s}$ value with the increasing ratio of simplices. For the High School
dataset, it can be observed that DFF centrality is the most effective of the
four centrality measures with betweeness and closeness centralities
overlapping and following the same set of values for $R_{s}$ with an increase
in the varying ratios. In contrast, the degree centrality proved to be least
effective for its low $R_{s}$ value below 0.5. Primary school dataset has the
most consistent increase in the value of diffusion index $R_{s}$ for all the
centrality measures as there are little or no anomalies within the curves
plotted for the four different centrality measures. The degree and the DFF
centralities are considered the most effective centralities as they both yield
the highest value of $R_{s}$ in comparison to betweenness and closeness
centralities. Finally, for the NDC-classes dataset, it can be seen that
initially the DFF centrality had a higher diffusion index ($R_{s}$) in
comparison to the degree centrality. Still, after the ratio ($p$) increases
above 12.5, the degree centrality proves to be more effective than the DFF
centrality and the other two centrality measures. In conclusion, all the four
centrality measures proved to be effective with varying ratios of higher-order
interactions used within this SIR model.

Figure 2: Varying ratio of simplices through the implementation of the SIR
Model. Here the infection rate is kept constant while the influential
simplices are obtained by using each of the centrality measures. A higher
diffusion index ($R_{s}$) determines the effectiveness of each of these
methods.

For the third result, we fix the ratio of the removed higher-order
interactions at $5\%$ and vary the infection rate to compare the centrality
measures further in Figure 3. A greater diffusion index or $R_{s}$ indicates
that the removed simplices are influential, and therefore, the method is more
effective. With the Enron dataset, closeness centrality performs the most
effectively with betweenness centrality after it. DFF overall performs about
as well as degree centrality but is outperformed by betweenness centrality and
closeness centrality. However, the differences in performances are not
drastic, and all the centrality measures overall perform well. In the Primary
school network, degree centrality outperforms all the other centrality
measures. Closeness and DFF overlap at several infection rates, with DFF
performing slightly more effectively at other infection rates. In the High
school dataset, DFF outperforms all the other centrality measures. However,
after the infection rate reaches 1.8, betweenness centrality performs better
than the rest of the centrality measures. Closeness centrality also performs
well. In this dataset, degree centrality does not perform as well. When
analyzing the NDC-classes network, it can be concluded that DFF outperforms
all the centrality measures. Degree centrality performs better than closeness
centrality at the lower infection rates. The two centrality measures’
effectiveness is about the same when the infection rate is set in between
1.4-1.6. At the greater infection rates, closeness outperforms degree
centrality. Betweenness centrality is the least effective of the centrality
measures in this dataset, but performance is not drastic. It can be noted that
with Enron and NDC-classes, as the infection rate increases, the diffusion
index or $R_{s}$ increases as well. However, for High school and Primary
school, $R_{s}$ initially increases but then decreases. This is due to the
network structure of these two datasets. Overall, the centrality methods, with
varying performances depending on the network applied to, effectively identify
influential higher-order interactions in complex networks for various
infection rates used in the SIR model.

Figure 3: Varying infection rate when using the SIR model on the selected
networks. The ratio of simplices removed in each trial is the top 5% of
influential simplices found by each of the centrality measures. A greater
diffusion index or $R_{s}$ indicates that the method is more effective.

##  4 Discussion

By proposing two new hypergraph Laplacians, we are able to redefine DFF,
betweenness centrality, closeness centrality, and degree centrality to
determine the influential higher-order interactions of a network. These
centrality measures are applied to four real-world network datasets. The
performances of the centrality measures in identifying influential higher-
order network interactions are compared and evaluated by the SIR model and
using spearman’s rank correlation coefficients. Overall, all the centrality
measures, adjusted to work with higher-order simplices, are effective in
finding influential higher-order interactions. The high spearman correlations
values for the centrality measures indicate this effectiveness as in Table 3.
Furthermore, the methods are effective when varying the ratio of infected
simplicies and when varying infection rates.

As mentioned earlier, there are not many known centrality measures capable of
effectively analyzing and identifying influential higher-order interactions in
complex networks. Being able to utilize several centrality measures provides
more flexibility, expanding the uses of determining significant higher-order
interactions. It also provides more options to select the best possible method
of analyzing higher-order interactions based on specific types of networks as
well as computational complexity and more room to expand on methods for
finding influential higher-order interactions. The results found are
significant as they provide a basis for DFF, betweenness centrality, closeness
centrality, and degree centrality, through hypergraph Laplacians, to be
utilized in real-life applications such as rumor controlling, marketing,
disease spreading, advertising, and more.

## References

  * Kempe et al. [2003] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 137–146, 2003.
  * Wang et al. [2020] Shanfeng Wang, Maoguo Gong, Wenfeng Liu, and Yue Wu.  Preventing epidemic spreading in networks by community detection and memetic algorithm.  _Applied Soft Computing_ , 89:106118, 2020.
  * Bonacich [1972] Phillip Bonacich.  Factoring and weighting approaches to status scores and clique identification.  _Journal of mathematical sociology_ , 2(1):113–120, 1972.
  * Lü et al. [2016] Linyuan Lü, Tao Zhou, Qian-Ming Zhang, and H Eugene Stanley.  The h-index of a network node and its relation to degree and coreness.  _Nature communications_ , 7(1):1–7, 2016.
  * Freeman [1978] Linton C Freeman.  Centrality in social networks conceptual clarification.  _Social networks_ , 1(3):215–239, 1978.
  * Freeman [1977] Linton C Freeman.  A set of measures of centrality based on betweenness.  _Sociometry_ , pages 35–41, 1977.
  * Brin and Page [1998] Sergey Brin and Lawrence Page.  The anatomy of a large-scale hypertextual web search engine.  _Computer networks and ISDN systems_ , 30(1-7):107–117, 1998.
  * [8] Mehmet E Aktas, Sidra Jawaid, Ebony Harrington, and Esra Akbas.  Influential nodes detection in complex networks via diffusion fréchet function.  under review.
  * Arulselvan et al. [2009] Ashwin Arulselvan, Clayton W Commander, Lily Elefteriadou, and Panos M Pardalos.  Detecting critical nodes in sparse graphs.  _Computers & Operations Research_, 36(7):2193–2200, 2009.
  * Yang et al. [2019] Guoli Yang, Tina P Benko, Matteo Cavaliere, Jincai Huang, and Matjaž Perc.  Identification of influential invaders in evolutionary populations.  _Scientific reports_ , 9(1):1–12, 2019.
  * Giuraniuc et al. [2005] CV Giuraniuc, JPL Hatchett, JO Indekeu, M Leone, I Pérez Castillo, Bert Van Schaeybroeck, and Carlo Vanderzande.  Trading interactions for topology in scale-free networks.  _Physical review letters_ , 95(9):098701, 2005\.
  * Girvan and Newman [2002] Michelle Girvan and Mark EJ Newman.  Community structure in social and biological networks.  _Proceedings of the national academy of sciences_ , 99(12):7821–7826, 2002.
  * Wang et al. [2017] Ziqi Wang, Jinghan He, Alexandru Nechifor, Dahai Zhang, and Peter Crossley.  Identification of critical transmission lines in complex power networks.  _Energies_ , 10(9):1294, 2017.
  * Zio et al. [2012] Enrico Zio, Lucia R Golea, et al.  Identifying groups of critical edges in a realistic electrical network by multi-objective genetic algorithms.  _Reliability Engineering & System Safety_, 99:172–177, 2012.
  * Saito et al. [2016] Kazumi Saito, Masahiro Kimura, Kouzou Ohara, and Hiroshi Motoda.  Detecting critical links in complex network to maintain information flow/reachability.  In _Pacific Rim International Conference on Artificial Intelligence_ , pages 419–432. Springer, 2016.
  * Wong et al. [2017] Petrie Wong, Cliz Sun, Eric Lo, Man Lung Yiu, Xiaowei Wu, Zhichao Zhao, T-H Hubert Chan, and Ben Kao.  Finding k most influential edges on flow graphs.  _Information Systems_ , 65:93–105, 2017.
  * Hamers et al. [1989] Lieve Hamers et al.  Similarity measures in scientometric research: The jaccard index versus salton’s cosine formula.  _Information Processing and Management_ , 25(3):315–18, 1989.
  * Yu et al. [2018] En-Yu Yu, Duan-Bing Chen, and Jun-Yan Zhao.  Identifying critical edges in complex networks.  _Scientific reports_ , 8(1):1–8, 2018.
  * Cheng et al. [2010] Xue-Qi Cheng, Fu-Xin Ren, Hua-Wei Shen, Zi-Ke Zhang, and Tao Zhou.  Bridgeness: a local index on edge significance in maintaining global connectivity.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2010(10):P10011, 2010.
  * Battiston et al. [2020] Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri.  Networks beyond pairwise interactions: structure and dynamics.  _arXiv preprint arXiv:2006.01764_ , 2020.
  * Veremyev et al. [2017] Alexander Veremyev, Oleg A Prokopyev, and Eduardo L Pasiliao.  Finding groups with maximum betweenness centrality.  _Optimization Methods and Software_ , 32(2):369–399, 2017.
  * Veremyev et al. [2019] Alexander Veremyev, Oleg A Prokopyev, and Eduardo L Pasiliao.  Finding critical links for closeness centrality.  _INFORMS Journal on Computing_ , 31(2):367–389, 2019.
  * Vogiatzis et al. [2015] Chrysafis Vogiatzis, Alexander Veremyev, Eduardo L Pasiliao, and Panos M Pardalos.  An integer programming approach for finding the most and the least central cliques.  _Optimization Letters_ , 9(4):615–633, 2015.
  * Nasirian et al. [2020] Farzaneh Nasirian, Foad Mahdavi Pajouh, and Balabhaskar Balasundaram.  Detecting a most closeness-central clique in complex networks.  _European Journal of Operational Research_ , 283(2):461–475, 2020.
  * Zhao et al. [2017] Junzhou Zhao, Pinghui Wang, John CS Lui, Don Towsley, and Xiaohong Guan.  I/o-efficient calculation of h-group closeness centrality over disk-resident graphs.  _Information Sciences_ , 400:105–128, 2017.
  * Newman [2002] Mark EJ Newman.  Spread of epidemic disease on networks.  _Physical review E_ , 66(1):016128, 2002.
  * Horak and Jost [2013] Danijela Horak and Jürgen Jost.  Spectra of combinatorial laplace operators on simplicial complexes.  _Advances in Mathematics_ , 244:303–336, 2013.
  * Aktas and Akbas [2021] Mehmet Emin Aktas and Esra Akbas.  Hypergraph laplacians in diffusion framework.  _arXiv preprint arXiv:2102.08867_ , 2021.
  * Martínez et al. [2018] Diego H Díaz Martínez, Christine H Lee, Peter T Kim, and Washington Mio.  Probing the geometry of data with diffusion fréchet functions.  _Applied and Computational Harmonic Analysis_ , 2018.  Elsevier.
  * Benson et al. [2018] Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg.  Simplicial closure and higher-order link prediction.  _Proceedings of the National Academy of Sciences_ , 115(48):E11221–E11230, 2018.
  * Guo et al. [2020] Chungu Guo, Liangwei Yang, Xiao Chen, Duanbing Chen, Hui Gao, and Jing Ma.  Influential nodes identification in complex networks via information entropy.  _Entropy_ , 22(2):242, 2020.
  * Sun et al. [2014] Ye Sun, Chuang Liu, Chu-Xu Zhang, and Zi-Ke Zhang.  Epidemic spreading on weighted complex networks.  _Physics Letters A_ , 378(7-8):635–640, 2014\.


# A novel multi-photon entangled state with enhanced resilience to path loss

Armanpreet Pannu12, Amr S. Helmy1, and Hesham El Gamal2  1The Edward S. Rogers
Department of Electrical and Computer Engineering, University of Toronto
2School of Electrical and Information Engineering, Faculty of Engineering, The
University of Sydney

###### Abstract

In the realm of quantum information, entanglement stands as a cornerstone
phenomenon. It underpins a vast array of quantum information processes,
offering significant potential for advancements in quantum computing,
communication, and sensing. This paper introduces a novel multi-photon
entangled state, which generalizes the maximally entangled single-photon state
and exhibits remarkable resilience to signal attenuation in photonic
applications. We demonstrate the novelty of the proposed state through a
simplified target detection model and illustrate its superior performance over
traditional single-photon protocols, attributed to its higher entanglement
level and enhanced noise suppression capabilities. Our findings suggest that
the proposed multi-photon state holds significant promise for enhancing the
efficiency and reliability of photonic applications subject to loss. This work
lays the groundwork for future exploration into the practical applications of
multi-photon entangled states in quantum technologies, potentially
revolutionizing our approach to quantum sensing and beyond.

##  I Introduction

Described by Einstein as "spooky action at a distance," entanglement
represents a unique and counter-intuitive aspect of quantum mechanics, playing
a crucial role in quantum information. Two quantum systems are considered
entangled if their respective quantum states cannot be described
independently. In such cases, the systems exhibit non-classical correlations,
even when separated by significant distances [1]. This phenomenon can be
harnessed in various engineering applications, including quantum computing
[2], quantum communication and key distribution [3], quantum sensing [4],
among others [5].

A class of quantum states of particular interest for their entanglement
properties are the high-dimensional Bell states [6]. In this paper, we look at
the simplest such two-partite, $M$-qudit state:

$\displaystyle\ket{\psi_{1}}=\sum_{k=1}^{M}\ket{k}_{A}\ket{k}_{B}$ (1)

where $A$ and $B$ represent two distinct quantum systems, and $\ket{k}$
denotes the system being in the $k$th state (out of $M$ possible states). The
case of $M=2$ corresponds to one of the four Bell states, which are the
maximally entangled qubit states. This state’s entanglement level increases
with an increase in the dimension of each Hilbert space $M$ [6] [7] and it has
been studied for enhancing channel capacity in communications [8], improving
noise resilience in target detection and LIDAR [4], and for quantum key
distribution [9]. In photonics, this state is typically generated by
entangling two photons across $M$ modes, including orbital angular momentum
modes [10], time-bin modes [11], frequency modes [12], or even spatial modes
[13].

A notable challenge with using the state $\ket{\psi_{1}}$ in photonic
applications is its nature as a single photon state. Many applications involve
transmitting one set of spatial modes through a lossy channel, where the
single photon is either transmitted or lost entirely. This contrasts with
classical protocols where multiple photons are transmitted simultaneously, and
the attenuated light suffices to achieve the desired result. While this issue
can be mitigated by sending multiple copies of $\ket{\psi_{1}}$, it either
requires multiple sequential runs, consuming considerable time, or the use of
many sets of $M$ orthogonal modes, which could instead be used to increase
entanglement.

Most studies on multi-photon entangled states, often involve NOON states,
where all photons occupy the same mode [14], or the use of additional
orthogonal modes without directly taking multiple copies of a single entangled
photon [15]. With NOON states, losing a single photon due to attenuation
(mathematically equivalent to applying an annihilation operator) disrupts all
entanglement between the systems, while using additional orthogonal again
waste modes which could be used for increased entanglement.

Quantum sensing states that are resilient to loss have been studied and shown
to exist [16] and are of great interest for both sensing and fault-tolerant
quantum communication. In this paper, we propose and explore the theoretical
properties of a novel multi-photon generalization of the state
$\ket{\psi_{1}}$, employing $M$ orthogonal modes and retaining the
entanglement properties of any returning photons, even if many photons are
absorbed. Utilizing this state enables leveraging some of the entanglement
properties of the high-dimensional Bell state, even in scenarios where the
transmitted signal may be heavily attenuated.

##  II Multi-Photon entangled state

Before diving into the core of our discussion, we establish some notation to
pave the way for a smoother understanding. In dealing with $M$ modes of
photons, we use the notation $\ket{\mathbf{n}}$ to represent the photon number
basis state, where the boldface $\mathbf{n}$ signifies a vector. For
$\mathbf{n}=(n_{1},...,n_{M})$, the state $\ket{\mathbf{n}}$ represents a
state with $n_{i}$ photons in mode $i$. The operators $\hat{a}^{\dagger}_{i}$
and $\hat{a}_{i}$ will represent the quantum creation and annihilation
operator respectively for the $i$-th mode. These operators act on the photon
number states as follows:
$\hat{a}_{i}^{\dagger}\ket{n_{1},...,n_{i},...,n_{M}}=\sqrt{n_{i}+1}\ket{n_{1},...,n_{i}+1,...,n_{M}}$
and
$\hat{a}_{i}\ket{n_{1},...,n_{i},...,n_{M}}=\sqrt{n_{i}}\ket{n_{1},...,n_{i}-1,...,n_{M}}$.
Whenever we mention a vector $\mathbf{n}$, the corresponding non-bold variable
will represent a sum of the elements $n=|\mathbf{n}|=n_{1}+n_{2}+...+n_{M}$
(This is the $l_{1}$ norm when all elements are positive as is the case in
this paper). Extending this to multiple spatial modes, each with $M$ modes, we
use $\ket{\mathbf{n},\mathbf{m}}$ to denote the basis states for two spatial
modes, where $\mathbf{n}$ and $\mathbf{m}$ are photon numbers for each set of
spatial modes.

With this in mind, we consider the $N$ photon state across two sets of $M$
modes which we refer to as the signal and the idler:

$\displaystyle\ket{\psi_{N}}$
$\displaystyle=\frac{1}{\sqrt{C_{N}}}\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}^{N}\ket{vac}$
(2) $\displaystyle={N+M-1\choose
N}^{-\frac{1}{2}}\sum_{|\mathbf{N_{S}}|=N}\ket{\mathbf{N_{S}},\mathbf{N_{S}}}$
(3)

Here, $C_{N}$ is a normalization constant (refer to appendix A) and
$\hat{a}_{I_{i}}^{\dagger}$ and $\hat{a}_{S_{i}}^{\dagger}$ are the creation
operators for the $i$-th idler and signal modes. The sum in (3) extends over
all vectors $\mathbf{N_{S}}$ with total photon number $N$. The number of such
vectors is equal to ${N+M-1\choose N}$ which gives the normalization constant
in (3). In the case of $N=0$, we simply have the vacuum state while the case
of $N=1$ gives us the high-dimensional Bell state $\ket{\psi_{1}}$.

We begin by noting that $\ket{\psi_{N}}$ spans a larger Hilbert space than
$\ket{\psi_{1}}$, suggesting a potential for higher entanglement gains.
However, these states become particularly intriguing when we explore the
effects of attenuation. To delve into their distinctive properties, we
introduce the operator
$\hat{A}^{\dagger}=\sum_{i=1}^{M}\hat{a}_{S_{i}}^{\dagger}\hat{a}_{I_{i}}^{\dagger}$.
Employing this operator enables the recursive generation of the states
$\ket{\psi_{N}}$ via the relation:

$\displaystyle\sqrt{N}\sqrt{N+M-1}\ket{\psi_{N}}$
$\displaystyle=\hat{A}^{\dagger}\ket{\psi_{N-1}}$ (4)

With a straightforward computation, we can also show that the following
commutation relations hold:

$\displaystyle\left[\hat{a}_{S_{j}},\hat{A}^{\dagger}\right]=\hat{a}_{I_{j}}^{\dagger}\qquad\qquad\left[\hat{a}_{I_{j}},\hat{A}^{\dagger}\right]=\hat{a}_{S_{j}}^{\dagger}$
(5)

Considering the scenario where a photon from the signal data is lost, modeled
by the annihilation operator $\hat{a}_{S_{j}}$, we can use the recursive
relationship and the commutator to show by induction that the state evolves as
follows:

$\displaystyle\hat{a}_{S_{j}}\ket{\psi_{N}}$
$\displaystyle=\frac{\sqrt{N}}{\sqrt{N+M-1}}\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}$
(6)

$\displaystyle\ket{\psi_{N}}_{I,S}\otimes\ket{\mathbf{0}}_{B}$
$\displaystyle={N+M-1\choose
M-1}^{-\frac{1}{2}}\sum_{|\mathbf{N_{S}}|=N}\prod_{i=1}^{M}\frac{1}{\sqrt{N_{S_{i}}}!}(\hat{a}_{S_{i}}^{\dagger})^{N_{S_{i}}}\ket{\mathbf{N_{S}},\mathbf{0},\mathbf{0}}_{I,S,B}$
(10) $\displaystyle\rightarrow{N+M-1\choose
M-1}^{-\frac{1}{2}}\sum_{|\mathbf{N_{S}}|=N}\prod_{i=1}^{M}\frac{1}{\sqrt{N_{S_{i}}}!}(\sqrt{\eta}\hat{a}_{S_{i}}^{\dagger}+\sqrt{1-\eta}\hat{a}_{B_{i}}^{\dagger})^{N_{S_{i}}}\ket{\mathbf{N_{S}},\mathbf{0},\mathbf{0}}_{I,S,B}$
$\displaystyle={N+M-1\choose
M-1}^{-\frac{1}{2}}\sum_{|\mathbf{N_{S}}|=N}\sum_{|\mathbf{N_{A}}|\leq
N}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\Bigg{(}\prod_{i=1}^{M}\sqrt{{N_{S_{i}}\choose
N_{A_{i}}}}\Bigg{)}\ket{\mathbf{N_{S}},\mathbf{N_{S}}-\mathbf{N_{A}},\mathbf{N_{A}}}_{I,S,B}$
$\displaystyle=\sum_{|\mathbf{N_{A}}|\leq
N}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\prod_{i=1}^{M}\frac{1}{\sqrt{N_{A_{i}}!}}\left(\hat{a}_{S_{i}}\right)^{{N_{A_{i}}}}\ket{\psi_{N}}_{I,S}\otimes\ket{\mathbf{N_{A}}}_{B}$

Equation (6) establishes the novelty of the state $\ket{\psi_{N}}$. In the
case where we send $N$ photons and lose a single photon, the returning $(N-1)$
photons maintain their entanglement structure but the idler has an extra
photon compared to $\ket{\psi_{N-1}}$. One can interpret this with a simple
thought experiment where Alice sends out the $N$ signal photons to Bob who
then measures and identifies a single photon and determines the mode it
occupies. By doing so, Bob collapses one of the $N$ idler photons that Alice
is holding to the same mode the single signal photon was found in. The
remaining $(N-1)$ photons stay entangled, unaffected by the interaction of the
lost photon with Bob, who represents the environment in this scenario.

This behavior is highly atypical of photons (and bosons in general) since
their indistinguishability properties prevent us from thinking of them as
independent particles unless they occupy disjoint Hilbert spaces. Yet, in this
scenario, the photons behave as identical yet independent particles, almost as
if each photon resides in its unique Hilbert space.

In practical terms, photon loss through attenuation introduces uncertainty in
the number and modes of the lost photons. The transmitted state thus becomes a
statistical mix of states
$\prod_{i=1}^{M}(\hat{a}_{I_{i}}^{\dagger})^{N_{A_{i}}}\ket{\psi_{N-k}}$ for
all combinations of $N_{A_{1}},...,N_{A_{M}}$, where
$k=N_{A_{1}}+...+N_{A_{M}}\leq N$. These states are mutually orthogonal,
allowing for measurements of the final state to account for all possible
incoming states and still exploit the entanglement present in the $N-k$
returning photons.

##  III Quantum Target Detection

To demonstrate the potential of this state for sensing applications, we
explore the problem of target detection, where the goal is to discern the
presence or absence of a target with reflectivity $0<\eta<1$ by probing with a
light source. In our model, we assume that there exists background noise that
could falsely signal the target’s presence. In this simplified scenario, we
assume that the receiver picks up either background noise or the partially
reflected signal but not both at the same time (where the attenuated version
of $\ket{\psi_{N}}$ mixes with the noise) akin to the approach in foundational
target detection work [4]. This model holds practical value when the average
incoming noise and average reflected photons ($MP_{B}$ and $\eta N$) are both
much less than one or in sensing applications where the goal is security and
deterring bad actors from sending false reflections.

In the case where the target is present, the loss is modeled with a
beamsplitter of reflectivity $\eta$ where one input is the signal and the
other one is the vacuum (excluding noise mixing). In the Heisenberg picture,
the creation operator evolves as
$\hat{a}_{S_{i}}^{\dagger}\rightarrow\sqrt{\eta}\hat{a}_{S_{i}}^{\dagger}+\sqrt{1-\eta}\hat{a}_{B_{i}}^{\dagger}$.
Evolving the signal, idler, and background modes as in equations (10) to (10)
on the bottom of the page 10 and tracing out the background modes, we derive
the collected state in the case of target present:

$\displaystyle\rho_{pres}=\sum_{|\mathbf{N_{A}}|\leq
N}\ket{\tilde{\phi}_{\mathbf{N_{A}}}}\bra{\tilde{\phi}_{\mathbf{N_{A}}}}$ (8)

where

$\displaystyle\ket{\tilde{\phi}_{\mathbf{N_{A}}}}$
$\displaystyle=\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\prod_{i=1}^{M}\frac{1}{\sqrt{N_{A_{i}}!}}\left(\hat{a}_{S_{i}}\right)^{{N_{A_{i}}}}\ket{\psi_{N}}$
(9)

Thus the collected light comes back as a mixture of
$\ket{\tilde{\phi}_{\mathbf{N_{A}}}}$ which is the un-normalized version of
the state where $\mathbf{N_{A}}$ photons remain in the environment. The norm
of these states $\bra{\phi_{\mathbf{N_{A}}}}\ket{\phi_{\mathbf{N_{A}}}}$ gives
the probability of measuring $\mathbf{N_{A}}$ photons in the environment as
evident by equation (8) and the orthogonality of the states
$\ket{\phi_{\mathbf{N_{A}}}}$. Given the unknown number of photons that remain
in the environment, our measurement must account for all possibilities.
Fortunately the normalized states
$\ket{\phi_{\mathbf{N_{A}}}}=\frac{\ket{\tilde{\phi}}}{\sqrt{\innerproduct{\tilde{\phi}_{\mathbf{N_{A}}}}{\tilde{\phi}_{\mathbf{N_{A}}}}}}$
are orthonormal, facilitating the use of the projective measurement
$\left\\{\hat{P},1-\hat{P}\right\\}$ where:

$\displaystyle\hat{P}=\sum_{|\mathbf{N_{A}}|\leq{N-1}}\ket{\phi_{\mathbf{N_{A}}}}\bra{\phi_{\mathbf{N_{A}}}}$
(10)

This measurement scheme excludes scenarios where $|\mathbf{N_{A}}|=N$,
indicating total photon absorption. The probability of a positive detection,
in the presence of a target, is given by:

$\displaystyle 1-P_{MD}$ $\displaystyle=Tr\left[\hat{P}\rho_{pres}\right]$
(11)
$\displaystyle=\sum_{\mathbf{N_{A}}\leq{N-1}}\innerproduct{\tilde{\phi}_{\mathbf{N_{A}}}}{\tilde{\phi}_{\mathbf{N_{A}}}}$
(12) $\displaystyle=1-(1-\eta)^{N}$ (13)

(a) $N=10$

(b) $N=100$

(c) $N=1000$

Figure 1: Comparison of the Probability of false alarm for a varying number of
incoming photons. The blue dashed curve is $P_{FA}=\frac{1}{M}$ which is the
probability of a false alarm when one photon in the state $\ket{\psi_{1}}$ is
transmitted. The orange dashed curve is $P_{FA}=\frac{N}{M}$ which is the
$N<<M$ approximation of the probability of a false alarm if $N$ copies of the
$\ket{\psi_{1}}$ are transmitted. The overall probability of error depends
highly on how the noise is distributed.

This indicates that a missed detection occurs solely when all $N$ photons are
absorbed, with even a single returning photon indicating target presence.
However, this approach’s efficacy hinges on whether utilizing $\ket{\psi_{N}}$
alongside $\hat{P}$ enhances noise resilience.

In the case that the detector picks up only environmental noise, the idler
mode is simply the starting state traced out and the signal is replaced with
the environment. The returning state is:

$\displaystyle\rho_{abs}={N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{S}}|=N}\sum_{\mathbf{N_{B}}}p_{\mathbf{N_{B}}}\ket{\mathbf{N_{S}},\mathbf{N_{B}}}\bra{\mathbf{N_{S}},\mathbf{N_{B}}}$
(14)

where $p_{\mathbf{N_{B}}}$ is the probability of having $\mathbf{N_{B}}$
photons in the environment. Typically, this is taken to be the probability
distribution given by identical thermal states in each mode. The only
assumption we make here is that this probability solely depends on the total
number of noise photons so $p_{\mathbf{N_{B}}}=\tilde{p}_{N_{B}}$ (which is
indeed the case for thermal noise). We highlight that this is the probability
of having $N_{B}$ photons in a particular arrangement while the overall
probability of having $N_{B}$ photons accounting for all arrangements is
${N_{B}+M-1\choose N_{B}}\tilde{p}_{N_{B}}$.
The probability of getting a false alarm can be computed as in the appendix:

$\displaystyle P_{FA}$
$\displaystyle=\tilde{p}_{1}\frac{N}{N+M-1}+\tilde{p}_{2}\frac{N(N-1)}{(N+M-1)(N+M-2)}+$
$\displaystyle\qquad\qquad\qquad\qquad...+\tilde{p}_{N}{M+N-1\choose
N}^{(-1)}$ (15)

Each term in this result corresponds to a different number of photons picked
up by the detector. All terms go to zero as $M\rightarrow\infty$ demonstrating
that the state $\ket{\psi_{N}}$ has the same noise suppression property as
$\ket{\psi_{1}}$ which is characterized by $P^{1}_{FA}\sim\frac{1}{M}$.

In comparison to the single-photon protocol using $\ket{\psi_{1}}$ as in [4],
the first term which corresponds to a single incoming noise photon has worse
performance for all $N>1$. However, all other terms in (15) eventually surpass
$\frac{1}{M}$ for large enough $M$ as can be seen in figure 1. The last term
corresponds to receiving all the $N$ transmitted photons in which case the
error scales inversely to the number of terms in (3) and is always lower than
$\frac{1}{M}$. With an increase in the number of photons returned error
probabilities diminish more rapidly with $M$, leading to lower error rates due
to increased entanglement.

Furthermore, if we factor in attenuation (which was the initial motivation for
$\ket{\psi_{N}}$), a protocol using $\ket{\psi_{1}}$ necessitates sending $N$
copies to match the energy expenditure and expected number of reflected
photons with that of a protocol using $\ket{\psi_{N}}$. As a result, the
probability of a false alarm in the single photon case goes up to
$\frac{N}{M}$, in the $N<<M$ approximation, and thus every term in (15)
outperforms the single-photon protocol. Intuitively, this is because
transmitting a single photon across $N$ trials necessitates more frequent
detector activation compared to transmitting all $N$ photons simultaneously,
thus increasing noise susceptibility.

It’s also important to recognize that $\tilde{p}_{i}$ might vary with $M$. In
most practical scenarios, including those involving thermal noise, increasing
$M$ tends to result in greater noise pickup. This works in our favor, as it
pushes the distribution of $\tilde{p}_{i}$ towards higher values of $i$. This
effect, in turn, shifts the false alarm probability in equation (15) to the
higher-order terms, which have better noise suppression.

The overall probability of error is heavily dependent on the noise profile and
$\tilde{p}_{i}$. With a preliminary understanding of the expected photon
return in the presence of a target, we can refine the projector $\hat{P}$ to
focus on a narrower photon range, thereby reducing false alarm rates,
especially when the anticipated number of photons due to target reflectivity,
$\eta N$, is different from the expected noise photons.

##  IV Conclusion

In conclusion, we have introduced a multi-photon entangled state that extends
the concept of the maximally entangled single-photon Bell state
$\ket{\psi_{1}}$. This innovative state possesses a remarkable property: even
when the signal undergoes attenuation, the entanglement structure of the
returning photons is largely preserved, as though a smaller number of photons
were dispatched without any loss.

Our exploration into a simplified target detection scenario highlights the
unique advantages of this multi-photon state. Not only does it maintain its
integrity in the face of attenuation, but it also surpasses the single-photon
protocol, thanks to a higher level of entanglement and diminished noise
interference due to fewer detection events.

The characteristics of the $\ket{\psi_{N}}$ state, as examined in this study,
indicate potential benefits across a range of photonic applications that
utilize the two-partite Bell state and are prone to loss. Although further
investigation is necessary to determine whether $\ket{\psi_{N}}$ exhibits
similar advantages in other contexts, particularly where noise mixing or
alternative channels play a role, the increased photon count and expanded
Hilbert space suggest that its susceptibility to external disturbances should
be equal to or less than that of multiple copies of $\ket{\psi_{1}}$.

## References

  * [1] J. S. Bell, “On the einstein podolsky rosen paradox,” _Physics Physique Fizika_ , vol. 1, pp. 195–200, Nov 1964. [Online]. Available: https://link.aps.org/doi/10.1103/PhysicsPhysiqueFizika.1.195
  * [2] R. P. Feynman, “Simulating physics with computers,” _International journal of theoretical physics_ , vol. 21, no. 6/7, pp. 467–488, 1982.
  * [3] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” _Theoretical Computer Science_ , vol. 560, p. 7–11, Dec. 2014. [Online]. Available: http://dx.doi.org/10.1016/j.tcs.2014.05.025
  * [4] S. Lloyd, “Enhanced sensitivity of photodetection via quantum illumination,” _Science_ , vol. 321, no. 5895, pp. 1463–1465, 2008.
  * [5] F. J. Duarte and T. S. Taylor, _Quantum Entanglement Engineering and Applications_ , ser. 2053-2563. IOP Publishing, 2021. [Online]. Available: https://dx.doi.org/10.1088/978-0-7503-3407-5
  * [6] D. Collins, N. Gisin, N. Linden, S. Massar, and S. Popescu, “Bell inequalities for arbitrarily high-dimensional systems,” _Phys. Rev. Lett._ , vol. 88, p. 040404, Jan 2002. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.88.040404
  * [7] D. Kaszlikowski, P. Gnaciński, M. Żukowski, W. Miklaszewski, and A. Zeilinger, “Violations of local realism by two entangled qunits are stronger than for two qubits,” _Physical Review Letters_ , vol. 85, no. 21, p. 4418–4421, Nov. 2000. [Online]. Available: http://dx.doi.org/10.1103/PhysRevLett.85.4418
  * [8] X.-M. Hu, Y. Guo, B.-H. Liu, Y.-F. Huang, C.-F. Li, and G.-C. Guo, “Beating the channel capacity limit for superdense coding with entangled ququarts,” _Science Advances_ , vol. 4, no. 7, p. eaat9304, 2018. [Online]. Available: https://www.science.org/doi/abs/10.1126/sciadv.aat9304
  * [9] L. Sheridan and V. Scarani, “Security proof for quantum key distribution using qudit systems,” _Physical Review A_ , vol. 82, no. 3, Sep. 2010. [Online]. Available: http://dx.doi.org/10.1103/PhysRevA.82.030301
  * [10] A. Mair, A. Vaziri, G. Weihs, and A. Zeilinger, “Entanglement of the orbital angular momentum states of photons,” _Nature_ , vol. 412, no. 6844, p. 313–316, Jul. 2001. [Online]. Available: http://dx.doi.org/10.1038/35085529
  * [11] I. Marcikic, H. de Riedmatten, W. Tittel, V. Scarani, H. Zbinden, and N. Gisin, “Time-bin entangled qubits for quantum communication created by femtosecond pulses,” _Phys. Rev. A_ , vol. 66, p. 062308, Dec 2002. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.66.062308
  * [12] R. Jin, R. Shimizu, M. Fujiwara, M. Takeoka, R. Wakabayashi, T. Yamashita, S. Miki, H. Terai, T. Gerrits, and M. Sasaki, “Simple method of generating and distributing frequency-entangled qudits,” _Quantum Science and Technology_ , vol. 1, p. 015004, 11 2016.
  * [13] M. Żukowski, A. Zeilinger, and M. A. Horne, “Realizable higher-dimensional two-particle entanglements via multiport beam splitters,” _Phys. Rev. A_ , vol. 55, pp. 2564–2579, Apr 1997. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.55.2564
  * [14] M. W. Mitchell, J. S. Lundeen, and A. M. Steinberg, “Super-resolving phase measurements with a multiphoton entangled state,” _Nature_ , vol. 429, no. 6988, p. 161–164, May 2004. [Online]. Available: http://dx.doi.org/10.1038/nature02493
  * [15] M. Malik, M. Erhard, M. Huber, M. Krenn, R. Fickler, and A. Zeilinger, “Multi-photon entanglement in high dimensions,” _Nature Photonics_ , vol. 10, no. 4, p. 248–252, Feb. 2016. [Online]. Available: http://dx.doi.org/10.1038/nphoton.2016.12
  * [16] M. Oszmaniec, R. Augusiak, C. Gogolin, J. Kołodyński, A. Acín, and M. Lewenstein, “Random bosonic states for robust quantum metrology,” _Physical Review X_ , vol. 6, no. 4, Dec. 2016. [Online]. Available: http://dx.doi.org/10.1103/PhysRevX.6.041044

##  V Appendix

###  V-A The states and their recursive relations

Starting from our proposed definition (2), we have:

$\displaystyle\ket{\psi_{N}}$
$\displaystyle=\frac{1}{\sqrt{C_{N}}}\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}^{N}\ket{vac}$
(16)
$\displaystyle=\frac{1}{\sqrt{C_{N}}}\left(\sum_{|\mathbf{N_{S}}|=N}{N\choose
N_{S_{1}},...,N_{S_{M}}}\left(\mathbf{\hat{a}}^{\dagger}_{I}\mathbf{\hat{a}}^{\dagger}_{S}\right)^{\mathbf{N_{S}}}\right)\ket{vac}$
(17)
$\displaystyle=\frac{1}{\sqrt{C_{N}}}\sum_{|\mathbf{N_{S}}|=N}N!\ket{\mathbf{N_{S}},\mathbf{N_{S}}}$
(18)

Equation (17) follows from the multinomial theorem where ${N\choose
N_{S_{1}},...,N_{S_{M}}}=\frac{N!}{N_{S_{1}}!...N_{S_{M}}!}$ is the
multinomial coefficient. The normalization constant can be computed as:

$\displaystyle 1$
$\displaystyle=\sum_{|\mathbf{N_{S}}|=N}\frac{1}{C_{N}}(N!)^{2}$ (19)
$\displaystyle=\frac{(N!)^{2}}{C_{N}}\sum_{|\mathbf{N_{S}}|=N}1$ (20)
$\displaystyle=\frac{(N!)^{2}}{C_{N}}{{N+M-1}\choose{M-1}}$ (21)
$\displaystyle C_{N}$ $\displaystyle=\frac{N!(N+M-1)!}{(M-1)!}$ (22)

Here, equation (21) follows from a standard combinatorics formula for the
number of vectors with element by element sum equal to $N$. Furthermore, we
have that:

$\displaystyle\frac{C_{N}}{C_{N-1}}$
$\displaystyle=N!\frac{(N+M-1)!}{(M-1)!}\frac{1}{(N-1)!}\frac{(M-1)!}{(N+M-2)!}$
(23) $\displaystyle=N(N+M-1)$ (24)

Which we can use to construct a recursive formula as:

$\displaystyle\ket{\psi_{N}}$
$\displaystyle=\frac{1}{\sqrt{C_{N}}}\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}^{N}\ket{vac}$
(25)
$\displaystyle=\frac{1}{\sqrt{C_{N}}}\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}^{N-1}\ket{vac}$
(26)
$\displaystyle=\frac{\sqrt{C_{N-1}}}{\sqrt{C_{N}}}\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}\ket{\psi_{N-1}}$
(27)
$\displaystyle=\frac{1}{\sqrt{N}\sqrt{N+M-1}}\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}\ket{\psi_{N-1}}$
(28) $\displaystyle\sqrt{N}\sqrt{N+M-1}\ket{\psi_{N}}$
$\displaystyle=\Bigg{(}\sum_{i=1}^{M}\hat{a}_{I_{i}}^{\dagger}\hat{a}_{S_{i}}^{\dagger}\Bigg{)}\ket{\psi_{N-1}}$
(29) $\displaystyle\sqrt{N}\sqrt{N+M-1}\ket{\psi_{N}}$
$\displaystyle=\hat{A}^{\dagger}\ket{\psi_{N-1}}$ (30)

where we let
$\hat{A}^{\dagger}=\sum_{i=1}^{M}\hat{a}_{S_{i}}^{\dagger}\hat{a}_{I_{i}}^{\dagger}$.

Now to study the behavior of the state $\ket{\psi_{N}}$ as a photon is
removed, we first compute the commutator:

$\displaystyle\left[\hat{a}_{S_{j}},\hat{A}^{\dagger}\right]$
$\displaystyle=\sum_{i=1}^{M}\left[\hat{a}_{S_{j}},\hat{a}_{S_{i}}^{\dagger}\hat{a}_{I_{i}}^{\dagger}\right]$
(31)
$\displaystyle=\left[\hat{a}_{S_{j}},\hat{a}_{S_{j}}^{\dagger}\hat{a}_{I_{j}}^{\dagger}\right]$
(32)
$\displaystyle=\sum_{i=1}^{M}\Big{(}\hat{a}_{S_{j}}\hat{a}_{S_{j}}^{\dagger}\hat{a}_{I_{j}}^{\dagger}-\hat{a}_{S_{j}}^{\dagger}\hat{a}_{I_{j}}^{\dagger}\hat{a}_{S_{j}}\Big{)}$
(33) $\displaystyle\left[\hat{a}_{S_{j}},\hat{A}^{\dagger}\right]$
$\displaystyle=\hat{a}_{I_{j}}^{\dagger}\qquad\qquad\qquad\qquad\qquad\qquad\text{likewise:}\quad\left[\hat{a}_{I_{j}},\hat{A}^{\dagger}\right]=\hat{a}_{S_{j}}^{\dagger}$
(34)

So applying an annihilation to the state, we claim that:

$\displaystyle\hat{a}_{S_{j}}\ket{\psi_{N}}=\frac{\sqrt{N}}{\sqrt{N+M-1}}\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}$
(35)

We can prove this by induction on $N$. For $N=1$, this is easy to verify:

$\displaystyle\hat{a}_{S_{j}}\ket{\psi_{N}}$
$\displaystyle=\frac{1}{\sqrt{M}}\hat{a}_{S_{j}}\sum_{i=1}^{M}\ket{\mathbf{e}_{i},\mathbf{e}_{i}}$
(36) $\displaystyle=\ket{\mathbf{e}_{j},0}$ (37)
$\displaystyle=\frac{\sqrt{1}}{\sqrt{1+M-1}}\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{0}}$
(38)

Now for the induction step, assume (35) holds for $N-1$

$\displaystyle\sqrt{N}\sqrt{N+M-1}\hat{a}_{S_{j}}\ket{\psi_{N}}$
$\displaystyle=\hat{a}_{S_{j}}\hat{A}^{\dagger}\ket{\psi_{N-1}}$ (39)
$\displaystyle=\left(\hat{a}_{I_{j}}^{\dagger}+\hat{A}^{\dagger}\hat{a}_{S_{j}}\right)\ket{\psi_{N-1}}$
(40)
$\displaystyle=\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}+\hat{A}^{\dagger}\hat{a}_{S_{j}}\ket{\psi_{N-1}}$
(41)
$\displaystyle=\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}+\frac{\sqrt{N-1}}{\sqrt{N+M-2}}\hat{A}^{\dagger}\hat{a}_{I_{J}}^{\dagger}\ket{\psi_{N-2}}\qquad\text{use
inductive hypothesis}$ (42)
$\displaystyle=\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}+\frac{\sqrt{N-1}}{\sqrt{N+M-2}}\hat{a}_{I_{J}}^{\dagger}\hat{A}^{\dagger}\ket{\psi_{N-2}}\qquad\text{the
idler operators commute with }\hat{A}^{\dagger}$ (43)
$\displaystyle=\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}+\sqrt{N-1}\sqrt{N+M-2}\frac{\sqrt{N-1}}{\sqrt{N+M-2}}\hat{a}_{I_{J}}^{\dagger}\ket{\psi_{N-1}}$
(44) $\displaystyle\sqrt{N}\sqrt{N+M-1}\hat{a}_{S_{j}}\ket{\psi_{N}}$
$\displaystyle=\left(1+(N-1)\right)\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}$
(45) $\displaystyle\hat{a}_{S_{j}}\ket{\psi_{N}}$
$\displaystyle=\frac{\sqrt{N}}{\sqrt{N+M-1}}\hat{a}_{I_{j}}^{\dagger}\ket{\psi_{N-1}}$
(46)

###  V-B Constructing the Projector

The state $\ket{\tilde{\phi}_{\mathbf{N_{A}}}}$ is:

$\displaystyle\ket{\tilde{\phi}_{\mathbf{N_{A}}}}$
$\displaystyle=\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\prod_{i=1}^{M}\frac{1}{\sqrt{N_{A_{i}}!}}\left(\hat{a}_{S_{i}}\right)^{{N_{A_{i}}}}\ket{\psi_{N}}_{I,S}$
(47) $\displaystyle={N+M-1\choose
M-1}^{-\frac{1}{2}}\sum_{\mathbf{N_{S}}}\sqrt{\eta}^{N_{s}-N_{A}}\sqrt{1-\eta}^{N_{A}}\left(\mathbf{\hat{a}_{S}}\right)^{\mathbf{N_{A}}}\ket{\mathbf{N_{S}},\mathbf{N_{S}}}$
(48)
$\displaystyle=\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\left(\mathbf{\hat{a}_{S}}\right)^{\mathbf{N_{A}}}\ket{\psi_{N}}$
(49)
$\displaystyle=\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\left(\prod_{n=N-N_{A}+1}^{N}\frac{\sqrt{n}}{\sqrt{n+M-1}}\right)\left(\mathbf{\hat{a}_{I}}^{\dagger}\right)^{\mathbf{N_{A}}}\ket{\psi_{N-N_{A}}}$
(50)
$\displaystyle=\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\sqrt{\frac{N!}{(N-N_{A})!}\frac{(N-N_{A}+M-1)!}{(N+M-1)!}}\left(\mathbf{\hat{a}_{I}}^{\dagger}\right)^{\mathbf{N_{A}}}\ket{\psi_{N-N_{A}}}$
(51)
$\displaystyle=\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\sqrt{{N-N_{A}+M-1\choose
N-N_{A}}{N+M-1\choose
N}^{-1}}\left(\mathbf{\hat{a}_{I}}^{\dagger}\right)^{\mathbf{N_{A}}}\ket{\psi_{N-N_{A}}}$
(52)
$\displaystyle=\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\sqrt{{N+M-1\choose
N}^{-1}}\left(\mathbf{\hat{a}_{I}}^{\dagger}\right)^{\mathbf{N_{A}}}\sum_{|\mathbf{N_{S}}|=N-N_{A}}\ket{\mathbf{N_{S}},\mathbf{N_{S}}}$
(53)
$\displaystyle=\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{\eta}^{N-N_{A}}\sqrt{1-\eta}^{N_{A}}\sqrt{{N+M-1\choose
N}^{-1}}\sum_{|\mathbf{N_{S}}|=N-N_{A}}\frac{\sqrt{(\mathbf{N_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N_{S}}!}}\ket{\mathbf{N_{S}}+\mathbf{N_{A}},\mathbf{N_{S}}}$
(54)

Before we construct the projector, we need to compute the norm and inner
products. The norm is:

$\displaystyle\bra{\tilde{\phi}_{\mathbf{N_{A}}}}\ket{\tilde{\phi}_{\mathbf{N_{A}}}}$
$\displaystyle=\frac{1}{\mathbf{N_{A}}!}\eta^{N-N_{A}}(1-\eta)^{N_{A}}{N+M-1\choose
N}^{-1}\sum_{\begin{subarray}{c}|\mathbf{N_{S}}|=N-N_{A}\\\
|\mathbf{N^{\prime}_{S}}|=N-N_{A}\end{subarray}}\frac{\sqrt{(\mathbf{N_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N_{S}}!}}\frac{\sqrt{(\mathbf{N^{\prime}_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N^{\prime}_{S}}!}}\bra{\mathbf{N^{\prime}_{S}}+\mathbf{N_{A}},\mathbf{N^{\prime}_{S}}}\ket{\mathbf{N_{S}}+\mathbf{N_{A}},\mathbf{N_{S}}}$
(55)
$\displaystyle=\frac{1}{\mathbf{N_{A}}!}\eta^{N-N_{A}}(1-\eta)^{N_{A}}{N+M-1\choose
N}^{-1}\sum_{|\mathbf{N_{S}}|=N-N_{A}}\frac{\sqrt{(\mathbf{N_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N_{S}}!}}\frac{\sqrt{(\mathbf{N_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N_{S}}!}}\bra{\mathbf{N_{S}}+\mathbf{N_{A}}}\ket{\mathbf{N_{S}}+\mathbf{N_{A}}}$
(56) $\displaystyle=\eta^{N-N_{A}}(1-\eta)^{N_{A}}{N+M-1\choose
N}^{-1}\sum_{|\mathbf{N_{S}}|=N-N_{A}}\frac{(\mathbf{N_{S}}+\mathbf{N_{A}})!}{\mathbf{N_{S}}!\mathbf{N_{A}}!}$
(57)

Thus the normalized version is:

$\displaystyle\ket{\phi_{\mathbf{N_{A}}}}$
$\displaystyle=\frac{1}{\sqrt{\innerproduct{\tilde{\phi}_{\mathbf{N_{A}}}}{\tilde{\phi}_{\mathbf{N_{A}}}}}}\ket{\tilde{\phi}_{\mathbf{N_{A}}}}$
(58) $\displaystyle=\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{{N-N_{A}+M-1\choose
N-N_{A}}}\left(\sum_{|\mathbf{N_{S}}|=N-N_{A}}\frac{(\mathbf{N_{S}}+\mathbf{N_{A}})!}{\mathbf{N_{S}}!\mathbf{N_{A}}!}\right)^{-\frac{1}{2}}\left(\mathbf{\hat{a}_{I}}^{\dagger}\right)^{\mathbf{N_{A}}}\ket{\psi_{N-N_{A}}}$
(59)

Now for the mutual inner product:

$\displaystyle\bra{\tilde{\phi}_{\mathbf{N_{A}}}}\ket{\tilde{\phi}_{\mathbf{N^{\prime}_{A}}}}$
$\displaystyle\propto\sum_{\begin{subarray}{c}|\mathbf{N_{S}}|=N-N_{A}\\\
|\mathbf{N^{\prime}_{S}}|=N-N^{\prime}_{A}\end{subarray}}\frac{\sqrt{(\mathbf{N_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N_{S}}!}}\frac{\sqrt{(\mathbf{N^{\prime}_{S}}+\mathbf{N^{\prime}_{A}})!}}{\sqrt{\mathbf{N^{\prime}_{S}}!}}\bra{\mathbf{N^{\prime}_{S}}+\mathbf{N^{\prime}_{A}},\mathbf{N^{\prime}_{S}}}\ket{\mathbf{N_{S}}+\mathbf{N_{A}},\mathbf{N_{S}}}$
(60)
$\displaystyle=\delta_{N_{A},N^{\prime}_{A}}\sum_{|\mathbf{N_{S}}|=N-N_{A}}\frac{\sqrt{(\mathbf{N_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N_{S}}!}}\frac{\sqrt{(\mathbf{N_{S}}+\mathbf{N^{\prime}_{A}})!}}{\sqrt{\mathbf{N_{S}}!}}\bra{\mathbf{N_{S}}+\mathbf{N^{\prime}_{A}}}\ket{\mathbf{N_{S}}+\mathbf{N_{A}}}$
(61) $\displaystyle=\delta_{\mathbf{N_{A}},\mathbf{N^{\prime}_{A}}}$ (62)

Therefore the states $\ket{\phi_{\mathbf{N_{A}}}}$ are mutually orthonormal
and projector is:

$\displaystyle\hat{P}$
$\displaystyle=\sum_{|\mathbf{N_{A}}|\leq{N-1}}\ket{\phi_{\mathbf{N_{A}}}}\bra{\phi_{\mathbf{N_{A}}}}$
(63)

###  V-C False Alarm Probability

$\displaystyle P_{FA}$ (64) $\displaystyle=\Tr\left[\hat{P}\rho_{abs}\right]$
(65)
$\displaystyle=\Tr\left[\left(\sum_{|\mathbf{N_{A}}|\leq{N-1}}\ket{\phi_{\mathbf{N_{A}}}}\bra{\phi_{\mathbf{N_{A}}}}\right)\left({N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{S}}|=N}\sum_{\mathbf{N_{B}}}p_{\mathbf{N_{B}}}\ket{\mathbf{N_{S}},\mathbf{N_{B}}}\bra{\mathbf{N_{S}},\mathbf{N_{B}}}\right)\right]$
(66) $\displaystyle={N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{A}}|\leq{N-1}}\sum_{|\mathbf{N_{S}}|=N}\sum_{\mathbf{N_{B}}}p_{\mathbf{N_{B}}}\left|\bra{\mathbf{N_{S}},\mathbf{N_{B}}}\ket{\phi_{\mathbf{N_{A}}}}\right|^{2}$
(67) $\displaystyle={N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{A}}|\leq{N-1}}\sum_{|\mathbf{N_{S}}|=N}\sum_{\mathbf{N_{B}}}p_{\mathbf{N_{B}}}$
$\displaystyle\qquad\qquad\qquad\qquad\left|\bra{\mathbf{N_{S}},\mathbf{N_{B}}}\frac{1}{\sqrt{\mathbf{N_{A}}!}}\sqrt{{N-N_{A}+M-1\choose
N-N_{A}}}\left(\sum_{|\mathbf{N^{\prime\prime}_{S}}|=N-N_{A}}\frac{(\mathbf{N^{\prime\prime}_{S}}+\mathbf{N_{A}})!}{\mathbf{N^{\prime\prime}_{S}}!\mathbf{N_{A}}!}\right)^{-\frac{1}{2}}\left(\mathbf{\hat{a}_{I}}^{\dagger}\right)^{\mathbf{N_{A}}}\ket{\psi_{N-N_{A}}}\right|^{2}$
(68) $\displaystyle={N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{A}}|\leq{N-1}}\sum_{|\mathbf{N_{S}}|=N}\sum_{\mathbf{N_{B}}}\frac{p_{\mathbf{N_{B}}}}{\mathbf{N_{A}}!}\left(\sum_{|\mathbf{N^{\prime\prime}_{S}}|=N-N_{A}}\frac{(\mathbf{N^{\prime\prime}_{S}}+\mathbf{N_{A}})!}{\mathbf{N^{\prime\prime}_{S}}!\mathbf{N_{A}}!}\right)^{-1}\left|\bra{\mathbf{N_{S}},\mathbf{N_{B}}}\left(\mathbf{\hat{a}_{I}}^{\dagger}\right)^{\mathbf{N_{A}}}\sum_{|\mathbf{N^{\prime}_{S}}|=N-N_{A}}\ket{\mathbf{N^{\prime}_{S}},\mathbf{N^{\prime}_{S}}}\right|^{2}$
(69) $\displaystyle={N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{A}}|\leq{N-1}}\sum_{|\mathbf{N_{S}}|=N}\sum_{\mathbf{N_{B}}}\frac{p_{\mathbf{N_{B}}}}{\mathbf{N_{A}}!}\left(\sum_{|\mathbf{N^{\prime\prime}_{S}}|=N-N_{A}}\frac{(\mathbf{N^{\prime\prime}_{S}}+\mathbf{N_{A}})!}{\mathbf{N^{\prime\prime}_{S}}!\mathbf{N_{A}}!}\right)^{-1}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left|\sum_{|\mathbf{N^{\prime}_{S}}|=N-N_{A}}\frac{\sqrt{(\mathbf{N^{\prime}_{S}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N^{\prime}_{S}}!}}\bra{\mathbf{N_{S}},\mathbf{N_{B}}}\ket{\mathbf{N^{\prime}_{S}}+\mathbf{N_{A}},\mathbf{N^{\prime}_{S}}}\right|^{2}$
(70) $\displaystyle={N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{A}}|\leq{N-1}}\sum_{|\mathbf{N_{S}}|=N}\sum_{|\mathbf{N_{B}}|=N-N_{A}}\frac{p_{\mathbf{N_{B}}}}{\mathbf{N_{A}}!}\left(\sum_{|\mathbf{N^{\prime\prime}_{S}}|=N-N_{A}}\frac{(\mathbf{N^{\prime\prime}_{S}}+\mathbf{N_{A}})!}{\mathbf{N^{\prime\prime}_{S}}!\mathbf{N_{A}}!}\right)^{-1}\left|\frac{\sqrt{(\mathbf{N_{B}}+\mathbf{N_{A}})!}}{\sqrt{\mathbf{N_{B}}!}}\bra{\mathbf{N_{S}}}\ket{\mathbf{N_{B}}+\mathbf{N_{A}}}\right|^{2}$
(71) $\displaystyle={N+M-1\choose
M-1}^{-1}\sum_{|\mathbf{N_{A}}|\leq{N-1}}\tilde{p}_{(N-N_{A})}\left(\sum_{|\mathbf{N^{\prime\prime}_{S}}|=N-N_{A}}\frac{(\mathbf{N^{\prime\prime}_{S}}+\mathbf{N_{A}})!}{\mathbf{N^{\prime\prime}_{S}}!\mathbf{N_{A}}!}\right)^{-1}\sum_{|\mathbf{N_{B}}|=N-N_{A}}\frac{(\mathbf{N_{B}}+\mathbf{N_{A}})!}{\mathbf{N_{A}}!\mathbf{N_{B}}!}$
(72) $\displaystyle={N+M-1\choose
M-1}^{-1}\sum_{N_{A}=0}^{N-1}{N-N_{A}+M-1\choose
N-N_{A}}\tilde{p}_{(N-N_{A})}$ (73)
$\displaystyle=\tilde{p}_{1}\frac{N}{N+M-1}+\tilde{p}_{2}\frac{N(N-1)}{(N+M-1)(N+M-2)}+...+\tilde{p}_{N}{M+N-1\choose
N}^{(-1)}$ (74)

###  V-D Probability of Missed Detection

$\displaystyle 1-P_{MD}$ $\displaystyle=Tr\left[\hat{P}\rho_{pres}\right]$
(75)
$\displaystyle=Tr\left[\left(\sum_{|\mathbf{N_{A}}|\leq{N-1}}\ket{\phi_{\mathbf{N_{A}}}}\bra{\phi_{\mathbf{N_{A}}}}\right)\left(\sum_{|\mathbf{N^{\prime}_{A}}|\leq
N}\ket{\tilde{\phi}_{\mathbf{N^{\prime}_{A}}}}\bra{\tilde{\phi}_{\mathbf{N^{\prime}_{A}}}}\right)\right]$
(76)
$\displaystyle=\sum_{|\mathbf{N_{A}}|\leq{N-1}}\sum_{|\mathbf{N^{\prime}_{A}}|\leq
N}\frac{1}{\innerproduct{\tilde{\phi}_{\mathbf{N_{A}}}}{\tilde{\phi}_{\mathbf{N_{A}}}}}Tr\left[\ket{\tilde{\phi}_{\mathbf{N_{A}}}}\bra{\tilde{\phi}_{\mathbf{N_{A}}}}\ket{\tilde{\phi}_{\mathbf{N^{\prime}_{A}}}}\bra{\tilde{\phi}_{\mathbf{N^{\prime}_{A}}}}\right]$
(77)
$\displaystyle=\sum_{|\mathbf{N_{A}}|\leq{N-1}}\sum_{|\mathbf{N^{\prime}_{A}}|\leq
N}\left|\bra{\tilde{\phi}_{\mathbf{N_{A}}}}\ket{\tilde{\phi}_{\mathbf{N^{\prime}_{A}}}}\right|$
(78)
$\displaystyle=\sum_{|\mathbf{N_{A}}|\leq{N-1}}\left|\bra{\tilde{\phi}_{\mathbf{N_{A}}}}\ket{\tilde{\phi}_{\mathbf{N_{A}}}}\right|$
(79)
$\displaystyle=1-\sum_{|\mathbf{N_{A}}|=N}\left|\bra{\tilde{\phi}_{\mathbf{N_{A}}}}\ket{\tilde{\phi}_{\mathbf{N_{A}}}}\right|$
(80)
$\displaystyle=1-\sum_{|\mathbf{N_{A}}|=N}\eta^{N-N}(1-\eta)^{N}{N+M-1\choose
N}^{-1}\sum_{|\mathbf{N_{S}}|=N-N}\frac{(\mathbf{N_{S}}+\mathbf{N_{A}})!}{\mathbf{N_{S}}!\mathbf{N_{A}}!}$
(81)
$\displaystyle=1-\sum_{|\mathbf{N_{A}}|=N}\eta^{0}(1-\eta)^{N}{N+M-1\choose
N}^{-1}\frac{(\mathbf{0}+\mathbf{N_{A}})!}{\mathbf{0}!\mathbf{N_{A}}!}$ (82)
$\displaystyle=1-(1-\eta)^{N}{N+M-1\choose N}^{-1}\sum_{|\mathbf{N_{A}}|=N}1$
(83) $\displaystyle=1-(1-\eta)^{N}$ (84)