Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Future Telecommunication Technologies (SOFTT)

Adaptation of Grover's Quantum Algorithm to Multiuser Detection in an OCDMA System

Muhammad Idham Habibie, Jihad Hamie, Claire Goursaud

Published Dec 6, 2021• 4 citations
Publisher

Abstract

To support multiple transmissions in an optical fiber, several techniques have been studied such as Optical Code Division Multiple Access (OCDMA). In particular, the incoherent OCDMA systems are appreciated for their sim-plicity and reduced cost. However, they suffer from Multiple Access Interference (MAI), which degrades the performances. In order to cope with this MAI, several detectors have been studied. Among them, the Maximum Likelihood (ML) detector is the optimal one but it suffers from high complexity as all possibilities have to be tested prior to decision. However, thanks to the recent quantum computing advances, the complexity problem can be circumvented. As a matter of fact, quantum algorithms, such as Grover, exploit the superposition states in the quantum domain to accelerate the computation. Thus, in this paper, we propose to adapt the quantum Grover's algorithm in the context of Multi-User Detection (MUD), in an OCDMA system using non-orthogonal codes. We propose a way to adapt the received noisy signal to the constraints defined by Grover's algorithm. We further evaluate the probability of success in detecting the active users for different noise levels. Aside from the complexity reduction, simulations show that our proposal has a high probability of detection when the received signal is not highly altered. We show the benefits of our proposal compared to the classical and the optimal ML detector.

DOI
10.1109/softt54252.2021.9673141

Related papers

A Performance Comparison of Classical and Quantum Algorithm for Active User Detection

Muhammad Idham Habibie, Jihad Hamie, Claire Goursaud

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.

IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)•Jul 4, 2022•6 citations

Adaptation de l’algorithme quantique de Grover à la détection multi-utilisateurs dans un système OCDMA

Muhammad Idham Habibie, Jihad Hamie, Claire Goursaud

Pour prendre en charge les transmissions multiples dans une fibre optique, plusieurs techniques ont été étudiées, comme l’accès multiple par répartition en code (OCDMA). En particulier, les systèmes OCDMA incohérents sont appréciés pour leur simplicité. Cependant, ils souffrent de l’interférence d’accès multiple (MAI), qui dégrade les performances. Afin de faire face à cette MAI, plusieurs détecteurs ont été étudiés. Parmi eux, le Maximum Likelihood (ML) est le meilleur. Mais il est très coûteux, car il nécessite tester toutes les possibilités avant de prendre une décision. Cependant, grâce aux récentes avancées de l’informatique quantique, ce problème de complexité peut être contourné. En effet, les algorithmes quantiques, tels que Grover, exploitent les états de superposition dans le domaine quantique et permettent d’accélérer le calcul. Ainsi, dans cet article, nous proposons d’adapter l’algorithme quantique de Grover dans le contexte de la détection multi-utilisateurs, dans un système OCDMA utilisant des codesnon-orthogonaux. Nous présentons un moyen d’adapter le signal bruité reçu aux contraintes définies par l’algorithme de Grover, et évaluons ensuite la probabilité de succès du récepteur quantique. Nous montrons les avantages de notre proposition par rapport au détecteur classique et au détecteur ML optimal.

•Aug 28, 2023•0 citations

Quantum Search Algorithms, Quantum Wireless, and a Low-Complexity Maximum Likelihood Iterative Quantum Multi-User Detector Design

Panagiotis Botsinis, Soon Xin Ng, Lajos Hanzo

The high complexity of numerous optimal classic communication schemes, such as the maximum likelihood (ML) multiuser detector (MUD), often prevents their practical implementation. In this paper, we present an extensive review and tutorial on quantum search algorithms (QSA) and their potential applications, and we employ a QSA that finds the minimum of a function in order to perform optimal hard MUD with a quadratic reduction in the computational complexity when compared to that of the ML MUD. Furthermore, we follow a quantum approach to achieve the same performance as the optimal soft-input soft-output classic detectors by replacing them with a quantum algorithm, which estimates the weighted sum of a function's evaluations. We propose a soft-input soft-output quantum-assisted MUD (QMUD) scheme, which is the quantum-domain equivalent of the ML MUD. We then demonstrate its application using the design example of a direct-sequence code division multiple access system employing bit-interleaved coded modulation relying on iterative decoding, and compare it with the optimal ML MUD in terms of its performance and complexity. Both our extrinsic information transfer charts and bit error ratio curves show that the performance of the proposed QMUD and that of the optimal classic MUD are equivalent, but the QMUD's computational complexity is significantly lower.

IEEE Access•Jan 1, 2013•64 citations

Performance evaluation of quantum based multi-user detector

Sándor Imre, Ferenc Balázs

Future wired and wireless communication systems will employ pure or combined code division multiple access (CDMA) techniques, such as in the European 3G mobile UMTS or power line communications system, but also several 4G proposals include, for example, multicarrier (MC) CDMA. Previous investigations discovered the drawbacks of single user detectors (SUD), which are widely employed in narrowband IS-95 CDMA systems, and were forced to develop suitable multiuser detection schemes to increase the efficiency against interference. However, at this moment there are only suboptimal solutions available became of the rather high complexity of optimal detectors. One of the possible receiver technologies may be quantum assisted computing devices which allow high level parallelism in computation. The first commercial devices are estimated for the next years, which meets the advent of 3G and 4G systems. We analyze the error probability and give tight bounds in a static and dynamically changing environment for a novel quantum computation based quantum multi-user detection (QMUD) algorithm, employing a quantum counting algorithm, which provides an optimal solution.

