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

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.