Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.06698

QASPA-MaxCut on Unweighted Graphs: Edge Encoding and QAOA Restarts

Dmytro Sapozhnyk

Published Nov 4, 2026• 0 citations
arXivHTMLPDF

Abstract

Max-Cut is a common testbed for near-term quantum optimization because it has a simple Ising Hamiltonian, established classical baselines, and a parameterized quantum circuit whose performance depends on the outer classical optimizer. This paper develops QASPA-MaxCut, a shift-phase circuit for Max-Cut that encodes graph edges through controlled $R_y$ rotations of the form $\mathrm{CX}_{ij}R_y(θ_{ij})\mathrm{CX}_{ij}$. We derive the exact two-qubit algebra of the edge block, trace an unweighted four-vertex example, and compare one-layer QASPA-MaxCut with depth-one QAOA by exact state-vector simulation. The protocol uses seed 42, evaluates connected backbone-augmented random graphs with additional-edge probabilities $p_{\mathrm{edge}}\in\{0.1,0.3,0.5,0.7\}$, and adds nineteen custom unweighted topologies. The QASPA-MaxCut score is reported after the algorithm's classical selection stage: the four leading QASPA bit strings are evaluated by the Max-Cut objective, and the best cut is retained. The QAOA score is the expected approximation ratio after local optimization, reported as a best-of-$k$ curve over one to ten restarts. In these small exact simulations, fixed-angle QASPA-MaxCut produces reported group-mean selection ratios between $0.955$ and $1.000$, the topology-level readout is unchanged in the retained finite-shot checks under the rule $\lceil 0.03047\cdot 2^n+1016.2\rceil$, and depth-one QAOA improves with additional classical restarts while remaining lower than the QASPA selection score in the reported mean summaries. This comparison motivates further study of the classical search budget needed to obtain competitive Max-Cut samples at shallow circuit depth.

DOI
10.48550/arxiv.2611.06698

Related papers

SOLVING THE MAX-CUT PROBLEM USING THE QASPA ALGORITHM

Д. О. САПОЖНИК

A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.

Bulletin of National Technical University KhPI Series System Analysis Control and Information Technologies•Dec 29, 2025•1 citation

Design of quantum approximation optimization algorithm for the maximum cut problem

Yun-Jiang Wang, XI Huiming, XIAO Zhuoyan +2 more

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.

Acta Physica Sinica•Jan 1, 2025•1 citation

From Problem-Structured QAOA to Problem-Agnostic Variational MaxCut Solvers: Representation, Redundancy, and Optimization Landscapes

Leonardo Lavagna, Massimo Panella

Variational quantum optimization provides a useful setting for examining how circuit structure, parameterization, and trainability interact in practice. Objectives: Among the most promising variational quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA) depends critically on circuit architecture, but greater circuit complexity does not necessarily lead to easier optimization or better solutions. Using the Maximum Cut (MaxCut) problem on graphs as a controlled setting, we investigate how variational behavior changes as problem-specific QAOA structure is progressively removed, with particular attention to representational capacity, optimization geometry, and finite-budget trainability. Methods: We analytically characterize a graph-agnostic product-state formulation of MaxCut and derive exact equivalences, redundancies, and local-landscape properties. These results motivate a controlled comparison among separable product ansätze, a representative graphagnostic entangling circuit, and graph-structured QAOA at several depths, including a parameter-count-matched control. The numerical benchmark comprises 95 small unweighted graph instances optimized under a common objective-evaluation budget. Results: The product-state formulation preserves the exact discrete MaxCut optimum, while its strict local maxima correspond to classical cuts that are stable under singlevertex flips. Redundant phase parameters increase optimization effort without enlarging the objective-relevant family. Under the prescribed optimization budget, the productstate ansatz attains higher average solution quality than the tested QAOA depths while requiring substantially fewer objective evaluations. The graph-agnostic entangling comparator provides no consistent advantage over the separable baseline, and a simple classical local-search method remains highly competitive. Conclusion: In the regime considered here, objective-relevant parameterization and optimization geometry can be as important as circuit richness.

Applied Mathematics and Statistics•Oct 13, 2026•0 citations

Regularized Warm-Started Quantum Approximate Optimization and Conditions for Surpassing Classical Solvers on the Max-Cut Problem

Zichang He, Anuj Apte, Brandon Augustino +4 more

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.

quant-pharXiv:2603.10191•Mar 12, 2026•8 citations

Exploring graph cuts in quantum approximate optimization algorithm

Nongmeikapam Brajabidhu Singh, Anish Kumar Saha

Abstract Graph cut, a combinatorial optimization, is explored in quantum computing, seeking optimal bi-partitions of a directed or undirected, weighted or unweighted graph. The cut models, such as max-cut and min-cut, are applied in domains including VLSI design, circuit partitioning, data clustering, and network analysis. This paper explores the Ising modeling of max-cut and min-cut in a Laplacian-based QAOA, including benchmarking, spectral analysis, and a detailed analysis of the results. It aims to discover how Ising cut modeling and QAOA perform on a structured graph class, such as a weighted chordal graph. Chordal graphs offer decomposition properties favorable to QUBO and Ising models. Experimental results show that the proposed QAOA framework yields optimal or near-optimal cut values with high and stable approximation ratios across circuit depths. Also, hardware-aware considerations are introduced through superconducting qubit layout design and eigenmode simulations in Qiskit Metal and Ansys EPR HFSS. Further analysis reveals challenges related to convergence and performance in denser topologies. The study gives the modeling and the comprehensive evaluation of QAOA for graph-cuts, including a conceptual hardware-aware analysis.

