prism-q 0.35.0

use super::*;
use crate::backend::Backend;
use crate::circuit::plan::Tracer;
use crate::gates::PauliRotData;
use crate::sim::unified_pauli::PauliAxis;
const EPS: f64 = 1e-12;

fn assert_mat_close(actual: &[[Complex64; 2]; 2], expected: &[[Complex64; 2]; 2]) {
    for i in 0..2 {
        for j in 0..2 {
            assert!(
                (actual[i][j] - expected[i][j]).norm() < EPS,
                "[{i}][{j}]: expected {:?}, got {:?}",
                expected[i][j],
                actual[i][j]
            );
        }
    }
}

fn identity_mat() -> [[Complex64; 2]; 2] {
    let zero = Complex64::new(0.0, 0.0);
    let one = Complex64::new(1.0, 0.0);
    [[one, zero], [zero, one]]
}

fn count_fused_2q(circuit: &Circuit) -> usize {
    circuit
        .instructions
        .iter()
        .filter(|inst| {
            matches!(
                inst,
                Instruction::Gate {
                    gate: Gate::Fused2q(_),
                    ..
                }
            )
        })
        .count()
}

#[test]
fn test_mat_mul_identity() {
    let id = identity_mat();
    let h = Gate::H.matrix_2x2();
    assert_mat_close(&mat_mul_2x2(&id, &h), &h);
    assert_mat_close(&mat_mul_2x2(&h, &id), &h);
}

#[test]
fn test_mat_mul_h_h_is_identity() {
    let h = Gate::H.matrix_2x2();
    let result = mat_mul_2x2(&h, &h);
    assert_mat_close(&result, &identity_mat());
}

#[test]
fn test_mat_mul_associative() {
    let a = Gate::Rx(1.0).matrix_2x2();
    let b = Gate::Ry(0.7).matrix_2x2();
    let c = Gate::Rz(2.3).matrix_2x2();
    let ab_c = mat_mul_2x2(&mat_mul_2x2(&a, &b), &c);
    let a_bc = mat_mul_2x2(&a, &mat_mul_2x2(&b, &c));
    assert_mat_close(&ab_c, &a_bc);
}

fn count_fused(circuit: &Circuit) -> usize {
    circuit
        .instructions
        .iter()
        .filter(|i| {
            matches!(
                i,
                Instruction::Gate {
                    gate: Gate::Fused(_),
                    ..
                }
            )
        })
        .count()
}

fn extract_fused_matrix(inst: &Instruction) -> [[Complex64; 2]; 2] {
    match inst {
        Instruction::Gate {
            gate: Gate::Fused(m),
            ..
        } => **m,
        _ => panic!("expected Fused gate"),
    }
}

#[test]
fn test_empty_circuit() {
    let c = Circuit::new(2, 0);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 0);
}

#[test]
fn test_no_fusion_single_gate() {
    let mut c = Circuit::new(1, 0);
    c.add_gate(Gate::H, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 1);
    assert_eq!(count_fused(&fused), 0);
    match &fused.instructions[0] {
        Instruction::Gate {
            gate: Gate::H,
            targets,
        } => assert_eq!(targets.as_slice(), &[0]),
        _ => panic!("expected H gate"),
    }
}

#[test]
fn test_no_fusion_different_qubits() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::X, &[1]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 2);
    assert_eq!(count_fused(&fused), 0);
}

#[test]
fn test_fuse_adjacent_same_qubit() {
    let mut c = Circuit::new(1, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::T, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 1);
    assert_eq!(count_fused(&fused), 1);
    let expected = mat_mul_2x2(&Gate::T.matrix_2x2(), &Gate::H.matrix_2x2());
    let actual = extract_fused_matrix(&fused.instructions[0]);
    assert_mat_close(&actual, &expected);
}

#[test]
fn test_fuse_across_different_qubit() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::X, &[1]);
    c.add_gate(Gate::T, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 2);
    // H·T on q0 stays Fused (no named match), X on q1 recognized as Gate::X
    assert_eq!(count_fused(&fused), 1);

    let expected = mat_mul_2x2(&Gate::T.matrix_2x2(), &Gate::H.matrix_2x2());
    let fused_mat = extract_fused_matrix(&fused.instructions[0]);
    assert_mat_close(&fused_mat, &expected);
}

#[test]
fn test_two_qubit_breaks_run() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::T, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 3);
    assert_eq!(count_fused(&fused), 0);
}

#[test]
fn test_measure_breaks_run() {
    let mut c = Circuit::new(1, 1);
    c.add_gate(Gate::H, &[0]);
    c.add_measure(0, 0);
    c.add_gate(Gate::T, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 3);
    assert_eq!(count_fused(&fused), 0);
}

#[test]
fn test_barrier_breaks_run() {
    let mut c = Circuit::new(1, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_barrier(&[0]);
    c.add_gate(Gate::T, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 3);
    assert_eq!(count_fused(&fused), 0);
}

#[test]
fn test_multiple_qubits_independent() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Ry(1.0), &[0]);
    c.add_gate(Gate::Rz(2.0), &[0]);
    c.add_gate(Gate::Ry(1.0), &[1]);
    c.add_gate(Gate::Rz(2.0), &[1]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 2);
    assert_eq!(count_fused(&fused), 2);
}

#[test]
fn test_long_chain() {
    let mut c = Circuit::new(1, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::S, &[0]);
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::X, &[0]);
    c.add_gate(Gate::Z, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 1);
    assert_eq!(count_fused(&fused), 1);
    let expected = mat_mul_2x2(
        &Gate::Z.matrix_2x2(),
        &mat_mul_2x2(
            &Gate::X.matrix_2x2(),
            &mat_mul_2x2(
                &Gate::T.matrix_2x2(),
                &mat_mul_2x2(&Gate::S.matrix_2x2(), &Gate::H.matrix_2x2()),
            ),
        ),
    );
    let actual = extract_fused_matrix(&fused.instructions[0]);
    assert_mat_close(&actual, &expected);
}

#[test]
fn test_gate_count_after_fusion() {
    let mut c = Circuit::new(2, 1);
    c.add_gate(Gate::Ry(1.0), &[0]);
    c.add_gate(Gate::Rz(2.0), &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::H, &[1]);
    c.add_measure(1, 0);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.gate_count(), 3);
    assert_eq!(fused.instructions.len(), 4);
}

