betaFeedback

WorksPhysics and Astronomy

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 RyR_y rotations of the form CXijRy(θij)CXij\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 pedge∈{0.1,0.3,0.5,0.7}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-kk curve over one to ten restarts. In these small exact simulations, fixed-angle QASPA-MaxCut produces reported group-mean selection ratios between 0.9550.955 and 1.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, 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.

Introduction

The Quantum Approximate Optimization Algorithm (QAOA) introduced by Farhi, Goldstone, and Gutmann is one of the canonical variational approaches to combinatorial optimization on gate-model quantum computers [1]. For Max-Cut, the usual construction alternates a diagonal problem unitary generated by the cut Hamiltonian and a transverse-field mixer. The circuit has a direct graph interpretation, but it also exposes a practical bottleneck: the reported performance depends not only on the quantum circuit depth, but also on the classical search over variational angles.

In the noisy intermediate-scale quantum (NISQ) regime, this bottleneck becomes a resource-accounting issue. Increasing depth can improve the variational family in principle, while gate noise, limited connectivity, and repeated circuit evaluations limit what can be run in practice. Recent reviews and performance studies consequently report approximation ratio together with the number of parameter evaluations, restarts, shots, and wall-clock time needed to obtain a good solution [3, 4, 5]. The present study isolates the restart effect by restricting the QASPA construction to unweighted graphs. Weighted Max-Cut would introduce a separate parameter-scaling question, so it is treated here as related work rather than as the operating regime of the proposed circuit [13, 14, 15].

The present work studies QASPA-MaxCut, a Max-Cut circuit based on edge-local controlled RyR_y rotations. A preliminary description of QASPA for Max-Cut appears in [20]. The present paper develops that construction as a mathematical and experimental object suitable for comparison with depth-one QAOA under a controlled amount of classical optimization. The main experimental variable is the number kk of independent QAOA optimizer restarts: one QAOA run means one local optimization from one random initial point, and the reported “best of kk” value is the best expected approximation ratio found after k=1,…,10k = 1, \ldots, 10 such starts.

The paper makes three concrete additions. First, it gives the exact algebra of the CX–RyR_y–CX block and states precisely how it acts on cut and uncut edge configurations. Second, it adds an unweighted four-vertex worked example with a generated graph figure, edge-by-edge transformations, and output probabilities. Third, it provides a reproducible experimental comparison in the form of explicit state-vector routines, table values, and code fragments that connect the reported figures to exact simulations.

The main result is stated under these assumptions. All graphs are unweighted, all reported simulations are exact state-vector simulations on small n=8n = 8 instances except for the four-vertex worked example, and QASPA is run at the fixed angle α=π/4\alpha= \pi/4. Within this scope, the observed fixed-angle QASPA state places large-cut candidates inside the set chosen by its classical selection stage in the tested random and custom graph groups, whereas depth-one QAOA improves gradually as additional independent classical optimizer starts are allowed. The result is a controlled statement about candidate quality and outer-loop optimization budget at shallow depth, not a claim of asymptotic separation or hardware-level superiority.

Related Work

The Max-Cut problem asks for a bipartition of the vertices of an unweighted graph that maximizes the number of crossing edges. The Goemans–Williamson semidefinite programming algorithm remains the standard approximation baseline, with a worst-case expected approximation factor of approximately 0.87856 [2]. Modern exact and heuristic classical solvers are also well developed, which is why quantum Max-Cut experiments need careful comparison against classical baselines and against realistic execution costs [4, 5, 6].

Several QAOA variants aim to improve low-depth performance by changing the mixer, the phase separator, or the ansatz. Multi-angle QAOA adds edge- and qubit-dependent angles and can match deeper standard QAOA on some Max-Cut instances [7]. Free-axis and expressive QAOA variants allow the mixer to use YY components rather than only XX rotations, improving low-depth expressivity at the cost of additional parameters [8, 9]. Constraint-preserving and XYXY mixers provide another route for problems where the feasible subspace should be preserved by construction [10, 11, 12]. These results motivate a central design question for QASPA-MaxCut: can some of the instance structure be moved from a difficult outer-loop search into edge-local circuit structure?

Parameter setting is now a research topic in its own right. Warm-started QAOA uses classical relaxations or approximate solutions to bias the initial quantum state and can improve low-depth behavior [16, 17, 18]. Other studies show that parameters can sometimes transfer across related Max-Cut instances, reducing the number of expensive circuit evaluations [13, 19]. These works support the experimental design used here: instead of reporting only the best QAOA value after an unspecified amount of tuning, we expose how solution quality changes as the number of classical optimization starts increases.

Mathematical Formulation

Let G=(V,E)G = (V,E) be an undirected unweighted graph with n=∣V∣n = |V|. A bit string z∈{0,1}nz \in\{0,1\}^{n} defines a cut, and the cut value is

CG(z)=∑(i,j)∈E(zi⊕zj).(1)C_G(z) = \sum_{(i,j)\in E} (z_i \mathbin{\oplus} z_j). \tag*{(1)}

Equivalently, with spin variables si=(−1)zis_i = (-1)^{z_i},

CG(z)=12∑(i,j)∈E(1−sisj).(2)C_G(z) = \frac{1}{2} \sum_{(i,j)\in E} (1 - s_i s_j). \tag*{(2)}

The usual Max-Cut cost Hamiltonian is therefore

HC=12∑(i,j)∈E(I−ZiZj),(3)H_C = \frac{1}{2} \sum_{(i,j)\in E} (I - Z_i Z_j), \tag*{(3)}

whose eigenvalue on computational basis state ∣z⟩|z\rangle is CG(z)C_G(z).

Depth-one QAOA prepares

∣ψQAOA(γ,β)⟩=UB(β)UC(γ)∣+⟩⊗n,(4)|\psi_{\mathrm{QAOA}}(\gamma,\beta)\rangle= U_B(\beta)U_C(\gamma)|+\rangle^{\otimes n}, \tag*{(4)}

where

UC(γ)=e−iγHC,UB(β)=e−iβ∑iXi=∏i=0n−1Rx(i)(2β).(5)\begin{aligned} U_C(\gamma) &= e^{-i\gamma H_C},\\ U_B(\beta) &= e^{-i\beta\sum_i X_i}\\ &= \prod_{i=0}^{n-1} R_x^{(i)}(2\beta). \tag*{(5)} \end{aligned}

The classical optimizer searches over (γ,β)(\gamma,\beta) to maximize ⟨HC⟩\langle H_C\rangle.

QASPA-MaxCut keeps the initial Hadamard layer but replaces the global XX mixer with edge-local YY-axis rotations. For each unweighted edge (i,j)(i,j) we set

θij=α,(6)\theta_{ij}=\alpha, \tag*{(6)}

where α\alpha is a global edge angle. No edge weights are introduced in the current QASPA circuit, so the graph contributes through its unweighted edge set and through the order in which the corresponding blocks are applied. The QASPA edge block is

Uij(Y)(θij)=CX⁡i,jRy(j)(θij)CX⁡i,j.(7)U_{ij}^{(Y)}(\theta_{ij})=\operatorname{CX}_{i,j}R_y^{(j)}(\theta_{ij})\operatorname{CX}_{i,j}. \tag*{(7)}

