wai-quantum 0.3.19

//! Deterministic circuit COMPILATION + equivalence proof — `wai.quantum.compile`
//! (extensions/quantum-ops § Compilation).
//!
//! A quantum compiler routes a circuit onto a device's coupling graph — inserting
//! SWAPs so every two-qubit gate acts on physically-connected qubits — and remaps
//! qubits. Whether the routed circuit still computes the same thing is a
//! correctness obligation that today is checked, if at all, by an unsigned,
//! non-reproducible tool. This module makes it a **signed certificate**: a
//! deterministic router plus a byte-exact **Clifford stabilizer-tableau**
//! equivalence check, sealed into a [`crate::quantum_ops::CompileReceipt`].
//!
//! Two Clifford circuits implement the same unitary (up to global phase) iff they
//! conjugate every Pauli identically — i.e. they map the `2n` generators
//! `{X_i, Z_i}` to the same signed Paulis. The tableau tracks those `2n` images
//! under `H`, `S`, `CX`, `SWAP` by the Aaronson–Gottesman update rules; equivalence
//! is a row-by-row comparison. Routing preserves semantics up to the final qubit
//! permutation, so the certificate checks `routed ++ (swaps restoring identity) ≡
//! source` — all through the same deterministic simulator, no hand-rolled Pauli
//! bookkeeping. Byte-identical on every machine; the verdict reproduces from the
//! circuits alone.
//!
//! Honest boundary: the equivalence check is exact for **Clifford** circuits (the
//! stabilizer formalism is complete there); general-circuit equivalence is
//! co-NP-hard and out of scope. That is the standard, honest scope for a
//! tableau-based checker — and it covers routing/mapping correctness, where the
//! transformation is Clifford (SWAPs + relabeling) regardless of the payload.

use crate::quantum_ops::{content_hash, CompileReceipt, GrantRef};
use ed25519_dalek::SigningKey;

fn splitmix64(state: &mut u64) -> u64 {
    *state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
    let mut z = *state;
    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    z ^ (z >> 31)
}

// ===========================================================================
// Circuits
// ===========================================================================

/// A Clifford gate on named qubits.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Gate {
    H(u32),
    S(u32),
    Cx(u32, u32),
    Swap(u32, u32),
}

impl Gate {
    fn tag(&self) -> u8 {
        match self {
            Gate::H(_) => 1,
            Gate::S(_) => 2,
            Gate::Cx(_, _) => 3,
            Gate::Swap(_, _) => 4,
        }
    }
    fn qubits(&self) -> (u32, u32) {
        match *self {
            Gate::H(q) | Gate::S(q) => (q, q),
            Gate::Cx(a, b) | Gate::Swap(a, b) => (a, b),
        }
    }
}

/// Canonical bytes of a circuit (`n` qubits) — what a receipt's circuit hashes bind.
pub fn circuit_bytes(gates: &[Gate], n: u32) -> Vec<u8> {
    let mut b = Vec::with_capacity(gates.len() * 9 + 8);
    b.extend_from_slice(b"wai:qc-circuit\x01");
    b.extend_from_slice(&n.to_le_bytes());
    for g in gates {
        let (p, q) = g.qubits();
        b.push(g.tag());
        b.extend_from_slice(&p.to_le_bytes());
        b.extend_from_slice(&q.to_le_bytes());
    }
    b
}

/// Canonical bytes of a routed circuit together with its final qubit mapping.
pub fn routed_bytes(gates: &[Gate], n: u32, final_map: &[u32]) -> Vec<u8> {
    let mut b = circuit_bytes(gates, n);
    b.extend_from_slice(b"\x01map\x01");
    for &m in final_map {
        b.extend_from_slice(&m.to_le_bytes());
    }
    b
}

// ===========================================================================
// Clifford stabilizer tableau
// ===========================================================================

