Approximate Solutions to Quantum Problems

Daniel R. Bes

И. В. Амирханов, V.S. Gurianov

Ken N. Okada, Hirofumi Nishi, Taichi Kosugi +1 more

Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm to solve combinatorial optimization problems in the era of noisy intermediate-scale quantum computers. Recently it has been revealed that warm-start approaches can improve the performance of QAOA, where approximate solutions are obtained by classical algorithms in advance and incorporated into the initial state and/or unitary ansatz. In this work, we study in detail how the accuracy of approximate solutions affects the performance of the warm-start QAOA (WS-QAOA). We numerically find that in typical MAX-CUT problems, WS-QAOA achieves higher fidelity (probability that exact solutions are observed) and approximation ratio than QAOA as the Hamming distance of approximate solutions to the exact ones becomes smaller. We reveal that this could be quantitatively attributed to the initial state of the ansatz. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having higher fidelity and approximation ratio than QAOA especially when the circuit is relatively shallow. We believe that our study may deepen understanding of the performance of WS-QAOA and also provide a guide as to the necessary quality of approximate solutions.

Ali Al-Bayaty, Marek A. Perkowski

This article investigates the performance impact of five classical optimization approximation algorithms on our previously introduced quantum search algorithm, termed the Boolean–Hamiltonians Transform for Quantum Approximate Optimization Algorithm (BHT-QAOA), to effectively search for all best-approximated solutions for Boolean-based problems. These optimization approximation algorithms are BFGS, L-BFGS-B, SLSQP, COBYLA, and COBYQA. Their performance impact is evaluated and compared using two proposed performance metrics—(i) the final number of function evaluations (the lower numbers denote the best optimization approximation algorithms) and (ii) the final quality of qubit measurements (the higher values indicate all best-approximated solutions were found for a problem). Arbitrary classical Boolean problems in various logical structures were examined and evaluated using the BHT-QAOA, these five optimization approximation algorithms, and a simulated noisy model of an IBM quantum computer. Broadly, the BHT-QAOA, with these five algorithms, successfully finds all optimized approximated solutions for these problems. Specifically, both the BFGS and SLSQP algorithms successfully find all best-approximated solutions for these problems, in the context of fewer function evaluations and higher quality of qubit measurements.