For one layer and a fixed edge ordering, the circuit is

∣ψQASPA(α)⟩=∏(i,j)∈E→Uij(Y)(α)∣+⟩⊗n.(8)\lvert\psi_{\mathrm{QASPA}}(\alpha)\rangle= \overrightarrow{\prod_{(i,j)\in E}} U_{ij}^{(Y)}(\alpha)\lvert+\rangle^{\otimes n}. \tag*{(8)}

The arrow reminds us that these edge blocks do not generally commute when edges share a vertex.

The algebra of the edge block is explicit because Ry(θ)=exp⁡(−iθY/2)R_y(\theta)=\exp(-i\theta Y/2) and XRy(θ)X=Ry(−θ)X R_y(\theta)X=R_y(-\theta) imply

Uij(Y)(θ)=∣0⟩⟨0∣i⊗Ry(j)(θ)+∣1⟩⟨1∣i⊗Ry(j)(−θ)=exp⁡(−iθ2ZiYj).(9)\begin{aligned} U_{ij}^{(Y)}(\theta) &=\lvert0\rangle\langle0\rvert_i\otimes R_y^{(j)}(\theta) +\lvert1\rangle\langle1\rvert_i\otimes R_y^{(j)}(-\theta)\\ &=\exp\left(-\frac{i\theta}{2}Z_iY_j\right). \tag*{(9)} \end{aligned}

Thus the control qubit selects the sign of the YY rotation on the target. Writing c=cos⁡(θ/2)c=\cos(\theta/2) and s=sin⁡(θ/2)s=\sin(\theta/2), the computational-basis action is

∣00⟩↦c∣00⟩+s∣01⟩,∣01⟩↦−s∣00⟩+c∣01⟩,\lvert00\rangle\mapsto c\lvert00\rangle+s\lvert01\rangle,\quad \lvert01\rangle\mapsto-s\lvert00\rangle+c\lvert01\rangle,
∣10⟩↦c∣10⟩−s∣11⟩,∣11⟩↦s∣10⟩+c∣11⟩.(10)\lvert10\rangle\mapsto c\lvert10\rangle-s\lvert11\rangle,\quad \lvert11\rangle\mapsto s\lvert10\rangle+c\lvert11\rangle. \tag*{(10)}

Each control-conditioned two-dimensional subspace contains one cut and one uncut configuration for the edge. The block therefore redistributes amplitude between cut and uncut states, rather than only applying a diagonal phase. Up to a target-qubit basis rotation that maps YjY_j to

Input unweighted graph G=(V,E)G=(V,E) and global angle α\alpha

Prepare ∣0⟩⊗n\lvert0\rangle^{\otimes n} and apply HH to every qubit

For each edge (i,j)(i,j), apply CX⁡i,jRy(j)(α)CX⁡i,j\operatorname{CX}_{i,j}R_y^{(j)}(\alpha)\operatorname{CX}_{i,j}

Compute or sample computational-basis output probabilities

Apply QASPA classical selection and report the best cut

ZjZ_j, the generator ZiYjZ_iY_j is equivalent to a ZiZjZ_iZ_j edge interaction.

To connect the algebraic block with the actual computation, Figure 1 presents the one-layer QASPA-MaxCut construction as a pipeline. The graph first determines the edge-block schedule, the scheduled blocks define the state-vector evolution, and the resulting probabilities are then passed to the classical selection stage.

Figure 1. Block scheme of the one-layer QASPA-MaxCut procedure for unweighted graphs.

Listing 1 uses the same order in code form, so the transition from the diagram to the implementation preserves the notation used in Eqs. (7)–(10).

Listing 1: Implementation skeleton for the QASPA edge layer.

state = zero_state(2**n)
state[0] = 1
for q in vertices:
    apply_h(state, q)

for (i, j) in edges:
    apply_cx(state, i, j)
    apply_ry(state, j, alpha)
    apply_cx(state, i, j)

probabilities = abs(state)**2
expected_cut = sum(probabilities[z] * cut_value(z, edges) for z in states)

Circuit Construction Details

The mathematical definition above is compact, but an implementation needs a fixed interpretation of qubit order, edge order, and output bit strings. This paper uses the q0-first convention throughout: the leftmost character of a reported bit string is the value of qubit 0. The convention is not a mathematical restriction, but stating it avoids a common source of mistakes when comparing simulator output, tables, and graph partitions.

Figure 2 expands the single product in Equation (8) into an algorithmic circuit schedule rather than a hardware transpilation. Each graph edge is translated into one local block, and the displayed order is part of the experimental definition: if two adjacent edge blocks share a qubit, changing their order can change the final state. The experiment therefore fixes a deterministic edge order before any probability or expectation value is computed.

Figure 2. Circuit schedule for the four-vertex example, where each edge block is a controlled sign-selecting RyR_y operation.

The edge block itself is shown in Figure 3. The first CNOT maps the parity information of the pair into the target qubit, the RyR_y gate rotates that target, and the final CNOT restores the computational labeling. This is the operational reason why the block is more than a diagonal phase: it modifies amplitudes in a two-dimensional subspace attached to an edge.

Figure 3. Gate-level structure of one QASPA edge block used to encode a graph edge in the circuit.

Figure 4 gives the same operation as an amplitude-flow picture. For a fixed value of the control qubit, the target qubit is rotated inside a pair of basis states, where one state cuts the edge and the other does not. The block therefore changes how much probability is assigned to cut and uncut configurations before the final measurement.

Figure 4. Amplitude redistribution induced by one edge block, with c=cos⁡(α/2)c = \cos(\alpha/2) and s=sin⁡(α/2)s = \sin(\alpha/2) defining the local rotation coefficients.

The bit-string convention introduced above becomes concrete in Listing 2. The same cut-value routine is used for the test graph, the exact optimum, and the expectation ratio, which keeps the mathematical definition and the numerical reporting aligned.

Listing 2: Cut-value routine for q0-first bit strings.

def bit_at(mask, q):
    return (mask >> q) & 1

def cut_value(mask, edges):
    total = 0
    for i, j in edges:
        if bit_at(mask, i) != bit_at(mask, j):
            total += 1
    return total

def bitstring(mask, n):
    return "".join(str(bit_at(mask, q)) for q in
                   range(n))

With the cut convention fixed, the expectation value can be evaluated by direct enumeration of the computational basis. This exact state-vector calculation is practical for the small graphs used in this article, and it removes sampling noise from the methodological comparison. Listing 3 implements the same quantity later normalized in Equation (14).

Listing 3: Exact expected cut from a state vector.

def expected_cut(state, edges):
    probabilities = abs(state)**2
    value = 0.0
    for mask, probability in enumerate(
        probabilities):
        value += probability * cut_value(mask,
        edges)
    return value

Worked Test Graph

Figure 5 shows the unweighted four-vertex graph used as a mathematical example. The optimum cut value is CG∗=4C_G^* = 4, obtained by the q0-first bit strings 0110 and 1001. The colors in the figure show one of these optimal partitions.

