Transfer learning of optimal QAOA parameters in combinatorial optimization

• URL: http://arxiv.org/abs/2402.05549v1
• Date: Thu, 8 Feb 2024 10:35:23 GMT
• Title: Transfer learning of optimal QAOA parameters in combinatorial optimization
• Authors: J. A. Montanez-Barrera, Dennis Willsch, Kristel Michielsen
• Abstract summary: We study the transfer learning (TL) methodology to reuse pre-trained QAOA parameters of one problem instance into different COP instances. In this work, 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, and portfolio optimization (PO) We show that cross-platform TL is possible using the D-Wave Advantage quantum annealer with the parameters found for BPP.
• Score: 0.46040036610482665
• License: http://creativecommons.org/licenses/by/4.0/
• 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. 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 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 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.

Related papers

• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots [2.906880059847219]
  We develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We implement a trapped-ion processor using up to 32 qubits and 5 QAOA layers. We demonstrate that the pipeline is robust to small amounts of hardware noise.
  arXiv  Detail & Related papers  (2024-08-01T13:39:40Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems [10.396104620517171]
  In this work, we develop parameter settings for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth $p=1$ applied to the weighted MaxCut problem under different assumptions on the weights. Second, for $pgeq 1$ we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Third, we propose a general rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness.
  arXiv  Detail & Related papers  (2023-05-24T14:37:33Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz [0.0]
  We introduce a strategy for parameter setting suitable for common cases in which the number of distinct cost values grows onlyly with the problem size. We define a Classical Homogeneous Proxy for QAOA in which Perfect Homogeneity holds exactly, and which yields information describing both states and expectation values. For up to $3$ QAOA levels we are easily able to find parameters that match approximation ratios returned by previous globally optimized approaches.
  arXiv  Detail & Related papers  (2022-11-17T00:18:06Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm [3.508346077709686]
  We study unsupervised Machine Learning approaches for setting parameters without optimization. We showcase them within Recursive-QAOA up to depth $3$ where the number of QAOA parameters used per iteration is limited to $3$. We obtain similar performances to the case where we extensively optimize the angles, hence saving numerous circuit calls.
  arXiv  Detail & Related papers  (2022-02-18T19:55:42Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
  arXiv  Detail & Related papers  (2021-08-11T15:44:16Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.