⚛️ quantum physics

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

This paper introduces QASPA-MaxCut, a shift-phase circuit encoding graph edges via controlled $R_y$ rotations, and demonstrates through exact simulations on various unweighted graphs that its fixed-angle approach with a classical selection stage outperforms depth-one QAOA even when the latter utilizes multiple classical restarts.

Original author: Dmytro Sapozhnyk

Published 2026-11-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: Dmytro Sapozhnyk

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the quiet corner of computing where scientists are trying to build machines that think differently, there is a persistent challenge known as the Max-Cut problem. Imagine a group of people at a party who need to be split into two separate rooms. The goal is to arrange them so that the maximum number of friendships exist between the two rooms, rather than within them. This simple-sounding task becomes incredibly difficult as the number of people grows, because the number of possible arrangements explodes faster than a human mind can calculate. For decades, classical computers have been the best tools we have for solving this, but researchers are now testing a new kind of machine: the quantum computer. These devices use the strange rules of the subatomic world to explore many possibilities at once. However, these early quantum machines are still fragile and prone to errors, so scientists must be very careful about how they ask them to solve problems. They need to know not just if a quantum machine can find a good answer, but how much effort it takes to get there, and whether that effort is worth the trouble compared to the reliable computers we already use.

A recent study by Dmytro Sapozhnyk tackles this question by comparing two different ways of asking a small quantum computer to solve the Max-Cut problem. The first method is a well-known approach called QAOA, which acts like a hiker trying to find the highest peak in a foggy landscape. The hiker takes a step, checks the height, and then adjusts their path based on that information. This process requires a lot of trial and error, with the computer running the same calculation over and over again, each time starting from a slightly different guess, hoping to stumble upon the best solution. The second method, which the author developed and named QASPA, takes a different approach. Instead of a hiker wandering through the fog, this method builds a specific path through the landscape that is designed to lead directly toward the high peaks. It uses a fixed set of instructions that do not change, relying on the structure of the problem itself to guide the quantum machine.

The researchers tested these two methods on a collection of small, unweighted graphs, which are essentially maps of connections between points. They simulated the behavior of a quantum computer with eight points, a size small enough to be calculated perfectly on a standard computer, allowing them to see exactly what the quantum machine would do without any noise or errors interfering. They ran the "hiker" method, QAOA, with a limited budget of attempts. They started with just one guess and gradually increased the number of attempts to ten, recording how much better the answers got each time. They also ran the fixed-path method, QASPA, just once, using a single, unchanging set of instructions. The results showed a clear difference in how the two methods performed. The hiker method, QAOA, did improve as it was allowed more attempts, slowly climbing higher in its search for the best arrangement. However, even after ten attempts, its average performance was still lower than the single, fixed run of the new QASPA method.

What made the QASPA method stand out was not that it found the absolute perfect answer every single time, but that it placed the best possible answers at the very top of its list of likely outcomes. When the researchers looked at the four most probable results generated by QASPA, they found that the best arrangement was almost always among them. In fact, for many of the test cases, the best arrangement was the single most likely outcome. This means that if a user simply picks the best option from the top few suggestions, they get an excellent result without needing to run the complex, time-consuming search that the other method requires. The study also checked if this result held up when the computer was forced to make a limited number of measurements, simulating the real-world constraints of a physical machine. Even with these limitations, the fixed-path method remained stable and reliable, consistently delivering high-quality candidates.

The researchers were careful to note that these findings come from simulations of very small systems and do not yet prove that this method will work better on larger, real-world problems or on actual quantum hardware. They did not claim to have solved the Max-Cut problem for all situations, nor did they suggest that their method is a magic bullet that makes classical computers obsolete. Instead, they provided a controlled comparison showing that for these specific, small instances, embedding the structure of the problem directly into the quantum instructions was more efficient than relying on a repetitive search process. The study suggests that by designing quantum circuits that respect the specific shape of the problem, we might be able to get better results with less effort, even on the imperfect machines of today. This insight offers a new direction for future research, pointing toward a way of building quantum algorithms that are less dependent on constant tuning and more focused on the inherent geometry of the problem they are trying to solve.

Technical Summary: QASPA-MaxCut on Unweighted Graphs

Problem Statement
The paper addresses the performance bottlenecks of the Quantum Approximate Optimization Algorithm (QAOA) in the Noisy Intermediate-Scale Quantum (NISQ) regime. While QAOA is a canonical variational approach for combinatorial optimization (specifically Max-Cut), its reported performance is heavily dependent on the classical outer-loop optimization of variational parameters. In practice, limited gate depth, noise, and the computational cost of repeated circuit evaluations constrain the ability to find optimal parameters. The author aims to isolate the impact of classical search budgets by comparing a standard depth-one QAOA against a new circuit construction, QASPA-MaxCut, which embeds graph structure directly into the circuit ansatz to reduce reliance on parameter tuning.