Figure 5. Unweighted test graph, where the dark edges cross the optimal partition 0110 and the light edge does not.

For this graph, the initial state and the first QASPA layer become explicit:

∣ψ0⟩=∣0000⟩,|\psi_0\rangle= |0000\rangle,
∣ψH⟩=H⊗4∣ψ0⟩=14∑z∈{0,1}4∣z⟩,(11)|\psi_H\rangle= H^{\otimes4}|\psi_0\rangle= \frac{1}{4}\sum_{z\in\{0,1\}^4}|z\rangle, \tag*{(11)}
∣ψQASPA⟩=U23(Y)(α)U13(Y)(α)U12(Y)(α)U02(Y)(α)U01(Y)(α)∣ψH⟩.(12)|\psi_{\mathrm{QASPA}}\rangle= U_{23}^{(Y)}(\alpha)U_{13}^{(Y)}(\alpha)U_{12}^{(Y)}(\alpha)U_{02}^{(Y)}(\alpha)U_{01}^{(Y)}(\alpha)|\psi_H\rangle. \tag*{(12)}

The fixed-angle condition α=π/4\alpha= \pi/4 assigns the same rotation scale to each unweighted edge, as recorded in Table 1.

EdgeSymbolic angle θij\theta_{ij}Numeric angle
(0, 1)α\alpha0.7854
(0, 2)α\alpha0.7854
(1, 2)α\alpha0.7854
(1, 3)α\alpha0.7854
(2, 3)α\alpha0.7854

Table 1. Edge-specific QASPA angles for the test graph at α=π/4\alpha= \pi/4.

At this fixed global scale, the five edge transformations are

U01(Y)(α)=exp⁡(−iα2Z0Y1),U02(Y)(α)=exp⁡(−iα2Z0Y2),U12(Y)(α)=exp⁡(−iα2Z1Y2),U13(Y)(α)=exp⁡(−iα2Z1Y3),U23(Y)(α)=exp⁡(−iα2Z2Y3),α=π4.(13)\begin{aligned} U_{01}^{(Y)}(\alpha) &= \exp\left(-\frac{i\alpha}{2}Z_0Y_1\right),\\ U_{02}^{(Y)}(\alpha) &= \exp\left(-\frac{i\alpha}{2}Z_0Y_2\right),\\ U_{12}^{(Y)}(\alpha) &= \exp\left(-\frac{i\alpha}{2}Z_1Y_2\right),\\ U_{13}^{(Y)}(\alpha) &= \exp\left(-\frac{i\alpha}{2}Z_1Y_3\right),\\ U_{23}^{(Y)}(\alpha) &= \exp\left(-\frac{i\alpha}{2}Z_2Y_3\right),\qquad\alpha= \frac{\pi}{4}. \tag*{(13)} \end{aligned}

Equations (12) and (13) give the complete symbolic circuit for the example.

Table 2 shows the largest output probabilities after the full QASPA layer at α=π/4\alpha= \pi/4. For this unweighted example, the two most probable strings are exactly the two optimum cuts. This provides a limited sanity check for the construction: in this instance, the edge-encoded RyR_y layer moves probability mass toward large cut values, even though a fixed angle is not a general guarantee of exact optimization.

RankBit stringProbabilityCut valueOptimal?
101100.21344.00yes
210010.21344.00yes
301000.10673.00no
410100.10673.00no
501010.10673.00no
610110.10673.00no
711000.03663.00no
800100.03663.00no

Table 2. Top QASPA output states for the test graph at α=π/4\alpha= \pi/4, with q0-first bit strings matching the simulator convention.

The probability chart in Figure 6 complements the exact values in Table 2. The table identifies the two optimal strings as the most probable outputs, while the figure shows that the fixed-angle layer still leaves visible probability mass on nearby nonoptimal strings. This observation sets up the benchmark interpretation: QASPA is treated as a candidate generator, and the reported score asks whether the retained high-probability candidates contain a large cut.

Figure 6. Largest output probabilities for the unweighted test graph under one QASPA layer with α=π/4\alpha= \pi/4, where green bars mark optimal cuts.

Because the four-vertex graph is small, the product in Equation (12) can be unfolded into an edge-by-edge trace. Table 3 gives the simulator order explicitly, connecting the graph, the circuit schedule, and the implementation convention before the paper moves to the numerical protocol.

StepEdgeOperatorPurpose
1(0, 1)U01(Y)(α)U_{01}^{(Y)}(\alpha)First relation
2(0, 2)U02(Y)(α)U_{02}^{(Y)}(\alpha)Second relation at 0
3(1, 2)U12(Y)(α)U_{12}^{(Y)}(\alpha)Middle relation
4(1, 3)U13(Y)(α)U_{13}^{(Y)}(\alpha)Lower-right relation
5(2, 3)U23(Y)(α)U_{23}^{(Y)}(\alpha)Lower-left relation

Table 3. Trace of the QASPA edge schedule for the four-vertex graph.

This deterministic trace is part of the algorithmic specification, since edge blocks acting on overlapping qubits are not treated as interchangeable algebraic factors in the reported experiments.

Figure 7 extends the edge-level trace to the final QASPA selection score, and Listing 4 ends the worked example by writing the four-vertex graph in the same form used by the later experiments.

Figure 7. Interpretation chain from a graph edge to its contribution in the QASPA classical selection score.

Manual construction of the four-vertex example

Figure 4 (PDF p. 6). Manual construction of the four-vertex example.

edges = [
    (0, 1),
    (0, 2),
    (1, 2),
    (1, 3),
    (2, 3),
]

alpha = pi / 4
state = qaspa_state(edges, n=4, alpha=alpha)
top_states = sort_by_probability(state)[:8]
optimum, optimum_masks = exact_optimum(edges, n=4)

Together, Figure 2, Table 3, Figure 7, and Listing 4 connect the visual circuit placement with the algebraic reason for each block and the final computational routine. The QASPA circuit first redistributes amplitudes through the ordered edge blocks, the resulting probability distribution is sampled or sorted, and only then are the four leading bit strings evaluated by the Max-Cut objective. This distinction matters because the QASPA value reported in the tables is the score after the algorithm’s classical selection stage, while the QAOA value is an expected approximation ratio optimized over restart budgets.

As a result, the example is not a hand-calculated special case detached from the experimental protocol. The same routines that evaluate the random graphs also evaluate the small graph in Figure 5, allowing the paper to move from a transparent trace to the larger benchmark without changing the computational definitions.

Experimental Protocol and Results

The worked example fixes the conventions; the experiment now asks how fixed-angle QASPA-MaxCut compares with depth-one QAOA when the classical optimization budget is made visible. The QASPA condition uses α=π/4\alpha= \pi/4 without an additional outer-loop angle search, while the QAOA condition uses a local Nelder–Mead optimizer. In the QAOA condition, one optimization run means one random initialization of (γ,β)(\gamma, \beta) followed by local optimization, and for each graph we record the best expected approximation ratio after k=1,…,10k = 1,\ldots,10 independent starts.

