Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems
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. V...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10472069/ |
| _version_ | 1797213588325138432 |
|---|---|
| author | Tatsuhiko Shirai Nozomu Togawa |
| author_facet | Tatsuhiko Shirai Nozomu Togawa |
| author_sort | Tatsuhiko Shirai |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-24T11:00:40Z |
| format | Article |
| id | doaj.art-53919177b93a49f4ab12835ba7e938dc |
| institution | Directory Open Access Journal |
| issn | 2689-1808 |
| language | English |
| last_indexed | 2024-04-24T11:00:40Z |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj.art-53919177b93a49f4ab12835ba7e938dc2024-04-11T23:00:54ZengIEEEIEEE Transactions on Quantum Engineering2689-18082024-01-01511410.1109/TQE.2024.337672110472069Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization ProblemsTatsuhiko Shirai0https://orcid.org/0000-0001-7375-4119Nozomu Togawa1https://orcid.org/0000-0003-3400-3587Department of Computer Science and Communications Engineering, Waseda University, Tokyo, JapanDepartment of Computer Science and Communications Engineering, Waseda University, Tokyo, JapanIn 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.https://ieeexplore.ieee.org/document/10472069/Combinatorial optimization problem (COP)Ising modelmetaheuristicsquantum devicevariational quantum algorithm |
| spellingShingle | Tatsuhiko Shirai Nozomu Togawa Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems IEEE Transactions on Quantum Engineering Combinatorial optimization problem (COP) Ising model metaheuristics quantum device variational quantum algorithm |
| title | Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems |
| title_full | Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems |
| title_fullStr | Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems |
| title_full_unstemmed | Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems |
| title_short | Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems |
| title_sort | postprocessing variationally scheduled quantum algorithm for constrained combinatorial optimization problems |
| topic | Combinatorial optimization problem (COP) Ising model metaheuristics quantum device variational quantum algorithm |
| url | https://ieeexplore.ieee.org/document/10472069/ |
| work_keys_str_mv | AT tatsuhikoshirai postprocessingvariationallyscheduledquantumalgorithmforconstrainedcombinatorialoptimizationproblems AT nozomutogawa postprocessingvariationallyscheduledquantumalgorithmforconstrainedcombinatorialoptimizationproblems |