Adaptive Profile QIR generation

[cesarzc]

The work to generate QIR that is compliant with the Adaptive Profile specification can be divided into a few major categories.

Runtime Capabilities Analysis (RCA)

RCA is the process of determining the capabilities a quantum kernel needs to be able to run a particular program. RCA also identifies program elements that can be pre-computed before execution on a quantum kernel and does not consider these elements when determining the capabilities.

• Detailed analysis for most of the Q# language (Implement Runtime Capabilities Analysis (RCA) #1164).
• Set dynamic qubits value kind as dynamic (Mark qubit value kind as dynamic when allocated within a dynamic scope #1304).

Runtime Capabilities Check Pass

Once RCA has identified the capabilities needed to run a particular program, it can be used to check whether the program can run on a particular target, and if not, provide compile-time feedback to the user about why.

• Implement runtime capabilities check pass (Runtime capabilities check pass #1291).
• Type of the entry expression should be part of the check (Include return type of entry point in RCA check #1417).
• Full support for partial eval of closures with captures (Support closures in RCA #1498)
• Disallow dynamic exponential operations (if possible only when the exponential is dynamic) (RCA check for use of dynamic rhs in exponent binop #1539)

Partial Evaluation

Partial evaluation is the process of generating a residual program by evaluating all purely classical computations. It starts with an entry expression for a program in the Flattened Intermediate Representation (FIR), uses RCA to identify purely classical computations and produces a program in the Residualized Intermediate Representation (RIR).

• Design the RIR data structure (Residualized Intermediate Representation (RIR) #1292).
• Implement partial evaluation.
  • Support custom backend to verify no quantum operations are simulated (Implement defaults for all functions in the Backend trait #1332).
  • Support for intrinsic unitary operations with classical arguments (Partial evaluation of intrinsic unitary operations with classical arguments #1334).
  • Support for proper qubit and measurement results management, including optimal qubit allocation (Partial evaluation qubits and results management #1367).
  • Set qubit and result counts in output program (Set qubit and result counts in partial eval output #1383).
  • Output recording (Partial Evaluation Output Recording support #1387).
  • Runtime failure for Result literals in output (Fail partial eval with error on Result literals #1409).
  • Full support for non-intrinsic function/operation calls (Partial evaluation support for calls with arguments #1386).
  • Support for controlled functors (Support for the Controlled functor in partial evaluation #1452).
  • Support loop unrolling (Partial evaluation support for loop unrolling #1378).
  • Support basic branching based on measurement results. i.e. calls to unitary operations inside branches (Partial evaluation support for branching #1376).
  • Support for hybrid return expressions (Partial evaluation support for return expressions #1421).
  • Support for assignment, array repeat, array in-place concatenation, array in-place update of value at index, and array access to value at index (Partial evaluation support for assignment expressions and multiple array related expressions #1480).
  • Support for dynamic binary operations and dynamic assign binary operations on Booleans and integers (except LHS dynamic Boolean and exponentiation) (Partial evaluation support for binary operations #1499).
  • Support LHS dynamic Booleans (Partial evaluation support for hybrid Boolean operations with a dynamic LHS expression #1540).
  • Support exponentiation (Partial evaluation support for exponentiation #1541).
  • Support for unary operations (Partial evaluation support for unary operator expressions #1485).
  • Support array slicing via ranges in index expressions (Partial evaluation support for array slicing #1546).
  • Make early returns raise an Unimplemented error (Switch early return to Unimplemented in Partial Eval #1544).
  • Perform eval-time RCA check for previously unresolved callables (Check unresolved callables during partial eval #1497)

RIR Transformation Passes

Some patterns might require enough complexity to eliminate or transform that they are better separated into RIR -> RIR transformation passes. This allows both the Partial Evaluation that precedes this step and the QIR Generation that follows to remain focused on their specific complexities.

• Disallow branching on literal by changing RIR structure (Disallow branching on literal in RIR #1360)
• Defer Measurements pass (RIR defer measurements and unreachable code passes #1319)
• Unreachable code pass (RIR defer measurements and unreachable code passes #1319)
• Qubit Reindex on Reuse pass (RIR qubit reindex pass #1342)
• SSA pass (aka mem2reg)
  • Remap block identifiers to be ordered by control flow graph (RIR remap block id pass #1353)
  • Replace all but final Store instructions within block with SSA (RIR SSA transformation pass #1363)
  • Calculate dominator tree for blocks (RIR dominator graph pass #1354)
  • Replace remaining Store instructions with Phi instructions in later blocks (RIR SSA transformation pass #1363)
  • Validation pass that ensures SSA values correctly dominate usage (RIR SSA check pass #1358)
• Move passes into RIR crate (Move RIR passes to qsc_rir #1341)
• Type consistency pass (Add RIR type check pass #1397)
• Block optimization pass that eliminates trivial jumps (blocks with only one successor, where that successor has only one predecessor) (RIR simplify control flow pass #1407)

QIR Generation

Once the compiler has performed partial evaluation and transformed the program into RIR, the compiler uses it as input to the code generation step, which produces specification-compliant QIR in text form.

• Support "straight-line" code, effectively base profile, where only void function calls are expected. (Support Base Profile RIR to QIR #1305)
• Support mid-circuit measurement with branching based on measurement results but not arbitrary mutable Booleans. (Codegen for basic branching on measurement #1311)
• Support codegen of Phi nodes. (QIR Codegen for Instructions #1337)
• Support codegen of integer arithmetic operations. (QIR Codegen for Instructions #1337)
• Support codegen of Boolean operations and comparisons. (QIR Codegen for Instructions #1337)
• Support codegen of bitshift operations. (QIR Codegen for Instructions #1337)

Integration

As the other four major pieces are completed, they can start being integrated into the rest of the QDK.

• Create feature flag for Adaptive Profile QIR generation. (Initial integration of RCA, preview QIR gen, and adaptive profile #1347)
• Extend target configuration to support more than just Unrestricted and Base. (Initial integration of RCA, preview QIR gen, and adaptive profile #1347)
  • Support for VSCode. (Initial integration of RCA, preview QIR gen, and adaptive profile #1347)
  • Support for Python. (Initial integration of RCA, preview QIR gen, and adaptive profile #1347)
• Integrate the runtime capabilities check pass into the language service.
  • OpenProject (Initial integration of RCA, preview QIR gen, and adaptive profile #1347)
  • Notebook (Run profile analysis in language service for notebooks #1373)
• Integrate Adaptive Profile QIR generation into the incremental compiler.
  • Wire everything together. (Initial integration of RCA, preview QIR gen, and adaptive profile #1347)
  • Implement code generation
    • OpenProject (Using new QIR codegen for adaptive profile in Rust/Python #1375)
    • Notebook (Using new QIR codegen for adaptive profile in Rust/Python #1375)
    • Python (Using new QIR codegen for adaptive profile in Rust/Python #1375)
• Unify QIR generation paths (Use new QIR gen API for Base Profile #1400)
• Replace base profile check pass with RCA. (Use RCA based code generation for all scenarios #1523)

End-to-end Testing

• Test correctness of program execution on QIR targets

Release

• Remove feature toggles (Use RCA based code generation for all scenarios #1523)
• Enable Python Base profile code generation (Use RCA based code generation for all scenarios #1523)

Related Items

• Extend Runtime Capabilities Analysis (RCA) to support more advanced scenarios #1306
• Adaptive Profile QIR Generation Post Release #1414
• QIR Specification Compliance #1433
• User experience improvements for QIR generation #1529