All simulations use exact state vectors and exact Max-Cut optima, and every graph in the experiment is unweighted. The random graphs are connected backbone-augmented instances: a path backbone is inserted first, and additional nonbackbone edges are then sampled independently. Each additional-edge probability group uses n=8n = 8 vertices and 12 instances, 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\}. A separate custom group contains nineteen hand-specified connected topologies on the same number of vertices. The local QAOA optimizer uses the exact expected cut

ρexp=Ez∼∣ψ∣2[CG(z)]CG∗.(14)\rho_{\mathrm{exp}} = \frac{\mathbb{E}_{z\sim|\psi|^2}\left[C_G(z)\right]}{C_G^*}. \tag*{(14)}

The reported QASPA score is the output of the method’s classical selection stage. Let SQASPA(ψ)S_{\mathrm{QASPA}}(\psi) be the four computational-basis bit strings selected from the largest output probabilities under the fixed-angle QASPA state ψ\psi. The QASPA selection ratio is

ρsel(ψ)=max⁡z∈SQASPA(ψ)CG(z)CG∗.(15)\rho_{\mathrm{sel}}(\psi) = \frac{\max_{z\in S_{\mathrm{QASPA}}(\psi)} C_G(z)}{C_G^*}. \tag*{(15)}

QASPA is therefore evaluated as a candidate-generating algorithm whose classical selection stage keeps the best cut among the selected candidates. QAOA is evaluated by the expected approximation ratio in Equation (14), because the comparison is designed to show how much the variational baseline improves with repeated classical optimization. The result section keeps this distinction explicit: QASPA asks whether a small retained candidate set already contains a large cut, while QAOA asks how the optimized expectation improves as more classical starts are spent on the same graph group. To make the metric difference auditable, Table 6 also reports the fixed-angle QASPA expected ratio alongside the prescribed QASPA selection score.

Graph groupQASPA selection ρsel\rho_{\mathrm{sel}}QASPA expected ρexp\rho_{\mathrm{exp}}QAOA best-of-10
Backbone p=0.1p = 0.10.9900.8580.786
Backbone p=0.3p = 0.30.9550.8520.806
Backbone p=0.5p = 0.50.9870.8580.826
Backbone p=0.7p = 0.70.9880.8800.854
Custom topologies1.0000.8840.798

Table 6. Metric-control comparison at the ten-restart QAOA budget. The QASPA selection column is ρsel\rho_{\mathrm{sel}} from Equation (15); the two expected-ratio columns use Equation (14).

To connect this exact readout rule with a finite-sampling setting, the topology-specific QASPA test also uses the shot budget

Nshots(n)=⌈0.03047⋅2n+1016.2⌉.(16)N_{\mathrm{shots}}(n) = \left\lceil0.03047 \cdot2^n + 1016.2 \right\rceil. \tag*{(16)}

For the n=8n = 8 graphs in this manuscript, Equation (16) gives Nshots=1025N_{\mathrm{shots}} = 1025. The sampled readout test draws that many outcomes from the QASPA output distribution, selects the four most frequently observed bit strings, and reports the best Max-Cut value after this classical selection stage. This readout is repeated 50 times for each custom topology with a deterministic sampling stream derived from seed 42. The shot budget is therefore adaptive in the number of qubits rather than a single constant budget reused across all graph sizes, and the reported sampled values include the variability of the finite readout. Listing 5 records the rule in the same pseudocode style as the algorithmic fragments below.

Listing 5: Adaptive QASPA shot-count rule used for finite readout.

def qaspa_shot_count(n):
    return ceil(0.03047 * 2**n + 1016.2)

Table 4 collects the fixed choices behind the experiment and makes the restart budget visible. The comparison is between a fixed QASPA edge angle and a QAOA optimizer that receives a controlled number of independent starts, rather than between arbitrary tuning effort and a fixed circuit.

ItemValue used in the manuscript
Graph typeConnected unweighted random backbones; custom topologies
Graph sizen=8n = 8 vertices
Additional-edge probabilitiespedge∈{0.1,0.3,0.5,0.7}p_{\mathrm{edge}} \in\{0.1, 0.3, 0.5, 0.7\}
Instances per additional-edge probability12
Custom topology count19
QASPA fixed angleα=π/4\alpha= \pi/4
QAOA depthOne alternating layer
QAOA restart budgetsk=1,…,10k = 1,\ldots,10 independent starts
OptimizerNelder–Mead, maximum iteration count 80
Reported scoresQASPA selection ratio; QAOA best expected ratio
QASPA shot budgetNshots=⌈0.03047⋅2n+1016.2⌉=1025N_{\mathrm{shots}} = \lceil0.03047 \cdot2^n + 1016.2 \rceil= 1025 for n=8n = 8
Random seed42

Table 4. Protocol controls used to make the numerical comparison reproducible and to expose the classical restart budget.

Table 5 reports the behavior of the local QAOA optimizer under these controls. The returned state from every local start is evaluated, including starts where the optimizer terminates at the iteration limit rather than satisfying its convergence criterion. This policy avoids silently discarding poor local starts, while the success column records how often the local search terminates normally.

Graph groupStartsSuccessfulSuccess rateMean nfevn_{\mathrm{fev}}Max nfevn_{\mathrm{fev}}
Backbone p=0.1p = 0.11201201.000115.1155
Backbone p=0.3p = 0.31201190.992112.3154
Backbone p=0.5p = 0.51201190.992114.0152
Backbone p=0.7p = 0.71201170.975117.8159
Custom topologies1901870.984115.2153

Table 5. Diagnostics for the depth-one QAOA local optimizer. Each local start uses Nelder–Mead with maximum iteration count 80; nfevn_{\mathrm{fev}} denotes objective-function evaluations.

After these controls are fixed, Figure 8 summarizes the same protocol as a block scheme. The diagram prepares the interpretation of Figure 9: the QAOA curve is a best-so-far curve over the restart budget, while the QASPA reference line is computed once per graph under the fixed-angle condition.

Block scheme of the experimental protocol

Figure 8. Block scheme of the experimental protocol, with numerical aggregates reported directly in the manuscript tables.

Figure 9. Mean approximation ratio for depth-one QAOA as a function of the number of independent classical optimizer restarts. Colors distinguish graph groups; solid curves show the QAOA best-of-kk expected ratio, and dashed horizontal lines show the corresponding fixed-angle QASPA classical selection score. Light shaded regions show one sample standard deviation over the graph instances in each group.

At the implementation level, Listing 6 gives the compact wrapper behind the restart curve. QASPA is evaluated once at the fixed angle, whereas QAOA is updated as a best-so-far value over repeated local optimizer starts.

The restart profile in Figure 9 is the main visual summary of this protocol. It uses seed 42, and the aggregate values needed to read the curves are printed directly in the manuscript tables.

def qaspa_selection_ratio(state, graph): probabilities = abs(state)**2 selected = argsort_descending(probabilities) [:4] best_cut = max(cut_value(mask, graph.edges) for mask in selected) return best_cut / exact_optimum(graph)

for graph in random_graphs + custom_graphs: qaspa_fixed = qaspa_selection_ratio( qaspa_state(graph, alpha=pi/4), graph)

