wai-quantum 0.5.0

//! A virtual quantum processor: a [`Sampler`] that returns the counts a noisy
//! device would, from a stated noise model, so that every piece of a quantum
//! processor's path through the fabric (submission, counts, statistical
//! certification, placement, receipts) runs and is tested before any real
//! device is reachable. Its certificates say they were earned in a simulator
//! ([`Provenance::Simulator`]), and placement ranks them after silicon.
//!
//! **The model** ([`NoiseProfile`], version [`MODEL_VERSION`]), applied to the
//! exact distribution `p` of the CPU's integer simulation:
//!
//! 1. **Gate errors, as global depolarizing.** Each gate with no control fails
//!    with probability `gate_1q`, each gate with controls with `gate_2q`; the
//!    run is error-free with probability `f = (1 − gate_1q)^{n₁}·(1 − gate_2q)^{n₂}`,
//!    and an error leaves the uniform distribution:
//!    `p' = f·p + (1 − f)/2ⁿ`. This is the digital error model the noisy
//!    simulator's tests measure against: it captures the fidelity's decay with
//!    depth, not the shape of real errors.
//! 2. **Readout errors**: each qubit's outcome flips with probability
//!    `readout`, independently.
//! 3. **Sampling**: `shots` draws by inverse transform from a splitmix64 stream
//!    seeded by the processor's seed, the circuit's hash and the shots, so the
//!    same request gives the same counts on every machine with IEEE binary64.
//!
//! It is a stand-in that is labelled as one. It claims nothing about any real
//! device's errors.
//!
//! [`VirtualDevice`] adds a device's shape: a coupling map and a native basis.
//! It compiles each circuit with [`crate::quantum_toolchain::native`], verifies
//! the program, and charges the gate errors for the program it would run, so a
//! circuit that needs routing on a sparse map samples worse than on a dense one,
//! as on a device.

use super::sampling::{Counts, SampleFuture, Sampler, check_counts, reference_distribution, sample_kernel, certify_sampler, QpuCorpus};
use super::{FabricClass, KernelEntry, Member, MemberError, Presence, Provenance, RunMeter, Window};
use crate::quantum::{Circuit, Gateset, QuantumError, circuit_hash};
use crate::quantum_toolchain::native::{compile, Basis, Coupling, NativeGate, NativeProgram};

/// The model's version: any change to how a distribution or a sample is
/// computed bumps it, and it is in the implementation id and the member id.
pub const MODEL_VERSION: u32 = 1;

/// The implementation name the id starts with.
pub const IMPLEMENTATION: &str = "vqpu-depolarizing-readout";

/// The simulator a certificate names.
pub const SIMULATOR: &str = "wai-quantum vqpu";

const DOMAIN_MEMBER: &[u8] = b"wai:quantum-fabric-vqpu-member\x01";
const DOMAIN_STREAM: &[u8] = b"wai:quantum-fabric-vqpu-stream\x01";

/// A virtual processor's error rates, each a probability in `[0, 1)`.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct NoiseProfile {
    /// The chance a gate with no control fails.
    pub gate_1q: f64,
    /// The chance a gate with controls fails.
    pub gate_2q: f64,
    /// The chance a qubit's measured bit is flipped.
    pub readout: f64,
}

impl NoiseProfile {
    /// No errors: the processor samples the exact distribution.
    pub const IDEAL: NoiseProfile = NoiseProfile { gate_1q: 0.0, gate_2q: 0.0, readout: 0.0 };

    /// Rates of the order superconducting processors publish in 2026:
    /// `1e-3` per one-qubit gate, `5e-3` per two-qubit gate, `1e-2` readout.
    pub const TYPICAL: NoiseProfile = NoiseProfile { gate_1q: 1e-3, gate_2q: 5e-3, readout: 1e-2 };

    /// Whether every rate is a probability in `[0, 1)`.
    pub fn is_valid(&self) -> bool {
        [self.gate_1q, self.gate_2q, self.readout].iter().all(|r| r.is_finite() && (0.0..1.0).contains(r))
    }
}

/// A virtual quantum processor: see the module docs.
#[derive(Clone, Debug, PartialEq)]
pub struct VirtualQpu {
    noise: NoiseProfile,
    seed: u64,
    max_qubits: u8,
    id: String,
}

