Shot-Aware Code Refinement for Post-Selected Quantum Programs

Many quantum programs work only "on condition": the circuit runs, an extra helper qubit is measured, and the run is kept only if that measurement gives the right answer. This is called post-selection. It is the standard way to apply operations that quantum hardware cannot perform directly, such as non-unitary matrices, imaginary-time evolution, or hard constraints. The cost is hidden in the discard rate. If each of $N$ conditional steps succeeds with probability $p$, only a fraction $p^N$ of runs survive. A program can pass every unit test on a small simulator and still need billions of repetitions at the problem sizes people care about. Language-model coding assistants for quantum software do not see this cost. They are trained and scored on whether the code runs and returns the right answer, never on how many runs it throws away.

We propose an inference-time refinement loop for quantum programs. A language model repeatedly rewrites a post-selected program, guided by a profiler that reports where in the program the runs are being discarded and how that loss grows with problem size. An equivalence checker confirms that the rewritten program still computes the same conditional output. The goal goes beyond faster code at a fixed size. We want rewrites that change how the discard cost scales: replacing terminal post-selection with mid-circuit checks, measurement-and-correct feedback, or dilations that need no discarding, and falling back to truncation or amplitude amplification when no such structure exists.

Core Claim

Our central hypothesis concerns where the scaling gains come from. On programs whose success probability decays exponentially in problem size $n$, a refinement loop that receives localized, per-measurement survival profiles will find structural rewrites that lower the fitted decay rate $\lambda$ in $P_{\text{succ}}(n) \approx e^{-\lambda n}$. These rewrites should hold on problem sizes larger than any the loop saw during refinement. Three cheaper strategies should not produce such gains, because they only change constants or halve the exponent: repeated sampling with selection, correctness-only refinement, and generic wrappers such as amplitude amplification.

We score each program by the expected cost per accepted sample at fixed output quality:

$$C(n) = \frac{T(n)}{P_{\text{succ}}(n)} \quad \text{subject to} \quad F(n) \ge F_0,$$

Here $T(n)$ is the circuit's execution time (depth weighted by gate and mid-circuit-measurement latencies), $P_{\text{succ}}(n)$ is the probability that a run is kept, $F(n)$ is the fidelity of the kept output to the reference, and $F_0$ is a task-specific threshold. The fidelity constraint matters because truncation can always buy success probability at the price of accuracy.

What Exists and Where This Differs

The closest work is quantum code generation with execution feedback. Qiskit Code Assistant adapts a 20B code model to modern Qiskit and generates code one-shot. Qiskit HumanEval reports that no model passed either "difficult" task. Quantum Verifiable Rewards puts a Qiskit simulator/hardware sandbox inside GRPO/DPO post-training and reaches 28.48% on QHE-hard. These papers motivate the proposal: execution feedback helps quantum code. They also mark the gap: feedback enters only at training time, and the reward is functional pass/fail. A correct program that discards 99.9999% of its runs gets full credit.

Classical refinement systems supply our method. POLO feeds call-graph profiles into an LLM refactoring loop and rejects changes that do not actually speed things up. That is the template for our profiler, with shot survival taking the place of CPU time. MEIC adds a scorer and rollback to the last stable version for RTL debugging. We reuse rollback to fight the "new error trap," where fixing one bug introduces another. The plateau after two or three iterations reported by Yan et al. constrains the design: we budget few iterations and test whether localized feedback delays the plateau.

Classical quantum compilers set the limit on what non-LLM rewriting already covers. QUESO synthesizes verified unitary rewrite rules using polynomial identity testing. It cannot reason about measurement, discarding, or feedforward. We borrow its idea of randomized equivalence testing and extend it to conditional (post-selected) maps. OnePerc is the one compiler in the file that directly attacks post-selection-style overhead, here from probabilistic photonic fusion. It does so with a hand-designed pass for one hardware model, not for arbitrary algorithm code.