/// The images of the `2n` Pauli generators under a Clifford circuit: rows
/// `0..n` are the images of `X_i`, rows `n..2n` the images of `Z_i`, each a signed
/// Pauli `(x, z, sign)`. Two circuits are equivalent (up to global phase) iff their
/// tableaux are equal.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Tableau {
    pub n: u32,
    /// `2n` rows of `(x_bits, z_bits, sign)`.
    rows: Vec<(u32, u32, u8)>,
    /// Generator-update work performed (for the receipt).
    pub work: u64,
}

#[inline]
fn bit(v: u32, q: u32) -> u32 {
    (v >> q) & 1
}
#[inline]
fn setbit(v: u32, q: u32, b: u32) -> u32 {
    (v & !(1 << q)) | (b << q)
}

impl Tableau {
    /// The identity tableau on `n` qubits.
    pub fn identity(n: u32) -> Tableau {
        let mut rows = Vec::with_capacity(2 * n as usize);
        for i in 0..n {
            rows.push((1 << i, 0, 0)); // X_i
        }
        for i in 0..n {
            rows.push((0, 1 << i, 0)); // Z_i
        }
        Tableau { n, rows, work: 0 }
    }

    fn apply(&mut self, g: &Gate) {
        match *g {
            Gate::H(q) => {
                for r in self.rows.iter_mut() {
                    let (x, z, s) = *r;
                    let xq = bit(x, q);
                    let zq = bit(z, q);
                    let ns = s ^ (xq & zq) as u8;
                    *r = (setbit(x, q, zq), setbit(z, q, xq), ns);
                }
            }
            Gate::S(q) => {
                for r in self.rows.iter_mut() {
                    let (x, z, s) = *r;
                    let xq = bit(x, q);
                    let zq = bit(z, q);
                    let ns = s ^ (xq & zq) as u8;
                    *r = (x, z ^ (xq << q), ns);
                }
            }
            Gate::Cx(c, t) => {
                for r in self.rows.iter_mut() {
                    let (x, z, s) = *r;
                    let xc = bit(x, c);
                    let zc = bit(z, c);
                    let xt = bit(x, t);
                    let zt = bit(z, t);
                    let ns = s ^ (xc & zt & (xt ^ zc ^ 1)) as u8;
                    *r = (x ^ (xc << t), z ^ (zt << c), ns);
                }
            }
            Gate::Swap(a, b) => {
                for r in self.rows.iter_mut() {
                    let (mut x, mut z, s) = *r;
                    let xa = bit(x, a);
                    let xb = bit(x, b);
                    x = setbit(setbit(x, a, xb), b, xa);
                    let za = bit(z, a);
                    let zb = bit(z, b);
                    z = setbit(setbit(z, a, zb), b, za);
                    *r = (x, z, s);
                }
            }
        }
        self.work += self.rows.len() as u64;
    }

    /// Build the tableau of a circuit.
    pub fn of(gates: &[Gate], n: u32) -> Tableau {
        let mut t = Tableau::identity(n);
        for g in gates {
            t.apply(g);
        }
        t
    }

    /// Do two circuits implement the same Clifford (up to global phase)?
    pub fn equivalent(&self, other: &Tableau) -> bool {
        self.n == other.n && self.rows == other.rows
    }
}

// ===========================================================================
// Coupling graph + routing
// ===========================================================================

/// A hardware coupling graph on `n` qubits (undirected adjacency).
#[derive(Clone, Debug)]
pub struct Coupling {
    pub n: u32,
    adj: Vec<Vec<u32>>,
}

