aainstitutetext:  Department of Physics and State Key Laboratory of Nuclear
Physics and Technology, Peking University, Beijing, 100871,
Chinabbinstitutetext:  School of Physics, Sun Yat-Sen University, Guangzhou
510275, China

# Searching for heavy leptoquarks at a muon collider

Sitian Qian a Congqiao Li a Qiang Li a Fanqiang Meng a Jie Xiao a Tianyi Yang
b Meng Lu b and Zhengyun You<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The LHCb Collaboration recently gave an update on testing lepton flavour
universality with $B^{+}\rightarrow K^{+}\ell^{+}\ell^{-}$, in which a 3.1
standard deviations from the standard model prediction was observed. The g-2
experiment also reports a 3.3 standard deviations from the standard model on
muon anomalous magnetic moment measurement. These deviations could be
explained by introducing new particles including leptoquarks. In this paper,
we show the possibility to search for heavy spin-1 leptoquarks at a future TeV
scale muon collider by performing studies from three channels: 1) same flavour
final states with either two bottom or two light quarks, 2) different flavour
quark final states, and 3) a so-called “VXS” process representing the
scattering between a vector boson and a leptoquark to probe the coupling
between leptoquark and tau lepton. We conclude that a 3 TeV muon collider with
$3~{}$\mathrm{a}\mathrm{b}^{-1}$$ of integrated luminosity is already
sufficient to cover the leptoquark parameter space in order to explain the
LHCb lepton flavour universality anomaly.

##  1 Introduction

Lepton Flavour Universality (LFU), one of the fundamental assumptions of the
Standard Model (SM), states that the lepton family shares common properties
when interacting with gauge bosons regardless of their different masses.
However, there have been clues that LFU seems to be broken and thus leads to
the evidence of physics beyond the SM (BSM). One interesting result is that
the Muon g-2 experiment announces very recently that muon anomalous magnetic
moment has 3.3 standard deviations from SM gminus2 , which is consistent with
the previous measurement at BNL gminus2-2  and leads to a combined 4.2
standard deviations from SM. Another interesting measurement is performed on
the $R_{K}$ anomaly through rare $B$ meson decay from LHCb Collaboration Rk1 ,
where the $R_{K}$ is defined as the ratio of branching fractions:

$R_{K}=\frac{BR(B^{+}\rightarrow K^{+}\mu^{+}\mu^{+})}{BR(B^{+}\rightarrow
K^{+}e^{+}e^{+})},$ (1)

the results show an evidence of breaking of LFU at 3.1 standard deviations
from the SM.

(a) Muon $g-2$ experiment (b) LHCb B anomaly

Figure 1: LQ induced Feynman Diagrams explaining both muon anomalies

Discrepancy between SM prediction and measurement of muon anomalous magnetic
moment is against the expectation of physicists, as for the theoretical
prediction and measurement of electron magnetic moment are consistent with
each other at a precision of a part per billion gminus2-3 , which is one of
the most powerful evidence of the SM. In the other hand, there have been
several previous measurements on $R_{K}$ from LHCb Collaboration Rk2 ; Rk3 ,
the continuous measurements and consistent results draw interests on the LFU
anomaly gradually. Due to the suppress of flavour-changing neutral current,
this decay channel of $B$ meson only occurs at loop level and supposed to be
very rare rare_bdecay , which makes this channel sensitive to the potential
deviation or anomaly.

An interesting and straightforward interpretation for both the muon magnetic
and LFU anomalies is to introduce the leptoquark (LQ) LQmodel0 ; LQmodel1 ;
LQmodel2 ; LQmodel3 ; LQmodel4 ; LQmodel5 ; LQmodel6 ; LQmodel7 ; LQmodel8 ;
LQmodel9 ; LQmodel10 ; LQmodel11 ; LQmodel12 ; LQmodel13 ; LQmodel14 ;
LQmodel15 ; LQmodel16 ; LQmodel17  which couples to a lepton and a quark at
the same time. Figure. 1 shows the typical Feynman diagrams explaining how the
LQ contributions accommodate both two anomalies. Contribution to the muon
anomalous magnetic moment from LQ is discussed in detail in Ref. muong2_1 ;
muong2_2 ; muong2_3 ; muong2_4 ; muong2_5 ; muong2_6 ; muong2_7 ; muong2_8 ;
muong2_9 ; muong2_10 . The SM particle zoo welcomes LQs of different forms,
such as scalar triplet, vector singlet and vector triplet. Despite of the
representation, LQs interact with charged leptons and down-type quarks and the
strength can be described phenomenologically by the coupling matrix:

${\lambda_{\overline{Q}L}}=\begin{pmatrix}\lambda_{de}&\lambda_{d\mu}&\lambda_{d\tau}\\\
\lambda_{se}&\lambda_{s\mu}&\lambda_{s\tau}\\\
\lambda_{be}&\lambda_{b\mu}&\lambda_{b\tau}\end{pmatrix}.\vspace{0.5cm}$ (2)

While LQ from each kind of representation can explain the muon anomalies in
its own way, in this paper we will only introduce vector singlet LQs as the
complementation to SM, whose Lagrangian is formulated as Eq. (3) by following
LQ1 :

$\mathcal{L}_{\text{int}}=\left(\lambda_{\bar{Q}L}\bar{Q}_{L}\gamma_{\mu}L_{L}+\lambda_{\bar{D}E}\bar{D}_{R}\gamma_{\mu}E_{R}\right)V_{1}^{\mu}+\text{h.c.}$
(3)

here $Q_{L}$($L_{L}$) stands for left-handed SM quark(lepton) doublet, and
$D_{R}$($E_{R}$) stands for the right-handed SM down-type quark(charged
lepton) as the consequence of the absence of SM right-handed neutrino.

To explain the $R_{K}$ anomaly in the context of leptoquark models, one can
relate $R_{K}$ to LQs coupling coefficients $\lambda_{\bar{Q}L}$. Constraint
from $R_{K}$ and $R_{K}^{*}$ reads LQ1

$\frac{\lambda_{b\mu}\bar{\lambda}_{s\mu}-\lambda_{be}\bar{\lambda}_{se}}{M_{\text{LQ}}^{2}}\simeq-\frac{1\pm
0.24}{(40~{}$\mathrm{T}\mathrm{e}\mathrm{V}$)^{2}}.$ (4)

Despite that the LQ coupling with electron is also able to explain for the
$R_{K}$ anomaly, anomaly from muon flavour is more favoured by other
experimental results, for example the anomalous magnetic moment measurement
gminus2-3  and $b\to s\mu\mu$ angular distributions LQ1 . In this paper we
will only focus on coupling between LQ and $\tau$ or $\mu$ leptons. More
specifically, we are interested in the coupling matrix with the form

${\lambda_{\overline{Q}L}}=\begin{pmatrix}0&0&0\\\
0&\lambda_{s\mu}&\lambda_{s\tau}\\\
0&\lambda_{b\mu}&\lambda_{b\tau}\end{pmatrix},\vspace{0.5cm}$ (5)

where we assume couplings between LQ and the first generation lepton is zero.
Despite that the coupling for first generation quarks are set to be zero
nominally, LQs are still able to talk with $d$ quarks in the context of
Cabibbo-Kobayashi-Maskawa (CKM) mixing. An additional assumption of this paper
is that each coupling constant $\lambda_{\bar{Q}L}$ is treated as a real
number.

There are quite a lot proposals for the next generation collider for the
purpose of Higgs boson related measurements, among which the lepton colliders
are in the majority. The promising proposals include Linear or Circular
electron positron collider ILC ; FCC ; CEPC ; CLIC  and muon collider Muc0 ;
Muc1 ; Muc2 ; Muc3 ; Muc4 . Compared with the existing hadron colliders, muons
collider could be more powerful with cleaner environment. Muons can be
accelerated to much higher energy than electrons due to much less synchrotron
radiation in a circular accelerator. These advantages of muon collider and
recent muon anomalies, in addition to the assumption that LQs do not couple to
electrons, drive us to perform the LQs study at a muon collider. There are
already some interesting results of LQs searches at muon collider LQ_RK1 ;
LQ_RK2 ; LQ_RK3 , our study will be supplement to them and make it clear that
the muon collider is able to answer the question of $B$ meson rare decay
anomaly. It is a well-known fact that the challenge of a muon collider is to
provide high luminosity and high phase-space density muon beams due to the
short life time and the source of muons (produced from $\pi$-decay) Mu1 ; Mu2
. Furthermore, the beam-induced background (BIB) BIB1 ; BIB2 ; BIB3 ; BIB4 ;
BIB5 ; BIB6 ; BIB7 ; BIB8  from muon decays is also tricky to handle. However,
we assume here the advanced technique has been achieved to provide high
luminosity muon beams with high quality in the future muon collider, and the
BIB issue is also solved with advanced detector design (e.g., using timing
detector or a shielding nozzle). Our studies will be shown based on these
assumptions. We also choose moderate work condition of a benchmark muon
collider by choosing center-of-mass (C.O.M) energy
$\sqrt{s}=3~{}$\mathrm{T}\mathrm{e}\mathrm{V}$$ with integrated luminosity
$L=3~{}$\mathrm{a}\mathrm{b}^{-1}$$.

##  2 Leptoquark Search at a Muon Collider

###  2.1 Samples and cuts

The samples we used are generated using MADGRAPH5_aMC@NLO(MG5aMC) MG5 . The
BSM leptoquark model is implemented by Ref. LQ1  with FeynRules feynrules  in
the Universal FeynRules Output convention.

In MG5aMC, basic cuts on phase space are applied as Table 1 documented. Cuts
on light jet and charged leptons follows the default setting of MG5aMC. The
transverse momentum requirement of b jet is aligned with the light jet case,
while the pseudo-rapidity cut on b jet is aligned with the charged lepton as
they both need track information provided by the tracker detector.

Category | light jet | b jet | charged lepton
---|---|---|---
$p_{T}$ |  $>20$ GeV |  $>20$ GeV |  $>10$ GeV
$|\eta|$ | $<5$ | $<2.5$ | $<2.5$
Table 1: Phase space cuts used in MG5aMC calculations.

###  2.2 Di-jet Final State

At a muon collider, the simplest processes involving LQs would be the di-jet
final states in which LQs show up in $t$-channel and lead to the muon-quark
conversion of incoming muons (Fig. 2a & 2b). The di-jet in the final states
can be either different flavour or same flavour, while the later one will
interfere with the SM $s$-channel di-jet production (Fig. 2c).

(a) Different Flavour $t$-channel Di-jet Final State (b) Same Flavour
$t$-channel Di-jet Final State

(c) SM $s$-channel Di-jet Production

Figure 2: Di-jet production mechanism at a muon collider with Leptoquarks.

Those $t$-channel processes can be classified into three categories as shown
in Table 2, where “light (jet)” stands for jet originating from Matrix Element
(ME) level $u/d/c/s/g$ partons. The cross section dependence on the BSM
coupling strength of different flavour final state is simple since there is no
such SM contribution, as shown in Table. 2. The situation for same flavour
final state is complicated due to the interference between BSM signal and SM
$s$-channel process, as shown in Fig. 3a, and we can also find the obvious
destructive interference between SM $s$-channel background and LQ $t$channel
signal.

Category | SM $s$-channel Interference | Cross Section Dependence
---|---|---
light+$b$ | No | $|\lambda_{s\mu}\bar{\lambda}^{b\mu}|^{2}$
light+light | Yes | Complicated
$b$ \+ $b$ | Yes | Complicated
Table 2: LQ search strategy through the di-jet processes.

####  2.2.1 Same Flavour Final State

To determine the LQ coupling strengths exclusively, we start with the same
flavour final states. In Ref. LQ_RK2  the authors discuss same flavour dijet
state in detail however mainly focusing on $b+b$ flavour. As the $B$ meson
rare decay anomaly requires non-zero product between the quark-LQ-muon
coupling constants of $b$ and $s$ flavour, specialized flavour assumptions are
needed to translate di-bjet limits to di-light jet limit in that case. In our
study, we will perform analysis on both $b+b$ and light+light final states
thus leads to a direct comparison between our results and the B meson anomaly
measurement.