#[test]
fn test_fused_probabilities_match_unfused() {
    use crate::backend::Backend;
    use crate::backend::statevector::StatevectorBackend;

    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::S, &[0]);
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::Ry(1.23), &[1]);
    c.add_gate(Gate::Rz(0.45), &[1]);
    c.add_gate(Gate::H, &[2]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rz(0.78), &[0]);
    c.add_gate(Gate::Rx(2.34), &[0]);
    c.add_gate(Gate::Cz, &[1, 2]);
    c.add_gate(Gate::T, &[2]);
    c.add_gate(Gate::S, &[2]);
    let mut b1 = StatevectorBackend::new(42);
    b1.init(c.num_qubits, c.num_classical_bits).unwrap();
    for inst in &c.instructions {
        b1.apply(inst).unwrap();
    }
    let probs_unfused = b1.probabilities().unwrap();
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    let mut b2 = StatevectorBackend::new(42);
    b2.init(fused.num_qubits, fused.num_classical_bits).unwrap();
    for inst in &fused.instructions {
        b2.apply(inst).unwrap();
    }
    let probs_fused = b2.probabilities().unwrap();

    assert_eq!(probs_unfused.len(), probs_fused.len());
    for (i, (a, b)) in probs_unfused.iter().zip(&probs_fused).enumerate() {
        assert!((a - b).abs() < 1e-10, "prob[{i}]: unfused={a}, fused={b}");
    }
}

#[test]
fn a_hand_built_weight_one_pauli_rotation_fuses_like_the_axis_rotation() {
    use crate::backend::statevector::StatevectorBackend;
    let axes = [PauliAxis::X, PauliAxis::Y, PauliAxis::Z];
    let mut c = Circuit::new(16, 0);
    let mut named = Circuit::new(16, 0);
    for q in 0..16 {
        c.add_gate(Gate::H, &[q]);
        named.add_gate(Gate::H, &[q]);
        let theta = 0.1 * (q as f64 + 1.0);
        let axis = axes[q % 3];
        c.add_gate(
            Gate::PauliRot(Box::new(PauliRotData {
                theta,
                axes: vec![axis],
            })),
            &[q],
        );
        named.add_gate(
            match axis {
                PauliAxis::X => Gate::Rx(theta),
                PauliAxis::Y => Gate::Ry(theta),
                PauliAxis::Z => Gate::Rz(theta),
            },
            &[q],
        );
        c.add_gate(Gate::T, &[q]);
        named.add_gate(Gate::T, &[q]);
    }
    let fused = fuse_circuit(&c, true);
    let fused_named = fuse_circuit(&named, true);
    assert_eq!(fused.instructions.len(), fused_named.instructions.len());
    let mut b1 = StatevectorBackend::new(42);
    b1.init(16, 0).unwrap();
    for inst in &fused.instructions {
        b1.apply(inst).unwrap();
    }
    let mut b2 = StatevectorBackend::new(42);
    b2.init(16, 0).unwrap();
    for inst in &fused_named.instructions {
        b2.apply(inst).unwrap();
    }
    for (a, b) in b1
        .probabilities()
        .unwrap()
        .iter()
        .zip(&b2.probabilities().unwrap())
    {
        assert!((a - b).abs() < 1e-12);
    }
}

#[test]
fn test_hea_style_fusion() {
    let mut c = Circuit::new(4, 0);
    for q in 0..4 {
        c.add_gate(Gate::Ry(0.5 + q as f64), &[q]);
        c.add_gate(Gate::Rz(1.0 + q as f64), &[q]);
    }
    for q in 0..3 {
        c.add_gate(Gate::Cx, &[q, q + 1]);
    }
    for q in 0..4 {
        c.add_gate(Gate::Ry(2.0 + q as f64), &[q]);
        c.add_gate(Gate::Rz(3.0 + q as f64), &[q]);
    }

    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.gate_count(), 11);
    assert_eq!(count_fused(&fused), 8);
    assert_eq!(c.gate_count(), 19);
}

#[test]
fn test_fusion_matrix_order_matters() {
    let mut c_xh = Circuit::new(1, 0);
    c_xh.add_gate(Gate::X, &[0]);
    c_xh.add_gate(Gate::H, &[0]);

    let mut c_hx = Circuit::new(1, 0);
    c_hx.add_gate(Gate::H, &[0]);
    c_hx.add_gate(Gate::X, &[0]);

    let fused_xh = fuse_single_qubit_gates(&c_xh, &mut Tracer::off());
    let fused_hx = fuse_single_qubit_gates(&c_hx, &mut Tracer::off());

    let mat_xh = extract_fused_matrix(&fused_xh.instructions[0]);
    let mat_hx = extract_fused_matrix(&fused_hx.instructions[0]);
    let differs = (0..2).any(|i| (0..2).any(|j| (mat_xh[i][j] - mat_hx[i][j]).norm() > EPS));
    assert!(
        differs,
        "X·H and H·X should produce different fused matrices"
    );
    let expected_xh = mat_mul_2x2(&Gate::H.matrix_2x2(), &Gate::X.matrix_2x2());
    assert_mat_close(&mat_xh, &expected_xh);

    let expected_hx = mat_mul_2x2(&Gate::X.matrix_2x2(), &Gate::H.matrix_2x2());
    assert_mat_close(&mat_hx, &expected_hx);
}

#[test]
fn test_s_squared_is_z_via_fusion() {
    let mut c = Circuit::new(1, 0);
    c.add_gate(Gate::S, &[0]);
    c.add_gate(Gate::S, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 1);
    // S·S recognized as Gate::Z
    assert!(matches!(
        &fused.instructions[0],
        Instruction::Gate { gate: Gate::Z, .. }
    ));
}

#[test]
fn test_t_tdg_cancel_via_fusion() {
    let mut c = Circuit::new(1, 0);
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::Tdg, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 0);
}

#[test]
fn test_identity_elision_h_h() {
    let mut c = Circuit::new(1, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::H, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 0);
}

#[test]
fn test_identity_elision_partial() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::T, &[1]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 1);
    // H·H on q0 elided, lone T on q1 recognized as Gate::T
    assert!(matches!(
        &fused.instructions[0],
        Instruction::Gate { gate: Gate::T, .. }
    ));
}

#[test]
fn test_identity_elision_preserves_probabilities() {
    use crate::backend::Backend;
    use crate::backend::statevector::StatevectorBackend;

    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Ry(0.7), &[1]);
    c.add_gate(Gate::Rz(1.3), &[1]);

    let mut b1 = StatevectorBackend::new(42);
    b1.init(2, 0).unwrap();
    for inst in &c.instructions {
        b1.apply(inst).unwrap();
    }
    let p1 = b1.probabilities().unwrap();

    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 1);

    let mut b2 = StatevectorBackend::new(42);
    b2.init(2, 0).unwrap();
    for inst in &fused.instructions {
        b2.apply(inst).unwrap();
    }
    let p2 = b2.probabilities().unwrap();

    for (i, (a, b)) in p1.iter().zip(&p2).enumerate() {
        assert!((a - b).abs() < 1e-12, "prob[{i}]: unfused={a}, fused={b}");
    }
}

