Decompositions

DecompositionBasis

Abstract type for decomposition targets that define a set of terminal operations and how to decompose non-terminal operations.

A DecompositionBasis combines two concerns:

1. What is terminal: Operations that should not be decomposed further.
2. How to decompose: The transformation logic for non-terminal operations.

Interface

Subtypes must implement:

• isterminal(basis, op): Return true if op is in the target set.
• decompose!(builder, basis, op, qtargets, ctargets, ztargets): Append decomposed instructions to builder for non-terminal operations.

Examples

struct CliffordT <: DecompositionBasis end

# Define terminal operations
isterminal(::CliffordT, ::GateH) = true
isterminal(::CliffordT, ::GateS) = true
isterminal(::CliffordT, ::GateT) = true
isterminal(::CliffordT, ::GateCX) = true
isterminal(::CliffordT, ::Operation) = false

# Define decomposition (can delegate to rewrite rules)
function decompose!(builder, ::CliffordT, op::Operation, qt, ct, zt)
    return decompose_step!(builder, CanonicalRewrite(), op, qt, ct, zt)
end

See also CanonicalBasis, RewriteRule, decompose.

decompose_step!(builder, rule::RewriteRule, op::Operation, qtargets, ctargets, ztargets)

Apply rule to transform op and append the resulting instructions to builder.

This is the low-level interface that each RewriteRule must implement for operations it matches.

Arguments

• builder: A circuit-like container (e.g., Circuit, Vector{Instruction}) to append to.
• rule: The rewrite rule to apply.
• op: The operation to transform.
• qtargets: Qubit indices for the operation.
• ctargets: Classical bit indices for the operation.
• ztargets: Z-variable indices for the operation.

Returns

The builder with decomposed instructions appended.

See also RewriteRule, matches, decompose_step.

matches(rule::RewriteRule, op::Operation) -> Bool

Return true if rule can transform operation op.

This is used to check whether a rewrite rule is applicable before attempting decomposition.

Examples

matches(CanonicalRewrite(), GateH())  # true if CanonicalRewrite handles GateH

See also RewriteRule, decompose_step!.

decompose!(circuit, source; basis=CanonicalBasis(), wrap=false)

Recursively decompose source to the given basis and append results to circuit. The basis argument can be a DecompositionBasis or a RewriteRule.

decompose!(circuit, basis, op, qtargets, ctargets, ztargets)

Low-level interface for defining how an OperationBasis decomposes a specific operation. Implement this method to customize decomposition behavior for your basis.

See also decompose, isterminal.

decompose(source; basis=CanonicalBasis(), wrap=false)::Circuit

Recursively decompose source until all operations are terminal in the given basis.

The basis argument can be a DecompositionBasis or a RewriteRule. If a rewrite rule is provided, it is applied recursively.

If wrap=true, non-terminal operations will be wrapped into GateDecl or Block containing their decomposition. Identical operations will share the same GateDecl.

Examples

# Decompose to primitive operations (CX, U, Measure, Reset, ...)
decompose(circuit)

# Decompose to Clifford+T
decompose(circuit; basis=CliffordT())

# Keep structure with wrapped declarations
decompose(circuit; wrap=true)

See also decompose!, decompose_step, eachdecomposed.

eachdecomposed(source; basis=CanonicalBasis(), wrap=false, cache=nothing)

Return an iterator over instructions resulting from decomposing source to the given basis. The basis can be a DecompositionBasis or RewriteRule.

This is memory-efficient for large circuits as it doesn't materialize the full decomposed circuit at once.

If wrap=true, non-terminal operations will be wrapped into GateDecl or Block containing their decomposition, rather than being flattened.

If cache is provided (a Dict{Operation,GateDecl}), wrapped GateDecls will be cached and reused when the same operation is encountered again.

Examples

for inst in eachdecomposed(circuit)
    # process each primitive instruction
end

# Collect into a vector
insts = collect(eachdecomposed(circuit))

See also decompose, DecomposeIterator.

decompose_step(operation; rule=CanonicalRewrite())::Circuit
decompose_step(instruction; rule=CanonicalRewrite())::Circuit
decompose_step(circuit; rule=CanonicalRewrite())::Circuit

decompose_step(instructions; rule=CanonicalRewrite())::Vector{Instruction}

Perform a single step of decomposition for the given object.

Returns a Circuit or Vector{Instruction} containing the decomposed instructions.

