Maximum-Likelihood Detection With QAOA for Massive MIMO and Sherrington-Kirkpatrick Model With Local Field at Infinite Size
Burhan Gülbahar
Abstract
Quantum-approximate optimization algorithm (QAOA) is promising in Noisy Intermediate-Scale Quantum (NISQ) computers with applications for NP-hard combinatorial optimization problems. It is recently utilized for NP-hard maximum-likelihood (ML) detection problem with challenges of optimization, simulation and performance analysis for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> × <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> multiple-input multiple output (MIMO) systems with large <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> . QAOA is recently applied by Farhi et al. on infinite size limit of Sherrington-Kirkpatrick (SK) model with a cost model including only quadratic terms. In this article, we extend the model by including also linear terms and then realize SK modeling of massive MIMO ML detection. The proposed design targets near ML performance while with complexity including <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> (16 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>p</i></sup> ) initial operations independent from problem instance and size <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> for optimizing QAOA angles and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> ) quantum operations for each instance. We provide both optimized and extrapolated angles for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> ∈ [1, 14] and signal-to-noise (SNR) < 12 dB achieving near-optimum ML performance with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> ≥ 4 for 25×25 and 12 × 12 MIMO systems modulated with BPSK and QPSK, respectively. We present two conjectures about concentration properties of QAOA and near-optimum performance for next generation massive MIMO systems covering <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> < 300.