#[test]
fn test_cphase_breaks_fusion_run() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Rz(0.5), &[0]);
    c.add_gate(Gate::cphase(0.3), &[0, 1]);
    c.add_gate(Gate::T, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 3);
    assert_eq!(count_fused(&fused), 0);
}

#[test]
fn test_fusion_around_cphase() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::cphase(0.5), &[0, 1]);
    c.add_gate(Gate::S, &[0]);
    c.add_gate(Gate::X, &[0]);
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 3);
    assert_eq!(count_fused(&fused), 2);
}

#[test]
fn test_cphase_fused_probabilities_match() {
    use crate::backend::Backend;
    use crate::backend::statevector::StatevectorBackend;
    use crate::sim;

    let n = 4;
    let mut c = Circuit::new(n, 0);
    for i in 0..n {
        c.add_gate(Gate::H, &[i]);
        for j in (i + 1)..n {
            let theta = std::f64::consts::TAU / (1u64 << (j - i)) as f64;
            c.add_gate(Gate::cphase(theta), &[i, j]);
        }
    }
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::S, &[0]);

    let fused_circuit = fuse_single_qubit_gates(&c, &mut Tracer::off());

    let mut b1 = StatevectorBackend::new(42);
    sim::run_on(&mut b1, &c).unwrap();
    let p1 = b1.probabilities().unwrap();

    let mut b2 = StatevectorBackend::new(42);
    b2.init(n, 0).unwrap();
    for inst in &fused_circuit.instructions {
        b2.apply(inst).unwrap();
    }
    let p2 = b2.probabilities().unwrap();

    for (i, (a, b)) in p1.iter().zip(p2.iter()).enumerate() {
        assert!((*a - *b).abs() < EPS, "prob[{i}]: unfused={a}, fused={b}");
    }
}

#[test]
fn test_cancel_adjacent_cx() {
    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Cx, &[0, 1]);
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    assert!(matches!(result, Cow::Owned(_)));
    assert_eq!(result.instructions.len(), 0);
}

#[test]
fn test_cancel_cx_with_non_conflicting_between() {
    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::H, &[2]); // doesn't touch q0 or q1
    c.add_gate(Gate::Cx, &[0, 1]);
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    assert!(matches!(result, Cow::Owned(_)));
    assert_eq!(result.instructions.len(), 1); // only H(2) remains
}

#[test]
fn test_no_cancel_cx_with_conflicting_between() {
    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::H, &[0]); // touches q0, breaks the chain
    c.add_gate(Gate::Cx, &[0, 1]);
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    // No cancellation, H on q0 intervenes
    assert_eq!(result.instructions.len(), 3);
}

#[test]
fn test_no_cancel_cx_reversed_targets() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Cx, &[1, 0]); // reversed, CX is NOT symmetric
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    assert_eq!(result.instructions.len(), 2);
}

#[test]
fn test_cancel_cz_symmetric() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Cz, &[0, 1]);
    c.add_gate(Gate::Cz, &[1, 0]); // reversed, CZ IS symmetric
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    assert_eq!(result.instructions.len(), 0);
}

#[test]
fn test_cancel_swap_symmetric() {
    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::Swap, &[0, 1]);
    c.add_gate(Gate::H, &[2]);
    c.add_gate(Gate::Swap, &[1, 0]); // reversed order
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    assert_eq!(result.instructions.len(), 1); // only H(2)
}

#[test]
fn test_cancel_multiple_pairs() {
    let mut c = Circuit::new(4, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Cx, &[2, 3]);
    c.add_gate(Gate::Cx, &[2, 3]);
    c.add_gate(Gate::Cx, &[0, 1]);
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    assert_eq!(result.instructions.len(), 0);
}

#[test]
fn test_cancel_no_candidates() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::T, &[1]);
    let result = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    assert!(matches!(result, Cow::Borrowed(_)));
}

#[test]
fn test_cancel_preserves_probabilities() {
    use crate::backend::Backend;
    use crate::backend::statevector::StatevectorBackend;

    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::T, &[2]);
    c.add_gate(Gate::Cx, &[0, 1]); // cancels with the first CX
    c.add_gate(Gate::H, &[1]);

    let mut b1 = StatevectorBackend::new(42);
    b1.init(3, 0).unwrap();
    for inst in &c.instructions {
        b1.apply(inst).unwrap();
    }
    let p1 = b1.probabilities().unwrap();

    let cancelled = cancel_self_inverse_pairs(&c, &mut Tracer::off());
    let mut b2 = StatevectorBackend::new(42);
    b2.init(3, 0).unwrap();
    for inst in &cancelled.instructions {
        b2.apply(inst).unwrap();
    }
    let p2 = b2.probabilities().unwrap();

    for (i, (a, b)) in p1.iter().zip(&p2).enumerate() {
        assert!(
            (a - b).abs() < 1e-12,
            "prob[{i}]: original={a}, cancelled={b}"
        );
    }
}

#[test]
fn test_reorder_1q_basic() {
    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::Fused(Box::new(Gate::H.matrix_2x2())), &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Fused(Box::new(Gate::T.matrix_2x2())), &[2]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(result, Cow::Owned(_)));
    assert_eq!(result.instructions.len(), 3);
    assert!(
        result.instructions[0..2].iter().all(|i| matches!(
            i,
            Instruction::Gate {
                gate: Gate::Fused(_),
                ..
            }
        )),
        "first two instructions should be 1q Fused gates"
    );
    let targets: Vec<usize> = result.instructions[0..2]
        .iter()
        .map(|i| match i {
            Instruction::Gate { targets, .. } => targets[0],
            _ => unreachable!(),
        })
        .collect();
    assert!(targets.contains(&0) && targets.contains(&2));
    assert!(matches!(
        &result.instructions[2],
        Instruction::Gate { gate: Gate::Cx, .. }
    ));
}

#[test]
fn test_reorder_no_opportunity() {
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Fused(Box::new(Gate::H.matrix_2x2())), &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Fused(Box::new(Gate::T.matrix_2x2())), &[1]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(result, Cow::Borrowed(_)));
}

