# Simplified Embedding Scheme for Quantum Annealing Applied to Activity Detection in Massive Wireless Networks

Romain Piron, Fabian Ganzer, Claire Goursaud

► To cite this version:

Romain Piron, Fabian Ganzer, Claire Goursaud. Simplified Embedding Scheme for Quantum Annealing Applied to Activity Detection in Massive Wireless Networks. INFOCOM 2025 - IEEE International Conference on Computer Communications, May 2025, London, United Kingdom. pp.1-6.
hal-04959922v2

HAL Id: hal-04959922

https://hal.science/hal-04959922v2

Submitted on 25 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Simplified Embedding Scheme for Quantum Annealing Applied to Activity Detection in Massive Wireless Networks

Romain Piron

Univ Lyon, INSA Lyon, INRIA

CITI EA 3720

69621 Villeurbanne, France

romain.piron@insa-lyon.fr

Fabian Ganzer

Univ Lyon, INSA Lyon, INRIA

CITI EA 3720

69621 Villeurbanne, France

fabian.ganzer@insa-lyon.fr

Claire Goursaud

Univ de Lyon, INSA Lyon, INRIA

CITI EA 3720

69621 Villeurbanne, France

claire.goursaud@insa-lyon.fr

**Abstract**—Leveraging quantum annealing (QA) for the activity detection problem in massive wireless networks is a promising approach to address the stringent reliability and latency constraints of typical application scenarios. However, the practical implementation of QA on current D-Wave's processors requires embedding the problem. This increases the number of qubits needed for a given network size, which degrades QA performance. In this work, we propose to add a pre-processing step called the threshold method to mitigate the undesired effects of embedding. Our results show that, within limited computational time, this threshold method improves QA's accuracy in solving the activity detection problem. Thus, this is promising to effectively reduce the negative impact of embedding.

**Index Terms**—Massive connectivity, Activity detection, Quantum annealing, Embedding, Quantum hardware

## I. INTRODUCTION

The future generation of wireless networks must address issues related to massive connectivity, reliability, and low latency [1] as it is expected to serve application cases such as the Industrial Internet of Things [2]. In such a scenario, a huge number of user equipments (UE) populate the network, thus the allocation of a dedicated time slot or frequency to each node before the transmission of data to the access point (AP) is unrealistic.

Instead, the AP allocates dedicated resources only to the active UEs [3]. To achieve this, each active UE must complete a random access procedure at the beginning of a frame before transmitting data [4]. Then, the AP identifies the active nodes during the so-called activity detection part [5], [6]. In 5G massive wireless networks, the grant-free non-orthogonal multiple access scheme is relevant to address the latency and scalability constraints [7]. However, it makes activity detection a challenging task due to the interferences between different pilot signals. Optimal recovery is theoretically possible with a maximum-likelihood estimation but is NP-hard [7].

The current approaches to address this issue without a perfect knowledge of the channel state information (CSI) use either approximate message passing algorithms [8] or coordinate descent methods [9], [10] in order to converge towards a good estimation of the activity pattern in a reasonable computational time. However, a novel method introduced in [9] formulates the activity detection problem without the

CSI knowledge as a least square problem which opens new perspectives. The optimal solution is still unreachable classically without an exhaustive search, but this new formulation falls into the category of quadratic unconstrained binary optimization (QUBO) problems [11]. Interestingly, QUBO problems are well suited for certain quantum algorithms.

Particularly, quantum annealing (QA) was introduced in [12] as a novel quantum computing method to find the ground state of energy functions known as Ising Hamiltonians. Such a task is equivalent to solving QUBO problems [11], which suggests that QA is a promising candidate for the activity detection problem. Although the generic advantage of QA over classical methods remains an active field of research today [13], [14], it already outperformed its classical analogue, known as simulated annealing [15], to find the ground state of certain classes of Hamiltonians [11]. This is why QA could provide more accurate results for activity detection in massive wireless networks than current methods while maintaining reasonable computational time. This potential has already attracted interest from the communication community [16] for various wireless network tasks such as MIMO processing [6], but also activity detection [17].

QA processes can already be executed on real quantum processors, such as those provided by D-Wave [18]. However, the QPU's topology restricts the problems that can be processed. In particular, the connectivity of the processor limits the number of pairwise interactions between the qubits. Thus, an embedding step [19], [20] is necessary to submit a QUBO problem to a D-Wave processor, but it increases the number of physical qubits required for QA. Despite improvements from the new Pegasus topology on D-Wave's Advantage System [21], [22], embedding still increases the qubit count, potentially reducing QA's advantage over classical methods [23]. This work thus proposes a pre-processing step to mitigate embedding effects while maintaining QA-based activity detection accuracy.