The same flavour di-jet events are generated considering the interference
between BSM signal and SM $s$-channel background. In Fig. 3 we use the $b+b$
final state for illustration while the light+light final state shares a
similar behaviour. Please note that the rapid growing of cross section is
caused by so-called unitarity violation (UV), which is a compromise on
allowing LQs couple to all lepton generations as discussed in Ref. LQ1 .
Figure. 3b shows the shape comparison of $|\eta_{b}|$ distribution with
$|\lambda_{b\mu}|=2$, while all the shapes are normalized to cross section of
SM value. The shape of $|\eta_{b}|$ is used for statistic analysis and ten
bins are used in the range of (0, 2.5), while the yields are estimated using
the corresponding cross section at 3 TeV C.O.M energy with integrated
luminosity $3~{}$\mathrm{a}\mathrm{b}^{-1}$$.

(a) Cross section dependence on $|\lambda_{b\mu}|$ for a 1 and 10 TeV LQ,
respectively.  (b) Shape comparison on $|\eta_{b}|$ distribution for the SM,
and the LQ cases with $|\lambda_{b\mu}|=2$

Figure 3: Effects of a 1 TeV and 10 TeV leptoquark in the $b+b$ di-jet
process.

We apply the same analysis strategy for both $b+b$ final state and light+light
final states. Apart from the $s+s$ final state events, s+d and d+d final
states can still appear after setting $\lambda_{d\mu}$ to zero due to CKM
mixing. However, as our light jet definition includes all $u/d/s/c$ quarks,
the total expected yields of light+light final state will only depend on the
$\lambda_{s\mu}$ deterministically and thus can be handled consistently once
the strength of CKM mixing is fixed. In our study, we assume the LQs couple
with the SM weak eigenstate of down-type quarks, thus the CKM mixing is set to
the SM Cabibbo angle.

Though our analysis is performed at parton level, we introduce jet flavour
identification efficiency mimicking the jet tagging techniques btag  in CMS in
order to obtain realistic results. The jet flavour tagging efficiencies we
used are listed in Table 3. We should keep in mind that the benchmark
efficiency we choose is at moderate transverse momentum of jets, and can be
improved up to TeV scale using e.g. the machine learning technique btag ;
btag_deep ; btag_atlas ; btag_mux  and may be further improved at the muon
collider (one may also rely on di-jet + QED/QCD emission processes to lower
down the momenta of final state jets). Currently the jet tagging techniques
for muon colliders are in a preliminary stage muon_btag_1 ; muon_btag_2 ;
muon_btag_3  and the methodology on reconstructing the secondary vertex is the
same as the hadron collider ones. Thus, hadron collider tagging efficiencies
can be viewed as a solid baseline. Although there could be “fake” background
from mis-tagged di-jet events, we neglect its contribution since it is
negligible compared with the dominant contribution from SM $s$-channel
background. We use the statistics $Z$ defined in Eq. 6 for both 95% CL
exclusion limit and 5$\sigma$ discovery limit, where $b$ is the SM background,
$n:=s+b$ is the total yields containing both signal and background, $s$ is the
BSM signal. Both $Z$ statistics subject to $\chi^{2}$ distribution with 10
degree of freedom corresponding to 10 bins asymptotic . Results are summarized
and plotted in Fig. 4 for both final states.

$\displaystyle Z=\sum_{i=1}^{10}Z_{i}$ (6)
$\displaystyle\begin{cases}Z_{i}:=\left[n_{i}-b_{i}+b_{i}\ln(b_{i}/n_{i})\right]&\text{95\%
CL Exclusion}\\\
Z_{i}:=\left[b_{i}-n_{i}+n_{i}\ln(n_{i}/b_{i})\right]&\text{$5\sigma$
Discovery}\end{cases}$

(a) $b+b$ final state (b) light + light final state

Figure 4: 95% CL exclusion line (dashed) and 5$\sigma$ discovery limit (solid)
against different vector singlet LQ mass values.

Treating the $b+b$ and light $+$ light final state as different measurement
and combining the p-values with the so-called Fisher method fisher , we can
obtain the corresponding 2d 95% CL exclusion contour as Fig. 5 shows. Last but
not least, the resulting limits on LQ couplings $\lambda_{ql}$ are relatively
small compared with those values resulting in very high cross sections (which
may be close to UV) in Figure 3a, thus the results are safe even with a UV
incomplete BSM LQ model.

Flavour | Tagged as light | Tagged as $b$
---|---|---
light | 0.9 | 0.01
$b$ | 0.1 | 0.7
Table 3: Flavour tagging efficiencies used in this analysis.

(a) 1 TeV LQ combined results (b) 10 TeV LQ combined results

Figure 5: 95% CL exclusion contour line on the
$|\lambda_{b\mu}|-|\lambda_{s\mu}|$ plane. Upper right portion of the dashed
blue line is the exclusion region.

####  2.2.2 Different Flavour Final State

Among all possible $t$-channel di-jet states, the different flavour channel is
an appealing choice for LQ search as there is no such process within SM due to
the fact that processes with different flavour di-jet violate the conservation
law on quark numbers. In Ref LQ_RK1 , the authors discuss a similar final
state via introducing a scalar leptoquark, however with $b+s$ final states
only without concerning the potential CKM mixing.

The ME cross section of such BSM process will proportional to the product of
coupling constants associated with two muon-LQ-quark vertices as shown in Fig.
2a. The corresponding cross section reads

$\sigma_{\text{DF}}(\mu^{+}\mu^{-}\to
jj)\propto|\lambda_{s\mu}\bar{\lambda}^{b\mu}|^{2}$ (7)

as described in Table 2, where DF means “Different Flavour”. However, the
different flavour channel is not background free as there can be “fake”
contributions originating from jet mis-tag, e.g., one b jet is identified as a
light jet in a di-bjet event or vice versa.

We set up the statistic analysis using event counting method to estimate the
limits of coupling strengths at 95% CL as well as the 5$\sigma$ discovery of
BSM signal. For each coupling strength, we calculate the corresponding signal
and background yields, and construct the corresponding $Z$ statistics for each
case following Eq. 8. The $Z$ statistic subjects to a $\chi^{2}$ distribution
with 1 degree of freedom asymptotic .

$\begin{cases}Z:=\left[n-b+b\ln(b/n)\right]&\text{for 95\% CL Exclusion}\\\
Z:=\left[b-n+n\ln(n/b)\right]&\text{for $5\sigma$ Discovery}\end{cases}$ (8)

Estimation of signal yield is achieved by scaling cross section against
coupling constants and multiplied by target luminosity
$L=3~{}$\mathrm{a}\mathrm{b}^{-1}$$. With
$\sqrt{s}=3~{}$\mathrm{T}\mathrm{e}\mathrm{V}$$ and
$\lambda_{s\mu}=\lambda_{b\mu}=0.1$, the BSM signal cross section calculated
using MG5aMC is $2.884~{}$\mathrm{f}\mathrm{b}$$ when LQ mass is
$1~{}$\mathrm{T}\mathrm{e}\mathrm{V}$$. For background estimation, we always
use the SM yields as a good approximation. The SM $s$-channel cross sections
are $10.03~{}$\mathrm{f}\mathrm{b}$$ for $b\bar{b}$ final state and
$59.63~{}$\mathrm{f}\mathrm{b}$$ for two light jet case. Cross sections are
defined within the phase space subject to kinematics region shown in Table 1.

Figure 6: 95% CL exclusion (dashed) and 5$\sigma$ discovery limit (solid) from
the different flavor jet analysis on $|\lambda_{s\mu}\bar{\lambda}_{b\mu}|$ is
shown against masses of vector singlet LQ. The 2$\sigma$ parameter space
favored by a fit of B anomalies LQ1  is shown as the yellow band. Exclusion
line (dash-dotted) from the same flavour analysis is also shown, by combining
directly b+b and light+light results.

The 95% CL exclusion line as well as 5$\sigma$ discovery limit for various LQ
mass are plotted in Fig. 6. We can find that for a muon collider with
$3~{}$\mathrm{T}\mathrm{e}\mathrm{V}$$ C.O.M and
$3~{}$\mathrm{a}\mathrm{b}^{-1}$$ integrated luminosity, such DF final state
can approach the phase space allowed by the $B$ meson rare decay anomaly, even
exclude some region with heavy LQ case. The aqua dash-dotted line is obtained
via multiplying the corresponding value from the SF results, which exclude all
the allowed phase space needed for the $B$ anomaly in a large range of LQ
mass.

###  2.3 Di-jet+di-lepton Final State: di-bjet + $\mu$ \+ $\tau$ as an example

Thinking about the recent results on muon $g-2$ and anomaly of LFU, should we
regard muon as the special one among all the charged leptons, or we could also
consider that the lepton flavour violations could follow the mass pattern
$3^{rd}>2^{nd}>1^{st}$ generation? Moreover, we have studied LQ coupling
across quark generations, should we have a similar trial on comparing
different lepton generations? Triggered by this idea, we start to investigate
the simultaneous study on LQ-$\tau$ and LQ-$\mu$ couplings.

At a muon collider, the leading contribution involving $\tau$ leptons in the
final states is however not as simple as the di-jet cases. Processes including
$\tau$-LQ-quark vertex can not be directly realized like the $\mu$-LQ-quark
vertex which can be related to the incoming muons. Instead of a simple $2\to
2$ process, we choose $2\to 4$ processes containing two electroweak vertices
and two LQ vertices with the order of
$(\alpha_{EW}^{2}\cdot\lambda_{q_{1}l_{1}}\cdot\lambda_{q_{2}l_{2}})$, in
which one type of process is the scattering between LQ and vector boson.
Similar leptoquark involved processes with 2 jet + 2 charged lepton in the
final state at muon collider is also discussed in Ref. LQ_RK2 ; LQ_RK3 .
However, they mainly focus on the final states with two same flavour muons
(taus) and two $b$ jets, which has interference with SM processes. Since this
$2\to 4$ process has similar topology with vector boson scattering (VBS), we
call this kind of process “VXS”. Typical Feynman diagrams are summarized as
Fig. 7, in which both LQ pair production (Fig. 7a) and single production via
fusion (Fig. 7c) contain the LQ-$Z/\gamma$-LQ vertex regarded as a electroweak
vertex with order $\alpha_{EW}$. The leading contribution comes from the pair
production and single production due to the $s$-channel resonance structure
for a light leptoquark within the setup of interest
($\sqrt{s}\sim\mathcal{O}(\text{TeV}),m_{\text{LQ}}\sim\mathcal{O}(1\sim
10~{}$\mathrm{T}\mathrm{e}\mathrm{V}$)$). The “VXS” process will dominate the
production gradually as LQ getting heavier compared with the C.O.M energy.

(a) LQ Pair Production (b) LQ Single Production via Radiation

(c) LQ Single Production via Fusion (d) LQ and Vector Boson Scattering

Figure 7: LQ involved $2\to 4$ processes at a muon collider, with a $\tau$ in
the final states.

The final states with one $\tau$ and one $\mu$ are used in order to have the
LQ-$\tau$ and LQ-$\mu$ couplings at the same time, and the jets are required
to be bottom flavour (similar when requiring two same flavour light jets or
two different flavour jets). The complete reconstruction of $\tau$ is not
possible in the leptonic decay channel due to the existence of neutrino, so we
require the $\tau$ in the final state decays hadronically, while the
reconstruction of hadronic decay $\tau$ have been studied well in Ref.
tau_reco . The hadronic decay branching fraction of $\tau$ is from PDG and is
applied on the BSM signal process to estimate the yields. The cross section of
BSM ($\tau\mu$bb) has a quadratic dependence on the product between
$\lambda_{b\mu}$ and $\lambda_{b\tau}$ as Eq. 9 shows.