#[test]
fn test_reorder_hea_pattern() {
    let mut c = Circuit::new(4, 0);
    let fused = |angle: f64| Gate::Fused(Box::new(Gate::Ry(angle).matrix_2x2()));
    c.add_gate(fused(0.1), &[0]);
    c.add_gate(fused(0.2), &[1]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(fused(0.3), &[2]);
    c.add_gate(Gate::Cx, &[1, 2]);
    c.add_gate(fused(0.4), &[3]);
    c.add_gate(Gate::Cx, &[2, 3]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert_eq!(result.instructions.len(), 7);
    for i in 0..4 {
        assert!(
            matches!(
                &result.instructions[i],
                Instruction::Gate { gate, .. } if gate.num_qubits() == 1
            ),
            "instruction {i} should be 1q gate"
        );
    }
    for i in 4..7 {
        assert!(
            matches!(
                &result.instructions[i],
                Instruction::Gate { gate: Gate::Cx, .. }
            ),
            "instruction {i} should be CX"
        );
    }
}

#[test]
fn test_reorder_preserves_probabilities() {
    use crate::backend::Backend;
    use crate::backend::statevector::StatevectorBackend;

    let mut c = Circuit::new(4, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Ry(1.2), &[1]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rz(0.8), &[2]);
    c.add_gate(Gate::Cx, &[1, 2]);
    c.add_gate(Gate::T, &[3]);
    c.add_gate(Gate::Cx, &[2, 3]);
    c.add_gate(Gate::H, &[0]);

    let mut b1 = StatevectorBackend::new(42);
    b1.init(4, 0).unwrap();
    for inst in &c.instructions {
        b1.apply(inst).unwrap();
    }
    let p1 = b1.probabilities().unwrap();

    let reordered = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    let mut b2 = StatevectorBackend::new(42);
    b2.init(4, 0).unwrap();
    for inst in &reordered.instructions {
        b2.apply(inst).unwrap();
    }
    let p2 = b2.probabilities().unwrap();

    for (i, (a, b)) in p1.iter().zip(&p2).enumerate() {
        assert!(
            (a - b).abs() < 1e-12,
            "prob[{i}]: original={a}, reordered={b}"
        );
    }
}

#[test]
fn test_reorder_respects_barrier() {
    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_barrier(&[0, 1, 2]);
    c.add_gate(Gate::T, &[2]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(result, Cow::Borrowed(_)));
}

#[test]
fn test_reorder_diagonal_commutes_through_cx_control() {
    // Rz(0) should move past CX(0,1) since diagonal commutes on control
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rz(0.5), &[0]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(result, Cow::Owned(_)));
    assert_eq!(result.instructions.len(), 2);
    assert!(matches!(
        &result.instructions[0],
        Instruction::Gate {
            gate: Gate::Rz(_),
            targets
        } if targets[0] == 0
    ));
    assert!(matches!(
        &result.instructions[1],
        Instruction::Gate { gate: Gate::Cx, .. }
    ));
}

#[test]
fn test_reorder_nondiagonal_blocked_by_cx_control() {
    // H(0) should NOT move past CX(0,1), H is not diagonal
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::H, &[0]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    // No reorder, H is blocked by CX on q0
    assert!(matches!(result, Cow::Borrowed(_)));
}

#[test]
fn test_reorder_diagonal_blocked_on_cx_target() {
    // Rz(1) should NOT move past CX(0,1), q1 is the target
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rz(0.5), &[1]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(result, Cow::Borrowed(_)));
}

#[test]
fn test_reorder_diagonal_commutes_through_cz() {
    // T(0) and T(1) should both move past CZ(0,1), diagonal commutes
    let mut c = Circuit::new(2, 0);
    c.add_gate(Gate::Cz, &[0, 1]);
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::S, &[1]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(result, Cow::Owned(_)));
    assert_eq!(result.instructions.len(), 3);
    // Both diagonal gates should precede CZ
    assert!(
        result.instructions[0..2]
            .iter()
            .all(|i| matches!(i, Instruction::Gate { gate, .. } if gate.num_qubits() == 1))
    );
    assert!(matches!(
        &result.instructions[2],
        Instruction::Gate { gate: Gate::Cz, .. }
    ));
}

#[test]
fn test_reorder_commutation_preserves_probabilities() {
    use crate::backend::Backend;
    use crate::backend::statevector::StatevectorBackend;

    let mut c = Circuit::new(3, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rz(0.7), &[0]); // diagonal on CX control, commutes
    c.add_gate(Gate::Cz, &[1, 2]);
    c.add_gate(Gate::T, &[1]); // diagonal, commutes through CZ
    c.add_gate(Gate::S, &[2]); // diagonal, commutes through CZ

    let mut b1 = StatevectorBackend::new(42);
    b1.init(3, 0).unwrap();
    for inst in &c.instructions {
        b1.apply(inst).unwrap();
    }
    let p1 = b1.probabilities().unwrap();

    let reordered = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    let mut b2 = StatevectorBackend::new(42);
    b2.init(3, 0).unwrap();
    for inst in &reordered.instructions {
        b2.apply(inst).unwrap();
    }
    let p2 = b2.probabilities().unwrap();

    for (i, (a, b)) in p1.iter().zip(&p2).enumerate() {
        assert!(
            (a - b).abs() < 1e-12,
            "prob[{i}]: original={a}, reordered={b}"
        );
    }
}

#[test]
fn test_reorder_respects_measurement() {
    let mut c = Circuit::new(2, 1);
    c.add_gate(Gate::H, &[0]);
    c.add_measure(0, 0);
    c.add_gate(Gate::T, &[1]);

    let result = reorder_1q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(result, Cow::Owned(_)));
    assert_eq!(result.instructions.len(), 3);
    assert!(
        result.instructions[0..2]
            .iter()
            .all(|i| matches!(i, Instruction::Gate { .. })),
        "first two instructions should be 1q gates"
    );
    let targets: Vec<usize> = result.instructions[0..2]
        .iter()
        .map(|i| match i {
            Instruction::Gate { targets, .. } => targets[0],
            _ => unreachable!(),
        })
        .collect();
    assert!(targets.contains(&0) && targets.contains(&1));
    assert!(matches!(
        &result.instructions[2],
        Instruction::Measure { .. }
    ));
}

#[test]
fn test_smart_multi_fusion_across_cx() {
    let mut c = Circuit::new(4, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::T, &[2]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::S, &[2]);
    c.add_gate(Gate::Rx(1.0), &[3]);

    let pass1 = fuse_single_qubit_gates(&c, &mut Tracer::off());
    let pass2 = fuse_multi_1q_gates(pass1, &mut Tracer::off());

    let multi_count = pass2
        .instructions
        .iter()
        .filter(|i| {
            matches!(
                i,
                Instruction::Gate {
                    gate: Gate::MultiFused(_),
                    ..
                }
            )
        })
        .count();
    assert_eq!(
        multi_count, 1,
        "q2 and q3 gates should accumulate across CX(q0,q1) into one MultiFused"
    );

    if let Instruction::Gate {
        gate: Gate::MultiFused(data),
        ..
    } = &pass2.instructions.last().unwrap()
    {
        let targets: Vec<usize> = data.gates.iter().map(|&(t, _)| t).collect();
        assert!(targets.contains(&2), "q2 should be in the MultiFused batch");
        assert!(targets.contains(&3), "q3 should be in the MultiFused batch");
    } else {
        panic!("last instruction should be MultiFused");
    }

    let mut b1 = crate::backend::statevector::StatevectorBackend::new(42);
    b1.init(c.num_qubits, 0).unwrap();
    for inst in &c.instructions {
        b1.apply(inst).unwrap();
    }
    let probs1 = b1.probabilities().unwrap();

    let mut b2 = crate::backend::statevector::StatevectorBackend::new(42);
    b2.init(pass2.num_qubits, 0).unwrap();
    for inst in &pass2.instructions {
        b2.apply(inst).unwrap();
    }
    let probs2 = b2.probabilities().unwrap();

    for (a, b) in probs1.iter().zip(probs2.iter()) {
        assert!(
            (*a - *b).abs() < 1e-12,
            "probabilities must match: {a} vs {b}"
        );
    }
}

#[test]
fn reorder_exposes_cx_cancellation() {
    // CX q0,q1; T q0; CX q0,q1. T is diagonal on CX control,
    // reorder moves it past CX, exposing CX·CX cancellation.
    let mut c = Circuit::new(10, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);

    let fused = fuse_circuit(&c, true);
    // CX pair cancelled; only T (as Fused) on q0 remains
    let gate_count = fused
        .instructions
        .iter()
        .filter(|i| matches!(i, Instruction::Gate { .. }))
        .count();
    assert_eq!(gate_count, 1, "CX pair should cancel after reorder");
}

#[test]
fn reorder_exposes_1q_fusion() {
    // H q0; CZ q0,q1; T q0. T is diagonal, commutes through CZ on either qubit.
    // After reorder: H q0; T q0; CZ q0,q1. H and T fuse.
    let mut c = Circuit::new(10, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Cz, &[0, 1]);
    c.add_gate(Gate::T, &[0]);

    let fused = fuse_circuit(&c, true);
    let gates: Vec<_> = fused
        .instructions
        .iter()
        .filter_map(|i| match i {
            Instruction::Gate { gate, targets } => Some((gate.clone(), targets.clone())),
            _ => None,
        })
        .collect();
    // Should be: Fused(H·T) on q0, CZ on q0,q1
    assert_eq!(gates.len(), 2, "H and T should fuse after reorder");
    assert!(
        matches!(&gates[0].0, Gate::Fused(_)),
        "first gate should be Fused(H·T)"
    );
    assert!(matches!(&gates[1].0, Gate::Cz), "second gate should be CZ");

    // Verify fused matrix = T · H (T applied after H)
    let t_mat = Gate::T.matrix_2x2();
    let h_mat = Gate::H.matrix_2x2();
    let expected = mat_mul_2x2(&t_mat, &h_mat);
    if let Gate::Fused(mat) = &gates[0].0 {
        assert_mat_close(mat, &expected);
    }
}

#[test]
fn reorder_exposes_cz_cancellation() {
    // CZ q0,q1; S q0; CZ q0,q1. S is diagonal, commutes through CZ.
    // After reorder: S q0; CZ q0,q1; CZ q0,q1 → CZ pair cancels.
    let mut c = Circuit::new(10, 0);
    c.add_gate(Gate::Cz, &[0, 1]);
    c.add_gate(Gate::S, &[0]);
    c.add_gate(Gate::Cz, &[0, 1]);

    let fused = fuse_circuit(&c, true);
    let gate_count = fused
        .instructions
        .iter()
        .filter(|i| matches!(i, Instruction::Gate { .. }))
        .count();
    assert_eq!(gate_count, 1, "CZ pair should cancel after reorder");
}

#[test]
fn same_pair_2q_block_fuses_w_state_pairs() {
    let circuit = crate::circuits::w_state_circuit(20);
    let pass_2q = fuse_2q_gates(Cow::Borrowed(&circuit), &mut Tracer::off());
    let before = count_fused_2q(&pass_2q);
    let fused = fuse_same_pair_2q_blocks(pass_2q, &mut Tracer::off());
    let after = count_fused_2q(&fused);

    assert!(before >= 2, "w-state should expose paired Fused2q gates");
    assert!(
        after < before,
        "same-pair block fusion should reduce Fused2q count"
    );
}

#[test]
fn same_pair_2q_block_fuses_qv_blocks() {
    let circuit = crate::circuits::quantum_volume_circuit(20, 1, 42);
    let pass_2q = fuse_2q_gates(Cow::Borrowed(&circuit), &mut Tracer::off());
    let before = count_fused_2q(&pass_2q);
    let fused = fuse_same_pair_2q_blocks(pass_2q, &mut Tracer::off());
    let after = count_fused_2q(&fused);

    assert!(before >= 2, "qv block should expose paired Fused2q gates");
    assert!(
        after < before,
        "same-pair block fusion should reduce Fused2q count"
    );
}

#[test]
fn same_pair_2q_block_accepts_reversed_targets() {
    let mut circuit = Circuit::new(20, 0);
    circuit.add_gate(Gate::H, &[0]);
    circuit.add_gate(Gate::Cx, &[0, 1]);
    circuit.add_gate(Gate::Ry(0.7), &[1]);
    circuit.add_gate(Gate::Cx, &[1, 0]);

    let pass_2q = fuse_2q_gates(Cow::Borrowed(&circuit), &mut Tracer::off());
    let before = count_fused_2q(&pass_2q);
    let fused = fuse_same_pair_2q_blocks(pass_2q, &mut Tracer::off());
    let after = count_fused_2q(&fused);

    assert_eq!(before, 2);
    assert_eq!(after, 1, "reversed pair order should still fuse");
    assert!(matches!(
        &fused.instructions[0],
        Instruction::Gate {
            gate: Gate::Fused2q(_),
            targets
        } if targets.as_slice() == [0, 1]
    ));
}

