Qubit efficient algorithms for binary optimization problems
B. Tan, M. A. Lemonde, S. Thanasilp, J. Tangpanitanon, D. G. Angelakis
Quantum 5, 454
Doing binary optimization problems either via quantum annealing or QAOA require as many qubits as in the classical variables. Realistic quadratic optimization problems (QUBO) usually entail 10.000 classical variables which means current approaches using NISQ devices are very far from achieving anything of real applications. In this work, we proposed and analyzed a set of novel variational quantum algorithms for QUBO where n classical variables can be implemented on O(log n) number of qubits. Our encoding scheme allows for a systematic increase in correlations among the classical variables captured by a given quantum state by progressively increasing the number of qubits. We apply this minimal encoding to find approximate solutions of a general problem instances comprised of 64 classical variables using 7 qubits. Next, we show how two-body correlations can be incorporated in the variational quantum state and how it can improve the quality of the approximate solutions. We give examples by solving a 42-variable Max-Cut problem using only 8 qubits where we exploit the specific topology of the problem. We analyze whether these cases can be optimized efficiently given the limited resources available in state-of-the-art quantum platforms. Lastly, we present the general framework for extending the expressibility of the probability distribution to any multi-body correlations.