We study correlation-guided cluster algorithms for solving the Max-Cut problem that iteratively try to improve solutions by updating clusters of nodes. Building on the recently proposed quantum-guided cluster algorithm (QGCA) [arXiv:2508.10656], which leverages precomputed two-point correlations to guide collective updates, we extend the cluster construction by incorporating next-nearest-neighbor (NNN) information. We evaluate this extension across different correlation sources on random regular graphs and non-degenerate tile-planted instances. Notably, we observe particularly strong performance on non-degenerate instances and provide a scaling analysis for this class. Finally, we outline an extension toward a correlation-guided Markov-chain Monte Carlo algorithm, whose detailed analysis remains an open direction for future work.
We study correlation-guided cluster algorithms for solving the Max-Cut problem that iteratively try to improve solutions by updating clusters of nodes. Building on the recently proposed quantum-guided cluster algorithm (QGCA) [arXiv:2508.10656], which leverages precomputed two-point correlations to guide collective updates, we extend the cluster construction by incorporating next-nearest-neighbor (NNN) information. We evaluate this extension across different correlation sources on random regular graphs and non-degenerate tile-planted instances. Notably, we observe particularly strong performance on non-degenerate instances and provide a scaling analysis for this class. Finally, we outline an extension toward a correlation-guided Markov-chain Monte Carlo algorithm, whose detailed analysis remains an open direction for future work.
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.
Of late, we are witnessing spectacular developments in Quantum Information Processing with the availability of Noisy Intermediate-Scale Quantum devices of different architectures and various software development kits to work on quantum algorithms. Different problems, which are hard to solve by classical computation, but can be sped up (significantly in some cases) are also being populated. Leveraging these aspects, this paper examines unsupervised graph clustering by quantum algorithms or, more precisely, quantum-assisted algorithms. By carefully examining the two cluster Max-Cut problem within the framework of quantum Ising model, an extension has been worked out for max 3-cut with the identification of an appropriate Hamiltonian. Representative results, after carrying out extensive numerical evaluations, have been provided including a suggestion for possible futuristic implementation with qutrit devices. Further, extrapolation to more than 3 classes, which can be handled by qudits, of both annealer and gate-circuit varieties, has also been touched upon with some preliminary observations; quantum-assisted solving of Quadratic Unconstrained D-ary Optimisation is arrived at within this context. As an additional novelty, a qudit circuit to solve max-d cut through Quantum Approximate Optimization algorithm is systematically constructed.
The quantum approximation optimisation algorithm (QAOA) is one of the leading
candidates for testing the applicability of gate-model quantum resources at solving
optimisation problems on small-sized quantum hardware. A combinatorial problem that
has been understudied with QAOA is correlation clustering: given a weighted (+1,-1)
graph, where the edge weights indicate whether two nodes are similar (positive edge
weight) or different (negative edge weight), the task in correlation clustering is to find a
clustering that either maximises agreements, minimises disagreements or a combination
of both. In this thesis, we design Hamiltonian formulations that encode correlation
clustering problems such that they can be solved with QAOA. For all Hamiltonian
formulations we propose circuit implementations and study their complexities. To
benchmark the performances of a basic QAOA algorithm using these formulations, we
use numerical simulations on complete graph data sets. For one of the formulations,
which uses a multi-level approach naturally suitable to qudit systems, we investigate
the performances of several optimisers and introduce heuristic strategies to further
improve its performance. On all instances in our data-sets, which include complete as
well as Erdős–Renyi graphs, the improved algorithm shows competitive performances
for QAOA depth p ≥ 2. We also show that for this algorithm at p = 1 parameters exists
such that it has a performance guarantee of 0.670 on 3-regular graphs.
Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.
Demonstrating quantum heuristics that outperform strong classical solvers on large-scale optimization remains an open challenge. Here we introduce Regularized Warm-Started QAOA (RWS-QAOA), which initializes qubits by minimizing expected energy with a regularizer that penalizes near-bitstring states, preventing QAOA from stalling. We further propose a protocol that yields fixed, instance-independent parameters, enabling RWS-QAOA to operate as a non-variational algorithm in which the quantum circuit parameters are fixed and only a classical warm starting step is instance-dependent. We evaluate RWS-QAOA on the Max-Cut problem for random regular graphs, where this protocol yields a constant-depth quantum circuit, across three complementary settings. First, on Quantinuum's trapped-ion processor, RWS-QAOA outperforms the classical algorithms with the best provable guarantees for Max-Cut on 3-regular graphs, namely Goemans-Williamson and Halperin-Livnat-Zwick, on 96-node instances. Second, tensor-network simulations on graphs with up to N=10,000 nodes show that depth-6 RWS-QAOA, achieving an average cut fraction of 0.9167, surpasses the best classical heuristics under matched restrictions (no local-search post-processing and no iterative refinement). Third, we remove these restrictions and benchmark against the strongest unrestricted classical heuristics, including an optimized parallel Burer-Monteiro solver that improves upon the MQLib implementation. Even against this stronger baseline, we project that surface-code RWS-QAOA reaches a quantum-classical runtime crossover below 0.2 seconds on 3,000-node graphs with fewer than 1.3 million physical qubits. Our results show that constant-depth quantum circuits combined with a classical warm start have a credible potential to surpass classical solvers on the Max-Cut problem when executed on future quantum computers.
The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.