best_qaoa = -infinity for k in range(1, 11): gamma, beta = random_initial_angles() state = local_optimize_qaoa(graph, gamma, beta) value = expected_ratio(state, graph) best_qaoa = max(best_qaoa, value) report_best_of_k(graph, k, best_qaoa, qaspa_fixed)

Tables 6–9 give the numerical values behind Figure 9. The expanded experiment shows a similar restart-budget pattern across low-, medium-, and high-additional-edge-probability groups and across custom topologies. For example, in the reported means QAOA improves from 0.712 to 0.786 on the pedge=0.1p_{\mathrm{edge}} = 0.1 group and from 0.771 to 0.798 on the custom topology group, while the corresponding fixed QASPA selection values are 0.990 and 1.000.

Table 6 adds a metric-control check at the largest QAOA restart budget. The QASPA selection column is ρsel\rho_{\mathrm{sel}}, while the QASPA expected column applies Equation (14) to the full fixed-angle QASPA distribution. This separates the comparison based on the prescribed QASPA readout from the comparison based on an expectation-value metric. The control reduces the risk that the QASPA selection scores are read as an expectation-value claim: in this small experiment the fixed-angle QASPA expectation is above the ten-restart QAOA expectation in the reported group means, but the margins are narrower than in the QASPA selection column. The later tables therefore keep the prescribed QASPA selection score as the primary value while leaving the expectation comparison visible as a calibration point.

The sparse graph groups in Table 7 provide the most direct view of restart sensitivity when few nonbackbone edges are present. The largest gain comes from the first few QAOA restarts, after which the expected ratio changes little and is lower than the fixed QASPA selection reference in both low-probability group means.

Graph groupRestarts kkQAOA meanQAOA std.QASPA fixed
Backbone p=0.1p = 0.110.7120.1170.990
Backbone p=0.1p = 0.120.7360.1100.990
Backbone p=0.1p = 0.130.7520.1000.990
Backbone p=0.1p = 0.140.7860.0500.990
Backbone p=0.1p = 0.150.7860.0500.990
Backbone p=0.1p = 0.160.7860.0500.990
Backbone p=0.1p = 0.170.7860.0500.990
Backbone p=0.1p = 0.180.7860.0500.990
Backbone p=0.1p = 0.190.7860.0500.990
Backbone p=0.1p = 0.1100.7860.0500.990
Backbone p=0.3p = 0.310.7200.0940.955
Backbone p=0.3p = 0.320.7540.0860.955
Backbone p=0.3p = 0.330.7690.0700.955
Backbone p=0.3p = 0.340.7810.0670.955
Backbone p=0.3p = 0.350.8060.0380.955
Backbone p=0.3p = 0.360.8060.0380.955
Backbone p=0.3p = 0.370.8060.0380.955
Backbone p=0.3p = 0.380.8060.0380.955
Backbone p=0.3p = 0.390.8060.0380.955
Backbone p=0.3p = 0.3100.8060.0380.955

Table 7. Experimental summary for sparse backbone-augmented graph groups. QAOA values are means over graph instances of the best expected ratio after kk optimizer restarts; QASPA values use the classical selection rule.

gain comes from the first few QAOA restarts, after which the expected ratio changes little and is lower than the fixed QASPA selection reference in both low-probability group means. Table 8 extends the same reading to the medium- and high-probability random groups, where more nonbackbone edges are available but the restart budget is kept unchanged. Reading the sparse and denser random groups together separates two effects that can otherwise be confused in a small Max-Cut study. A larger value of pedgep_{\mathrm{edge}} changes the number of cost terms, whereas the restart count changes only the amount of classical search given to QAOA after the depth-one circuit has been fixed. The resulting plateau is therefore a restart-budget diagnostic: it indicates that the chosen local optimizer and initialization scheme stopped improving within ten starts, not that the instance family or QAOA ansatz has been exhausted. This keeps the interpretation local before the analysis moves from randomly augmented backbones to hand-specified topologies.

Graph groupRestarts kkQAOA meanQAOA std.QASPA fixed
Backbone p=0.5p = 0.510.7780.0760.987
Backbone p=0.5p = 0.520.8000.0500.987
Backbone p=0.5p = 0.530.8090.0530.987
Backbone p=0.5p = 0.540.8130.0540.987
Backbone p=0.5p = 0.550.8130.0540.987
Backbone p=0.5p = 0.560.8130.0540.987
Backbone p=0.5p = 0.570.8190.0600.987
Backbone p=0.5p = 0.580.8190.0600.987
Backbone p=0.5p = 0.590.8190.0600.987
Backbone p=0.5p = 0.5100.8260.0550.987
Backbone p=0.7p = 0.710.8170.0670.988
Backbone p=0.7p = 0.720.8460.0390.988
Backbone p=0.7p = 0.730.8540.0390.988
Backbone p=0.7p = 0.740.8540.0390.988
Backbone p=0.7p = 0.750.8540.0390.988
Backbone p=0.7p = 0.760.8540.0390.988
Backbone p=0.7p = 0.770.8540.0390.988
Backbone p=0.7p = 0.780.8540.0390.988
Backbone p=0.7p = 0.790.8540.0390.988
Backbone p=0.7p = 0.7100.8540.0390.988

Table 8. Experimental summary for medium- and high-probability backbone-augmented graph groups.

Table 8 shows that increasing the additional-edge probability does not qualitatively change this pattern in the reported means. QAOA expected ratios improve with restarts and start closer to the fixed QASPA selection line at pedge=0.7p_{\mathrm{edge}} = 0.7, but the fixed QASPA selection score remains higher within the ten-start budget used here.

The aggregate custom-topology row in Table 9 does not show how individual graph shapes behave under QASPA readout. Table 10 therefore separates the nineteen hand-specified topologies and compares the exact QASPA selection score with the finite-shot score obtained from Equation (16). This is not a new QAOA comparison; it is a readout check for the QASPA classical selection stage across named graph shapes. Reporting each topology also prevents the aggregate value from hiding failures on individual shapes and prepares the later edge-order study, where noncommuting blocks are tied to concrete graph structures rather than to an anonymous average.

Graph groupRestarts kkQAOA meanQAOA std.QASPA fixed
Custom topologies10.7710.1081.000
Custom topologies20.7940.0721.000
Custom topologies30.7980.0751.000
Custom topologies40.7980.0751.000
Custom topologies50.7980.0751.000
Custom topologies60.7980.0751.000
Custom topologies70.7980.0751.000
Custom topologies80.7980.0751.000
Custom topologies90.7980.0751.000
Custom topologies100.7980.0751.000

Table 9. Experimental summary for the nineteen hand-specified custom topologies.

TopologyEdgesOptimumShotsExact sel.Sampled meanSampled std.Opt. rate
Path7710251.0001.0000.0001.00
Cycle8810251.0001.0000.0001.00
Star7710251.0001.0000.0001.00
Wheel141010251.0001.0000.0001.00
Ladder 2x4101010251.0001.0000.0001.00
Cube121210251.0001.0000.0001.00
Prism-tail11910251.0001.0000.0001.00
Lollipop10810251.0001.0000.0001.00
Barbell9710251.0001.0000.0001.00
House-tail9810251.0001.0000.0001.00
Bowtie-tail9710251.0001.0000.0001.00
Sparse bipartite101010251.0001.0000.0001.00
Chordal cycle12810251.0001.0000.0001.00
Dense core with leaves13910251.0001.0000.0001.00
Two squares101010251.0001.0000.0001.00
Fan131010251.0001.0000.0001.00
Zigzag with chords131010251.0001.0000.0001.00
Bridge mesh101010251.0001.0000.0001.00
Ring with hubs131010251.0001.0000.0001.00