Methodology
The study introduces QASPA-MaxCut, a shift-phase circuit designed for unweighted graphs. Unlike standard QAOA, which alternates a global problem unitary ( $e^{-i\gamma H_C}$ ) and a global transverse-field mixer ( $e^{-i\beta \sum X_i}$ ), QASPA replaces the global mixer with edge-local controlled rotations.

Circuit Construction: The QASPA ansatz begins with a Hadamard layer to create a uniform superposition. For each edge $(i, j)$ in the graph, a specific block is applied: $CX_{i,j} R_y^{(j)}(\theta_{ij}) CX_{i,j}$ .
Edge Encoding: The rotation angle $\theta_{ij}$ is fixed globally to $\alpha = \pi/4$ for all edges in the unweighted case. The block algebraically acts as $\exp(-i \frac{\alpha}{2} Z_i Y_j)$ , redistributing amplitude between cut and uncut configurations for the specific edge pair rather than applying a diagonal phase.
Experimental Protocol:
- Graphs: The study uses exact state-vector simulations on small instances ( $n=8$ vertices). Graphs include connected backbone-augmented random graphs (with additional edge probabilities $p_{edge} \in \{0.1, 0.3, 0.5, 0.7\}$ ) and 19 hand-specified custom topologies.
- QAOA Baseline: A depth-one QAOA circuit is optimized using a local Nelder-Mead optimizer. The performance is measured as a "best-of- $k$ " curve, where $k$ represents the number of independent random restarts (ranging from 1 to 10).
- QASPA Evaluation: QASPA is run with the fixed angle $\alpha = \pi/4$ without an outer-loop search. The reported score is the classical selection ratio: the algorithm selects the four bit strings with the highest output probabilities, evaluates them against the Max-Cut objective, and reports the best cut found among them.
- Readout: For custom topologies, a finite-shot readout check is performed using an adaptive shot budget ( $N_{shots} = \lceil 0.03047 \cdot 2^n + 1016.2 \rceil$ ) to verify stability under sampling noise.

Key Contributions

Algebraic Derivation: The paper provides the exact two-qubit algebra of the QASPA edge block, demonstrating how the $CX-R_y-CX$ sequence redistributes amplitude between cut and uncut states, effectively embedding edge structure into the mixing step.
Worked Example: A complete, traceable mathematical and numerical walkthrough of a four-vertex unweighted graph is provided, detailing the edge schedule, state evolution, and output probabilities to validate the construction.
Controlled Comparison: The study establishes a reproducible experimental framework comparing a fixed-angle, structure-embedded circuit (QASPA) against a variational baseline (QAOA) with a transparent classical search budget. This isolates the "restart effect" to determine how much classical optimization is required to compete with the fixed-angle approach.

Results

Candidate Quality: In the tested small instances, the fixed-angle QASPA state places the optimal (or near-optimal) Max-Cut solutions within the top four highest-probability bit strings. Consequently, the QASPA classical selection ratio is extremely high, ranging from 0.955 to 1.000 across graph groups.
QAOA Sensitivity: The depth-one QAOA performance is highly sensitive to the number of classical restarts. While the expected approximation ratio improves with additional restarts (e.g., rising from ~0.71 to ~0.79 for sparse graphs), it consistently remains lower than the QASPA selection score within the tested budget of 10 restarts.
Stability: The finite-shot readout checks on custom topologies show that the QASPA selection score remains stable (mean 1.000 with zero standard deviation) under the prescribed shot budget, confirming the robustness of the candidate selection rule for these specific instances.
Edge Order Sensitivity: The study notes that QASPA is not order-invariant due to non-commuting edge blocks. However, random permutations of edge orders in the tests yielded group means close to the canonical fixed-order values, suggesting some resilience in small-scale tests.

Significance and Claims
The paper makes modest, controlled claims rather than asserting asymptotic superiority or hardware dominance. The primary finding is that for small, unweighted graphs, a fixed-angle QASPA circuit can generate a candidate set containing high-quality Max-Cut solutions without the need for an expensive outer-loop parameter search. In contrast, the standard depth-one QAOA requires a significant classical optimization budget (multiple restarts) to approach similar performance levels, and even then, it does not surpass the QASPA selection score in the reported means.

The author frames this as a demonstration that embedding instance structure directly into the circuit ansatz (via edge-local mixing) can reduce the burden on classical parameter tuning. The work serves as a baseline for understanding the trade-off between circuit structure and classical search budget at shallow depths. The paper explicitly avoids claims regarding scaling to larger $n$ , performance on weighted graphs, or behavior on noisy hardware, identifying these as necessary future steps before hardware-facing conclusions can be drawn.

More like this