$\sigma(\mu^{+}\mu^{-}\to\tau\mu
bb)\propto|\lambda_{b\mu}\bar{\lambda}^{b\tau}|^{2}$ (9)

Similar with different flavour di-jet final state, the di-jet+di-lepton final
state have no SM background at ME level due to the violation of lepton number.
However, there could be “fake” backgrounds from objects mis-identification,
e.g., jet is mis-identificated as $\mu$ or $\tau$. We applied jet flavour
tagging efficiencies as Table 3 documented, and the hadronic $\tau$
identification efficiency is chosen from the performance of the CMS detector.
The mis-tagging rates are both $\sim 1\%$ from CEPC detector simulation
cepc_reco  and CMS estimation tau_reco .

We use $\lambda_{b\mu}=\lambda_{b\tau}=0.1$ and
$m_{LQ}=1~{}$\mathrm{T}\mathrm{e}\mathrm{V}$$ as the benchmark setup, the
corresponding cross section is $2.504~{}$\mathrm{f}\mathrm{b}$$ for
$\sqrt{s}=3~{}$\mathrm{T}\mathrm{e}\mathrm{V}$$ within the phase space shown
in Table 1. With the similar counting analysis strategy introduced for the
different flavour di-jet cases, we construct $Z$ statistics as defined in Eq.
8. The 95% CL exclusion line as well as 5$\sigma$ discovery limit are reported
in Fig. 8b.

(a) Cross section under benchmark LQ coupling at 3 TeV C.O.M  (b)
Corresponding Limits for di-lepton + di-bjet Case

Figure 8: (Left) Cross section dependence on LQ masses of the di-bjet and di-
lepton processes, and the corresponding dominate sub-processes. (Right) 95% CL
exclusion line (dashed) and 5$\sigma$ discovery limit (solid) against LQ
masses.

##  3 Conclusion

In this paper, we show the possibility to search for heavy leptoquarks at a
muon collider through three channels: 1) same flavour di-jet, 2) different
flavour di-jet and 3) di-jet+di-lepton final states. The leptoquark we focus
on is a vector singlet, which is one kind of leptoquarks could explain the
muon (g-2) anomaly and $B$ meson rare decay anomaly. We neglect the coupling
between leptoquark and electron, and require that leptoquarks can only couple
to down-type quarks. Under the benchmark conditions that the center-of-mass at
3 TeV and integrated luminosity $3~{}$\mathrm{a}\mathrm{b}^{-1}$$, we obtain
the limits on $\lambda_{b\mu}$, $\lambda_{s\mu}$ and combined limit of them at
different mass of leptoquark. The results show that a muon collider under the
benchmark condition is capable of answering the question from $B$ meson rare
decay anomaly. Besides the study on the coupling between leptoquark and $\mu$,
we also show the ability of a muon collider to investigate the coupling
between leptoquark and $\tau$, which enables us to understand whether the
possible lepton flavour universality violation follow the mass pattern of
charged leptons.

###### Acknowledgements.

This work is supported in part by the National Natural Science Foundation of
China under Grant No. 12075004, by MOST under grant No. 2018YFA0403900.

## References

  * (1) B. Abiet et al. [Muon g-2 Collaboration], “Measurement of the Positive Muon Anomalous Magnetic Momentto 0.46 ppm,” Phys. Rev. Lett.126(2021) no.14, 141801 [arXiv:2104.03281 [hep-ex]]
  * (2) G. W. Bennett et al. [Muon g-2 Collaboration], “Final report of the muon E821 anomalous magnetic moment measurement at BNL,” Phys. Rev. D 73, 072003 (2006)
  * (3) R. Aaijet et al. [LHCb], “Test of lepton universality in beauty-quark decays,” [arXiv:2103.11769 [hep-ex]]
  * (4) D. Hanneke, S. Fogwell, and G. Gabrielse, “New Measurement of the Electron Magnetic Moment and the Fine Structure Constant,” Phys. Rev. Lett. 100, 120801 (2008).
  * (5) R. Aaijet et al. [LHCb], “Test of lepton universality with $B^{0}\rightarrow K^{*0}l^{+}l^{-}$ decays,” J. High Energ. Phys. 08, 055 (2017) [arXiv:1705.05802 [hep-ex]]
  * (6) R. Aaijet et al. [LHCb], “Search for lepton-universality violation in $B^{+}\rightarrow K^{+}l^{+}l^{-}$ decays,” Phys. Rev. Lett. 122, 191801 (2019) [arXiv:1903.09252 [hep-ex]]
  * (7) Particle Data Group, P. A. Zyla et al. “Review of particle physics,” Prog. Theor. Exp. Phys. 2020 (2020) 083C01
  * (8) J. Blumlein and R. Ruckl. “Production of scalar and vector leptoquarks in e+ e- annihilation,” Phys. Lett. B 304 (1993) 337-346
  * (9) O. Popov, M. A. Schmidt and G. White. “$R_{2}$ as a single leptoquark solution to $R_{D^{(*)}}$ and $R_{K^{(*)}}$,” Phys. Rev. D, 100, 035028 (2019)
  * (10) G. D’Amico et al. “Flavour anomalies after the $R_{K^{*}}$ measurement,” J. High Energ. Phys. 09, 010 (2017)
  * (11) A. Angelescu et al. “On the single leptoquark solution to the $B$-physics anomalies,” [arXiv:2103.12504 [hep-ph]]
  * (12) G. Hiller and I. Nisandzic. “$R_{K}$ and $R_{K^{*}}$ beyond the Standard Model,” Phys. Rev. D, 96, 035003 (2017)
  * (13) D. Becirevic and O. Sumensari. “A leptoquark model to accommodate $R_{K}^{exp}<R_{K}^{SM}$ and $R_{K^{*}}^{exp}<R_{K^{*}}^{SM}$,” J. High Energ. Phys. 08, 104 (2017)
  * (14) I. Bigaran, J. Gargalionis and RR. Volkas. “A near-minimal leptoquark model for reconciling flavour anomalies and generating radiative neutrino masses,” J. High Energ. Phys. 10, 106 (2019)
  * (15) S.Saad. “Combined explanations of $(g-2)_{\mu}$, $R_{D^{(*)}}$, $R_{K^{(*)}}$ anomalies in a two-loop radiative neutrino mass model,” Phys.Rev.D 102 (2020) 1, 015019
  * (16) L. Calibbi, A. Crivellin and T. Li. “Model of vector leptoquarks in view of the $B$-physics anomalies,” Phys.Rev.D 98 (2018) 11, 115002
  * (17) M. Blanke and A. Crivellin. “$B$ Meson Anomalies in a Pati-Salam Model within the Randall-Sundrum Background,” Phys.Rev.Lett. 121 (2018) 1, 011801
  * (18) A. Crivellin, D. Müller and T. Ota. “Simultaneous explanation of R(D(∗)) and b $\rightarrow$ s$\mu^{+}\mu^{-}$: the last scalar leptoquarks standing,” JHEP 09 (2017) 040
  * (19) A. Crivellin, D. Müller and F. Saturnino. “Flavor Phenomenology of the Leptoquark Singlet-Triplet Model,” JHEP 06 (2020) 020
  * (20) P. Bandyopadhyay and R. Mandal. “Revisiting scalar leptoquark at the LHC,” Eur. Phys. J. C 78, 491 (2018). https://doi.org/10.1140/epjc/s10052-018-5959-x
  * (21) P. Bandyopadhyay, S. Dutta and A. Karan. “Investigating the production of leptoquarks by means of zeros of amplitude at photon electron collider,” Eur. Phys. J. C 80, 573 (2020). https://doi.org/10.1140/epjc/s10052-020-8083-7
  * (22) P. Bandyopadhyay, S. Dutta and A. Karan. “Zeros of amplitude in the associated production of photon and leptoquark at $e-p$ collider,” Eur. Phys. J. C 81, 315 (2021). https://doi.org/10.1140/epjc/s10052-021-09090-z
  * (23) P. Bandyopadhyay et al. “Distinguishing Leptoquarks at the LHC/FCC,” Nuclear Physics B, 971 (2021), https://doi.org/10.1016/j.nuclphysb.2021.115524
  * (24) W. Yin. “Radiative lepton mass and muon $g-2$ with suppressed lepton flavor and CP violations,” JHEP 08 (2021) 043
  * (25) K. S. Babu et al. “Unified Framework for $B$-Anomalies, Muon $g-2$, and Neutrino Masses,” JHEP 03 (2021) 179
  * (26) G. Couture and H. Konig. “Bounds on second generation scalar leptoquarks from the anomalous magnetic moment of the muon,” Phys. Rev. D, 53 (1996), pp. 555-557, 10.1103/PhysRevD.53.555
  * (27) K.-m. Cheung. “Muon anomalous magnetic moment and leptoquark solutions,” Phys. Rev. D, 64 (2001), Article 033001, 10.1103/PhysRevD.64.033001
  * (28) U. Mahanta. “Implications of BNL measurement of delta a(mu) on a class of scalar leptoquark interactions,” Eur. Phys. J. C, 21 (2001), pp. 171-173, 10.1007/s100520100705
  * (29) I. Doršner et al. “$\mu\rightarrow e\gamma$ selecting scalar leptoquark solutions for the $(g-2)_{e,\mu}$ puzzles,” Phys.Rev.D 102 (2020) 7, 075007
  * (30) E. C. Leskow et al. “$(g-2)\mu$, lepton flavor violation, and $Z$ decays with leptoquarks: Correlations and future prospects,” Phys.Rev.D 95 (2017) 5, 055018
  * (31) A. Crivellin, D. Mueller and F. Saturnino. “Correlating h $\rightarrow\mu^{+}\mu^{-}$ to the Anomalous Magnetic Moment of the Muon via Leptoquarks,” Phys.Rev.Lett. 127 (2021) 2, 021801
  * (32) W. Yin and M. Yamaguchi. “Muon $g-2$ at multi-TeV muon collider,” [arXiv:2012.03928 [hep-ph]]
  * (33) M. Davier, A. Hoecker, B. Malaescu et al. “Reevaluation of the hadronic contributions to the muon $g-2$ and to $\alpha(M^{2}_{Z})$,” Eur. Phys. J. C 71, 1515 (2011)
  * (34) M. Davier, A. Hoecker, B. Malaescu et al. “Reevaluation of the hadronic vacuum polarisation contributions to the Standard Model predictions of the muon $g-2$ and $\alpha(M^{2}_{Z})$ using newest hadronic cross-section data,” Eur. Phys. J. C 77, 827 (2017)
  * (35) M. Davier, A. Hoecker, B. Malaescu et al. “A new evaluation of the hadronic vacuum polarisation contributions to the muon anomalous magnetic moment and to ${\alpha}({{m}}_{{Z}}^{2})$,” Eur. Phys. J. C 80, 241 (2020)
  * (36) Hiller, G. et al. “Flavorful leptoquarks at the LHC and beyond: spin 1.” J. High Energ. Phys. 06, 80 (2021). https://doi.org/10.1007/JHEP06(2021)080
  * (37) T. Behnke et al. [arXiv:1306.6327 [physics.acc-ph]]
  * (38) CERN FCC web site, http://fcc.web.cern.ch
  * (39) CEPC Study Group, CEPC Conceptual Design Report, arXiv:1809.00285[physics.acc-ph]
  * (40) Compact Linear Collider (CLIC), http://clic.cern/
  * (41) C. M. Ankenbrandt et al. “Status of Muon Collider Research and Development and Future Plans,” Phys.Rev.ST Accel.Beams 2:081001,1999
  * (42) R. B. Palmer, “Muon Colliders,” Rev. Accel. Sci. Tech. 7 (2014) 137-159
  * (43) M-H. Wang et al. “Design of a 6 TeV muon collider,” JINST 11 (2016) P09003
  * (44) D. Neuffer, V. Shiltsev, “On The Feasibility of a Pulsed 14 TeV c.m.e. Muon Collider in the LHC Tunnel,” JINST 13 (2018) T10003
  * (45) J. P. Delahaye, M. Diemoz, K. Long et al. “Muon colliders,” 2019, http://arxiv.org/abs/1901.06150
  * (46) G. Huang et al. “Probing the $R_{K}^{(*)}$ Anomaly at a Muon Collider,” arXiv:2103.01617 [hep-ph]
  * (47) P. Asadi et al. “Searching for Leptoquarks at Future Muon Colliders,” arXiv:2104.05720 [hep-ph]
  * (48) P. Bandyopadhyay, A. Karan and R. Mandal. “Distinguishing signatures of scalar leptoquarks at hadron and muon colliders,” arXiv:2108.06506[hep-ph]
  * (49) Daniel Schulte et al. “Muon Collider. A Path to the Future?” PoS EPS-HEP2019, 004 (2020), doi:10.22323/1.364.0004
  * (50) D. Neuffer, “Principles and Applications of Muon Cooling,” Part. Accel. 14, 75-90 (1983), doi:10.2172/1156195
  * (51) M. A. C. Cummings et al. “G4beamline and MARS Comparison for Muon Collider Backgrounds,” Conf. Proc. C 110328 (2011) 2297-2299
  * (52) S. A. Kahn et al. “Beam Induced Detector Backgrounds at a Muon Collider,” Conf. Proc. C 110328 (2011) 2300-2302.
  * (53) N. V. Mokhov and S. I. Striganov, “Detector Background at Muon Colliders,” Phys. Procedia 37 (2012) 2015-2022
  * (54) N. V. Mokhov, S. I. Striganov, and I. S. Tropin, “Reducing Backgrounds in the Higgs Factory Muon Collider Detector,” in 5th International Particle Accelerator Conference, pp. 1081-1083. 6, 2014. arXiv:1409.1939 [physics.ins-det]
  * (55) V. Di Benedetto et al. “A Study of Muon Collider Background Rejection Criteria in Silicon Vertex and Tracker Detectors,” JINST 13 (2018) P09004
  * (56) N. Bartosik et al. “Preliminary Report on the Study of Beam-Induced Background Effects at a Muon Collider,” arXiv:1905.03725 [hep-ex]
  * (57) N. Bartosik et al. “Detector and Physics Performance at a Muon Collider,” JINST 15 no. 05, (2020) P05001
  * (58) D. Lucchesi et al. “Detector Performances Studies at Muon Collider,” PoS EPS-HEP2019 (2020) 118
  * (59) J. Alwall et al. “The automated computation of tree-level and next-to-leading order differential cross sections, and their matching to parton shower simulations,” J. High Energ. Phys. 07, 079 (2014)
  * (60) A. Alloul et al. “FeynRules 2.0 - A complete toolbox for tree-level phenomenology,” Comput. Phys. Commun. 185, 2250-2300 (2014), doi:10.1016/j.cpc.2014.04.012 [arXiv:1310.1921 [hep-ph]]
  * (61) CMS Collaboration, “Jet flavour classification using DeepJet,” JINST 15 (2020) P12012
  * (62) E. Bols et al. , “Identification of heavy-flavour jets with the CMS detector in pp collisions at 13 TeV,” JINST 13 (2018) P05011
  * (63) M. Paganini and on behalf of the ATLAS Collaboration, “Machine Learning Algorithms for b-Jet Tagging at the ATLAS Experiment,” J. Phys.: Conf. Ser. 1085 042031, doi: 10.1088/1742-6596/1085/4/042031
  * (64) Z.Sullivan and K. Pedersen1. “Flavor tagging TeV jets for physics beyond the Standard Model,” EPJ Web of Conferences 120, 03001 (2016), doi: 10.1051/epjconf/201612003001
  * (65) G. Cowan, K. Cranmer, E. Gross et al. “Asymptotic formulae for likelihood-based tests of new physics,” Eur. Phys. J. C 73, 2501 (2013)
  * (66) Mosteller, Frederick, and R. A. Fisher. “Questions and Answers.” The American Statistician, vol. 2, no. 5, 1948, pp. 30-31
  * (67) Sirunyan, A. M. et al. “Performance of reconstruction and identification of $\tau$ leptons decaying to hadrons and $\nu_{\tau}$ in pp collisions at $\sqrt{s}=$ 13 TeV,” JINST 13 (2018) P10005
  * (68) CEPC Study Group, “CEPC Conceptual Design Report: Volume 2 - Physics & Detector,” arXiv:1811.10545[hep-ex]
  * (69) V. Di Benedetto et al., J. Inst. 13, P09004 (2018).
  * (70) N. Bartosik et al., J. Inst. 15, P05001 (2020).
  * (71) B. J. King, The workshop on physics at the first muon collider and at the front end of a muon collider 621 (1998).


$3,5$ | $4$ | yes, $6$ steps | $90$ | $75$ | $\boldsymbol{95\,\mathrm{ms}}$ | $1.2\,\mathrm{s}$
$15,17$ | $10$ | yes, $18$ steps | $258$ | $195$ | $\boldsymbol{220\,\mathrm{ms}}$ | $36\,\mathrm{s}$
$57,73$ | $51$ | yes, $92$ steps | $1294$ | $935$ | $\boldsymbol{1.7\,\mathrm{s}}$ | $>1\,\mathrm{h}$
$9,12$ | $4$ | no | $106$ | $74$ | $\boldsymbol{130\,\mathrm{ms}}$ | $1.8\,\mathrm{s}$
$10,16$ | $5$ | no | $190$ | $134$ | $\boldsymbol{140\,\mathrm{ms}}$ | $11\,\mathrm{s}$
$8,14,17$ | $2$ | yes, $4$ steps | $411$ | $642$ | $\boldsymbol{300\,\mathrm{ms}}$ | $26\,\mathrm{s}$
$14,26,27$ | $14$ | yes, $15$ steps | $21635$ | $15279$ | $\boldsymbol{7.7\,\mathrm{s}}$ | $>1\,\mathrm{h}$
$12,15,18$ | $10$ | no | $2391$ | $1442$ | $\boldsymbol{550\,\mathrm{ms}}$ | $20\,\mathrm{min}$
$12,21,27$ | $8$ | no | $4029$ | $2444$ | $\boldsymbol{1.0\,\mathrm{s}}$ | $88\,\mathrm{min}$

Table 1 presents the results for this benchmark. The original puzzle with
$n=[3,5]$ and $m=4$ is included in the first line. Additionally, we randomly
selected eight parameter sets such that we consider four scenarios involving 2
buckets and four scenarios involving 3 buckets.

We indicate in each scenario whether the puzzle is solvable, and in the
positive case, how many steps a minimal solution has. We compare the time to
check the reachability of a goal state (fireability of the $\mathit{goal}$
transition, cp. above) of the low-level and symbolic approach. The faster
approach is highlighted with bold font. Additionally, we notate the number of
conditions ($|B|$) and events ($|E|$) of the generated prefix. Each of these
two numbers coincides between the two approaches.

When we pick the parameters at random the low-level approach generally is much
faster. We can, however, construct examples in which the symbolic approach
outspeeds the low-level approach. In these constructed cases we have a large
color domain but can reach the goal quite quickly, e.g., with two buckets of
capacity $10^{6}$ and $10^{6}+1$, and a target of $m=1$.

##### Hobbits And Orcs.

For the Hobbits And Orcs benchmark we vary the and the capacity $n$ of the
boat fixed in Figures 10(a), 10(b), 10(c), and number the of each Hobbits and
Orcs, $m$, plotted on the x-axis. We indicate the time needed by the low-level
approach in blue and by the symbolic approach in orange, with a timeout of 3
minutes.

(a) $n=2$

(b) $n=4$

(c) $n=6$

Figure 10:  Results for Hobbits And Orcs problem for a fixed boat capacity $n$
in 10(a), 10(b), 10(c), and population with $m$ of each Hobbits and Orcs on
the x-axis. The orange line shows the time needed by the symbolic approach and
the blue line shows the low-level approach.

We find that the low-level approach performs better when the boat capacity is
smaller. For $n=2$, the symbolic approach gets a timeout at $m=13$ while the
low-level approach can calculate the prefix up to $m=33$. We expected this
behavior, because a smaller the boat capacity yields a higher degree of mode
determinism in the net. When the capacity increases, the net is ‘less’ mode
deterministic. For $n\geq 6$ the symbolic approach is faster for all
population sizes. Independent of the boat size $n$, both approaches take
exponentially more time with growing population size.

##### Mastermind.

We present some results for the Mastermind benchmark in Table 2. We compare
the time needed by the low-level and symbolic approach to generate the
unfolding, with a timeout of two minutes. The table also shows the number of
nodes (conditions $|\mathsf{B}|$ resp. $|B|$, and events $|\mathsf{E}|$ resp.
$|E|$) in the unfolding. In each row the faster time is highlighted in bold
font.

Table 2: Results of the Mastermind benchmark. |  |  |  c |  c
---|---|---|---|---
$k$ | $n$ | $m$ | time | $|\mathsf{B}|$ | $|\mathsf{E}|$ | time | $|B|$ | $|E|$
$12$ | $4$ | $6$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{1\,\mathrm{min}}$ | $149$ | $36$
$1$ | $3$ | $3$ | $86\,\mathrm{ms}$ | $219$ | $48$ | $\boldsymbol{62\,\mathrm{ms}}$ | $14$ | $3$
$1$ | $3$ | $5$ | $1.8\,\mathrm{s}$ | $18363$ | $3720$ | $\boldsymbol{54\,\mathrm{ms}}$ | $14$ | $3$
$1$ | $3$ | $6$ | $18\,\mathrm{s}$ | $72723$ | $14640$ | $\boldsymbol{61\,\mathrm{ms}}$ | $14$ | $3$
$1$ | $3$ | $7$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{54\,\mathrm{ms}}$ | $14$ | $3$
$1$ | $3$ | $1000$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{53\,\mathrm{ms}}$ | $14$ | $3$
$1$ | $4$ | $4$ | $1\,\mathrm{s}$ | $3651$ | $624$ | $\boldsymbol{60\,\mathrm{ms}}$ | $17$ | $3$
$1$ | $4$ | $5$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{67\,\mathrm{ms}}$ | $17$ | $3$
$1$ | $5$ | $1000$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{77\,\mathrm{ms}}$ | $20$ | $3$
$1$ | $28$ | $1000$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{1\,\mathrm{s}}$ | $89$ | $3$
$2$ | $3$ | $3$ | $215\,\mathrm{ms}$ | $1719$ | $438$ | $\boldsymbol{206\,\mathrm{ms}}$ | $24$ | $6$
$2$ | $3$ | $4$ | $3.3\,\mathrm{s}$ | $110115$ | $27672$ | $\boldsymbol{120\,\mathrm{ms}}$ | $24$ | $6$
$2$ | $3$ | $5$ | $111\,\mathrm{s}$ | $1726443$ | $432060$ | $\boldsymbol{124\,\mathrm{ms}}$ | $24$ | $6$
$2$ | $3$ | $6$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{119\,\mathrm{ms}}$ | $24$ | $6$
$2$ | $3$ | $1000$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{127\,\mathrm{ms}}$ | $29$ | $6$
$2$ | $4$ | $4$ | $5.5\,\mathrm{s}$ | $137235$ | $27672$ | $\boldsymbol{1.3\,\mathrm{s}}$ | $29$ | $6$
$2$ | $4$ | $5$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{116\,\mathrm{ms}}$ | $29$ | $6$
$2$ | $4$ | $1000$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{162\,\mathrm{ms}}$ | $29$ | $6$
$2$ | $10$ | $1000$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{1\,\mathrm{s}}$ | $59$ | $6$
$3$ | $4$ | $4$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{35\,\mathrm{s}}$ | $41$ | $9$
$4$ | $3$ | $3$ | $2.6\,\mathrm{s}$ | $46719$ | $12138$ | $\boldsymbol{803\,\mathrm{ms}}$ | $44$ | $12$
$5$ | $3$ | $3$ | $39\,\mathrm{s}$ | $234219$ | $60888$ | $\boldsymbol{1.3\,\mathrm{s}}$ | $54$ | $15$
$6$ | $3$ | $3$ | $>2\,\mathrm{min}$ | - | - | $\boldsymbol{1.8\,\mathrm{s}}$ | $64$ | $18$