#[test]
fn same_pair_2q_block_leaves_diagonal_runs() {
    let mut circuit = Circuit::new(20, 0);
    circuit.add_gate(Gate::Rz(0.3), &[0]);
    circuit.add_gate(Gate::Cz, &[0, 1]);
    circuit.add_gate(Gate::T, &[1]);
    circuit.add_gate(Gate::Cz, &[1, 0]);

    let pass_2q = fuse_2q_gates(Cow::Borrowed(&circuit), &mut Tracer::off());
    let before = count_fused_2q(&pass_2q);
    let fused = fuse_same_pair_2q_blocks(pass_2q, &mut Tracer::off());
    let after = count_fused_2q(&fused);

    assert_eq!(before, 2);
    assert_eq!(after, 2, "all-diagonal Fused2q runs should stay split");
}

fn final_state(circuit: &Circuit) -> Vec<Complex64> {
    use crate::backend::statevector::StatevectorBackend;
    let mut b = StatevectorBackend::new(42);
    b.init(circuit.num_qubits, circuit.num_classical_bits)
        .unwrap();
    for inst in &circuit.instructions {
        b.apply(inst).unwrap();
    }
    b.export_statevector().unwrap()
}

fn assert_same_state(a: &Circuit, b: &Circuit) {
    for (i, (x, y)) in final_state(a).iter().zip(&final_state(b)).enumerate() {
        assert!((x - y).norm() < 1e-12, "amp[{i}]: {x} vs {y}");
    }
}

#[test]
fn trailing_1q_folds_back_into_its_fused2q_on_either_target() {
    let mut c = Circuit::new(12, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rx(0.3), &[2]);
    c.add_gate(Gate::Cx, &[2, 3]);
    c.add_gate(Gate::Ry(0.4), &[0]);
    c.add_gate(Gate::Ry(0.9), &[3]);

    let fused = fuse_2q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 2);
    assert_eq!(count_fused_2q(&fused), 2);
    assert_same_state(&c, &fused);
}

#[test]
fn trailing_1q_does_not_fold_past_a_later_gate_on_its_qubit() {
    let mut c = Circuit::new(12, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Cx, &[0, 2]);
    c.add_gate(Gate::Ry(0.4), &[0]);

    let fused = fuse_2q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert!(matches!(
        fused.instructions.last(),
        Some(Instruction::Gate { gate: Gate::Fused(_), targets }) if targets.as_slice() == [0]
    ));
    assert_same_state(&c, &fused);
}

#[test]
fn trailing_1q_keeps_a_diagonal_fused2q_diagonal() {
    let mut c = Circuit::new(12, 0);
    c.add_gate(Gate::Rz(0.3), &[0]);
    c.add_gate(Gate::Cz, &[0, 1]);
    c.add_gate(Gate::T, &[1]);
    c.add_gate(Gate::Ry(0.4), &[0]);

    let fused = fuse_2q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    assert_eq!(fused.instructions.len(), 2, "T folds, Ry stays out");
    let Instruction::Gate {
        gate: Gate::Fused2q(m),
        ..
    } = &fused.instructions[0]
    else {
        panic!("expected a Fused2q first");
    };
    assert!(is_diagonal_4x4(m));
    assert_same_state(&c, &fused);
}

#[test]
fn qv_leaves_no_1q_gate_after_fusion() {
    let c = crate::circuits::quantum_volume_circuit(20, 3, 42);
    let fused = fuse_circuit(&c, true);
    for inst in &fused.instructions {
        assert!(
            matches!(
                inst,
                Instruction::Gate {
                    gate: Gate::Fused2q(_) | Gate::Multi2q(_),
                    ..
                }
            ),
            "{inst:?}"
        );
    }
}

#[test]
fn fuse_1q_returns_borrowed_without_consecutive_pair() {
    let mut c = Circuit::new(12, 0);
    c.add_gate(Gate::H, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rx(0.3), &[0]);
    assert!(matches!(
        fuse_single_qubit_gates(&c, &mut Tracer::off()),
        Cow::Borrowed(_)
    ));
}

#[test]
fn fuse_2q_returns_borrowed_without_absorbable_1q() {
    let mut c = Circuit::new(12, 0);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Cz, &[1, 2]);
    assert!(matches!(
        fuse_2q_gates(Cow::Borrowed(&c), &mut Tracer::off()),
        Cow::Borrowed(_)
    ));
}

#[test]
fn fuse_multi_2q_returns_borrowed_without_tileable_run() {
    let mut c = Circuit::new(20, 0);
    c.add_gate(Gate::Fused2q(Box::new(Gate::Cx.matrix_4x4())), &[0, 1]);
    c.add_gate(Gate::H, &[2]);
    c.add_gate(Gate::Fused2q(Box::new(Gate::Cz.matrix_4x4())), &[2, 3]);
    assert!(matches!(
        fuse_multi_2q_gates(Cow::Borrowed(&c), &mut Tracer::off()),
        Cow::Borrowed(_)
    ));
}

#[test]
fn tile_reorder_pulls_later_gates_ahead_of_a_skipped_gate_on_other_qubits() {
    // Shaped from the host's tile budget: `fill` disjoint pairs take the whole
    // high-qubit budget, the next pair brings two new qubits and is skipped, and
    // two later gates inside the tile are pulled ahead of it.
    let base = crate::gates::multi_2q_low_bits();
    let fill = crate::gates::multi_2q_high_budget_for(20) / 2;
    let top = base + 2 * fill;
    let mut pairs: Vec<(usize, usize)> = (0..fill)
        .map(|i| (base + 2 * i, base + 2 * i + 1))
        .collect();
    pairs.extend([
        (top, top + 1),
        (base, base + 2),
        (top, base),
        (base + 1, base + 3),
        (base, base + 1),
    ]);
    let prelude = top + 2 - base;
    let mut c = Circuit::new(20.max(top + 2), 0);
    for q in base..top + 2 {
        c.add_gate(Gate::Ry(0.1 * q as f64 + 0.2), &[q]);
    }
    for (k, &(a, b)) in pairs.iter().enumerate() {
        let gate = if k % 2 == 0 { Gate::Cx } else { Gate::Swap };
        c.add_gate(Gate::Fused2q(Box::new(gate.matrix_4x4())), &[a, b]);
    }
    let reordered = reorder_fused2q_into_tiles(Cow::Borrowed(&c), &mut Tracer::off());
    let order: Vec<(usize, usize)> = reordered.instructions[prelude..]
        .iter()
        .map(|inst| match inst {
            Instruction::Gate { targets, .. } => (targets[0], targets[1]),
            other => panic!("{other:?}"),
        })
        .collect();
    let expect: Vec<(usize, usize)> = (0..fill)
        .chain([fill + 1, fill + 3, fill, fill + 2, fill + 4])
        .map(|k| pairs[k])
        .collect();
    assert_eq!(order, expect);
    assert_same_state(&c, &reordered);
}

#[test]
fn multi_2q_batches_bare_cx_and_swap_with_fused_gates() {
    let mut c = Circuit::new(20, 0);
    for q in 0..20 {
        c.add_gate(Gate::Ry(0.05 * q as f64 + 0.1), &[q]);
    }
    let dense = Gate::Fused2q(Box::new(mat_mul_4x4(
        &Gate::Cx.matrix_4x4(),
        &kron_2x2(&Gate::H.matrix_2x2(), &Gate::S.matrix_2x2()),
    )));
    c.add_gate(dense.clone(), &[6, 7]);
    c.add_gate(Gate::Cx, &[7, 8]);
    c.add_gate(Gate::Swap, &[8, 9]);
    c.add_gate(dense, &[9, 10]);
    let batched = fuse_multi_2q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    let tail: Vec<&str> = batched.instructions[20..]
        .iter()
        .map(|inst| match inst {
            Instruction::Gate { gate, .. } => gate.name(),
            other => panic!("{other:?}"),
        })
        .collect();
    assert_eq!(tail, ["multi_2q"]);
    assert_same_state(&c, &batched);
}

#[test]
fn multi_2q_keeps_a_lone_cx_on_its_own_kernel() {
    let mut c = Circuit::new(20, 0);
    c.add_gate(Gate::Cx, &[6, 7]);
    c.add_gate(Gate::Swap, &[7, 8]);
    c.add_gate(Gate::H, &[9]);
    c.add_gate(Gate::Cx, &[9, 10]);
    let batched = fuse_multi_2q_gates(Cow::Borrowed(&c), &mut Tracer::off());
    let names: Vec<&str> = batched
        .instructions
        .iter()
        .map(|inst| match inst {
            Instruction::Gate { gate, .. } => gate.name(),
            other => panic!("{other:?}"),
        })
        .collect();
    assert_eq!(names, ["multi_2q", "h", "cx"]);
}

#[test]
fn fuse_controlled_phases_returns_borrowed_without_batchable_chain() {
    let one = Complex64::new(1.0, 0.0);
    let zero = Complex64::new(0.0, 0.0);
    let phase = Complex64::new(0.0, 1.0);
    let mut c = Circuit::new(20, 0);
    c.add_gate(Gate::cu([[one, zero], [zero, phase]]), &[0, 1]);
    c.add_gate(Gate::Cx, &[2, 3]);
    assert!(matches!(
        fuse_controlled_phases(Cow::Borrowed(&c), &mut Tracer::off()),
        Cow::Borrowed(_)
    ));
}

#[test]
fn qaoa_20q_fuses_to_6_instructions() {
    let circuit = crate::circuits::qaoa_circuit(20, 3, 0xDEAD_BEEF);
    let fused = fuse_circuit(&circuit, true);
    assert_eq!(fused.instructions.len(), 6);

    let batch_rzz_count = fused
        .instructions
        .iter()
        .filter(|i| {
            matches!(
                i,
                Instruction::Gate {
                    gate: Gate::BatchRzz(_),
                    ..
                }
            )
        })
        .count();
    let multi_fused_count = fused
        .instructions
        .iter()
        .filter(|i| {
            matches!(
                i,
                Instruction::Gate {
                    gate: Gate::MultiFused(_),
                    ..
                }
            )
        })
        .count();
    assert_eq!(batch_rzz_count, 3);
    assert_eq!(multi_fused_count, 3);
}

#[test]
fn qv_12_uses_multi_2q_fusion() {
    let circuit = crate::circuits::quantum_volume_circuit(12, 1, 42);
    let fused = fuse_circuit(&circuit, true);
    let multi_2q_count = fused
        .instructions
        .iter()
        .filter(|i| {
            matches!(
                i,
                Instruction::Gate {
                    gate: Gate::Multi2q(_),
                    ..
                }
            )
        })
        .count();
    assert!(multi_2q_count > 0, "QV 12q should use Multi2q fusion");
}

#[test]
fn qv_20_batches_fit_one_subcube_tile() {
    use crate::gates::{multi_2q_high_budget_for, multi_2q_low_bits};
    let circuit = crate::circuits::quantum_volume_circuit(20, 20, 42);
    let fused = fuse_circuit(&circuit, true);
    let mut batches = 0usize;
    let mut batched_gates = 0usize;
    let mut lone = 0usize;
    for inst in &fused.instructions {
        match inst {
            Instruction::Gate {
                gate: Gate::Multi2q(data),
                ..
            } => {
                let mut high: Vec<usize> = data
                    .gates
                    .iter()
                    .flat_map(|&(q0, q1, _)| [q0, q1])
                    .filter(|&q| q >= multi_2q_low_bits())
                    .collect();
                high.sort_unstable();
                high.dedup();
                assert!(
                    high.len() <= multi_2q_high_budget_for(20),
                    "batch spans {high:?}"
                );
                batches += 1;
                batched_gates += data.gates.len();
            }
            Instruction::Gate {
                gate: Gate::Fused2q(_),
                ..
            } => lone += 1,
            _ => {}
        }
    }
    assert_eq!(batched_gates + lone, 200);
    // Ten disjoint pairs per layer pack into a few tiles, not one sweep each.
    assert!(
        batches + lone <= 80,
        "{batches} batches and {lone} lone gates"
    );
}

#[test]
fn test_recognition_extends_clifford_prefix() {
    let mut c = Circuit::new(2, 0);
    // T, T on q0 then CX then Rx on q1
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::T, &[0]);
    c.add_gate(Gate::Cx, &[0, 1]);
    c.add_gate(Gate::Rx(0.7), &[1]);

    // Without fusion: first gate is T (non-Clifford), so no prefix at all
    assert!(c.clifford_prefix_split().is_none());

    // After fusion: T·T recognized as S (Clifford), so prefix = [S, CX], tail = [Rx]
    let fused = fuse_single_qubit_gates(&c, &mut Tracer::off());
    assert!(matches!(
        &fused.instructions[0],
        Instruction::Gate { gate: Gate::S, .. }
    ));
    let split = fused.clifford_prefix_split();
    assert!(split.is_some());
    let (pre_f, tail_f) = split.unwrap();
    assert_eq!(pre_f.instructions.len(), 2); // S + CX
    assert_eq!(tail_f.instructions.len(), 1); // Rx(0.7)
}

fn fused_rotation_counts(circuit: &Circuit) -> Vec<(&'static str, usize)> {
    fuse_circuit(circuit, true)
        .instructions
        .iter()
        .filter_map(|inst| match inst {
            Instruction::Gate {
                gate: Gate::MultiPauliRot(data),
                ..
            } => Some(("multi_pauli_rot", data.rotations.len())),
            Instruction::Gate {
                gate: Gate::PauliRot(_),
                ..
            } => Some(("pauli_rot", 1)),
            _ => None,
        })
        .collect()
}