fn hex(bytes: &[u8]) -> String {
    bytes.iter().map(|b| format!("{b:02x}")).collect()
}

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

/// `p` after gate errors as global depolarizing (`n1` uncontrolled gates, `n2`
/// controlled) and independent readout flips on `n` qubits.
fn noisy(mut p: Vec<f64>, noise: NoiseProfile, n1: i32, n2: i32, n: u8) -> Vec<f64> {
    let f = (1.0 - noise.gate_1q).powi(n1) * (1.0 - noise.gate_2q).powi(n2);
    let uniform = (1.0 - f) / p.len() as f64;
    p.iter_mut().for_each(|x| *x = f * *x + uniform);
    let r = noise.readout;
    for q in 0..n {
        let bit = 1usize << q;
        for x in 0..p.len() {
            if x & bit == 0 {
                let (a, b) = (p[x], p[x | bit]);
                p[x] = (1.0 - r) * a + r * b;
                p[x | bit] = r * a + (1.0 - r) * b;
            }
        }
    }
    p
}

/// `shots` inverse-transform draws from `p`, from a splitmix64 stream seeded by
/// the domain, the seed, the circuit's hash and the shots.
fn draw(p: &[f64], domain: &[u8], seed: u64, c: &Circuit, shots: u64) -> Result<Counts, MemberError> {
    let hash = circuit_hash(c).map_err(MemberError::Circuit)?;
    let mut h = blake3::Hasher::new();
    h.update(domain);
    h.update(&seed.to_le_bytes());
    h.update(&hash);
    h.update(&shots.to_le_bytes());
    let d = h.finalize();
    let mut s = u64::from_le_bytes(d.as_bytes()[..8].try_into().expect("8 bytes"));
    let mut cum = Vec::with_capacity(p.len());
    let mut total = 0.0;
    for x in p {
        total += x;
        cum.push(total);
    }
    let mut counts = vec![0u64; p.len()];
    for _ in 0..shots {
        let u = (splitmix(&mut s) >> 11) as f64 * (1.0 / (1u64 << 53) as f64) * total;
        let i = cum.partition_point(|&c| c <= u).min(counts.len() - 1);
        counts[i] += 1;
    }
    Ok(counts)
}

impl VirtualQpu {
    /// A processor with `noise`, drawing from `seed`, holding at most
    /// `max_qubits` qubits (a real device's width); `None` unless every rate
    /// is a probability in `[0, 1)` and the width is 1 to 20.
    pub fn new(noise: NoiseProfile, seed: u64, max_qubits: u8) -> Option<VirtualQpu> {
        if !noise.is_valid() || !(1..=20).contains(&max_qubits) {
            return None;
        }
        let mut o = DOMAIN_MEMBER.to_vec();
        o.extend_from_slice(&MODEL_VERSION.to_be_bytes());
        for r in [noise.gate_1q, noise.gate_2q, noise.readout] {
            o.extend_from_slice(&r.to_bits().to_be_bytes());
        }
        o.extend_from_slice(&seed.to_be_bytes());
        o.push(max_qubits);
        let id = format!("local/vqpu-{}", hex(&blake3::hash(&o).as_bytes()[..6]));
        Some(VirtualQpu { noise, seed, max_qubits, id })
    }

    /// `"local/vqpu-<12 hex>"`, over the model version, the rates, the seed
    /// and the width.
    pub fn id(&self) -> &str {
        &self.id
    }

    pub fn noise(&self) -> NoiseProfile {
        self.noise
    }

    pub fn max_qubits(&self) -> u8 {
        self.max_qubits
    }

    /// `"vqpu-depolarizing-readout/<MODEL_VERSION>"`.
    pub fn implementation() -> String {
        format!("{IMPLEMENTATION}/{MODEL_VERSION}")
    }

    /// `Simulator("wai-quantum vqpu <MODEL_VERSION>")`.
    pub fn provenance() -> Provenance {
        Provenance::Simulator(format!("{SIMULATOR} {MODEL_VERSION}"))
    }

