qirc-compiler 0.1.1

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

use crate::ir::*;
use crate::transpile::{self, GateSet};

const MAX_TERMS: usize = 1 << 16;
const NEGLIGIBLE: f64 = 1e-12;

fn bit(key: &[u64], index: usize) -> bool {
    key[index / 64] >> (index % 64) & 1 == 1
}

fn xz(words: usize, key: &[u64], q: usize) -> (bool, bool) {
    (bit(key, q), bit(key, 64 * words + q))
}

fn set(words: usize, key: &mut [u64], q: usize, x: bool, z: bool) {
    for (index, value) in [(q, x), (64 * words + q, z)] {
        let mask = 1u64 << (index % 64);
        if value {
            key[index / 64] |= mask;
        } else {
            key[index / 64] &= !mask;
        }
    }
}

struct Terms {
    words: usize,
    map: HashMap<Vec<u64>, f64>,
}

impl Terms {
    fn rotate(&mut self, q: usize, axis: (bool, bool), angle: f64) {
        let (gx, gz) = axis;
        let words = self.words;
        let flipped: Vec<(Vec<u64>, f64)> = self
            .map
            .iter()
            .filter(|(key, _)| {
                let (x, z) = xz(words, key, q);
                (x & gz) ^ (z & gx)
            })
            .map(|(key, &c)| (key.clone(), c))
            .collect();
        let (sin, cos) = angle.sin_cos();
        for (key, c) in &flipped {
            self.map.insert(key.clone(), c * cos);
        }
        let index = |x: bool, z: bool| match (x, z) {
            (true, false) => 0,
            (true, true) => 1,
            _ => 2,
        };
        for (mut key, c) in flipped {
            let (x, z) = xz(words, &key, q);
            let sign = if (index(gx, gz) + 3 - index(x, z)) % 3 == 1 {
                1.0
            } else {
                -1.0
            };
            set(words, &mut key, q, x ^ gx, z ^ gz);
            *self.map.entry(key).or_insert(0.0) += sign * sin * c;
        }
    }

    fn cx(&mut self, control: usize, target: usize) {
        let words = self.words;
        let moved: Vec<(Vec<u64>, f64)> = self
            .map
            .extract_if(|key, _| xz(words, key, control).0 || xz(words, key, target).1)
            .collect();
        for (mut key, c) in moved {
            let (xc, zc) = xz(words, &key, control);
            let (xt, zt) = xz(words, &key, target);
            set(words, &mut key, control, xc, zc ^ zt);
            set(words, &mut key, target, xt ^ xc, zt);
            self.map
                .insert(key, if xc && zt && xt == zc { -c } else { c });
        }
    }
}

pub(crate) fn propagate(program: &Program, paulis: &[(usize, bool, bool)]) -> Result<f64, String> {
    let words = (program.num_qubits as usize).div_ceil(64).max(1);
    let mut lowered = program.clone();
    transpile::transpile(&mut lowered, &GateSet::parse("rz-sx-cx")?);
    let mut terms = Terms {
        words,
        map: HashMap::new(),
    };
    let mut start = vec![0; 2 * words];
    for &(q, x, z) in paulis {
        set(words, &mut start, q, x, z);
    }
    terms.map.insert(start, 1.0);
    let gates: Vec<&Gate> = lowered.gates().collect();
    for gate in gates.into_iter().rev() {
        let target = gate.targets[0].index();
        if let (GateKind::X, [control]) = (gate.kind, &gate.controls[..]) {
            terms.cx(control.index(), target);
            continue;
        }
        let angle = || {
            gate.constant_angle().ok_or(
                "cannot propagate a Pauli through a rotation whose angle is only known at run time",
            )
        };
        let (x, y, z) = ((true, false), (true, true), (false, true));
        let (axis, turn) = match (gate.kind, gate.controls.len()) {
            (GateKind::I, 0) => continue,
            (GateKind::Rz | GateKind::R1, 0) => (z, angle()?),
            (GateKind::Rx, 0) => (x, angle()?),
            (GateKind::Ry, 0) => (y, angle()?),
            (GateKind::X, 0) => (x, PI),
            (GateKind::Y, 0) => (y, PI),
            (GateKind::Z, 0) => (z, PI),
            (GateKind::SX, 0) => (x, FRAC_PI_2),
            (GateKind::SXDag, 0) => (x, -FRAC_PI_2),
            (GateKind::S, 0) => (z, FRAC_PI_2),
            (GateKind::SDag, 0) => (z, -FRAC_PI_2),
            (GateKind::T, 0) => (z, FRAC_PI_4),
            (GateKind::TDag, 0) => (z, -FRAC_PI_4),
            (kind, _) => {
                return Err(format!(
                    "cannot propagate a Pauli through `{}`",
                    kind.name()
                ));
            }
        };
        terms.rotate(target, axis, turn);
        terms.map.retain(|_, c| c.abs() >= NEGLIGIBLE);
        if terms.map.len() > MAX_TERMS {
            return Err(format!(
                "the light cone of a term is too wide for a state vector and its Pauli expansion grew past {MAX_TERMS} strings"
            ));
        }
    }
    Ok(terms
        .map
        .iter()
        .filter(|(key, _)| key[..words].iter().all(|&w| w == 0))
        .map(|(_, c)| c)
        .sum())
}