Solving Large-Scale QUBO with Transferred Parameters from Multilevel QAOA of low depth

• URL: http://arxiv.org/abs/2505.11464v1
• Date: Fri, 16 May 2025 17:18:36 GMT
• Title: Solving Large-Scale QUBO with Transferred Parameters from Multilevel QAOA of low depth
• Authors: Bao G Bach, Filip B. Maciejewski, Ilya Safro,
• Abstract summary: We propose a fast hybrid multilevel algorithm with QAOA parameterization throughout the multilevel hierarchy and its reinforcement with genetic algorithms.<n>Results highlight the practical potential of multilevel QAOA as a scalable method for optimization on near-term quantum devices.
• Score: 2.1215729831364887
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum approach for tackling combinatorial optimization problems. However, hardware constraints such as limited scaling and susceptibility to noise pose significant challenges when applying QAOA to large instances. To overcome these limitations, scalable hybrid multilevel strategies have been proposed. In this work, we propose a fast hybrid multilevel algorithm with QAOA parameterization throughout the multilevel hierarchy and its reinforcement with genetic algorithms, which results in a high-quality, low-depth QAOA solver. Notably, we propose parameter transfer from the coarsest level to the finer level, showing that the relaxation-based coarsening preserves the problem structural information needed for QAOA parametrization. Our strategy improves the coarsening phase and leverages both Quantum Relax \& Round and genetic algorithms to incorporate $p=1$ QAOA samples effectively. The results highlight the practical potential of multilevel QAOA as a scalable method for combinatorial optimization on near-term quantum devices.

Related papers

• Hybrid quantum optimization in the context of minimizing traffic congestion [0.0]
  We benchmark solutions obtained from the Quantum Approximate optimization Algorithm (QAOA)<n>In principle, as the number of QAOA layers approaches infinity, the solutions should reach optimality.<n>For NISQ devices with limited qubit connectivity and circuit depth, we introduce a noise-resilient variant of QAOA.<n>Our results show that this QAOA variant is surprisingly effective, outperforming QAOA on a physical IBM Quantum computer device.
  arXiv  Detail & Related papers  (2025-04-11T06:15:23Z)
• MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
  Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling optimization challenges. The requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices. We introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians.
  arXiv  Detail & Related papers  (2024-09-27T12:28:18Z)
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack [0.0]
  variational quantum algorithms (VQAs) are a promising family of hybrid quantum-classical methods tailored to cope with the limited capability of near-term quantum hardware.<n>We show that leveraging regular parameter patterns deeply affects the decision-tree structure and allows for a flexible and noise-resilient optimization strategy.
  arXiv  Detail & Related papers  (2024-08-22T18:00:02Z)
• Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem [3.3682090109106446]
  We propose the Variational Quantum Algorithm-Preserving Feasible Space (VQA-PFS) ansatz. This ansatz applies mixed operators on constrained variables while employing Hardware-Efficient Ansatz (HEA) on unconstrained variables. The numerical results demonstrate that VQA-PFS significantly enhances the success probability and exhibits faster convergence.
  arXiv  Detail & Related papers  (2023-12-12T01:36:49Z)
• Benchmarking Metaheuristic-Integrated QAOA against Quantum Annealing [0.0]
  The study provides insights into the strengths and limitations of both Quantum Annealing and metaheuristic-integrated QAOA across different problem domains. The findings suggest that the hybrid approach can leverage classical optimization strategies to enhance the solution quality and convergence speed of QAOA.
  arXiv  Detail & Related papers  (2023-09-28T18:55:22Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• 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)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• 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)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• 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.