ADR: Intent-First Algorithms (Intent/Plan/Execute), Not Gate-Lingua-Franca

Status: Accepted

Date: 2025-12-17

What This Means For Library Users

If you are just using FSharp.Azure.Quantum (F# or C#), this ADR is mainly about making algorithms run correctly across very different backends (state-vector simulators, Azure Quantum providers, and future topological/Majorana-style backends).

Practical impact:

If you need to reason about backend support, use the existing capability probes (IQuantumBackend.SupportsOperation, NativeStateType), and prefer algorithm APIs that expose explicit configuration for exactness/approximation where available.

Context

This repository already provides a unified execution surface via IQuantumBackend (ExecuteToState, ApplyOperation, InitializeState, NativeStateType, SupportsOperation). This enables writing algorithms once and running them on multiple backends.

However, several “generic” algorithms and solvers still encode algorithm intent primarily as gate sequences (QuantumOperation.Gate ...). In practice, this makes the gate model the lingua franca, and forces non-gate-native backends to translate gates into their native model.

This is risky because:

We expect Microsoft’s future Majorana platform to be a topological quantum computer, and Azure Quantum includes annealing providers. A robust unified model must allow running workloads across these paradigms without requiring “gate-first” translation as the definition of correctness.

Decision

Algorithms and solvers must be expressed as “intent” first, using Algebraic Data Types (F# discriminated unions and records), and only lowered to gates/braids as an explicit execution strategy.

Principles

  1. Intent is canonical
    • Algorithm meaning is captured by DUs/records.
    • A gate-level decomposition is a strategy artifact.
  2. Execution is planned
    • Execution uses a planning step: intent → plan → execution.
    • Plans are explicit about which strategy is chosen.
  3. No silent fallback to gates
    • If an algorithm cannot be executed natively and a lowering is not valid/available, it must fail with a clear error (not silently “do something gate-shaped”).
  4. Correctness is explicit
    • Plans/results must be explicit about exactness vs approximation.
  5. Interfaces are optional and justified
    • Prefer DUs and pattern matching.
    • Use interfaces only as an “open-world plugin point” (e.g., external provider packages) when we cannot depend on concrete backend types.

Each algorithm module (e.g., Grover, QFT, later Shor) should define:

1) Intent DU

A DU expressing what the algorithm step means.

Example (illustrative):

type QftIntent =
    { Qubits: int list
      Inverse: bool
      ApplySwaps: bool }

type QftStep =
    | ApplyQft of QftIntent
    | ApplyControlledPhase of control:int * target:int * angle:float
    | ApplySwap of a:int * b:int

2) Plan DU

A DU expressing how we will execute the intent on a specific backend.

type Exactness =
    | Exact
    | Approximate of epsilon: float

type QftPlan =
    | ExecuteNatively of exactness: Exactness
    | ExecuteViaOps of ops: BackendAbstraction.QuantumOperation list * exactness: Exactness

3) Planner + Executor

The algorithm entrypoints (execute, executeOnState, etc.) should:

  1. Build intent (QftStep list) from configuration.
  2. Plan against the backend.
  3. Execute the chosen plan.

Relating Intent to IQuantumBackend

IQuantumBackend remains the unified execution surface. Intent planning should use these signals:

Lowering outputs must target existing QuantumOperation where possible:

When Interfaces Are Acceptable

By default, intent execution should use DUs and pattern matching on:

Interfaces may be used when we need open-world extensibility, e.g.:

If interfaces are used, they should be:

Testing & Correctness Contract

Tests should be written to reflect this:

Current Status (Implemented In Repo)

The intent-first pattern described here is already implemented in several core algorithms.

Follow-Ups (Optional Improvements)

Consequences

Pros

Cons

Notes