The first line shows the original problem with $k=12$ attempts, a code length
of $n=4$, and $m=6$ colors. We observe that in the low-level approach, time
and size grow exponentially with respect to the number $m$ of colors, whereas
the high-level approach remains constant. When we increase the parameter $n$
controlling the length of the code, both approaches grow exponentially in
time. Interestingly the high-level approach only grows linear in _size_
(number of nodes). This is due to the size of the guard of the
$\mathit{evaluate}$ transition increasing exponentially ($n$ choose $2$).

Overall, the symbolic approach is the clear winner of the Mastermind
benchmark. The low-level approach can only barely compete for the smallest
instances of the problem.

We also observe that, in comparison to other parameters, the performance of
the high-level approach drops when $n=m$. We currently have no explanation for
this. This could be a quirk of the SMT solvers, or alternatively, the formulas
may be inherently more challenging to solve in this particular case. The low-
level approach is not impacted negatively by this case, but still much slower
than the symbolic approach, as seen in lines with parameters $(1,3,3)$,
$(1,4,4)$, $(2,3,3)$, $(2,4,4)$, and in the last four lines.

##  7 Conclusions and Outlook

We introduced the notion of complete finite prefixes of symbolic unfoldings of
high-level Petri nets. We identified a class of 1-safe high-level nets
generalizing 1-safe P/T nets, for which we generalized the well-known
algorithm by Esparza et al. to compute such a finite and complete prefix. This
constitutes a consolidation and generalization of the concepts of [8, 13, 4,
11]. While the resulting symbolic prefix has the same depth as a finite and
complete prefix of the unfolding of the represented P/T net, it can be
significantly smaller due to less branching. In the case of infinitely many
reachable markings (where the original algorithm is not applicable) we
identified the class of so-called _symbolically compact_ nets for which an
adapted version of the generalized algorithm works. For that, we showed how to
check an adapted cut-off criterion by symbolically describing sets of
markings. We implemented the generalized algorithm and tested it against four
novel benchmark families. This experimentation validated a heuristic
indicating the circumstances where the symbolic approach outperforms the low-
level approach. This heuristic relies on the concept of a net property we call
“mode determinism”.

Future works include the construction of a symbolic reachability graph for
symbolically compact nets and a comparison with the complete finite prefix, as
outlined in Sec. 4.4. Additionally, a generalization for $k$-bounded high-
level Petri nets seems possible. Furthermore, we want to apply the results to
_high-level Petri games_ [30, 31] to find “symbolic strategies” with
techniques similar to [32] or [33, 34], employing a successively increasing
bound on size of the considered prefix of the symbolic unfolding.

## References

  * [1] Würdemann N, Chatain T, Haar S.  Taking Complete Finite Prefixes to High Level, Symbolically.  In: Proc. PETRI NETS 2023, LNCS 13929. Springer, 2023 pp. 123–144.  10.1007/978-3-031-33620-1_7.
  * [2] Reisig W.  Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies.  Springer, 2013.  ISBN 978-3-642-33277-7.  10.1007/978-3-642-33278-4.
  * [3] Jensen K.  Coloured Petri Nets - Basic Concepts, Analysis Methods and Practical Use - Volume 1, Second Edition.  Monographs in Theoretical Computer Science. An EATCS Series. Springer, 1996.  ISBN 978-3-642-08243-6.  10.1007/978-3-662-03241-1.
  * [4] Chatain T, Fabre E.  Factorization Properties of Symbolic Unfoldings of Colored Petri Nets.  In: Lilius J, Penczek W (eds.), Proc. PETRI NETS 2010, LNCS 6128. Springer, 2010 pp. 165–184.  10.1007/978-3-642-13675-7_11.
  * [5] Nielsen M, Plotkin GD, Winskel G.  Petri Nets, Event Structures and Domains, Part I.  _Theor. Comput. Sci._ , 1981.  13:85–108.  10.1016/0304-3975(81)90112-2.
  * [6] Engelfriet J.  Branching Processes of Petri Nets.  _Acta Informatica_ , 1991.  28(6):575–591.  10.1007/BF01463946.
  * [7] McMillan KL.  A Technique of State Space Search Based on Unfolding.  _Formal Methods Syst. Des._ , 1995.  6(1):45–65.  10.1007/BF01384314.
  * [8] Esparza J, Römer S, Vogler W.  An Improvement of McMillan’s Unfolding Algorithm.  _Formal Methods Syst. Des._ , 2002.  20(3):285–310.  10.1023/A:1014746130920.
  * [9] Khomenko V, Koutny M.  Branching Processes of High-Level Petri Nets.  In: Proc. TACAS 2003, LNCS 2619. Springer, 2003 pp. 458–472.  10.1007/3-540-36577-X_34.
  * [10] Ehrig H, Hoffmann K, Padberg J, Baldan P, Heckel R.  High-Level Net Processes.  In: Formal and Natural Computing, LNCS 2300. Springer, 2002 pp. 191–219.  10.1007/3-540-45711-9_12.
  * [11] Chatain T, Jard C.  Symbolic Diagnosis of Partially Observable Concurrent Systems.  In: Proc. FORTE 2004, LNCS 3235. Springer, 2004 pp. 326–342.  10.1007/978-3-540-30232-2_21.
  * [12] Chatain T, Jard C.  Complete Finite Prefixes of Symbolic Unfoldings of Safe Time Petri Nets.  In: Proc. ICATPN 2006, LNCS 4024. Springer, 2006 pp. 125–145.  10.1007/11767589_8.
  * [13] Chatain T.  Symbolic Unfoldings of High-Level Petri Nets and Application to Supervision of Distributed Systems.  Ph.D. thesis, Universit é de Rennes, 2006.  URL https://www.sudoc.fr/246936924.
  * [14] Presburger M.  Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt.  In: Proc. Comptes-rendus du I Congrés des Mathématiciens des Pays Slaves, Varsovie 1929. 1930 pp. 92–101.
  * [15] Abdulla PA, Iyer SP, Nylén A.  Unfoldings of Unbounded Petri Nets.  In: Proc. CAV 2000, LNCS 1855. Springer, 2000 pp. 495–507.  10.1007/10722167_37.
  * [16] Desel J, Juhás G, Neumair C.  Finite Unfoldings of Unbounded Petri Nets.  In: Proc. PETRI NETS 2004, LNCS 3099. Springer, 2004 pp. 157–176.  10.1007/978-3-540-27793-4_10.
  * [17] Herbreteau F, Sutre G, Tran TQ.  Unfolding Concurrent Well-Structured Transition Systems.  In: Proc. TACAS 2007, LNCS 4424. Springer, 2007 pp. 706–720.  10.1007/978-3-540-71209-1_55.
  * [18] Schmidt K.  Parameterized Reachability Trees for Algebraic Petri Nets.  In: Proc. PETRI NETS 1995, LNCS 935. Springer, 1995 pp. 392–411.  10.1007/3-540-60029-9_51.
  * [19] Schwoon S.  Mole.  URL http://www.lsv.ens-cachan.fr/~schwoon/tools/mole/.
  * [20] Rodríguez C.  Cunf.  URL https://github.com/cesaro/cunf.
  * [21] Rodríguez C, Schwoon S.  Cunf: A Tool for Unfolding and Verifying Petri Nets with Read Arcs.  In: Proc. ATVA 2013, volume 8172 of _LNCS_. Springer, 2013 pp. 492–495.  10.1007/978-3-319-02444-8_42.
  * [22] Khomenko V.  Punf.  URL homepages.cs.ncl.ac.uk/victor.khomenko/tools/punf/.
  * [23] Panneke L.  ColorUnfolder.  URL https://github.com/Selebrator/ColorUnfolder.
  * [24] Barbosa H, Barrett CW, Brain M, Kremer G, Lachnitt H, Mann M, Mohamed A, Mohamed M, Niemetz A, Nötzli A, Ozdemir A, Preiner M, Reynolds A, Sheng Y, Tinelli C, Zohar Y.  cvc5: A Versatile and Industrial-Strength SMT Solver.  In: Fisman D, Rosu G (eds.), Proc. TACAS 2022, LNCS 13243. Springer, 2022 pp. 415–442.  10.1007/978-3-030-99524-9_24.
  * [25] Atwood ME, Polson PG.  A process model for water jug problems.  _Cognitive Psychology_ , 1976.  8(2):191–216.  https://doi.org/10.1016/0010-0285(76)90023-2.
  * [26] Jeffries R, Polson PG, Razran L, Atwood ME.  A process model for Missionaries-Cannibals and other river-crossing problems.  _Cognitive Psychology_ , 1977.  9(4):412–440.  https://doi.org/10.1016/0010-0285(77)90015-9.
  * [27] Pressman I, Singmaster D.  The jealous husbands and The missionaries and cannibals.  _The Mathematical Gazette_ , 1989.  73(464):73–81.  10.2307/3619658.
  * [28] Knuth DE.  The Computer as Master Mind.  _J. Recreational Mathematics_ , 1976–77.  9(1):1–6.
  * [29] Koyama K, Lai TW.  An optimal Mastermind Strategy.  _J. Recreational Mathematics_ , 1993.  25(4):251–256.
  * [30] Gieseking M, Olderog E.  High-Level Representation of Benchmark Families for Petri Games.  In: Model Checking, Synthesis, and Learning, LNCS 13030. Springer, 2021 pp. 115–137.  10.1007/978-3-030-91384-7_7.
  * [31] Gieseking M, Olderog E, Würdemann N.  Solving high-level Petri games.  _Acta Informatica_ , 2020.  57(3-5):591–626.  10.1007/s00236-020-00368-5.
  * [32] Finkbeiner B.  Bounded Synthesis for Petri Games.  In: Correct System Design, LNCS 9360. Springer, 2015 pp. 223–237.  10.1007/978-3-319-23506-6_15.
  * [33] Chatain T, Haar S, Jezequel L, Paulevé L, Schwoon S.  Characterization of Reachable Attractors Using Petri Net Unfoldings.  In: Proc. CMSB 2014, LNCS 8859. Springer, 2014 pp. 129–142.  10.1007/978-3-319-12982-2_10.
  * [34] Aguirre-Samboní GK, Haar S, Paulevé L, Schwoon S, Würdemann N.  Avoid One’s Doom: Finding Cliff-Edge Configurations in Petri Nets.  In: Proc. GandALF 2022, EPTCS 370. 2022 pp. 178–193.  10.4204/EPTCS.370.12.

##  Appendix A Appendix

###  A.1 Examples of adequate orders

We show that the adequate order used in [7], as well as the orders $\prec_{E}$
and $\prec_{F}$ treated in [8], when lifted to the symbolic unfolding, are
still adequate orders. In particular we show that $\prec_{F}$ is a total
adequate order on the symbolic unfolding, limiting the size of the later
constructed finite prefix. The definition of these orders does not change, so
we take most of the following notation directly from [8].

##### The orders $\prec_{M}$ and $\prec_{E}$.

The order $\prec_{M}$ used in [7] is defined by
$C_{1}\prec_{M}C_{2}:\Leftrightarrow|C_{1}|<|C_{2}|$. It is trivial to see
that $\prec_{M}$ satisfies i) and ii) from Def. 2.6. Since $\varphi_{1,D}^{2}$
is a injective, we have $|\varphi_{1,D}^{2}(D)|=|D|$, which yields iii).

