prism-q 0.28.0

PRISM-Q: Performance Rust Interoperable Simulator for Quantum
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

//! Integer-keyed hashing for hot maps.
//!
//! The stdlib default hasher is SipHash-1-3, which is collision-resistant
//! against adversarial keys. Nothing in this crate hashes untrusted input: keys
//! are basis-state indices and packed measurement words. The multiply-xor hash
//! below costs a rotate, an xor, and a multiply per word, which is what the
//! sparse state map and the shot histogram want on their inner loops.

use std::collections::HashMap;
use std::hash::{BuildHasher, Hasher};

pub(crate) struct FxHasher {
    hash: u64,
}

impl FxHasher {
    const SEED: u64 = 0x517cc1b727220a95;
}

impl Hasher for FxHasher {
    /// The multiply-xor step drives entropy toward the high bits while the
    /// table takes its bucket index from the low ones, so structured keys
    /// cluster. Basis-state indices from a low-entanglement circuit are exactly
    /// that, and the clustering grows with the key count: without this
    /// finalizer `sparse/low_entanglement` regresses 11.8% at 20 qubits while
    /// the high-entropy `sparse/random_d10` rows are unaffected.
    #[inline]
    fn finish(&self) -> u64 {
        let mut h = self.hash;
        h ^= h >> 33;
        h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
        h ^= h >> 33;
        h
    }

    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        for chunk in bytes.chunks(8) {
            let mut buf = [0u8; 8];
            buf[..chunk.len()].copy_from_slice(chunk);
            let word = u64::from_ne_bytes(buf);
            self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(Self::SEED);
        }
    }

    #[inline]
    fn write_u64(&mut self, i: u64) {
        self.hash = (self.hash.rotate_left(5) ^ i).wrapping_mul(Self::SEED);
    }

    #[inline]
    fn write_usize(&mut self, i: usize) {
        self.hash = (self.hash.rotate_left(5) ^ i as u64).wrapping_mul(Self::SEED);
    }
}

#[derive(Clone, Default)]
pub(crate) struct FxBuildHasher;

impl BuildHasher for FxBuildHasher {
    type Hasher = FxHasher;

    fn build_hasher(&self) -> FxHasher {
        FxHasher { hash: 0 }
    }
}

pub(crate) type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn fx_hasher_finish_changes_with_writes() {
        let mut h1 = FxBuildHasher.build_hasher();
        h1.write(&[1, 2, 3, 4, 5, 6, 7, 8, 9]);
        let v1 = h1.finish();
        let mut h2 = FxBuildHasher.build_hasher();
        h2.write_u64(42);
        h2.write_usize(7);
        let v2 = h2.finish();
        assert_ne!(v1, 0);
        assert_ne!(v2, 0);
        assert_ne!(v1, v2);
    }
}