Technical Summary: RASP-QAOA

Problem Statement

Exact simulation of the Quantum Approximate Optimization Algorithm (QAOA) relies on classical computational representations that exhibit sharply divergent performance characteristics depending on graph structure, circuit depth ($p$), numerical precision, and available memory. No single backend or representation is uniformly optimal. For instance, full-state GPU implementations are efficient when memory permits but fail for large $n$; tensor contraction avoids state materialization but scales poorly with contraction width; and local evaluators are effective only at shallow depths. Furthermore, constraint-preserving mixers can reduce the basis size from $2^n$ to $\binom{n}{k}$, opening distinct feasible regions.

Current approaches often select a "backend name" (e.g., CUDA-Q), which implicitly fixes the representation, adapter, precision mode, and memory policy. This coarse selection fails to exploit the heterogeneity of available simulators. The paper argues that the decision must be made at the level of the executable action—a specific tuple of representation, adapter, configuration, precision, and memory policy—rather than a generic backend. The core challenge is to select the optimal action for a specific QAOA request $x = (G, H_C, p, M, \epsilon, B, H)$, where $G$ is the graph, $p$ is depth, and $B$ is the memory budget, while ensuring the action is semantically compatible and can complete within resource constraints.

Methodology: RASP-QAOA

The author proposes RASP-QAOA (Resource-Aware Per-Instance Selection for Exact QAOA), a two-stage selection framework that operates over a portfolio of ten distinct executable actions. The method separates the decision into compatibility (feasibility) and ordering (performance prediction).

1. Compatibility Filtering

Before ranking, the system filters the action portfolio to form a candidate set $C(x)$. An action $a$ is included only if it satisfies four conditions:

• Semantic ($S_a$): The representation and mixer support the problem constraints (e.g., fixed-weight mixers require specific subspace representations).
• Precision ($P_a$): The configured precision (e.g., fp32 vs. fp64) matches the request's numerical tolerance.
• Deployment ($D_a$): The required software package and device path are available.
• Memory ($M_a$): A calibrated peak-memory estimate (based on $n$, $p$, and representation type) fits within $\min(B, 0.9 \times \text{VRAM})$.

This stage ensures that the selected action is capable of implementing the requested QAOA semantics and execution requirements.

2. Ordering Strategy

Once $C(x)$ is established, RASP-QAOA orders the actions using a hybrid approach:

• Learned Support ($A_\phi$): For actions observed during development, a feature-based ranker $q_\phi(a, z(x))$ predicts performance. The feature vector $z(x)$ includes graph size, density, depth, degree statistics, and proxies for contraction width or causal cones.
• Analytical Estimation: If $C(x)$ contains actions outside the learned support (i.e., $C(x) \cap A_\phi = \emptyset$), the system falls back to representation-aware work estimates. These are analytical proxies based on theoretical scaling, such as $p2^n$ for full-state, $p\binom{n}{k}$ for fixed-weight, and contraction-width estimates for tensor methods.

The final policy selects the highest-scoring action from the learned set if available; otherwise, it selects the action with the lowest analytical work estimate. The two stages are never compared on a shared scale; the learned path takes priority.

Key Contributions

1. Per-Instance Formulation: The decision object is defined as a complete executable action key (representation + adapter + configuration), with compatibility determined strictly before performance ranking.
2. Hybrid Selection Policy: RASP-QAOA integrates request-aware compatibility checks, feature-based ordering for development-supported actions, and analytical ordering for compatible actions outside the learned support.
3. Component-Resolved Evaluation: The paper provides a rigorous evaluation on a fresh H200 hardware portfolio, distinguishing between coverage (finding a valid action) and ranking quality (finding the fastest valid action).

Experimental Results

The evaluation was conducted on a fresh 60-request test set using NVIDIA H200 GPUs, disjoint from the development data.

• Coverage: Among the 60 requests, 31 had at least one admissible action that completed and validated (strict completion). RASP-QAOA successfully selected a valid action for all 31 of these requests. In contrast, development-selected CUAOA covered only 19, and a static priority baseline covered 23.
• Ranking Quality: On the 31 solvable requests, RASP-QAOA achieved 27/31 top-1 selections (within the first 5% timing-equivalent group) and 31/31 top-2 selections.
• Performance Metrics:
  • Geometric-mean regret: 1.051.
  • Failure-penalized PAR10: 0.0396 times that of the development-selected CUAOA (a 25.26-fold improvement).
  • Planning Time: Median of 22.5 $\mu$s.
• Structural Crossover: A separate 30-request crossover experiment varying graph structures (with fixed $n=20, p=2$) showed that using full structural features improved top-1 selection from 12/30 to 25/30 compared to using only $n$ and $p$. A simple depth-1 decision stump matched the performance of gradient boosting, suggesting that the gains come from representation features rather than classifier complexity.
• Robustness: The results remained stable across different reuse horizons ($h=1$ to $32$) and numerical tolerance settings.

Significance and Claims

The paper claims that resource-aware representation selection is critical for exact QAOA simulation at scales of $n \le 35$ and $p \le 5$. The primary contribution is not a new simulator, but a selection mechanism that dynamically matches the problem instance to the most suitable computational representation.

The author emphasizes that the observed performance gains are driven by:

1. Portfolio Breadth: The ability to identify and select representations (like fixed-weight or local evaluators) that development-selected baselines (like CUAOA) cannot use due to semantic or memory incompatibility.
2. Feature-Based Ordering: The ability to rank overlapping compatible actions based on instance structure.

The paper explicitly states that the results are specific to the tested hardware (H200), software stack, and exact expectation-value simulation. It does not claim to solve approximate simulation or different hardware targets, noting that these would require new action definitions and calibration. The work demonstrates that separating compatibility checks from performance ranking allows for a robust selection policy that maximizes coverage while maintaining high ranking accuracy.