Quantum Partial Sorting for Signal Decoding in Wireless Communication Systems

Abstract

This work proposes a novel quantum-assisted partial sorting algorithm, called multi-minima Dürr–Høyer (MMDH), designed to reduce query complexity in scenarios where only a small subset of elements must be sorted. Empirical results show that MMDH significantly outperforms classical algorithms in these settings, achieving over an order of magnitude reduction in query complexity. The algorithm is applied to signal detection in multiple-input multiple-output systems and is particularly effective when integrated into a newly introduced variable-complexity sphere decoder, called progressive tree expansion (PTE), which inherently benefits from partial sorting. Compared to fixed-complexity sphere decoders (FCSDs), the PTE algorithm substantially reduces the computational complexity, especially at high signal-to-noise ratios (SNRs). When augmented with MMDH, the quantum-assisted PTE decoder achieves near maximum-likelihood error performance while mitigating the query overhead commonly associated with tree-based decoders. In contrast, conventional FCSDs benefit less from MMDH, as they require selection of multiple minima rather than partial ordering, a task where classical methods such as heap-based selection remain competitive. Although MMDH introduces a small failure probability, the resulting error floor stays below practical thresholds in high-SNR regimes.