Quantum Speedup for Multiuser Detection With Optimized Parameters in Grover Adaptive Search

Abstract

Maximum-likelihood multiuser detection incurs a large computational complexity, and its low-complexity detection scheme suffers from a performance loss, where this tradeoff is inevitable and inherent in a classical computer. In this paper, we use the Grover adaptive search (GAS) to break the tradeoff, which is a quantum exhaustive search algorithm guaranteed to obtain the optimal solution, achieving a quadratic speedup. Specifically, we design two specific parameters of GAS to achieve the optimal performance with a reduced complexity: the initial threshold and the number of Grover rotations. The initial threshold of GAS can be optimized using a solution of semi-definite programming, and it is possible to calculate the distribution of the number of solutions smaller than the initial threshold in advance, which depends on instantaneous channel coefficients. In addition, we analyze the number of quantum gates required for GAS and show that the gate count can be reduced by bypassing the higher-order terms in the objective function, leading to a reduced circuit runtime. Our analysis and simulation results demonstrate that the proposed approach achieves the same performance as the optimal maximum-likelihood detection while reducing the query complexity of GAS, implying that the large constant overhead of quadratic speedup can be further reduced.

Keywords

• Grover adaptive search
• multiple-input multiple-output
• multiuser detection
• quadratic speedup
• semi-definite programming