1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
//! State-vector representation of an n-qubit register.
use crate::rng::Rng;
use num_complex::Complex64;
#[cfg(feature = "parallel")]
use rayon::prelude::*;
/// The full state vector of an `n`-qubit quantum register.
///
/// Amplitudes are stored in little-endian order: index `i` corresponds to
/// the computational basis state whose bit `q` equals `(i >> q) & 1`.
#[derive(Debug, Clone, PartialEq)]
pub struct State {
n_qubits: usize,
amps: Vec<Complex64>,
}
impl State {
/// Create the |0...0> state for `n_qubits` qubits.
pub fn new(n_qubits: usize) -> Self {
let mut amps = vec![Complex64::new(0.0, 0.0); 1usize << n_qubits];
amps[0] = Complex64::new(1.0, 0.0);
State { n_qubits, amps }
}
/// Number of qubits in the register.
pub fn n_qubits(&self) -> usize {
self.n_qubits
}
/// Read-only access to the amplitude vector.
pub fn amplitudes(&self) -> &[Complex64] {
&self.amps
}
/// Probability of measuring basis state `index`.
pub fn probability(&self, index: usize) -> f64 {
self.amps[index].norm_sqr()
}
/// Apply a single-qubit gate (2x2 unitary) to qubit `target`.
///
/// The amplitude vector splits into contiguous blocks of `2·2^target`,
/// and within each block the low and high halves are the `|0>`/`|1>`
/// partners of the target bit. Iterating over those halves with slice
/// iterators keeps the inner loop bounds-check-free.
///
/// With the `parallel` feature this runs across threads via rayon,
/// parallelizing over blocks for a low target qubit and within a block for
/// a high one — whichever axis carries more work.
pub fn apply_1q(&mut self, gate: &[[Complex64; 2]; 2], target: usize) {
assert!(target < self.n_qubits, "target qubit out of range");
// Hoist the matrix entries so the inner loop does not reload them.
let (g00, g01) = (gate[0][0], gate[0][1]);
let (g10, g11) = (gate[1][0], gate[1][1]);
let butterfly = move |a: &mut Complex64, b: &mut Complex64| {
let (x, y) = (*a, *b);
*a = g00 * x + g01 * y;
*b = g10 * x + g11 * y;
};
let step = 1usize << target;
let block = step << 1;
#[cfg(feature = "parallel")]
{
// A coarse tile so parallel tasks are large enough to amortize
// scheduling overhead (a block can be as small as two amplitudes).
const TILE: usize = 1 << 14;
if block <= TILE {
// Low target: parallelize over tiles, each holding many blocks.
self.amps.par_chunks_mut(TILE).for_each(|region| {
for blk in region.chunks_exact_mut(block) {
let (low, high) = blk.split_at_mut(step);
low.iter_mut()
.zip(high.iter_mut())
.for_each(|(a, b)| butterfly(a, b));
}
});
} else {
// High target: few large blocks, so parallelize their halves.
for blk in self.amps.chunks_exact_mut(block) {
let (low, high) = blk.split_at_mut(step);
low.par_iter_mut()
.zip(high.par_iter_mut())
.for_each(|(a, b)| butterfly(a, b));
}
}
}
#[cfg(not(feature = "parallel"))]
{
for blk in self.amps.chunks_exact_mut(block) {
let (low, high) = blk.split_at_mut(step);
low.iter_mut()
.zip(high.iter_mut())
.for_each(|(a, b)| butterfly(a, b));
}
}
}
/// Apply a controlled single-qubit gate: `gate` acts on `target`
/// only when `control` is |1>.
pub fn apply_controlled_1q(
&mut self,
gate: &[[Complex64; 2]; 2],
control: usize,
target: usize,
) {
assert!(control < self.n_qubits, "control qubit out of range");
assert!(target < self.n_qubits, "target qubit out of range");
assert_ne!(control, target, "control and target must differ");
// With a single control bit, `(j & cmask) != 0` and `== cmask` agree.
self.apply_masked(gate, 1usize << control, target);
}
/// Apply a single-qubit `gate` to `target`, but only on basis states
/// where **every** qubit in `controls` is |1>.
///
/// This generalizes [`apply_controlled_1q`](Self::apply_controlled_1q) to
/// any number of controls: zero controls degenerate to an unconditional
/// gate, one control reproduces `apply_controlled_1q`, and two controls
/// with an X gate give a Toffoli. Controls must be distinct from `target`.
pub fn apply_multi_controlled_1q(
&mut self,
gate: &[[Complex64; 2]; 2],
controls: &[usize],
target: usize,
) {
assert!(target < self.n_qubits, "target qubit out of range");
let mut cmask = 0usize;
for &ctrl in controls {
assert!(ctrl < self.n_qubits, "control qubit out of range");
assert_ne!(ctrl, target, "control and target must differ");
cmask |= 1usize << ctrl;
}
self.apply_masked(gate, cmask, target);
}
/// Apply `gate`'s butterfly to the `target` bit's `|0>`/`|1>` pairs, but
/// only for basis states where every bit in `cmask` is set. Shared by the
/// controlled and multi-controlled kernels (a single control is just a
/// one-bit `cmask`).
///
/// Structurally identical to [`apply_1q`](Self::apply_1q) — a walk over the
/// target bit's halves — with a per-pair `cmask` test on the absolute
/// index. With the `parallel` feature it threads the same way.
fn apply_masked(&mut self, gate: &[[Complex64; 2]; 2], cmask: usize, target: usize) {
let (g00, g01) = (gate[0][0], gate[0][1]);
let (g10, g11) = (gate[1][0], gate[1][1]);
// `base` is the absolute index of `low[0]` in its block; the pair for
// `low[k]` sits at index `base + k`, whose control bits we test.
let butterfly = move |base: usize, k: usize, a: &mut Complex64, b: &mut Complex64| {
if ((base + k) & cmask) == cmask {
let (x, y) = (*a, *b);
*a = g00 * x + g01 * y;
*b = g10 * x + g11 * y;
}
};
let step = 1usize << target;
let block = step << 1;
#[cfg(feature = "parallel")]
{
const TILE: usize = 1 << 14;
if block <= TILE {
self.amps
.par_chunks_mut(TILE)
.enumerate()
.for_each(|(t, region)| {
let region_base = t * TILE;
for (bi, blk) in region.chunks_exact_mut(block).enumerate() {
let base = region_base + bi * block;
let (low, high) = blk.split_at_mut(step);
for (k, (a, b)) in low.iter_mut().zip(high.iter_mut()).enumerate() {
butterfly(base, k, a, b);
}
}
});
} else {
for (bi, blk) in self.amps.chunks_exact_mut(block).enumerate() {
let base = bi * block;
let (low, high) = blk.split_at_mut(step);
low.par_iter_mut()
.zip(high.par_iter_mut())
.enumerate()
.for_each(|(k, (a, b))| butterfly(base, k, a, b));
}
}
}
#[cfg(not(feature = "parallel"))]
{
for (bi, blk) in self.amps.chunks_exact_mut(block).enumerate() {
let base = bi * block;
let (low, high) = blk.split_at_mut(step);
for (k, (a, b)) in low.iter_mut().zip(high.iter_mut()).enumerate() {
butterfly(base, k, a, b);
}
}
}
}
/// Exchange the states of qubits `a` and `b`.
///
/// Implemented by swapping the amplitudes of every basis-state pair that
/// differs only in these two bits (i.e. |..1..0..> <-> |..0..1..>). Each
/// pair is touched exactly once.
pub fn swap_qubits(&mut self, a: usize, b: usize) {
assert!(a < self.n_qubits, "qubit a out of range");
assert!(b < self.n_qubits, "qubit b out of range");
if a == b {
return;
}
let amask = 1usize << a;
let bmask = 1usize << b;
for i in 0..self.amps.len() {
// Act once per pair: pick the index with bit a set and bit b clear,
// then swap it with its partner (bit a clear, bit b set).
if (i & amask) != 0 && (i & bmask) == 0 {
let j = (i & !amask) | bmask;
self.amps.swap(i, j);
}
}
}
/// Total probability (should stay ~1.0). Useful for sanity checks/tests.
pub fn norm(&self) -> f64 {
self.amps.iter().map(|c| c.norm_sqr()).sum()
}
/// Expectation `<psi|M|psi>` of a single-qubit Hermitian `m` on qubit `q`.
///
/// One read-only pass over the amplitudes, so a Kraus branch probability
/// costs no allocation and no clone of the state vector.
fn expectation_1q(&self, m: &[[Complex64; 2]; 2], q: usize) -> f64 {
let mask = 1usize << q;
let mut total = 0.0;
for (i, a0) in self.amps.iter().enumerate() {
if i & mask != 0 {
continue;
}
let a1 = self.amps[i | mask];
let v0 = m[0][0] * a0 + m[0][1] * a1;
let v1 = m[1][0] * a0 + m[1][1] * a1;
// `m` is Hermitian, so this is real; the imaginary part is rounding.
total += (a0.conj() * v0 + a1.conj() * v1).re;
}
total
}
/// Apply a quantum channel to `q` by sampling one Kraus operator, returning
/// which one was taken.
///
/// This is the quantum-trajectory (Monte Carlo wave function) method: a
/// channel that would otherwise need a density matrix is simulated by
/// choosing operator `K_i` with probability `<psi|K_i^dagger K_i|psi>` and
/// renormalizing. Averaged over shots the ensemble reproduces the density
/// matrix, so a state vector suffices — at the cost of needing many shots.
///
/// `ops` should be trace preserving; see
/// [`noise::is_trace_preserving`](crate::noise::is_trace_preserving). The
/// probabilities are normalized before sampling regardless, so a set that
/// is slightly off from rounding still behaves.
pub fn apply_kraus(&mut self, ops: &[[[Complex64; 2]; 2]], q: usize, rng: &mut Rng) -> usize {
assert!(q < self.n_qubits, "qubit out of range");
assert!(
!ops.is_empty(),
"a channel needs at least one Kraus operator"
);
let probs: Vec<f64> = ops
.iter()
.map(|k| self.expectation_1q(&dagger_product(k), q).max(0.0))
.collect();
let total: f64 = probs.iter().sum();
assert!(total > 0.0, "channel has zero probability on this state");
// Walk the cumulative distribution to pick a branch.
let mut r = rng.next_f64() * total;
let mut chosen = probs.len() - 1;
for (i, p) in probs.iter().enumerate() {
if r < *p {
chosen = i;
break;
}
r -= p;
}
self.apply_1q(&ops[chosen], q);
// The chosen branch carried probability `probs[chosen]`; scale back to
// a unit vector.
let scale = 1.0 / probs[chosen].sqrt();
for a in self.amps.iter_mut() {
*a *= scale;
}
chosen
}
/// Probability that qubit `q` is measured in the |1> state.
///
/// This is the sum of `|amplitude|^2` over every basis state whose
/// bit `q` is set. Does not modify the state.
pub fn prob_qubit_one(&self, q: usize) -> f64 {
assert!(q < self.n_qubits, "qubit out of range");
let mask = 1usize << q;
self.amps
.iter()
.enumerate()
.filter(|(i, _)| (i & mask) != 0)
.map(|(_, a)| a.norm_sqr())
.sum()
}
/// Measure qubit `q` in the computational basis.
///
/// Samples an outcome (`true` = |1>, `false` = |0>) via the Born rule,
/// then collapses the state onto the measured subspace and renormalizes
/// so the surviving amplitudes again sum to probability 1.
pub fn measure_qubit(&mut self, q: usize, rng: &mut Rng) -> bool {
assert!(q < self.n_qubits, "qubit out of range");
let mask = 1usize << q;
let p1 = self.prob_qubit_one(q);
let outcome = rng.next_f64() < p1;
// Probability mass of the branch we are keeping.
let branch_prob = if outcome { p1 } else { 1.0 - p1 };
// Guard against dividing by zero if the branch has (numerically) no
// amplitude; in that case the surviving amplitudes are all zero anyway.
let inv_norm = if branch_prob > 0.0 {
1.0 / branch_prob.sqrt()
} else {
0.0
};
for (i, a) in self.amps.iter_mut().enumerate() {
let bit_set = (i & mask) != 0;
if bit_set == outcome {
*a *= inv_norm;
} else {
*a = Complex64::new(0.0, 0.0);
}
}
outcome
}
/// Measure every qubit at once, returning the sampled basis-state index.
///
/// The outcome is drawn from the full Born-rule distribution
/// `p(i) = |amplitude(i)|^2` and the state collapses onto that single
/// basis state. The returned `usize` is little-endian: bit `q` is the
/// measured value of qubit `q`.
pub fn measure_all(&mut self, rng: &mut Rng) -> usize {
let r = rng.next_f64();
let mut cumulative = 0.0;
// Default to the last basis state carrying nonzero amplitude. This
// guards the edge case where floating-point roundoff leaves the
// cumulative sum just shy of `r`.
let mut outcome = 0;
for (i, a) in self.amps.iter().enumerate() {
let p = a.norm_sqr();
if p > 0.0 {
outcome = i;
}
cumulative += p;
if r < cumulative {
outcome = i;
break;
}
}
for (i, a) in self.amps.iter_mut().enumerate() {
*a = if i == outcome {
Complex64::new(1.0, 0.0)
} else {
Complex64::new(0.0, 0.0)
};
}
outcome
}
}
/// `K^dagger K` for a 2x2 operator — the positive matrix whose expectation on
/// the state is the probability of taking that Kraus branch.
fn dagger_product(k: &[[Complex64; 2]; 2]) -> [[Complex64; 2]; 2] {
let entry = |i: usize, j: usize| k[0][i].conj() * k[0][j] + k[1][i].conj() * k[1][j];
[[entry(0, 0), entry(0, 1)], [entry(1, 0), entry(1, 1)]]
}