Table 10. Topology-level QASPA readout sanity check. The exact column uses the four largest state-vector probabilities. The sampled columns repeat Nshots=1025N_{\mathrm{shots}} = 1025 draws 50 times and then apply the same QASPA classical selection rule to the observed counts.

The topology-level check remains local to the retained custom set, rather than serving as a broad sampling-robustness claim. In this restricted set, repeated finite readout matches the exact QASPA selection result for the nineteen graph shapes: each sampled mean is 1.000 with zero observed standard deviation over the 50 repeated readouts. The result supports the stability of the prescribed classical selection rule for these small retained topologies, while leaving larger or more degenerate graph families to future finite-shot studies.

Because QASPA edge blocks on adjacent edges need not commute, the edge order is part of the algorithmic specification. Table 11 checks how much the QASPA selection score changes when the canonical edge order is replaced by the reverse order or by random permutations. For each graph, the random-order column uses 20 sampled edge permutations; the table reports group means and the range observed across those random-order trials. The result is not order-invariant, but the shuffled means stay close to the canonical fixed-order values in these small tests.

Graph groupCanonicalReversedRandom meanRandom std.Random range
Backbone p=0.1p = 0.10.9901.0000.9990.0110.875–1.000
Backbone p=0.3p = 0.30.9550.9720.9670.0520.800–1.000
Backbone p=0.5p = 0.50.9870.9580.9700.0510.714–1.000
Backbone p=0.7p = 0.70.9880.8860.9590.0550.667–1.000
Custom topologies1.0000.9780.9910.0300.800–1.000

Table 11. Sensitivity of the QASPA selection ratio to edge ordering. Random-order statistics use 20 edge permutations per graph.

Taken together, Figure 9 and Table 7–Table 11 support two modest claims about optimization budget and shallow-depth baselines. First, QAOA’s reported quality is sensitive to the classical optimization budget, since one optimizer start is not the same experiment as ten starts. Second, the QASPA edge-encoded circuit places large-cut candidates inside the retained candidate set without an outer-loop angle search in these tests. The comparison is not a hardware or scaling claim, but it provides a controlled indication that QASPA-like edge-encoded mixing is worth testing as a way to change how much outer-loop tuning is needed.

Discussion and Limitations

The mathematical difference between the two approaches is where graph structure enters the circuit. In depth-one QAOA, the unweighted edge set defines a diagonal phase separator and the global XX mixer then converts phase differences into amplitude changes. In QASPA-MaxCut, each edge immediately applies a conditional YYaxis rotation, so part of the edge structure is embedded into the mixing step itself. This resembles the broader trend in multi-angle, free-axis, and custom-mixer QAOA variants: shallow circuits often use more problem structure inside the ansatz when they are designed to reduce the burden on depth or repeated classical tuning.

The comparison also exposes a trade-off that matters for later hardware-facing work. At the usual gate-decomposition level, both one-layer QASPA and depth-one QAOA can require edge-local entangling structure: QASPA uses a CX–RyR_y–CX block per ordered edge, while QAOA cost unitaries are commonly compiled through edge-local ZZ rotations. The difference emphasized here is not a universal two-qubit-gate advantage, but the placement of graph structure inside a noncommuting ordered QASPA mixing layer instead of a diagonal QAOA phase layer followed by a global mixer. This affects scheduling, edge-order

sensitivity, and the amount of classical parameter search associated with obtaining large-cut samples.

The QASPA selection score is intentionally reported because it is the classical optimization stage of the algorithm studied here, not a second search routine applied after the state has been prepared. The classical work after measurement is the evaluation of four candidate bit strings by the original Max-Cut objective, which is also the verification step needed to report any sampled cut value. This choice makes QASPA a candidate-generation method rather than an expectation-value optimizer. For that reason the paper also reports the QASPA expectation value as a metric-control quantity and avoids interpreting the selection-score comparison as a variational-optimization dominance claim.

The limitations are important for reading the result at the right scale. The experiments use only n=8n = 8 exact state-vector simulations, so all results are small-instance evidence. The QAOA baseline is depth-one and uses a standard local optimizer with a fixed iteration limit; the diagnostic table records starts that terminate at that limit rather than hiding them. Deeper QAOA, warm-started QAOA, transferred parameters, CVaR objectives, or other optimizer choices could change the comparison. The QASPA edge order is also part of the algorithmic definition. The sensitivity check shows that random edge orders give nearby group means in the tested cases, but it does not prove order robustness for larger graphs. The current QASPA construction is restricted to unweighted graphs, since a weighted Max-Cut variant would need a separate derivation rather than the direct substitution θij=αwij\theta_{ij} = \alpha w_{ij}. The topology readout test samples repeatedly from an ideal state-vector distribution, so a next version should add device-aware transpilation and noise models. It should also test larger unweighted graph families where exact opt-

Implementation Details and Reproducibility

This section expands the implementation path behind the compact listings used throughout the manuscript. Its role is not to introduce a second algorithm, but to make the computational workflow readable as a sequence of small, checkable operations. The same convention is used throughout: graphs are unweighted, bit strings are q0-first, and the expected cut is computed exactly from the state-vector probabilities when optimizing QAOA, while the main QASPA score uses exact probabilities inside its classical selection stage. The topology readout test then repeats that QASPA selection step on sampled counts.

Figure 10 gives the section-level workflow before the individual code fragments are introduced. Meanwhile are replaced by independently verified classical baselines. It connects graph generation, exact state construction, QAOA restarts, sampled QASPA readout, and manuscript tables inside one reproducibility path.

Figure 10. Reproducibility workflow used for the figures and tables in the manuscript.

Listing 7 shows the graph construction rule in algorithmic form. A path backbone is inserted first so that every generated instance is connected, and additional edges are then added according to pedgep_{\mathrm{edge}}. This makes the random graph family simple enough to describe in the paper while avoiding isolated vertices that would not affect the Max-Cut objective.

Listing 7: Connected unweighted graph generation.

def connected_random_graph(n, p_edge, seed):
    rng = random_generator(seed)
    edges = [(i, i + 1) for i in range(n - 1)]
    existing = set(edges)

    for i in range(n):
        for j in range(i + 1, n):
            if (i, j) not in existing and rng.
            random() < p_edge:
                edges.append((i, j))
                existing.add((i, j))

    if len(edges) == n - 1 and n > 2:
        edges.append((0, n - 1))

    return edges

The experiment also includes nineteen explicit graph topologies that are not sampled from the additional-edge model. Table 12 lists these topologies immediately after the generator fragment, so the random and hand-specified graph sources are introduced in one continuous methodological block.

