Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems

Tatsuhiko Shirai*, Nozomu Togawa


研究成果: Article査読


In this article, we propose a postprocessing variationally scheduled quantum algorithm (pVSQA) for solving constrained combinatorial optimization problems (COPs). COPs are typically transformed into ground-state search problems of the Ising model on a quantum annealer or gate-based quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Postprocessing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. The pVSQA combines the variational methods and the postprocessing technique. We obtain a sufficient condition for constrained COPs to apply the pVSQA based on a greedy postprocessing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. The pVSQA on a simulator shows that a small number of variational parameters is sufficient to achieve a (near-) optimal performance within a predetermined operation time. Then, building upon the simulator results, we implement the pVSQA on a quantum annealer and a gate-based quantum device. The experimental results demonstrate the effectiveness of our proposed method.

ジャーナルIEEE Transactions on Quantum Engineering
出版ステータスPublished - 2024

ASJC Scopus subject areas

  • ソフトウェア
  • コンピュータ サイエンス(その他)
  • 凝縮系物理学
  • 機械工学
  • 工学(その他)
  • 電子工学および電気工学
  • コンピュータ サイエンスの応用


「Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。