For a high-level Petri net $N$, let $\ll$ be an arbitrary total order on the
transitions of $N$. Given a set $E^{\prime}$ of events in the unfolding of
$N$, let $\mathbf{p}(E^{\prime})$ be that sequence of transitions which is
ordered according to $\ll$, and contains each transition $t$ as often as there
are events in $E^{\prime}$ with label $t$. We say
$\mathbf{p}(E_{1})\ll\mathbf{p}(E_{2})$ if $\mathbf{p}(E_{1})$ is
lexicographically smaller than $\mathbf{p}(E_{2})$ with respect to the order
$\ll$.

The order $\prec_{E}$ is then defined as follows: let $C_{1},C_{2}$ be two
configurations of the symbolic unfoldings of a high-level Petri net.
$C_{1}\prec_{E}C_{2}$ holds if either $|C_{1}|<|C_{2}|$, or $|C_{1}|=|C_{2}|$
and $\mathbf{p}(C_{1})\ll\mathbf{p}(C_{2})$. The proof that $\prec_{E}$ is an
adequate order works exactly as in [8]:

It is easy to show that $\prec_{E}$ is a well-founded partial order implied by
inclusion. We now show that $\prec_{E}$ is preserved by finite extensions. As
already mentioned above, $|D|=|\varphi_{1,D}^{2}(D)|$. Additionally, we have
$\mathbf{p}(D)=\mathbf{p}(\varphi_{1,D}^{2}(D))$, since $\varphi_{1,D}^{2}$
preserves the labeling of events.

Assume $C_{1}\prec_{E}C_{2}$. If $|C_{1}|<|C_{2}|$, then
$|C_{1}{\oplus}D|<|C_{2}{\oplus}\varphi_{1,D}^{2}(D)|$. If $|C_{1}|=|C_{2}|$
and $\mathbf{p}(C_{1})\ll\mathbf{p}(C_{2})$, then
$|C_{1}{\oplus}D|=|C_{2}{\oplus}\varphi_{1,D}^{2}(D)|$ and, by the properties
of the lexicographic order,
$\mathbf{p}(C_{1}{\oplus}D)\ll\mathbf{p}(C_{2}{\oplus}\varphi_{1,D}^{2}(D))$.

##### The Total Adequate Order $\prec_{F}$.

The _Foata normal form_ $\mathit{FC}$ of a configuration $C$ is obtained by
starting with $\mathit{FC}$ empty, and iteratively deleting the set
$\mathit{Min}(C)$ from $C$ and appending it to $\mathit{FC}$, until $C$ is
empty.

Given two configurations $C_{1},C_{2}$, we can compare their Foata normal
forms $\mathit{FC}_{1}=C_{11}\dots C_{1n_{1}}$ and
$\mathit{FC}_{2}=C_{21}\dots C_{2n_{2}}$ with respect to the order $\ll$ by
saying $\mathit{FC}_{1}\ll\mathit{FC}_{2}$ if there exists $i\leq i\leq n_{1}$
such that $\mathbf{p}(C_{1j})=\mathbf{p}(C_{2j})$ for every $1\leq j<i$, and
$\mathbf{p}(C_{1i})\ll\mathbf{p}(C_{2i})$.

######  Definition A.1 (Order $\prec_{F}$)

let $C_{1}$ and $C_{2}$ be two configurations of the symbolic unfolding of a
high-level Petri net. $C_{1}\prec_{F}C_{2}$ holds if

  * •

$|C_{1}|<|C_{2}|$, or

  * •

$|C_{1}|=|C_{2}|$ and $\mathbf{p}(C_{1})\ll\mathbf{p}(C_{2})$, or

  * •

$\mathbf{p}(C_{1})=\mathbf{p}(C_{2})$ and $\mathit{FC}_{1}\ll\mathit{FC}_{2}$.

We prove that $\prec_{F}$ is a total adequate order. In the proof, (a) – (c)
are taken directly from [8], with small adaptations due to the high-level
formalism. While the ideas from (d) also come directly from [8], we have work
with the monomorphism $\varphi_{1,D}^{2}$ instead of the isomorphism
$I_{1}^{2}$, and the new definition of adequate order. This is where the only
deviation from [8] happens.

Let $\beta=(O,h)$ be the symbolic unfolding of
$N=(\mathcal{N},\mathcal{M}_{0})$.

  1. (a)

$\prec_{F}$ is a well-founded partial order.

This follows immediately from the fact that $\prec_{E}$ is a well-founded
partial order as is the lexicographic order on transition sequences of some
fixed length.

  2. (b)

$C_{1}\subset C_{2}$ implies $C_{1}\prec_{F}C_{2}$.

This is obvious, since $C_{1}\subset C_{2}$ implies $|C_{1}|<|C_{2}|$.

  3. (c)

$\prec_{F}$ is total.

Assume that $C_{1}$ and $C_{2}$ are two incomparable configurations under
$\prec_{F}$, i.e., $|C_{1}|=|C_{2}|$, $\mathbf{p}(C_{1})=\mathbf{p}(C_{2})$,
and $\mathbf{p}(\mathit{FC}_{1})=\mathbf{p}(\mathit{FC}_{2})$. We prove
$C_{1}=C_{2}$ by induction on the common size $k=|C_{1}|=|C_{2}|$.

The base case $k=0$ gives $C_{1}=C_{2}=\emptyset$, so assume $k>0$.

We first prove $\mathit{Min}(C_{1})=\mathit{Min}(C_{2})$. Aiming a
contradiction, assume w.l.o.g. that
$e_{1}\in\mathit{Min}(C_{1})\setminus\mathit{Min}(C_{2})$. Since
$\mathbf{p}(\mathit{Min}(C_{1}))=\mathbf{p}(\mathit{Min}(C_{2}))$,
$\mathit{Min}(C_{2})$ contains an event $e_{2}$ s.t. $h(e_{1})=h(e_{2})$.
Since ${\rightarrow}\mathit{Min}(C_{1})$ and
${\rightarrow}\mathit{Min}(C_{2})$ are subsets of $B_{0}$, and all conditions
of $B_{0}$ carry different labels, we have
${\rightarrow}{e_{1}}={\rightarrow}{e_{2}}$, and thus,
$\mathit{pre}(e_{1})=\mathit{pre}(e_{2})$. This contradicts the definition of
symbolic branching processes.

Since $\mathit{Min}(C_{1})=\mathit{Min}(C_{2})$, both
$C_{1}\setminus\mathit{Min}(C_{1})$ and $C_{2}\setminus\mathit{Min}(C_{1})$
are configurations of the branching process ${\Uparrow}\mathit{Min}(C_{1})$ of
$(\mathcal{N},\mathcal{M}(\mathit{Min}(C_{1})))$, and they are incomparable
under $\prec_{F}$ by construction. Since the common size of
$C_{1}\setminus\mathit{Min}(C_{1})$ and $C_{2}\setminus\mathit{Min}(C_{1})$ is
strictly smaller than $k$, we can apply the induction hypothesis and conclude
$C_{1}=C_{2}$.

  4. (d)

$\prec_{F}$ is preserved by finite extensions.

Take two finite configurations $C_{1}$ and $C_{2}$, let $D$ be a finite suffix
of $C_{1}$, and let $M\in\mathcal{M}(C_{1})\cap\mathcal{M}(C_{2})$ such that
$C_{1}\llbracket M\rrbracket D$. We have to show that $C_{1}\prec C_{2}$
implies $C_{1}{\oplus}D\prec C_{2}{\oplus}\varphi_{1,D}^{2}(D)$.

