Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems

Tatsuhiko Shirai*, Nozomu Togawa

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number3101114
Pages (from-to)1-14
Number of pages14
JournalIEEE Transactions on Quantum Engineering
Volume5
DOIs
Publication statusPublished - 2024

Keywords

  • Combinatorial optimization problem (COP)
  • Ising model
  • metaheuristics
  • quantum device
  • variational quantum algorithm

ASJC Scopus subject areas

  • Software
  • Computer Science (miscellaneous)
  • Condensed Matter Physics
  • Mechanical Engineering
  • Engineering (miscellaneous)
  • Electrical and Electronic Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems'. Together they form a unique fingerprint.

Cite this