Quantum-Native Maximum Likelihood Detection in Random Access Channel with Overloaded MIMO

Hyoga Iizumi, Naoki Ishikawa, Shunsuke Uehashi, Kota Nakamura, Shusaku Umeda, Toshiaki Koike-Akino (Yokohama National Univ. / Mitsubishi Electric Research Labs) · arXiv:2605.19389 · cross-listed from eess.SP · submitted 19 May 2026 · score 8/10 (HIGH)

Abstract

In this paper, we propose a quantum-native formulation of maximum likelihood detection (MLD) for overloaded multiple-input multiple-output (MIMO) systems in a random access channel, where numerous user terminals share the same channel resource and asynchronously transmit signals. Classical linear detectors suffer from significant performance degradation in this scenario, whereas the exhaustive-search MLD achieves the optimal performance but incurs an exponential computational complexity. To overcome this trade-off, we formulate the MLD as a binary optimization problem and solve it via Grover adaptive search (GAS) — a quantum exhaustive search algorithm offering quadratic speedup in fault-tolerant quantum computing. We then introduce a search space reduction technique to substantially decrease the required computational resources. In addition, we investigate efficient parameter settings for GAS through probability analysis to improve convergence performance. We demonstrate that the proposed detector achieves the optimal detection performance while reducing the required Grover rotation count to reach the solution by up to approximately 65% compared with the conventional GAS, showing its potential as a viable solution for future quantum-accelerated wireless systems.

Executive summary

Iizumi et al. formulate the MLD problem for asynchronous overloaded MIMO as a binary optimisation problem solved by Grover Adaptive Search (GAS), and introduce three accelerators: (i) a problem-specific search space reduction exploiting structural constraints from the modulation alphabet, (ii) an analytically derived tighter lower bound L_min on the number of Grover operators per round, and (iii) a calibrated initial threshold obtained from a classical minimum-variance distortion (MVD) pre-detector, with a restart strategy for when the MVD estimate accidentally undershoots. Together these reduce the Grover rotation count to reach the optimum by ~65% versus vanilla GAS. For Yuan, this is methodologically the closest 2026-05-20 paper to Y4: same Grover-on-structured-feasible-space mechanism, similar L_min/L_max tuning, and an explicit demonstration that the structural reductions matter as much as the Grover engine itself.

Main contribution

The paper takes the well-known Grover Adaptive Search of Bulger/Baritompa/Stephens and Gilliam et al., specialises it to the MIMO ML detection problem, then attacks both ends of the GAS cost: the per-round Grover-operator schedule (bounded above by the standard L_max = ⌈π/(4 arcsin √(1/(4·feasible_fraction)))⌉ family of bounds, and below by a problem-aware L_min the authors derive analytically), and the search-space size itself, by exploiting modulation-alphabet symmetry to halve or quarter the effective search space. The MVD-initialised threshold + restart strategy stabilises convergence when the classical seed estimate is bad.

Key theorems / lemmas / algorithms

Lemma: Search space reduction (Sec. IV-B). By exploiting symmetry in the QPSK/π/2-BPSK constellation and the structure of the asynchronous overlap matrix, the feasible binary search space can be reduced by a factor depending on (M, N, τ_max), without losing the optimal solution.
Theorem: Tighter L_min bound (Sec. V-C). A problem-aware lower bound on the number of Grover operators needed in the worst case, derived from the modulation-alphabet structure, strictly improves on the generic L_min = 1 of vanilla GAS.
MVD-seeded initial threshold (Sec. V-B). A linear minimum-variance detector with explicit treatment of preamble-length-dependent estimation error provides an initial threshold y_MVD for GAS; the value is calibrated against the expected MLD energy E_min.
Restart strategy (Sec. V-D). If y_MVD < E_min (i.e. the seed is unrealistically low and GAS would not find any improving sample), restart from a recalibrated threshold; this prevents pathological non-convergence.
Convergence analysis (Sec. VI-C, derived from generic GAS theory). The expected number of Grover rotations to find the optimal MLD solution is approximately quartered when (i) search-space reduction is applied and (ii) the L_min bound is enforced.

Detailed walkthrough

System model (Sec. III). M user terminals (UTs) asynchronously transmit signals to N receive antennas; each UT's symbol can arrive in any of τ_max+1 time slots. The aggregate received signal at the N antennas, after sampling, is a noisy linear combination of all UTs' symbols across overlap slots. The ML detector finds the binary representation of the symbol vector that minimises ‖y − H x‖² over the discrete modulation alphabet — classically O(|alphabet|^M(τ_max+1)), exponentially intractable for large M, τ_max.