    /// The distribution this processor samples for `c`: the exact one, then
    /// gate errors as global depolarizing, then readout flips. Refuses what
    /// the simulator refuses.
    pub fn distribution(&self, c: &Circuit) -> Result<Vec<f64>, QuantumError> {
        let p = reference_distribution(c)?;
        let n1 = c.ops.iter().filter(|g| g.controls.is_empty()).count() as i32;
        let n2 = c.ops.len() as i32 - n1;
        Ok(noisy(p, self.noise, n1, n2, c.n_qubits))
    }

    /// `shots` draws for `c` (see the module docs), or why there are none: what
    /// the simulator refuses, or more qubits than this processor holds.
    pub fn sample_now(&self, c: &Circuit, shots: u64) -> Result<Counts, MemberError> {
        if c.n_qubits > self.max_qubits {
            return Err(MemberError::TooWide { n_qubits: c.n_qubits, max: self.max_qubits });
        }
        let p = self.distribution(c).map_err(MemberError::Circuit)?;
        let counts = draw(&p, DOMAIN_STREAM, self.seed, c, shots)?;
        check_counts(c, shots, &counts)?;
        Ok(counts)
    }

    /// A fabric [`Member`] of class [`FabricClass::Qpu`]: one sampling entry per
    /// gateset, each certified in this call on `corpus` with `shots` per
    /// circuit, earned in a simulator.
    pub fn member(&self, corpus: QpuCorpus, shots: u64) -> Result<Member, MemberError> {
        let mut kernels = Vec::new();
        for gs in Gateset::ALL {
            let certificate = super::ready(certify_sampler(self, &Self::implementation(), gs, corpus, shots, Self::provenance()))
                .ok_or_else(|| MemberError::Other("the certification did not resolve".into()))??;
            kernels.push(KernelEntry { kernel: sample_kernel(gs).into(), implementation: Self::implementation(), certificate, energy: None });
        }
        let n = self.noise;
        Ok(Member {
            id: self.id.clone(),
            class: FabricClass::Qpu,
            presence: Presence::Detected,
            kernels,
            detail: format!(
                "virtual quantum processor, model {MODEL_VERSION}: gate errors {} (one-qubit) and {} (controlled), readout {}; up to {} qubits; a simulator, not a device",
                n.gate_1q, n.gate_2q, n.readout, self.max_qubits
            ),
        })
    }
}

impl Sampler for VirtualQpu {
    fn member_id(&self) -> String {
        self.id.clone()
    }

    fn sample<'r>(&'r self, implementation: &'r str, c: &'r Circuit, shots: u64, meter: &'r mut dyn RunMeter) -> SampleFuture<'r> {
        Box::pin(async move {
            if implementation != Self::implementation() {
                return Err(MemberError::Other(format!("{} runs implementation {}, not {implementation:?}", self.id, Self::implementation())));
            }
            let mut window = Window::new(meter);
            window.open();
            let counts = self.sample_now(c, shots)?;
            let (joules_micro, class) = window.close();
            Ok((counts, joules_micro, class))
        })
    }
}

/// The virtual device's model version: in its implementation id and member id.
pub const DEVICE_MODEL_VERSION: u32 = 1;

/// The implementation name a virtual device's id starts with.
pub const DEVICE_IMPLEMENTATION: &str = "vdevice-native-depolarizing-readout";

/// The simulator a virtual device's certificate names.
pub const DEVICE_SIMULATOR: &str = "wai-quantum vdevice";

const DOMAIN_DEVICE: &[u8] = b"wai:quantum-fabric-vdevice-member\x01";
const DOMAIN_DEVICE_STREAM: &[u8] = b"wai:quantum-fabric-vdevice-stream\x01";

/// A virtual quantum processor with a device's shape: a coupling map and a
/// native gate basis. Each circuit is compiled to a [`NativeProgram`] for that
/// map and basis, the program is verified against the circuit, and the gate
/// errors are charged for the program the device would run, routing `SWAP`s
/// included: each `sx`, `x`, `prx`, `gpi` or `gpi2` at `gate_1q`, each `cz` or
/// `zz` at `gate_2q`, and `rz` free, as a virtual rotation is. Readout and
/// sampling are as for [`VirtualQpu`]. Logical qubit `i` is read from the physical qubit it ends on,
/// into bit `i` of the counts' index.
#[derive(Clone, Debug, PartialEq)]
pub struct VirtualDevice {
    coupling: Coupling,
    basis: Basis,
    noise: NoiseProfile,
    seed: u64,
    id: String,
}

