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!.

DecomposeIterator(source, basis; wrap=false, cache=nothing)

An iterator that yields instructions from recursive decomposition of source to the given basis. Performs depth-first decomposition. The basis argument can be a DecompositionBasis or a RewriteRule.

If wrap=true, non-terminal operations are wrapped, rather than flattened, into a GateDecl (for gates) or a Block (for other operations, such as MeasureReset) holding their full decomposition. Gates inside a Block are wrapped as well.

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

See also eachdecomposed, decompose.

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 gates are wrapped into a GateDecl holding their decomposition, and identical gates share the same GateDecl. Other non-terminal operations, such as MeasureReset or MeasurePauli, are wrapped into a Block holding their decomposition, whose gates are wrapped in turn.

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 are wrapped, rather than flattened, into a GateDecl (for gates) or a Block (for other operations) holding their decomposition.

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(; rotations=GridSynthRewrite())
CliffordTBasis(; sk_depth)

Decomposition basis targeting the Clifford+T gate set.

Clifford+T is the standard universal gate set of error-corrected quantum computing. The terminal operations of this basis are those of StimBasis plus GateT and GateTDG, so the two bases always keep the same Clifford and stabilizer operations:

• single-qubit Cliffords: GateID, GateX, GateY, GateZ, GateH, GateHXY, GateHYZ, GateS, GateSDG, GateSX, GateSXDG, GateSY, GateSYDG;
• two-qubit Cliffords: GateCX, GateCY, GateCZ, GateSWAP, GateISWAP, GateISWAPDG, GateDCX, GateECR;
• Pauli rotations by ±π/2: GateRXX, GateRYY, GateRZZ, and RPauli with a non-identity Pauli string;
• the non-Clifford GateT and GateTDG;
• measurements, resets and measure-and-resets in the X, Y and Z bases, MeasureXX, MeasureYY, MeasureZZ and MeasurePauli;
• Pauli noise: PauliX, PauliY, PauliZ, Depolarizing1, Depolarizing2 and PauliNoise;
• barriers and annotations;
• classical operations, which StimBasis does not keep;
• an IfStatement whose body is terminal in this basis, with any condition. StimBasis only keeps a conditional GateX, GateY or GateZ on a single bit.

Decomposition Pipeline

Non-terminal operations are rewritten by the first rule that matches, in this order:

1. SpecialAngleRewrite: rotations by multiples of π/4 to exact Clifford+T.
2. ToffoliToCliffordTRewrite: GateCCX to Clifford+T with 7 T gates.
3. A GateU whose angles are all zero (a pure global phase) is dropped.
4. ZYZRewrite: GateU to RZ·RY·RZ.
5. ToZRotationRewrite: GateRX, GateRY to GateRZ and Cliffords.
6. The rotations rule (default GridSynthRewrite): remaining GateRZ to an approximate Clifford+T sequence.
7. CanonicalRewrite: any other operation, toward GateU and GateCX.

The rotations rule only sees angles that step 1 could not decompose exactly. The body of an IfStatement goes through the same pipeline and stays conditional. No T-count optimization is performed on the result.

Keyword Arguments

• rotations::RewriteRule: rule that synthesizes the remaining Z-rotations. The default GridSynthRewrite() approximates each rotation to operator-norm error 1e-10. The rule must match GateRZ with a numeric angle and emit only gates of this basis.
• sk_depth::Int: use SolovayKitaevRewrite with this recursion depth as the rotations rule.

Throws an ArgumentError if both keywords are given, or if rotations does not match GateRZ. Decomposing an operation that no rule handles, such as a noise channel other than the Pauli ones above, throws a DecompositionError.

Examples

# Decompose to Clifford+T; each arbitrary rotation is approximated to 1e-10
decompose(circuit; basis=CliffordTBasis())

# A looser error bound per rotation gives fewer T gates
decompose(circuit; basis=CliffordTBasis(rotations=GridSynthRewrite(epsilon=1e-6)))

# Solovay-Kitaev at depth 3 instead of gridsynth
decompose(circuit; basis=CliffordTBasis(sk_depth=3))

# Count the T gates of the result
decomposed = decompose(circuit; basis=CliffordTBasis())
t_count = count(inst -> getoperation(inst) isa Union{GateT, GateTDG}, decomposed)

See also DecompositionBasis, StimBasis, 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)

Other operations:

• GateCall (custom gate invocations)

