pith. sign in

arxiv: 2605.19389 · v1 · pith:O455TPPWnew · submitted 2026-05-19 · 📡 eess.SP · quant-ph

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 This is my paper

Pith reviewed 2026-05-20 03:18 UTC · model grok-4.3

classification 📡 eess.SP quant-ph
keywords maximum likelihood detectionoverloaded MIMOGrover adaptive searchrandom access channelbinary optimizationquantum detectionsignal processingwireless communications
0
0 comments X

The pith

Quantum-native maximum likelihood detection achieves optimal performance in overloaded MIMO while reducing Grover rotations by up to 65 percent.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper reformulates maximum likelihood detection for overloaded MIMO systems in random access channels as a binary optimization problem. It solves this formulation using Grover adaptive search, a quantum algorithm that provides quadratic speedup over classical exhaustive search. Adding a search space reduction technique and optimized parameter settings for the algorithm allows the detector to reach the optimal solution with substantially fewer quantum operations than standard Grover adaptive search. A sympathetic reader would care because classical linear detectors lose performance badly when many users share the channel asynchronously, while brute-force search is computationally prohibitive. The central result is that the quantum approach matches exhaustive-search accuracy at lower resource cost.

Core claim

The paper claims that formulating maximum likelihood detection as a binary optimization problem and solving it via Grover adaptive search with search space reduction and tuned parameters achieves the same optimal detection performance as exhaustive search while cutting the required Grover rotation count by up to approximately 65 percent compared with conventional Grover adaptive search.

What carries the argument

Grover adaptive search applied to a binary optimization reformulation of maximum likelihood detection, augmented by search space reduction and probability-based parameter tuning.

Load-bearing premise

The maximum likelihood detection problem can be exactly reformulated as a binary optimization problem whose solution via Grover adaptive search preserves optimality, assuming fault-tolerant quantum hardware that runs without decoherence.

What would settle it

A quantum simulation or hardware run in which the proposed detector produces a higher error rate than classical exhaustive search or fails to reduce the Grover rotation count by a substantial fraction would falsify the optimality and efficiency claims.

Figures

Figures reproduced from arXiv: 2605.19389 by Hyoga Iizumi, Kota Nakamura, Naoki Ishikawa, Shunsuke Uehashi, Shusaku Umeda, Toshiaki Koike-Akino.