#[test]
fn pauli_rotations_batch_while_their_xy_qubits_fit_a_tile() {
    use crate::gates::{multi_2q_high_budget_for, multi_2q_low_bits};
    use crate::sim::unified_pauli::PauliTerm;
    let n = 20;
    let budget = multi_2q_high_budget_for(n);
    let low = multi_2q_low_bits();
    let mut c = Circuit::new(n, 0);
    c.add_pauli_rotation(0.3, &[PauliTerm::x(0), PauliTerm::x(1), PauliTerm::z(19)]);
    // Each string brings one new high X qubit; the one past the budget opens a run.
    for k in 0..=budget {
        c.add_pauli_rotation(
            0.1 + 0.01 * k as f64,
            &[PauliTerm::y(0), PauliTerm::x(low + k), PauliTerm::z(19)],
        );
    }
    assert_eq!(
        fused_rotation_counts(&c),
        vec![("multi_pauli_rot", budget + 1), ("pauli_rot", 1)]
    );
}

#[test]
fn z_letters_never_count_against_the_tile_budget() {
    use crate::sim::unified_pauli::PauliTerm;
    let n = 20;
    let mut c = Circuit::new(n, 0);
    for k in 6..17 {
        c.add_pauli_rotation(
            0.2,
            &[
                PauliTerm::x(0),
                PauliTerm::y(1),
                PauliTerm::z(k),
                PauliTerm::z(k + 1),
                PauliTerm::z(k + 3),
            ],
        );
    }
    assert_eq!(fused_rotation_counts(&c), vec![("multi_pauli_rot", 11)]);
}

#[test]
fn a_string_wider_than_the_tile_stays_native_and_splits_the_run() {
    use crate::gates::{multi_2q_high_budget_for, multi_2q_low_bits};
    use crate::sim::unified_pauli::PauliTerm;
    let n = 20;
    let low = multi_2q_low_bits();
    let wide: Vec<PauliTerm> = (low..=low + multi_2q_high_budget_for(n))
        .map(PauliTerm::x)
        .collect();
    let narrow = [PauliTerm::x(0), PauliTerm::y(2), PauliTerm::z(18)];
    let mut c = Circuit::new(n, 0);
    c.add_pauli_rotation(0.1, &narrow);
    c.add_pauli_rotation(0.2, &narrow);
    c.add_pauli_rotation(0.3, &wide);
    c.add_pauli_rotation(0.4, &narrow);
    c.add_pauli_rotation(0.5, &narrow);
    assert_eq!(
        fused_rotation_counts(&c),
        vec![
            ("multi_pauli_rot", 2),
            ("pauli_rot", 1),
            ("multi_pauli_rot", 2)
        ]
    );
}

#[test]
fn pauli_rotations_stay_native_below_the_batch_floor() {
    use crate::sim::unified_pauli::PauliTerm;
    let n = MIN_QUBITS_FOR_PAULI_ROT_BATCH - 1;
    let mut c = Circuit::new(n, 0);
    for q in 0..n - 2 {
        c.add_pauli_rotation(
            0.2,
            &[PauliTerm::x(q), PauliTerm::y(q + 1), PauliTerm::z(q + 2)],
        );
    }
    assert!(
        fused_rotation_counts(&c)
            .iter()
            .all(|&(name, _)| name == "pauli_rot")
    );
}

// The producer's packing check has to agree with the kernel's, or a batch it emits
// runs every entry per amplitude on the fallback path.
#[test]
fn diagonal_batches_stay_within_the_kernel_tables() {
    use crate::backend::statevector::kernels::build_diagonal_batch_tables;
    let mut state = 42u64;
    let mut next = |bound: usize| {
        state = state
            .wrapping_mul(6364136223846793005)
            .wrapping_add(1442695040888963407);
        (state >> 33) as usize % bound
    };
    let mut batches = 0usize;
    for _ in 0..60 {
        let n = 16 + next(5);
        let mut c = Circuit::new(n, 0);
        for q in 0..n {
            c.add_gate(Gate::H, &[q]);
        }
        for _ in 0..40 + next(60) {
            let q0 = next(n);
            let q1 = (q0 + 1 + next(n - 1)) % n;
            let theta = next(628) as f64 / 100.0;
            match next(6) {
                0 => c.add_gate(Gate::Cz, &[q0, q1]),
                1 => c.add_gate(Gate::Rzz(theta), &[q0, q1]),
                2 => c.add_gate(Gate::cphase(theta), &[q0, q1]),
                3 => c.add_gate(Gate::cu(Gate::Rz(theta).matrix_2x2()), &[q0, q1]),
                4 => c.add_gate(Gate::T, &[q0]),
                _ => c.add_gate(Gate::Rx(theta), &[q0]),
            }
        }
        let fused = fuse_circuit(&c, true);
        for inst in &fused.instructions {
            if let Instruction::Gate {
                gate: Gate::DiagonalBatch(data),
                ..
            } = inst
            {
                batches += 1;
                assert!(
                    build_diagonal_batch_tables(&data.entries).is_some(),
                    "a {n}q batch outgrew the kernel tables"
                );
            }
        }
    }
    assert!(
        batches > 60,
        "the sweep should form batches, formed {batches}"
    );
}

#[test]
fn diagonal_entries_reproduce_each_batchable_gate() {
    use crate::gates::diag_entries_phase;
    let rz = Gate::Rz(0.7).matrix_2x2();
    let dense = Gate::Fused2q(Box::new(mat_mul_4x4(
        &Gate::cphase(1.1).matrix_4x4(),
        &kron_2x2(&Gate::T.matrix_2x2(), &rz),
    )));
    for (gate, targets) in [
        (Gate::cu(rz), [3usize, 1]),
        (Gate::cphase(0.4), [0, 2]),
        (dense, [2, 0]),
        (Gate::Rzz(0.9), [1, 3]),
    ] {
        assert!(gate.is_diag_batchable(), "{}", gate.name());
        let mut entries = Vec::new();
        gate.push_diag_entries(&targets, &mut entries);
        let mat = gate.matrix_4x4();
        for index in 0..16usize {
            let row = 2 * (index >> targets[0] & 1) + (index >> targets[1] & 1);
            assert!(
                (diag_entries_phase(index, &entries) - mat[row][row]).norm() < EPS,
                "{} at basis state {index}",
                gate.name()
            );
        }
    }
}