Unlike decompose, this function acts non-recursively and treats blocks or other container-like operations as opaque.

decompose_step!(container, operation; rule=CanonicalRewrite())
decompose_step!(container, instruction; rule=CanonicalRewrite())
decompose_step!(container, circuit; rule=CanonicalRewrite())

Perform a single step of decomposition for the given object and appending the result to container.

decompose_step!(builder, rule, op, qtargets, ctargets, ztargets)

Is the low-level interface that must be implemented by rewrite rules.

Unlike decompose, this function acts non-recursively and treats blocks or other container-like operations as opaque.

See also decompose_step.

CanonicalBasis <: DecompositionBasis

The canonical basis decomposes all operations to a minimal set of primitives: GateU, GateCX, Measure, Reset, and other irreducible operations.

This is the default basis used by decompose.

Examples

decompose(circuit) # uses CanonicalBasis() by default
decompose(circuit; basis=CanonicalBasis())

See also DecompositionBasis, CanonicalRewrite.

CliffordTBasis <: DecompositionBasis

Decomposition basis targeting the Clifford+T universal gate set.

The Clifford+T gate set is fault-tolerant and widely used in error-corrected quantum computing. It consists of:

• Single-qubit Clifford: H, S, S†, X, Y, Z, SX, SX†, SY, SY†
• T gates: T, T† (the non-Clifford gates enabling universality)
• Two-qubit Clifford: CX (CNOT), CY, CZ, SWAP, iSWAP

Decomposition Pipeline

The basis applies rewrite rules in the following priority order:

1. SpecialAngleRewrite: Rotations with angles k·π/4 → exact Clifford+T
2. ToffoliToCliffordTRewrite: CCX → 7 T gates + Cliffords
3. ControlledPhaseToCliffordTRewrite: CP, CRZ → Clifford+T
4. SwapToCliffotdRewrite: SWAP → 3 CNOTs
5. ZYZRewrite: GateU → RZ·RY·RZ
6. ToZRotationRewrite: RX, RY → RZ + Cliffords
7. SolovayKitaevRewrite: Arbitrary RZ → approximate Clifford+T
8. CanonicalRewrite: Fallback for other gates

Examples

# Decompose to Clifford+T
decompose(circuit; basis=CliffordTBasis())

# Check T-count after decomposition
decomposed = decompose(circuit; basis=CliffordTBasis())
t_count = count(inst -> getoperation(inst) isa Union{GateT, GateTDG}, decomposed)

Performance Notes

• Exact decompositions (SpecialAngleRewrite) are preferred when applicable
• Solovay-Kitaev is only used as a last resort for arbitrary angles
• T-count optimization is not performed; use a dedicated pass for that

See also DecompositionBasis, CanonicalBasis.

QASMBasis <: DecompositionBasis

Decomposition basis targeting the OpenQASM 2.0 gate library.

This basis includes all gates defined in qelib1.inc (the standard QASM 2.0 library) plus common extensions, making it suitable for exporting circuits to QASM format or running on QASM-compatible backends.

Terminal Operations

The following gate categories are terminal (not decomposed further):

Fundamental gates (OpenQASM 2.0 built-in):

• GateU, GateCX — the universal basis for QASM 2.0

Single-qubit gates from qelib1.inc:

• Legacy U gates: GateU3, GateU2, GateU1
• Pauli: GateID, GateX, GateY, GateZ
• Hadamard: GateH
• Phase: GateS, GateSDG, GateT, GateTDG
• Rotations: GateRX, GateRY, GateRZ

Two-qubit gates from qelib1.inc:

• Controlled Paulis: GateCY, GateCZ
• Controlled Hadamard: GateCH
• Swap family: GateSWAP
• Controlled rotations: GateCRX, GateCRY, GateCRZ
• Ising coupling: GateRXX, GateRZZ

Three-qubit gates from qelib1.inc:

• GateCCX (Toffoli), GateCSWAP (Fredkin)

Four-qubit gates from qelib1.inc:

• GateC3X

Non-unitary operations:

• Measure, Reset, Barrier
• IfStatement (if inner operation is terminal)

Oher operations:

• GateCall (custom gate invocations)

Examples

# Decompose to QASM-compatible gates
decompose(circuit; basis=QASMBasis())

# Export to OpenQASM 2.0
qasm_circuit = decompose(circuit; basis=QASMBasis())
saveqasm(qasm_circuit, "output.qasm")

