qirc-compiler 0.1.1

Compiler and state vector simulator for QIR, the Quantum Intermediate Representation
Documentation
use std::cmp::Ordering;
use std::collections::HashMap;
use std::f64::consts::{FRAC_PI_2, FRAC_PI_4, PI};

use crate::ir::*;

const EPSILON: f64 = 1e-12;

struct Term {
    at: usize,
    flipped: bool,
    angle: f64,
}

fn slope(gate: &Gate) -> Option<f64> {
    if !gate.controls.is_empty() {
        return None;
    }
    match gate.kind {
        GateKind::Z => Some(PI),
        GateKind::S => Some(FRAC_PI_2),
        GateKind::SDag => Some(-FRAC_PI_2),
        GateKind::T => Some(FRAC_PI_4),
        GateKind::TDag => Some(-FRAC_PI_4),
        GateKind::Rz | GateKind::R1 => gate.params.first()?.constant().map(Const::as_f64),
        _ => None,
    }
}

pub(crate) fn diagonal(kind: GateKind) -> bool {
    matches!(
        kind,
        GateKind::I
            | GateKind::Z
            | GateKind::S
            | GateKind::SDag
            | GateKind::T
            | GateKind::TDag
            | GateKind::Rz
            | GateKind::R1
    )
}

fn xor(a: &[u32], b: &[u32]) -> Vec<u32> {
    let mut out = Vec::with_capacity(a.len() + b.len());
    let (mut i, mut j) = (0, 0);
    while i < a.len() && j < b.len() {
        match a[i].cmp(&b[j]) {
            Ordering::Less => {
                out.push(a[i]);
                i += 1;
            }
            Ordering::Greater => {
                out.push(b[j]);
                j += 1;
            }
            Ordering::Equal => {
                i += 1;
                j += 1;
            }
        }
    }
    out.extend_from_slice(&a[i..]);
    out.extend_from_slice(&b[j..]);
    out
}

fn wrap(angle: f64) -> f64 {
    let turn = 2.0 * PI;
    let wrapped = angle.rem_euclid(turn);
    if wrapped > PI {
        wrapped - turn
    } else {
        wrapped
    }
}

fn rewrite(gate: &mut Gate, angle: f64) {
    let named = [
        (PI, GateKind::Z),
        (-PI, GateKind::Z),
        (FRAC_PI_2, GateKind::S),
        (-FRAC_PI_2, GateKind::SDag),
        (FRAC_PI_4, GateKind::T),
        (-FRAC_PI_4, GateKind::TDag),
    ];
    if let Some(&(_, kind)) = named.iter().find(|(a, _)| (a - angle).abs() < 1e-9) {
        gate.kind = kind;
        gate.params.clear();
    } else {
        if !matches!(gate.kind, GateKind::Rz | GateKind::R1) {
            gate.kind = GateKind::Rz;
        }
        gate.params = vec![Operand::Const(Const::Float(angle))];
    }
}

fn fold_block(ops: &mut Vec<Op>, qubits: usize) -> usize {
    let mut fresh = qubits as u32;
    let mut parity: Vec<(Vec<u32>, bool)> = (0..qubits as u32).map(|q| (vec![q], false)).collect();
    let mut terms: HashMap<Vec<u32>, Term> = HashMap::new();
    let mut finished = Vec::new();
    let mut keep = vec![true; ops.len()];
    let mut renew = |parity: &mut Vec<(Vec<u32>, bool)>, q: usize| {
        parity[q] = (vec![fresh], false);
        fresh += 1;
    };

    for (index, op) in ops.iter().enumerate() {
        let wires = op.qubits();
        let tracked = match op {
            Op::Gate(gate) => match (
                slope(gate),
                gate.kind,
                &gate.controls[..],
                &gate.targets[..],
            ) {
                (Some(slope), ..) => {
                    let (p, flipped) = &parity[gate.targets[0].index()];
                    let signed = if *flipped { -slope } else { slope };
                    if p.is_empty() {
                        keep[index] = false;
                    } else if let Some(term) = terms.get_mut(p) {
                        term.angle += signed;
                        keep[index] = false;
                    } else {
                        terms.insert(
                            p.clone(),
                            Term {
                                at: index,
                                flipped: *flipped,
                                angle: signed,
                            },
                        );
                    }
                    true
                }
                (None, kind, ..) if diagonal(kind) => true,
                (None, GateKind::X, [], [t]) => {
                    parity[t.index()].1 ^= true;
                    true
                }
                (None, GateKind::X, [c], [t]) => {
                    let control = parity[c.index()].clone();
                    let target = &mut parity[t.index()];
                    target.0 = xor(&target.0, &control.0);
                    target.1 ^= control.1;
                    true
                }
                (None, GateKind::Swap, [], [a, b]) => {
                    parity.swap(a.index(), b.index());
                    true
                }
                (None, GateKind::H, [], [t]) => {
                    renew(&mut parity, t.index());
                    true
                }
                _ => false,
            },
            _ => wires.is_empty(),
        };
        if !tracked {
            finished.extend(terms.drain().map(|(_, term)| term));
            for q in wires {
                renew(&mut parity, q.index());
            }
        }
    }
    finished.extend(terms.into_values());

    for term in finished {
        let angle = wrap(if term.flipped {
            -term.angle
        } else {
            term.angle
        });
        if angle.abs() < EPSILON {
            keep[term.at] = false;
        } else if let Op::Gate(gate) = &mut ops[term.at]
            && slope(gate).is_none_or(|s| (wrap(s) - angle).abs() > EPSILON)
        {
            rewrite(gate, angle);
        }
    }

    let removed = keep.iter().filter(|k| !**k).count();
    keep_marked(ops, &keep);
    removed
}

pub(crate) fn fold(program: &mut Program) -> usize {
    let qubits = program.num_qubits as usize;
    program
        .blocks
        .iter_mut()
        .map(|block| fold_block(&mut block.ops, qubits))
        .sum()
}