TopologyEdgesExact optimum
Path77
Cycle88
Star77
Wheel1410
Ladder 2x41010
Cube1212
Prism-tail119
Lollipop108
Barbell97
House-tail98
Bowtie-tail97
Sparse bipartite1010
Chordal cycle128
Dense core with leaves139
Two squares1010
Fan1310
Zigzag with chords1310
Bridge mesh1010
Ring with hubs1310

Table 12. Hand-specified unweighted custom graph topologies used as a separate experimental group.

The custom list makes the nonrandom part of the experiment auditable. The topologies cover sparse trees, cycles, bipartite graphs, dense cores with leaves, and mixed bridge structures while preserving the unweighted-graph restriction of the QASPA construction.

The QASPA state update is deterministic once the edge order and angle are fixed. The depth parameter is retained in Listing 8 to make clear how a later experiment could repeat the same edge schedule, even though the numerical comparison in this manuscript uses one layer.

Listing 8: Full QASPA state construction used in the experiment.

def qaspa_state(edges, n, alpha, depth=1):
    state = zero_state(2**n)
    state[0] = 1

    for q in range(n):
        apply_h(state, q)

    for layer in range(depth):
        for i, j in edges:
            apply_cz(state, i, j)
            apply_ry(state, j, alpha)
            apply_cx(state, i, j)

    return state

For the QAOA baseline, the state starts from ∣+⟩⊗n\lvert+\rangle^{\otimes n}, receives the diagonal phase generated by the Max-Cut cost, and then receives the global XX mixer. Listing 9 follows Equations (4) and (5) closely, making the transition from the mathematical expression to the exact state-vector calculation explicit.

Listing 9: Depth-one QAOA state construction.

def qaoa_state(edges, n, gamma, beta):
    state = plus_state(n)
    cut_values = [cut_value(mask, edges) for mask
                  in range(2**n)]

    for mask in range(2**n):
        state[mask] *= exp(-1j * gamma *
                           cut_values[mask])

    for q in range(n):
        apply_rx_mixer(state, q, beta)

    return state

The restart comparison is a classical wrapper around this state preparation. A single local optimization can stop in a poor region of the two-dimensional parameter landscape, so the restart routine records the best value after the first start, after the first two starts, and so on until ten starts. This best-so-far trace is the quantity shown in Figure 9 and Table 7–Table 9, where the sparse random, denser random, and hand-specified topology groups are reported separately. Listing 10 gives this best-of-kk wrapper explicitly.

Listing 10: Best-of-kk QAOA restart wrapper.

def qaoa_best_of_k(edges, n, k_max):
    best = -infinity
    trace = []

    for k in range(1, k_max + 1):
        gamma0, beta0 = random_angles()
        gamma, beta = local_search(edges, n,
                                    gamma0, beta0)
        state = qaoa_state(edges, n, gamma, beta)
        ratio = expected_cut(state, edges) /
                exact_optimum(edges, n)
        best = max(best, ratio)
        trace.append((k, best))

    return trace

The topology readout test uses the same QASPA classical selection rule, but the four candidates are obtained from observed counts rather than from exact probability ordering. Listing 11 records this finite-shot wrapper separately so that it is not confused with the QAOA restart loop.

Listing 11: Finite-shot QASPA classical selection for topology tests.

def qaspa_sampled_selection(state, graph, n):
    shots = ceil(0.03047 * 2**n + 1016.2)
    counts = sample(abs(state)**2, shots)

    selected = four_most_frequent_bitstrings(
        counts)
    best_cut = max(cut_value(mask, graph.edges)
                   for mask in selected)
    return best_cut / exact_optimum(graph)

The exact optimum is computed by exhaustive enumeration in these small instances, which is not a scalable Max-Cut solver but is appropriate for n=8n = 8 because it gives an unambiguous denominator for the approximation ratio. The enumeration routine is shown in Listing 12.

Listing 12: Exact optimum for the small graphs in this manuscript.

def exact_optimum(edges, n):
    best_value = -infinity
    best_masks = []

    for mask in range(2**n):
        value = cut_value(mask, edges)
        if value > best_value:
            best_value = value
            best_masks = [mask]
        elif value == best_value:
            best_masks.append(mask)

    return best_value, best_masks

Future Work and Scope

The main experimental result is reported as a mean over graph groups rather than as a claim about every graph. This matters because variational optimization can behave unevenly across instances. Some instances can be easy for one ansatz and hard for another, and small changes in the optimizer starting point can change the local optimum found by QAOA. The restart curve is a diagnostic of classical search sensitivity, not a universal ordering of algorithms.

The fixed QASPA line functions as a low-classical-search baseline. It does not require a two-dimensional optimizer, and in the fixed-angle condition it does not require any instance-specific angle selection. This keeps the contrast with QAOA focused on the visible restart budget rather than on two different forms of classical parameter search.

The QAOA line is intentionally shown as best-of-kk rather than as ten independent unrelated numbers. A practitioner who can afford ten local starts will keep the best result, so the best-of-kk curve is the relevant budget curve. The plateau in this experiment means that, after several starts, additional random initializations did not substantially change the mean expected ratio under the chosen optimizer and graph group. It does not mean that no other optimizer, initialization rule, or QAOA depth could improve the result.

The edge-block view also clarifies why unweighted graphs are the scope adopted in the current paper. The QASPA circuit uses the same angle on each edge, and the graph structure enters through the placement and ordering of edge blocks. Simply multiplying the angle by a weight would change the interpretation of the block and would need to be justified as a separate algorithm. The present manuscript keeps the scientific question narrow: what can be learned from edge-encoded RyR_y mixing on unweighted Max-Cut instances?

Figure 11 summarizes the natural extension path from the present exact simulations toward more demanding evaluations.

Figure 11. Suggested extension path beyond the present exact-simulation study, moving from broader finite-shot studies toward a separately derived weighted variant.

The next step is to add one complication at a time: broader finite-shot uncertainty intervals, hardware-aware compilation, larger unweighted graph families, and then a separately derived weighted variant if the unweighted behavior remains promising. This sequence helps prevent the present result from being overread as a hardware or scaling claim. The experiments in this paper test whether the fixed QASPA state places large cuts inside the candidate set chosen by its classical selection stage on small unweighted graphs, and they compare that behavior with the restart sensitivity of depth-one QAOA. They do not estimate device noise, routing overheads, asymptotic scaling, or the effect of stronger classical baselines. Those questions are best added after the finite-shot behavior is measured across a broader collection of unweighted instances, because otherwise sampling variation, optimizer sensitivity, and hardware effects would be mixed into one ambiguous performance number.

The order in Figure 11 is deliberately conservative. Finite-shot uncertainty is still placed before hardware mapping because sampling variation is easier to interpret when it is separated from device noise. Stronger classical baselines are placed before any weighted-graph extension because the present QASPA block does not define a weight-dependent angle rule. This ordering keeps future work connected to the assumptions used in the current experiments.

Table 13 lists the checks that should be added before moving from the present paper to a hardware-facing claim, and it records the boundary between this manuscript and the next research stage rather than introducing a new experiment.

