acceptodds
Withdrawn from ICLR 2027

BOLT-DA: A Shot-Efficient Depth-Aware QAOA for MaxCut

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Optimizing the Quantum Approximate Optimization Algorithm (QAOA) under a limited measurement budget requires allocating measurements between parameter search and reliable comparison of candidate solutions. We propose BOLT-DA, a depth-aware optimizer for MaxCut that combines branch-specific search continuation with structured reuse of solutions from preceding depths. BOLT-DA maintains separate searches on the target graph and a reduced donor graph, augments their outputs with interpolation and identity-padded candidates, and uses fresh measurements on the target graph to select from this constant-size candidate pool under an explicitly accounted raw-shot budget. On held-out AIDS, Linux, and IMDb graphs, BOLT-DA achieves higher mean approximation ratios and lower normalized-gap mean squared errors than Red-QAOA, Neural QAOA2, and an MG-inspired multi-angle control across all 15 dataset-depth settings at the primary low-shot configuration. At depth 5, its MSE is 32.33%–81.00% lower than Neural QAOA2. Equal-budget ablations identify identity padding as the principal source of candidate-reuse gains and show that the reduced donor provides a quality–logical-cost trade-off relative to a second target-search branch. Experiments on 12-, 14-, and 16-node graphs retain leading native-solution means across all 15 size-depth settings, and a five-node hardware case study demonstrates practical execution behavior.

Primary area:
applications to physical sciences (physics, chemistry, biology, etc.)
Keywords:
Quantum Approximate Optimization Algorithm (QAOA), MaxCut, shot-efficient optimization, depth-aware parameter transfer, variational quantum algorithms

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_V4ZcOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies QAOA parameter optimization under a limited measurement budget, addressing how to allocate shots between candidate search and evaluation, and how to reuse effective parameters as circuit depth increases. The proposed BOLT-DA framework divides the budget among original-graph search, reduced-graph search, and candidate selection. It combines branch-specific continuation with interpolation and zero-padding of previously selected parameters, followed by fresh evaluation on the original graph.

Critical strengths

Allocating limited measurements between parameter search and candidate evaluation addresses a meaningful challenge in QAOA optimization. Explicitly accounting for both costs makes the evaluation relevant to settings with restricted measurement budgets.

Critical weaknesses
  1. Limited methodological novelty. The framework combines established components: INTERP[1], zero-angle insertion[2], and reduced-graph parameter transfer[3]. Its distinctive separation of branch-specific continuation from selected-solution reuse is not isolated experimentally, leaving the incremental contribution unclear. No direct ablation isolates the benefit of continuing each branch from its own previous output rather than from the previously selected winner.

  2. Insufficient evidence for the incremental benefit of the full design. Under matched shot budgets and circuit-batch counts, replacing the reduced-graph branch with a second original-graph search (2ndT) yields significantly higher mean approximation ratios on AIDS and Linux, by 0.42 and 0.48 percentage points, respectively (Table 10). Although BOLT-DA reports lower MSE point estimates and reduced logical gate costs, the evidence does not clearly establish the full design’s incremental value over simpler alternatives.

[1] Zhou, Leo, et al. "Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices." Physical Review X (2020).

[2] Sack, Stefan H., et al. "Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement." Physical Review A (2023).

[3] Wang, Meng, et al. "Red-qaoa: Efficient variational optimization through circuit reduction." Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. (2024).

Questions for authors
  1. Please verify and correct the bibliography: Arrasmith et al. (2021) has an incorrect author list; Pagano et al. (2020) contains two incorrect author names and omits an author; and the DOI for Shaydulin and Wild (2021) points to a different paper. 2. How was Neural QAOA² adapted to the small-graph, finite-shot, and increasing-depth settings? 3. Does removing the guard throughout the entire depth ladder, rather than only reselecting from fixed final-depth pools, materially change performance? 4. Do all results labeled “MG-Net” correspond to the MG-control described in Table 6?
Reviewer_YuUvOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies QAOA parameter optimization for MaxCut under a limited measurement budget. It proposes BOLT-DA, which combines searches on the original and reduced graphs with parameter reuse across circuit depths. The main idea is to preserve earlier solutions while continuing the search, then compare a small set of candidates using fresh measurements on the original graph. Experiments report better solution quality than the tested baselines on small graphs.

Critical strengths
  1. The problem is meaningful. Limited measurements make both parameter search and candidate comparison unreliable. Explicitly budgeting these two stages addresses a real issue in QAOA optimization.

  2. The reported results are positive. BOLT-DA achieves higher mean approximation ratios and lower squared optimality gaps than the tested baselines in the main small-graph experiments. The paired statistical analysis supports the approximation-ratio improvements at the final depth.

  3. The component analysis is useful. The ablations identify identity padding as an important source of improvement. The resource audit also makes several quality–cost trade-offs explicit.

Critical weaknesses
  1. I noticed that baselines are often evaluated on scales involving graph with hundreds or thousands of nodes. However, the graphs used in the main experiments of this paper contain only 3–10 nodes, and even in the extended experiments, they consist of only 16 nodes. Isn't this sample size a bit too small? The hardware study also only uses a single five-node graph and evaluates already optimized circuits. These results provide limited evidence about how the method’s benefits and resource requirements change on larger instances.

  2. Although the paper reports resource costs, the main quality comparisons match raw measurement counts. Through depth five at (q=32), BOLT-DA uses 5,188 circuit batches, compared with 3,840 for Red-QAOA. Its reported logical gate-shot costs are also higher than Red-QAOA’s (Appendix E). Without a quality–runtime comparison, it is difficult to assess whether the improved solutions justify the additional computation.

  3. The methodological advance over existing depth-wise QAOA optimization methods needs clearer justification. My understanding is that an important part of the method is to retain good solutions from shallower circuits while continuing optimization at larger depths. The ablations support the usefulness of this mechanism. However, the variant using only ZPAD for historical-solution reuse already achieves mean approximation ratios close to those of the full method. Could the authors clarify which benefits require their specific separation of branch continuation and winner reuse, and compare against a simpler depth-wise optimizer with historical-solution retention under the same measurement budget?

Questions for authors

See Weaknesses.

Reviewer_pREwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work considers how to optimize QAOA under limited shot budgets. It combines the parameter search results on original graph and reduced graph to obtain the parameters of QAOA circuits with higher performance. Results on three datasets demonstrate that the proposed method achieves higher approximation ratio and ablation studies explain the role of each component in the method.

Critical strengths
  1. The reported approximation ratio achieved by the proposed method is higher than other existing methods.

  2. This work considers the limitation of shot budgets, which is meaningful in practice.

Critical weaknesses
  1. This work can be regarded as an extension of Red-QAOA. However, the numerical results cannot support the benefit of the added operations compared to Red-QAOA. The main performance gain comes from retaining history solution.

  2. The theoretical analysis cannot explain the advantage of the proposed method.

  3. The writing of the manuscription needs further polishment.

Questions for authors
  1. What is the key advantage of the proposed method over Red-QAOA?

  2. Is the reduced-graph search branch necessary?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.