The rest of the paper is organized as follows. We first present in Sec. II the activity detection problem in a massive wireless network. Then, we briefly remind the general principle of QA in Sec. III and present our strategy for embedding an activity detection problem on a D-Wave's annealer. At last, we discuss our experimental protocol and our results in Sec. IV.
## Notations

<table><thead><tr><th>Object</th><th>Notation</th></tr></thead><tbody><tr><td>Scalar</td><td>x</td></tr><tr><td>Vector</td><td><b>x</b></td></tr><tr><td>Matrix</td><td><b>X</b></td></tr><tr><td>Diagonal matrix such that X<sub>ii</sub> = x<sub>i</sub></td><td>Diag(<b>x</b>)</td></tr><tr><td>Sphere of radius 1 in d dimensions</td><td>S<sup>d-1</sup></td></tr><tr><td><i>l</i><sub>2</sub> norm</td><td>||·||<sub>2</sub></td></tr><tr><td>Froebenius norm</td><td>||·||<sub>F</sub></td></tr><tr><td>Uniform distribution over a set Ω</td><td>U(Ω)</td></tr><tr><td>Gaussian law of mean <b>μ</b> and covariance matrix <b>Σ</b></td><td>N(<b>μ</b>, <b>Σ</b>)</td></tr><tr><td>Delta function over a discrete set peaked on μ<sub>0</sub></td><td>δ<sub>μ<sub>0</sub></sub>(μ)</td></tr></tbody></table>

# II. ACTIVITY DETECTION PROBLEM

## A. Scenario of interest

We consider the common scheme of a grant-free multiple access protocol [8] in a massive wireless network. Especially, we focus on the uplink of N user equipments (UEs), e.g. sensors, linked to a K-antenna access point (AP). Each user #i is assigned a pilot sequence $p_i$ of length M. Before data transmission, the active UEs transmit their sequence at the start of the frame to enable the AP to detect them. Since the coherence block is limited, preserving symbols for data transmission constrains M [8], typically making M < N and $p_i$ non-orthogonal. Consequently, users should be processed collectively for better accuracy.

## B. System model

One denotes $h_i \in \mathbb{C}^K$ the channel vector between the i-th UE and the AP. As usually done in related works [3], [8], the sequences $p_i$ are generated randomly, and we adopt the simple generation scheme:

$$p_i \sim U(S^{M-1}) \quad \text{for } i = 1, \dots, N. \qquad (1)$$

The difficulty of activity detection may depend on the chosen generation scheme. In this work, we set aside these considerations, but a discussion can be found in [24].

The user's activity is encoded in a bitstring $\alpha^{(0)}$ called the activity pattern such that:

$$\alpha_i^{(0)} = \begin{cases} 1 & \text{if the } i\text{-th UE is active} \\ 0 & \text{otherwise} \end{cases} \qquad (2)$$

The received signal $\mathbf{Y} = [\mathbf{y}_1 \cdots \mathbf{y}_K]$ at the AP contains the sent pilots altered by the channels, and an additive white Gaussian noise (AWGN) [3], [17]:

$$\mathbf{Y} = \mathbf{P} \cdot \text{Diag}(\alpha^{(0)}) \cdot \mathbf{H}^T + \mathbf{W} \qquad (3)$$

with the following notations:

$$\mathbf{P} = [\mathbf{p}_1 \cdots \mathbf{p}_N] \in \mathbb{C}^{M \times N} \quad \text{(Pilot matrix)}$$

$$\mathbf{H} = [\mathbf{h}_1 \cdots \mathbf{h}_N] \in \mathbb{C}^{K \times N} \quad \text{(Channel matrix)} \qquad (4)$$

$$\mathbf{W} = [\mathbf{w}_1 \cdots \mathbf{w}_K] \in \mathbb{C}^{M \times K} \quad \text{(AWGN)}$$

Due to the stochastic nature of the perturbations, $\mathbf{H}$ and $\mathbf{W}$ are random matrices. We assume that they obey the following distributions [25]:

$$\mathbf{h}_i \sim \mathcal{N}(\mathbf{0}, \beta_i I_K) \quad \text{for } i = 1, \dots, N,$$

$$\mathbf{w}_k \sim \mathcal{N}(\mathbf{0}, \xi^2 I_M) \quad \text{for } k = 1, \dots, K \qquad (5)$$

The $\beta_i$'s are known as the large scale fading coefficients and $\xi^2$ is the power of the AWGN. We assume that one is able

