prism-q 0.28.0

//! Single-qubit gate fusion and matrix precomputation pass.
//!
//! Scans the instruction stream and fuses consecutive single-qubit gates on the
//! same target qubit into a single `Gate::Fused` carrying the product matrix.
//! Gates on different qubits are transparent. They do not break a pending fusion.
//!
//! When the pass creates a new instruction stream, ALL single-qubit gates are
//! emitted as `Gate::Fused` with precomputed matrices, including isolated gates
//! that have no fusion partner. This avoids redundant `matrix_2x2()` dispatch
//! during simulation. Identity matrices (from inverse cancellation) are elided.
//!
//! # Matrix multiplication order
//!
//! Gates applied in circuit order G1, G2, G3 produce fused matrix M = G3 · G2 · G1.
//! The accumulator multiplies each new gate on the LEFT: `acc = G_new * acc`.
//!
//! # Flush triggers
//!
//! Two-qubit gates, measurements, and barriers flush pending fusions for every
//! qubit they touch before the instruction is emitted.

use std::borrow::Cow;

use num_complex::Complex64;

use super::{Circuit, Instruction, SmallVec, smallvec};
use crate::gates::{
    DiagEntry, DiagonalBatchData, Gate, Multi2qData, MultiFusedData, is_diagonal_2x2,
    is_diagonal_4x4, kron_2x2, mat_mul_2x2, mat_mul_4x4,
};

use super::fusion_phase::{batch_post_phase_1q, fuse_controlled_phases};
use super::fusion_rzz::{fuse_batch_rzz, fuse_rzz};

pub(super) const IDENTITY_EPS: f64 = 1e-12;

/// Minimum qubit count for 1q fusion, reorder, and batching passes.
///
/// Below 10 qubits, statevectors are small enough that gate execution is
/// nanoseconds. The instruction-clone cost of fusion passes (allocating output
/// Vec, cloning non-fuseable instructions) exceeds any simulation savings.
const MIN_QUBITS_FOR_FUSION: usize = 10;

/// Minimum qubit count for multi-gate tiled fusion to be profitable.
const MIN_QUBITS_FOR_MULTI_FUSION: usize = 14;

/// Minimum qubit count for diagonal-family batch passes (BatchRzz, BatchPhase,
/// DiagonalBatch) to be profitable. LUT kernel overhead needs enough state size
/// to amortize.
const MIN_QUBITS_FOR_DIAG_BATCH: usize = 16;

/// Minimum qubit count for post-phase-fusion 1q batching.
///
/// After `fuse_controlled_phases`, consecutive 1q gates (H gates in QFT) are
/// batched into MultiFused for tiled execution. At 16q (1MB, L3-resident),
/// tiling overhead exceeds savings. Profitable at 18q+ where DRAM bandwidth
/// dominates.
const MIN_QUBITS_FOR_POST_PHASE_BATCH: usize = 18;

/// Minimum qubit count for two-qubit gate fusion (absorb 1q into CX/CZ) to be profitable.
///
/// The generic 4×4 kernel does ~4x the FLOPs of specialized CX/CZ + SIMD 1q kernels.
/// Benchmarked QV and random sweeps show memory-pass reduction wins from 12q.
const MIN_QUBITS_FOR_2Q_FUSION: usize = 12;

/// Bench-only kill switch for `reorder_disjoint_fused2q`. Reads
/// `PRISM_NO_REORDER` once and caches the result. Toggle for A/B timing
/// comparisons without rebuilding.
#[inline]
fn reorder_2q_enabled() -> bool {
    use std::sync::OnceLock;
    static ENABLED: OnceLock<bool> = OnceLock::new();
    *ENABLED.get_or_init(|| std::env::var_os("PRISM_NO_REORDER").is_none())
}

/// Minimum qubit count for multi-2q tiled fusion to be profitable.
///
/// Batches consecutive Fused2q gates into a single cache-tiled pass. Only
/// created when Fused2q gates exist, so threshold matches.
const MIN_QUBITS_FOR_MULTI_2Q_FUSION: usize = MIN_QUBITS_FOR_2Q_FUSION;

/// Minimum batch size for multi-2q fusion (single gate not worth wrapping).
const MIN_MULTI_2Q_BATCH: usize = 2;

/// Append `q` to a fused-instruction target list unless already present.
#[inline]
pub(super) fn push_unique(qubits: &mut SmallVec<[usize; 4]>, q: usize) {
    if !qubits.contains(&q) {
        qubits.push(q);
    }
}

/// Returns the qubits touched by an instruction.
fn inst_qubits(inst: &Instruction) -> &[usize] {
    match inst {
        Instruction::Gate { targets, .. } | Instruction::Conditional { targets, .. } => targets,
        Instruction::Measure { qubit, .. } | Instruction::Reset { qubit } => {
            std::slice::from_ref(qubit)
        }
        Instruction::Barrier { qubits } => qubits,
    }
}

/// Clear the pending entry for qubit `q` and its partner.
fn clear_pending(q: usize, instructions: &[Instruction], pending: &mut [Option<usize>]) {
    if let Some(pi) = pending[q] {
        if let Instruction::Gate { targets, .. } = &instructions[pi] {
            for &t in targets.iter() {
                pending[t] = None;
            }
        }
    }
}

/// True if two instructions form a cancelling pair (same self-inverse 2q gate, same targets).
///
/// For CX, target order must match exactly (CX(0,1) ≠ CX(1,0)).
/// For CZ and SWAP, either order matches (symmetric gates).
fn is_cancelling_pair(a: &Instruction, b: &Instruction) -> bool {
    match (a, b) {
        (
            Instruction::Gate {
                gate: ga,
                targets: ta,
            },
            Instruction::Gate {
                gate: gb,
                targets: tb,
            },
        ) => {
            if !ga.is_self_inverse_2q() || std::mem::discriminant(ga) != std::mem::discriminant(gb)
            {
                return false;
            }
            if ta.as_slice() == tb.as_slice() {
                return true;
            }
            // CZ and SWAP are symmetric, reversed order also cancels
            matches!(ga, Gate::Cz | Gate::Swap)
                && ta.len() == 2
                && tb.len() == 2
                && ta[0] == tb[1]
                && ta[1] == tb[0]
        }
        _ => false,
    }
}

/// Cancel pairs of self-inverse two-qubit gates (CX·CX, CZ·CZ, SWAP·SWAP).
///
/// Tracks pending self-inverse 2q gates per-qubit. When a matching gate appears
/// with no intervening instruction on the same qubits, both are removed.
/// Returns `Cow::Borrowed` when no cancellation opportunities exist.
pub(crate) fn cancel_self_inverse_pairs(circuit: &Circuit) -> Cow<'_, Circuit> {
    let has_candidates = circuit.instructions.iter().any(|inst| {
        matches!(
            inst,
            Instruction::Gate { gate, .. } if gate.is_self_inverse_2q()
        )
    });
    if !has_candidates {
        return Cow::Borrowed(circuit);
    }

    let n = circuit.num_qubits;
    let len = circuit.instructions.len();
    let mut cancelled = vec![false; len];
    let mut any_cancelled = false;

    let mut pending: Vec<Option<usize>> = vec![None; n];

    for i in 0..len {
        let inst = &circuit.instructions[i];
        match inst {
            Instruction::Gate { gate, targets } if gate.is_self_inverse_2q() => {
                let (q0, q1) = (targets[0], targets[1]);

                let found = pending[q0]
                    .filter(|&pi| is_cancelling_pair(&circuit.instructions[pi], inst))
                    .or_else(|| {
                        pending[q1]
                            .filter(|&pi| is_cancelling_pair(&circuit.instructions[pi], inst))
                    });

                if let Some(pi) = found {
                    cancelled[pi] = true;
                    cancelled[i] = true;
                    any_cancelled = true;
                    clear_pending(q0, &circuit.instructions, &mut pending);
                    clear_pending(q1, &circuit.instructions, &mut pending);
                } else {
                    clear_pending(q0, &circuit.instructions, &mut pending);
                    clear_pending(q1, &circuit.instructions, &mut pending);
                    pending[q0] = Some(i);
                    pending[q1] = Some(i);
                }
            }
            _ => {
                for &q in inst_qubits(inst) {
                    if q < n {
                        clear_pending(q, &circuit.instructions, &mut pending);
                    }
                }
            }
        }
    }

    if !any_cancelled {
        return Cow::Borrowed(circuit);
    }

    let output = circuit
        .instructions
        .iter()
        .enumerate()
        .filter(|(j, _)| !cancelled[*j])
        .map(|(_, inst)| inst.clone())
        .collect();

    Cow::Owned(circuit.with_instructions(output))
}

fn is_identity(mat: &[[Complex64; 2]; 2]) -> bool {
    (mat[0][0].re - 1.0).abs() < IDENTITY_EPS
        && mat[0][0].im.abs() < IDENTITY_EPS
        && mat[0][1].norm() < IDENTITY_EPS
        && mat[1][0].norm() < IDENTITY_EPS
        && (mat[1][1].re - 1.0).abs() < IDENTITY_EPS
        && mat[1][1].im.abs() < IDENTITY_EPS
}

#[inline]
fn gate_1q_matrix(gate: &Gate) -> [[Complex64; 2]; 2] {
    match gate {
        Gate::Fused(m) => **m,
        _ => gate.matrix_2x2(),
    }
}

#[inline]
fn accumulate_1q(slot: &mut Option<[[Complex64; 2]; 2]>, mat: [[Complex64; 2]; 2]) -> bool {
    match slot {
        Some(existing) => {
            *existing = mat_mul_2x2(&mat, existing);
            false
        }
        empty => {
            *empty = Some(mat);
            true
        }
    }
}

#[inline]
fn push_fused_1q(output: &mut Vec<Instruction>, q: usize, mat: [[Complex64; 2]; 2]) {
    output.push(Instruction::Gate {
        gate: Gate::Fused(Box::new(mat)),
        targets: smallvec![q],
    });
}

struct PendingFusion {
    matrix: [[Complex64; 2]; 2],
    target: usize,
}

