In the VBLAST system, linear detection has low computational complexity, but its detection performance is poor. Conversely, Maximum Likelihood(ML) detection achieves optimal detection performance, but its computational complexity grows exponentially with the number of transmit antennas and the signal modulation order. This is a typical NP problem. To reduce the computational complexity of ML detection in the VBLAST system, while at the same time retaining optimal detection performance, an improved ML detection method is proposed in this paper. Both the quantum Grover and Grover-Long algorithms are used in the ML detection algorithm for the VBLAST system, and the complexity and performance of the algorithm are simulated. The simulation results show that not only is the computational complexity of Grover algorithm detection square accelerated, but also that the detection performance of the algorithm is close to that of ML detection. Moreover,this is the first time that a quantum algorithm is used to solve an engineering problem.In the VBLAST system, linear detection has low computational complexity, but its detection performance is poor. Conversely, Maximum Likelihood(ML) detection achieves optimal detection performance, but its computational complexity grows exponentially with the number of transmit antennas and the signal modulation order. This is a typical NP problem. To reduce the computational complexity of ML detection in the VBLAST system, while at the same time retaining optimal detection performance, an improved ML detection method is proposed in this paper. Both the quantum Grover and Grover-Long algorithms are used in the ML detection algorithm for the VBLAST system, and the complexity and performance of the algorithm are simulated. The simulation results show that not only is the computational complexity of Grover algorithm detection square accelerated, but also that the detection performance of the algorithm is close to that of ML detection. Moreover,this is the first time that a quantum algorithm is used to solve an engineering problem.

Scientia Sinica InformationisJan 1, 20131 citation

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.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

A quantum search based signal detection for MIMO-OFDM systems

Fei Li, Lizhi Zhou, Li Liu +1 more

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).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).

May 1, 20114 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.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

Quantum-Native Formulation of 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 in random access channel with overloaded multiple-input multiple-output (MIMO), where a number of user terminals share the same channel resource and asynchronously transmit signals. Classical low-complexity linear detectors suffer from significant performance degradation in this scenario, while the exhaustive-search-based maximum likelihood detection achieves the optimal performance but induces an exponential increase in time complexity. To strike this fundamental tradeoff, we formulate the maximum likelihood detection as a binary optimization problem and solve it via the Grover adaptive search (GAS), a quantum exhaustive search algorithm offering quadratic speedup. We further introduce a search space reduction technique using quantum W states and controlled-H gates, which substantially decreases complexity. In addition, we investigate the effects of efficient parameter settings in GAS. Our simulation results show that the proposed detector achieved the optimal detection performance while reducing the query complexity, thereby highlighting its potential as a solution for future quantum-accelerated overloaded MIMO systems.In this paper, we propose a quantum-native formulation of maximum likelihood detection in random access channel with overloaded multiple-input multiple-output (MIMO), where a number of user terminals share the same channel resource and asynchronously transmit signals. Classical low-complexity linear detectors suffer from significant performance degradation in this scenario, while the exhaustive-search-based maximum likelihood detection achieves the optimal performance but induces an exponential increase in time complexity. To strike this fundamental tradeoff, we formulate the maximum likelihood detection as a binary optimization problem and solve it via the Grover adaptive search (GAS), a quantum exhaustive search algorithm offering quadratic speedup. We further introduce a search space reduction technique using quantum W states and controlled-H gates, which substantially decreases complexity. In addition, we investigate the effects of efficient parameter settings in GAS. Our simulation results show that the proposed detector achieved the optimal detection performance while reducing the query complexity, thereby highlighting its potential as a solution for future quantum-accelerated overloaded MIMO systems.

IEEE Vehicular Technology ConferenceOct 19, 20250 citations

Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection

Jingjing Cui, Yifeng Xiong, Soon Xin Ng +1 more

Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithm (QAOA) constitutes a promising candidate for demonstrating tangible quantum advantages based on NISQ devices. In this paper, we consider the maximum likelihood (ML) detection problem of binary symbols transmitted over a multiple-input and multiple-output (MIMO) channel, where finding the optimal solution is exponentially hard using classical computers. Here, we apply the QAOA for the ML detection by encoding the problem of interest into a level- $p$ QAOA circuit having $2p$ variational parameters, which can be optimized by classical optimizers. This level- $p$ QAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately in $p$ consecutive rounds. More explicitly, we first encode the optimal solution of the ML detection problem into the ground state of a problem Hamiltonian. Using the quantum adiabatic evolution technique, we provide both analytical and numerical results for characterizing the evolution of the eigenvalues of the quantum system used for ML detection. Then, for level-1 QAOA circuits, we derive the analytical expressions of the expectation values of the QAOA and discuss the complexity of the QAOA based ML detector. Explicitly, we evaluate the computational complexity of the classical optimizer used and the storage requirement of simulating the QAOA. Finally, we evaluate the bit error rate (BER) of the QAOA based ML detector and compare it both to the classical ML detector and to the classical minimum mean squared error (MMSE) detector, demonstrating that the QAOA based ML detector is capable of approaching the performance of the classical ML detector.Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithm (QAOA) constitutes a promising candidate for demonstrating tangible quantum advantages based on NISQ devices. In this paper, we consider the maximum likelihood (ML) detection problem of binary symbols transmitted over a multiple-input and multiple-output (MIMO) channel, where finding the optimal solution is exponentially hard using classical computers. Here, we apply the QAOA for the ML detection by encoding the problem of interest into a level-$p$QAOA circuit having$2p$variational parameters, which can be optimized by classical optimizers. This level-$p$QAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately in$p$consecutive rounds. More explicitly, we first encode the optimal solution of the ML detection problem into the ground state of a problem Hamiltonian. Using the quantum adiabatic evolution technique, we provide both analytical and numerical results for characterizing the evolution of the eigenvalues of the quantum system used for ML detection. Then, for level-1 QAOA circuits, we derive the analytical expressions of the expectation values of the QAOA and discuss the complexity of the QAOA based ML detector. Explicitly, we evaluate the computational complexity of the classical optimizer used and the storage requirement of simulating the QAOA. Finally, we evaluate the bit error rate (BER) of the QAOA based ML detector and compare it both to the classical ML detector and to the classical minimum mean squared error (MMSE) detector, demonstrating that the QAOA based ML detector is capable of approaching the performance of the classical ML detector.

arXiv:2107.05020IEEE Transactions on CommunicationsJun 22, 202241 citations

p

QAOA circuit having

2p

variational parameters, which can be optimized by classical optimizers. This level-

p

QAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately in

p

consecutive rounds. More explicitly, we first encode the optimal solution of the ML detection problem into the ground state of a problem Hamiltonian. Using the quantum adiabatic evolution technique, we provide both analytical and numerical results for characterizing the evolution of the eigenvalues of the quantum system used for ML detection. Then, for level-1 QAOA circuits, we derive the analytical expressions of the expectation values of the QAOA and discuss the complexity of the QAOA based ML detector. Explicitly, we evaluate the computational complexity of the classical optimizer used and the storage requirement of simulating the QAOA. Finally, we evaluate the bit error rate (BER) of the QAOA based ML detector and compare it both to the classical ML detector and to the classical minimum mean squared error (MMSE) detector, demonstrating that the QAOA based ML detector is capable of approaching the performance of the classical ML detector.