impl VirtualDevice {
    /// A device with `coupling` and `basis`, `noise`, drawing from `seed`;
    /// `None` unless every rate is a probability in `[0, 1)` and the map has a
    /// qubit.
    pub fn new(coupling: Coupling, basis: Basis, noise: NoiseProfile, seed: u64) -> Option<VirtualDevice> {
        if !noise.is_valid() || coupling.qubits() == 0 {
            return None;
        }
        let mut o = DOMAIN_DEVICE.to_vec();
        o.extend_from_slice(&DEVICE_MODEL_VERSION.to_be_bytes());
        o.push(match basis {
            Basis::RzSxXCz => 1,
            Basis::PrxCz => 2,
            Basis::GpiZz => 3,
        });
        o.extend_from_slice(&coupling.qubits().to_be_bytes());
        for a in 0..coupling.qubits() {
            for b in a + 1..coupling.qubits() {
                if coupling.connected(a, b) {
                    o.extend_from_slice(&a.to_be_bytes());
                    o.extend_from_slice(&b.to_be_bytes());
                }
            }
        }
        for r in [noise.gate_1q, noise.gate_2q, noise.readout] {
            o.extend_from_slice(&r.to_bits().to_be_bytes());
        }
        o.extend_from_slice(&seed.to_be_bytes());
        let id = format!("local/vdevice-{}", hex(&blake3::hash(&o).as_bytes()[..6]));
        Some(VirtualDevice { coupling, basis, noise, seed, id })
    }

    /// `"local/vdevice-<12 hex>"`, over the model version, the basis, the map,
    /// the rates and the seed.
    pub fn id(&self) -> &str {
        &self.id
    }

    pub fn coupling(&self) -> &Coupling {
        &self.coupling
    }

    pub fn basis(&self) -> Basis {
        self.basis
    }

    /// `"vdevice-native-depolarizing-readout/<DEVICE_MODEL_VERSION>"`.
    pub fn implementation() -> String {
        format!("{DEVICE_IMPLEMENTATION}/{DEVICE_MODEL_VERSION}")
    }

    /// `Simulator("wai-quantum vdevice <DEVICE_MODEL_VERSION>")`.
    pub fn provenance() -> Provenance {
        Provenance::Simulator(format!("{DEVICE_SIMULATOR} {DEVICE_MODEL_VERSION}"))
    }

    /// The program this device runs for `c`, verified against `c`.
    pub fn compile(&self, c: &Circuit) -> Result<NativeProgram, MemberError> {
        if c.n_qubits > MAX_DEVICE_SAMPLE_QUBITS {
            return Err(MemberError::TooWide { n_qubits: c.n_qubits, max: MAX_DEVICE_SAMPLE_QUBITS });
        }
        let program = compile(c, self.basis, &self.coupling).map_err(|e| MemberError::Other(format!("{}: {e}", self.id)))?;
        program.verify(c, &self.coupling).map_err(|e| MemberError::Other(format!("{}: the compiled program failed its check: {e}", self.id)))?;
        Ok(program)
    }

    /// The distribution this device samples for `c`, and the program it runs.
    pub fn distribution(&self, c: &Circuit) -> Result<(Vec<f64>, NativeProgram), MemberError> {
        let program = self.compile(c)?;
        let p = reference_distribution(c).map_err(MemberError::Circuit)?;
        let n1 = program.gates.iter().filter(|g| matches!(g, NativeGate::Sx(_) | NativeGate::X(_) | NativeGate::Prx(..) | NativeGate::Gpi(..) | NativeGate::Gpi2(..))).count() as i32;
        let n2 = program.gates.iter().filter(|g| matches!(g, NativeGate::Cz(..) | NativeGate::Zz(..))).count() as i32;
        Ok((noisy(p, self.noise, n1, n2, c.n_qubits), program))
    }

    /// `shots` draws for `c`, or why there are none.
    pub fn sample_now(&self, c: &Circuit, shots: u64) -> Result<Counts, MemberError> {
        let (p, _) = self.distribution(c)?;
        let counts = draw(&p, DOMAIN_DEVICE_STREAM, self.seed, c, shots)?;
        check_counts(c, shots, &counts)?;
        Ok(counts)
    }

    /// A fabric [`Member`] of class [`FabricClass::Qpu`], as for
    /// [`VirtualQpu::member`].
    pub fn member(&self, corpus: QpuCorpus, shots: u64) -> Result<Member, MemberError> {
        let mut kernels = Vec::new();
        for gs in Gateset::ALL {
            let certificate = super::ready(certify_sampler(self, &Self::implementation(), gs, corpus, shots, Self::provenance()))
                .ok_or_else(|| MemberError::Other("the certification did not resolve".into()))??;
            kernels.push(KernelEntry { kernel: sample_kernel(gs).into(), implementation: Self::implementation(), certificate, energy: None });
        }
        let n = self.noise;
        let basis = match self.basis {
            Basis::RzSxXCz => "rz, sx, x, cz",
            Basis::PrxCz => "prx, cz",
            Basis::GpiZz => "gpi, gpi2, zz",
        };
        Ok(Member {
            id: self.id.clone(),
            class: FabricClass::Qpu,
            presence: Presence::Detected,
            kernels,
            detail: format!(
                "virtual device, model {DEVICE_MODEL_VERSION}: {} qubits, basis {basis}, programs routed on its coupling map and verified before they run; gate errors {} (one-qubit rotations) and {} (two-qubit gates), readout {}; a simulator, not a device",
                self.coupling.qubits(),
                n.gate_1q,
                n.gate_2q,
                n.readout
            ),
        })
    }
}

/// The widest circuit a virtual device samples: its distribution is a dense
/// table of `2^n` probabilities.
pub const MAX_DEVICE_SAMPLE_QUBITS: u8 = 20;

impl Sampler for VirtualDevice {
    fn member_id(&self) -> String {
        self.id.clone()
    }

    fn sample<'r>(&'r self, implementation: &'r str, c: &'r Circuit, shots: u64, meter: &'r mut dyn RunMeter) -> SampleFuture<'r> {
        Box::pin(async move {
            if implementation != Self::implementation() {
                return Err(MemberError::Other(format!("{} runs implementation {}, not {implementation:?}", self.id, Self::implementation())));
            }
            let mut window = Window::new(meter);
            window.open();
            let counts = self.sample_now(c, shots)?;
            let (joules_micro, class) = window.close();
            Ok((counts, joules_micro, class))
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::quantum_fabric::sampling::{QPU_DEFAULT, local_sampling_member};
    use crate::quantum_fabric::{Parity, Unmetered, place, ready, statistical};

    fn bell() -> Circuit {
        let mut c = Circuit::new(2);
        c.h(0).cx(0, 1);
        c
    }

    #[test]
    fn rates_must_be_probabilities_and_the_id_names_the_model() {
        assert!(VirtualQpu::new(NoiseProfile { gate_1q: -0.1, ..NoiseProfile::IDEAL }, 1, 5).is_none());
        assert!(VirtualQpu::new(NoiseProfile { readout: 1.0, ..NoiseProfile::IDEAL }, 1, 5).is_none());
        assert!(VirtualQpu::new(NoiseProfile { gate_2q: f64::NAN, ..NoiseProfile::IDEAL }, 1, 5).is_none());
        assert!(VirtualQpu::new(NoiseProfile::IDEAL, 1, 0).is_none());
        let a = VirtualQpu::new(NoiseProfile::TYPICAL, 1, 5).unwrap();
        assert!(a.id().starts_with("local/vqpu-"));
        assert_ne!(VirtualQpu::new(NoiseProfile::TYPICAL, 2, 5).unwrap().id(), a.id());
        assert_ne!(VirtualQpu::new(NoiseProfile::IDEAL, 1, 5).unwrap().id(), a.id());
        assert_ne!(VirtualQpu::new(NoiseProfile::TYPICAL, 1, 6).unwrap().id(), a.id());
        assert_eq!(VirtualQpu::implementation(), "vqpu-depolarizing-readout/1");
        assert_eq!(VirtualQpu::provenance().label(), "simulator:wai-quantum vqpu 1");
    }

    #[test]
    fn an_ideal_processor_samples_the_exact_distribution() {
        let v = VirtualQpu::new(NoiseProfile::IDEAL, 9, 8).unwrap();
        for c in [bell(), Circuit::qft(4)] {
            assert_eq!(v.distribution(&c).unwrap(), reference_distribution(&c).unwrap());
        }
    }

    #[test]
    fn noise_mixes_toward_uniform_and_flips_readout() {
        let c = bell();
        let gates = VirtualQpu::new(NoiseProfile { gate_2q: 0.1, ..NoiseProfile::IDEAL }, 1, 5).unwrap().distribution(&c).unwrap();
        // One controlled gate at 0.1: 0.9·0.5 + 0.1/4 on the two peaks.
        assert!((gates[0] - 0.475).abs() < 1e-12 && (gates[1] - 0.025).abs() < 1e-12, "{gates:?}");
        let readout = VirtualQpu::new(NoiseProfile { readout: 0.1, ..NoiseProfile::IDEAL }, 1, 5).unwrap().distribution(&c).unwrap();
        // |00⟩ stays with (0.9)² or comes from |11⟩ with (0.1)².
        assert!((readout[0] - 0.5 * (0.81 + 0.01)).abs() < 1e-12, "{readout:?}");
        for d in [&gates, &readout] {
            assert!((d.iter().sum::<f64>() - 1.0).abs() < 1e-12);
        }
    }

    #[test]
    fn the_same_request_gives_the_same_counts() {
        let v = VirtualQpu::new(NoiseProfile::TYPICAL, 3, 5).unwrap();
        let a = v.sample_now(&Circuit::qft(3), 2000).unwrap();
        assert_eq!(v.sample_now(&Circuit::qft(3), 2000).unwrap(), a);
        assert_eq!(a.iter().sum::<u64>(), 2000);
        assert_eq!(v.sample_now(&Circuit::qft(3), 2001).unwrap().iter().sum::<u64>(), 2001);
        assert_eq!(v.sample_now(&Circuit::new(6), 10), Err(MemberError::TooWide { n_qubits: 6, max: 5 }));
    }

    #[test]
    fn fidelity_falls_as_the_noise_rises() {
        let c = QPU_DEFAULT.circuits(Gateset::V2).pop().unwrap();
        let reference = reference_distribution(&c).unwrap();
        let mut last = 1.0;
        for scale in [0.0, 1.0, 10.0, 50.0] {
            let noise = NoiseProfile { gate_1q: 1e-3 * scale, gate_2q: 5e-3 * scale, readout: (1e-2 * scale).min(0.4) };
            let v = VirtualQpu::new(noise, 5, 5).unwrap();
            let Parity::Statistical { fidelity, .. } = statistical(&reference, &v.sample_now(&c, 20_000).unwrap()) else { panic!() };
            assert!(fidelity <= last + 1e-3, "scale {scale}: {fidelity} after {last}");
            last = fidelity;
        }
        assert!(last < 0.9, "heavy noise is visible: {last}");
    }

    #[test]
    fn a_virtual_member_is_a_simulated_qpu_placed_after_silicon() {
        let v = VirtualQpu::new(NoiseProfile::TYPICAL, 11, 5).unwrap();
        let member = v.member(QPU_DEFAULT, 2000).unwrap();
        assert_eq!((member.class, member.presence, member.kernels.len()), (FabricClass::Qpu, Presence::Detected, 2));
        for (entry, gs) in member.kernels.iter().zip(Gateset::ALL) {
            assert_eq!(entry.kernel, sample_kernel(gs));
            assert_eq!(entry.certificate.provenance, VirtualQpu::provenance());
            let Parity::Statistical { fidelity, shots } = entry.certificate.parity else { panic!("{:?}", entry.certificate.parity) };
            assert_eq!(shots, 2000);
            assert!(fidelity > 0.8 && fidelity < 1.0, "{gs:?}: {fidelity}");
        }
        let need = Parity::Statistical { fidelity: 0.5, shots: 1000 };
        let local = local_sampling_member();
        for gs in Gateset::ALL {
            let pair = [member.clone(), local.clone()];
            let (placed, _) = place(&pair, sample_kernel(gs), &need).unwrap();
            assert_eq!(placed.id, local.id);
            let (placed, k) = place(std::slice::from_ref(&member), sample_kernel(gs), &need).unwrap();
            assert_eq!((placed.id.as_str(), k.implementation.as_str()), (v.id(), VirtualQpu::implementation().as_str()));
        }
        // On the Sampler surface, with the wrong implementation, nothing runs.
        assert!(ready(v.sample("other", &bell(), 10, &mut Unmetered)).unwrap().is_err());
    }

    fn complete(n: u16) -> Coupling {
        let mut pairs = Vec::new();
        for a in 0..n {
            for b in a + 1..n {
                pairs.push((a, b));
            }
        }
        Coupling::new(n, &pairs).unwrap()
    }

    #[test]
    fn an_ideal_device_samples_the_exact_distribution_in_either_basis() {
        for basis in [Basis::RzSxXCz, Basis::PrxCz, Basis::GpiZz] {
            let d = VirtualDevice::new(Coupling::grid(2, 3), basis, NoiseProfile::IDEAL, 4).unwrap();
            for c in [bell(), Circuit::qft(4)] {
                let (p, program) = d.distribution(&c).unwrap();
                assert_eq!(p, reference_distribution(&c).unwrap());
                assert_eq!(program.basis, basis);
            }
        }
    }

    #[test]
    fn routing_on_a_sparse_map_costs_fidelity() {
        // Every pair of five qubits interacts: a line needs SWAPs, a complete map
        // none, so the line's program carries more cz and samples worse.
        let mut c = Circuit::new(5);
        for a in 0..5u8 {
            c.h(a);
        }
        for a in 0..5u8 {
            for b in a + 1..5 {
                c.cz(a, b);
            }
        }
        // Read in the X basis: depolarizing leaves a uniform distribution as it
        // was, so the distribution must not be one.
        for a in 0..5u8 {
            c.h(a);
        }
        let noise = NoiseProfile { gate_1q: 1e-3, gate_2q: 2e-2, readout: 0.0 };
        let line = VirtualDevice::new(Coupling::line(5), Basis::RzSxXCz, noise, 1).unwrap();
        let full = VirtualDevice::new(complete(5), Basis::RzSxXCz, noise, 1).unwrap();
        let (pl, prog_line) = line.distribution(&c).unwrap();
        let (pf, prog_full) = full.distribution(&c).unwrap();
        assert!(prog_line.swaps > 0 && prog_full.swaps == 0);
        let reference = reference_distribution(&c).unwrap();
        assert!(reference.iter().cloned().fold(0.0, f64::max) > 1.5 / 32.0);
        let overlap = |p: &[f64]| -> f64 { p.iter().zip(&reference).map(|(a, b)| (a * b).sqrt()).sum::<f64>().powi(2) };
        assert!(overlap(&pl) < overlap(&pf), "line {} vs complete {}", overlap(&pl), overlap(&pf));
        assert_ne!(line.id(), full.id());
    }

    #[test]
    fn a_device_member_is_certified_through_compiled_programs() {
        let d = VirtualDevice::new(Coupling::grid(3, 3), Basis::PrxCz, NoiseProfile::TYPICAL, 21).unwrap();
        let member = d.member(QPU_DEFAULT, 2000).unwrap();
        assert_eq!((member.class, member.kernels.len()), (FabricClass::Qpu, 2));
        for entry in &member.kernels {
            assert_eq!(entry.certificate.provenance, VirtualDevice::provenance());
            let Parity::Statistical { fidelity, shots } = entry.certificate.parity else { panic!("{:?}", entry.certificate.parity) };
            assert_eq!(shots, 2000);
            assert!(fidelity > 0.7 && fidelity < 1.0, "{fidelity}");
        }
        assert_eq!(d.sample_now(&Circuit::qft(3), 500).unwrap(), d.sample_now(&Circuit::qft(3), 500).unwrap());
        // Wider than the map: no layout exists.
        assert!(d.sample_now(&Circuit::new(10), 10).is_err());
        assert!(ready(d.sample("other", &bell(), 10, &mut Unmetered)).unwrap().is_err());
        assert!(VirtualDevice::new(Coupling::line(0), Basis::PrxCz, NoiseProfile::IDEAL, 1).is_none());
        assert!(VirtualDevice::new(Coupling::line(3), Basis::PrxCz, NoiseProfile { readout: 2.0, ..NoiseProfile::IDEAL }, 1).is_none());
    }
}