Figure 1
Figure 1. Figure 1: An example of a quantum circuit for GAS with an [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: System model with M UTs and N receive antennas. Each UT modulates its packet bm and transmits a waveform sm(t) ∈ C asynchronously, written as sm(t) = M(bm), 0 ≤ t ≤ DT , (7) where M denotes a modulation operator. The duration of the transmitted waveform is DT = T DS, where DS is the symbol duration. Each UT moves independently and transmits signals asynchronously so that sm(t) experiences delay τm. This de… view at source ↗
Figure 3
Figure 3. Figure 3: Quantum circuits to generate the initial state for [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The distribution of the optimal number of operators [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparison of query complexity showing the effects [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: BER comparison when varying the initial threshold. [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Comparisons of query complexity when varying the lower bound of operators [PITH_FULL_IMAGE:figures/full_fig_p010_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Example of the placement of symbols for β1 (M = 2, QPSK). Using (45) and an additional variable a, the MLD problem can be reformulated as ˆ¯s = arg min ¯s,a [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a quantum-native maximum likelihood detection method for overloaded MIMO systems in random access channels. It reformulates the MLD problem as a binary optimization problem and solves it using Grover adaptive search (GAS), introducing a search space reduction technique that reportedly reduces the number of Grover rotations by up to 65% while achieving optimal detection performance. The work also includes analysis for efficient GAS parameter settings.

Significance. If the search space reduction is shown to preserve the exact optimality of the ML solution and the simulation results are statistically robust, this could represent a meaningful step toward practical quantum-accelerated signal detection in wireless systems, leveraging the quadratic speedup of quantum search algorithms in fault-tolerant quantum computing. The probability analysis for GAS parameters is a useful contribution to improving convergence.

major comments (2)
  1. The search space reduction technique is key to the claimed 65% reduction in Grover rotations. However, without a clear demonstration that the reduced space always includes the global optimum (e.g., via mathematical equivalence or exhaustive checks in simulations), the optimality claim is at risk, particularly in overloaded MIMO with asynchronous users.
  2. Numerical Results section: the comparison to classical MLD should include statistical error bars and specify the number of trials to validate that the quantum detector achieves identical performance.
minor comments (1)
  1. Clarify the exact nature of the search space reduction (e.g., is it based on norm thresholds or timing estimates?) to allow readers to assess its generality.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which will help strengthen the presentation and rigor of our work. We address each major comment in detail below and outline the specific revisions planned for the next version of the manuscript.

read point-by-point responses

  1. Referee: The search space reduction technique is key to the claimed 65% reduction in Grover rotations. However, without a clear demonstration that the reduced space always includes the global optimum (e.g., via mathematical equivalence or exhaustive checks in simulations), the optimality claim is at risk, particularly in overloaded MIMO with asynchronous users.

    Authors: We agree that an explicit demonstration of optimality preservation is essential. The reduction technique eliminates candidate vectors whose Euclidean distance to the received signal exceeds a threshold derived from the noise variance and the asynchronous user model, while retaining all vectors that could achieve the minimum distance. In the revised manuscript we will add a dedicated subsection containing a formal proof that the global ML solution is always retained under this criterion, leveraging the structure of the overloaded MIMO random-access signal model. We will also include exhaustive enumeration results for small-scale instances (up to 4 users) with asynchronous offsets to empirically confirm that the reduced space contains the optimum in every trial. revision: yes

  2. Referee: Numerical Results section: the comparison to classical MLD should include statistical error bars and specify the number of trials to validate that the quantum detector achieves identical performance.

    Authors: We concur that statistical validation strengthens the comparison. In the revised Numerical Results section we will add error bars representing the standard deviation across independent Monte Carlo trials and will explicitly state that each BER/SNR point is obtained from 10,000 independent channel and noise realizations. This will confirm that the proposed detector matches classical MLD performance within statistical fluctuations. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's core chain begins with an exact reformulation of classical MLD as a binary optimization problem (standard encoding of finite-alphabet exhaustive search), followed by direct application of the known Grover adaptive search algorithm for quadratic speedup. The subsequent search-space reduction and probability-based parameter tuning are presented as efficiency enhancements whose performance impact is demonstrated separately rather than defined into the optimality claim. No equation reduces to its own input by construction, no fitted quantity is relabeled as a prediction, and no load-bearing step relies on a self-citation chain or smuggled ansatz. The derivation remains self-contained against external benchmarks of MLD and Grover search.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard properties of Grover adaptive search and the assumption that MLD can be cast exactly as binary optimization; no new physical constants or ad-hoc fitted parameters are introduced in the abstract description.

axioms (1)
  • standard math Grover adaptive search provides quadratic speedup for unstructured search problems on fault-tolerant quantum computers.
    Invoked to justify the computational advantage over classical exhaustive search.

pith-pipeline@v0.9.0 · 5731 in / 1355 out tokens · 52678 ms · 2026-05-20T03:18:36.247146+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 2 internal anchors

  1. [1]

    Quantum-native formulation of maximum likelihood detection in random access channel with overloaded MIMO,

    H. Iizumi, N. Ishikawa, S. Uehashi, K. Nakamura, A. Kurita, and M. Oga, “Quantum-native formulation of maximum likelihood detection in random access channel with overloaded MIMO,” inIEEE V ehicular Technology Conference, Chengdu, China, 2025, pp. 1–5

    work page 2025

  2. [2]

    Efficient high-performance de- coding for overloaded MIMO antenna systems,

    K. Wong, A. Paulraj, and R. Murch, “Efficient high-performance de- coding for overloaded MIMO antenna systems,”IEEE Transactions on Wireless Communications, vol. 6, no. 5, pp. 1833–1843, May 2007

    work page 2007

  3. [3]

    Gaussian message passing for overloaded massive MIMO-NOMA,

    L. Liu, C. Yuen, Y . L. Guan, Y . Li, and C. Huang, “Gaussian message passing for overloaded massive MIMO-NOMA,”IEEE Transactions on Wireless Communications, vol. 18, no. 1, pp. 210–226, Nov. 2018

    work page 2018

  4. [4]

    Packet separation in phase noise impaired random access channel,

    M. Pajovic, G. Ozcan, T. Koike-Akino, P. Wang, and P. Orlik, “Packet separation in phase noise impaired random access channel,” inIEEE Global Communications Conference, Abu Dhabi, United Arab Emirates, 2018, pp. 1–7

    work page 2018

  5. [5]

    Multiuser detection of collided AIS packets with accurate estimates of Doppler frequencies,

    K. Nozaki, Y . Takanezawa, Y . Chang, K. Fukawa, and D. Hirahara, “Multiuser detection of collided AIS packets with accurate estimates of Doppler frequencies,” inIEEE V ehicular Technology Conference, 2021, pp. 1–5

    work page 2021

  6. [6]

    Detection algorithm and initial laboratory results using V-BLAST space-time communication architecture,

    G. D. Golden, C. J. Foschini, R. A. Valenzuela, and P. W. Wolniansky, “Detection algorithm and initial laboratory results using V-BLAST space-time communication architecture,”Electronics Letters, vol. 35, no. 1, pp. 14–16, 1999

    work page 1999

  7. [7]

    An iterative groupwise mul- tiuser detector for overloaded MIMO applications,

    B. Zarikoff, J. Cavers, and S. Bavarian, “An iterative groupwise mul- tiuser detector for overloaded MIMO applications,”IEEE Transactions on Wireless Communications, vol. 6, no. 2, pp. 443–447, Feb. 2007

    work page 2007

  8. [8]

    Enhanced V-BLAST performance in MIMO wireless communication systems,

    B. M. Lee, R. J. P. De Figueiredo, and Laboratory for Intelligent Signal Processing and Communications University of California, “Enhanced V-BLAST performance in MIMO wireless communication systems,” Synchroinfo Journal, vol. 7, no. 6, pp. 26–30, 2021

    work page 2021

  9. [9]

    Application of deep learning to sphere decoding for large MIMO systems,

    N. T. Nguyen, K. Lee, and H. Dai, “Application of deep learning to sphere decoding for large MIMO systems,”IEEE Transactions on Wireless Communications, vol. 20, no. 10, pp. 6787–6803, Oct. 2021

    work page 2021

  10. [10]

    2023 IRDS Chairman’s Editorial,

    IRDS, “2023 IRDS Chairman’s Editorial,” 2023

    work page 2023

  11. [11]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,”arXiv:1411.4028 [quant-ph], Nov. 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  12. [12]

    Quantum annealing in the transverse ising model,

    T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse ising model,”Physical Review E, vol. 58, no. 5, pp. 5355–5363, Jan. 1998

    work page 1998

  13. [13]

    Learning quantum many-body systems from a few copies,

    C. Rouz ´e and D. S. Franc ¸a, “Learning quantum many-body systems from a few copies,”Quantum, vol. 8, p. 1319, Apr. 2024

    work page 2024

  14. [14]

    Algorithms for quantum computation: discrete logarithms and factoring,

    P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” inIEEE Symposium on F oundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124–134

    work page 1994

  15. [15]

    A fast quantum mechanical algorithm for database search,

    L. K. Grover, “A fast quantum mechanical algorithm for database search,” inACM Symposium on Theory of Computing, Philadelphia, Pennsylvania, United States, 1996, pp. 212–219

    work page 1996

  16. [16]

    Quantum algorithm for solving linear systems of equations,

    A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for solving linear systems of equations,”Physical Review Letters, vol. 103, no. 15, p. 150502, Oct. 2009

    work page 2009

  17. [17]

    Grover adaptive search for constrained polynomial binary optimization,

    A. Gilliam, S. Woerner, and C. Gonciulea, “Grover adaptive search for constrained polynomial binary optimization,”Quantum, vol. 5, p. 428, Apr. 2021

    work page 2021

  18. [18]

    Quantum search algorithms for wireless commu- nications,

    P. Botsinis, D. Alanis, Z. Babar, H. V . Nguyen, D. Chandra, S. X. Ng, and L. Hanzo, “Quantum search algorithms for wireless commu- nications,”IEEE Communications Surveys Tutorials, vol. 21, no. 2, pp. 1209–1242, 2019

    work page 2019

  19. [19]

    Quantum-accelerated wireless communications: Concepts, connections, and implications,

    N. Ishikawa, G. T. F. de Abreu, P. Popovski, and R. W. Heath, “Quantum-accelerated wireless communications: Concepts, connections, and implications,”IEEE Communications Magazine, vol. 64, no. 3, pp. 156–162, Dec. 2025

    work page 2025

  20. [20]

    Quan- tum codes in classical communication: A space-time block code from quantum error correction,

    T. C. Cuvelier, S. A. Lanham, B. R. L. Cour, and R. W. Heath, “Quan- tum codes in classical communication: A space-time block code from quantum error correction,”IEEE Open Journal of the Communications Society, vol. 2, pp. 2383–2412, 2021

    work page 2021

  21. [21]

    Quantum approximate optimization algorithm based maximum likelihood detection,

    J. Cui, Y . Xiong, S. X. Ng, and L. Hanzo, “Quantum approximate optimization algorithm based maximum likelihood detection,”IEEE Transactions on Communications, vol. 70, no. 8, pp. 5386–5400, Aug. 2022

    work page 2022

  22. [22]

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

    B. G ¨ulbahar, “Maximum-likelihood detection with QAOA for massive MIMO and Sherrington-Kirkpatrick model with local field at infinite size,”IEEE Transactions on Wireless Communications, vol. 23, no. 9, pp. 11 567–11 579, Sep. 2024

    work page 2024

  23. [23]

    Leveraging quantum anealing for large MIMO processing in centralized radio access networks,

    M. Kim, D. Venturelli, and K. Jamieson, “Leveraging quantum anealing for large MIMO processing in centralized radio access networks,” in ACM Special Interest Group on Data Communication, Beijing, China, 2019, pp. 241–255

    work page 2019

  24. [24]

    Evaluation of quantum annealer performance via the massive MIMO problem,

    Z. I. Tabi, A. Marosits, Z. Kallus, P. Vaderna, I. Godor, and Z. Zimboras, “Evaluation of quantum annealer performance via the massive MIMO problem,”IEEE Access, vol. 9, pp. 131 658–131 671, 2021

    work page 2021

  25. [25]

    Fixed-complexity quantum-assisted multi-user detection for CDMA and SDMA,

    P. Botsinis, S. X. Ng, and L. Hanzo, “Fixed-complexity quantum-assisted multi-user detection for CDMA and SDMA,”IEEE Transactions on Communications, vol. 62, no. 3, pp. 990–1000, 2014

    work page 2014

  26. [26]

    Quantum search algorithm for binary constant weight codes,

    K. Yukiyoshi and N. Ishikawa, “Quantum search algorithm for binary constant weight codes,”Quantum Information Processing, vol. 23, no. 10, p. 360, Oct. 2024

    work page 2024

  27. [27]

    Qubit reduction and quantum speedup for wireless channel assignment problem,

    Y . Sano, M. Norimoto, and N. Ishikawa, “Qubit reduction and quantum speedup for wireless channel assignment problem,”IEEE Transactions on Quantum Engineering, pp. 1–12, 2023

    work page 2023

  28. [28]

    Quantum speedup of the dispersion and codebook design problems,

    K. Yukiyoshi, T. Mikuriya, H. S. Rou, G. T. F. de Abreu, and N. Ishikawa, “Quantum speedup of the dispersion and codebook design problems,”IEEE Transactions on Quantum Engineering, vol. 5, pp. 1– 16, Aug. 2024

    work page 2024

  29. [29]

    Quantum algorithm for higher-order unconstrained binary optimization and MIMO maximum likelihood detection,

    M. Norimoto, R. Mori, and N. Ishikawa, “Quantum algorithm for higher-order unconstrained binary optimization and MIMO maximum likelihood detection,”IEEE Transactions on Communications, vol. 71, no. 4, pp. 1926–1939, Apr. 2023

    work page 1926

  30. [30]

    Quantum speedup for mul- tiuser detection with optimized parameters in Grover adaptive search,

    M. Norimoto, T. Mikuriya, and N. Ishikawa, “Quantum speedup for mul- tiuser detection with optimized parameters in Grover adaptive search,” IEEE Access, vol. 12, pp. 83 810–83 821, 2024

    work page 2024

  31. [31]

    A Quantum Algorithm for Finding the Minimum

    C. Durr and P. Hoyer, “A quantum algorithm for finding the minimum,” arXiv:quant-ph/9607014, Jan. 1999

    work page internal anchor Pith review Pith/arXiv arXiv 1999

  32. [32]

    Tight bounds on quantum searching,

    M. Boyer, G. Brassard, P. Hoeyer, and A. Tapp, “Tight bounds on quantum searching,”F ortschritte der Physik, vol. 46, no. 4-5, pp. 493– 505, Jun. 1998

    work page 1998

  33. [33]

    ProjectQ: An open source software framework for quantum computing,

    D. S. Steiger, T. H ¨aner, and M. Troyer, “ProjectQ: An open source software framework for quantum computing,”Quantum, vol. 2, p. 49, Jan. 2018

    work page 2018

  34. [34]

    Efficient quantum algorithms for GHZ and W states, and implementation on the IBM quantum computer,

    D. Cruz, R. Fournier, F. Gremion, A. Jeannerot, K. Komagata, T. Tosic, J. Thiesbrummel, C. L. Chan, N. Macris, M. A. Dupertuis, and C. J. Galy, “Efficient quantum algorithms for GHZ and W states, and implementation on the IBM quantum computer,”Advanced Quantum Technologies, vol. 2, no. 5-6, p. 1900015, Jun. 2019

    work page 2019

  35. [35]

    M. A. Nielsen and I. L. Chuang,Quantum computation and quantum information. Cambridge University Press, 2010

    work page 2010

  36. [36]

    Performance analysis of a linear MMSE receiver in time-variant Rayleigh fading channels,

    G. Fodor, S. Fodor, and M. Telek, “Performance analysis of a linear MMSE receiver in time-variant Rayleigh fading channels,”IEEE Trans- actions on Communications, vol. 69, no. 6, pp. 4098–4112, Jun. 2021

    work page 2021

  37. [37]

    Semidefinite relaxation of quadratic optimization problems,

    Z. Luo, W. Ma, A. So, Y . Ye, and S. Zhang, “Semidefinite relaxation of quadratic optimization problems,”IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 20–34, May 2010

    work page 2010