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

arXiv:2204.05126

General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm

Jingjing Cui, Long, Gui Lu, Hanzo, Lajos

Published Apr 11, 2022• 5 citations
arXivHTMLPDF

Abstract

The quantum approximate optimization algorithm (QAOA) conceived for solving combinatorial optimization problems has attracted significant interest since it can be run on the existing noisy intermediate-scale quantum (NISQ) devices. A primary step of using the QAOA is the efficient Hamiltonian construction based on different problem instances. Hence, we solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA, which gives rise to a new paradigm in communication systems. We first transform the ML detection problem into a weighted minimum $N$-satisfiability (WMIN-$N$-SAT) problem, where we formulate the objective function of the WMIN-$N$-SAT as a pseudo Boolean function. Furthermore, we formalize the connection between the degree of the objective function and the Gray-labelled modulation constellations. Explicitly, we show a series of results exploring the connection between the coefficients of the monomials and the patterns of the associated constellation points, which substantially simplifies the objective function with respect to the problem Hamiltonian of the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest, which allows the in-phase and quadrature components to be detected separately using the QAOA. Furthermore, we characterize the degree of the objective function in the WMIN-$N$-SAT problem corresponding to the ML detection of multiple-input and multiple-output (MIMO) channels. Finally, we evaluate the approximation ratio of the QAOA for the ML detection problem of quadrature phase shift keying (QPSK) relying on QAOA circuits of different depths.

DOI
10.48550/arxiv.2204.05126

Related papers

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.

arXiv:2107.05020•IEEE Transactions on Communications•Jun 22, 2022•41 citations

Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO

Yuxiang Liu, Fanxu Meng, Zetong Li +2 more

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.

arXiv:2510.13350•IEEE Wireless Communications and Networking Conference•Apr 21, 2024•7 citations

Beyond Binary Encoding: Qudit-Based QAOA Framework for ML Detection in $M$-QAM MIMO Systems

Chiran Siriwardena, Chanula Luckshan, Samiru Gayan +2 more

Maximum likelihood (ML) detection in massive multiple-input multiple-output (MIMO) systems is an NP-hard combinatorial problem whose complexity grows exponentially with the number of transmit antennas and the modulation order. The Quantum Approximate Optimization Algorithm (QAOA) has recently emerged as a promising near-term quantum heuristic for such problems; however, existing qubit-based formulations require $\log_2 M$ qubits per $M$-QAM symbol, inflating both circuit width and depth. In this paper, we propose a qudit-based QAOA framework that encodes each $M$-QAM symbol directly into a pair of $d$-dimensional quantum states, where $d=\sqrt{M}$. We derive a Hermitian cost Hamiltonian via a real-imaginary decomposition of the constellation, and introduce a generalized cyclic-shift mixer that ensures ergodic exploration of the search space without binary encoding. The proposed formulation reduces the number of quantum carriers from $\mathcal{O}(N_t \log_2 M)$ to $\mathcal{O}(N_t)$ and the Hamiltonian interaction complexity from $\mathcal{O}((N_t \log_2 M)^2)$ to $\mathcal{O}(N_t^2)$, while preserving the geometric structure of the constellation. Bit-error-rate (BER) simulations for $2\times 2$ MIMO systems employing 4-QAM and 16-QAM over Rayleigh fading channels, with circuit depth $p=3$, demonstrate that the proposed detector closely approximates the performance of the optimal classical maximum-likelihood (ML) detector, while consistently outperforming the conventional minimum mean square error (MMSE) detector.

arXiv:2610.30925•Oct 22, 2026•0 citations

Maximum-Likelihood Detection With QAOA for Massive MIMO and Sherrington-Kirkpatrick Model With Local Field at Infinite Size

Burhan Gülbahar

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.

IEEE Transactions on Wireless Communications•Apr 5, 2024•14 citations

Maximum-likelihood detection with QAOA for massive MIMO and Sherrington-Kirkpatrick model with local field at infinite size

Burhan Gülbahar

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.

•Sep 21, 2023•0 citations

M-QAM MIMO Maximum-Likelihood Detection with QAOA: ML-Rate Offline Angle Design and Correlated Infinite-Size Spin-Glass Models