MeasureReset decomposes into Measure followed by Reset. This leaves the same state and bit as its canonical decomposition, a measurement and a GateX conditioned on its outcome, and unlike that conditional it can be written for a circuit of any number of bits. OpenQASM 2.0 has no loops, so WhileStatement throws a DecompositionError.

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. A GateU whose angles are all zero (a pure global phase) is dropped.
2. ZYZRewrite: GateU → RZ·RY·RZ Euler decomposition
3. SpecialAngleRewrite (Clifford-only): Rotations at k·π/2 → exact Clifford gates
4. 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, GateHXY, GateHYZ
• 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

Pauli rotations by ±π/2:

• GateRXX, GateRYY, GateRZZ with angle ±π/2
• RPauli with angle ±π/2 and a non-identity Pauli string

Angles are compared modulo 2π, since a rotation by 3π/2 equals a rotation by -π/2 up to a global phase. Other angles are decomposed.

Feedback:

• IfStatement of GateX, GateY or GateZ conditioned on a single bit being 1. The same gate conditioned on the bit being 0 is decomposed into the gate followed by the gate conditioned on 1. Any other conditional operation has its body decomposed while staying conditional, and raises a DecompositionError if that does not lead to a conditional Pauli.

Measurements:

• Z-basis: Measure
• X-basis: MeasureX
• Y-basis: MeasureY
• Two-qubit parities: MeasureXX, MeasureYY, MeasureZZ
• Pauli products: MeasurePauli

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
• Pauli channels: PauliNoise

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),

GridSynthRewrite(; epsilon=1e-10, seed=0)

Rewrite rule that approximates GateRZ with a Clifford+T sequence, using the Ross–Selinger gridsynth algorithm.

For GateRZ(λ) the rule emits a sequence of GateH, GateS, GateSDG, GateZ, GateT and GateX whose unitary V satisfies min_φ ‖RZ(λ) − e^{iφ}V‖ ≤ epsilon in operator norm. The approximation holds up to a global phase, which is dropped. The T-count is about 3·log₂(1/epsilon) and, except for rare failures of the integer factoring step, optimal among ancilla-free Clifford+T circuits with this error. Angles that are multiples of π/4 give their exact short decomposition.

The factoring step is randomized. For a fixed seed, the same angle and tolerance always give the same sequence. Results are cached per angle, since circuits often repeat the same rotation.

Keyword Arguments

• epsilon::Real: operator-norm tolerance, 1e-100 ≤ epsilon < 1 (default 1e-10). A rotation takes a few milliseconds at 1e-10 and up to about a second at 1e-100.
• seed::Integer: seed of the randomized factoring step, in [0, 2^64) (default 0).

Throws an ArgumentError if epsilon or seed is out of range. Decomposing a GateRZ whose angle is not finite throws an ArgumentError.

Supported Operations

• GateRZ(λ) with a numeric angle λ.

Symbolic angles are not matched. GateRX, GateRY and GateU must first be reduced to Z-rotations, for example with ZYZRewrite and ToZRotationRewrite. CliffordTBasis does this and uses this rule by default.

Examples

# Approximate one rotation to the default tolerance 1e-10
decompose_step(GateRZ(0.123); rule=GridSynthRewrite())

# A coarser tolerance gives fewer T gates
decompose_step(GateRZ(0.123); rule=GridSynthRewrite(epsilon=1e-4))

# Choose the tolerance used by the Clifford+T basis
decompose(circuit; basis=CliffordTBasis(rotations=GridSynthRewrite(epsilon=1e-8)))

References

• N. J. Ross and P. Selinger, "Optimal ancilla-free Clifford+T approximation of z-rotations", Quantum Inf. Comput. 16, 901 (2016), arXiv:1403.2975.

See also RewriteRule, SolovayKitaevRewrite, CliffordTBasis.

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.

ToffoliToCliffordTRewrite <: RewriteRule

Rewrite rule that decomposes the Toffoli gate (GateCCX) into Clifford+T gates.

The decomposition uses 7 T/Tdg gates and 6 CNOT gates, which is optimal for T-count. This is the standard textbook decomposition.

Transformation

CCX(c1, c2, t) → H(t), CX(c2,t), Tdg(t), CX(c1,t), T(t), CX(c2,t), Tdg(t),
                 CX(c1,t), T(c2), T(t), H(t), CX(c1,c2), T(c1), Tdg(c2), CX(c1,c2)

Output Gates

