wai-quantum 0.4.1

//! The program a fabric member runs for a circuit, and the CPU executor of
//! exactly that program. A member is correct when its runs equal [`execute`]'s;
//! `execute` is certified against the native simulator for every
//! configuration.
//!
//! A [`Program`] holds the circuit's gates as [`GateWords`], in op-log order,
//! and the steps that apply them. Each step here is one gate over the whole
//! state. The arithmetic is [`lanes::apply_words`]: the stored lanes are the
//! low 32 bits of the exact values, and a run reports the first op whose exact
//! result left 32 bits, which no valid circuit of at most [`lanes::horizon`]
//! gates can do.

use super::lanes::{self, GateWords, Lane};
use crate::quantum::{Circuit, MAX_QUBITS, ONE, QuantumError};

/// Bumped whenever the meaning of a [`Program`] changes. An implementation id
/// that depends on more than [`Step::Gate`] includes it; the per-gate WGSL
/// kernel's id ([`super::wgsl::implementation_id`]) versions the one step it
/// runs with [`super::wgsl::HOST_LAYOUT`] instead.
pub const PLAN_REVISION: u32 = 1;

/// One gate of a program.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct PlannedGate {
    pub words: GateWords,
    /// The gate's position in the op-log (what a range report names).
    pub index: u32,
    /// `m01 = m10 = (0, 0)`: the gate acts on each amplitude alone.
    pub diag: bool,
}

/// One step of a program.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Step {
    /// `gates[gate]` over the whole state: one dispatch.
    Gate { gate: u32 },
}

/// What a member runs for one circuit from one basis state.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Program {
    pub n_qubits: u8,
    /// The basis state the run starts from, already reduced modulo `2^n`.
    pub start: usize,
    pub gates: Vec<PlannedGate>,
    pub steps: Vec<Step>,
}

/// Validates exactly as [`Circuit::simulate_from`] does, with the same errors
/// in the same order (`validate()`, then [`QuantumError::TooManyQubits`]),
/// then plans one [`Step::Gate`] per op, in op-log order.
pub fn compile(c: &Circuit, start: usize) -> Result<Program, QuantumError> {
    c.validate()?;
    if c.n_qubits > MAX_QUBITS {
        return Err(QuantumError::TooManyQubits(c.n_qubits));
    }
    let gates: Vec<PlannedGate> = c
        .ops
        .iter()
        .enumerate()
        .map(|(k, g)| {
            let words = lanes::gate_words(g, c.gateset);
            // `validate` holds the op count to `u32`.
            PlannedGate { words, index: k as u32, diag: words.m[2..6] == [0; 4] }
        })
        .collect();
    let steps = (0..gates.len() as u32).map(|gate| Step::Gate { gate }).collect();
    Ok(Program { n_qubits: c.n_qubits, start: start % (1usize << c.n_qubits), gates, steps })
}

/// A run in lanes.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct LaneRun {
    pub amps: Vec<Lane>,
    /// The lowest op-log index whose exact result left 32 bits; `None` if
    /// none did. When it is set, `amps` holds only the low 32 bits of the
    /// reference's values from that op on.
    pub out_of_range: Option<u32>,
}

/// The program on the CPU: `amps[start] = (2^30, 0)`, then each step with
/// [`lanes::apply_words`]. Panics only if the program is malformed, which
/// [`compile`] never makes.
pub fn execute(p: &Program) -> LaneRun {
    let mut amps = vec![[0i32; 2]; 1usize << p.n_qubits];
    amps[p.start] = [ONE as i32, 0];
    let mut out_of_range: Option<u32> = None;
    for step in &p.steps {
        match *step {
            Step::Gate { gate } => {
                let g = &p.gates[gate as usize];
                let fits = lanes::apply_words(&mut amps, &g.words).expect("a compiled program's words fit its state");
                if !fits {
                    out_of_range = Some(out_of_range.map_or(g.index, |k| k.min(g.index)));
                }
            }
        }
    }
    LaneRun { amps, out_of_range }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::quantum::{BaseGate, Gate, Gateset};
    use crate::quantum_fabric::{Corpus, FABRIC_DEFAULT};

    fn widened(lanes: &[Lane]) -> Vec<[i64; 2]> {
        lanes.iter().map(|a| [i64::from(a[0]), i64::from(a[1])]).collect()
    }

    fn native(c: &Circuit, start: usize) -> Vec<[i64; 2]> {
        c.simulate_from(start).unwrap().amps.iter().map(|a| [a.re, a.im]).collect()
    }

    #[test]
    fn execute_is_the_native_simulator() {
        for gs in Gateset::ALL {
            let random = Corpus::Random { seed: 7, cases: 300 }.circuits(gs);
            let fabric = FABRIC_DEFAULT.circuits(gs);
            for (name, circuits) in [("random-v1", random), ("fabric-v1", fabric)] {
                for c in &circuits {
                    for start in [0, 5] {
                        let p = compile(c, start).unwrap();
                        assert_eq!(p.start, start % (1 << c.n_qubits));
                        assert_eq!((p.gates.len(), p.steps.len()), (c.ops.len(), c.ops.len()));
                        let run = execute(&p);
                        assert_eq!(run.out_of_range, None, "{name} {gs:?}");
                        assert_eq!(widened(&run.amps), native(c, start), "{name} {gs:?} start {start}");
                    }
                }
            }
        }
        // The program is the op-log: one step per op, in order, each gate
        // naming its position; `diag` exactly when the off-diagonal is zero.
        let mut c = Circuit::with_gateset(3, Gateset::V1);
        c.h(0).t(1).cx(0, 2).p(19, 2).y(1).z(0);
        let p = compile(&c, 11).unwrap();
        assert_eq!(p.start, 3);
        assert_eq!(p.steps, (0..6).map(|gate| Step::Gate { gate }).collect::<Vec<_>>());
        assert_eq!(p.gates.iter().map(|g| g.index).collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5]);
        assert_eq!(p.gates.iter().map(|g| g.diag).collect::<Vec<_>>(), [false, true, false, true, false, true]);
        // No qubits: no gates, and the one amplitude.
        let empty = compile(&Circuit::with_gateset(0, Gateset::V2), 9).unwrap();
        assert_eq!((empty.start, empty.gates.len()), (0, 0));
        assert_eq!(execute(&empty), LaneRun { amps: vec![[ONE as i32, 0]], out_of_range: None });
        // It refuses what the native simulator refuses, with the same error.
        for c in crate::quantum_fabric::tests::refused_circuits() {
            assert_eq!(compile(&c, 0).unwrap_err(), c.simulate_from(0).unwrap_err(), "{c:?}");
        }
        let mut wide = Circuit::new(MAX_QUBITS + 1);
        wide.ops.push(Gate { base: BaseGate::X, controls: vec![], target: 0, param: 0 });
        assert_eq!(compile(&wide, 0).unwrap_err(), QuantumError::TooManyQubits(MAX_QUBITS + 1));
        assert_eq!(compile(&Circuit::new(MAX_QUBITS + 1), 0).unwrap_err(), QuantumError::TooManyQubits(MAX_QUBITS + 1));
        // Validation comes first, as in the native simulator.
        let mut both = Circuit::new(MAX_QUBITS + 1);
        both.ops.push(Gate { base: BaseGate::P, controls: vec![], target: 0, param: 0 });
        assert_eq!(compile(&both, 0).unwrap_err(), both.simulate_from(0).unwrap_err());
        assert!(matches!(compile(&both, 0), Err(QuantumError::Invalid(_))));
    }
}