[17a-M_B07-1~9] KS.2 Quantum Information Engineering Group

9:30 AM - 9:45 AM JST(12:30 AM - 12:45 AM UTC)

[17a-M_B07-3] Absence of Local Minima and Convergence to the Global Optimum in Quantum Gradient Descent for Combinatorial Optimization Problems

〇Haruya Nagata¹, Takumi Kanezashi¹, Tomoki Matsunaga¹, Yuka Kondo¹, Jun-ichi Shirakashi¹, Tetsuo Shibuya², Hiroshi Imai² (1.Tokyo Univ. Agr. & Tech., 2.Univ. Tokyo)

Keywords:

Quantum Gradient Descent,Quantum Algorithm,Combinatorial Optimization

近年、量子計算機を用いて組合せ最適化問題を解くための新たな方法として量子勾配降下法が注目されている。本研究では、ラグランジュの未定乗数法とヘッセ行列の定値性を用いて、組合せ最適化問題における量子勾配降下法の解空間には局所解がなく、大域解と鞍点のみであることを理論的に示した。また、実際にMaxCut問題の求解を行い、大域解へ収束することを実験的に確認した。