A quantum search based signal detection for MIMO-OFDM systems

Fei Li, Lizhi Zhou, Li Liu, Haibo Li

Published May 1, 2011• 4 citations

Abstract

Multiple input multiple output-orthogonal frequency division multiplexing (MIMO-OFDM) is considered as candidates for future broadband wireless services. In this paper a novel signal detection scheme based on Grover's quantum search algorithm is proposed for MIMO-OFDM systems. Grover's quantum search algorithm is based on the concept and principles of quantum computing, such as quantum bit, quantum register and quantum parallelism. An analysis is given to the theoretical basis of Grover's algorithm and the performance of Grover's algorithm is evaluated. A novel signal detector based on Grover's algorithm (GD) for MIMO-OFDM system is proposed. The simulation results show that the proposed detector has more powerful properties in bit error rate than MMSE detector and VBLAST-MMSE detector. The performance of the proposed GD detector is close to optimal when the failure probability is 0.001. When the failure probability is 0.00001, the performance of GD detector declines. In this case, our proposed improved Grover's algorithm based detector is still close to the optimal ML detector. The complexity of GD and IGD is O(√N). It's much better than classical ML detector which complexity is O(N).

DOI: 10.1109/cts.2011.5898934

Related papers

Grover's Quantum Search Based Data Detection Algorithm for MIMO System

Jing Shen, Muqing Wu, Linlin Luan

Abstract Maximum like-lihood (ML) algorithm is the optimal detection scheme for the data detection of multiple-input multiple-output (MIMO) communication systems, but it has a high complexity in its preprocessing. For good performance and low complexity, a new Grover’s Quantum Search (GS) based data detection algorithm for MIMO system is proposed. It can increase the probability amplitude of solutions while reducing the probability amplitude of non-solutions. By Grover’s iterative process, the probability amplitude of solutions can reach maximum. So it can get the solutions after measurement with a high probability. The simulation results show that the proposed data detection algorithm for MIMO system has a very close to ML based data detection in Bit Error Rate (BER) performance, but it has lower complexity than ML based data detection algorithm.

International Journal of Advancements in Computing TechnologyJan 31, 20127 citations

Grover's QSA based MC-CDMA Detector

Saif Hasan Abdulnabi, Saleem Mohammed Ridha Taha

Multi-Carrier Code Division Multiple Access (MC-CDMA) is considered as one of the major techniques used in 4G broadband wireless services.It combines the advantages of the OFDM systems, of robustness to the multi path effects, and the advantages of CDMA systems, which are high privacy and security.However, a problem appears in the detection of transmitted information because of the effect of noise, fading and other multipath effects.In this paper, Grover's quantum search algorithm based MC-CDMA detector is proposed as a solution for this problem.Grover's quantum search algorithm is based on the concepts of quantum computing, such as quantum bit, quantum register and quantum parallelism.The performance of the proposed detector was realized and compared with previous works.The simulation results showed the superiority of the proposed detector in BER performance.The performance of the proposed detector showed that it is very close to the optimum.

International Journal of Computer ApplicationsApr 22, 20151 citation

ML Criterion Based Signal Detection of a MIMO-OFDM System Using Quantum and Semi-Quantum Assisted Modified DHA/BBHT Search Algorithm

Subhadeep Mondal, Mostafizur Rahaman Laskar, Amit Kumar Dutta

The quantum search algorithm (QSA) is one of the most recent developments in the era of quantum signal processing (QSP) and quantum information theory (QIT). It shows a faster performance in finding the solutions of system such as multiple-input multiple-output (MIMO) communication system, quantum error correction and others with a polynomial order over the classical one. Grover's algorithm is one of the first proposed QSA in identifying the index number of the solution of a system, whose solutions are known to the oracle. A further improved QSA called Boyer-Brassard-Høyer-Tapp (BBHT) is followed by the Durr-Hoyer algorithm (DHA), which proposes to find the solutions, while the exact number of the solutions is not known. In this treatise, we propose two modifications to the existing DHA and BBHT algorithms. In DHA, we propose a semi-quantum framework, where after each iteration in DHA, the non-solution points are removed in classical framework. This makes the data set iteratively shorter. In the case of BBHT algorithm, we propose to choose the Grover search number based on the Gamma distribution instead of the uniform one, which gives more chances to the new larger values to improve probability of success. The performance of the proposed QSAs demonstrates plausible improvement in search success performance as compared to their existing BBHT and DHA counterparts. Numerical simulations are conducted with the proposed QSA algorithms on a MIMO orthogonal frequency division multiplexing (OFDM) system to demonstrate the performance improvement.

IEEE Transactions on Vehicular TechnologyJan 29, 202121 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 TechnologyMay 2, 20241 citation

Quantum-Native Maximum Likelihood Detection in Random Access Channel with Overloaded MIMO

Hyoga Iizumi, Naoki Ishikawa, Shunsuke Uehashi +3 more

In this paper, we propose a quantum-native formulation of maximum likelihood detection (MLD) for overloaded multiple-input multiple-output (MIMO) systems in a random access channel, where numerous user terminals share the same channel resource and asynchronously transmit signals. Classical linear detectors suffer from significant performance degradation in this scenario, whereas the exhaustive-search MLD achieves the optimal performance but incurs an exponential computational complexity. To overcome this trade-off, we formulate the MLD as a binary optimization problem and solve it via Grover adaptive search (GAS) -- a quantum exhaustive search algorithm offering quadratic speedup in fault-tolerant quantum computing. We then introduce a search space reduction technique to substantially decrease the required computational resources. In addition, we investigate efficient parameter settings for GAS through probability analysis to improve convergence performance. We demonstrate that the proposed detector achieves the optimal detection performance while reducing the required Grover rotation count to reach the solution by up to approximately 65% compared with the conventional GAS, showing its potential as a viable solution for future quantum-accelerated wireless systems.

eess.SPCross-listedarXiv:2605.19389May 20, 20260 citations

Maximum Likelihood Detection Based on Warm-start Quantum Optimization Algorithm

Xinlin He, Han Zeng, Xutao Yu

Quantum computing, with its powerful parallel computing capabilities, is considered one of the promising candidates for solving complex communication problems. This paper proposes a new detection scheme by combining quantum approximation optimization algorithms (QAOA) with maximum likelihood (ML) detection. The scheme addresses the computational complexity problem faced by ML detection in large-scale multiple-input multiple-output (MIMO) channels. The primary focus lies in the warm-start optimization based on the QAOA-ML detection. We use semi-definite relaxation (SDR) to calculate the temporary solution of ML for initializing quantum circuits. The feasibility of the scheme is verified through simulation. The proposed detection scheme is evaluated and compared with classical computer-based ML detection and Minimum Mean Square Error (MMSE) detection, demonstrating similar bit error rate (BER) performance. The enormous potential of quantum algorithms in computing power solving the drawbacks of traditional ML detection algorithms provides new possibilities for improving detection efficiency.

Information Communication Technologies Conference (ICTC)May 10, 20242 citations