QASPA-MaxCut on Unweighted Graphs: Edge Encoding and QAOA Restarts
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 Ry rotations of the form CXijRy(θ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}, 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 ⌈ 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.
Related
- Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation
- Effect of reactive targets on diffusive transport with intermittent restarts
- Restarts of bursts in turbulence in a log-minimal channel
- Qudit encoding in Rydberg-blockaded arrays of atoms
- Quantum simulation of wave optics in weakly inhomogeneous media using block encoding
BibTeX
@misc{sapozhnyk2026qaspamaxcut,
title = {{QASPA-MaxCut on Unweighted Graphs: Edge Encoding and QAOA Restarts}},
author = {Dmytro Sapozhnyk},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06698},
eprint = {2611.06698},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06698},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - QASPA-MaxCut on Unweighted Graphs: Edge Encoding and QAOA Restarts
AU - Dmytro Sapozhnyk
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06698
UR - https://arxiv.org/abs/2611.06698
AB - 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 CX_ijR_y(θ_ij)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_edge∈{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 ⌈ 0.03047· 2^n+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.
ER -