impl Coupling {
    pub fn from_edges(n: u32, edges: &[(u32, u32)]) -> Coupling {
        let mut adj = vec![Vec::new(); n as usize];
        for &(a, b) in edges {
            adj[a as usize].push(b);
            adj[b as usize].push(a);
        }
        Coupling { n, adj }
    }
    /// A line `0-1-…-(n-1)`.
    pub fn line(n: u32) -> Coupling {
        let e: Vec<(u32, u32)> = (0..n.saturating_sub(1)).map(|i| (i, i + 1)).collect();
        Coupling::from_edges(n, &e)
    }
    /// A ring (line plus the wrap edge).
    pub fn ring(n: u32) -> Coupling {
        let mut e: Vec<(u32, u32)> = (0..n.saturating_sub(1)).map(|i| (i, i + 1)).collect();
        if n > 2 {
            e.push((n - 1, 0));
        }
        Coupling::from_edges(n, &e)
    }
    fn coupled(&self, a: u32, b: u32) -> bool {
        self.adj[a as usize].contains(&b)
    }
    /// Shortest path `a → b` (inclusive) via BFS. Deterministic (neighbors in
    /// insertion order).
    fn path(&self, a: u32, b: u32) -> Vec<u32> {
        if a == b {
            return vec![a];
        }
        let n = self.n as usize;
        let mut prev = vec![u32::MAX; n];
        let mut seen = vec![false; n];
        let mut q = std::collections::VecDeque::new();
        q.push_back(a);
        seen[a as usize] = true;
        while let Some(u) = q.pop_front() {
            if u == b {
                break;
            }
            for &v in &self.adj[u as usize] {
                if !seen[v as usize] {
                    seen[v as usize] = true;
                    prev[v as usize] = u;
                    q.push_back(v);
                }
            }
        }
        let mut path = vec![b];
        let mut cur = b;
        while cur != a {
            cur = prev[cur as usize];
            if cur == u32::MAX {
                return Vec::new(); // disconnected
            }
            path.push(cur);
        }
        path.reverse();
        path
    }

    pub fn bytes(&self) -> Vec<u8> {
        let mut b = Vec::new();
        b.extend_from_slice(b"wai:qc-coupling\x01");
        b.extend_from_slice(&self.n.to_le_bytes());
        for (a, nb) in self.adj.iter().enumerate() {
            for &c in nb {
                if (a as u32) < c {
                    b.extend_from_slice(&(a as u32).to_le_bytes());
                    b.extend_from_slice(&c.to_le_bytes());
                }
            }
        }
        b
    }
}

/// The result of routing a logical circuit onto a coupling graph.
#[derive(Clone, Debug)]
pub struct RouteResult {
    /// The routed circuit, on physical qubits (includes inserted SWAPs).
    pub routed: Vec<Gate>,
    /// Final mapping `final_map[logical] = physical`.
    pub final_map: Vec<u32>,
    /// SWAP gates inserted.
    pub swaps: u32,
}

/// Route a logical circuit onto `coupling` by inserting SWAPs (moving a qubit
/// along the shortest path to its partner). Deterministic.
pub fn route(gates: &[Gate], coupling: &Coupling) -> RouteResult {
    let n = coupling.n;
    // phys[l] = physical location of logical l; log[p] = logical at physical p.
    let mut phys: Vec<u32> = (0..n).collect();
    let mut logq: Vec<u32> = (0..n).collect();
    let mut routed = Vec::new();
    let mut swaps = 0u32;

    let do_swap = |routed: &mut Vec<Gate>, phys: &mut [u32], logq: &mut [u32], p: u32, q: u32| {
        routed.push(Gate::Swap(p, q));
        let (lp, lq) = (logq[p as usize], logq[q as usize]);
        logq[p as usize] = lq;
        logq[q as usize] = lp;
        phys[lp as usize] = q;
        phys[lq as usize] = p;
    };

    for g in gates {
        match *g {
            Gate::H(l) => routed.push(Gate::H(phys[l as usize])),
            Gate::S(l) => routed.push(Gate::S(phys[l as usize])),
            Gate::Cx(a, b) | Gate::Swap(a, b) => {
                let (pa, pb) = (phys[a as usize], phys[b as usize]);
                if !coupling.coupled(pa, pb) {
                    let path = coupling.path(pa, pb);
                    // walk logical-a along the path until it sits adjacent to pb
                    for w in 0..path.len().saturating_sub(2) {
                        do_swap(&mut routed, &mut phys, &mut logq, path[w], path[w + 1]);
                        swaps += 1;
                    }
                }
                let (pa, pb) = (phys[a as usize], phys[b as usize]);
                match *g {
                    Gate::Cx(_, _) => routed.push(Gate::Cx(pa, pb)),
                    _ => do_swap(&mut routed, &mut phys, &mut logq, pa, pb),
                }
            }
        }
    }
    RouteResult { routed, final_map: phys, swaps }
}