IEEE International Symposium on Spread Spectrum Techniques and Applications (ISSSTA)•Jun 25, 2003•6 citations

Grover's Quantum Search for the Signal Detection of OFDMA Downlink and SC-FDMA Uplink

Swaraj Mondal, Nazmun Nahar Zarin, Mohammad Ismat Kadir

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.

International Conference on Electrical Engineering and Information Communication Technology•May 2, 2024•1 citation

Quantum-assisted multi-user wireless systems

Panagiotis Botsinis

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.

•Mar 1, 2015•0 citations
To support multiple transmissions in an optical fiber, several techniques have been studied such as Optical Code Division Multiple Access (OCDMA). In particular, the incoherent OCDMA systems are appreciated for their sim-plicity and reduced cost. However, they suffer from Multiple Access Interference (MAI), which degrades the performances. In order to cope with this MAI, several detectors have been studied. Among them, the Maximum Likelihood (ML) detector is the optimal one but it suffers from high complexity as all possibilities have to be tested prior to decision. However, thanks to the recent quantum computing advances, the complexity problem can be circumvented. As a matter of fact, quantum algorithms, such as Grover, exploit the superposition states in the quantum domain to accelerate the computation. Thus, in this paper, we propose to adapt the quantum Grover's algorithm in the context of Multi-User Detection (MUD), in an OCDMA system using non-orthogonal codes. We propose a way to adapt the received noisy signal to the constraints defined by Grover's algorithm. We further evaluate the probability of success in detecting the active users for different noise levels. Aside from the complexity reduction, simulations show that our proposal has a high probability of detection when the received signal is not highly altered. We show the benefits of our proposal compared to the classical and the optimal ML detector.
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.
Pour prendre en charge les transmissions multiples dans une fibre optique, plusieurs techniques ont été étudiées, comme l’accès multiple par répartition en code (OCDMA). En particulier, les systèmes OCDMA incohérents sont appréciés pour leur simplicité. Cependant, ils souffrent de l’interférence d’accès multiple (MAI), qui dégrade les performances. Afin de faire face à cette MAI, plusieurs détecteurs ont été étudiés. Parmi eux, le Maximum Likelihood (ML) est le meilleur. Mais il est très coûteux, car il nécessite tester toutes les possibilités avant de prendre une décision. Cependant, grâce aux récentes avancées de l’informatique quantique, ce problème de complexité peut être contourné. En effet, les algorithmes quantiques, tels que Grover, exploitent les états de superposition dans le domaine quantique et permettent d’accélérer le calcul. Ainsi, dans cet article, nous proposons d’adapter l’algorithme quantique de Grover dans le contexte de la détection multi-utilisateurs, dans un système OCDMA utilisant des codesnon-orthogonaux. Nous présentons un moyen d’adapter le signal bruité reçu aux contraintes définies par l’algorithme de Grover, et évaluons ensuite la probabilité de succès du récepteur quantique. Nous montrons les avantages de notre proposition par rapport au détecteur classique et au détecteur ML optimal.
The high complexity of numerous optimal classic communication schemes, such as the maximum likelihood (ML) multiuser detector (MUD), often prevents their practical implementation. In this paper, we present an extensive review and tutorial on quantum search algorithms (QSA) and their potential applications, and we employ a QSA that finds the minimum of a function in order to perform optimal hard MUD with a quadratic reduction in the computational complexity when compared to that of the ML MUD. Furthermore, we follow a quantum approach to achieve the same performance as the optimal soft-input soft-output classic detectors by replacing them with a quantum algorithm, which estimates the weighted sum of a function's evaluations. We propose a soft-input soft-output quantum-assisted MUD (QMUD) scheme, which is the quantum-domain equivalent of the ML MUD. We then demonstrate its application using the design example of a direct-sequence code division multiple access system employing bit-interleaved coded modulation relying on iterative decoding, and compare it with the optimal ML MUD in terms of its performance and complexity. Both our extrinsic information transfer charts and bit error ratio curves show that the performance of the proposed QMUD and that of the optimal classic MUD are equivalent, but the QMUD's computational complexity is significantly lower.
Future wired and wireless communication systems will employ pure or combined code division multiple access (CDMA) techniques, such as in the European 3G mobile UMTS or power line communications system, but also several 4G proposals include, for example, multicarrier (MC) CDMA. Previous investigations discovered the drawbacks of single user detectors (SUD), which are widely employed in narrowband IS-95 CDMA systems, and were forced to develop suitable multiuser detection schemes to increase the efficiency against interference. However, at this moment there are only suboptimal solutions available became of the rather high complexity of optimal detectors. One of the possible receiver technologies may be quantum assisted computing devices which allow high level parallelism in computation. The first commercial devices are estimated for the next years, which meets the advent of 3G and 4G systems. We analyze the error probability and give tight bounds in a static and dynamically changing environment for a novel quantum computation based quantum multi-user detection (QMUD) algorithm, employing a quantum counting algorithm, which provides an optimal solution.
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.
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.