See also DecompositionBasis, CanonicalBasis, CliffordTBasis.

StimBasis <: DecompositionBasis

Decomposition basis targeting the Stim stabilizer simulator gate set.

Stim is a high-performance stabilizer circuit simulator by Craig Gidney. It supports only Clifford gates, stabilizer operations, noise channels, and quantum error correction annotations.

Decomposition Pipeline

The basis applies rewrite rules to decompose gates into Clifford operations:

1. ZYZRewrite: GateU → RZ·RY·RZ Euler decomposition
2. SpecialAngleRewrite (Clifford-only): Rotations at k·π/2 → exact Clifford gates
3. CanonicalRewrite: Fallback for other gates

Non-Clifford rotations (angles not multiples of π/2) are explicitly rejected with a clear error message.

Terminal Operations

Single-qubit Clifford gates:

• Pauli: GateID, GateX, GateY, GateZ
• Hadamard: GateH
• Phase: GateS, GateSDG
• √X: GateSX, GateSXDG
• √Y: GateSY, GateSYDG

Two-qubit Clifford gates:

• Controlled Paulis: GateCX, GateCY, GateCZ
• Swap: GateSWAP, GateISWAP, GateISWAPDG
• Double CX: GateDCX
• ECR: GateECR

Measurements:

• Z-basis: Measure
• X-basis: MeasureX
• Y-basis: MeasureY

Resets:

• Z-basis: Reset
• X-basis: ResetX
• Y-basis: ResetY

Measure-and-reset:

• Z-basis: MeasureReset
• X-basis: MeasureResetX
• Y-basis: MeasureResetY

Noise channels:

• Pauli errors: PauliX, PauliY, PauliZ
• Depolarizing: Depolarizing1, Depolarizing2

QEC annotations:

• Detector, ObservableInclude, QubitCoordinates
• Barrier

Stim Gate Mapping

Examples

# Decompose Clifford circuit to Stim-compatible gates
decompose(circuit; basis=StimBasis())

# This works (RZ(π/2) = S is Clifford)
decompose(GateRZ(π/2); basis=StimBasis())

# This fails (RZ(π/4) = T is non-Clifford)
decompose(GateRZ(π/4); basis=StimBasis())  # throws DecompositionError

# This also fails (arbitrary angle)
decompose(GateRZ(0.123); basis=StimBasis())  # throws DecompositionError

See also DecompositionBasis, CliffordTBasis, QASMBasis.

CanonicalRewrite

Canonical rewrite rules for the MIMIQ framework.

Built so that most operations are decomposed down to a basic set of gates (GateU and GateCX),

SolovayKitaevRewrite <: RewriteRule

Rewrite rule that approximates arbitrary single-qubit unitaries using the Solovay-Kitaev algorithm, producing a sequence of Clifford+T gates.

The algorithm recursively refines an initial approximation using group commutators, achieving ε-approximation with O(log^c(1/ε)) gates where c ≈ 3.97.

Parameters

• depth::Int: Recursion depth (default: 3). Higher depth = better precision but more gates.
• simplify::Bool: Whether to simplify the resulting gate sequence (default: true).
• basis_gates::Vector{AbstractGate}: The basis set to use (default: Clifford+T).
• net_max_depth::Int: Max depth for generating the initial epsilon-net (default: 15).
• net_max_points::Int: Max points in the epsilon-net (default: 100,000).
• net_min_dist::Float64: Minimum distance for epsilon-net points (default: 0.01).

Supported Operations

• GateRZ(λ) — Z-rotation by angle λ
• GateRY(θ) — Y-rotation by angle θ
• GateRX(θ) — X-rotation by angle θ
• GateU(θ, ϕ, λ, γ) — General single-qubit unitary

Symbolic parameters are not supported.

Output Gates

The decomposition produces gates from the provided basis_gates. For the default Clifford+T basis: GateH, GateS, GateSDG, GateT, GateTDG, GateX, GateY, GateZ.

Examples

# Default depth (3)
decompose_step(GateRZ(0.123); rule=SolovayKitaevRewrite())

# Higher precision, custom basis
decompose_step(GateRZ(0.123); rule=SolovayKitaevRewrite(5; basis_gates=[GateH(), GateT()]))

References

• Dawson & Nielsen, "The Solovay-Kitaev algorithm" (2005)
• Kitaev, Shen, Vyalyi, "Classical and Quantum Computation" (2002)

