{"id":3070550,"date":"2024-01-18T07:23:15","date_gmt":"2024-01-18T12:23:15","guid":{"rendered":"https:\/\/wordpress-1016567-4521551.cloudwaysapps.com\/plato-data\/parameter-setting-in-quantum-approximate-optimization-of-weighted-problems\/"},"modified":"2024-01-18T07:23:15","modified_gmt":"2024-01-18T12:23:15","slug":"parameter-setting-in-quantum-approximate-optimization-of-weighted-problems","status":"publish","type":"station","link":"https:\/\/platodata.io\/plato-data\/parameter-setting-in-quantum-approximate-optimization-of-weighted-problems\/","title":{"rendered":"Parameter Setting in Quantum Approximate Optimization of Weighted Problems"},"content":{"rendered":"
\n

Shree Hari Sureshbabu1<\/sup>, Dylan Herman1<\/sup>, Ruslan Shaydulin1<\/sup>, Joao Basso2<\/sup>, Shouvanik Chakrabarti1<\/sup>, Yue Sun1<\/sup>, and Marco Pistoia1<\/sup><\/p>\n

1<\/sup>Global Technology Applied Research, JPMorgan Chase, New York, NY 10017
2<\/sup>Department of Mathematics, University of California, Berkeley, CA 94720<\/p>\n

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate<\/a>.<\/p>\n<\/header>\n

\n

Abstract<\/h3>\n

Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth $p=1$ applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for $pgeq 1$ we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for $p=1$ the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only $1.1$ percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.<\/p>\n

\n
<\/div>\n

Featured image: Procedure for transferring optimal QAOA parameters from the Sherrington-Kirkpatrick (SK) model to a weighted MaxCut problem on a regular graph of the same size. The $gamma^{text{inf}}$ parameters are scaled according to the proposed method, while the $beta^{text{inf}}$ are fixed. The plot shows that QAOA with the novel scaling technique achieves higher approximation ratio than prior techniques and comparable to optimized parameters.<\/p>\n<\/div>\n

Popular summary<\/a><\/h3>\n
This work investigates parameter setting rules for QAOA, a leading quantum heuristic algorithm, applied to a general class of combinatorial optimization problems. Parameter optimization is a significant bottleneck towards near-term application. A general parameter-scaling heuristic for transferring QAOA parameters between weighted problem instances is proposed and rigorous results showing the effectiveness of this procedure on MaxCut is presented. Additionally, the numerics show that this procedure significantly reduces the training time of QAOA for portfolio optimization, which is an important problem in financial engineering<\/div>\n

\u25ba BibTeX data<\/a><\/h3>\n