Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection

Abstract

In this paper, we propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization (HUBO) problem. This algorithm is based on the Grover adaptive search that originally supported HUBO with integer coefficients. Next, as an application example, we formulate multiple-input multiple-output maximum likelihood detection as a HUBO problem with real-valued coefficients, where we use the Gray-coded bit-to-symbol mapping specified in the 5G standard. The proposed approach allows us to construct an efficient quantum circuit for the detection problem and to analyze specific numbers of required qubits and quantum gates, whereas other conventional studies have assumed that such a circuit is feasible as a quantum oracle. To further accelerate the quantum algorithm, we also derive a probability distribution of the objective function value and determine a unique threshold to sample better states. Assuming a future fault-tolerant quantum computing, our proposed algorithm has the potential for significantly reducing query complexity in the classical domain and providing a quadratic speedup in the quantum domain.

14 pages, 14 figures, accepted for publication in IEEE Transactions on Communications

References in corpus (3)

• Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks
• Noise Threshold of Quantum Supremacy
• Optimizing Quantum Search Using a Generalized Version of Grover's Algorithm

Cited by in corpus (5)

• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Quantum Speedup of the Dispersion and Codebook Design Problems
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Grover Adaptive Search with Spin Variables