The decomposition produces only:

• GateH
• GateCX
• GateT, GateTDG

Examples

decompose_step(GateCCX(); rule=ToffoliToCliffordTRewrite())

See also RewriteRule, SpecialAngleRewrite.

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()))

pauli_based_computation(c::Circuit; basis=CliffordTBasis(), magic_states=false)

Rewrite a circuit in Pauli-based computation form: a sequence of $\pi/8$ Pauli product rotations (RPauli with angle $\pm\pi/4$) and Pauli product measurements (MeasurePauli), with no Clifford gates left.

The circuit is first decomposed with basis, which must produce Clifford+T gates, the measurements and resets listed below, and the conditional operations described below. Those measurements, resets and conditional Pauli products are kept whole, whatever basis does with them. Each Clifford $C$ is then moved past every later T gate and measurement, conjugating them: a T gate on qubit $q$ becomes the rotation $\exp(-i \frac{\pi}{8} C^\dagger Z_q C)$, and a measurement of $Z_q$ becomes a measurement of $C^\dagger Z_q C$. When the conjugated observable has a minus sign, the rotation angle is negated, or the measured bit is flipped with Not.

The Cliffords left after the last measurement do not change any outcome and are dropped. The result therefore reproduces the measurement statistics of c, not its final quantum state, and each rotation is exact up to a global phase. Classical operations and annotations are kept in place; barriers and identity gates are dropped.

Measurements, resets and conditional operations

• Measure, MeasureX, MeasureY, MeasureXX, MeasureYY, MeasureZZ and MeasurePauli measure a Pauli product $P$ and become a MeasurePauli of $C^\dagger P C$.
• A reset in the Z, X or Y basis (Reset, ResetX, ResetY) measures $Z$, $X$ or $Y$ into a new bit, then applies, if the outcome is 1, the Pauli that maps the $-1$ eigenstate to the $+1$ one: $X$ for the Z and Y bases, $Z$ for the X basis. The measure-and-reset operations (MeasureReset, MeasureResetX, MeasureResetY) do the same with the bit they are given.
• An IfStatement whose body is made only of Pauli operators applies one Pauli product $P$ when its condition holds. The body can be GateX, GateY, GateZ, GateID, a PauliString, or a Block, Parallel, Repeat or GateCall holding only such operations, at any depth. It becomes one IfStatement of the PauliString $C^\dagger P C$ with the same condition. The phase of $P$ is dropped, as it only multiplies one classical branch.
• A conditional T or T† gate becomes a conditional RPauli rotation with the same condition.

Any other conditional operation is refused. After a conditional Clifford gate, the accumulated Clifford would depend on the condition bits, so the later rotations and measurements could not be computed before the circuit runs.

Magic-state injection

With magic_states=true the rotations are removed as well. Each $\pi/8$ rotation on $P$ consumes a magic state $T\ket{+}$, prepared with PrepareStateT on one ancilla qubit that is reused for every rotation:

1. MeasurePauli of $P \otimes Z$ on the data qubits and the ancilla, with outcome $m_1$.
2. MeasurePauli of $X$ on the ancilla if $m_1 = 0$, of $Y$ if $m_1 = 1$ (swapped for a negative angle), with outcome $m_2$. The choice is made by two IfStatements.

When $m_2 = 1$ the rotation is applied together with a Pauli byproduct $P$. Byproducts are not corrected with gates. Instead, their product $F$ is tracked in classical bits, the Pauli frame: one bit for the X part and one for the Z part of $F$ on each data qubit. When $m_2 = 1$, Xor operations multiply the frame by $P$. Each later $m_1$ or measurement outcome whose Pauli anticommutes with $F$ is flipped in place, again with Xor, so the bits hold the outcomes of the ideal circuit.

A conditional Pauli, including the correction of a reset, is not applied either: it multiplies the frame when its condition holds, with the same Xor operations. A condition other than a single bit equal to 1 is first evaluated into one extra bit with SetBit1 and 3-bit And operations; each condition bit compared with 0 is flipped with Not while it is read and flipped back right after. A conditional T or T† gate is refused, since a magic state cannot be injected conditionally.

Every classical operation added is therefore a 3-bit Xor or And, a Not or a SetBit1, whatever the size of the circuit. The result contains only Pauli product measurements, magic-state preparations and classical logic.

Bit layout