Burhan Gülbahar

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(p\,4^p)$ cost while the ML rate transfers angles from a fixed $q_{\rm ref}$-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 $r_0\,p^{-α}$, with larger exponents for the sampling design, which tracks exact ML at $5\times5$ 16-QAM (0-20 dB) and $3\times3$ 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.

eess.SPCross-listedarXiv:2608.17721•Aug 19, 2026•0 citations
The quantum approximate optimization algorithm (QAOA) conceived for solving combinatorial optimization problems has attracted significant interest since it can be run on the existing noisy intermediate-scale quantum (NISQ) devices. A primary step of using the QAOA is the efficient Hamiltonian construction based on different problem instances. Hence, we solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA, which gives rise to a new paradigm in communication systems. We first transform the ML detection problem into a weighted minimum NNN-satisfiability (WMIN-NNN-SAT) problem, where we formulate the objective function of the WMIN-NNN-SAT as a pseudo Boolean function. Furthermore, we formalize the connection between the degree of the objective function and the Gray-labelled modulation constellations. Explicitly, we show a series of results exploring the connection between the coefficients of the monomials and the patterns of the associated constellation points, which substantially simplifies the objective function with respect to the problem Hamiltonian of the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest, which allows the in-phase and quadrature components to be detected separately using the QAOA. Furthermore, we characterize the degree of the objective function in the WMIN-NNN-SAT problem corresponding to the ML detection of multiple-input and multiple-output (MIMO) channels. Finally, we evaluate the approximation ratio of the QAOA for the ML detection problem of quadrature phase shift keying (QPSK) relying on QAOA circuits of different depths.
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-pppQAOA circuit having2p2p2pvariational parameters, which can be optimized by classical optimizers. This level-pppQAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately inpppconsecutive 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.
Beyond Binary Encoding: Qudit-Based QAOA Framework for ML Detection in MMM-QAM MIMO Systems
Maximum likelihood (ML) detection in massive multiple-input multiple-output (MIMO) systems is an NP-hard combinatorial problem whose complexity grows exponentially with the number of transmit antennas and the modulation order. The Quantum Approximate Optimization Algorithm (QAOA) has recently emerged as a promising near-term quantum heuristic for such problems; however, existing qubit-based formulations require log⁡2M\log_2 Mlog2​M qubits per MMM-QAM symbol, inflating both circuit width and depth. In this paper, we propose a qudit-based QAOA framework that encodes each MMM-QAM symbol directly into a pair of ddd-dimensional quantum states, where d=Md=\sqrt{M}d=M​. We derive a Hermitian cost Hamiltonian via a real-imaginary decomposition of the constellation, and introduce a generalized cyclic-shift mixer that ensures ergodic exploration of the search space without binary encoding. The proposed formulation reduces the number of quantum carriers from O(Ntlog⁡2M)\mathcal{O}(N_t \log_2 M)O(Nt​log2​M) to O(Nt)\mathcal{O}(N_t)O(Nt​) and the Hamiltonian interaction complexity from O((Ntlog⁡2M)2)\mathcal{O}((N_t \log_2 M)^2)O((Nt​log2​M)2) to O(Nt2)\mathcal{O}(N_t^2)O(Nt2​), while preserving the geometric structure of the constellation. Bit-error-rate (BER) simulations for 2×22\times 22×2 MIMO systems employing 4-QAM and 16-QAM over Rayleigh fading channels, with circuit depth p=3p=3p=3, demonstrate that the proposed detector closely approximates the performance of the optimal classical maximum-likelihood (ML) detector, while consistently outperforming the conventional minimum mean square error (MMSE) detector.
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.
The quantum approximate optimization algorithm (QAOA) targets NP-hard maximum-likelihood (ML) detection in multiple-input multiple-output (MIMO) systems. Existing MMM-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 qqq-free at O(p 4p)O(p\,4^p)O(p4p) cost while the ML rate transfers angles from a fixed qrefq_{\rm ref}qref​-qubit reference. Tests reach 4096-QAM, 128 antennas, p=30p=30p=30 and per-symbol SNR 0-45 dB. In simulations, ML rates fall as a power law r0 p−αr_0\,p^{-α}r0​p−α, with larger exponents for the sampling design, which tracks exact ML at 5×55\times55×5 16-QAM (0-20 dB) and 3×33\times33×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.