See also RewriteRule, SpecialAngleRewrite.

SpecialAngleRewrite <: RewriteRule

Rewrite rule that decomposes single-qubit rotations with special angles into explicit Clifford or Clifford+T gates.

This rule only matches rotations whose angle is a multiple of π/4 (or π/2 in Clifford-only mode). Generic rotations with arbitrary angles are not matched and should be handled by other rules (e.g., SolovayKitaevRewrite).

Constructor

SpecialAngleRewrite(; only_cliffords::Bool=false)

• only_cliffords=false (default): Match angles k·π/4, decompose to Clifford+T
• only_cliffords=true: Match only angles k·π/2, decompose to Clifford gates only

Supported Operations

When only_cliffords=true, only even values of k are matched (k=0,2,4,6), producing only Clifford gates (identity, S/SX/SY, Z/X/Y, S†/SX†/SY†).

Examples

# Default: Clifford+T decomposition
rule = SpecialAngleRewrite()
decompose_step(GateRZ(π/4); rule=rule)  # → T

# Clifford-only mode (for Stim compatibility)
rule_clifford = SpecialAngleRewrite(only_cliffords=true)
matches(rule_clifford, GateRZ(π/2))  # true  → S
matches(rule_clifford, GateRZ(π/4))  # false → not matched (T is non-Clifford)

# Generic rotation is not matched
matches(SpecialAngleRewrite(), GateRZ(0.123))  # false

See also RewriteRule, CliffordTBasis, StimBasis.

ToZRotationRewrite <: RewriteRule

Rewrite rule that converts GateRX and GateRY rotations into GateRZ conjugated by Clifford gates.

This is useful for backends that natively support only Z-rotations, or as a preprocessing step before applying SpecialAngleRewrite or SolovayKitaevRewrite.

Transformations

Examples

# RX becomes RZ conjugated by Hadamards
decompose_step(GateRX(θ); rule=ToZRotationRewrite())
# Result: H, RZ(θ), H

# RY requires additional S gates
decompose_step(GateRY(θ); rule=ToZRotationRewrite())
# Result: S, H, RZ(θ), H, Sdg

See also RewriteRule, SpecialAngleRewrite, ZYZRewrite.

ZYZRewrite <: RewriteRule

Rewrite rule that decomposes single-qubit unitaries into the ZYZ Euler angle decomposition: RZ(α) · RY(β) · RZ(γ).

This is a standard decomposition for arbitrary single-qubit gates, producing only Z and Y rotations (plus a global phase for GateU).

Transformations

Identity rotations (angle = 0) are omitted from the output.

Examples

# U gate decomposes to RZ-RY-RZ sequence
decompose_step(GateU(π/2, π/4, π/3); rule=ZYZRewrite())

# RX is converted via S conjugation
decompose_step(GateRX(θ); rule=ZYZRewrite())
# Result: S, RY(θ), Sdg

See also RewriteRule, ToZRotationRewrite, SpecialAngleRewrite.

FlattenedBasis <: DecompositionBasis

A basis that flattens all container operations (GateCall, Block, etc.) into their constituent instructions, while leaving all other operations (including all gates) untouched.

This is useful for analyzing the "flat" structure of a circuit without decomposing gates into a specific basis.

Examples

# Expand all nested blocks/calls
flat_circuit = decompose(circuit; basis=FlattenedBasis())

See also FlattenContainers.

FlattenContainers <: RewriteRule

A rewrite rule that flattens container operations (GateCall, Block, and their inverses) into their constituent instructions, without performing any gate-level decomposition.

This is useful for:

• Expanding user-defined gates while preserving primitive gate structure
• Preparing circuits for analysis or visualization at a specific abstraction level
• Step-by-step expansion of nested circuit structures

Examples

# Flatten one level of containers
flat = decompose_step(circuit; rule=FlattenContainers())

# Recursively flatten all containers (but keep gates intact)
fully_flat = decompose(circuit; basis=FlattenedBasis())

See also CanonicalRewrite, GateCall, Block.

RuleBasis{R<:RewriteRule} <: DecompositionBasis

A decomposition basis that recursively applies a single rewrite rule until no more matches are found.

This allows any RewriteRule to be used directly as a decomposition basis.

Examples

# Use a rewrite rule as a basis directly
decompose(circuit; basis=FlattenContainers())

# Or explicitly wrap it (equivalent)
decompose(circuit; basis=RuleBasis(FlattenContainers()))