RFC: Qubit Lifetime & Deallocation Semantics in QC/QCO

[simon1hofmann]

Based on comments and discussion in #1569:

🧩 Problem Statement

We need a consistent and implementable model for:

• Qubit allocation and deallocation
• Interaction between:
  • QC (higher-level IR)
  • QCO (lower-level IR)
• Handling of:
  • static vs dynamic qubits
  • control flow
  • aggregates (tensors/lists)

Key challenge:

Ensuring correct deallocation in the presence of control flow and data structures without introducing excessive complexity (e.g., reference counting or garbage collection).

🎯 Goals

• Maintain correctness guarantees (no leaks, no double frees)
• Keep lowering simple and predictable
• Avoid:
  • global program analysis
  • alias tracking
  • runtime reference counting

❌ Non-Goals

• Supporting all possible user-written programs
• Emulating classical memory models (e.g., arbitrary aliasing)
• Introducing quantum garbage collection

🔍 Observations from Existing Frameworks

• High-level frameworks (Qiskit, PennyLane):
  • avoid deallocation entirely
• QIR:
  • uses explicit allocation/deallocation
  • does not enforce correctness structurally
• Linear IRs (MLIR-based, Guppy-style):
  • enforce ownership and linear usage
  • restrict ambiguous programs

Conclusion:

Systems that guarantee correctness structurally restrict expressiveness.

💡 Proposal

1. Unified Deallocation in QCO

• Every qubit (static or dynamic) must be explicitly consumed

• Introduce:

  qco.sink %q : qubit
  

  (or keep qco.dealloc)

Semantics:

• Consumes the qubit
• Marks end of lifetime

2. QC lifetime model (static vs dynamic mode)

• QC(static): No qc.dealloc. Static qubits are not explicitly deallocated.
• QC(dynamic): Explicit qc.dealloc is required for dynamically allocated qubits (and registers).

Lowering rules:

• QC(dynamic) → QCO: qc.dealloc → qco.sink
• QC(static) → QCO: insert qco.sink at end-of-scope for all static qubits introduced/used in that scope (or equivalently, for all qubits not returned)
• QCO → QC(dynamic): qco.sink → qc.dealloc
• QCO → QC(static): drop qco.sink

3. Linear Ownership Model

• Qubits are:
  • SSA values
  • must be consumed exactly once
• Control flow:
  • must preserve linearity via structured regions (yield)

4. Restrictions on Aggregates (Critical)

To ensure correctness, the following are invalid IR:

❌ Mixed ownership in aggregates

[p, q]  // where p is borrowed, q is owned

5. Valid Patterns

✅ Structured control flow

if cond:
  return p
else:
  return q

✅ Uniform aggregates

[q1, q2, q3]  // all owned

⚖️ Alternatives Considered

A. Always deallocate everything without restrictions

• ❌ Fails for dynamic indexing
• ❌ Requires alias tracking

B. Reference counting / GC

• ❌ Complex
• ❌ Unnecessary with linear types

C. Separate static/dynamic types

• ⚠️ Improves clarity
• ❌ Complicates lowering and transformations

🧠 Rationale

The proposed design:

• Aligns with:
  • MLIR principles
  • linear type systems
• Avoids:
  • global analysis
  • runtime mechanisms
• Keeps:
  • lowering simple
  • semantics explicit

🚧 Open Questions

• Naming:
  • dealloc vs sink
• Extent of aggregate restrictions:
  • enforce via verifier?
  • or rely on frontend guarantees?

✅ Decision

Adopt:

• Explicit consumption in QCO
• Implicit lifetime in QC
• Strict linear ownership with IR restrictions

📌 Consequences

Pros

• Simple lowering
• Strong correctness guarantees
• No GC or alias analysis needed

Cons

• Reduced expressiveness
• Some programs become invalid IR

🔮 Future Work

• Formal verifier for ownership constraints
• Documentation for frontend authors
• Exploration of safe aggregate abstractions

[denialhaag]

One observation from working on the QC-to-QIR conversion: QIR 2.1 now supports dynamic and static allocations. However, the spec reads to me as if dynamic and static allocations should not be mixed. When dynamic_qubit_management is set to true, required_num_qubits (i.e., static qubits) is not really supposed to be used: https://github.com/qir-alliance/qir-spec/blob/main/specification/Memory_Management.md#enabling-dynamic-memory-management

[burgholzer]

Yeah, QIR treats these as mutually exclusive.
And from the discussions in #1569, I think we should too.
There is a well-defined transition from dynamic to static qubits as part of placement and routing.

This is something that we can also easily verify.

[burgholzer]

To pick up on the thought from above: If we do not allow programs that mix static and dynamic qubits, then we also do not need to treat deallocs implicitly in QC.

• If a QC program only uses dynamic qubits, every qubit or register needs to be deallocated; upon conversion to QCO, every single dealloc gets replaced with a qco.sink.
• If a QC program only uses static qubits, no deallocation is necessary; upon conversion to QCO, qco.sink operations are added for each qubit at the end of the scope where they are allocated.
• Conversion from dynamic to static happens in QCO (in most cases as part of placement-and-routing). Since QCO programs have sinks for all qubits already, this should be as simple as it is today in the code.
• A QCO program using dynamic qubits is converted back by replacing qco.sink with qc.dealloc.
• A QCO program using static qubits is converted back by dropping qco.sink operations.

[DRovara]

That sounds reasonable to me. I can't think of a single reason, why static and dynamic qubits have to be mixed (considering static qubits will likely only be placed by compilers that have the goal of eliminating all dynamic qubits anyways).

In that case, the handling as you suggest it sounds reasonable and pretty efficient.

[DRovara]

Thanks for the RFC, sounds pretty good to me. Just some minor notes on the text itself:

1. Section 2 in "Proposal" says there is no explicit dellocation in QC. I don't think that's quite compatible with our discussions (and, in fact, the note on QCO -> QC translation in that section says the sinks can be removed if desired (implying there is a way to keep them in). This just doesn't sound super clear.

2. Section 4 is a bit confusing. It says things like "Dynamic indexing with ambiguous ownership" is forbidden if elements differ, while just the point above said having different ownerships in aggregates is not allowed at all. Maybe I'm also just missing a distinction here, though.

[simon1hofmann]

Thanks a lot for the review, I updated Section 2:

2. QC lifetime model (static vs dynamic mode)

• QC(static): No qc.dealloc. Static qubits are not explicitly deallocated.
• QC(dynamic): Explicit qc.dealloc is required for dynamically allocated qubits (and registers).

Lowering rules:

• QC(dynamic) → QCO: qc.dealloc → qco.sink
• QC(static) → QCO: insert qco.sink at end-of-scope for all static qubits introduced/used in that scope (or equivalently, for all qubits not returned)
• QCO → QC(dynamic): qco.sink → qc.dealloc
• QCO → QC(static): drop qco.sink

and Section 4:

• removed the points ❌ Dynamic indexing with ambiguous ownership and ❌ Permutations that lose provenance as they are already excluded if ambiguous ownership is forbidden.

[burgholzer]

This has now been implemented in #1569 🎉