Quantum approximate optimization algorithm (QAOA) with layer depthpis promising near-optimum performance and low complexity for NP-hard maximum-likelihood (ML) detection inn×nmulti-input multi-output (MIMO) systems. Experimental challenges for ML detection on Noisy Intermediate-Scale Quantum (NISQ) computers arise from accumulated errors with largepandn. Recursive QAOA (RQAOA) is promising with smallpby reducing complexity overnsteps. In this article, we modify RQAOA forp≪nwith cost sorting and post-selection inm≪nsteps, and then integrate it with majority voting (MV) and successive interference cancellation (SIC) into the QAOA-MVSIC algorithm to tackle experimental challenges. We truncate QAOA circuits to further improve experimental feasibility. Simulations withn= 24 and 12 for BPSK and QPSK modulations, respectively, show near-optimum bit-error rate (BER) withp= 1 andm≤ 4. Truncated version requiresO(m n p) quantum andO(m n2) classical operations with low complexity. We experimentally implement QAOA combined with MV (QAOA-MV) fornϵ [17; 64] in IBM Eagle processor by observing superior performance of QAOA-MV over QAOA and reducing problem dimensions by at leastn/4. We generalize QAOA as cost-restricted uniform sampling (CRUS) oracle and approximately simulate forn≤ 128 to obtain comparison benchmark for future QAOA experiments.
Quantum approximate optimization algorithm (QAOA) with layer depthpis promising near-optimum performance and low complexity for NP-hard maximum-likelihood (ML) detection inn×nmulti-input multi-output (MIMO) systems. Experimental challenges for ML detection on Noisy Intermediate-Scale Quantum (NISQ) computers arise from accumulated errors with largepandn. Recursive QAOA (RQAOA) is promising with smallpby reducing complexity overnsteps. In this article, we modify RQAOA forp≪nwith cost sorting and post-selection inm≪nsteps, and then integrate it with majority voting (MV) and successive interference cancellation (SIC) into the QAOA-MVSIC algorithm to tackle experimental challenges. We truncate QAOA circuits to further improve experimental feasibility. Simulations withn= 24 and 12 for BPSK and QPSK modulations, respectively, show near-optimum bit-error rate (BER) withp= 1 andm≤ 4. Truncated version requiresO(m n p) quantum andO(m n2) classical operations with low complexity. We experimentally implement QAOA combined with MV (QAOA-MV) fornϵ [17; 64] in IBM Eagle processor by observing superior performance of QAOA-MV over QAOA and reducing problem dimensions by at leastn/4. We generalize QAOA as cost-restricted uniform sampling (CRUS) oracle and approximately simulate forn≤ 128 to obtain comparison benchmark for future QAOA experiments.
Quantum approximate optimization algorithm (QAOA) promises near-optimal decoding for n × n massive multiple-input multiple-output (mMIMO) systems. QAOA-MVSIC, recently formulated for Noisy Intermediate-Scale Quantum (NISQ) settings, combines truncated QAOA of small depth p with majority voting (MV) and successive-interference cancellation (SIC) for robustness to noise. We introduce RRT-Q, a recursive, repetitive extension of truncated QAOA-MVSIC, and demonstrate strong noise tolerance, markedly outperforming QAOA and QAOA-MVSIC. We report, to our knowledge, the first experimental bit-error-rate (BER) results for QAOA-based decoding: on an IBM Eagle processor, performance matches semidefinite relaxation with Gaussian randomization (SDR-GR) at signal-to-noise ratio (SNR) ≤ 10 dB for n = 120 (BPSK) and n = 32 (QPSK). Matrix-product-state tensor-network simulations up to n ≤ 256 reach SDR-GR with p = 1. We derive RRT-Q complexity bounds; empirically, we observe that for n ≤ 256 and SNR ≤ 10 dB with Ns QAOA samples, average cost per instance is n α +Ns n β (classical) and Nsn η (quantum) with α ∈ [2.8, 3.4], β ∈ [1.8, 2.2] and η ∈ [1.6, 2.2] while RRT-Q-ML version with maximum-likelihood detection at the final step adds n ζ term with ζ ∈ [2.7, 4.6]. The tunable, low-complexity design targets near-optimal NISQ performance and is expected to scale to the fault-tolerant regime (n ≫ 256).
Quantum-approximate optimization algorithm (QAOA) is promising in Noisy Intermediate-Scale Quantum (NISQ) computers with applications for NP-hard combinatorial optimization problems. It is recently utilized for NP-hard maximum-likelihood (ML) detection problem with challenges of optimization, simulation and performance analysis forn×nmultiple-input multiple output (MIMO) systems with largen. QAOA is recently applied by Farhi et al. on infinite size limit of Sherrington-Kirkpatrick (SK) model with a cost model including only quadratic terms. In this article, we extend the model by including also linear terms and then realize SK modeling of massive MIMO ML detection. The proposed design targets near ML performance while with complexity includingO(16p) initial operations independent from problem instance and sizenfor optimizing QAOA angles andO(n2p) quantum operations for each instance. We provide both optimized and extrapolated angles forp∈ [1, 14] and signal-to-noise (SNR)p≥ 4 for 25×25 and 12 × 12 MIMO systems modulated with BPSK and QPSK, respectively. We present two conjectures about concentration properties of QAOA and near-optimum performance for next generation massive MIMO systems coveringn< 300.
Quantum-approximate optimization algorithm (QAOA) is promising in Noisy Intermediate-Scale Quantum (NISQ) computers with applications for NP-hard combinatorial optimization problems. It is recently utilized for NP-hard maximum-likelihood (ML) detection problem with fundamental challenges of optimization, simulation and performance analysis for n x n multiple-input multiple output (MIMO) systems with large n. QAOA is recently applied by Farhi et al. on infinite size limit of Sherrington-Kirkpatrick (SK) model with a cost model including only quadratic terms. In this article, we extend application of QAOA on SK model by including also linear terms and then realize SK modeling of massive MIMO ML detection by ensuring independence from specific problem instance and size n while preserving computational complexity of O(16p) designed by Farhi et al. We provide both optimized and extrapolated angles for p in the set [1, 14] and signal-to-noise (SNR) < 12 dB achieving near-optimum ML performance for 25 x 25 MIMO system with p >= 4 in extensive simulations where 236500 different QAOA circuits are simulated. We present two conjectures about the concentration properties of QAOA and its near-optimum performance for massive MIMO systems with large sizes covering n < 300 promising significant performance for next generation massive MIMO systems.
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-pQAOA circuit having2pvariational parameters, which can be optimized by classical optimizers. This level-pQAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately inpconsecutive 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.
In the massive multiple-input and multiple-output (Massive MIMO) systems, the maximum likelihood (ML) detection problem is NP-hard and becoming classically intricate with the number of transmitting antennas and symbols increasing. The quantum approximate optimization algorithm (QAOA), a leading candidate algorithm running in the noisy intermediate-scale quantum (NISQ) devices, can show quantum advantage for approximately solving combinatorial optimization problems. In this paper, we propose the QAOA based on the maximum likelihood detection solver of binary symbols. In the proposed scheme, we first conduct a universal and compact analytical expression for the expectation value of the 1-level QAOA. Second, a Bayesian optimization based parameters initialization is presented, which can speedup the convergence of the QAOA to a lower local minimum and improve the probability of measuring the exact solution. Compared to the state-of-the-art QAOA based ML detection algorithm, our scheme has the more universal and compact expectation value expression of the 1-level QAOA, and requires few quantum resources and has the higher probability to obtain the exact solution.
The quantum approximate optimization algorithm (QAOA) targets NP-hard maximum-likelihood (ML) detection in multiple-input multiple-output (MIMO) systems. Existing M-ary quadrature amplitude modulation (M-QAM) detectors design angles by expected Ising energy: online per instance, warm-started, or ramped, while train-once designs remain B/QPSK-only or block-local, leaving M-QAM without a size-scalable benchmark. Their infinite-size spin-glass theory assumes independent disorder, matching the retained covariances at B/QPSK but not M-QAM's correlated couplings and fields. We develop a correlated infinite-size multi-species spin-glass framework whose covariance-matched evaluators make that energy an offline objective with a size-scalable benchmark. In addition, the ML rate, the exponential rate of sampling the ML string, is for the first time exploited for QAOA angle design in MIMO detection. The energy evaluator is q-free at O(p4p) cost while the ML rate transfers angles from a fixed qref-qubit reference. Tests reach 4096-QAM, 128 antennas, p=30 and per-symbol SNR 0-45 dB. In simulations, ML rates fall as a power law r0p−α, with larger exponents for the sampling design, which tracks exact ML at 5×5 16-QAM (0-20 dB) and 3×3 64-QAM (8-28 dB) while its bit-error rate (BER) advantage widens with SNR to two orders of magnitude. The approach points toward near-optimum decoding on deeper noiseless fault-tolerant quantum (FTQ) circuits.