to set $\beta_i = 1$ for all $i$, for instance, using automatic gain control as in [9]. Since the pilot sequences carry unit power, the signal-to-noise ratio (SNR) between the i-th UE and the AP is independent of $i$ and is given in dB by [25]:

$$\text{SNR} = -10 \log_{10} (M \xi^2) \qquad (6)$$

## C. Recovery of the activity pattern

The activity detection task consists in retrieving the actual activity pattern $\alpha^{(0)}$ from the available data at the AP. Given a guess $\alpha$ of the activity pattern, the recovery error is evaluated with the user-error rate (UER) that counts the number of different bits between $\alpha$ and $\alpha^{(0)}$:

$$\text{UER}(\alpha, \alpha^{(0)}) = \frac{1}{N} \sum_{i=1}^{N} \delta(\alpha_i \neq \alpha_i^{(0)}) \qquad (7)$$

This work focuses on a recovery method from the covariance-based approach [5], [9]. Especially, we use the NNLS detector introduced in [9] defined as:

$$\alpha^{\text{NNLS}} = \arg \min_{\alpha \in \{0,1\}^N} \left\| \mathbf{P} \cdot \text{Diag}(\alpha) \cdot \mathbf{P}^{\text{H}} - \frac{1}{K} \sum_{k=1}^{K} \mathbf{y}_k \mathbf{y}_k^{\text{H}} \right\|_{F}^{2} \qquad (8)$$

This detector consists in matching the true covariance matrix of the signal to the sample one retrieved from the available data at the AP [9], i.e. from the received signal $\mathbf{Y}$ and the pilot matrix $\mathbf{P}$. Thus, we call a pair $(\mathbf{Y}, \mathbf{P})$ a problem instance in this paper.

One major advantage of the NNLS detector is that it does not require to know the channel-state information $\mathbf{H}$ or the noise level $\xi^2$. Furthermore, $\alpha^{\text{NNLS}}$ converges towards the activity pattern as $K \to \infty$ [5] in the sense that:

$$\text{UER}(\alpha^{\text{NNLS}}, \alpha^{(0)}) \underset{K \to \infty}{\longrightarrow} 0, \qquad (9)$$

which makes $\alpha^{\text{NNLS}}$ particularly relevant for SIMO and MIMO systems [5]. However, Eq. 8 clearly shows that the computation of this detector is NP-hard. Nonetheless, this problem is exactly a QUBO problem. [11]. Thus, leveraging QA in this context might permit to accurately recover the activity pattern in a reasonable computational time.

In this work, we want to isolate the recovery errors coming specifically from the QA protocol that we will implement to compute the NNLS detector. Thus, we consider the asymptotical regime in which $\alpha^{\text{NNLS}}$ perfectly recovers the activity pattern once it is computed, that is:

$$\left\{ \begin{array}{l} \text{SNR} \rightarrow \infty \\ K \gg 1 \end{array} \right. \qquad (10)$$

In practice, we fix once for all $\xi^2 = 0$ and $K = 100$ in order to reasonably assume that $\text{UER}(\alpha^{\text{NNLS}}, \alpha^{(0)}) = 0$.

# III. EMBEDDING THE QA APPROACH ON A QUANTUM HARDWARE

## A. Background for QA

QA was originally introduced in [12] as a novel approach for minimizing energy functions known as Ising Hamiltonians. Such function is expressed in terms of spin variables $\sigma \in \{-1, 1\}$ and has the general form [11]:

$$H_P(\boldsymbol{\sigma}) = - \sum_{i<j} J_{ij} \sigma_i \sigma_j - \sum_i b_i \sigma_i, \qquad (11)$$
<figure><img src="image_2.png" /><figcaption>Figure 1: Evolution of A and B on a D-Wave’s annealer with respect to s = t/T, for a standard annealing</figcaption></figure>

where the $J_{ij}$'s and the $b_i$'s are hyper-parameters known respectively as couplings and local fields. By promoting the classical spins to quantum spins, one can encode the problem in a quantum Hamiltonian $\hat{H}_P$. QA introduces a transverse term $\hat{H}_C$ whose ground state (i.e. minimal configuration) is trivial and defines the global Hamiltonian:

$$ \hat{H}(t) = \mathcal{A}(t)\hat{H}_C + \mathcal{B}(t)\hat{H}_P \quad (12) $$

over a certain period $t \in [0, T]$. Initially, $\mathcal{A}(0) \gg \mathcal{B}(0)$ so that the system starts in the ground state of $\hat{H}_C$. Then, the system is annealed towards $\mathcal{A}(T) \ll \mathcal{B}(T)$ so that the dynamics at the final time is fully dictated by $\hat{H}_P$. Under non trivial conditions on the ramps A and B, one can expect to end up in the ground state of $\hat{H}_P$ which corresponds to the target configuration.

The Advantage System [18] made available by D-Wave allows to perform QA on instances of Ising models with real quantum processor units (QPU). The ramps A and B are predefined and their shape is shown on Fig. 1 $^1$. Meanwhile, the device connectivity related to the architecture of the QPU limits the number of interactions between the qubits [19], [23]. In practice, it means that a D-Wave’s annealer can handle an Ising Hamiltonian with only a limited number of non zero $J_{ij}$. The present work aims at dealing with this aspect in a novel way.

## B. Construction of the Ising Hamiltonian

As explained in [11], the minimization of an Ising Hamiltonian is equivalent to a QUBO problem via the change of variable:

$$ \sigma = 1 - 2\alpha. \quad (13) $$

For the rest of the paper, we keep the notation $\alpha$ for binary variables while $\sigma$ denotes the associated spin configuration obtained via Eq. 13. As a first task, we need to use this change of variable to reformulate Eq. 8 in the spin space. One obtains:

$$ \sigma^{\text{NNLS}} = \arg \min_{\sigma \in \{-1, 1\}^N} H_P(\sigma), \quad (14) $$

where $H_P$ is the Ising Hamiltonian:

$$ H_P(\sigma) = -\sum_{i<j} J_{ij} \sigma_i \sigma_j - \sum_i b_i \sigma_i, \quad (15) $$

involving the coupling parameters $J_{ij}$ and the local fields $b_i$ defined by:

$$ \left\{ \begin{aligned} b_i &= -\frac{1}{K} \sum_{k=1}^{K} |\mathbf{p}_i^H \mathbf{y}_k|^2 + \frac{1}{2} \sum_{j=1}^{N} |\mathbf{p}_i^H \mathbf{p}_j|^2 \\ J_{ij} &= -\frac{1}{2} |\mathbf{p}_i^H \mathbf{p}_j|^2 \end{aligned} \right. . \quad (16) $$

Generally, our Ising Hamiltonian involves non-zero couplings $J_{ij}$ for all $i < j$ which cannot be handled in practice by D-Wave’s QPU. The usual way to deal with this aspect is to use a minor embedding of the problem.

## C. Minor embedding and limitations

The QPUs currently available on the D-Wave’s Leap interface correspond to the D-Wave’s Advantage System $^2$. The topology of these QPUs is called the Pegasus topology [21], [22] and possesses a higher connectivity than the previous generation of D-Wave’s system.

To encode the problem Hamiltonian $\hat{H}_P$, an embedding scheme is used to map the original problem onto the QPU’s architecture. The common approach to deal with D-Wave’s architectures, minor embedding [19], [20], maps a logical qubit onto a chain of physical qubits, with specific parameters defining an effective Hamiltonian (i.e. that still encodes the problem to solve) compatible with the QPU’s topology. Even though such process faithfully represents the problem onto the QPU, it can dramatically increase the number of physical qubits required to represent the Hamiltonian. In fact, the embedding of highly connected Ising models of size $N$ onto current QPUs require $O(N^2)$ physical qubits [23]. We show on Fig. 2a a graph representation of an Ising Hamiltonian $H_P$ associated to a problem instance for $N = 10$ and $M = 5$. The local fields are not represented and a non zero $J_{ij}$ is represented by an edge between the vertices $i$ and $j$. Its minor embedding onto a Pegasus graph shown on Fig. 2b requires 18 qubits while the number of logical qubits is 10.

In addition, the work conducted in [23] shows that the increase of the number of qubits caused by usual embedding schemes results in a significant degradation of the time-to-solution of QA hardwares. Thus, it is crucial to optimize the pre-processing phase of a given problem before sending it on a QPU.

## D. The threshold method

The inherent structure of our activity detection problem suggests that neglecting some couplings might not dramatically affect its solution. Specifically, as shown in Eq. 16, the coupling parameters $J_{ij}$ capture cross-correlations between pilot sequences, while the correlation between the $i$-th pilot sequence and the received signal at the AP is encoded in the local field $b_i$. To reduce the number of physical qubits needed for the activity detection problem, we propose to limit the number of edges by applying a selection rule to the coupling parameters before mapping the problem onto a topology.

We propose a simple approach called the threshold method throughout this work. Given a coupling matrix $J$, we fix an

<footnote>$^1$Taken from D-Wave’s documentation available at https://docs.dwavesys.com/docs/latest/c_qpu_annnealing.html (Accessed on December 13, 2024)</footnote>

<footnote>$^2$Note that other related works on QA in MIMO systems such as [6] where conducted on the previous generation of D-Wave’s QPU, the D-Wave 2000Q system.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2: Fully connected problem (a) and its minor-embedding onto a Pegasus topology (b). We propose to cut the edges with the lowest magnitude (c) ($\eta = 0.1$ for this example) and perform a minor embedding of the cut problem (d).</figcaption></figure>

arbitrary threshold $\eta > 0$ and construct the cut matrix $J^{(\eta)}$ with the rule:

$$J_{ij}^{(\eta)} = \begin{cases} 0 & \text{if } |J_{ij}| \le \eta \\ J_{ij} & \text{otherwise} \end{cases} \qquad (17)$$

This threshold method neglects the least significant couplings, as they might not affect to much the ground state. As the pilot sequences are normalized, our original model verifies $0 \le |J_{ij}| \le 1$ (due to the Cauchy-Schwartz inequality), hence we take in practice $\eta \in [0, 1]$. Once the new coupling matrix is obtained, we build the new Ising Hamiltonian $H_P^{(\eta)}$ (the local biases are not modified):

$$H_P^{(\eta)}(\sigma) = -\sum_{i<j} J_{ij}^{(\eta)} \sigma_i \sigma_j - \sum_i b_i \sigma_i, \qquad (18)$$

on which we apply the minor embedding scheme. The ground state of this new Hamiltonian is denoted $\sigma^{\text{NNLS},(\eta)}$.

Figure 2c illustrates the graph obtained from Fig. 2a after applying a threshold of $\eta = 0.1$. This reduction in vertices decreases the physical qubits needed for embedding the cut problem (Fig. 2d) from 18 to 11.

## IV. EXPERIMENTAL PROTOCOL AND RESULTS

### A. Choice of the threshold

Before even running any experiment on a D-Wave's QPU, let us specify the interesting values to pick up for the threshold $\eta$. Indeed, a relevant threshold must fulfill the two following conditions:

1) Offer a significant reduction on the number of physical qubits required to represent the problem

2) Lead to a solution $\alpha^{\text{NNLS},(\eta)}$ that does not degrade too much the UER compared to what would be obtained with $\alpha^{\text{NNLS},(0)} = \alpha^{\text{NNLS}}$.

