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 Access

Quantum Search-Aided Multi-User Detection for Sparse Code Multiple Access

Wenjing Ye, Wei Chen, Xin Guo, Chen K. Sun, Lajos Hanzo

Published Jan 1, 2019• 11 citations
Publisher

Abstract

With the explosive proliferation of mobile devices, the scarcity of communication resources has emerged as a critical issue in the next generation (NG) communication systems. To overcome this, non-orthogonal multiple access (NOMA) has been shown to provide a beneficial spectral efficiency gain, while supporting massive connectivity. Sparse code multiple access (SCMA) is one of the NOMA schemes, but its application is hampered by its high-complexity multi-user detection. Fortunately, quantum search techniques were shown to substantially reduce the complexity of multi-user detectors (MUD). However, the quantum search-aided multiuser detection of SCMA is an open problem at the time of writing. Hence, we conceive a pair of quantum search-aided MUDs for SCMA, namely, a quantum-assisted message passing algorithm (Q-MPA) -based MUD and a quantum-assisted sphere decoder-based MPA (QSD-MPA) MUD.

DOI
10.1109/access.2019.2910776

Related papers

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

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

Quantum Annealing-Aided Multi-User Detection: An Application to Uplink Non-Orthogonal Multiple Access

Kouki Yonaga, Kenichi Takizawa

A new method to realize computation of the log-likelihood ratio (LLR) in multi-user detection (MUD) by quantum annealing (QA) is proposed herein. One metaheuristic algorithm for solving combinatorial optimization problems is QA. Recently, QA has been applied in various fields to hasten computations. This study specifically examines the application of QA in up-link non-orthogonal multiple access (UL-NOMA) that employs iterative MUD. Our proposed method, QA-aided MUD, uses QA to calculate LLR in iterative MUD. We tested QA-aided MUD with a D-Wave quantum annealer. The error rate analysis demonstrates that QA-aided MUD has comparable performance to that of conventional MUD method. Furthermore, when the annealing time was set to 20 µs, we demonstrated than that the total computation time is 1/10 of the computation time necessary when using a digital computer. We also evaluated the convergence behavior of QA-aided MUD through evolution of mutual information. The results indicate that QA-assisted MUD has almost identical convergence performance to that of the conventional MUD method for LLR calculations.

International Conference on Communications•May 28, 2023•7 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

Low-complexity iterative quantum multi-user detection in SDMA systems

Panagiotis Botsinis, Soon Xin Ng, Lajos Hanzo

The potentially excessive complexity of the Maximum Likelihood Multi-User Detector (ML MUD) in large-scale Spatial Division Multiple Access (SDMA) systems dictates the employment of low-complexity sub-optimal MUDs in the context of conventional systems. However, this limitation was circumvented by the recently proposed Dürr-Høyer Algorithm (DHA)-aided Quantum Weighted Sum Algorithm (QWSA)-based Quantum Multi-User Detector (QMUD) employed for performing optimal ML iterative detection in SDMA systems. Focusing our attention on the QWSA, we analyse the QMUD and the evolution of the quantum system with the aid of a simple SDMA uplink scenario. We characterize the performance of the DHA-QWSA QMUD advocated, which is capable of matching the performance of the ML MUD both in terms of its EXIT charts and BER curves.

International Conference on Communications•Jun 1, 2014•11 citations

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

Muhammad Idham Habibie, Jihad Hamie, Claire Goursaud

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.

IEEE International Symposium on Future Telecommunication Technologies (SOFTT)•Dec 6, 2021•4 citations
With the explosive proliferation of mobile devices, the scarcity of communication resources has emerged as a critical issue in the next generation (NG) communication systems. To overcome this, non-orthogonal multiple access (NOMA) has been shown to provide a beneficial spectral efficiency gain, while supporting massive connectivity. Sparse code multiple access (SCMA) is one of the NOMA schemes, but its application is hampered by its high-complexity multi-user detection. Fortunately, quantum search techniques were shown to substantially reduce the complexity of multi-user detectors (MUD). However, the quantum search-aided multiuser detection of SCMA is an open problem at the time of writing. Hence, we conceive a pair of quantum search-aided MUDs for SCMA, namely, a quantum-assisted message passing algorithm (Q-MPA) -based MUD and a quantum-assisted sphere decoder-based MPA (QSD-MPA) MUD.
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.
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.
A new method to realize computation of the log-likelihood ratio (LLR) in multi-user detection (MUD) by quantum annealing (QA) is proposed herein. One metaheuristic algorithm for solving combinatorial optimization problems is QA. Recently, QA has been applied in various fields to hasten computations. This study specifically examines the application of QA in up-link non-orthogonal multiple access (UL-NOMA) that employs iterative MUD. Our proposed method, QA-aided MUD, uses QA to calculate LLR in iterative MUD. We tested QA-aided MUD with a D-Wave quantum annealer. The error rate analysis demonstrates that QA-aided MUD has comparable performance to that of conventional MUD method. Furthermore, when the annealing time was set to 20 µs, we demonstrated than that the total computation time is 1/10 of the computation time necessary when using a digital computer. We also evaluated the convergence behavior of QA-aided MUD through evolution of mutual information. The results indicate that QA-assisted MUD has almost identical convergence performance to that of the conventional MUD method for LLR calculations.
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.
The potentially excessive complexity of the Maximum Likelihood Multi-User Detector (ML MUD) in large-scale Spatial Division Multiple Access (SDMA) systems dictates the employment of low-complexity sub-optimal MUDs in the context of conventional systems. However, this limitation was circumvented by the recently proposed Dürr-Høyer Algorithm (DHA)-aided Quantum Weighted Sum Algorithm (QWSA)-based Quantum Multi-User Detector (QMUD) employed for performing optimal ML iterative detection in SDMA systems. Focusing our attention on the QWSA, we analyse the QMUD and the evolution of the quantum system with the aid of a simple SDMA uplink scenario. We characterize the performance of the DHA-QWSA QMUD advocated, which is capable of matching the performance of the ML MUD both in terms of its EXIT charts and BER curves.
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.