The quantum literature shows that the rewrites we want exist but are derived by hand for each problem, so it supplies both targets and ceilings. Examples include measurement-based imaginary time evolution with adaptive feedforward for the AKLT state (Efficient preparation of the AKLT State), Stinespring dilation that makes Lindblad simulation succeed with probability one (Simulating Open Quantum Systems), mid-circuit parity checks that confine a constrained ansatz to valid permutations (Rethinking Parity Check Enhanced Symmetry-Preserving Ansatz), singular-value truncation in non-unitary basis transformations (Quantum circuit for non-unitary linear transformation of basis sets), and variational post-selection modules with success probability 0.5–0.7 (Variational post-selection).

The AKLT authors warn that their construction relies on special structure and may not generalize. We take that seriously. Part of the evaluation is a measurement of which tasks admit an exponent-changing rewrite at all. On tasks without such structure, a refinement loop "succeeding" should mean that it correctly falls back to bounded truncation or amplitude amplification rather than inventing a rewrite.

Research Program

We will build three components.

The first is a shot profiler. It runs a program at several small sizes in exact statevector simulation (up to roughly 20 qubits). For every mid-circuit or terminal post-selection point, it records the conditional survival probability given that earlier points passed. It then fits a per-point decay rate across sizes. Its report to the model reads like a profiler trace: which ancilla measurement accounts for most of the loss, how that loss grows with $n$, and, where relevant, the singular values or constraint violations responsible. This localization is the ingredient we expect to matter. A single scalar "your success probability is $10^{-5}$" tells the model nothing about what to change.

The second is a conditional equivalence checker. Two programs are equivalent if, for random input states, the normalized output state given acceptance matches the reference within tolerance. For channel tasks, we compare the accepted output channel on random probe states. Following QUESO's randomized-testing logic, we use many random inputs instead of a symbolic proof. We report the false-acceptance rate measured against deliberately corrupted programs.

The third is the refinement loop. It has a generator, a critic that reads the profiler and checker reports, a tool library the generator may call (amplitude amplification, mid-circuit measurement with classical conditioning, reset, Qiskit dynamic-circuit primitives), and rollback to the best program seen so far under $C(n)$ subject to the fidelity constraint. Programs must be written as functions of $n$. Refinement sees only small $n$. Scoring happens at held-out larger $n$, computed exactly where simulation allows and otherwise from the fitted per-point decay rates, which we validate against exact values at the largest simulable size.

Alongside these components we will build a benchmark, which the file shows does not yet exist. It will contain about 40 tasks. Each pairs a naive, test-passing post-selected Qiskit implementation with a reference output and, where the literature gives one, an expert low-overhead solution. Task families come directly from the papers above: AKLT and other frustration-free ground states prepared by repeated post-selected projections, Lindblad dynamics via post-selected Kraus steps, QAP and assignment-type constrained ansatzes with terminal symmetry verification, block-encoded non-unitary basis transforms with small singular values, imaginary-time thermal-state preparation for the transverse-field Ising model, and repeat-until-success state preparation. We will also include tasks where no exponent-changing rewrite is known, so we can measure false claims.

Baselines

The do-nothing reference is the naive post-selected program run through Qiskit transpile at optimization level 3. This shows how much of the cost standard compilation already recovers. We expect it to shorten depth but leave $P_{\text{succ}}$ essentially untouched, since gate cancellation and routing do not change which measurement outcomes are kept.

The generic-wrapper baseline applies amplitude amplification to every terminal post-selection where the circuit is coherent. This is a purely mechanical transformation that turns $1/P_{\text{succ}}$ repetitions into roughly $1/\sqrt{P_{\text{succ}}}$ deeper circuits. It is scored on the same $C(n)$, including its added depth. Beating it requires a lower fitted exponent of $C(n)$ on held-out sizes, not just a better constant at one size.