fn flush(pending: &mut Option<PendingFusion>, output: &mut Vec<Instruction>) {
    if let Some(p) = pending.take() {
        if !is_identity(&p.matrix) {
            let gate = match Gate::recognize_matrix(&p.matrix) {
                Some(Gate::Id) => return,
                Some(named) => named,
                None => Gate::Fused(Box::new(p.matrix)),
            };
            output.push(Instruction::Gate {
                gate,
                targets: smallvec![p.target],
            });
        }
    }
}

/// Fuse consecutive single-qubit gates on the same target into one `Gate::Fused`.
///
/// Returns a `Cow::Borrowed` reference to the original circuit when no two
/// consecutive 1q gates share a qubit (zero overhead), or a `Cow::Owned` new
/// circuit with fused instructions. The fused circuit produces identical
/// simulation results.
pub(crate) fn fuse_single_qubit_gates(circuit: &Circuit) -> Cow<'_, Circuit> {
    let n = circuit.num_qubits;
    let mut pending: Vec<Option<PendingFusion>> = (0..n).map(|_| None).collect();
    let mut output: Vec<Instruction> = Vec::with_capacity(circuit.instructions.len());
    let mut changed = false;

    for inst in &circuit.instructions {
        match inst {
            Instruction::Gate { gate, targets } if gate.num_qubits() == 1 => {
                let q = targets[0];
                let mat = gate.matrix_2x2();
                match &mut pending[q] {
                    Some(p) => {
                        p.matrix = mat_mul_2x2(&mat, &p.matrix);
                        changed = true;
                    }
                    slot => {
                        *slot = Some(PendingFusion {
                            matrix: mat,
                            target: q,
                        });
                    }
                }
            }
            _ => {
                for &q in inst_qubits(inst) {
                    flush(&mut pending[q], &mut output);
                }
                output.push(inst.clone());
            }
        }
    }

    for slot in &mut pending {
        flush(slot, &mut output);
    }

    if changed {
        Cow::Owned(circuit.with_instructions(output))
    } else {
        Cow::Borrowed(circuit)
    }
}