Given a network size $N$, we fixed $M = \lfloor N/2 \rfloor$ and randomly generated $n_{\text{samples}} = 50$ problem instances $(Y, P)$. For each of them, we applied several thresholds $\eta$. Then, we evaluated the number of physical qubits required by the embedding and the UER between the initial activity pattern and the state $\alpha^{\text{NNLS},(\eta)}$.

The results on Fig. 3a show the number of physical qubits required for a Pegasus topology against the network size $N$ (averaged over the $n_{\text{samples}}$ instances) for the values of the threshold $\eta \in \{0, 0.03, 0.06, 0.1\}$. We include $\eta = 0$ that corresponds to the original problem (as it amounts to not

<figure><img src="image_4.png" /><figcaption>Figure 3: The number of physical qubits against the system size for several $\eta$ (a) and UER degradation against the threshold for several $N$ (b).</figcaption></figure>

modify the problem Hamiltonian) for reference. Clearly, low values of the threshold $\eta \le 0.1$ already offer a significant reduction of the number of physical qubits which will be amplified as $N$ grows.

On the other hand, Fig. 3b shows the UER averaged over the $n_{\text{samples}}$ instances against the value of the threshold for some values of $N$. As expected, the averaged UER grows against $\eta$ and even reaches a plateau for $\eta \ge 0.2$ that likely corresponds to cases where all the edges of the original problems are cut. At $\eta = 0.1$, the degradation of the UER is already visible but not too significant. Hence we propose to restrict our study to $\eta \le 0.1$.

### B. Execution of a D-Wave's experiment

Given a problem Hamiltonian, one usually fixes the time of the annealing process but allows several shots [26] because of random phenomena that impact the output state. Indeed, the final configuration of a QA process is a quantum superposition, which means that probabilistic measurement effects influence the output state. Furthermore, real QPUs are subject to environmental noise despite efforts to mitigate it. Hence the output of a D-Wave's experiment with $N$ qubits is a collection of $2^N$ states rather than one unique state. For further convenience, let us denote such collection $\{\alpha_\mu, p_\mu\}_{\mu=1,...,2^N}$, where $\alpha_\mu$ span $\{0, 1\}^N$, and the $p_\mu$ are the corresponding proportions.
<figure><img src="image_5.png" /><figcaption>Figure 4: Histogram ($H_P(\alpha_\mu), p_\mu$) obtained with a random problem instance ($N = 32, M = 16, K = 100, \xi^2 = 0$)</figcaption></figure>

