Recursive quantum optimization stops paying equal shots per step: a learned controller cuts weighted Max-Cut sampling by 36%
Synopsis
Recursive QAOA re-measures at every variable elimination, so shot cost compounds along the recursion even though steps differ in difficulty. The work casts step-wise shot allocation in depth-1 recursive QAOA as a sequential decision problem: a hand-crafted rule keyed to local difficulty sets a baseline, and a tabular Double Q-learning agent learns residual corrections under a Lagrangian constraint while the elimination rule stays fixed. Under a fixed per-step cap, on 130 held-out policy-instance pairs the heuristic cuts total shots by about 23% and the learned policy by 36.1% versus uniform allocation, with an effective shots-per-success ratio of 0.676, and the gain holds at about 36.6% on problem sizes unseen in training.
Interpretation
The measurement cost of recursive quantum approximate optimization (RQAOA) can be tuned step by step instead of spending the same number of shots at every elimination. Earlier shot-reduction work mostly targets variational eigensolvers and gradient-based parameter-update loops; step-wise measurement control inside the recursive elimination chain has drawn little attention. Under a fixed per-step cap with the elimination rule unchanged, the learned policy achieves a mean pairwise shot reduction of 36.1% versus uniform allocation on 130 held-out operational policy-instance pairs, against 23.0% for the heuristic.
A hand-written rule first judges how hard the current elimination step is, and the learned policy then adds or subtracts shots around that baseline. The heuristic reads four quantities: remaining variables, the ratio of the two largest absolute correlations, the endpoint conflict ratio among the top three candidate edges, and the graph distance between the two strongest edges, choosing among fractions of the cap from 20% to 80%. A tabular Double Q-learning agent outputs a level offset from that baseline, trained on a noiseless simulator with a single designated weighted Max-Cut instance as its base, using 16 or 32 probe shots per step that count toward the total.
The learned corrections transfer to node counts not seen during training rather than memorizing size-specific thresholds. The cross-size subset spans n from 15 to 25, excluding the training sizes 14 and 20, giving 98 policy-instance pairs as the most demanding transfer test. On that subset the learned policy's mean shot reduction is 36.6%, essentially matching the overall held-out average, while the heuristic reaches 22.2%.
Perspective
The demonstrated scope is depth-1 recursive QAOA on d-regular Gaussian-weighted Max-Cut instances in a noiseless simulator, with the elimination rule and circuit construction unchanged; the held-out operational subset is 130 policy-instance pairs over 81 unique instances, and the cross-size subset is 98 pairs.
The training constraint targets a success rate of 0.95, while the observed success rate on the held-out operational subset is about 0.91; the constraint is enforced on a designated training instance through an adaptive multiplier, whereas test-time evaluation aggregates held-out instances of varying difficulty. All experiments run on a noiseless simulator, and settings beyond depth 1 and behavior on real hardware are not evaluated.