Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
arXiv:2309.08120 · doi:10.1109/TQE.2024.3376721
Abstract
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.
arXiv comment14 pages, 8 figures
References in corpus (21)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Approximate Optimization Algorithm
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum Computation by Adiabatic Evolution
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
- Improving Variational Quantum Optimization using CVaR
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- Optimal Protocols in Quantum Annealing and QAOA Problems
- Quantum variational optimization: The role of entanglement and problem hardness
- Benchmarking simulated and physical quantum processing units using quantum and hybrid algorithms
- Toward Practical-Scale Quantum Annealing Machine for Prime Factoring
- Convergence of Quantum Annealing with Real-Time Schrodinger Dynamics
- Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme
- Designing Quantum Annealing Schedules using Bayesian Optimization
- Variationally Scheduled Quantum Simulation
- Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm
- Diabatic Quantum Annealing for the Frustrated Ring Model
Cited by in corpus (5)
- Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
- LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
- Improving the efficiency of quantum annealing with controlled diagonal catalysts
- IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
- Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing