qirc-compiler 0.1.1

Compiler and state vector simulator for QIR, the Quantum Intermediate Representation
Documentation
use std::collections::{HashMap, HashSet};
use std::fmt;

use crate::calibration::Calibration;
use crate::ir::*;

const MAX_PATHS: usize = 256;

#[derive(Clone, Copy, Default, PartialEq, Debug)]
pub struct Tally {
    pub t: usize,
    pub cx: usize,
    pub gates: usize,
    pub depth: usize,
    pub live: usize,
    pub success: Option<f64>,
    pub time: Option<f64>,
}

impl Tally {
    fn of<'a>(blocks: impl Iterator<Item = &'a Block>, calibration: Option<&Calibration>) -> Tally {
        let blocks: Vec<&Block> = blocks.collect();
        let ops = || blocks.iter().flat_map(|b| &b.ops);
        let mut tally = Tally::default();
        if let Some(c) = calibration {
            let (time, idle) = c.schedule(ops());
            tally.success = Some((-c.infidelity(ops()) - idle).exp());
            tally.time = c.timed().then_some(time);
        }
        let mut frontier: HashMap<QubitId, usize> = HashMap::new();
        let mut open: HashMap<QubitId, usize> = HashMap::new();
        let mut intervals = Vec::new();
        for op in blocks.iter().flat_map(|b| &b.ops) {
            let qubits = op.qubits();
            let Some(layer) = qubits
                .iter()
                .map(|q| frontier.get(q).copied().unwrap_or(0) + 1)
                .max()
            else {
                continue;
            };
            for &q in &qubits {
                frontier.insert(q, layer);
                open.entry(q).or_insert(layer);
            }
            match op {
                Op::Gate(gate) => {
                    tally.gates += 1;
                    tally.cx += usize::from(qubits.len() > 1);
                    tally.t += usize::from(
                        gate.controls.is_empty()
                            && matches!(gate.kind, GateKind::T | GateKind::TDag),
                    );
                }
                Op::Reset { qubit, .. } => {
                    intervals.extend(open.remove(qubit).map(|start| (start, layer)))
                }
                _ => {}
            }
        }
        intervals.extend(open.iter().map(|(q, &start)| (start, frontier[q])));
        tally.depth = frontier.into_values().max().unwrap_or(0);
        tally.live = peak(&intervals);
        tally
    }

    fn max(self, other: Tally) -> Tally {
        Tally {
            t: self.t.max(other.t),
            cx: self.cx.max(other.cx),
            gates: self.gates.max(other.gates),
            depth: self.depth.max(other.depth),
            live: self.live.max(other.live),
            success: match (self.success, other.success) {
                (Some(a), Some(b)) => Some(a.min(b)),
                (a, b) => a.or(b),
            },
            time: match (self.time, other.time) {
                (Some(a), Some(b)) => Some(a.max(b)),
                (a, b) => a.or(b),
            },
        }
    }
}

fn peak(intervals: &[(usize, usize)]) -> usize {
    let mut events: Vec<(usize, isize)> = intervals
        .iter()
        .flat_map(|&(start, end)| [(start, 1), (end + 1, -1)])
        .collect();
    events.sort_unstable();
    let mut live = 0isize;
    let mut most = 0;
    for (_, step) in events {
        live += step;
        most = most.max(live);
    }
    most as usize
}

pub struct Path {
    pub labels: Vec<String>,
    pub again: Option<String>,
    pub tally: Tally,
}

pub struct Report {
    pub paths: Vec<Path>,
    pub worst: Tally,
    pub truncated: bool,
}

struct Frame {
    block: BlockId,
    successors: Vec<BlockId>,
    next: usize,
}

fn frame(program: &Program, block: BlockId) -> Frame {
    let mut successors = program.block(block).term.successors();
    successors.dedup();
    Frame {
        block,
        successors,
        next: 0,
    }
}

fn path(
    program: &Program,
    frames: &[Frame],
    again: Option<BlockId>,
    calibration: Option<&Calibration>,
) -> Path {
    let label = |id: BlockId| program.block(id).label.clone();
    Path {
        labels: frames.iter().map(|f| label(f.block)).collect(),
        again: again.map(label),
        tally: Tally::of(frames.iter().map(|f| program.block(f.block)), calibration),
    }
}

pub fn analyse(program: &Program, calibration: Option<&Calibration>) -> Report {
    let mut paths = Vec::new();
    let mut truncated = false;
    let mut frames = vec![frame(program, program.entry)];
    let mut on_path = HashSet::from([program.entry]);
    if frames[0].successors.is_empty() {
        paths.push(path(program, &frames, None, calibration));
    }

    while let Some(top) = frames.last_mut() {
        let Some(&next) = top.successors.get(top.next) else {
            on_path.remove(&top.block);
            frames.pop();
            continue;
        };
        top.next += 1;
        let again = on_path.contains(&next);
        if !again {
            on_path.insert(next);
            frames.push(frame(program, next));
        }
        let ends = again || frames.last().is_some_and(|f| f.successors.is_empty());
        if !ends {
            continue;
        }
        if paths.len() == MAX_PATHS {
            truncated = true;
            break;
        }
        paths.push(path(program, &frames, again.then_some(next), calibration));
    }

    let worst = paths
        .iter()
        .fold(Tally::default(), |worst, p| worst.max(p.tally));
    Report {
        paths,
        worst,
        truncated,
    }
}

impl fmt::Display for Report {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let names: Vec<String> = self
            .paths
            .iter()
            .map(|p| {
                let mut name = p.labels.join(" > ");
                if let Some(again) = &p.again {
                    name.push_str(&format!(" > {again} again"));
                }
                name
            })
            .collect();
        let width = names
            .iter()
            .map(String::len)
            .max()
            .unwrap_or(0)
            .max("worst listed".len());
        let row = |f: &mut fmt::Formatter<'_>, name: &str, t: &Tally| {
            write!(
                f,
                "{name:<width$}  {:>6}  {:>6}  {:>6}  {:>6}  {:>6}",
                t.t, t.cx, t.gates, t.depth, t.live
            )?;
            if let Some(time) = t.time {
                write!(f, "  {:>9.2}", time / 1000.0)?;
            }
            match t.success {
                Some(success) => writeln!(f, "  {success:>8.4}"),
                None => writeln!(f),
            }
        };
        write!(
            f,
            "{:<width$}  {:>6}  {:>6}  {:>6}  {:>6}  {:>6}",
            "path", "t", "cx", "gates", "depth", "live"
        )?;
        if self.worst.time.is_some() {
            write!(f, "  {:>9}", "time us")?;
        }
        if self.worst.success.is_some() {
            writeln!(f, "  {:>8}", "success")?;
        } else {
            writeln!(f)?;
        }
        for (name, p) in names.iter().zip(&self.paths) {
            row(f, name, &p.tally)?;
        }
        if self.paths.len() > 1 {
            let label = if self.truncated {
                "worst listed"
            } else {
                "worst case"
            };
            row(f, label, &self.worst)?;
        }
        if self.truncated {
            writeln!(f, "only the first {MAX_PATHS} paths are listed")?;
        }
        if self.paths.iter().any(|p| p.again.is_some()) {
            writeln!(
                f,
                "a path ending in `again` loops back, so its counts cover one pass through the loop"
            )?;
        }
        Ok(())
    }
}