/// The SWAP network that restores the identity mapping from `final_map`
/// (`final_map[l] = physical`). Appended to a routed circuit, it "unroutes" it.
fn restore_swaps(final_map: &[u32], n: u32) -> Vec<Gate> {
    // logq[p] = logical currently at physical p
    let mut logq = vec![0u32; n as usize];
    for (l, &p) in final_map.iter().enumerate() {
        logq[p as usize] = l as u32;
    }
    let mut phys: Vec<u32> = final_map.to_vec();
    let mut out = Vec::new();
    for p in 0..n as usize {
        // we want logical p at physical p
        while logq[p] != p as u32 {
            let want = p as u32; // logical we want here
            let cur_phys = phys[want as usize];
            // swap physical p with cur_phys
            out.push(Gate::Swap(p as u32, cur_phys));
            let (lp, lc) = (logq[p], logq[cur_phys as usize]);
            logq[p] = lc;
            logq[cur_phys as usize] = lp;
            phys[lp as usize] = cur_phys;
            phys[lc as usize] = p as u32;
        }
    }
    out
}

/// Prove a routed circuit is equivalent to its source: `routed ++ restore ≡ source`
/// as Cliffords. Returns `(equivalent, total_work)`.
pub fn verify_routing(source: &[Gate], route: &RouteResult, n: u32) -> (bool, u64) {
    let mut full = route.routed.clone();
    full.extend(restore_swaps(&route.final_map, n));
    let t_routed = Tableau::of(&full, n);
    let t_source = Tableau::of(source, n);
    let work = t_routed.work + t_source.work;
    (t_source.equivalent(&t_routed), work)
}

// ===========================================================================
// Random Clifford circuits + sealing
// ===========================================================================

/// A deterministic random Clifford circuit on `n` qubits with `depth` gates —
/// CX gates on arbitrary (possibly non-adjacent) qubit pairs, so routing is needed.
pub fn random_clifford(n: u32, depth: u32, seed: u64) -> Vec<Gate> {
    let mut st = seed.wrapping_mul(0x2545_F491).wrapping_add(1);
    let mut g = Vec::with_capacity(depth as usize);
    for _ in 0..depth {
        match splitmix64(&mut st) % 3 {
            0 => g.push(Gate::H((splitmix64(&mut st) % n as u64) as u32)),
            1 => g.push(Gate::S((splitmix64(&mut st) % n as u64) as u32)),
            _ => {
                let a = (splitmix64(&mut st) % n as u64) as u32;
                let mut b = (splitmix64(&mut st) % n as u64) as u32;
                if b == a {
                    b = (b + 1) % n;
                }
                g.push(Gate::Cx(a, b));
            }
        }
    }
    g
}