/// Reorder single-qubit gates as early as possible in the instruction stream.
///
/// Moves each 1q gate backward past non-conflicting instructions (those that
/// don't touch the same qubit). Diagonal 1q gates can also pass through CX
/// (when on the control qubit) and CZ (on either qubit) via commutation.
///
/// This groups 1q gates together, maximizing batching opportunities for the
/// subsequent `fuse_multi_1q_gates()` pass.
///
/// Returns the input unchanged when no gate moves.
pub(crate) fn reorder_1q_gates(circuit: Cow<'_, Circuit>) -> Cow<'_, Circuit> {
    let n = circuit.num_qubits;
    // block_all[q] / block_diag[q]: index into non_1q of the last blocker
    let mut block_all: Vec<usize> = vec![usize::MAX; n];
    let mut block_diag: Vec<usize> = vec![usize::MAX; n];
    let mut last_1q_slot: Vec<usize> = vec![0; n];
    let mut non_1q: Vec<&Instruction> = Vec::new();
    let mut slots: Vec<Vec<Instruction>> = vec![Vec::new()];
    let mut changed = false;

    for inst in &circuit.instructions {
        match inst {
            Instruction::Gate { gate, targets } if gate.num_qubits() == 1 => {
                let q = targets[0];
                let blocker = if gate.is_diagonal_1q() {
                    block_diag[q]
                } else {
                    block_all[q]
                };
                let dep_slot = if blocker == usize::MAX {
                    0
                } else {
                    blocker + 1
                };
                let slot = dep_slot.max(last_1q_slot[q]);
                if slot < non_1q.len() {
                    changed = true;
                }
                slots[slot].push(inst.clone());
                last_1q_slot[q] = slot;
            }
            _ => {
                let idx = non_1q.len();
                non_1q.push(inst);
                slots.push(Vec::new());
                match inst {
                    Instruction::Gate { gate, targets } => match gate {
                        Gate::Cx => {
                            block_all[targets[0]] = idx;
                            // block_diag[targets[0]] unchanged, diagonal commutes on control
                            block_all[targets[1]] = idx;
                            block_diag[targets[1]] = idx;
                        }
                        Gate::Cz | Gate::Rzz(_) => {
                            block_all[targets[0]] = idx;
                            block_all[targets[1]] = idx;
                            // block_diag unchanged for both, diagonal commutes on both
                        }
                        Gate::BatchRzz(_) | Gate::DiagonalBatch(_) => {
                            for &q in targets.iter() {
                                block_all[q] = idx;
                            }
                            // block_diag unchanged, all-diagonal gate
                        }
                        _ => {
                            for &q in targets.iter() {
                                block_all[q] = idx;
                                block_diag[q] = idx;
                            }
                        }
                    },
                    _ => {
                        for &q in inst_qubits(inst) {
                            block_all[q] = idx;
                            block_diag[q] = idx;
                        }
                    }
                }
            }
        }
    }

    if !changed {
        return circuit;
    }

    let mut output: Vec<Instruction> = Vec::with_capacity(circuit.instructions.len());
    for (i, non_1q_inst) in non_1q.iter().enumerate() {
        output.append(&mut slots[i]);
        output.push((*non_1q_inst).clone());
    }
    output.append(&mut slots[non_1q.len()]);

    Cow::Owned(circuit.with_instructions(output))
}

/// Fuse single-qubit gates on distinct qubits into `Gate::MultiFused`.
///
/// Accumulates 1q gates per-qubit across the instruction stream. When a non-1q
/// instruction is encountered, only the pending gates on the **affected qubits**
/// are flushed. Gates on unrelated qubits continue accumulating. This produces
/// fewer but larger MultiFused batches than flushing the entire run at every 2q gate.
///
/// Correctness: a 1q gate on qubit q commutes with any multi-qubit gate not
/// involving q (independent subspaces), so deferring its application is safe.
pub(crate) fn fuse_multi_1q_gates(circuit: Cow<'_, Circuit>) -> Cow<'_, Circuit> {
    if !has_multi_1q_run(&circuit) {
        return circuit;
    }

    let n = circuit.num_qubits;
    let mut output: Vec<Instruction> = Vec::with_capacity(circuit.instructions.len());
    let mut pending: Vec<Option<[[Complex64; 2]; 2]>> = vec![None; n];
    let mut pending_count = 0usize;

    for inst in &circuit.instructions {
        match inst {
            Instruction::Gate { gate, targets } if gate.num_qubits() == 1 => {
                let q = targets[0];
                let mat = gate_1q_matrix(gate);
                if accumulate_1q(&mut pending[q], mat) {
                    pending_count += 1;
                }
            }
            _ => {
                for &q in inst_qubits(inst) {
                    flush_1q_pending(q, &mut pending, &mut pending_count, &mut output);
                }
                output.push(inst.clone());
            }
        }
    }
    flush_all_pending(&mut pending, &mut pending_count, &mut output);

    Cow::Owned(circuit.with_instructions(output))
}

#[inline]
fn flush_indexed_1q(
    q: usize,
    pending: &mut [Option<[[Complex64; 2]; 2]>],
    output: &mut Vec<Instruction>,
) {
    if let Some(mat) = pending[q].take() {
        push_fused_1q(output, q, mat);
    }
}

fn flush_1q_pending(
    q: usize,
    pending: &mut [Option<[[Complex64; 2]; 2]>],
    pending_count: &mut usize,
    output: &mut Vec<Instruction>,
) {
    if pending[q].is_some() {
        *pending_count -= 1;
        flush_indexed_1q(q, pending, output);
    }
}

fn flush_all_pending(
    pending: &mut [Option<[[Complex64; 2]; 2]>],
    pending_count: &mut usize,
    output: &mut Vec<Instruction>,
) {
    if *pending_count >= 2 {
        let mut gates: Vec<(usize, [[Complex64; 2]; 2])> = Vec::with_capacity(*pending_count);
        for (q, slot) in pending.iter_mut().enumerate() {
            if let Some(mat) = slot.take() {
                gates.push((q, mat));
            }
        }
        let all_diagonal = gates.iter().all(|(_, m)| is_diagonal_2x2(m));
        let targets: SmallVec<[usize; 4]> = gates.iter().map(|&(t, _)| t).collect();
        output.push(Instruction::Gate {
            gate: Gate::MultiFused(Box::new(MultiFusedData {
                gates,
                all_diagonal,
            })),
            targets,
        });
    } else {
        for (q, slot) in pending.iter_mut().enumerate() {
            if let Some(mat) = slot.take() {
                push_fused_1q(output, q, mat);
            }
        }
    }
    *pending_count = 0;
}

fn has_multi_1q_run(circuit: &Circuit) -> bool {
    let mut total_1q = 0usize;
    for inst in &circuit.instructions {
        if let Instruction::Gate { gate, .. } = inst {
            if gate.num_qubits() == 1 {
                total_1q += 1;
                if total_1q >= 2 {
                    return true;
                }
            }
        }
    }
    false
}

/// Fuse adjacent single-qubit gates into two-qubit gates.
///
/// Scans for patterns where a CX or CZ gate has pending 1q gates on its qubits.
/// The 1q gates are absorbed into the 2q gate via Kronecker product,
/// producing a `Gate::Fused2q` with a 4×4 unitary.
///
/// Only CX and CZ are targeted. SWAP and Cu have specialized SIMD kernels;
/// Cu is excluded to preserve downstream cphase batching.
///
/// Algorithm: greedy forward pass, absorbing pre-gates only. Post-gates of one
/// 2q gate become pre-gates of the next, so most HEA-style patterns are captured.
///
/// Returns the input unchanged when no absorption happens.
pub(crate) fn fuse_2q_gates(circuit: Cow<'_, Circuit>) -> Cow<'_, Circuit> {
    let identity_2x2 = Gate::Id.matrix_2x2();
    let n = circuit.num_qubits;
    let mut pending_1q: Vec<Option<[[Complex64; 2]; 2]>> = vec![None; n];
    let mut output: Vec<Instruction> = Vec::with_capacity(circuit.instructions.len());
    let mut changed = false;

    for inst in &circuit.instructions {
        match inst {
            Instruction::Gate { gate, targets } if gate.num_qubits() == 1 => {
                let q = targets[0];
                let mat = gate_1q_matrix(gate);
                accumulate_1q(&mut pending_1q[q], mat);
            }
            Instruction::Gate {
                gate: gate @ (Gate::Cx | Gate::Cz),
                targets,
            } => {
                let q0 = targets[0];
                let q1 = targets[1];
                let pre0 = pending_1q[q0].take();
                let pre1 = pending_1q[q1].take();

                if pre0.is_none() && pre1.is_none() {
                    output.push(inst.clone());
                } else {
                    let m0 = pre0.unwrap_or(identity_2x2);
                    let m1 = pre1.unwrap_or(identity_2x2);
                    let kron = kron_2x2(&m0, &m1);
                    let gate4 = gate.matrix_4x4();
                    let fused = mat_mul_4x4(&gate4, &kron);
                    output.push(Instruction::Gate {
                        gate: Gate::Fused2q(Box::new(fused)),
                        targets: smallvec![q0, q1],
                    });
                    changed = true;
                }
            }
            _ => {
                for &q in inst_qubits(inst) {
                    flush_indexed_1q(q, &mut pending_1q, &mut output);
                }
                output.push(inst.clone());
            }
        }
    }

    for q in 0..n {
        flush_indexed_1q(q, &mut pending_1q, &mut output);
    }

    if changed {
        Cow::Owned(circuit.with_instructions(output))
    } else {
        circuit
    }
}

/// Cache-tier classification for 2q gates based on max target qubit.
///
/// A 2q gate on (q0, q1) fits in a tile of 2^N elements iff max(q0, q1) < N.
/// L2 tiles = 16384 = 2^14 → max qubit ≤ 13.
/// L3 tiles = 131072 = 2^17 → max qubit ≤ 16.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Tier2q {
    L2,
    L3,
    Individual,
}

fn classify_2q_tier(q0: usize, q1: usize) -> Tier2q {
    let max_q = q0.max(q1);
    if max_q <= 13 {
        Tier2q::L2
    } else if max_q <= 16 {
        Tier2q::L3
    } else {
        Tier2q::Individual
    }
}

#[inline]
fn swap_order_4x4(mat: &[[Complex64; 4]; 4]) -> [[Complex64; 4]; 4] {
    let swap = Gate::Swap.matrix_4x4();
    mat_mul_4x4(&swap, &mat_mul_4x4(mat, &swap))
}

#[inline]
fn same_unordered_pair(a0: usize, a1: usize, b0: usize, b1: usize) -> bool {
    (a0 == b0 && a1 == b1) || (a0 == b1 && a1 == b0)
}

#[inline]
fn orient_2q_matrix(
    mat: &[[Complex64; 4]; 4],
    targets: &[usize],
    q0: usize,
    q1: usize,
) -> [[Complex64; 4]; 4] {
    if targets[0] == q0 && targets[1] == q1 {
        *mat
    } else {
        swap_order_4x4(mat)
    }
}

#[inline]
fn embed_1q_matrix(mat: &[[Complex64; 2]; 2], target: usize, q0: usize) -> [[Complex64; 4]; 4] {
    let id = Gate::Id.matrix_2x2();
    if target == q0 {
        kron_2x2(mat, &id)
    } else {
        kron_2x2(&id, mat)
    }
}

struct PairRun {
    q0: usize,
    q1: usize,
    acc: [[Complex64; 4]; 4],
    fused_2q_count: usize,
    has_nondiagonal_2q: bool,
    originals: Vec<Instruction>,
}

impl PairRun {
    fn new(q0: usize, q1: usize, mat: [[Complex64; 4]; 4], original: Instruction) -> Self {
        Self {
            q0,
            q1,
            acc: mat,
            fused_2q_count: 1,
            has_nondiagonal_2q: !is_diagonal_4x4(&mat),
            originals: vec![original],
        }
    }

    #[inline]
    fn can_accept_pair(&self, q0: usize, q1: usize) -> bool {
        same_unordered_pair(self.q0, self.q1, q0, q1)
    }

    #[inline]
    fn can_accept_1q(&self, q: usize) -> bool {
        q == self.q0 || q == self.q1
    }

    fn push_2q(&mut self, mat: [[Complex64; 4]; 4], targets: &[usize], original: Instruction) {
        let oriented = orient_2q_matrix(&mat, targets, self.q0, self.q1);
        self.acc = mat_mul_4x4(&oriented, &self.acc);
        self.fused_2q_count += 1;
        self.has_nondiagonal_2q |= !is_diagonal_4x4(&oriented);
        self.originals.push(original);
    }

    fn push_1q(&mut self, mat: [[Complex64; 2]; 2], target: usize, original: Instruction) {
        let embedded = embed_1q_matrix(&mat, target, self.q0);
        self.acc = mat_mul_4x4(&embedded, &self.acc);
        self.originals.push(original);
    }

    fn should_fuse(&self) -> bool {
        self.fused_2q_count >= 2 && self.has_nondiagonal_2q
    }
}

fn flush_pair_run(run: &mut Option<PairRun>, output: &mut Vec<Instruction>, changed: &mut bool) {
    let Some(run) = run.take() else {
        return;
    };
    if run.should_fuse() {
        output.push(Instruction::Gate {
            gate: Gate::Fused2q(Box::new(run.acc)),
            targets: smallvec![run.q0, run.q1],
        });
        *changed = true;
    } else {
        output.extend(run.originals);
    }
}

/// Fuse contiguous same-pair `Fused2q` runs into one larger `Fused2q`.
///
/// This pass is deliberately narrow: it only consumes existing `Fused2q` gates
/// and single-qubit gates on the same two qubits, and only emits a fused block
/// when at least two 2q units are present. All-diagonal runs are left alone so
/// diagonal batch passes keep their cheaper kernels.
fn fuse_same_pair_2q_blocks(input: Cow<'_, Circuit>) -> Cow<'_, Circuit> {
    let circuit = input.as_ref();
    let mut output: Vec<Instruction> = Vec::with_capacity(circuit.instructions.len());
    let mut run: Option<PairRun> = None;
    let mut changed = false;

    for inst in &circuit.instructions {
        match inst {
            Instruction::Gate {
                gate: Gate::Fused2q(mat),
                targets,
            } => {
                if let Some(active) = &mut run {
                    if active.can_accept_pair(targets[0], targets[1]) {
                        active.push_2q(**mat, targets, inst.clone());
                    } else {
                        flush_pair_run(&mut run, &mut output, &mut changed);
                        run = Some(PairRun::new(targets[0], targets[1], **mat, inst.clone()));
                    }
                } else {
                    run = Some(PairRun::new(targets[0], targets[1], **mat, inst.clone()));
                }
            }
            Instruction::Gate { gate, targets } if gate.num_qubits() == 1 => {
                if let Some(active) = &mut run {
                    if active.can_accept_1q(targets[0]) {
                        let mat = gate_1q_matrix(gate);
                        active.push_1q(mat, targets[0], inst.clone());
                    } else {
                        flush_pair_run(&mut run, &mut output, &mut changed);
                        output.push(inst.clone());
                    }
                } else {
                    output.push(inst.clone());
                }
            }
            _ => {
                flush_pair_run(&mut run, &mut output, &mut changed);
                output.push(inst.clone());
            }
        }
    }

    flush_pair_run(&mut run, &mut output, &mut changed);

    if changed {
        Cow::Owned(circuit.with_instructions(output))
    } else {
        input
    }
}

/// Reorder consecutive `Fused2q` gates with pairwise-disjoint qubit supports
/// so that gates of the same `Tier2q` are grouped together. Disjoint-support
/// 2q gates commute, so reordering is identity-preserving.
///
/// Random pair circuits (notably Quantum Volume) emit `Fused2q` streams whose
/// tiers are interleaved. The downstream `fuse_multi_2q_gates` only batches
/// consecutive same-tier gates, so without this pass tier transitions break
/// the run after every one or two gates.
///
/// Returns `Cow::Borrowed` when no reorder happens.
pub(crate) fn reorder_disjoint_fused2q(input: Cow<'_, Circuit>) -> Cow<'_, Circuit> {
    let circuit = input.as_ref();
    let mut output: Vec<Instruction> = Vec::with_capacity(circuit.instructions.len());
    let mut window: Vec<(Tier2q, Instruction)> = Vec::new();
    let mut window_qubits = vec![false; circuit.num_qubits];
    let mut changed = false;

    for inst in &circuit.instructions {
        if let Instruction::Gate {
            gate: Gate::Fused2q(_),
            targets,
        } = inst
        {
            let q0 = targets[0];
            let q1 = targets[1];
            if window_qubits[q0] || window_qubits[q1] {
                flush_disjoint_window(&mut window, &mut window_qubits, &mut output, &mut changed);
            }
            window_qubits[q0] = true;
            window_qubits[q1] = true;
            window.push((classify_2q_tier(q0, q1), inst.clone()));
        } else {
            flush_disjoint_window(&mut window, &mut window_qubits, &mut output, &mut changed);
            output.push(inst.clone());
        }
    }
    flush_disjoint_window(&mut window, &mut window_qubits, &mut output, &mut changed);

    if changed {
        Cow::Owned(circuit.with_instructions(output))
    } else {
        input
    }
}

fn flush_disjoint_window(
    window: &mut Vec<(Tier2q, Instruction)>,
    window_qubits: &mut [bool],
    output: &mut Vec<Instruction>,
    changed: &mut bool,
) {
    if window.len() >= 2 {
        let mut tier_counts = [0u32; 3];
        for (t, _) in window.iter() {
            tier_counts[*t as usize] += 1;
        }
        let any_tier_batchable = tier_counts.iter().any(|&c| c >= MIN_MULTI_2Q_BATCH as u32);
        if any_tier_batchable {
            let already_sorted = window.windows(2).all(|w| (w[0].0 as u8) <= (w[1].0 as u8));
            if !already_sorted {
                window.sort_by_key(|(t, _)| *t as u8);
                *changed = true;
            }
        }
    }
    for (_, inst) in window.drain(..) {
        output.push(inst);
    }
    for q in window_qubits.iter_mut() {
        *q = false;
    }
}

/// Batch consecutive `Fused2q` gates into `Multi2q` for cache-tiled execution.
///
/// Scans for runs of consecutive `Fused2q` instructions within the same cache
/// tier (L2 or L3). Each run of ≥2 gates is replaced by a single `Multi2q`
/// gate that the statevector backend applies in a tiled pass. Individual-tier
/// gates (max qubit > 16) are left as-is.
///
/// Returns the input unchanged when no batch forms.
pub(crate) fn fuse_multi_2q_gates(circuit: Cow<'_, Circuit>) -> Cow<'_, Circuit> {
    let mut output: Vec<Instruction> = Vec::with_capacity(circuit.instructions.len());
    let mut pending: Vec<(usize, usize, [[Complex64; 4]; 4])> = Vec::new();
    let mut current_tier: Option<Tier2q> = None;
    let mut changed = false;

    let flush = |pending: &mut Vec<(usize, usize, [[Complex64; 4]; 4])>,
                 tier: &mut Option<Tier2q>,
                 output: &mut Vec<Instruction>,
                 changed: &mut bool| {
        if pending.is_empty() {
            return;
        }
        let t = tier.take().unwrap();
        if t == Tier2q::Individual || pending.len() < MIN_MULTI_2Q_BATCH {
            for (q0, q1, mat) in pending.drain(..) {
                output.push(Instruction::Gate {
                    gate: Gate::Fused2q(Box::new(mat)),
                    targets: smallvec![q0, q1],
                });
            }
        } else {
            let mut all_qubits: SmallVec<[usize; 4]> = SmallVec::new();
            for &(q0, q1, _) in pending.iter() {
                push_unique(&mut all_qubits, q0);
                push_unique(&mut all_qubits, q1);
            }
            all_qubits.sort_unstable();
            output.push(Instruction::Gate {
                gate: Gate::Multi2q(Box::new(Multi2qData {
                    gates: std::mem::take(pending),
                })),
                targets: all_qubits,
            });
            *changed = true;
        }
    };

    for inst in &circuit.instructions {
        match inst {
            Instruction::Gate {
                gate: Gate::Fused2q(mat),
                targets,
            } => {
                let q0 = targets[0];
                let q1 = targets[1];
                let tier = classify_2q_tier(q0, q1);

                if let Some(ct) = current_tier {
                    if ct != tier {
                        flush(&mut pending, &mut current_tier, &mut output, &mut changed);
                    }
                }
                if current_tier.is_none() {
                    current_tier = Some(tier);
                }
                pending.push((q0, q1, **mat));
            }
            _ => {
                flush(&mut pending, &mut current_tier, &mut output, &mut changed);
                output.push(inst.clone());
            }
        }
    }
    flush(&mut pending, &mut current_tier, &mut output, &mut changed);

    if changed {
        Cow::Owned(circuit.with_instructions(output))
    } else {
        circuit
    }
}

/// Batch contiguous runs of diagonal gates into `DiagonalBatch` instructions.
///
/// Diagonal gates (Z, S, T, Rz, P, CZ, Rzz, CPhase) commute with each other,
/// so adjacent diagonal gates can be collapsed into a single pass with precomputed
/// phase LUTs. Non-diagonal gates on non-involved qubits are deferred past the run.
fn fuse_diagonal_batch(input: Cow<'_, Circuit>) -> Cow<'_, Circuit> {
    let circuit = input.as_ref();
    let insts = &circuit.instructions;
    let n = insts.len();
    if n < 2 {
        return input;
    }

    let diag_count = insts
        .iter()
        .filter(|i| matches!(i, Instruction::Gate { gate, .. } if gate.is_diag_batchable()))
        .count();
    if diag_count < 2 {
        return input;
    }

    let mut output: Vec<Instruction> = Vec::with_capacity(n);
    let mut run_entries: Vec<DiagEntry> = Vec::new();
    let mut run_originals: Vec<Instruction> = Vec::new();
    let mut run_qubits = vec![false; circuit.num_qubits];
    let mut deferred: Vec<Instruction> = Vec::new();
    let mut deferred_qubits = vec![false; circuit.num_qubits];

    let flush_diag_run = |output: &mut Vec<Instruction>,
                          entries: &mut Vec<DiagEntry>,
                          originals: &mut Vec<Instruction>,
                          deferred: &mut Vec<Instruction>,
                          run_qubits: &mut [bool],
                          deferred_qubits: &mut [bool]| {
        if entries.len() >= 2 {
            let mut tgts: SmallVec<[usize; 4]> = SmallVec::new();
            for (i, &used) in run_qubits.iter().enumerate() {
                if used {
                    tgts.push(i);
                }
            }
            output.push(Instruction::Gate {
                gate: Gate::DiagonalBatch(Box::new(DiagonalBatchData {
                    entries: std::mem::take(entries),
                })),
                targets: tgts,
            });
        } else {
            output.append(originals);
        }
        entries.clear();
        originals.clear();
        output.append(deferred);
        run_qubits.fill(false);
        deferred_qubits.fill(false);
    };

    for inst in insts {
        if let Instruction::Gate { gate, targets } = inst {
            if gate.is_diag_batchable() {
                // Deferred gates are re-emitted after the whole batch. Admitting
                // a diagonal gate on a deferred gate's qubit would sink that
                // gate behind one it does not commute with, so close the run
                // first and let this gate open a new one.
                if targets.iter().any(|t| deferred_qubits[*t]) {
                    flush_diag_run(
                        &mut output,
                        &mut run_entries,
                        &mut run_originals,
                        &mut deferred,
                        &mut run_qubits,
                        &mut deferred_qubits,
                    );
                }
                let new_entries = gate.diag_entries(targets);
                for t in targets.iter() {
                    run_qubits[*t] = true;
                }
                run_entries.extend(new_entries);
                run_originals.push(inst.clone());
                continue;
            }

            if !run_entries.is_empty() && gate.num_qubits() == 1 && !run_qubits[targets[0]] {
                deferred_qubits[targets[0]] = true;
                deferred.push(inst.clone());
                continue;
            }
        }

        flush_diag_run(
            &mut output,
            &mut run_entries,
            &mut run_originals,
            &mut deferred,
            &mut run_qubits,
            &mut deferred_qubits,
        );
        output.push(inst.clone());
    }

    flush_diag_run(
        &mut output,
        &mut run_entries,
        &mut run_originals,
        &mut deferred,
        &mut run_qubits,
        &mut deferred_qubits,
    );

    let mut c = Circuit::new(circuit.num_qubits, circuit.num_classical_bits);
    c.instructions = output;
    Cow::Owned(c)
}

/// Threads a `&Circuit -> Cow<Circuit>` pass over a `Cow<Circuit>` while
/// preserving zero-copy when both input and output are borrowed.
#[inline]
fn apply_pass<'a, F>(input: Cow<'a, Circuit>, pass: F) -> Cow<'a, Circuit>
where
    F: for<'b> Fn(&'b Circuit) -> Cow<'b, Circuit>,
{
    match input {
        Cow::Borrowed(c) => pass(c),
        Cow::Owned(c) => Cow::Owned(pass(&c).into_owned()),
    }
}

#[inline]
fn gated<'a, F>(
    input: Cow<'a, Circuit>,
    num_qubits: usize,
    threshold: usize,
    pass: F,
) -> Cow<'a, Circuit>
where
    F: FnOnce(Cow<'a, Circuit>) -> Cow<'a, Circuit>,
{
    if num_qubits >= threshold {
        pass(input)
    } else {
        input
    }
}

/// Returns `Cow::Borrowed` when no fusion is profitable (zero overhead).
/// Set `supports_fused` to `false` for backends that cannot handle fused gates
/// (e.g., stabilizer).
pub fn fuse_circuit<'a>(circuit: &'a Circuit, supports_fused: bool) -> Cow<'a, Circuit> {
    if !supports_fused {
        return Cow::Borrowed(circuit);
    }

    let n = circuit.num_qubits;
    let pass0 = cancel_self_inverse_pairs(circuit);
    let pass0r = apply_pass(pass0, fuse_rzz);
    let pass0b = gated(pass0r, n, MIN_QUBITS_FOR_DIAG_BATCH, |c| {
        apply_pass(c, fuse_batch_rzz)
    });

    if n < MIN_QUBITS_FOR_FUSION {
        return pass0b;
    }

    let pass1 = apply_pass(pass0b, fuse_single_qubit_gates);
    let pass1r = reorder_1q_gates(pass1);
    let pass1c = apply_pass(pass1r, cancel_self_inverse_pairs);
    let pass1f = apply_pass(pass1c, fuse_single_qubit_gates);

    let pass_2q = gated(pass1f, n, MIN_QUBITS_FOR_2Q_FUSION, fuse_2q_gates);
    let pass_2qb = gated(
        pass_2q,
        n,
        MIN_QUBITS_FOR_2Q_FUSION,
        fuse_same_pair_2q_blocks,
    );
    let pass2 = gated(
        pass_2qb,
        n,
        MIN_QUBITS_FOR_MULTI_FUSION,
        fuse_multi_1q_gates,
    );
    let pass_2qr = if n >= MIN_QUBITS_FOR_MULTI_2Q_FUSION && reorder_2q_enabled() {
        reorder_disjoint_fused2q(pass2)
    } else {
        pass2
    };
    let pass_m2q = gated(
        pass_2qr,
        n,
        MIN_QUBITS_FOR_MULTI_2Q_FUSION,
        fuse_multi_2q_gates,
    );
    let pass_cp = gated(
        pass_m2q,
        n,
        MIN_QUBITS_FOR_DIAG_BATCH,
        fuse_controlled_phases,
    );
    let pass_db = gated(pass_cp, n, MIN_QUBITS_FOR_DIAG_BATCH, fuse_diagonal_batch);
    gated(
        pass_db,
        n,
        MIN_QUBITS_FOR_POST_PHASE_BATCH,
        batch_post_phase_1q,
    )
}

#[cfg(test)]
#[path = "fusion_tests.rs"]
mod tests;