With $n_b$ the number of bits of the decomposed circuit and $r$ its number of resets, the $j$-th reset writes its outcome to bit $n_b + j$. With magic states, let $n'_b = n_b + r$, $n$ be the number of qubits and $t$ the number of T and T† gates of the decomposed circuit. The ancilla is qubit $n + 1$. The $k$-th rotation writes $m_1$ to bit $n'_b + 2k - 1$ and $m_2$ to bit $n'_b + 2k$. The frame bits of qubit $q$ follow: the X part at bit $n'_b + 2t + q$ and the Z part at bit $n'_b + 2t + n + q$. The condition of a conditional Pauli, when it needs its own bit, goes to bit $n'_b + 2t + 2n + 1$.

Errors

Throws a DecompositionError if basis cannot decompose an operation, such as a noise channel. Throws an ArgumentError if the decomposed circuit contains anything other than Clifford+T gates, the measurements and resets listed above, the conditional operations listed above, classical operations and annotations: for example a non-Clifford gate, a conditional Clifford gate or a conditional measurement. With magic_states=true, a conditional T or T† gate also throws an ArgumentError.

Examples

Prepare a Bell pair, apply a T gate to qubit 2 and measure both qubits:

julia> c = push!(Circuit(), GateH(), 1);

julia> push!(c, GateCX(), 1, 2);

julia> push!(c, GateT(), 2);

julia> push!(c, Measure(), 1:2, 1:2);

julia> pauli_based_computation(c)
2-qubit, 2-bit circuit with 3 instructions:
├── R("XZ", π / 4) @ q[1:2]
├── MP(X) @ q[1], c[1]
└── MP(XZ) @ q[1:2], c[2]

The Clifford before the T gate is $C = \mathrm{CX}_{12} H_1$, so the T gate becomes a $\pi/8$ rotation on $C^\dagger Z_2 C = X_1 Z_2$. The two measurements of $Z_1$ and $Z_2$ become measurements of $X_1$ and $X_1 Z_2$, and write to the same bits as before.

With magic states, the rotation becomes an injection on the ancilla qubit 3, whose outcomes $m_1$ and $m_2$ go to the new bits 3 and 4:

julia> c = push!(Circuit(), GateH(), 1);

julia> push!(c, GateCX(), 1, 2);

julia> push!(c, GateT(), 2);

julia> push!(c, Measure(), 1:2, 1:2);

julia> pauli_based_computation(c; magic_states=true)
3-qubit, 8-bit circuit with 8 instructions:
├── PrepareStateT @ q[3]
├── MP(XZZ) @ q[1:3], c[3]
├── IF(c==0) MP(X) @ q[3], c[4], condition[3]
├── IF(c==1) MP(Y) @ q[3], c[4], condition[3]
├── c[5] ⊻= c[4]
├── c[8] ⊻= c[4]
├── MP(X) @ q[1], c[1]
└── MP(XZ) @ q[1:2], c[2]

The ancilla is measured in X or Y depending on $m_1$ (bit 3). The byproduct $X_1 Z_2$ goes into the frame: bit 5 holds its X part on qubit 1 and bit 8 its Z part on qubit 2. The final measurements commute with it, so their bits are not corrected.

A conditional Pauli and a reset. The Hadamard gate before the conditional $Z_2$ turns it into a conditional $X_2$, and the reset of qubit 1 after its Hadamard gate measures $X_1$ into the new bit 4, then applies $Z_1$ if the outcome is 1:

julia> c = push!(Circuit(), GateH(), 1);

julia> push!(c, Measure(), 1, 1);

julia> push!(c, GateH(), 2);

julia> push!(c, IfStatement(GateZ(), bs"1"), 2, 1);

julia> push!(c, Reset(), 1);

julia> push!(c, Measure(), 1:2, 2:3);

julia> pauli_based_computation(c)
2-qubit, 4-bit circuit with 6 instructions:
├── MP(X) @ q[1], c[1]
├── IF(c==1) X @ q[2], condition[1]
├── MP(X) @ q[1], c[4]
├── IF(c==1) Z @ q[1], condition[4]
├── MP(X) @ q[1], c[2]
└── MP(X) @ q[2], c[3]

References

• D. Litinski, "A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery", Quantum 3, 128 (2019).
• S. Bravyi, G. Smith, J. A. Smolin, "Trading Classical and Quantum Computational Resources", Phys. Rev. X 6, 021043 (2016).

See also MeasurePauli, PrepareStateT, RPauli, CliffordTBasis.