/// A full route + verify + seal: route `source` onto `coupling`, prove equivalence,
/// and seal a `CompileReceipt` binding source, routed circuit (+ mapping), and
/// coupling to the verdict.
#[allow(clippy::too_many_arguments)]
pub fn compile_and_seal(
    signer: &SigningKey,
    signer_id: &str,
    source: &[Gate],
    coupling: &Coupling,
    joules_micro: u64,
    grant: GrantRef,
) -> (RouteResult, bool, CompileReceipt) {
    let n = coupling.n;
    let r = route(source, coupling);
    let (equivalent, work) = verify_routing(source, &r, n);
    let receipt = CompileReceipt::seal(
        signer,
        signer_id,
        "clifford-tableau",
        content_hash(&circuit_bytes(source, n)),
        content_hash(&routed_bytes(&r.routed, n, &r.final_map)),
        content_hash(&coupling.bytes()),
        equivalent,
        r.swaps,
        work,
        joules_micro,
        grant,
        None,
    );
    (r, equivalent, receipt)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn key(s: u8) -> SigningKey {
        SigningKey::from_bytes(&[s; 32])
    }

    #[test]
    fn hh_is_identity() {
        let t = Tableau::of(&[Gate::H(0), Gate::H(0)], 2);
        assert!(t.equivalent(&Tableau::identity(2)));
    }

    #[test]
    fn s_to_the_fourth_is_identity() {
        let t = Tableau::of(&[Gate::S(0), Gate::S(0), Gate::S(0), Gate::S(0)], 1);
        assert!(t.equivalent(&Tableau::identity(1)));
    }

    #[test]
    fn swap_equals_three_cnots() {
        let a = Tableau::of(&[Gate::Swap(0, 1)], 2);
        let b = Tableau::of(&[Gate::Cx(0, 1), Gate::Cx(1, 0), Gate::Cx(0, 1)], 2);
        assert!(a.equivalent(&b));
    }

    #[test]
    fn distinct_circuits_are_not_equivalent() {
        let a = Tableau::of(&[Gate::H(0)], 2);
        let b = Tableau::of(&[Gate::S(0)], 2);
        assert!(!a.equivalent(&b));
    }

    #[test]
    fn routing_preserves_equivalence() {
        // The heart of it: route a random Clifford circuit onto a line, and the
        // routed circuit must be provably equivalent to the source.
        let n = 5;
        let coupling = Coupling::line(n);
        for seed in 0..40u64 {
            let src = random_clifford(n, 40, seed.wrapping_mul(0x9E37));
            let r = route(&src, &coupling);
            let (equiv, _) = verify_routing(&src, &r, n);
            assert!(equiv, "routed circuit must be equivalent (seed {seed})");
            // every 2-qubit gate in the routed circuit is on a coupled pair
            for g in &r.routed {
                if let Gate::Cx(a, b) | Gate::Swap(a, b) = *g {
                    assert!(coupling.coupled(a, b), "routed 2q gate must be local");
                }
            }
        }
    }

    #[test]
    fn tamper_breaks_equivalence() {
        // A corrupted routed circuit must be caught by the check.
        let n = 5;
        let coupling = Coupling::line(n);
        let src = random_clifford(n, 40, 0xBEEF);
        let mut r = route(&src, &coupling);
        // drop the last gate — no longer equivalent
        r.routed.pop();
        let (equiv, _) = verify_routing(&src, &r, n);
        assert!(!equiv, "a tampered routed circuit must NOT verify as equivalent");
    }

    #[test]
    fn compile_seals_verifying_receipt() {
        let coupling = Coupling::ring(6);
        let src = random_clifford(6, 60, 7);
        let (r, equiv, rec) = compile_and_seal(
            &key(1), "did:key:lab", &src, &coupling, 300_000, GrantRef::unbounded("quantum.compile"),
        );
        assert!(equiv);
        assert!(rec.verify());
        assert!(rec.equivalent);
        assert!(rec.source_matches(&circuit_bytes(&src, 6)));
        assert!(rec.target_matches(&routed_bytes(&r.routed, 6, &r.final_map)));
    }

    #[test]
    fn routing_is_deterministic() {
        let coupling = Coupling::line(6);
        let src = random_clifford(6, 50, 123);
        let a = route(&src, &coupling);
        let b = route(&src, &coupling);
        assert_eq!(a.routed, b.routed);
        assert_eq!(a.final_map, b.final_map);
    }
}