CheckWhy it mattersCurrent status
Finite-shot studySampling variance50 readouts
Noise modelGate errorsNot modeled
Mapping2-qubit routingNot modeled
Larger nnScalingNot included
BaselinesSeparationFuture work
Weighted variantAngle ruleFuture work

Table 13. Future checks that should precede any hardware-facing claims about QASPA performance.

Conclusion

This paper develops QASPA-MaxCut as a reproducible Max-Cut study by defining the edge-encoded RyR_y block algebraically and showing the complete transformation sequence on an unweighted test graph. It also includes the graph, probability, and schematic figures used in the text, and it adds a comparison against depth-one QAOA under a visible restart budget. The topology-level readout check further shows how the proposed shot rule interacts with the QASPA classical selection stage on hand-specified graph shapes.

The main empirical observation is that the fixed QASPA state places large-cut strings among its highest-probability candidates in the tested instances, while the QAOA expected ratio improves as additional classical optimizer starts are allowed. The next scientific question is whether this candidate-quality behavior persists for larger unweighted graphs and noisy hardware-aware execution.

Author Contribution Statement

Dmytro Sapozhnyk conceived the study, developed the QASPA-MaxCut formulation, implemented the simulations, designed the experiments, interpreted the results, and wrote and revised the manuscript. AI-assisted tools were used only to generate schematic diagrams used as visual aids in the manuscript. The author reviewed all generated schemes and takes full responsibility for the content of the work.

Data and Code Availability

The numerical values reported in the paper are given directly in the tables and figures, and the experimental protocol is specified by the graph families, fixed seed, shot rule, QASPA classical selection rule, and QAOA restart budget described in the main text. A frozen supplementary source archive containing the simulation code, raw numerical arrays, plotted data, and figure-generation inputs is prepared for anonymous editor and referee inspection. No external datasets are required. Upon acceptance, the public archive is intended to be released under a FOSS license compatible with the journal’s open-source policy.

References

  1. [1]E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv:1411.4028, 2014. https://arxiv.org/abs/1411.4028.
  2. [2]M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of the ACM, vol. 42, no. 6, pp. 1115–1145, 1995. https://doi.org/10.1145/227683.227684.
  3. [3]K. Blekos, D. Brand, C. C. Chou, R.-H. Li, K. Pandya, and A. Summer, “A review on Quantum Approximate Optimization Algorithm and its variants,” Physics Reports, vol. 1068, pp. 1–66, 2024. https://doi.org/10.1016/j.physrep.2024.03.002.
  4. [4]T. Lubinski, C. Coffrin, C. McGeoch, P. Sathe, J. Apanavicius, and D. E. B. Neira, “Optimization applications as quantum performance benchmarks,” ACM Transactions on Quantum Computing, vol. 5, no. 3, article 18, 2024. https://doi.org/10.1145/3678184.
  5. [5]M. Dupont, B. Sundar, B. Evert, D. E. B. Neira, Z. Peng, S. Jeffrey, and M. Hodson, “Benchmarking quantum optimization for the maximum-cut problem on a superconducting quantum computer,” arXiv:2404.17579, 2024. https://arxiv.org/abs/2404.17579.
  6. [6]D. Rehfeldt, T. Koch, and Y. Shihano, “Faster exact solution of sparse MaxCut and QUBO problems,” Mathematical Programming Computation, vol. 15, pp. 445–470, 2023. https://doi.org/10.1007/s12532-023-00236-6.
  7. [7]R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, “Multi-angle quantum approximate optimization algorithm,” Scientific Reports, vol. 12, 2022. https://doi.org/10.1038/s41598-022-10555-8.
  8. [8]L. C. G. Govia, C. Poole, M. Saffman, and H. Krovi, “Freedom of the mixer rotation axis improves performance in the quantum approximate optimization algorithm,” Physical Review A, vol. 104, p. 062428, 2021. https://doi.org/10.1103/PhysRevA.104.062428.
  9. [9]V. Vijendran, A. Das, D. E. Koh, S. Assad, and P. K. Lam, “An expressive ansatz for low-depth quantum approximate optimization,” Quantum Science and Technology, vol. 9, p. 015021, 2024. https://doi.org/10.1088/2058-9565/ad200a.
  10. [10]Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, “XY mixers: Analytical and numerical results for the quantum alternating operator ansatz,” Physical Review A, vol. 101, p. 012320, 2020. https://doi.org/10.1103/PhysRevA.101.012320.
  11. [11]F. G. Grus, K. H. Lye, H. M. Nilsen, A. J. Stasik, and G. Sartor, “Constraint preserving mixers for the quantum approximate optimization algorithm,” Algorithms, vol. 15, p. 202, 2022. https://doi.org/10.3390/a15060202.
  12. [12]S. Hadfield, T. Hogg, and E. G. Rieffel, “Analytical framework for quantum alternating operator ansätze,” arXiv:2105.06996, 2021. https://arxiv.org/abs/2105.06996.
  13. [13]R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, “Parameter transfer for quantum approximate optimization of weighted MaxCut,” ACM Transactions on Quantum Computing, vol. 4, pp. 1–15, 2022. https://doi.org/10.1145/3549554.
  14. [14]S. H. Sureshbabu, D. Herman, R. Shaydulin, J. Basso, S. Chakrabarti, Y. Sun, and M. Pistoia, “Parameter setting in quantum approximate optimization of weighted problems,” Quantum, vol. 8, p. 1231, 2024. https://doi.org/10.22331/q-2024-01-18-1231.
  15. [15]B. Choy and D. J. Wales, “Energy landscapes for the quantum approximate optimisation algorithm,” arXiv:2401.04784, 2024. https://arxiv.org/abs/2401.04784.
  16. [16]D. J. Egger, J. Mareček, and S. Woerner, “Warm-starting quantum optimization,” Quantum, vol. 5, p. 479, 2021. https://doi.org/10.22331/q-2021-06-17-479.
  17. [17]R. Tate, J. Moondra, B. T. Gard, G. Mohler, and S. Gupta, “Warm-started QAOA with custom mixers provably converges and computationally beats Goemans–Williamson’s Max-Cut at low circuit depths,” Quantum, vol. 7, p. 1121, 2023. https://doi.org/10.22331/q-2023-09-07-1121.
  18. [18]Y. Yu, X.-B. Wang, N. Shannon, and R. Joynt, “Warm-start adaptive-bias quantum approximate optimization algorithm,” arXiv:2503.20048, 2025. https://arxiv.org/abs/2503.20048.
  19. [19]J. Falla, Q. Langfift, Y. Alexeev, and I. Safro, “Graph representation learning for parameter transferability in quantum approximate optimization algorithm,” arXiv:2401.06655, 2024. https://arxiv.org/abs/2401.06655.
  20. [20]D. Sapozhnyk, “Solving the Max-Cut problem using the QASPA algorithm,” Bulletin of National Technical University “KhPI”. Series: System Analysis, Control and Information Technologies, no. 2(14), pp. 96–101, 2025. https://doi.org/10.20998/2079-0023-2025-02-13.

Paper details

vlnc:W_uqxvmb86
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

AI-assisted tools

View statement
Looking for related papers…
Contents