For our experiments, we used the specific QPU Advantage_system6.4 <fnref n="3" />. We fixed $T = 1\mu$s and performed $n_{shots} = 500$ repetitions of an annealing process on the same problem. One usually represents the results with an histogram of the values of the problem Hamiltonian obtained at the end of each shot. As an example, we performed an annealing experiment with a network populated by $N = 32$ UEs and with $M = 16$. Fig. 4 shows the obtained histogram ($H_P(\alpha_\mu), p_\mu$). The ground energy (i.e. the minimum value of $H_P$) is depicted with a dashed red line.

An ideal experiment would return a histogram peaked on this ground energy, which is of course not the case in practice. In order to evaluate the quality of the histograms as shown on Fig. 4, let us define appropriate metrics.

### C. Metrics for D-Wave’s outputs

First, we aim to quantify the ability of an annealing process to converge to the target state (the ground state of the problem Hamiltonian). To do this, we compare the empirical distribution $p_\mu$ of an experiment to the ideal one, that is a delta-function at the target state. We define the divergence $d$ as the Kullback-Leibler divergence between these two distributions:

$$d = \sum_{\mu} \delta_{\mu_{GS}}(\mu) \log \left( \frac{\delta_{\mu_{GS}}(\mu)}{p_{\mu}} \right) = - \log p_{\mu_{GS}}, \quad (19)$$

where $\mu_{GS}$ is the label of the ground state of the experiment (notice that, with this notation, $\alpha_{\mu_{GS}} = \alpha^{NNLS,(\eta)}$). One has $d \in [0, \infty)$ and the lower $d$, the better the convergence of the experiment towards the target state.

Secondly, when a threshold $\eta > 0$ is applied to the problem Hamiltonian, the UER of target state $\alpha^{NNLS,(\eta)}$ with respect to the initial activity pattern $\alpha^{(0)}$ increases. Thus, we also need to quantify the recovery performance of an experiment $\{\alpha_\mu, p_\mu\}$. To do so, we evaluate empirically the mean UER obtained over the configurations of the experiment:

$$\hat{U}_{ER} = \sum_{\mu} p_{\mu} UER(\alpha_{\mu}, \alpha^{(0)}) \quad (20)$$

One has $\hat{U}_{ER} \in [0, 1]$ and the lower the $\hat{U}_{ER}$, the better the accuracy of the experiment to recover the activity pattern.

<figure><img src="image_6.png" /><figcaption>Figure 5: Cumulative distribution functions of the divergence $d$ (a) and the empirical $\hat{U}_{ER}$ (b) over the $n_{sample} = 85$ D-Wave’s experiments</figcaption></figure>

### D. Convergence and accuracy

For the annealing experiments, we set the network size to $N = 32$ UEs and sequence length to $M = 16$, conducting $n_{samples} = 85$ experiments with four versions of the problem corresponding to threshold values $\eta \in \{0, 0.03, 0.06, 0.1\}$. This allowed us to evaluate the metrics $d$ and $\hat{U}_{ER}$, from which we deduced the empirical cumulative distribution function (CDF) of these metrics for each threshold:

