Quantum-Guided Cluster Algorithms for Combinatorial Optimization

• URL: http://arxiv.org/abs/2508.10656v1
• Date: Thu, 14 Aug 2025 13:54:56 GMT
• Title: Quantum-Guided Cluster Algorithms for Combinatorial Optimization
• Abstract summary: We introduce a novel algorithm for finding the ground state of Ising spin glasses.<n>Various classical and quantum algorithms can be employed to generate correlations that embody information about the energy landscape of the problem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding the ground state of Ising spin glasses is notoriously difficult due to disorder and frustration. Often, this challenge is framed as a combinatorial optimization problem, for which a common strategy employs simulated annealing, a Monte Carlo (MC)-based algorithm that updates spins one at a time. Yet, these localized updates can cause the system to become trapped in local minima. Cluster algorithms (CAs) were developed to address this limitation and have demonstrated considerable success in studying ferromagnetic systems; however, they tend to encounter percolation issues when applied to generic spin glasses. In this work, we introduce a novel CA designed to tackle these challenges by leveraging precomputed two-point correlations, aiming solve combinatorial optimization problems in the form of Max-Cut more efficiently. In our approach, clusters are formed probabilistically based on these correlations. Various classical and quantum algorithms can be employed to generate correlations that embody information about the energy landscape of the problem. By utilizing this information, the algorithm aims to identify groups of spins whose simultaneous flipping induces large transitions in configuration space with high acceptance probability -- even at low energy levels -- thereby escaping local minima more effectively. Notably, clusters generated using correlations from the Quantum Approximate Optimization Algorithm exhibit high acceptance rates at low temperatures. These acceptance rates often increase with circuit depth, accelerating the algorithm and enabling more efficient exploration of the solution space.

Related papers

• Decomposition-Based QAOA for Maximum Coverage Location Problem in Satellite Constellation Design [4.190898032627423]
  maximizing coverage while utilizing limited orbital resources is one of the critical design challenges for complex optimization problems.<n>The maximal covering location problem (MCLP), serves as a base for orbital coverage modeling, is NP-hard and computationally intractable for large-constellation instances.<n>This paper proposes a scalable quantum optimization framework for MCLP in satellite constellation design.
  arXiv  Detail & Related papers  (2026-07-09T04:39:44Z)
• Better LMO-based Momentum Methods with Second-Order Information [48.580700968416444]
  Hessian-Corrected Momentum (HCM) aims to improve momentum convergence rates.<n>Hessian-Corrected Momentum can adapt to the geometry of the problem and achieve a faster rate than traditional momentum.<n>We extend the Linear Minimization Oracle framework by integrating HCM, and provide convergence guarantees under relaxed smoothness and arbitrary norm settings.
  arXiv  Detail & Related papers  (2025-12-15T11:43:09Z)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  We propose a novel quantum algorithm for the Minimum Vertex Cover (MVC) problem based on continuous-time quantum walks (CTQWs)<n>In this framework, the coherent propagation of a quantum walker over a graph encodes its structural properties into state amplitudes.<n>We show that the CTQW-based algorithm consistently achieves superior approximation ratios and exhibits remarkable robustness with respect to network topology.
  arXiv  Detail & Related papers  (2025-12-02T17:04:57Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking [45.147301546565316]
  This paper considers the problem of decentralized optimization on compact submanifolds.<n>We propose an algorithm where agents update variables using quantized variables.<n>To the best of our knowledge, this is the first algorithm to achieve an $mathcalO (1/K)$ convergence rate in the presence of quantization.
  arXiv  Detail & Related papers  (2025-06-09T01:57:25Z)
• Learning with Local Search MCMC Layers [11.772298193297013]
  We introduce a theoretically-principled approach for learning with inexact solvers.<n>We transform problem-specific neighborhood systems used in local searchs into proposal distributions.<n>We demonstrate our approach on a large-scale dynamic vehicle routing problem with time windows.
  arXiv  Detail & Related papers  (2025-05-20T11:47:42Z)
• Qubit-efficient quantum local search for combinatorial optimization [0.0]
  We present a qubit-efficient variational quantum algorithm that implements a quantum version of local search with only $lceil log l rceil$ qubits.<n>This achievement highlights the algorithm's potential for solving large-scale optimization problems on near-term quantum devices.
  arXiv  Detail & Related papers  (2025-02-04T11:44:34Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• Hybrid discrete-continuous compilation of trapped-ion quantum circuits with deep reinforcement learning [1.7087507417780985]
  We show that we can significantly reduce the size of relevant quantum circuits for trapped-ion computing.<n>Our framework can also be applied to an experimental setup whose goal is to reproduce an unknown unitary process.
  arXiv  Detail & Related papers  (2023-07-12T14:55:28Z)
• A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms [18.075115172621096]
  We present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs via Ising solvers. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm.
  arXiv  Detail & Related papers  (2022-07-27T16:47:32Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization [1.1783108699768]
  We introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo (NMC) algorithms by developing an adaptive gradient-free strategy. We observe significant speedup and robustness over both specialized solvers and generic solvers.
  arXiv  Detail & Related papers  (2021-11-26T17:45:32Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)

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.