First, notice that we can assume $D=\\{e\\}$: For $e\in\mathit{Min}(D)$ we
have from $C_{1}\llbracket M\rrbracket D$ that
$\exists\theta\in\Theta(C_{1}{\oplus}D):\operatorname{mark}(C_{1}.\theta|_{\mathit{Var}_{C_{1}\cup\\{\bot\\}}})=M$.
Thus, for $M^{\prime}$ s.t. $M[h(e).\sigma\rangle M^{\prime}$ with
$\sigma=\theta\circ[v\mapsto v_{e}]_{v\in\mathit{Var}(e)}$, we have that
$M^{\prime}\in\mathcal{M}(C_{1}{\oplus}\\{e\\})\cap\mathcal{M}(C_{2}{\oplus}\\{\varphi_{1,D}^{2}(e)\\})$
and $(C_{1}{\oplus}\\{e\\})\llbracket
M^{\prime}\rrbracket(D\setminus\\{e\\})$.

Second, the cases $|C_{1}|<|C_{2}|$ and $C_{1}\prec_{E}C_{2}$ in (i), (and the
respective cases $|C_{2}|<|C_{1}|$ and $C_{2}\prec_{E}C_{1}$ in (ii)) are easy
(shown above). Hence, assume $|C_{1}|=|C_{2}|$ and
$\mathbf{p}(C_{1})=\mathbf{p}(C_{2})$.

Third, we show that under these two assumptions $e$ is a minimal event of
$C_{1}^{\prime}:=C_{1}\cup\\{e\\}$ if and only if $\varphi_{1,D}^{2}(e)$ is a
minimal event of $C_{2}^{\prime}:=C_{2}\cup\\{\varphi_{1,D}^{2}(e)\\}$. Let
$e$ be minimal in $C_{1}^{\prime}$, i.e., the transition $h(e)$ can be fired
in a mode in one initial marking. Let $p\in{\rightarrow}h(e)$; then no
condition in ${\rightarrow}C\cup C{\rightarrow}$ is labeled $p$, since these
conditions would be concurrent to the $p$-labeled condition in
${\rightarrow}e$, contradicting that $(\mathcal{N},\mathcal{M}_{0})$ is safe.
Thus, $C_{1}$ contains no event $e^{\prime}$ with
$p\in{\rightarrow}h(e^{\prime})$, and the same holds for $C_{2}$, since
$\mathbf{p}(C_{1})=\mathbf{p}(C_{2})$. Therefore, the conditions in
$\operatorname{cut}(C_{2})$ with label in ${\rightarrow}h(e)$ are minimal
conditions of $\beta$, and $\varphi_{1,D}^{2}(e)=e$ is minimal in
$C_{2}^{\prime}$. The reverse implication holds analogously, since about
$C_{1}$ and $C_{2}$ we have only used the hypothesis
$\mathbf{p}(C_{1})=\mathbf{p}(C_{2})$.

With this knowledge, we now show the implication. Assume
$C_{1}\prec_{F}C_{2}$. We show $C_{1}^{\prime}\prec_{F}C_{2}^{\prime}$.

If $\mathit{Min}(C_{1})\prec_{E}\mathit{Min}(C_{2})$, then we now see
$\mathit{Min}(C_{1}^{\prime})\prec_{E}\mathit{Min}(C_{2}^{\prime})$, hence
$\mathbf{p}(\mathit{FC}_{1}^{\prime})\ll\mathbf{p}(\mathit{FC}_{2}^{\prime})$
and so we are done. If
$\mathbf{p}(\mathit{Min}(C_{1}))=\mathbf{p}(\mathit{Min}(C_{2}))$ and
$e\in\mathit{Min}(C_{1}^{\prime})$, then

$C_{1}^{\prime}\setminus\mathit{Min}(C_{1}^{\prime})=C_{1}\setminus\mathit{Min}(C_{1})\prec_{F}C_{2}\setminus\mathit{Min}(C_{2})=C_{2}^{\prime}\setminus\mathit{Min}(C_{2}^{\prime}),$

hence $C_{1}^{\prime}\prec_{F}C_{2}^{\prime}$. Finally, if
$\mathbf{p}(\mathit{Min}(C_{1}))=\mathbf{p}(\mathit{Min}(C_{2}))$ and
$e\notin\mathit{Min}(C_{1}^{\prime})$, we again argue that
$\mathit{Min}(C_{1})=\mathit{Min}(C_{2})$ and that, hence,
$C\setminus\mathit{Min}(C_{1})$ and $C_{2}\setminus\mathit{Min}(C_{1})$ are
configurations of the branching process ${\Uparrow}\mathit{Min}(C_{1})$ of
$(\mathcal{N},\mathcal{M}(\mathit{Min}(C_{1})))$. With an inductive argument
we get
$C_{1}^{\prime}\setminus\mathit{Min}(C_{1}^{\prime})\prec_{F}C_{2}^{\prime}\setminus\mathit{Min}(C_{2}^{\prime})$
and are also done in this case.

###  A.2 More Symbolic and Low-level Unfoldings

In this appendix we present unfoldings omitted in the main body of the paper.

##### Low-level Unfolding of Fork And Join.

Since the symbolic unfolding of any Fork And Join is structurally equal to the
net itself we do not display it here. Fig. 11 shows the low-level unfolding
with $(n+2)(m+1)^{n}+1$ nodes for a Fork And Join.

Figure 11: The symbolic unfolding of a Fork And Join, depending on the
parameters $m$ and $n$.

##### Symbolic Unfolding of Water Pouring Puzzle.

Figure 12 shows the complete finite prefix of the symbolic unfolding of the
Water Pouring Puzzle from Fig. 6 with $n=[5,3]$ and $m=4$, calculated by our
implementation ColorUnfolder [23] of the generalized ERV-algorithm, Alg. 1.
The figure is automatically produced from the output of ColorUnfolder. Cut-off
events are marked by a red border. Additionally marked by a red border are the
events representing the added $\mathit{goal}$ transition that checks the
target states. Since the net is mode deterministic, the symbolic unfolding’s
skeleton coincides with the low-level unfolding. Thus, the skeleton of the
complete finite prefix in Figure 12 coincides with the complete finite prefix
of the low-level unfolding generated by the original ERV-algorithm from [8].

Figure 12: A prefix of the symbolic unfolding of the Water Pouring Puzzle for
$n=[3,5]$ and $m=4$, produced by ColorUnfolder.

##### Symbolic Unfolding of Mastermind.

Figure 13 shows a prefix of the symbolic unfolding of the Mastermind net from
Fig. 8 with 6 available colors, a code of length 4, and 12 possible attempts.
Combinatorial arguments give that the low-level unfolding has more than
$10^{37}$ nodes, so we do not present it here.

Figure 13: A prefix of the symbolic unfolding of the Mastermind net from Fig.
8.


# Joint Power Allocation and Beamformer for mmW-NOMA Downlink Systems by Deep
Reinforcement Learning

Abbas Akbarpour-Kasgari and Mehrdad Ardebilipour A. Akbarpour-Kasgari and M.
Ardebilipour are with the Department of Electrical and Computer Engineering,
K. N. Toosi University of Technology, Tehran, Iran e-mail:
<EMAIL_ADDRESS>
###### Abstract

The high demand for data rate in the next generation of wireless communication
could be ensured by Non-Orthogonal Multiple Access (NOMA) approach in the
millimetre-wave (mmW) frequency band. Joint power allocation and beamforming
of mmW-NOMA systems is mandatory which could be met by optimization
approaches. To this end, we have exploited Deep Reinforcement Learning (DRL)
approach due to policy generation leading to an optimized sum-rate of users.
Actor-critic phenomena are utilized to measure the immediate reward and
provide the new action to maximize the overall Q-value of the network. The
immediate reward has been defined based on the summation of the rate of two
users regarding the minimum guaranteed rate for each user and the sum of
consumed power as the constraints. The simulation results represent the
superiority of the proposed approach rather than the Time-Division Multiple
Access (TDMA) and another NOMA optimized strategy in terms of sum-rate of
users.

###### Index Terms:

millimetre-wave, Non-Orthogonal Multiple Access, Power allocation,
Beamforming, Deep reinforcement learning.

##  I Introduction

Multiple access techniques due to their ability to provide suitable data
accommodation, are the key enabler of the high data rate demands in future
network generation. Among the well-known approaches, non-orthogonal multiple
access (NOMA) is attracting researchers’ interest to support high data rate
demands and massive connectivity in 5G and beyond [1]. NOMA technique is
introduced to outperform other well-known approaches such as time division
multiple access (TDMA), orthogonal frequency division multiple access (OFDMA),
and zero-forcing (ZF) in terms of spectral and energy efficiency [1]. NOMA
allocates frequency and time resources between all the available users,
simultaneously, thanks to the power domain superposition [2].

The most crucial difference between mmW-NOMA and conventional NOMA is the
interlace of power allocation and beamforming problems. In [3], one of the
pioneer works on mmW-NOMA schemes was adapted to introduce the random steering
beamformer limited to the near users to each other. The energy efficiency was
optimized subject to the power allocation and sub-channel assignment in [4],
where no beamformer was represented. In [5], a fully digital beamformer was
introduced to optimize the sum-rate. Moreover, in [6], the joint problem was
considered but the optimization was only performed on the most powerful path
in the channel. Further, in [7] joint power allocation and beamforming were
optimized by considering Signal-to-Leakage-plus-Noise (SLNR) in order to
decouple the power allocation and beamforming. On the contrary to all the
mentioned prior works, we have used newly introduced machine learning (ML)
tools to optimize the joint power allocation and beamformer design in mmW-
NOMA.

Recently, machine learning (ML) techniques are deployed in wireless
communication networks as optimization tools. Among them, Reinforcement
Learning (RL) is a closed-loop optimization procedure that is based on the
action and reaction of the agent and environment, respectively. Further,
encountering a continuous problem with a large number of states will be
handled with deep RL (DRL) approaches [8, 9, 10]. In [8] DRL is exploited to
optimize joint beamforming, power control, and interference coordination in
$5^{th}$ generation (5G) network. The authors used a deep Q-learning approach
to estimate future rewards. Besides, Hybrid beamforming in mmW network was
considered in multi-user multiple-input single-output (MU-MISO) system
utilizing multi-agent DRL-based approach in [9]. Further, The optimal approach
was designed based on employing a deep Q-learning approach and the cooperation
of BSs in [10].

In this paper, we have exploited DRL to optimize joint power allocation and
beamformer in the Base Station (BS) to increase the sum-rate of two users. We
have demonstrated joint power allocation and beamformer design in an
optimization problem form. Further, we have demonstrated the agent and
environment, the states, the actions, and the immediate reward to be maximized
during the flow of the DRL algorithm. To handle the problem, we have borrowed
actor-critic networks from DRL approaches with the aid of a deep neural
network (DNN). Since the states of beamformer and power allocation are
continuous, the DNN is employed to handle the complexity of the problem. Two
different DNNs are exploited by actor and critic individually. The critic
network accepts states of the environment and measures the action immediate
reward. The actor network accepts states and the reward to generate the new
action from space in order to maximize the future reward.

The rest of the paper is organized as follows: Subsequent to the system model
and problem formulation in section II, the proposed joint power allocation and
beamformer design are represented in section III. Further, the numerical
results and concluding remarks are demonstrated in section IV and section V,
respectively.

##  II System Model and Problem Formulation

We consider a millimetre-wave non-orthogonal multiple access (mmW-NOMA)
downlink system where an $N$-antenna equipped Base Station (BS) transmits
towards $2$ single antenna users. In essence, the BS exploits $N$ antenna and
NOMA strategy to simultaneously serves two users. Specifically, if we consider
$s_{k}$ ($\mathbb{E}\left(|s_{k}|^{2}\right)=1$) as the transmitted message
for $k$-th user, the BS will transmit superposition
$\sqrt{p_{1}}\mathbf{w}_{1}s_{1}+\sqrt{p_{2}}\mathbf{w}_{2}s_{2}$ toward the
users, where $p_{k}$, and $\mathbf{w}_{k}$ are the power devoted to the $k$-th
user and the beamformer weight ($\|\mathbf{w}_{k}\|^{2}=1$), respectively.
Accordingly, the received signal in the $k$-th user is denoted by

$y_{k}=\mathbf{h}_{k}^{H}\sqrt{p_{k}}\mathbf{w}_{k}s_{k}+\mathbf{h}^{H}_{\bar{k}}\sqrt{p_{\bar{k}}}\mathbf{w}_{\bar{k}}s_{\bar{k}}+n_{k},$
(1)

where $\bar{k}=2(=1)$ for $k=1(=2)$, and $\mathbf{h}_{k}\in\mathbb{C}^{N}$
represents the complex channel vector between the BS and the $k$-th user.

The channel vector between the BS and $k$-th user is an mmW channel. Since
there are limited scatterers in the mmW band, the multipath which is caused by
reflection is small and leads to a spatially sparse directional channel in the
angle domain [11]. Assuming a uniform linear array (ULA), the mmW channel can
be demonstrated as [11]

$\mathbf{h}_{k}=\sum\limits_{l=1}^{L_{k}}\lambda_{k,l}\mathbf{a}(N,\Omega_{k,l})$
(2)

where $\lambda_{k,l}$, and $\Omega_{k,l}$ are the complex coefficient and
angle-of-arrival (AoD) of the $l$-th multipath components, respectively.
Further, $L_{k}$ is the number of multipath components for $k$-th user, and
$\mathbf{a}(.)$ is the steering vector function which is defined as

$\mathbf{a}(N,\Omega)=\left[e^{j\pi 0\cos(\Omega)},e^{j\pi
1\cos(\Omega)},\dots,e^{j\pi(N-1)\cos(\Omega)}\right]$ (3)

and is dependent to the geometry of the array. For the rest of the paper, we
assume that the users are ordered based on their channel quality, i.e.,
$\|\mathbf{h}_{1}\|_{2}\leq\|\mathbf{h}_{2}\|_{2}$. Exploiting Successive
Interference Cancellation (SIC), the NOMA receiver can decode the power domain
signal transmitted signal in the same frequency and time resource [12]. Based
on the suggested ordering the received Signal-to-Interference-plus-Noise
(SINR) in each user can be defined as

$\displaystyle\text{SINR}_{1}=\frac{|\mathbf{h}^{H}_{1}\mathbf{w}_{1}|^{2}p_{1}}{|\mathbf{h}^{H}_{1}\mathbf{w}_{2}|^{2}p_{2}+\sigma^{2}}$
(4)
$\displaystyle\text{SINR}_{2}=\frac{|\mathbf{h}^{H}_{2}\mathbf{w}_{2}|^{2}p_{2}}{\sigma^{2}}$
(5)

where $\sigma_{2}$ is the noise variance. Hence, the achievable rate in each
user is denoted as

$\displaystyle R_{k}=\log_{2}(1+\text{SINR}_{k}).$ (6)

In this paper, we consider the problem of joint power allocation and
beamformer design for sum-rate optimization. As a consequence, the objective
function is the sum-rate of two users. Moreover, there are some constraints
which are denoted as below:

$\begin{array}[]{rrclcl}\max_{\mathbf{w}_{k},p_{k}}&R_{1}+R_{2}\\\
s.t.&R_{k}\geq r_{k}\\\ &p_{1}+p_{2}=P\\\
&\|\mathbf{w}_{k}\|_{2}^{2}=1\end{array}$ (7)

where $k=1,2$ for the above equation and $P$ is the total available power in
BS. Moreover, $r_{k}$ is the minimum achievable rate in $k$-th user which
should be provided. As discussed earlier, the cost function is the sum-rate of
the users. Further, the first constraint ensures the minimum rate for each
user. Besides, the second and third constraints determine the feasible space
of the independent variables of the problem, i.e., they guarantee the
transmission power of the users and their corresponding beamforming weights.

##  III Joint Power Allocation and Beamformer Design

Here we will discuss the proposed approach to solve the joint power
optimization and beamformer design problem in Eq. (7). We have utilized the
Deep Reinforcement Learning (DRL) approach to introduce the optimized power
and beamformer weights.

###  III-A Deep Reinforcement Learning

DRL is involved of Deep Learning (DL) and Reinforcement Learning (RL),
simultaneously. Due to existence of the DL part in this approach, it’s very
suitable for handling large state and action space Markov Decision Process
(MDP) problems [13]. The MDP can be defined by a four-tuple space as
$\\{\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R}\\}$, where $\mathcal{S}$
is the state space denoting the observation from environment. Further,
$\mathcal{A}$ is the action space and representing the available actions from
the agent to optimize the reward. Besides, $\mathcal{P}$ is the state
transition probability, and $\mathcal{R}$ is the immediate reward of the
action $a_{t}\in\mathcal{A}$ in state $s_{t}\in\mathcal{S}$. According to the
immediate reward, the long-term reward
$V(s)=\mathbb{E}\\{\sum\limits_{t=0}^{\infty}\gamma^{t}r_{t}(s_{t},a_{t})|s\\}$
for discount factor $\gamma\in[0,1]$ can be maximized to guarantee the best
action in each state.

