1use num_complex::Complex;
18use tpt_math_linalg::tpt_math_linalg_dense::{DMatrix, DVector};
19
20use crate::{State, StateError};
21
22#[inline]
24fn block(z: Complex<f64>) -> [f64; 4] {
25 [z.re, -z.im, z.im, z.re]
26}
27
28pub 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
44pub 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
56pub 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
68fn identity_2x2() -> DMatrix<f64> {
70 DMatrix::from_fn(2, 2, |i, j| if i == j { 1.0 } else { 0.0 })
71}
72
73pub(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
98pub(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
104fn 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
148fn 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#[derive(Clone)]
160enum Elem {
161 Single {
163 qubit: usize,
164 gate: [Complex<f64>; 4],
165 },
166 Pair {
170 lo: usize,
171 hi: usize,
172 matrix: [Complex<f64>; 16],
173 },
174}
175
176#[derive(Clone, Default)]
198pub struct Circuit {
199 n: usize,
200 elems: Vec<Elem>,
201}
202
203impl Circuit {
204 #[must_use]
206 pub fn new(n: usize) -> Self {
207 Circuit {
208 n,
209 elems: Vec::new(),
210 }
211 }
212
213 #[must_use]
215 pub fn n_qubits(&self) -> usize {
216 self.n
217 }
218
219 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 pub fn h(&mut self, qubit: usize) -> &mut Self {
227 self.gate(qubit, crate::H)
228 }
229
230 pub fn x(&mut self, qubit: usize) -> &mut Self {
232 self.gate(qubit, crate::X)
233 }
234
235 pub fn y(&mut self, qubit: usize) -> &mut Self {
237 self.gate(qubit, crate::Y)
238 }
239
240 pub fn z(&mut self, qubit: usize) -> &mut Self {
242 self.gate(qubit, crate::Z)
243 }
244
245 pub fn s(&mut self, qubit: usize) -> &mut Self {
247 self.gate(qubit, crate::S)
248 }
249
250 pub fn t(&mut self, qubit: usize) -> &mut Self {
252 self.gate(qubit, crate::T)
253 }
254
255 pub fn cnot(&mut self, control: usize, target: usize) -> &mut Self {
257 self.controlled(control, target, crate::X)
258 }
259
260 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 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 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 #[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
327pub(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
349fn 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 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 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 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 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 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 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 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 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 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}