Partial evaluation: ResourceManager::allocate_qubit is O(n) per call, making static qubit allocation O(n^2) #3959

Summary

When compiling to QIR with static qubit management (for example the Adaptive profile), ResourceManager::allocate_qubit makes two scans that both start at index 0 on every call. If many qubits are live at the same time, allocating n qubits costs O(n²). For programs with tens of thousands of qubits, this can dominate compile time.

Details

allocate_qubit (in source/compiler/qsc_partial_eval/src/management.rs) does the following when no delayed-release qubit is available:

1. Finds a free internal slot with a linear scan from the start:

   self.qubits_in_use.iter().position(|in_use| !in_use)

   If no qubit has been released, every entry is true, so the scan reads all k existing entries before pushing a new one.

2. Finds the lowest unused external ID, also starting from 0:

   let mut next_id = 0;
   loop {
       if !self.qubit_id_map.contains_key(next_id) { /* insert */ break; }
       next_id += 1;
   }

   IndexMap::contains_key is O(1), since it indexes a Vec<Option<V>>. The problem is the number of lookups: allocation k checks IDs 0..k before finding a free one.

When n qubits are live at once and none are released, the total work is about 2 × (0 + 1 + … + (n−1)) ≈ n² checks. For n = 30,000 that's roughly 900 million checks.

Observed impact

A ripple-carry adder over two 10,000-bit registers plus a 10,000-qubit carry register (30,000 live qubits), compiled with Profile::Adaptive in a debug test build:

The generated QIR is small: about 100 lines, the loop is kept as a loop, and the helpers are emitted as functions. That means the time isn't spent on code size or loop unrolling. The allocation pattern above is the main suspect.

Note: the link between the 11.65 s and allocate_qubit comes from reading the code and estimating the cost, not from a profiler run inside partial evaluation. Profiling or benchmarking allocate_qubit on its own would confirm how much of that time it accounts for.

Repro (minimal, expected)

I haven't run this snippet on its own. It's the allocation pattern from the adder case:

operation Main() : Unit {
    use a = Qubit[10000];
    use b = Qubit[10000];
    use c = Qubit[10000];
    // apply some gates so allocations are not optimized away
    for i in 0..9999 { CNOT(a[i], b[i]); CNOT(b[i], c[i]); }
}

Compile to QIR with the Adaptive profile and time partial evaluation. Doubling the register sizes should roughly quadruple the partial-evaluation time.

Suggested fix

Replace the scans from 0 with amortized O(1) or O(log n) structures, keeping the current "reuse the lowest available ID" behaviour:

• Internal slots: keep a min-heap or BTreeSet of freed slot indices. If it's empty, push a new slot (qubits_in_use.len()).
• External IDs: keep a min-heap or BTreeSet of freed IDs plus a next_fresh_id counter. Take the smallest freed ID if there is one, otherwise use next_fresh_id and increment it.
• Update free_qubit_id to add the released slot and ID back into those sets.
• Leave the delayed-release path (DelayedQubitReleaseStack) as it is.

With these changes, allocating n qubits costs O(n log n) in the worst case, and O(n) when nothing is freed.

Acceptance criteria

• Compiled QIR is identical to today's, including qubit ID assignment.
• Existing qsc_partial_eval and codegen tests pass.
• Partial-evaluation time for the 30,000-qubit case grows roughly linearly with qubit count.

I named the delayed-release path and the "lowest available ID" behaviour explicitly so the fix won't change qubit numbering in generated QIR.