The strongest existing method is the QVR post-trained model (Quantum Verifiable Rewards), which reports 28.48% on QHE-hard. We use it two ways. First, one-shot, prompted with the naive program and asked to reduce discard overhead. Second, as the generator inside a best-of-N scheme: it draws as many samples as our loop spends in generator calls, filters them through the same equivalence checker, and keeps the lowest-cost survivor. Best-of-N gets the same token budget and the same number of simulator calls as our loop. There is no reported result found on Lacuna for any method on post-selection overhead of generated code. On functional correctness, the bar is the 28.48% QHE-hard figure. Our loop must not fall below what the same generator achieves one-shot on QHE-hard, as a check that optimizing for discard cost does not damage basic coding.

The correctness-only refinement loop is identical to ours, with rollback and the same iteration budget, but receives only test and traceback feedback. Its output is then scored on $C(n)$. This shows whether ordinary refinement reduces overhead as a side effect.

The key ablation replaces the localized profile with a single scalar success probability at the largest training size, keeping everything else fixed. A second ablation removes rollback. The proposal's central claim stands or falls on the localized-versus-scalar comparison: if scalar feedback matches localized feedback on exponent reduction, the profiler design is not the contribution.

Why not just…?

Why not just sample many programs and keep the cheapest one that passes? This is the most serious threat, and it is why best-of-N is matched on budget. If a model sometimes writes the low-overhead version unprompted, selection alone will find it. The quantum code literature suggests this is rare for structurally hard rewrites: one-shot generation fails outright on difficult QHE tasks (Qiskit HumanEval), and the deterministic constructions we target took dedicated papers to derive. Still, this is an empirical question. If best-of-N matches the loop on exponent reduction, we will report that the gain comes from the cost-aware selector and checker, not from iteration, and reframe the contribution around those two pieces.

Why not just wrap every post-selection in amplitude amplification? It is general and provably helps, but it only halves the exponent. It also needs a coherent, invertible preparation circuit, which excludes programs that already use mid-circuit measurement. The AKLT feedforward protocol reaches constant-time scaling (Efficient preparation of the AKLT State), which amplification cannot. We include amplification as a tool the agent may call. On tasks without exploitable structure, we expect the agent's best answer to be amplification itself, and we will report those tasks honestly as ties.

Why not just fine-tune with a shot-cost reward instead of refining at inference time? This is a reasonable next step, and the profiler and checker built here are exactly the reward model it would need. But reward design must come first: QVR's binary reward ignores discard cost, and a scalar cost reward is the same signal our scalar ablation tests. If localized feedback beats scalar feedback at inference time, that is evidence for what a training reward should contain. MEIC's comparison, where an iterative workflow reached a 78% functional fix rate versus 66% for fine-tuning/RAG (MEIC), suggests inference-time loops are competitive in a neighbouring domain, but that result does not transfer automatically.

Why not just tune truncation thresholds by grid search? For tasks whose only lever is a scalar such as the $\varepsilon$ cutoff in Zhu et al., grid search over $C(n)$ subject to fidelity is the right tool, and the loop should not beat it. We run grid search on those tasks and count matching it as success. The loop's claim applies only to tasks that need program restructuring.

Decisive Checks

The main result is the fitted decay rate of $C(n)$ on held-out sizes, for each task and method. Together with the fraction of tasks where the loop lowers the exponent beyond what amplitude amplification achieves, while keeping $F \ge F_0$ and passing the equivalence checker, this reported across the loop and every baseline under identical budgets settles the question. The proposal succeeds if the loop beats best-of-N and the scalar-feedback ablation on that fraction, and recovers the published expert construction on a meaningful share of the AKLT, Lindblad and constrained-ansatz tasks.

It fails clearly if best-of-N matches it. It is also falsified if its gains vanish at held-out sizes, which would mean it tuned constants rather than finding structure. A third failure mode is claiming exponent reductions on the no-known-structure tasks that the exact simulator refutes. For the checker, we report its false-acceptance rate on corrupted programs. Any loop improvement achieved by programs the checker wrongly accepted is subtracted from the headline numbers.