GAS recap (Sec. II). Grover Adaptive Search wraps a Grover search inside a classical loop. At round t with threshold y_t, an oracle marks all bitstrings x with E(x) < y_t; Grover amplifies the marked subspace; measurement gives a candidate x'; if E(x') < y_t, set y_t+1 = E(x') and continue, else retry with larger Grover-operator count L drawn from the standard exponentially expanding schedule. The total cost is O(√(2ⁿ/M)) rotations in expectation for M marked items.

Search-space reduction (Sec. IV-B). The clever observation is that for QPSK and π/2-BPSK constellations, the MLD objective has discrete symmetries (a global rotation by π/2 maps feasible to feasible with related energies). By fixing one degree of freedom per symbol — equivalently, working in a quotient of the alphabet — the effective n drops by a factor of 2–4, immediately squaring the GAS speedup. They prove the reduction preserves the optimum.

Tighter L_min (Sec. V-C). The default GAS schedule starts each round with a Grover-operator count drawn uniformly from [1, L_t]; the floor of 1 is wasteful when the marked-subspace fraction is provably bounded below. The authors compute the worst-case marked fraction induced by the threshold-update rule and the problem structure, deriving a problem-aware L_min > 1 that prunes rounds in which Grover is statistically guaranteed to fail. Empirically (Figs. 8 and 9 of the LaTeX) this saves a substantial fraction of total rotations.

MVD-seeded threshold (Sec. V-B + V-D). A linear MVD detector with explicit modelling of preamble-length-dependent estimation error produces an initial y_MVD. The catch: if y_MVD < E_min (an unrealistically low seed), no Grover round can improve, and the algorithm stalls. The restart strategy detects this case (via the failure rate of the first few rounds) and re-initialises with a more conservative threshold.

Performance (Sec. VI). Numerical experiments on small N, M, τ_max configurations (e.g. N=2, M=4, τ_max=1) confirm the bit-error rate (BER) attains the exhaustive-MLD optimum while the average Grover-rotation count to convergence drops by up to ~65% versus vanilla GAS. Comparisons across preamble lengths (Fig. 6), initial-threshold variants (Fig. 7), and L_min values (Fig. 8) isolate each improvement.

Figures

Figure 1. An example of a quantum circuit for GAS with an objective function E(x) = 2 − y_i + x₁ − 3 x₁ x₂ x₃ + x₁ x₂ x₃ — the GAS oracle inverts amplitudes of bitstrings whose energy beats the current threshold.

Figure 2. CDF of query complexity showing the effect of the proposed search-space reduction. Vanilla GAS vs. the reduced-search-space variant at N=2, M=4, τ_max=1.

Figure 3. BER comparison when varying the length of the preamble used to seed the MVD threshold.

Figure 4. BER comparison when varying the initial threshold y₀ — comparison across four initial-value strategies (zero, classical MVD, MVD with estimation-error correction, ideal).

Figure 5. CDF of query complexity when varying the lower bound L_min on the number of Grover operators per round; N=2, M=4, τ_max=2, C=2.

Figure 6. Same study, τ_max=2, C=4 — larger constellation. The tighter L_min bound continues to help.

Figure 7. Same study, τ_max=5 — larger asynchronous overlap window. The proposed L_min approach remains beneficial even with more aggressive asynchrony.

Figure 8. Same study, M=8 users — scale-up. The relative speedup from the tighter L_min bound is preserved.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y4 (Grover + ADMM for cardinality-constrained BO; O(√(C(n,k)/M)) rotations): nearly identical methodological core — both papers wrap a problem-specific structural reduction around Grover Adaptive Search. Yuan's reduction is cardinality-symmetric (Hamming weight = k); Iizumi's is constellation-symmetric (modulation alphabet symmetry). Both achieve sub-2^n/2 rotation counts by reducing the feasible space rather than improving Grover. The L_min tightening in this paper is a useful trick that could be back-ported to Y4.
Y2 / Y3 (QAOA-based portfolio): tangential — the QAOA-vs-GAS choice is exactly the QAOA vs. Grover trade-off Yuan navigates between Y2/Y3 and Y4. This paper's BER-vs-rotation curves give one more data point on the GAS side of that comparison.
Y5 (SDP via Gibbs states): no direct overlap.
Y1, Y6: no overlap.

Recommended action for Yuan

Adopt the tighter L_min derivation for Y4's cardinality-Grover schedule: Y4 currently uses a generic GAS schedule; this paper's analytical L_min bound is directly portable to the cardinality constraint and would tighten Y4's rotation-count claim.
Compare search-space-reduction philosophies: Y4 uses the cardinality constraint as a hard filter on the search space; this paper uses modulation-alphabet symmetry. A unified write-up of "structural pre-reductions for GAS" could be a useful methods paper bridging cardinality and constellation cases.
Read Sec. V-D (restart strategy) — the failure-detection logic for bad initial thresholds is a generally useful trick that Y4's hybrid-ADMM seed could benefit from.