use super::*;
const SLOTS: usize = 8192;
const PROBES: usize = 8;
pub(super) const MIN_STATES: usize = 128;
pub(super) const MIN_COEFFICIENTS: usize = 32;
pub(super) const MAX_COEFFICIENTS: usize = 4096;
#[derive(Clone, Copy)]
struct Entry {
node: usize,
fingerprint: u64,
id: usize,
}
#[cfg(test)]
mod tests {
use super::*;
fn state(values: &[ComplexAmp]) -> CachedState {
CachedState {
coefficients: Arc::new(values.to_vec()),
next_node: None,
transition: CachedOp::None,
}
}
#[test]
fn aliases_require_same_node_and_every_coefficient_bit() {
let values = [ComplexAmp::new(0.0, -0.0), ComplexAmp::new(0.5, 0.25)];
let states = vec![state(&values)];
let mut table = CoefficientIntern::new(usize::MAX).unwrap();
let (_, Some((slot, hash))) = table.find_or_slot(31, &values, &states) else {
panic!("empty index must offer a slot")
};
table.insert(slot, hash, 31, 0);
assert_eq!(table.find_or_slot(31, &values, &states).0, Some(0));
assert_eq!(table.find_or_slot(32, &values, &states).0, None);
assert_eq!(table.find_or_slot(31, &values[..1], &states).0, None);
let mut changed = values;
changed[0].im = 0.0;
assert_eq!(table.find_or_slot(31, &changed, &states).0, None);
changed = values;
changed[1].re = f64::from_bits(0.5f64.to_bits() + 1);
assert_eq!(table.find_or_slot(31, &changed, &states).0, None);
}
#[test]
fn colliding_fingerprints_are_checked_and_full_probe_window_declines() {
let query = [ComplexAmp::new(0.25, 0.5), ComplexAmp::new(0.5, 0.0)];
let other = [ComplexAmp::new(0.5, 0.25), ComplexAmp::new(0.5, 0.0)];
let states = vec![state(&other), state(&query)];
let mut table = CoefficientIntern::new(usize::MAX).unwrap();
let (_, Some((start, hash))) = table.find_or_slot(27, &query, &states) else {
panic!("empty index must offer a slot")
};
for offset in 0..PROBES {
table.insert((start + offset) & (SLOTS - 1), hash, 27, 0);
}
assert_eq!(table.find_or_slot(27, &query, &states), (None, None));
table.entries[(start + PROBES - 1) & (SLOTS - 1)].id = 1;
assert_eq!(table.find_or_slot(27, &query, &states), (Some(1), None));
}
#[test]
fn unsampled_coefficient_difference_cannot_alias_a_sparse_fingerprint() {
let values = vec![ComplexAmp::new(0.25, -0.5); 64];
let mut different = values.clone();
different[11].im = f64::from_bits((-0.5f64).to_bits() + 1);
assert_eq!(
CoefficientIntern::fingerprint(29, &values),
CoefficientIntern::fingerprint(29, &different)
);
let states = vec![state(&values)];
let mut table = CoefficientIntern::new(usize::MAX).unwrap();
let (_, Some((slot, hash))) = table.find_or_slot(29, &values, &states) else {
panic!("empty index must offer a slot")
};
table.insert(slot, hash, 29, 0);
assert_eq!(table.find_or_slot(29, &values, &states).0, Some(0));
assert_eq!(table.find_or_slot(29, &different, &states).0, None);
}
#[test]
fn original_cultivation_counts_delay_index_then_reuse_states_with_exact_rng() {
use rand::{RngCore, SeedableRng, rngs::StdRng};
use std::collections::HashSet;
let text = include_str!(
"../../../benchmarks/near_clifford/application_counts/fixtures/msc_d5_inject_cultivate_p1e-3.stim"
);
for arithmetic in [
CompiledRotationArithmetic::Strict,
CompiledRotationArithmetic::Fused,
] {
let plan = CompiledNearCliffordExecutor::compile_text_with_arithmetic(text, arithmetic)
.unwrap();
let mut cached = plan.prepare_sampler().unwrap();
let mut scalar = plan.prepare_sampler_with_cache_budget(0).unwrap();
let mut a = StdRng::seed_from_u64(1739);
let mut b = a.clone();
for shots in [1, 64, 1024, 64] {
let rows = scalar.sample(shots, &mut b).unwrap();
let accepted: Vec<_> = rows
.iter()
.filter(|r| r.detectors.iter().all(|&v| !v))
.collect();
let expected = NearCliffordPostselectedCounts {
attempted: shots,
accepted: accepted.len(),
logical_errors: accepted
.iter()
.filter(|r| {
r.observables
.iter()
.filter(|(i, _)| *i == 0)
.fold(false, |v, (_, bit)| v ^ bit)
})
.count(),
};
assert_eq!(
cached.sample_postselected_counts(shots, 0, &mut a).unwrap(),
expected
);
if shots == 1 {
assert!(cached.cache.as_ref().unwrap().intern.is_none());
}
for _ in 0..16 {
assert_eq!(a.next_u64(), b.next_u64());
}
}
assert_eq!(
cached.sample_measurements_u8(17, &mut a).unwrap(),
scalar.sample_measurements_u8(17, &mut b).unwrap()
);
for _ in 0..16 {
assert_eq!(a.next_u64(), b.next_u64());
}
let cache = cached.cache.as_ref().unwrap();
assert!(
cache.intern.is_some(),
"bulk calls must actually activate the optional index"
);
let mut children = HashSet::new();
let mut reused = false;
let edges = cache.nodes.iter().copied().enumerate().chain(
cache
.states
.iter()
.skip(1)
.filter_map(|s| s.next_node.map(|n| (n, s.transition))),
);
for (node, op) in edges {
let next = match op {
CachedOp::Rotate(next) => next,
CachedOp::Measure(m) => m.next,
CachedOp::None => [None; 2],
};
for child in next.into_iter().flatten().filter(|&id| id != 0) {
reused |= !children.insert((node, child));
}
}
assert!(
reused,
"the original circuit must witness an exactly reused coherent state"
);
}
}
#[test]
fn index_capacity_is_charged_and_small_budget_declines() {
assert!(CoefficientIntern::new(0).is_none());
assert!(CoefficientIntern::new(SLOTS * size_of::<Entry>() - 1).is_none());
let table = CoefficientIntern::new(usize::MAX).unwrap();
assert!(table.reserved_bytes() >= SLOTS * size_of::<Entry>());
assert_eq!(table.entries.len(), SLOTS);
}
#[test]
fn small_vectors_keep_ordinary_admission_without_constructing_an_index() {
let plan = CompiledNearCliffordExecutor::compile_text("H 0\nT 0\nMY 0\n").unwrap();
let mut cache = CoefficientCache::new(&plan, DEFAULT_CACHE_BYTE_BUDGET).unwrap();
let values = vec![ComplexAmp::new(0.5, -0.25); MIN_COEFFICIENTS / 2];
let initial = cache.reserved;
let charge = CoefficientCache::state_charge(&values).unwrap();
for node in 0..2 * MIN_STATES {
let id = cache.store(node, &values).unwrap();
assert_eq!(&*cache.states[id].coefficients, &values);
assert!(cache.intern.is_none());
assert!(!cache.intern_attempted);
assert_eq!(cache.reserved, initial + (node + 1) * charge);
}
let larger = vec![ComplexAmp::new(0.5, -0.25); MIN_COEFFICIENTS];
let id = cache.store(311, &larger).unwrap();
assert!(cache.intern.is_some());
assert_eq!(cache.store(311, &larger), Some(id));
}
#[test]
fn lazy_interning_reuses_exact_states_until_admission_closes() {
let plan = CompiledNearCliffordExecutor::compile_text("H 0\nT 0\nMY 0\n").unwrap();
let mut cache = CoefficientCache::new(&plan, DEFAULT_CACHE_BYTE_BUDGET).unwrap();
let initial = cache.reserved;
assert!(cache.intern.is_none());
let values = vec![ComplexAmp::new(0.5, 0.25); MIN_COEFFICIENTS];
let first_cold = cache.store(23, &values).unwrap();
assert!(cache.intern.is_none());
assert!(!cache.intern_attempted);
assert_eq!(
cache.reserved,
initial + CoefficientCache::state_charge(&values).unwrap()
);
for node in 100.. {
if cache.states.len() >= MIN_STATES {
break;
}
cache.store(node, &values).unwrap();
assert!(cache.intern.is_none());
assert!(!cache.intern_attempted);
}
assert_eq!(&*cache.states[first_cold].coefficients, &values);
let first = cache.store(23, &values).unwrap();
assert_ne!(first, first_cold);
assert!(cache.intern.is_some());
assert!(cache.reserved > initial);
let reserved = cache.reserved;
let states = cache.states.len();
assert_eq!(cache.store(23, &values), Some(first));
assert_eq!(cache.reserved, reserved);
assert_eq!(cache.states.len(), states);
cache.budget = reserved;
assert_eq!(cache.store(23, &values), None);
assert_eq!(cache.store(24, &values), None);
assert_eq!(cache.reserved, reserved);
assert_eq!(cache.states.len(), states);
}
}
pub(super) struct CoefficientIntern {
entries: Vec<Entry>,
}
impl CoefficientIntern {
pub(super) fn new(remaining_bytes: usize) -> Option<Self> {
let requested = SLOTS.checked_mul(size_of::<Entry>())?;
if requested > remaining_bytes {
return None;
}
let mut entries = Vec::new();
entries.try_reserve_exact(SLOTS).ok()?;
if entries.capacity().checked_mul(size_of::<Entry>())? > remaining_bytes {
return None;
}
entries.resize(
SLOTS,
Entry {
node: 0,
fingerprint: 0,
id: usize::MAX,
},
);
Some(Self { entries })
}
pub(super) fn reserved_bytes(&self) -> usize {
self.entries.capacity() * size_of::<Entry>()
}
fn fingerprint(node: usize, coefficients: &[ComplexAmp]) -> u64 {
let mut hash = (node as u64) ^ (coefficients.len() as u64).rotate_left(17);
let mut mix = |index: usize| {
if let Some(value) = coefficients.get(index) {
hash = (hash ^ value.re.to_bits())
.rotate_left(13)
.wrapping_mul(0x9e3779b185ebca87);
hash = (hash ^ value.im.to_bits())
.rotate_left(17)
.wrapping_mul(0xc2b2ae3d27d4eb4f);
}
};
mix(0);
for bit in 0..usize::BITS {
let index = 1usize << bit;
if index >= coefficients.len() {
break;
}
mix(index);
}
mix(coefficients.len().saturating_sub(1));
mix(coefficients.len() / 3);
mix(2 * (coefficients.len() / 3));
hash ^ (hash >> 29)
}
pub(super) fn find_or_slot(
&self,
node: usize,
coefficients: &[ComplexAmp],
states: &[CachedState],
) -> (Option<usize>, Option<(usize, u64)>) {
let hash = Self::fingerprint(node, coefficients);
let start = hash as usize & (SLOTS - 1);
for offset in 0..PROBES {
let slot = (start + offset) & (SLOTS - 1);
let entry = self.entries[slot];
if entry.id == usize::MAX {
return (None, Some((slot, hash)));
}
if entry.node == node && entry.fingerprint == hash {
let prior = &states[entry.id].coefficients;
if prior.len() == coefficients.len()
&& prior.iter().zip(coefficients).all(|(a, b)| {
a.re.to_bits() == b.re.to_bits() && a.im.to_bits() == b.im.to_bits()
})
{
return (Some(entry.id), None);
}
}
}
(None, None)
}
pub(super) fn insert(&mut self, slot: usize, fingerprint: u64, node: usize, id: usize) {
debug_assert_eq!(self.entries[slot].id, usize::MAX);
self.entries[slot] = Entry {
node,
fingerprint,
id,
};
}
}