Accordingly, we can model the problem at hand into the DRL framework by
defining mandatory 4-tuple state variables. To represent the 4-tuple state
variables, we demonstrate the immediate reward function based on the problem.
To this end, we need to reconsider the optimization problem in Eq. (7). The
auxiliary variable $\alpha$ is defined to guarantee the feasibility of the
constraint. Hence, the following immediate reward is defined

$r_{t}=(1-\alpha)(R_{1}+R_{2})$ (8)

where $\alpha=1$ if one of the constraints is not met, while $\alpha=0$
ensures the constraints feasibility. In other words, if each of the
constraints in Eq. (7) is not met, then $\alpha=1$. Consequently, immediate
reward in the episode will be zero.

Hence, the state $\mathcal{S}$ is defined as
$\mathcal{S}=\\{\mathbf{h}_{1}^{\mathcal{R}},\mathbf{h}_{1}^{\mathcal{I}},\mathbf{h}_{2}^{\mathcal{R}},\mathbf{h}_{2}^{\mathcal{I}},\alpha\\}$,
where superscript $\mathcal{R}$ and $\mathcal{I}$ denote real part and
imaginary part, respectively. Furthermore, the action state $\mathcal{A}$ is
defined as
$\mathcal{A}=\\{\mathbf{w}_{1}^{\mathcal{R}},\mathbf{w}_{1}^{\mathcal{I}},\mathbf{w}_{2}^{\mathcal{R}},\mathbf{w}_{2}^{\mathcal{I}},p_{1},p_{2}\\}$.

###  III-B Deep Deterministic Policy Gradient

Due to the continuous state space of the joint power allocation and
beamformer, we have exploited the Deep Deterministic Policy Gradient (DDPG)
approach to map the state $s_{t}\in S$ to the action space
$a_{t}\in\mathcal{A}$ such that the value function is maximized. DDPG
algorithm utilizes a DNN with the parameter $\theta$ to estimate the optimal
policy function [13]. The DNN training tries to update the policy
$\pi_{\theta}$ in the gradient direction of value function defined as

$\triangledown_{\theta}J(v)=\mathbb{E}_{s}\left[\triangledown_{a}Q(s,a|\beta)\triangledown_{\theta}\pi_{\theta}(s)|_{a=\pi_{\theta}(s)}\right]$
(9)

where $J(v)$ is the value function and defined as

$J(v)=\sum_{s\in\mathcal{S}}p(s)\sum_{a\in\mathcal{A}}\pi_{\theta}(a|s)Q(s,a|\beta)$
(10)

The gradient formulation in Eq. (9) inspires the actor-critic framework where
two separate DNN parameters corresponding to $(\theta,\beta)$ are optimized
[13]. The actor network will update $\theta$ and demonstrate the optimal
policy, while the critic network will update $\beta$ to demonstrate the
intermediate value function for the current action which has been applied by
the agent. The whole network of the system is demonstrated as in Fig. 1.

Figure 1: Schematic diagram of actor-critic network

###  III-C Deep Neural Networks

As mentioned earlier, the whole optimization network involved two independent
DNNs. The first one which is the critic one accepts two different inputs
including current observation and current action. These inputs are merged via
a concatenation layer and then go across three dense layers followed by ReLU
as the activation layer. Finally, a dense layer will estimate the Q-value of
the network.

Secondly, the actor network welcomes the current action and after applying
four dense layers with ReLU as the activation layer, will determine the next
action of the agent.

##  IV Numerical Results

In this section, the simulation results are shown. Further, the results are
compared with the TDMA approach which is denoted as ’TDMA’ in the figures.
Moreover, the NLOS system in [6] is considered as another benchmark for
comparison which is called ’NLOS-NOMA’ in the figures. The simulation results
are averaged on $1000$ independent runs. In the DDPG part, the forgetting
factor, actor learning rate, and critic learning rate are $0.99$, $0.0001$,
and $0.0005$, respectively. Further, the number of episodes is $1000$ in
training while the number of runs over each episode is $250$. The average
score is defined based on the last $250$ score. Additionally, the number of
users is two, while the number of transmitter and receiver antennas is $16$.
The signal-to-noise ratio (SNR) is defined as the ratio of total power to the
noise power ($P/\sigma^{2}$).

The score of the training part is represented in Fig. 2. As depicted, $5000$
episodes are used for training. Each episode is consist of $250$ trials and
the score is moving average of the last $250$ consecutive results. Moreover,
the SNR is $30$ dB, and $r_{1}=r_{2}=1$ (bps/Hz). As represented, the
achievable sum-rate is increased from $7$ to more than $12$ and stabled around
it. This simulation represented that the algorithm is converged.

In Fig. 3, the achievable sum-rate is compared for different algorithms in
various SNRs. Here, the minimum guaranteed rate for each user is equal to $1$
(bps/Hz). As stated before, TDMA and NLOS-NOMA are utilized as the benchmarks
of comparison. As can be seen, the sum-rate of the proposed DRL-based approach
outperforms the other approaches. The superiority of the proposed approach to
TDMA is obviously due to the simultaneous resource allocation in NOMA rather
than TDMA. Further, the proposed DRL-based approach is superior to the NLOS-
NOMA which could be two-fold. On one hand, the proposed approach tries to
simultaneously optimize the power allocation and beamformer design, while in
NLOS-NOMA the problem is broken into two individual parts. On the other hand,
the proposed approach is not limited to the channel condition, while in NLOS-
NOMA, the power of the LOS tap is very effective in the performance of the
algorithm.

In Fig. 4, the impact of the minimum guaranteed rate for each user is
considered on the achievable sum-rate with the predefined SNR = $30$ dB. Here,
the proposed DRL-based approach is superior to the other benchmarks, too. With
some more accurate consideration, it is obvious that the gap between the
proposed DRL-based approach and the NLOS-NOMA approach is decreased with the
increase of the minimum guaranteed rate. This is caused by the score
definition. In Eq. (8), we have defined $\alpha=0$ or $\alpha=1$. In essence,
we have defined a step that cut the score calculation very sharply if the
conditions are not satisfied. This would increase the number of zero scores in
higher minimum guaranteed rates. Consequently, the optimization problem is
encountered with some discrete points which is not favorable. Hence, in our
future works, we will consider a soft limiter in the score calculation and
represent its performance.

Figure 2: The average score value during training in 5000 episodes Figure 3:
The achievable sum-rate comparison regarding the SNR of signal Figure 4: The
achievable sum-rate comparison regarding the guaranteed minimum rate

##  V Concluding Remarks

In this paper, we have considered the joint power allocation and beamformer
design in the mmW-NOMA downlink system. In order to optimize the problem, we
have exploited a well-known data-science-borrowed DRL approach with the actor-
critic framework. The most crucial advantage of the proposed approach rather
than previous ones is the joint optimization while in other previous works the
joint problem is broken into two individual ones due to non-convexity. We have
defined action space, states, and immediate reward of the system based on the
sum-rate of two users, as well. Ultimately, we have compared our proposed DRL-
based approach with TDMA and NLOS-NOMA based approaches as the state-of-the-
art algorithms. As represented in the figures, the proposed approach
outperforms other algorithms perfectly, due to simultaneous optimization and
limitless behavior encountering various channels.

## Acknowledgement

The authors would like to thank from Iran National Science Foundation (INSF)
which supported this work financially under grant number 99011213.

## References

  * [1] X. Chen, Z. Zhang, C. Zhong, and D. W. K. Ng, “Exploiting multiple-antenna techniques for non-orthogonal multiple access,” _IEEE Journal on Selected Areas in Communications_ , vol. 35, no. 10, pp. 2207–2220, October 2017.
  * [2] B. Wang, L. Dai, Z. Wang, N. Ge, and S. Zhou, “Spectrum and energy efficient beamspace MIMO-NOMA for millimeter-wave communications using lens antenna array,” _IEEE Journal on Selected Areas in Communications_ , vol. 35, no. 10, pp. 2370–2382, Oct. 2017.
  * [3] Z. Ding, P. Fan, and H. V. Poor, “Random beamforming in millimeterwave NOMA networks,” _IEEE Access_ , vol. 5, pp. 7667–7681, Feb. 2017.
  * [4] F. Fang, H. Zhang, J. Cheng, and V. C. M. Leung, “Energy-efficient resource allocation for downlink non-orthogonal multiple access network,” _IEEE Transactions on Communications_ , vol. 64, no. 9, pp. 3722–3732, Sept. 2016.
  * [5] M. F. Hanif, Z. Ding, T. Ratnarajah, and G. K. Karagiannidis, “A minorization-maximization method for optimizing sum rate in the downlink of non-orthogonal multiple access systems,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 1, pp. 76–88, Jan. 2016.
  * [6] Z. Xiao, L. Zhu, J. Choi, P. Xia, and X.-G. Xia, “Joint power allocation and beamforming for non-orthogonal multiple access (NOMA) in 5G millimeter wave communications,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 5, pp. 2961–2974, May 2018.
  * [7] L. Pang, W. Wu, Y. Zhang, Y. Yuan, Y. Chen, A. Wang, and J. Li, “Joint power allocation and hybrid beamforming for downlink mmWave-NOMA systems,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 10, pp. 10173–10184, Oct. 2021.
  * [8] F. B. Mismar, B. L. Evans, and A. Alkhateeb, “Deep reinforcement learning for 5G networks: Joint beamforming, power control, interference coordination,” _IEEE Transactions on Communications_ , vol. 68, no. 3, pp. 1581–1592, Mar. 2020.
  * [9] Q. Wang, X. Li, S. Jin, and Y. Chen, “Hybrid beamforming for mmWave MU-MISO systems exploiting Multi-agent deep reinforcement learning,” _IEEE Wireless Communications Letters_ , vol. 10, no. 5, pp. 1046–1050, May 2021.
  * [10] J. Ge, Y. C. Liang, J. Joung, and S. Sun, “Deep reinforcement learning for distributed dynamic MISO downlink-beamforming coordination,” _IEEE Transactions on Communications_ , vol. 68, no. 10, pp. 6070–6085, Oct. 2020.
  * [11] Z. Xiao, P. Xia, and X.-G. Xia, “Codebook design for millimeter-wave channel estimation with hybrid precoding structure,” _IEEE Transactions on Wireless Communications_ , vol. 16, no. 1, pp. 141–153, Jan. 2017.
  * [12] G. Wunder, P. Jung, M. Kasparick, T. Wild, F. Schaich, Y. Chen, S. T. Brink, I. Gaspar, N. Michailow, A. Festag, L. Mendes, N. Cassiau, D. Ktenas, M. Dryjanski, S. Pietrzyk, B. Eged, P. Vago, and F. Wiedmann, “5GNOW: non-orthogonal, asynchronous waveforms for future mobile applications,” _IEEE Communications Magazine_ , vol. 52, no. 2, pp. 97–105, Feb. 2014.
  * [13] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.