Source-linked AI summary
General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm
Jingjing Cui, Gui Lu Long, Lajos Hanzo
TL;DR
ML detection is a combinatorial optimization problem, and constructing its Hamiltonian for QAOA is a central challenge. The paper formulates detection as WMIN-N-SAT and exploits Gray-labelled constellation structure to simplify the Hamiltonian. In QPSK simulations, the approximation ratio improves with circuit depth and approaches one as depth grows.
Problem
ML detection searches all transmitted-signal vectors with complexity increasing as M^N, making it an NP-hard combinatorial optimization problem.
Source: §I · p. 2Method
The paper maps general-constellation ML detection to WMIN-N-SAT, represents its objective as a pseudo Boolean function, and uses Gray-label structure to simplify the QAOA Hamiltonian.
Source: §I · p. 4Results
In QPSK simulations over AWGN at SNR=15dB, the approximation ratio increases from 0.7892 for p = 1 to 0.9973 for p = 4.
Source: §VI · p. 22Takeaways & Limitations
For Gray-mapped MQAM, the required encoding can be reduced to ⌈N/2⌉ qubits, and in-phase and quadrature components can be detected separately.
Source: §I · p. 4, §VII · p. 23
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper addresses the combinatorial complexity of maximum-likelihood detection by constructing QAOA Hamiltonians from a WMIN-N-SAT formulation. It uses Gray-label structure to simplify the objective and extends its analysis to MIMO channels.
I. INTRODUCTION
- ML detection searches over transmitted-signal vectors with complexity increasing as M^N, and the optimization problem is NP-hard.The paper motivates QAOA as a hybrid approach suited to noisy intermediate-scale quantum devices.Source: §I · p. 2
- The proposed construction transforms general-constellation ML detection into WMIN-N-SAT and represents its objective as a pseudo Boolean function.This yields an unconstrained minimization problem for constructing the problem Hamiltonian.Source: §I · p. 4
- For QPSK, equal sums of squared distances to the two diagonal-point pairs let the authors reduce the objective-function degree and simplify the Hamiltonian.The paper relates monomial coefficients to patterns in Gray-labelled constellations.Source: §I · p. 4
- In Gray-labelled MQAM, in-phase and quadrature qubits do not interact, and the paper extends its degree characterization to MIMO joint constellations.The introduction states that the MQAM Hamiltonian degree equals the number of in-phase bits.Source: §I · pp. 4–5
- The QAOA-assisted detector does not need conventional signal demapping, and the paper evaluates its QPSK approximation ratio through simulations.The work also compares the QAOA-assisted and classical ML detector architectures.Source: §I · p. 5
II. SYSTEM MODEL
- The MIMO model assumes perfect receiver knowledge of the channel and defines ML detection as finding the closest lattice point in a complex space.The transmitted signals are drawn independently from a finite constellation, with zero-mean complex Gaussian noise.Source: §II · p. 5
III. SISO CHANNEL
The SISO ML detection objective is recast as WMIN-N-SAT by mapping constellation points to bit strings and assigning clauses weights from their received-signal distances. Its pseudo Boolean expansion links monomials to patterns in the constellation and their associated bit labels.
A. Problem reformulation
- Each constellation point maps to a clause over N binary variables, turning SISO ML detection into a WMIN-N-SAT problem.For Gray-labelled QPSK, the mapping uses two-variable clauses; for 8QAM, it uses three-variable clauses and eight clauses total.Source: A. Problem reformulation · pp. 6–7
- The clause weight is the squared Euclidean distance from the received signal to its associated constellation point, and minimizing total weight selects the ML point.The objective is expressed as a pseudo Boolean function of the binary variables.Source: A. Problem reformulation · pp. 6–7
- The objective is a multilinear polynomial whose degree is the largest number of distinct variables in any monomial; its constant term can be omitted without changing the optimum.The resulting WMIN-N-SAT minimization is equivalent to the ML detection problem.Source: A. Problem reformulation · p. 7
- For S ⊆ N, Ci contains the monomial given by the product of z_n over n in S exactly when every bit outside S is zero; the monomial appears in 2^|S| clauses.Source: A. Problem reformulation · pp. 7–8
B. Constructing Hamiltonians
The QAOA problem Hamiltonian encodes the WMIN-N-SAT objective, with its ground state corresponding to the minimum-distance constellation assignment. Gray mapping can eliminate QPSK's quadratic interaction, while constellation geometry gives further conditions for zero monomial coefficients.
B. Constructing Hamiltonians
- The problem Hamiltonian encodes the objective in qubit interactions, and its ground state represents the assignment with minimum Euclidean distance.The QAOA seeks this ground state.Source: B. Constructing Hamiltonians · pp. 8–9
1) Problem Hamiltonian for QPSK:
- Gray-labelled QPSK has a zero quadratic coefficient, so its two qubits have no interaction and detection can use a single-qubit device twice or in parallel.The same diagonal-distance property extends to four constellation points forming a rectangle.Source: 1) Problem Hamiltonian for QPSK · pp. 9–10
- The constellation-point patterns associated with monomials indicate which coefficients vanish; QPSK's quadratic monomial corresponds to a rectangle with diagonal pairs of differing bit-parity patterns.The figure uses dashed outlines for zero-coefficient patterns and solid outlines for nonzero-coefficient patterns.Source: 1) Problem Hamiltonian for QPSK · pp. 10–11
- For non-Gray mappings, rectangle coverage with the specified diagonal-label parity pattern can also make the highest-degree monomial coefficient zero.For general labelling orders, the stated zero-coefficient condition applies to monomials whose associated points form rectangles satisfying the shared-vertex and parity conditions.Source: 1) Problem Hamiltonian for QPSK · pp. 10–12
2) Problem Hamiltonian for 8QAM Constellation:
The 8QAM objective simplifies to a quadratic function with one pairwise interaction, while Gray-labelled rectangular MQAM has cancellations that separate in-phase and quadrature variables. The section also shows how constellation geometry determines polynomial degree and where pseudo-Gray cross QAM can retain higher-degree terms.
2) Problem Hamiltonian for 8QAM Constellation:
- 8QAM uses three qubits, but its simplified objective has only one interaction, between qubits 0 and 1, so at least a two-qubit device is required.The objective is quadratic and contains the product z0z1.Source: 2) Problem Hamiltonian for 8QAM… · p. 12
- In 16QAM, rectangle-associated degree-3 and degree-4 coefficients vanish, yielding two independent 8QAM components and enabling implementation on a two-qubit device.The simplified objective is the sum of f8QAM(z0, z1) and f8QAM(z2, z3).Source: 3) Problem Hamiltonian for 16QAM · p. 13
- For Gray-labelled rectangular MQAM, mixed in-phase/quadrature monomials cancel, the objective degree is NI = ⌈N 2 ⌉, and the two qubit groups do not interact.The interaction graph is disconnected; QPSK and 8QAM have isolated nodes when one group has size one.Source: 3) Problem Hamiltonian for 16QAM · pp. 13–14
- For cross 32QAM using the quasi-Gray mapping orders of,, some degree-4 monomials cannot be cancelled, so the objective function f32QAM(z0, ···, z4) has degree 4.More generally, the degree is no higher than N − 1 if the cross constellation obeys Corollary 1 properties 1)-3).Source: 3) Problem Hamiltonian for 16QAM · p. 14
4) Problem Hamiltonian of 64QAM:
The 64QAM objective separates into two independent functions over three variables each. Each function has degree three, so its Hamiltonian is 3-local and must be reduced to two-local interactions for the described QAOA implementation.
4) Problem Hamiltonian of 64QAM:
- 64QAM simplifies into f(z0, z1, z2) + f(z3, z4, z5), with the two Hamiltonians independent and implementable on separate quantum systems.Each three-variable function has degree three and corresponds to a 3-local Hamiltonian.Source: 4) Problem Hamiltonian of 64QAM · pp. 14–15
- Because QAOA is described as typically limited to two-local interactions, each 3-local Hamiltonian must be reduced before implementation.The paper names substitution reduction, which uses auxiliary variables, and split reduction, which does not add them.Source: 4) Problem Hamiltonian of 64QAM · p. 15
IV. PROBLEM HAMILTONIAN CONSTRUCTIONS FOR MIMO CHANNELS
The MIMO section builds the ML objective over a joint constellation and extends constellation-pattern cancellations to the resulting Hamiltonian. For Gray-labelled QAM, the objective degree depends on the modulation and number of transmit antennas, while in-phase and quadrature qubits remain uncoupled.
IV. PROBLEM HAMILTONIAN CONSTRUCTIONS FOR MIMO CHANNELS
- The MIMO ML detector selects a point in the joint constellation minimizing the summed distance from the received signal over receive antennas.The joint constellation is formed as a Cartesian product of the per-transmit-antenna constellations.Source: §IV · p. 15
- For Gray-labelled MIMO constellations, monomials mixing in-phase and quadrature variables have zero coefficients, so their qubits remain noninteracting.The single-constellation rectangle cancellation property carries over to the joint MIMO objective.Source: §IV · pp. 16–17
- For Gray-labelled QPSK, the MIMO objective degree is Nt; for Gray-labelled MQAM, it is NINt.Source: §IV · p. 17
- For the 1 × 2 QPSK example, the objective is quadratic and has no interactions within either qubit pair (z0, z1) or (z2, z3).The Hamiltonian therefore contains at most two-local interactions.Source: §IV · pp. 17–18
A. Implementation of the QAOA
The QAOA implementation uses separate circuits for the in-phase and quadrature qubits of Gray-labelled QAM, with circuit depth set by p. It alternates problem- and mixing-Hamiltonian evolutions, then measures candidate bit strings to estimate the ML objective.
A. Implementation of the QAOA
- For Gray-labelled SISO QAM, independent in-phase and quadrature qubits are handled by a pair of QAOA circuits, and p controls their depth.The variational parameters are γ = [γ1, · · · , γp] and β = [β1, · · · , βp].Source: A. Implementation of the QAOA · p. 18
- Each level alternates problem-Hamiltonian and mixing-Hamiltonian unitaries; problem evolution for qI uses two-qubit Rzz gates and single-qubit rotations.Each Rzz unitary comprises two CNOT gates and an Rz gate; the mixing evolution uses Rx rotations.Source: A. Implementation of the QAOA · pp. 18–19
- Repeated preparation and computational-basis measurement of the parameterized state provide samples used to estimate the ML objective expectation.Source: A. Implementation of the QAOA · p. 19
B. Quantum Maximum Likelihood (QML) detection
The QAOA encodes candidate transmit symbols as binary variables, with the optimal bit string represented by the problem Hamiltonian’s ground state. Its output is the estimated transmitted bit string, unlike classical ML detection, which demaps its detected symbol.
B. Quantum Maximum Likelihood (QML) detection
- The QAOA’s ground state encodes the optimal binary solution, and its output is the estimated transmitted bit string directly.Unlike the classical ML receiver, it requires no signal-demapping step.Source: B. Quantum Maximum Likelihood (QML)… · p. 20
- The approximation ratio evaluates the quality of the QAOA solution for this minimization problem against the classical ML objective value.The classical ML objective value is denoted fCML.Source: B. Quantum Maximum Likelihood (QML)… · p. 20
VI. SIMULATION RESULTS
The simulations examine QPSK QAOA objective landscapes and approximation ratios across problem instances, optimization runs, circuit depths, and SNRs. The reported approximation ratio improves with more runs and higher circuit depth, while SNR sensitivity is more evident at p = 1.
VI. SIMULATION RESULTS
- The QPSK objective landscapes show global-minimum positions varying with SNR, noise, channel coefficients, and transmitted symbols.The landscapes cover AWGN and uncorrelated Rayleigh channels; darker regions indicate lower objective values.Source: §VI · p. 21, Figure 8 · p. 21
- At SNR=15dB, AWGN ρ rises from 0.7892 at p = 1 to 0.9973 at p = 4; Rayleigh ρ rises from 0.7316 to 0.9923.Each point averages 100 channel realizations; the plotted comparison is approximation ratio versus number of runs, parameterized by p.Source: Figure 9 · p. 22, §VI · p. 22
- Approximation ratio is more SNR-sensitive at p = 1 than at p ≥ 2 across the simulated AWGN and Rayleigh channels.The SNR comparison uses 100 channel realizations and 2000 runs.Source: Figure 10 · p. 22, §VI · p. 22
VII. CONCLUSIONS
The paper presents a SAT-based Hamiltonian construction for ML detection and relates objective-function degree to Gray-labelled constellations. It concludes that Gray-mapped MQAM can use fewer qubits, while QAOA directly outputs estimated input bits.
VII. CONCLUSIONS
- The SAT-based construction simplifies the problem Hamiltonian representation for ML detection.The paper formulates the problem using a pseudo Boolean function.Source: §VII · p. 23
- For Gray-mapped MQAM, encoding requires ⌈N/2⌉ qubits rather than the general bound of at most N qubits for an M-point constellation.Here, N = log2(M).Source: §VII · p. 23
- The QAOA-assisted detector directly delivers the estimated input bit string without the classical detector’s signal-demapping procedure.Source: §VII · p. 23
APPENDIX A: PROOF OF PROPOSITION 1
The appendices prove a QPSK distance identity and derive how Gray-labelled constellation patterns cancel coefficients in the pseudo Boolean objective function. The results extend to vanishing coefficients for specified monomials in the corollaries.
APPENDIX A: PROOF OF PROPOSITION 1
- For a received signal inside or outside the QPSK square, the two pairs of diagonal constellation points have equal sums of squared distances.The geometric proof establishes d0 + d3 = d1 + d2, yielding d̄0,1 = 0.Source: Appendix A · p. 23, Figure A.1 · p. 24
APPENDIX B: PROOF OF Theorem 1
- For Gray-labelled rectangular QAM and PSK, opposite signs among diagonal-point coefficients make the full-degree monomial coefficient zero.The appendix derives monomial coefficients by summing signed squared distances across the clauses containing each monomial.Source: Appendix B · pp. 24–25
APPENDIX C: PROOFS OF Corollary 1 AND Corollary 2
- Corollary 1’s rectangle properties yield a zero full-degree coefficient; Corollary 2 extends the cancellation to any monomial indexed by S.The proof uses rectangles formed without shared vertices.Source: Appendix C · pp. 25–26
APPENDIX D: PROOF OF Theorem 2
The proofs connect Gray-labeling patterns to the objective function’s degree: mixed in-phase and quadrature monomials cancel, while MIMO degrees depend on the constellation structure.
APPENDIX D: PROOF OF Theorem 2
- Gray-mapped rectangular QAM cancels mixed-axis monomials containing a zero bit from each bit group, while its objective function has degree NI.The degree-NI term does not cancel because points with zero quadrature bits lie on a line parallel to the in-phase axis.Source: Appendix D · p. 27
APPENDIX E: PROOFS OF Corollary 3 AND Corollary 4
- For MIMO QPSK, the objective function has degree Nt; for Gray-labelled MQAM with M ≥ 4, it has degree NINt.For MQAM, coefficients above degree NINt vanish, while the terms containing all in-phase bits across the constellations do not cancel.Source: Appendix E · p. 28
APPENDIX F: PROOF OF Theorem 3
- For MIMO with QPSK or MQAM, the objective function has degree NINt, with NI = 1 for QPSK; in hybrid MQAM, each constellation contributes its own highest-degree monomials to the expanded objective.The hybrid case allows different Gray-mapped QAM constellations across the Nt transmit streams.Source: Appendix F · p. 28