Physica Scripta•Oct 29, 2025•1 citation

A Max K-Cut Implementation for QAOA in the Measurement Based Quantum Computing Formalism

Sebastiano Corli, Daniele Dragoni, Massimiliano Proietti +3 more

The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•12 citations
Max-Cut is a common testbed for near-term quantum optimization because it has a simple Ising Hamiltonian, established classical baselines, and a parameterized quantum circuit whose performance depends on the outer classical optimizer. This paper develops QASPA-MaxCut, a shift-phase circuit for Max-Cut that encodes graph edges through controlled RyR_yRy​ rotations of the form CXijRy(θij)CXij\mathrm{CX}_{ij}R_y(θ_{ij})\mathrm{CX}_{ij}CXij​Ry​(θij​)CXij​. We derive the exact two-qubit algebra of the edge block, trace an unweighted four-vertex example, and compare one-layer QASPA-MaxCut with depth-one QAOA by exact state-vector simulation. The protocol uses seed 42, evaluates connected backbone-augmented random graphs with additional-edge probabilities pedge∈{0.1,0.3,0.5,0.7}p_{\mathrm{edge}}\in\{0.1,0.3,0.5,0.7\}pedge​∈{0.1,0.3,0.5,0.7}, and adds nineteen custom unweighted topologies. The QASPA-MaxCut score is reported after the algorithm's classical selection stage: the four leading QASPA bit strings are evaluated by the Max-Cut objective, and the best cut is retained. The QAOA score is the expected approximation ratio after local optimization, reported as a best-of-kkk curve over one to ten restarts. In these small exact simulations, fixed-angle QASPA-MaxCut produces reported group-mean selection ratios between 0.9550.9550.955 and 1.0001.0001.000, the topology-level readout is unchanged in the retained finite-shot checks under the rule ⌈0.03047⋅2n+1016.2⌉\lceil 0.03047\cdot 2^n+1016.2\rceil⌈0.03047⋅2n+1016.2⌉, and depth-one QAOA improves with additional classical restarts while remaining lower than the QASPA selection score in the reported mean summaries. This comparison motivates further study of the classical search budget needed to obtain competitive Max-Cut samples at shallow circuit depth.
A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.
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.
Variational quantum optimization provides a useful setting for examining how circuit structure, parameterization, and trainability interact in practice. Objectives: Among the most promising variational quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA) depends critically on circuit architecture, but greater circuit complexity does not necessarily lead to easier optimization or better solutions. Using the Maximum Cut (MaxCut) problem on graphs as a controlled setting, we investigate how variational behavior changes as problem-specific QAOA structure is progressively removed, with particular attention to representational capacity, optimization geometry, and finite-budget trainability. Methods: We analytically characterize a graph-agnostic product-state formulation of MaxCut and derive exact equivalences, redundancies, and local-landscape properties. These results motivate a controlled comparison among separable product ansätze, a representative graphagnostic entangling circuit, and graph-structured QAOA at several depths, including a parameter-count-matched control. The numerical benchmark comprises 95 small unweighted graph instances optimized under a common objective-evaluation budget. Results: The product-state formulation preserves the exact discrete MaxCut optimum, while its strict local maxima correspond to classical cuts that are stable under singlevertex flips. Redundant phase parameters increase optimization effort without enlarging the objective-relevant family. Under the prescribed optimization budget, the productstate ansatz attains higher average solution quality than the tested QAOA depths while requiring substantially fewer objective evaluations. The graph-agnostic entangling comparator provides no consistent advantage over the separable baseline, and a simple classical local-search method remains highly competitive. Conclusion: In the regime considered here, objective-relevant parameterization and optimization geometry can be as important as circuit richness.
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 333-regular graphs, namely Goemans-Williamson and Halperin-Livnat-Zwick, on 969696-node instances. Second, tensor-network simulations on graphs with up to N=10,000N{=}10{,}000N=10,000 nodes show that depth-666 RWS-QAOA, achieving an average cut fraction of 0.91670.91670.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.20.20.2 seconds on 3,0003{,}0003,000-node graphs with fewer than 1.31.31.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.
Abstract Graph cut, a combinatorial optimization, is explored in quantum computing, seeking optimal bi-partitions of a directed or undirected, weighted or unweighted graph. The cut models, such as max-cut and min-cut, are applied in domains including VLSI design, circuit partitioning, data clustering, and network analysis. This paper explores the Ising modeling of max-cut and min-cut in a Laplacian-based QAOA, including benchmarking, spectral analysis, and a detailed analysis of the results. It aims to discover how Ising cut modeling and QAOA perform on a structured graph class, such as a weighted chordal graph. Chordal graphs offer decomposition properties favorable to QUBO and Ising models. Experimental results show that the proposed QAOA framework yields optimal or near-optimal cut values with high and stable approximation ratios across circuit depths. Also, hardware-aware considerations are introduced through superconducting qubit layout design and eigenmode simulations in Qiskit Metal and Ansys EPR HFSS. Further analysis reveals challenges related to convergence and performance in denser topologies. The study gives the modeling and the comprehensive evaluation of QAOA for graph-cuts, including a conceptual hardware-aware analysis.
The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.