$$\left\{ \begin{aligned} \text{CDF}_d(x) &= \frac{\{\#\text{experiments s.t. } d < x\}}{n_{\text{samples}}} \\ \text{CDF}_{\hat{U}_{ER}}(x) &= \frac{\{\#\text{experiments s.t. } \hat{U}_{ER} < x\}}{n_{\text{samples}}} \end{aligned} \right. \quad (21)$$

The CDFs of the divergences for different values of $\eta$ are shown in Fig. 5a. For any $d$, the curve for $\eta = 0$ is always below the others, indicating that cut problems are more likely to return their target state, than the original problem to $\alpha^{NNLS}$.

While increasing $\eta$ improves experimental convergence, recovery errors should be evaluated using the CDFs of $\hat{U}_{ER}$ for different $\eta$ values. Fig. 5b shows that the optimal threshold depends on the accuracy upper bound. For example, the threshold $\eta = 0.1$ gives the highest proportion of experiments with $\hat{U}_{ER}$ below 0.8%, but the CDF for this value of $\eta$ goes under the other CDFs when the UER is upper bounded by 2% or more. However, the CDF of $\hat{U}_{ER}$ for $\eta = 0$ is always below those for $\eta = 0.03$ and $\eta = 0.06$, which confirms that, given a certain upper bound for the value of UER, it is preferable to run a QA process with these cut problems rather than with the original one. Specifically, $\eta = 0.06$ is best for accuracy below 2%, while $\eta = 0.03$ and $\eta = 0.06$ are equivalent for higher error rates.

Ultimately, the cut problems converge better to their target state, but there’s a trade-off between convergence and accuracy. In particular, for these four optimal values of $\eta$ in the range $\eta \in [0.03, 0.06]$, the threshold permits to improve the performances.

## V. CONCLUSION

This work presents a practical QA implementation for activity detection in massive wireless networks, using a

<footnote n="3">³See https://docs.dwavesys.com/docs/latest/doc_solver_ref.html for the detailed Solver’s documentation</footnote>
generic Ising Hamiltonian to encode the NNLS detector for activity recovery. We have shown that the fully connected structure of the exact Hamiltonian leads to poor convergence due to embedding side effects. Our threshold method modifies the Hamiltonian to improve convergence towards the ground state. Although the ground state is slightly degraded compared to the activity pattern, improved convergence leads to more experiments achieving higher accuracy. Thus, we recommend using a deformed version of the problem with our method over the exact problem with poorer convergence.

This work might be extended by enhancing the threshold method with graph sparsification techniques to further reduce the number of edges in the graph of the problem.

## COMPETING INTEREST

The authors declare that there are no competing interests related to the content of this article.

## ACKNOWLEDGMENT

We are grateful for the access to the Advantage System made available by D-Wave through the D-Wave's Leap.

This work was supported by the ANR under the France 2030 program, grant "NF-PERSEUS : ANR-22-PEFT-0004".

## REFERENCES

[1] P. Popovski, C. Stefanovic, J. J. Nielsen, et al., "Wireless Access in Ultra-Reliable Low-Latency Communication (URLLC)", en, *IEEE Transactions on Communications*, vol. 67, no. 8, pp. 5783-5801, Aug. 2019. [Online]. Available: https://ieeexplore.ieee.org/document/8705373/.

[2] G. A. Akpakwu, B. J. Silva, G. P. Hancke, and A. M. Abu-Mahfouz, "A Survey on 5G Networks for the Internet of Things: Communication Technologies and Challenges", en, *IEEE Access*, vol. 6, pp. 3619-3647, 2018. [Online]. Available: http://ieeexplore.ieee.org/document/8141874/.

[3] L. Chetot, M. Egan, and J.-M. Gorce, "Active User Detection and Channel Estimation for Grant-Free Random Access with Gaussian Correlated Activity", en, in 2023 IEEE 97th Vehicular Technology Conference (VTC2023-Spring), Florence, Italy: IEEE, Jun. 2023, pp. 1-6. [Online]. Available: https://ieeexplore.ieee.org/document/10199877/.

[4] X. Chen, D. W. K. Ng, W. Yu, E. G. Larsson, N. Al-Dhahir, and R. Schober, "Massive Access for 5G and Beyond", *IEEE Journal on Selected Areas in Communications*, vol. 39, no. 3, pp. 615-637, Mar. 2021, Conference Name: IEEE Journal on Selected Areas in Communications. [Online]. Available: https://ieeexplore.ieee.org/document/9205230/?arnumber=9205230.

[5] A. Fengler, S. Haghighatshoar, P. Jung, and G. Caire, "Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access with a Massive MIMO Receiver", *IEEE Transactions on Information Theory*, vol. 67, no. 5, pp. 2925-2951, May 2021, arXiv:1910.11266 [cs]. [Online]. Available: http://arxiv.org/abs/1910.11266.

[6] M. Kim, D. Venturelli, and K. Jamieson, *Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks*, arXiv:2001.04014, Jan. 2020. [Online]. Available: http://arxiv.org/abs/2001.04014.

[7] L. Dai, B. Wang, Z. Ding, Z. Wang, S. Chen, and L. Hanzo, "A Survey of Non-Orthogonal Multiple Access for 5G", *IEEE Communications Surveys & Tutorials*, vol. 20, no. 3, pp. 2294-2323, 2018. Conference Name: IEEE Communications Surveys & Tutorials. [Online]. Available: https://ieeexplore.ieee.org/document/8357810/?arnumber=8357810.

[8] L. Liu and W. Yu, *Massive Connectivity with Massive MIMO-Part 1: Device Activity Detection and Channel Estimation*, arXiv:1706.06438, Mar. 2018. [Online]. Available: http://arxiv.org/abs/1706.06438.

[9] S. Haghighatshoar, P. Jung, and G. Caire, "Improved Scaling Law for Activity Detection in Massive MIMO Systems", in 2018 IEEE International Symposium on Information Theory (ISIT), ISSN: 2157-8117, Jun. 2018, pp. 381-385. [Online]. Available: https://ieeexplore.ieee.org/document/8437359/?arnumber=8437359.

[10] L. Marata, E. Ollila, and H. Alves, *Activity Detection for Massive Random Access using Covariance-based Matching Pursuit*, en, arXiv:2405.02741 [eess], May 2024. [Online]. Available: http://arxiv.org/abs/2405.02741.

[11] P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, "Perspectives of quantum annealing: Methods and implementations", *Reports on Progress in Physics*, vol. 83, no. 5, p. 054401, May 2020, arXiv:1903.06559 [quant-ph]. [Online]. Available: http://arxiv.org/abs/1903.06559.

[12] T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model", en, *Physical Review E*, vol. 58, no. 5, pp. 5355-5363, Nov. 1998. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevE.58.5355.

[13] M. Bernaschi, I. G.-A. Pemartín, V. Martín-Mayor, and G. Parisi, "The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps", *Nature*, vol. 631, no. 8022, pp. 749-754, Jul. 2024, arXiv:2310.07486 [cond-mat]. [Online]. Available: http://arxiv.org/abs/2310.07486.

[14] T. Albash and D. A. Lidar, "Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing", en, *Physical Review X*, vol. 8, no. 3, p. 031016, Jul. 2018. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevX.8.031016.

[15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing", *Science*, vol. 220, no. 4598, pp. 671-680, May 1983, Publisher: American Association for the Advancement of Science. [Online]. Available: https://www.science.org/doi/10.1126/science.220.4598.671.

[16] L. P. Yulianti and K. Surendro, "Implementation of Quantum Annealing: A Systematic Review", *IEEE Access*, vol. 10, pp. 73156-73177, 2022, Conference Name: IEEE Access. [Online]. Available: https://ieeexplore.ieee.org/document/9813715/?arnumber=9813715.

[17] R. Piron and C. Goursaud, *Quantum Annealing for Active User Detection in NOMA Systems*, arXiv:2411.05411, Nov. 2024. [Online]. Available: http://arxiv.org/abs/2411.05411.

[18] C. McGeoch and P. Farré, "Advantage Processor Overview", en, Jan. 2022. [Online]. Available: https://www.dwavesys.com/media/3xvdipcn/14-1058a-a-advantage_processer_overview.pdf.

[19] V. Choi, *Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem*, arXiv:0804.4884, Apr. 2008. [Online]. Available: http://arxiv.org/abs/0804.4884.

[20] V. Choi, *Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design*, arXiv:1001.3116, Jan. 2010. [Online]. Available: http://arxiv.org/abs/1001.3116.

[21] N. Dattani, S. Szalay, and N. Chancellor, *Pegasus: The second connectivity graph for large-scale quantum annealing hardware*, arXiv:1901.07636, Jan. 2019. [Online]. Available: http://arxiv.org/abs/1901.07636.

[22] K. Boothby, P. Bunyk, J. Raymond, and A. Roy, *Next-Generation Topology of D-Wave Quantum Processors*, arXiv:2003.00133 [quant-ph], Feb. 2020. [Online]. Available: http://arxiv.org/abs/2003.00133.

[23] M. S. Könz, W. Lechner, H. G. Katzgraber, and M. Troyer, "Scaling overhead of embedding optimization problems in quantum annealing", *PRX Quantum*, vol. 2, no. 4, p. 040322, Nov. 2021, arXiv:2103.15991 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2103.15991.

[24] R. Piron and C. Goursaud, *Scheduling Quantum Annealing for Active User Detection in a NOMA Network*, arXiv:2407.21547, Jul. 2024. [Online]. Available: http://arxiv.org/abs/2407.21547.

[25] K.-H. Ngo, M. Guillaud, A. Decurninge, S. Yang, and P. Schniter, *Multi-User Detection Based on Expectation Propagation for the Non-Coherent SIMO Multiple Access Channel*, en, arXiv:1905.11152 [cs, math], Jun. 2020. [Online]. Available: http://arxiv.org/abs/1905.11152.

[26] S. Boixo, T. F. Rønnow, S. V. Isakov, et al., "Quantum annealing with more than one hundred qubits", *Nature Physics*, vol. 10, no. 3, pp. 218-224, Mar. 2014, arXiv:1304.4595 [quant-ph]. [Online]. Available: http://arxiv.org/abs/1304.4595.