Transfer learning of optimal QAOA parameters in combinatorial optimization

Abstract

Solving combinatorial optimization problems (COPs) is a promising application of quantum computation, with the Quantum Approximate Optimization Algorithm (QAOA) being one of the most studied quantum algorithms for solving them. However, multiple factors make the parameter search of the QAOA a hard optimization problem. In this work, we study transfer learning (TL), a methodology to reuse pre-trained QAOA parameters of one problem instance into different COP instances. This methodology can be used to alleviate the necessity of classical optimization to find good parameters for individual problems. To this end, we select small cases of the traveling salesman problem (TSP), the bin packing problem (BPP), the knapsack problem (KP), the weighted maximum cut (MaxCut) problem, the maximal independent set (MIS) problem, and portfolio optimization (PO), and find optimal $\beta$ and $\gamma$ parameters for p layers. We compare how well the parameters found for one problem adapt to the others. Among the different problems, BPP is the one that produces the best transferable parameters, maintaining the probability of finding the optimal solution above a quadratic speedup over random guessing for problem sizes up to 42 qubits and p = 10 layers. Using the BPP parameters, we perform experiments on IonQ Harmony and Aria, Rigetti Aspen-M-3, and IBM Brisbane of MIS instances for up to 18 qubits. The results indicate that IonQ Aria yields the best overlap with the ideal probability distribution. Additionally, we show that cross-platform TL is possible using the D-Wave Advantage quantum annealer with the parameters found for BPP. We show an improvement in performance compared to the default protocols for MIS with up to 170 qubits. Our results suggest that there are QAOA parameters that generalize well for different COPs and annealing protocols.

15 pages, 10 figures

References in corpus (25)

• Variational Quantum Algorithms
• Ising formulations of many NP problems
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Training variational quantum algorithms is NP-hard
• Warm-starting quantum optimization
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• A scalable control system for a superconducting adiabatic quantum optimization processor
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Reachability Deficits in Quantum Approximate Optimization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Performance comparison of optimization methods on variational quantum algorithms
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Quantum-Informed Recursive Optimization Algorithms
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-constrained Optimization Approach
• Guided quantum walk
• Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• Evolutionary Bin Packing for Memory-Efficient Dataflow Inference Acceleration on FPGA

Cited by in corpus (5)

• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Quantum Approximate Multi-Objective Optimization
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem