Skip to main content

tpt_sci_quantum/
tensor.rs

1//! Tensor-product (Kronecker) formulation of qubit circuits.
2//!
3//! The in-place [`State`] simulator mutates amplitudes directly with explicit
4//! index arithmetic. This module provides the complementary *dense* view: a
5//! circuit is recorded as a sequence of single- and two-qubit gates and
6//! assembled into a single complex unitary `U`, then applied as
7//! `|ψ'⟩ = U|ψ⟩`.
8//!
9//! Because `tpt-math-linalg` is real-only (`f64`), every complex scalar
10//! `a + bi` is embedded as the real `2×2` block `[[a, -b], [b, a]]`; a
11//! complex `d×d` matrix therefore becomes a real `2d×2d` matrix handled by
12//! `DMatrix<f64>`. This is the tensor-product (Kronecker) representation of a
13//! circuit — exact for the qubits present — and is most useful at modest
14//! width (it is `O(4^n)` to build and `O(4^n)` to apply). The in-place
15//! [`State`] path remains the scalable one for wide registers.
16
17use num_complex::Complex;
18use tpt_math_linalg::tpt_math_linalg_dense::{DMatrix, DVector};
19
20use crate::{State, StateError};
21
22/// Real `2×2` block embedding of a complex scalar `a + bi`.
23#[inline]
24fn block(z: Complex<f64>) -> [f64; 4] {
25    [z.re, -z.im, z.im, z.re]
26}
27
28/// Kronecker product `A ⊗ B` over `DMatrix<f64>`.
29///
30/// Entry `(i, j)` of the result is `A[(i/r, j/s)] · B[(i%r, j%s)]` where
31/// `r, s` are the row/column counts of `B`.
32pub fn kron(a: &DMatrix<f64>, b: &DMatrix<f64>) -> DMatrix<f64> {
33    let (p, q) = (a.nrows(), a.ncols());
34    let (r, s) = (b.nrows(), b.ncols());
35    DMatrix::from_fn(p * r, q * s, |i, j| {
36        let ai = i / r;
37        let aj = j / s;
38        let bi = i % r;
39        let bj = j % s;
40        a[(ai, aj)] * b[(bi, bj)]
41    })
42}
43
44/// Embed a complex `2×2` gate (row-major `[g00, g01, g10, g11]`) as a real `4×4`.
45pub fn embed_gate_2x2(gate: &[Complex<f64>; 4]) -> DMatrix<f64> {
46    DMatrix::from_fn(4, 4, |i, j| {
47        let qr = i / 2;
48        let qc = j / 2;
49        let sr = i % 2;
50        let sc = j % 2;
51        let z = gate[qr * 2 + qc];
52        block(z)[sr * 2 + sc]
53    })
54}
55
56/// Embed a complex `4×4` gate (row-major, 16 entries) as a real `8×8`.
57pub fn embed_gate_4x4(gate: &[Complex<f64>; 16]) -> DMatrix<f64> {
58    DMatrix::from_fn(8, 8, |i, j| {
59        let qr = i / 2;
60        let qc = j / 2;
61        let sr = i % 2;
62        let sc = j % 2;
63        let z = gate[qr * 4 + qc];
64        block(z)[sr * 2 + sc]
65    })
66}
67
68/// A `2×2` real identity, the embedding of the complex identity gate.
69fn identity_2x2() -> DMatrix<f64> {
70    DMatrix::from_fn(2, 2, |i, j| if i == j { 1.0 } else { 0.0 })
71}
72
73/// Real `2d×2d` block embedding of an arbitrary `d×d` complex matrix given
74/// row-major as `entries` (length `d*d`).
75///
76/// Generalizes [`embed_gate_2x2`]/[`embed_gate_4x4`] to any dimension `d`.
77/// Used by the [`crate::density`] module to embed density matrices and
78/// (possibly non-unitary) Kraus operators into the same real-embedded
79/// representation used for unitaries, so that gate/channel application can
80/// reuse ordinary real `DMatrix` multiplication.
81///
82/// A useful identity of this embedding: for any complex matrix `A`,
83/// `embed(A†) == embed(A).transpose()` (conjugate-transpose becomes plain
84/// real transpose), which is what lets [`crate::density::DensityMatrix`]
85/// implement `ρ ↦ K ρ K†` as ordinary real matrix products.
86pub(crate) fn embed_complex_square(entries: &[Complex<f64>], d: usize) -> DMatrix<f64> {
87    debug_assert_eq!(entries.len(), d * d);
88    DMatrix::from_fn(2 * d, 2 * d, |i, j| {
89        let qr = i / 2;
90        let qc = j / 2;
91        let sr = i % 2;
92        let sc = j % 2;
93        let z = entries[qr * d + qc];
94        block(z)[sr * 2 + sc]
95    })
96}
97
98/// Extract the complex entry `(i, j)` of a `d×d` complex matrix from its
99/// real `2d×2d` block embedding (the inverse of [`embed_complex_square`]).
100pub(crate) fn unembed_entry(real: &DMatrix<f64>, i: usize, j: usize) -> Complex<f64> {
101    Complex::new(real[(2 * i, 2 * j)], real[(2 * i + 1, 2 * j)])
102}
103
104/// Complex `4×4` matrix (row-major, 16 entries) of a controlled-`gate`.
105///
106/// `gate` is applied to `target` whenever `control` is set. The two qubits
107/// span the `lo = min(control, target)` (low bit) and `hi = max(...)`
108/// (high bit) positions of the 2-qubit index, so the result is independent of
109/// which physical qubit is the higher index.
110fn controlled_2q_matrix(
111    control: usize,
112    target: usize,
113    gate: &[Complex<f64>; 4],
114) -> [Complex<f64>; 16] {
115    let lo = control.min(target);
116    let mut m = [Complex::new(0.0, 0.0); 16];
117    for idx_in in 0..4usize {
118        let b_lo = idx_in & 1;
119        let b_hi = (idx_in >> 1) & 1;
120        let control_bit = if control == lo { b_lo } else { b_hi };
121        if control_bit == 0 {
122            m[idx_in * 4 + idx_in] = Complex::new(1.0, 0.0);
123        } else {
124            let target_in = if target == lo { b_lo } else { b_hi };
125            for out_t in 0..2usize {
126                let amp = gate[target_in * 2 + out_t];
127                if amp.norm_sqr() < 1e-30 {
128                    continue;
129                }
130                let mut idx_out = 0usize;
131                if control == lo {
132                    idx_out |= control_bit;
133                } else {
134                    idx_out |= control_bit << 1;
135                }
136                if target == lo {
137                    idx_out |= out_t;
138                } else {
139                    idx_out |= out_t << 1;
140                }
141                m[idx_out * 4 + idx_in] = amp;
142            }
143        }
144    }
145    m
146}
147
148/// Complex `4×4` SWAP matrix (row-major): `|01⟩ ↔ |10⟩`.
149fn swap_matrix() -> [Complex<f64>; 16] {
150    let mut m = [Complex::new(0.0, 0.0); 16];
151    m[0] = Complex::new(1.0, 0.0);
152    m[6] = Complex::new(1.0, 0.0);
153    m[9] = Complex::new(1.0, 0.0);
154    m[15] = Complex::new(1.0, 0.0);
155    m
156}
157
158/// An elementary gate recorded by [`Circuit`].
159#[derive(Clone)]
160enum Elem {
161    /// Single-qubit gate on one qubit (embedded as a `4×4` real block).
162    Single {
163        qubit: usize,
164        gate: [Complex<f64>; 4],
165    },
166    /// Two-qubit gate on an *adjacent* pair `(lo, lo + 1)`, embedded as an
167    /// `8×8` real block. Non-adjacent gates are decomposed into a sequence of
168    /// these plus SWAPs.
169    Pair {
170        lo: usize,
171        hi: usize,
172        matrix: [Complex<f64>; 16],
173    },
174}
175
176/// A circuit recorded as a sequence of single- and two-qubit gates.
177///
178/// Gates are stored verbatim and assembled into a single real-embedded unitary
179/// by [`Circuit::unitary`], which can then be applied to a [`State`] with
180/// [`State::apply_unitary`].
181///
182/// # Examples
183///
184/// ```
185/// use tpt_sci_quantum::Circuit;
186/// use tpt_sci_quantum::State;
187///
188/// let mut c = Circuit::new(2);
189/// c.h(0).cnot(0, 1);
190/// let u = c.unitary();
191/// let s = State::new(2).unwrap();
192/// let s2 = s.apply_unitary(&u).unwrap();
193/// let p = s2.probabilities();
194/// assert!((p[0] - 0.5).abs() < 1e-9);
195/// assert!((p[3] - 0.5).abs() < 1e-9);
196/// ```
197#[derive(Clone, Default)]
198pub struct Circuit {
199    n: usize,
200    elems: Vec<Elem>,
201}
202
203impl Circuit {
204    /// Create an empty circuit acting on `n` qubits.
205    #[must_use]
206    pub fn new(n: usize) -> Self {
207        Circuit {
208            n,
209            elems: Vec::new(),
210        }
211    }
212
213    /// The number of qubits this circuit acts on.
214    #[must_use]
215    pub fn n_qubits(&self) -> usize {
216        self.n
217    }
218
219    /// Record an arbitrary single-qubit `gate` on `qubit`.
220    pub fn gate(&mut self, qubit: usize, gate: [Complex<f64>; 4]) -> &mut Self {
221        self.elems.push(Elem::Single { qubit, gate });
222        self
223    }
224
225    /// Record a Hadamard gate on `qubit`.
226    pub fn h(&mut self, qubit: usize) -> &mut Self {
227        self.gate(qubit, crate::H)
228    }
229
230    /// Record a Pauli-X gate on `qubit`.
231    pub fn x(&mut self, qubit: usize) -> &mut Self {
232        self.gate(qubit, crate::X)
233    }
234
235    /// Record a Pauli-Y gate on `qubit`.
236    pub fn y(&mut self, qubit: usize) -> &mut Self {
237        self.gate(qubit, crate::Y)
238    }
239
240    /// Record a Pauli-Z gate on `qubit`.
241    pub fn z(&mut self, qubit: usize) -> &mut Self {
242        self.gate(qubit, crate::Z)
243    }
244
245    /// Record a phase `S` gate on `qubit`.
246    pub fn s(&mut self, qubit: usize) -> &mut Self {
247        self.gate(qubit, crate::S)
248    }
249
250    /// Record a `π/4` `T` gate on `qubit`.
251    pub fn t(&mut self, qubit: usize) -> &mut Self {
252        self.gate(qubit, crate::T)
253    }
254
255    /// Record a controlled-NOT: flip `target` whenever `control` is set.
256    pub fn cnot(&mut self, control: usize, target: usize) -> &mut Self {
257        self.controlled(control, target, crate::X)
258    }
259
260    /// Record a `gate` applied to `target`, controlled on `control == 1`.
261    ///
262    /// Non-adjacent `control`/`target` are handled by a SWAP decomposition:
263    /// the target is swapped down next to the control, the controlled gate is
264    /// applied on the adjacent pair, and the swaps are undone.
265    pub fn controlled(
266        &mut self,
267        control: usize,
268        target: usize,
269        gate: [Complex<f64>; 4],
270    ) -> &mut Self {
271        if control == target {
272            return self;
273        }
274        let c = control;
275        let t = target;
276        let lo = c.min(t);
277        let hi = c.max(t);
278
279        let mut ops: Vec<Elem> = Vec::new();
280        // Bring `target` (at `hi`) down to `lo + 1` by adjacent swaps.
281        for k in ((lo + 1)..hi).rev() {
282            ops.push(Elem::Pair {
283                lo: k,
284                hi: k + 1,
285                matrix: swap_matrix(),
286            });
287        }
288        ops.push(Elem::Pair {
289            lo,
290            hi: lo + 1,
291            matrix: controlled_2q_matrix(lo, lo + 1, &gate),
292        });
293        // Undo the swaps, restoring `target` to `hi`.
294        for k in (lo + 1)..hi {
295            ops.push(Elem::Pair {
296                lo: k,
297                hi: k + 1,
298                matrix: swap_matrix(),
299            });
300        }
301        self.elems.extend(ops);
302        self
303    }
304
305    /// Assemble the full real-embedded unitary (`2^(n+1) × 2^(n+1)`) of the
306    /// recorded circuit.
307    ///
308    /// Each elementary gate is expanded to a full-size matrix via Kronecker
309    /// products of per-qubit factors and the matrices are multiplied in
310    /// application order. The result can be applied with [`State::apply_unitary`].
311    #[must_use]
312    pub fn unitary(&self) -> DMatrix<f64> {
313        let n = self.n;
314        let expected = (1usize << n) * 2;
315        let mut acc = DMatrix::from_fn(expected, expected, |i, j| if i == j { 1.0 } else { 0.0 });
316        for e in &self.elems {
317            let m = match e {
318                Elem::Single { qubit, gate } => expand_single(n, *qubit, gate),
319                Elem::Pair { lo, hi, matrix } => expand_pair(n, *lo, *hi, matrix),
320            };
321            acc = m * acc;
322        }
323        acc
324    }
325}
326
327/// Expand a single-qubit gate to a full `2^(n+1) × 2^(.)` real-embedded matrix.
328///
329/// `pub(crate)` so the [`crate::density`] module can embed single-qubit Kraus
330/// operators (e.g. bit-flip/depolarizing noise) into the full `n`-qubit space
331/// the same way single-qubit gates are embedded here.
332pub(crate) fn expand_single(n: usize, qubit: usize, gate: &[Complex<f64>; 4]) -> DMatrix<f64> {
333    let block = embed_gate_2x2(gate);
334    let mut u: Option<DMatrix<f64>> = None;
335    for q in 0..n {
336        let f = if q == qubit {
337            block.clone()
338        } else {
339            identity_2x2()
340        };
341        u = Some(match u {
342            None => f,
343            Some(prev) => kron(&f, &prev),
344        });
345    }
346    u.expect("n >= 1")
347}
348
349/// Expand an adjacent two-qubit gate `(lo, lo + 1)` to a full real-embedded matrix.
350fn expand_pair(n: usize, lo: usize, hi: usize, matrix: &[Complex<f64>; 16]) -> DMatrix<f64> {
351    debug_assert_eq!(hi, lo + 1);
352    let block = embed_gate_4x4(matrix);
353    let mut u: Option<DMatrix<f64>> = None;
354    for q in 0..n {
355        if q == hi {
356            // Consumed by the combined `lo`/`hi` block; skip.
357            continue;
358        }
359        let f = if q == lo {
360            block.clone()
361        } else {
362            identity_2x2()
363        };
364        u = Some(match u {
365            None => f,
366            Some(prev) => kron(&f, &prev),
367        });
368    }
369    u.expect("n >= 2")
370}
371
372impl State {
373    /// Apply a real-embedded unitary `u` (as produced by [`Circuit::unitary`]
374    /// or built directly) to this state, returning the evolved state.
375    ///
376    /// The state's complex amplitude vector is embedded into a real
377    /// `DVector<f64>` (`2·2^n` long, interleaved real/imaginary parts),
378    /// multiplied by `u`, and un-embedded.
379    ///
380    /// # Errors
381    ///
382    /// Returns [`StateError::UnitarySizeMismatch`] if `u` is not
383    /// `2^(n+1) × 2^(n+1)` for this state's `n` qubits.
384    ///
385    /// # Examples
386    ///
387    /// ```
388    /// use tpt_sci_quantum::State;
389    /// use tpt_sci_quantum::tensor::kron;
390    /// use tpt_math_linalg::tpt_math_linalg_dense::DMatrix;
391    ///
392    /// // H ⊗ I on two qubits, built from per-qubit factors.
393    /// let h = tpt_sci_quantum::embed_gate_2x2(&tpt_sci_quantum::H);
394    /// let i2 = DMatrix::from_fn(2, 2, |a, b| if a == b { 1.0 } else { 0.0 });
395    /// let u = kron(&h, &i2);
396    /// let s = State::new(2).unwrap();
397    /// let s2 = s.apply_unitary(&u).unwrap();
398    /// assert!((s2.amplitude(0).re - std::f64::consts::FRAC_1_SQRT_2).abs() < 1e-9);
399    /// ```
400    pub fn apply_unitary(&self, u: &DMatrix<f64>) -> Result<State, StateError> {
401        let n = self.n_qubits();
402        let d = 1usize << n;
403        let expected = d * 2;
404        if u.nrows() != expected || u.ncols() != expected {
405            return Err(StateError::UnitarySizeMismatch {
406                expected,
407                got: u.nrows(),
408            });
409        }
410        let w = DVector::from_fn(expected, |k| {
411            let i = k / 2;
412            let part = k % 2;
413            let z = self.amps[i];
414            if part == 0 { z.re } else { z.im }
415        });
416        let out = u.clone() * w;
417        let mut amps = vec![Complex::new(0.0, 0.0); d];
418        for i in 0..d {
419            amps[i] = Complex::new(out[2 * i], out[2 * i + 1]);
420        }
421        Ok(State { amps })
422    }
423}
424
425#[cfg(test)]
426mod tests {
427    use super::*;
428    use crate::{H, X};
429    use approx::assert_abs_diff_eq;
430
431    const TOL: f64 = 1e-9;
432
433    #[test]
434    fn kron_identity_replicates_factor() {
435        let a = embed_gate_2x2(&H);
436        let i2 = DMatrix::from_fn(2, 2, |p, q| if p == q { 1.0 } else { 0.0 });
437        let k = kron(&a, &i2);
438        assert_eq!(k.nrows(), 8);
439        assert_eq!(k.ncols(), 8);
440    }
441
442    #[test]
443    fn single_h_matches_state_vector() {
444        let mut s = State::new(1).unwrap();
445        s.h(0).unwrap();
446        let expected = s.amplitudes().to_vec();
447
448        let mut c = Circuit::new(1);
449        c.h(0);
450        let u = c.unitary();
451        let s2 = State::new(1).unwrap().apply_unitary(&u).unwrap();
452        for (a, b) in expected.iter().zip(s2.amplitudes()) {
453            assert_abs_diff_eq!(a.re, b.re, epsilon = TOL);
454            assert_abs_diff_eq!(a.im, b.im, epsilon = TOL);
455        }
456    }
457
458    #[test]
459    fn bell_state_matches_unitary_path() {
460        // In-place path.
461        let mut s = State::new(2).unwrap();
462        s.h(0).unwrap();
463        s.cnot(0, 1).unwrap();
464        let expected = s.amplitudes().to_vec();
465
466        // Tensor (Kronecker) path.
467        let mut c = Circuit::new(2);
468        c.h(0).cnot(0, 1);
469        let u = c.unitary();
470        let s2 = State::new(2).unwrap().apply_unitary(&u).unwrap();
471        for (a, b) in expected.iter().zip(s2.amplitudes()) {
472            assert_abs_diff_eq!(a.re, b.re, epsilon = TOL);
473            assert_abs_diff_eq!(a.im, b.im, epsilon = TOL);
474        }
475    }
476
477    #[test]
478    fn ghz_with_nonadjacent_cnot() {
479        // In-place path: H(0), CNOT(0,1), CNOT(0,2) — note (0,2) is non-adjacent.
480        let mut s = State::new(3).unwrap();
481        s.h(0).unwrap();
482        s.cnot(0, 1).unwrap();
483        s.cnot(0, 2).unwrap();
484        let expected = s.amplitudes().to_vec();
485
486        // Tensor path must decompose the non-adjacent CNOT via SWAPs.
487        let mut c = Circuit::new(3);
488        c.h(0).cnot(0, 1).cnot(0, 2);
489        let u = c.unitary();
490        let s2 = State::new(3).unwrap().apply_unitary(&u).unwrap();
491        for (a, b) in expected.iter().zip(s2.amplitudes()) {
492            assert_abs_diff_eq!(a.re, b.re, epsilon = TOL);
493            assert_abs_diff_eq!(a.im, b.im, epsilon = TOL);
494        }
495        // GHZ: only |000⟩ and |111⟩ populated.
496        let inv = std::f64::consts::FRAC_1_SQRT_2;
497        assert_abs_diff_eq!(s2.amplitude(0).re, inv, epsilon = TOL);
498        assert_abs_diff_eq!(s2.amplitude(7).re, inv, epsilon = TOL);
499    }
500
501    #[test]
502    fn controlled_gate_matches_analytic() {
503        // Controlled-X with |0⟩ control leaves |00⟩ unchanged.
504        let mut c = Circuit::new(2);
505        c.controlled(0, 1, X);
506        let u = c.unitary();
507        let s2 = State::new(2).unwrap().apply_unitary(&u).unwrap();
508        assert_abs_diff_eq!(s2.amplitude(0).re, 1.0, epsilon = TOL);
509        assert_abs_diff_eq!(s2.amplitude(3).norm(), 0.0, epsilon = TOL);
510
511        // With a |1⟩ control (X(0) first), the target flips: |10⟩ → |11⟩.
512        let mut c2 = Circuit::new(2);
513        c2.x(0).controlled(0, 1, X);
514        let s3 = State::new(2).unwrap().apply_unitary(&c2.unitary()).unwrap();
515        assert_abs_diff_eq!(s3.amplitude(3).re, 1.0, epsilon = TOL);
516    }
517
518    #[test]
519    fn unitary_size_mismatch_is_rejected() {
520        let wrong = DMatrix::from_fn(4, 4, |i, j| if i == j { 1.0 } else { 0.0 });
521        let s = State::new(2).unwrap();
522        assert_eq!(
523            s.apply_unitary(&wrong),
524            Err(StateError::UnitarySizeMismatch {
525                expected: 8,
526                got: 4
527            })
528        );
529    }
530}