The key features of 5G, such as ultra-reliable low latency (URLLC) and massive machine-type communication (mMTC), are designed to address the need for low latency and the ability to connect a large number of devices in the IoT context. To support these constraints, mobile devices transmit information without previously establishing a connection with the base station (BS). This requires the Base Station to detect in real-time the active users (process known as Active User Detection (AUD)). With classical processors, one can employ the Maximum Likelihood (ML) method (the optimal detector, but suffers from high complexity and delay), or suboptimal ones (which are simpler, but less reliable). Meanwhile, quantum algorithms, particularly Durr and Hoyer (DHA) algorithm, addressing minimum searching problems, can significantly reduce complexity while keeping good performances. However, these algorithms were designed for generic problems, and their initialization and parameterization are blindly done. Nonetheless, we can have access to prior information on the system’s behavior. Therefore, in this paper, we aim to adapt and improve these quantum algorithms by using prior knowledge on the system for the AUD problem. We first propose a novel algorithm, the Improved Iterative Minimum Searching Algorithm (IIMSA) where we define more efficiently the parameters. Then, further enhancements of IIMSA are obtained thanks to a better initialization of the algorithms by exploiting classical preprocessing of the received signals with classical Conventional Correlation Receiver (CCR) or Zero Forcing (ZF). The obtained results show that these proposed algorithms operate more efficiently (i.e., less complexity with better accuracy).
The key features of 5G, such as ultra-reliable low latency (URLLC) and massive machine-type communication (mMTC), are designed to address the need for low latency and the ability to connect a large number of devices in the IoT context. To support these constraints, mobile devices transmit information without previously establishing a connection with the base station (BS). This requires the Base Station to detect in real-time the active users (process known as Active User Detection (AUD)). With classical processors, one can employ the Maximum Likelihood (ML) method (the optimal detector, but suffers from high complexity and delay), or suboptimal ones (which are simpler, but less reliable). Meanwhile, quantum algorithms, particularly Durr and Hoyer (DHA) algorithm, addressing minimum searching problems, can significantly reduce complexity while keeping good performances. However, these algorithms were designed for generic problems, and their initialization and parameterization are blindly done. Nonetheless, we can have access to prior information on the system’s behavior. Therefore, in this paper, we aim to adapt and improve these quantum algorithms by using prior knowledge on the system for the AUD problem. We first propose a novel algorithm, the Improved Iterative Minimum Searching Algorithm (IIMSA) where we define more efficiently the parameters. Then, further enhancements of IIMSA are obtained thanks to a better initialization of the algorithms by exploiting classical preprocessing of the received signals with classical Conventional Correlation Receiver (CCR) or Zero Forcing (ZF). The obtained results show that these proposed algorithms operate more efficiently (i.e., less complexity with better accuracy).
The key features of 5G, particularly URLLC and mMTC, are designed to achieve low latency and high scalability. To support these requirements, a proposed approach for random access scenarios, known as the GF scheme, eliminates handshakes between the BS and mobile users to reduce latency and accommodate a large number of devices. However, this introduces a new challenge known as AUD, where users send messages indicating their activity status, requiring the BS to detect and decode them. Decoding these messages, however, demands high computational complexity, which increases exponentially with the number of users. Several algorithms, such as ZF and CCR, have been proposed to mitigate this complexity, but they suffer from suboptimal performance. On the other hand, the optimal solution, known as ML, performs well but suffers from high complexity. To address this, quantum algorithms, like Grover's algorithm, have been proposed due to their ability to reduce search complexity while also keep detecting active users performance better. However, Grover's algorithm requires adaptation in this context, as the optimal number of iterations depends on the number of solutions, which is always unknown in the AUD case. To address this, the BBHT and DHA algorithms have been proposed to minimize complexity when the solution is unknown, but both still exhibit relatively high computational demands. In this paper, we propose an Enhanced BBHT that aims to reduce this complexity while maintaining detection performance. Our findings demonstrate that the Enhanced BBHT reduces computational complexity while keeping the performance stable.
Sixth-generation (6G) networks must deliver ultra-low latency and near-100 percent reliability to support massive-scale Internet of Things (IoT) deployments and Hyper-Reliable Low-Latency Communications (HRLLC). Grant-free access protocols permit devices to transmit without prior scheduling; nevertheless, this uncoordinated transmission introduces uncertainty at the receiver, necessitating Active User Detection (AUD) to ascertain which devices are active. Quantum search methods—most notably Grover’s algorithm—can accelerate AUD, yet they require knowing the optimal number of iterations, which depends on the (typically unknown and time-varying) number of valid solutions induced by the current activity pattern and channel/noise conditions. To overcome this, we formulate an optimization problem that optimizes the number of Grover iterations to maximize detection accuracy and minimize computational cost without any prior activity information. We then apply a Deep Q-Network (DQN) to learn, via deep reinforcement learning, an adaptive policy for selecting the iteration count. Simulation results verify that the DQN converges to an optimal strategy and outperforms two baseline schemes under varying fading conditions and active-user transmit powers.
The strong growth in the number of connected mobile devices has imposed new challenges in efficiently exploiting the available networks resources. Code Domain Non-Orthogonal Multiple Access (NOMA) technique appears as a tremendous efficient solution. Each device uses its assigned code to simultaneously transmit its data along with the user identifier, without any resource reservation exchange, saving precious wireless resources. However, this requires a receiver capable of blindly detecting the active users, which is highly complex. Driven by the promising superposition property of quantum architecture, the goal of this paper is to adapt and apply the quantum Grover algorithm for Active User Detection (AUD) purpose in the context of NOMA, to alleviate the search complexity. This adapted Grover’s algorithm is compared with the optimal classical Maximum Likelihood (ML) AUD receivers, as well as with the basic classical Conventional Correlation Receiver (CCR). A benchmark on the probability of AUD is assessed as a function of the Signal to Noise Ratio (SNR) of the received signal. We show that our adapted Grover’s algorithm is very promising in high SNR regime.
The high complexity of numerous optimal classical communication schemes, such as the Maximum Likelihood (ML) and Maximum A posteriori Probability (MAP) Multi-User Detector (MUD) designed for coherent detection or the ML and MAP Multiple-Symbol Differential Detectors (MSDD) conceived for non-coherent receivers often prevents their practical implementation. In this thesis we commence with a review and tutorial on Quantum Search Algorithms (QSA) and propose a number of hard-output and iterative Quantum-assisted MUDs (QMUD) and MSDDs (QMSDD). We employ a QSA, termed as the Durr-Hyer Algorithm (DHA) that finds the minimum of a function in order to perform near-optimal detection with quadratic reduction in the computational complexity, when compared to that of the ML MUD / MSDD. Two further techniques conceived for reducing the complexity of the DHA-based Quantum-assisted MUD (QMUD) are also proposed. These novel QMUDs / QMSDDs are employed in the uplink of various multiple access systems, such as Direct Sequence Code Division Multiple Access systems, Space Division Multiple Access systems as well as in Direct-Sequence Spreading and Slow Subcarrier Hopping SDMA systems amalgamated with Orthogonal Frequency Division Multiplexing and Interleave Division Multiple Access systems. Furthermore, we follow a quantum approach to achieve the same performance as the optimal Soft Input Soft-Output (SISO) classical detectors by replacing them with a quantum algorithm, which estimates the weighted sum of all the evaluations of a function. We propose a SISO QMUD / QMSDD scheme, which is the quantum-domain equivalent of the MAP MUD / MSDD. Both our EXtrinsic Information Transfer (EXIT) charts and Bit Error Ratio (BER) curves show that the computational complexity of the proposed QMUD / QMSDD is significantly lower than that of the MAP MUD / MSDD, whilst their performance remains equivalent. Moreover, we propose two additional families of iterative DHA-based QMUD / QMSDDs for performing near-optimal MAP detection exhibiting an even lower tunable complexity than the QWSA QMUD. Several variations of the proposed QMUD / QMSDDs have been developed and they are shown to perform better than the state-of-the-art low-complexity MUDs / MSDDs at a given complexity. Their iterative decoding performance is investigated with the aid of non-Gaussian EXIT charts.
Solutions améliorées de l'algorithme de Grover pour la détection d'utilisateurs actifs dans les résaux sans fil 5G comprend des fonctionnalités telles que Ultra-fiables à faible latence (URLLC) et Massives entre machines (mMTC) pour minimiser les délais et connecter de nombreux appareils. Cela nécessite un schéma Détection des utilisateurs Actifs (AUD), nécessitant une détection en temps réel par Base Station (BS). Maximum de Vraisemblance (ML) est le plus performant pour AUD mais il est complexe. Pour simplifier, des alternatives comme CCR et ZF ont été introduites mais ne peuvent égaler les performances de ML. Pour y remédier, nous explorons l’algorithme de Grover, connu pour ses capacités de superposition (travail avec 0 et 1), superposition (travailler avec 0 et 1 en même temps). Cependant, l’algorithme de Grover, lorsqu’il est contraint par la fonction f(x) = δ, n’est pas aussi performant que ML ; il est plus proche de CCR et de ZF. Pour atteindre les performances de ML, l’algorithme de Grover doit être modifié pour trouver la distance minimale, comme ML la distance minimale, comme le fait ML. Nous proposons un nouvel algorithme, à savoir Algorithme Amélioré de Recherche de Minimum par Itération (IIMSA), visant à améliorer les algorithmes existants Boyer-Brassard-Høyer-Tapp (BBHT) et Durr-Hoyer Algorithm (DHA), qui sont les méthodes prometteuses pour trouver le minimum à l’aide de l’algorithme de Grover afin de réduire leur complexité tout en maintenant des performances élevées. L’idée est d’utiliser n’importe quel nombre aléatoire de solutions plutôt que d’effectuer L itérations aléatoires comme le suggère DHA. Nous incorporons également des méthodes classiques telles que ZF et CCR pour améliorer leurs performances et réduire la complexité. Nous adaptons également l’algorithme de Grover dans le contexte de AUD dans cette thèse. Nous présentons également un algorithme de Grover amélioré inspiré d’une solution hybride quantique qui exploite à la fois des éléments quantiques et classiques, solution hybride quantique qui exploite à la fois des éléments quantiques et classiques. L’objectif principal est d’augmenter la probabilité de succès Ps et de réduire la complexité de l’algorithme original de Grover de l’algorithme de Grover original. Le concept consiste à utiliser moins d’itérations de Grover que le nombre optimal, dénommé Ps. que le nombre optimal, noté Lopt, et de le combiner avec la probabilité de succès classique. Nous pensons que cette approche a le potentiel de modifier le comportement de la complexité et d’obtenir une probabilité de succès élevé et d’atteindre une probabilité de succès élevée.
There are different access systems proposed for next-generation wireless communications. As the number of users in wireless systems increases, the challenge of reliable communications can be faced with the aid of exhaustive search-based signal detection. However, exhaustive maximum-likelihood searches impose a high complexity. In classical communication systems, performance improvement is achieved at the cost of substantially increased computational complexity. In this study, we consider an OFDMA downlink and SC-FDMA uplink scenario. We propose the employment of quantum search methods for signal detection. Specifically, we employ Grover's algorithm for database search in signal detection. We observe from our simulations that the error performance provided by the classical ML search is attainable by our method. As a benefit of using quantum search, the complexity imposed is substantially reduced compared to using classical ML detectors. We also compare the performance of the proposed scheme with Grover's search-based MC-CDMA detector. We investigate with multiple users as well and find that the quantum search-based scheme is effective in improving performance, while the computational burden is very low.