Source-linked AI summary
Beyond Binary Encoding: Qudit-Based QAOA Framework for ML Detection in $M$-QAM MIMO Systems
Chiran Siriwardena, Chanula Luckshan, Samiru Gayan, Hazer Inaltekin, Wonjae Shin
TL;DR
ML detection in MIMO systems is NP-hard, while qubit-based QAOA encodings require log2 M qubits per QAM symbol. This paper develops a qudit-based QAOA framework for M-QAM detection; simulations report performance close to classical ML and consistently better than MMSE in the tested settings.
Problem
Qubit-based QAOA requires log2 M qubits per M-QAM symbol, increasing circuit width, depth, and interaction overhead for ML detection.
Source: §I · p. 1Method
The framework encodes each M-QAM symbol in two d-dimensional qudits via a real-imaginary decomposition and uses a generalized cyclic-shift mixer.
Source: §I · p. 1, D. Qudit Cost Hamiltonian · p. 3, E. Qudit Mixer Hamiltonian and Initial… · p. 3Results
At depth p = 3, the qudit-QAOA detector closely tracks ML at low and moderate SNR and consistently outperforms MMSE across the 4-QAM SNR range.
Source: D. BER Performance · p. 5Takeaways & Limitations
The qudit formulation preserves the constellation's Euclidean geometry while avoiding binary encoding and is demonstrated in 2 × 2 MIMO simulations.
Source: §VI · p. 6Most platforms currently cap controllable qudit dimension near d ≤ 10, and multi-level control complicates calibration and error mitigation while increasing leakage risk.
Source: F. Limitations and Outlook · p. 6
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
ML detection offers lower BER than tractable linear receivers but is NP-hard, and existing QAOA formulations represent QAM symbols with costly binary encodings. This work proposes a qudit representation for M-QAM detection, addressing a bottleneck shared by prior QAOA-MIMO methods.
I. INTRODUCTION
- ML detection is NP-hard as a lattice Closest Vector Problem, while tractable ZF and MMSE receivers fall short of its optimal BER.The search space scales as M^Nt; prior sphere-decoding, semidefinite-relaxation, and tabu-search methods have not scaled gracefully to envisioned large arrays and high-order constellations.Source: §I · p. 1
- Qubit-based QAOA uses log2 M qubits per symbol, increasing circuit width, pairwise interactions, and depth while distorting constellation geometry.The paper identifies circuits for 256-QAM and 1024-QAM as prohibitive on foreseeable NISQ hardware.Source: §I · p. 1
- The proposed framework encodes each M-QAM symbol in two d-dimensional qudits, with d = √M, and uses a Hermitian cost Hamiltonian and generalized cyclic-shift mixer.The real-imaginary decomposition preserves constellation geometry, and the mixer ensures ergodic exploration of the qudit search space.Source: §I · p. 1
- The paper reports lower carrier requirements and interaction complexity for the qudit formulation, and simulations show it closely tracks ML while outperforming MMSE.The simulations cover 2 × 2 MIMO with 4-QAM and 16-QAM over Rayleigh fading; the supplied passages do not give numerical complexity values.Source: §I · p. 2
II. RELATED WORK
- Prior QAOA-MIMO work addresses detection through binary encodings and algorithmic refinements, while this framework targets the shared representation bottleneck.Earlier work includes warm-starting, recursive QAOA, and sampling methods,; the proposed representation is described as complementary to those techniques.Source: §II · p. 2
A. MIMO System Model
The system model casts transmission over a MIMO channel with additive Gaussian noise as an ML detection problem under perfect channel-state information. A real-valued reformulation separates the transmitted symbols into real and imaginary components to prepare the objective for qudit encoding.
A. MIMO System Model
- The model has Nt transmit and Nr receive antennas, channel H, transmitted vector x from an M-QAM constellation, and complex Gaussian noise.The detector is assumed to have perfect channel state information at the receiver.Source: A. MIMO System Model · p. 2
- Dropping the constant y†y term from the expanded ML objective yields f(x) = x†Ax − 2 ℜ{b†x}, with A = H†H and b = H†y.This is the equivalent quadratic objective used for the subsequent formulation.Source: A. MIMO System Model · p. 2
B. Real-Valued Equivalent Formulation
- The objective is recast in real-valued form using a real Gram matrix and vector, separating the real and imaginary parts of the transmitted signal.The expansion includes real-real, imaginary-imaginary, and real-imaginary cross terms.Source: B. Real-Valued Equivalent Formulation · pp. 2–3
IV. PROPOSED QUDIT-BASED QAOA FRAMEWORK
QAOA alternates a diagonal cost Hamiltonian and a non-diagonal mixer, starting from a uniform superposition. A classical outer loop tunes the variational parameters to minimize expected cost before sampling candidate solutions.
IV. PROPOSED QUDIT-BASED QAOA FRAMEWORK
- QAOA applies a diagonal problem Hamiltonian and a non-diagonal mixer in alternating layers to prepare a parameterized trial state.The supplied passages identify these as the cost Hamiltonian and mixer Hamiltonian.Source: A. QAOA Preliminaries · p. 3
- The depth-p evolution begins from the uniform superposition |ψ0⟩.Source: A. QAOA Preliminaries · p. 3
- A classical outer loop tunes γ and β to minimize the cost expectation, after which sampling the optimized state yields candidate solutions.The objective is Fp(γ, β) = ⟨ψp|Hf|ψp⟩.Source: A. QAOA Preliminaries · p. 3
B. Qubit-Based Baseline for BPSK
Binary QAOA represents each M-QAM symbol using log2 M qubits, whereas the proposed encoding uses two qudits per symbol. The qudit basis-to-constellation mapping preserves rectangular geometry so cyclic mixer moves correspond to local moves in signal space.
B. Qubit-Based Baseline for BPSK
- Binary encoding requires log2 M qubits per M-QAM symbol; advanced binary methods can reduce interaction scaling but retain higher carrier requirements than the qudit formulation.Naive binary formulations incur a quadratic increase in interaction terms, while more advanced approaches [4] exploit constellation structure for linear scaling in log2 M.Source: B. Qubit-Based Baseline for BPSK · p. 3
C. Qudit Encoding of M-QAM Symbols
- Each M-QAM symbol is represented by two d-dimensional qudits, one for its in-phase level and one for its quadrature level.The computational-basis indices k and l range from 0 to d − 1.Source: C. Qudit Encoding of M-QAM Symbols · p. 3
- The qudit basis mapping preserves rectangular constellation geometry, making adjacent basis states correspond to Euclidean-adjacent symbols and local signal-space moves.Source: C. Qudit Encoding of M-QAM Symbols · p. 3
D. Qudit Cost Hamiltonian
The cost Hamiltonian is built from two diagonal Hermitian operators that encode each symbol register’s real and imaginary components. Its computational-basis eigenvalues reproduce the classical detection cost, so its ground state encodes the ML solution.
D. Qudit Cost Hamiltonian
- The two diagonal operators act on one two-qudit symbol register and return the symbol’s real and imaginary components.Source: D. Qudit Cost Hamiltonian · p. 3
- Their diagonal entries are real, making both operators Hermitian and physically realizable observables.Source: D. Qudit Cost Hamiltonian · p. 3
- Substituting the operators for each symbol register into the classical cost yields the proposed cost Hamiltonian.Source: D. Qudit Cost Hamiltonian · p. 3
- Each computational-basis state has the classical cost as its eigenvalue, and the Hamiltonian’s ground state encodes the ML solution.Source: D. Qudit Cost Hamiltonian · p. 3
E. Qudit Mixer Hamiltonian and Initial State
The qudit mixer uses generalized cyclic shifts to redistribute amplitude and connect all computational-basis states, enabling ergodic search-space exploration. The gate implementation uses diagonal phase rotations and Fourier transforms, with hardware-native and decomposed options described.
E. Qudit Mixer Hamiltonian and Initial State
- The mixer redistributes amplitude between basis states to help QAOA evolution escape local minima, using a generalized cyclic shift instead of qubit Pauli-X.Source: E. Qudit Mixer Hamiltonian and Initial… · p. 3
- Repeated applications of the Hermitian mixer connect every pair of computational-basis states, ensuring ergodic exploration.Source: E. Qudit Mixer Hamiltonian and Initial… · p. 3
- The initial uniform superposition assigns equal probability to all M^Nt candidate symbol vectors at p = 0.Source: E. Qudit Mixer Hamiltonian and Initial… · p. 4
F. Gate-Level Implementation
- Diagonal cost terms implement as generalized RZd phase rotations, while the mixer is diagonalized by a qudit Fourier transform around a phase rotation.Source: F. Gate-Level Implementation · p. 4
- Native qudit phase-rotation primitives are available on trapped-ion and photonic platforms; without native gates, the listed rotations and Fourier transform decompose into two-level operations.Source: F. Gate-Level Implementation · p. 4
G. QAOA Algorithm
The detector constructs its cost and mixer Hamiltonians, initializes QAOA parameters with a linear ramp, and uses a classical optimizer to update them until convergence or budget exhaustion. The supplied passages also identify Table I as a resource comparison, but do not provide its cell values.
G. QAOA Algorithm
- The optimizer uses COBYLA with multi-start initialization in the simulations, while the general algorithm allows any gradient-free routine.The linear-ramp initialization sets γ_k = (k/p)Δγ and β_k = (1 − k/p)Δβ, with Δγ and Δβ in [0, π].Source: G. QAOA Algorithm · p. 4
- The algorithm constructs diagonal real and imaginary operators, builds the cost and mixer Hamiltonians, and initializes QAOA parameters with a linear ramp.Source: G. QAOA Algorithm · p. 4
- Parameter updates continue until convergence or the optimization budget is exhausted, after which the estimated symbol vector is returned through the inverse mapping.Source: G. QAOA Algorithm · p. 4
- Table I is captioned as a resource comparison of qubit- and qudit-based QAOA for M-QAM ML detection.Source: Table I · p. 4
A. Quantum Resource Comparison
The proposed qudit formulation reduces carrier and interaction scaling relative to binary encodings, with circuit-depth benefits and width scaling independent of modulation order. The supplied simulation setup uses 2 × 2 MIMO systems, 4-QAM and 16-QAM, and Rayleigh fading.
A. Quantum Resource Comparison
- The qudit formulation reduces quantum carriers from O(Nt log2 M) to O(Nt) and improves circuit-depth scaling versus the SAT-based approach.Source: A. Quantum Resource Comparison · p. 4
- Interaction complexity is O(Nt^2), rather than O((Nt log2 M)^2) for naive binary QAOA, a reduction by O((log2 M)^2).Source: A. Quantum Resource Comparison · p. 4
B. Scalability
- The qudit width scales as O(Nt), independent of M, while qubit width scales as O(Nt log2 M); the paper highlights 256-QAM and 1024-QAM as envisioned use cases.Source: B. Scalability · p. 5
C. Simulation Setup
- Simulations use 2 × 2 MIMO, 4-QAM and 16-QAM over i.i.d. Rayleigh fading, with QAOA depth p = 3 and BER averaged over SNR-dependent channel-realization counts.Source: C. Simulation Setup · p. 5
D. BER Performance
The qudit-QAOA detector closely tracks classical ML at low and moderate SNR and outperforms MMSE for 4-QAM, while greater depth improves approximation but has hardware trade-offs. The paper also identifies qudit-control limits and reports a 2 × 2 16-QAM example confirming predicted savings.
D. BER Performance
- At low and moderate SNR, qudit-QAOA closely tracks ML; it outperforms MMSE across the 4-QAM SNR range, with a small high-SNR gap to ML for both modulations.The reported BER range is −4 to 12 dB.Source: D. BER Performance · p. 5
E. Effect of QAOA Depth and Circuit Complexity
- Higher QAOA depth improves ground-state approximation, but 4-QAM BER reductions beyond p = 3 were below 0.5 dB, while hardware errors favor shallow p = 1–2.Greater depth also amplifies gate errors and decoherence, exacerbated in qudit systems by leakage and more complex d-dimensional gates.Source: E. Effect of QAOA Depth and Circuit… · pp. 5–6
F. Limitations and Outlook
- Controllable qudit dimension is capped near d ≤ 10 on most platforms, supporting up to 64-QAM with present hardware and 256-QAM in the near term; multilevel control complicates calibration and error mitigation, with more leakage.The authors identify these as limitations of the framework’s hardware outlook.Source: F. Limitations and Outlook · p. 6
VI. CONCLUSION
- A worked 2 × 2 16-QAM example confirms predicted savings, and the paper provides pseudocode and gate-level decomposition for reproduction.The conclusion also reports 2 × 2 4-QAM Rayleigh-fading simulations that closely track ML and outperform MMSE at modest depth.Source: §VI · p. 6
APPENDIX
The appendix establishes that computational basis states encode classical detection candidates and that their Hamiltonian eigenvalues equal the corresponding classical costs for BPSK and M-QAM.
A. Proof of Proposition 1 (BPSK)
- For BPSK, computational basis states are eigenstates of the cost Hamiltonian, with eigenvalues equal to the classical BPSK cost under the bijection s_k = 1 − 2z_k.The proof uses the basis-state action of the Pauli-Z operator to recover the corresponding symbol values.Source: A. Proof of Proposition 1 (BPSK) · p. 6
B. Proof of Proposition 2 (M-QAM)
- For M-QAM, computational basis states indexed by the bijection g are eigenstates whose eigenvalues equal the classical M-QAM cost at the corresponding constellation vector.The proof concludes that f(a) matches the classical cost term by term.Source: B. Proof of Proposition 2 (M-QAM) · p. 6