Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2309.08120 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909168616603648 |
|---|---|
| author | Shirai, Tatsuhiko Togawa, Nozomu |
| author_facet | Shirai, Tatsuhiko Togawa, Nozomu |
| contents | We propose a post-processing 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-type quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. 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 pVSQA on a quantum annealer and a gate-type quantum device. The experimental results demonstrate the effectiveness of our proposed method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_08120 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems Shirai, Tatsuhiko Togawa, Nozomu Quantum Physics We propose a post-processing 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-type quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. 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 pVSQA on a quantum annealer and a gate-type quantum device. The experimental results demonstrate the effectiveness of our proposed method. |
| title | Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2309.08120 |