Skip to main content

ctrl_freeq/autodiff/
tape.rs

1//! The reverse-mode tape.
2//!
3//! A [`Tape`] records every operation as a node holding its value and how it was made.  [`Tape::backward`] walks
4//! the nodes in reverse and applies each operation's adjoint, giving the gradient of a real scalar with respect to
5//! every leaf - the same model as PyTorch's autograd, at the granularity of whole matrices.
6//!
7//! Gradients with respect to complex values follow PyTorch's conjugate convention: for a real loss `L` and a complex
8//! `z = x + iy`, the gradient is `∂L/∂x + i·∂L/∂y`.
9//!
10//! Constants an operation needs - basis matrices, control operators, targets - are borrowed for the tape's lifetime
11//! `'a` rather than copied, because the propagation records several hundred nodes per batch element per evaluation.
12
13use super::ops_complex::{LindbladOps, Step};
14use super::{C, Scalar};
15use crate::error::{Error, Result};
16use crate::linalg::{CMat, RMat};
17
18/// A node's value: a real or a complex matrix.  Vectors are single columns and scalars are `1 × 1`.
19#[derive(Clone, Debug, PartialEq)]
20pub enum Value<T> {
21    /// A real matrix.
22    R(RMat<T>),
23    /// A complex matrix.
24    C(CMat<T>),
25}
26
27impl<T: Scalar> Value<T> {
28    /// `(rows, cols)`.
29    pub fn shape(&self) -> (usize, usize) {
30        match self {
31            Value::R(m) => m.shape(),
32            Value::C(m) => m.shape(),
33        }
34    }
35
36    /// The real matrix, or an error naming `what`.
37    pub fn r(&self, what: &str) -> Result<&RMat<T>> {
38        match self {
39            Value::R(m) => Ok(m),
40            Value::C(_) => Err(Error::Dimension(format!("{what} needs a real operand"))),
41        }
42    }
43
44    /// The complex matrix, or an error naming `what`.
45    pub fn c(&self, what: &str) -> Result<&CMat<T>> {
46        match self {
47            Value::C(m) => Ok(m),
48            Value::R(_) => Err(Error::Dimension(format!("{what} needs a complex operand"))),
49        }
50    }
51
52    /// `self += o`, elementwise.
53    fn accumulate(&mut self, o: Value<T>) {
54        match (self, o) {
55            (Value::R(a), Value::R(b)) => a.data.iter_mut().zip(b.data).for_each(|(x, y)| *x += y),
56            (Value::C(a), Value::C(b)) => a.data.iter_mut().zip(b.data).for_each(|(x, y)| *x += y),
57            _ => unreachable!("gradients of one node always share its type"),
58        }
59    }
60
61    /// Every entry times the real `s`.
62    pub(crate) fn scaled(&self, s: T) -> Value<T> {
63        match self {
64            Value::R(m) => Value::R(m.map(|v| v * s)),
65            Value::C(m) => Value::C(m.scale_re(s)),
66        }
67    }
68}
69
70/// A handle to a node on a [`Tape`].
71#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
72pub struct Var(pub(crate) usize);
73
74/// How a node was made, with what its adjoint needs.
75pub(crate) enum Op<'a, T> {
76    Leaf,
77    Constant,
78    Add(Var, Var),
79    Sub(Var, Var),
80    Mul(Var, Var),
81    Scale(Var, f64),
82    Square(Var),
83    Sqrt(Var),
84    Cos(Var),
85    Sin(Var),
86    Atan2(Var, Var),
87    MatmulConst(&'a RMat<f64>, Var),
88    Slice(Var, usize),
89    Col(Var, usize),
90    HStack(Vec<Var>),
91    AmpPenalty(Var, Option<usize>),
92    Sum(Var),
93    Mean(Var),
94    Complex(Var, Var),
95    Real(Var),
96    Imag(Var),
97    MulConstC(Var, &'a CMat<f64>),
98    LincombRow(Var, usize, &'a [CMat<f64>]),
99    ExpmMiDt(Var, f64),
100    Matmul(Var, Var),
101    Sandwich(Var, Var),
102    Lindblad(Var, &'a LindbladOps, Step),
103    Fidelity(&'a CMat<f64>, Var),
104    ReTraceProduct(&'a CMat<f64>, Var),
105    BatchMean(Vec<Var>, Vec<Value<T>>),
106}
107
108pub(crate) struct Node<'a, T> {
109    pub(crate) value: Value<T>,
110    pub(crate) op: Op<'a, T>,
111    pub(crate) requires_grad: bool,
112}
113
114/// A record of operations that can be differentiated in reverse.
115pub struct Tape<'a, T: Scalar> {
116    pub(crate) nodes: Vec<Node<'a, T>>,
117    grad_enabled: bool,
118}
119
120impl<T: Scalar> Default for Tape<'_, T> {
121    fn default() -> Self {
122        Tape::new()
123    }
124}
125
126/// Gradients from one [`Tape::backward`] call.
127pub struct Grads<T> {
128    grads: Vec<Option<Value<T>>>,
129}
130
131impl<T: Scalar> Grads<T> {
132    /// The gradient with respect to `v`, or `None` if the output does not depend on it.
133    pub fn wrt(&self, v: Var) -> Option<&Value<T>> {
134        self.grads.get(v.0).and_then(|g| g.as_ref())
135    }
136
137    /// The gradient with respect to a real leaf, as a flat vector (zeros if the output does not depend on it).
138    pub fn wrt_real(&self, v: Var, len: usize) -> Vec<T> {
139        match self.wrt(v) {
140            Some(Value::R(m)) => m.data.clone(),
141            _ => vec![T::zero(); len],
142        }
143    }
144}
145
146impl<'a, T: Scalar> Tape<'a, T> {
147    /// A tape that records what it needs for [`backward`](Self::backward).
148    pub fn new() -> Self {
149        Tape {
150            nodes: Vec::new(),
151            grad_enabled: true,
152        }
153    }
154
155    /// A tape for evaluation only: values, no gradients.
156    pub fn no_grad() -> Self {
157        Tape {
158            nodes: Vec::new(),
159            grad_enabled: false,
160        }
161    }
162
163    /// Whether this tape records gradients.
164    pub fn grad_enabled(&self) -> bool {
165        self.grad_enabled
166    }
167
168    /// A differentiable input.
169    pub fn leaf(&mut self, value: Value<T>) -> Var {
170        let requires = self.grad_enabled;
171        self.nodes.push(Node {
172            value,
173            op: Op::Leaf,
174            requires_grad: requires,
175        });
176        Var(self.nodes.len() - 1)
177    }
178
179    /// A constant input.
180    pub fn constant(&mut self, value: Value<T>) -> Var {
181        self.nodes.push(Node {
182            value,
183            op: Op::Constant,
184            requires_grad: false,
185        });
186        Var(self.nodes.len() - 1)
187    }
188
189    /// The value of `v`.
190    pub fn value(&self, v: Var) -> &Value<T> {
191        &self.nodes[v.0].value
192    }
193
194    /// The value of a `1 × 1` real node.
195    pub fn scalar(&self, v: Var) -> Result<T> {
196        let m = self.value(v).r("scalar")?;
197        if m.shape() != (1, 1) {
198            return Err(Error::Dimension(format!(
199                "expected a scalar, got {}x{}",
200                m.rows, m.cols
201            )));
202        }
203        Ok(m.data[0])
204    }
205
206    /// The number of nodes recorded.
207    pub fn len(&self) -> usize {
208        self.nodes.len()
209    }
210
211    /// Whether nothing has been recorded.
212    pub fn is_empty(&self) -> bool {
213        self.nodes.is_empty()
214    }
215
216    pub(crate) fn requires(&self, v: Var) -> bool {
217        self.nodes[v.0].requires_grad
218    }
219
220    /// Record a node made from `parents`.
221    pub(crate) fn push(&mut self, value: Value<T>, op: Op<'a, T>, parents: &[Var]) -> Var {
222        let requires = self.grad_enabled && parents.iter().any(|&p| self.requires(p));
223        let op = if requires { op } else { Op::Constant };
224        self.nodes.push(Node {
225            value,
226            op,
227            requires_grad: requires,
228        });
229        Var(self.nodes.len() - 1)
230    }
231
232    /// Gradients of the real `1 × 1` node `root` with respect to every node it depends on.
233    pub fn backward(&self, root: Var) -> Result<Grads<T>> {
234        if !self.grad_enabled {
235            return Err(Error::NotSupported("backward on a tape made with Tape::no_grad".into()));
236        }
237        self.scalar(root)?;
238        let mut grads: Vec<Option<Value<T>>> = Vec::with_capacity(root.0 + 1);
239        grads.resize_with(root.0 + 1, || None);
240        grads[root.0] = Some(Value::R(RMat::from_vec(1, 1, vec![T::one()])?));
241
242        for i in (0..=root.0).rev() {
243            let Some(g) = grads[i].take() else { continue };
244            let node = &self.nodes[i];
245            if node.requires_grad {
246                for (parent, pg) in self.adjoint(node, &g)? {
247                    if !self.requires(parent) {
248                        continue;
249                    }
250                    match &mut grads[parent.0] {
251                        Some(acc) => acc.accumulate(pg),
252                        slot => *slot = Some(pg),
253                    }
254                }
255            }
256            grads[i] = Some(g);
257        }
258        Ok(Grads { grads })
259    }
260
261    /// The adjoint of one node: the gradient contribution to each parent given the node's own gradient `g`.
262    fn adjoint(&self, node: &Node<'a, T>, g: &Value<T>) -> Result<Vec<(Var, Value<T>)>> {
263        use super::ops_complex as oc;
264        use super::ops_real as or;
265        let v = |x: Var| &self.nodes[x.0].value;
266        Ok(match &node.op {
267            Op::Leaf | Op::Constant => Vec::new(),
268            Op::Add(a, b) => vec![(*a, g.clone()), (*b, g.clone())],
269            Op::Sub(a, b) => vec![(*a, g.clone()), (*b, g.scaled(-T::one()))],
270            Op::Mul(a, b) => or::mul_adjoint(*a, *b, v(*a), v(*b), g)?,
271            Op::Scale(a, s) => vec![(*a, g.scaled(T::from_f64(*s)))],
272            Op::Square(a) => vec![(*a, or::square_adjoint(v(*a), g)?)],
273            Op::Sqrt(a) => vec![(*a, or::sqrt_adjoint(&node.value, g)?)],
274            Op::Cos(a) => vec![(*a, or::cos_adjoint(v(*a), g)?)],
275            Op::Sin(a) => vec![(*a, or::sin_adjoint(v(*a), g)?)],
276            Op::Atan2(y, x) => or::atan2_adjoint(*y, *x, v(*y), v(*x), g)?,
277            Op::MatmulConst(m, a) => vec![(*a, or::matmul_const_adjoint(m, g)?)],
278            Op::Slice(a, start) => vec![(*a, or::slice_adjoint(v(*a), *start, g)?)],
279            Op::Col(a, c) => vec![(*a, or::col_adjoint(v(*a), *c, g)?)],
280            Op::HStack(parts) => or::hstack_adjoint(parts, |p| v(p).shape().1, g)?,
281            Op::AmpPenalty(a, arg) => vec![(*a, or::amp_penalty_adjoint(v(*a), *arg, g)?)],
282            Op::Sum(a) => vec![(*a, or::sum_adjoint(v(*a), g, T::one())?)],
283            Op::Mean(a) => {
284                let (r, c) = v(*a).shape();
285                vec![(*a, or::sum_adjoint(v(*a), g, T::from_f64(1.0 / (r * c) as f64))?)]
286            }
287            Op::Complex(re, im) => oc::complex_adjoint(*re, *im, g)?,
288            Op::Real(z) => vec![(*z, oc::real_adjoint(g, false)?)],
289            Op::Imag(z) => vec![(*z, oc::real_adjoint(g, true)?)],
290            Op::MulConstC(z, c) => vec![(*z, oc::mul_const_c_adjoint(c, g)?)],
291            Op::LincombRow(u, row, ops) => vec![(*u, oc::lincomb_row_adjoint(v(*u), *row, ops, g)?)],
292            Op::ExpmMiDt(h, dt) => vec![(*h, oc::expm_mi_dt_adjoint(v(*h), *dt, g)?)],
293            Op::Matmul(a, b) => oc::matmul_adjoint(*a, *b, v(*a), v(*b), g)?,
294            Op::Sandwich(u, rho) => oc::sandwich_adjoint(*u, *rho, v(*u), v(*rho), g)?,
295            Op::Lindblad(rho, ops, step) => vec![(*rho, oc::lindblad_adjoint(ops, *step, g)?)],
296            Op::Fidelity(t, psi) => vec![(*psi, oc::fidelity_adjoint(t, v(*psi), g)?)],
297            Op::ReTraceProduct(sigma, rho) => vec![(*rho, oc::re_trace_product_adjoint(sigma, g)?)],
298            Op::BatchMean(inputs, stored) => {
299                let s = g.r("batch mean gradient")?.data[0];
300                inputs.iter().zip(stored).map(|(&x, gx)| (x, gx.scaled(s))).collect()
301            }
302        })
303    }
304}
305
306/// Multiply an `f64` complex constant by a complex value of any scalar type.
307#[inline]
308pub(crate) fn mulc<T: Scalar>(a: C<f64>, b: C<T>) -> C<T> {
309    let (ar, ai) = (T::from_f64(a.re), T::from_f64(a.im));
310    C::new(ar * b.re - ai * b.im, ar * b.im + ai * b.re)
311}
312
313/// Lift an `f64` complex constant.
314#[inline]
315pub(crate) fn liftc<T: Scalar>(a: C<f64>) -> C<T> {
316    C::new(T::from_f64(a.re), T::from_f64(a.im))
317}