use crate::ir::{StimInstr, StimTarget};
use crate::sim::packed_inverse_tableau::CanonicalTableauSnapshot;
use crate::sim::symbolic_mask::SymbolicMask;
use crate::sim::tableau::StabilizerState;
use rand::{Rng, SeedableRng, rngs::StdRng};
use std::sync::{Arc, OnceLock};
mod compiled;
pub use compiled::{
CompiledNearCliffordEagerSampler, CompiledNearCliffordExecutor, CompiledNearCliffordSampler,
CompiledRotationArithmetic,
};
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct ComplexAmp {
pub re: f64,
pub im: f64,
}
impl ComplexAmp {
pub const fn new(re: f64, im: f64) -> Self {
Self { re, im }
}
pub fn norm_sqr(self) -> f64 {
self.re * self.re + self.im * self.im
}
pub fn conj(self) -> Self {
Self::new(self.re, -self.im)
}
}
impl std::ops::Add for ComplexAmp {
type Output = Self;
fn add(self, rhs: Self) -> Self {
Self::new(self.re + rhs.re, self.im + rhs.im)
}
}
impl std::ops::Mul for ComplexAmp {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
Self::new(
self.re * rhs.re - self.im * rhs.im,
self.re * rhs.im + self.im * rhs.re,
)
}
}
impl std::ops::Mul<f64> for ComplexAmp {
type Output = Self;
fn mul(self, rhs: f64) -> Self {
Self::new(self.re * rhs, self.im * rhs)
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum CliffordGate {
H(usize),
S(usize),
SDag(usize),
X(usize),
Y(usize),
Z(usize),
CX(usize, usize),
CZ(usize, usize),
Swap(usize, usize),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum MeasurementBasis {
X,
Y,
Z,
}
#[derive(Clone, Debug)]
pub struct ActiveState {
num_qubits: usize,
frame: Arc<StabilizerState>,
origin: Vec<bool>,
axes: Vec<Vec<bool>>,
axes_are_canonical: bool,
coefficients: Vec<ComplexAmp>,
global_phase: ComplexAmp,
max_active_qubits: usize,
}
impl ActiveState {
pub fn new(num_qubits: usize, max_active_qubits: usize) -> Self {
Self {
num_qubits,
frame: Arc::new(StabilizerState::new(num_qubits)),
origin: vec![false; num_qubits],
axes: Vec::new(),
axes_are_canonical: true,
coefficients: vec![ComplexAmp::new(1.0, 0.0)],
global_phase: ComplexAmp::new(1.0, 0.0),
max_active_qubits,
}
}
pub fn num_qubits(&self) -> usize {
self.num_qubits
}
pub fn active_rank(&self) -> usize {
self.axes.len()
}
pub fn active_axes(&self) -> &[Vec<bool>] {
&self.axes
}
pub fn origin(&self) -> &[bool] {
&self.origin
}
pub fn coefficients(&self) -> &[ComplexAmp] {
&self.coefficients
}
pub fn global_phase(&self) -> ComplexAmp {
self.global_phase
}
pub fn frame_snapshot(&self) -> CanonicalTableauSnapshot {
self.frame.canonical_snapshot()
}
pub fn apply_clifford(&mut self, gate: CliffordGate) -> Result<(), String> {
use CliffordGate::*;
let n = self.num_qubits();
let check_one = |q: usize| {
if q < n {
Ok(())
} else {
Err(format!("qubit {q} outside {n}-qubit near-Clifford state"))
}
};
match gate {
H(q) | S(q) | SDag(q) | X(q) | Y(q) | Z(q) => check_one(q)?,
CX(a, b) | CZ(a, b) | Swap(a, b) => {
check_one(a)?;
check_one(b)?;
if a == b {
return Err("two-qubit Clifford gate requires distinct targets".into());
}
}
}
match gate {
H(q) => Arc::make_mut(&mut self.frame).h(q),
S(q) => Arc::make_mut(&mut self.frame).s(q),
SDag(q) => Arc::make_mut(&mut self.frame).s_dag_near_clifford(q),
X(q) => Arc::make_mut(&mut self.frame).x_gate(q),
Y(q) => Arc::make_mut(&mut self.frame).y_near_clifford(q),
Z(q) => Arc::make_mut(&mut self.frame).z_gate(q),
CX(a, b) => Arc::make_mut(&mut self.frame).cx(a, b),
CZ(a, b) => Arc::make_mut(&mut self.frame).cz_near_clifford(a, b),
Swap(a, b) => Arc::make_mut(&mut self.frame).swap(a, b),
}
Ok(())
}
pub fn t(&mut self, q: usize) -> Result<(), String> {
self.rotate_z(q, false)
}
pub fn t_dag(&mut self, q: usize) -> Result<(), String> {
self.rotate_z(q, true)
}
fn rotate_z(&mut self, q: usize, dagger: bool) -> Result<(), String> {
if q >= self.num_qubits() {
return Err(format!("qubit {q} outside near-Clifford state"));
}
let n = self.num_qubits();
let mut physical_z = vec![false; n];
physical_z[q] = true;
let pauli = self.physical_pauli(&vec![false; n], &physical_z)?;
let mask = self.ensure_axis(&pauli.x)?;
let old = self.coefficients.clone();
let mut next = vec![ComplexAmp::default(); old.len()];
let c = (std::f64::consts::PI / 8.0).cos();
let s = (std::f64::consts::PI / 8.0).sin();
let rotation = ComplexAmp::new(0.0, if dagger { s } else { -s });
let (sign_origin, sign_mask) = self.sign_coordinates(&pauli.z);
for (index, amplitude) in old.iter().copied().enumerate() {
let sign = if sign_origin ^ ((index & sign_mask).count_ones() & 1 != 0) {
-1.0
} else {
1.0
};
let image = i_pow(pauli.phase) * (amplitude * sign);
next[index] = next[index] + amplitude * c;
next[index ^ mask] = next[index ^ mask] + image * rotation;
}
self.coefficients = next;
let angle = if dagger {
-std::f64::consts::PI / 8.0
} else {
std::f64::consts::PI / 8.0
};
self.global_phase = self.global_phase * ComplexAmp::new(angle.cos(), angle.sin());
Ok(())
}
fn rotate_axis(
&mut self,
q: usize,
basis: MeasurementBasis,
half_turns: f64,
) -> Result<(), String> {
if q >= self.num_qubits() || !half_turns.is_finite() {
return Err("near-Clifford rotation requires a finite angle and valid qubit".into());
}
if let Some(quarters) = rotation_clifford_quarters(half_turns) {
for _ in 0..quarters {
for gate in quarter_rotation_gates(q, basis).into_iter().flatten() {
self.apply_clifford(gate)?;
}
}
if basis != MeasurementBasis::Y {
let phase = -f64::from(quarters) * std::f64::consts::PI / 4.0;
self.global_phase = self.global_phase * ComplexAmp::new(phase.cos(), phase.sin());
}
return Ok(());
}
let (c, s) = rotation_coefficients(half_turns);
if s == 0.0 {
self.global_phase = self.global_phase * c;
return Ok(());
}
let mut x = vec![false; self.num_qubits()];
let mut z = x.clone();
x[q] = basis != MeasurementBasis::Z;
z[q] = basis != MeasurementBasis::X;
let pauli = self.physical_pauli(&x, &z)?;
let mask = self.ensure_axis(&pauli.x)?;
let old = self.coefficients.clone();
let mut next = vec![ComplexAmp::default(); old.len()];
let (origin, sign_mask) = self.sign_coordinates(&pauli.z);
let factor = ComplexAmp::new(0.0, -s);
for (index, amplitude) in old.into_iter().enumerate() {
let sign = if origin ^ ((index & sign_mask).count_ones() & 1 != 0) {
-1.0
} else {
1.0
};
next[index] = next[index] + amplitude * c;
next[index ^ mask] =
next[index ^ mask] + i_pow(pauli.phase) * (amplitude * sign) * factor;
}
self.coefficients = next;
Ok(())
}
pub fn measurement_probabilities(
&self,
q: usize,
basis: MeasurementBasis,
) -> Result<(f64, f64), String> {
let pauli = self.single_qubit_pauli(q, basis)?;
let (mask, independent) = self.coordinate_mask(&pauli.x);
let zero = self.pauli_probability_zero(&pauli, mask, independent);
Ok((zero, 1.0 - zero))
}
fn pauli_probability_zero(&self, pauli: &Pauli, mask: usize, independent: bool) -> f64 {
if independent {
return 0.5;
}
let (sign_origin, sign_mask) = self.sign_coordinates(&pauli.z);
let negative = sign_origin ^ (pauli.phase & 2 != 0);
let expectation = if mask == 0 {
debug_assert_eq!(pauli.phase % 2, 0);
if sign_mask.is_power_of_two() {
if negative {
self.single_axis_expectation::<true>(sign_mask)
} else {
self.single_axis_expectation::<false>(sign_mask)
}
} else {
self.coefficients
.iter()
.enumerate()
.map(|(index, amplitude)| {
let norm = amplitude.norm_sqr();
if negative ^ ((index & sign_mask).count_ones() & 1 != 0) {
-norm
} else {
norm
}
})
.sum::<f64>()
}
} else {
debug_assert_eq!(
(mask & sign_mask).count_ones() & 1,
(pauli.phase % 2) as u32
);
if pauli.phase & 1 == 0 {
self.pauli_orbit_expectation::<false>(mask, sign_mask, negative)
} else {
self.pauli_orbit_expectation::<true>(mask, sign_mask, negative)
}
};
((1.0 + expectation) / 2.0).clamp(0.0, 1.0)
}
fn single_axis_expectation<const NEGATIVE: bool>(&self, pivot: usize) -> f64 {
let mut expectation = 0.0;
if pivot == 1 {
for pair in self.coefficients.chunks_exact(2) {
let zero = pair[0].norm_sqr();
let one = pair[1].norm_sqr();
expectation += if NEGATIVE { -zero } else { zero };
expectation += if NEGATIVE { one } else { -one };
}
return expectation;
}
for block in self.coefficients.chunks_exact(pivot * 2) {
let (zero, one) = block.split_at(pivot);
for amplitude in zero {
let norm = amplitude.norm_sqr();
expectation += if NEGATIVE { -norm } else { norm };
}
for amplitude in one {
let norm = amplitude.norm_sqr();
expectation += if NEGATIVE { norm } else { -norm };
}
}
expectation
}
fn pauli_orbit_expectation<const IMAGINARY: bool>(
&self,
mask: usize,
sign_mask: usize,
negative: bool,
) -> f64 {
let pivot = 1usize << (usize::BITS - 1 - mask.leading_zeros());
let mut expectation = 0.0;
for block in (0..self.coefficients.len()).step_by(pivot * 2) {
for offset in 0..pivot {
let index = block + offset;
let left = self.coefficients[index];
let right = self.coefficients[index ^ mask];
let value = if IMAGINARY {
right.im * left.re - right.re * left.im
} else {
right.re * left.re + right.im * left.im
};
expectation += if negative ^ ((index & sign_mask).count_ones() & 1 != 0) {
-2.0 * value
} else {
2.0 * value
};
}
}
expectation
}
pub fn measure(
&mut self,
q: usize,
basis: MeasurementBasis,
rng: &mut impl Rng,
) -> Result<bool, String> {
if q >= self.num_qubits() {
return Err(format!("qubit {q} outside near-Clifford state"));
}
if self.axes.is_empty() {
self.rebase_origin_into_frame();
let outcome = match basis {
MeasurementBasis::Z => Arc::make_mut(&mut self.frame).measure_z(q, rng).0,
MeasurementBasis::X => {
Arc::make_mut(&mut self.frame).h(q);
let bit = Arc::make_mut(&mut self.frame).measure_z(q, rng).0;
Arc::make_mut(&mut self.frame).h(q);
bit
}
MeasurementBasis::Y => {
Arc::make_mut(&mut self.frame).s_dag(q);
Arc::make_mut(&mut self.frame).h(q);
let bit = Arc::make_mut(&mut self.frame).measure_z(q, rng).0;
Arc::make_mut(&mut self.frame).h(q);
Arc::make_mut(&mut self.frame).s(q);
bit
}
};
return Ok(outcome != 0);
}
let pauli = self.single_qubit_pauli(q, basis)?;
self.measure_active_pauli(q, basis, &pauli, rng)
}
fn measure_clifford_forced(&mut self, q: usize, basis: MeasurementBasis, outcome: bool) {
debug_assert!(self.axes.is_empty());
self.rebase_origin_into_frame();
let frame = Arc::make_mut(&mut self.frame);
match basis {
MeasurementBasis::Z => {}
MeasurementBasis::X => frame.h(q),
MeasurementBasis::Y => {
frame.s_dag(q);
frame.h(q);
}
}
let (actual, _) = frame.measure_z_with_forced_random_outcome(q, u8::from(outcome));
match basis {
MeasurementBasis::Z => {}
MeasurementBasis::X => frame.h(q),
MeasurementBasis::Y => {
frame.h(q);
frame.s(q);
}
}
debug_assert_eq!(actual != 0, outcome);
}
fn measure_forced(
&mut self,
q: usize,
basis: MeasurementBasis,
outcome: bool,
) -> Result<(), String> {
if self.axes.is_empty() {
self.measure_clifford_forced(q, basis, outcome);
} else {
let pauli = self.single_qubit_pauli(q, basis)?;
let (mask, independent) = self.coordinate_mask(&pauli.x);
if independent {
self.absorb_independent_measurement(q, basis, outcome, &pauli)?;
} else {
let probability_zero = self.pauli_probability_zero(&pauli, mask, false);
self.project_active_measurement(q, basis, &pauli, mask, outcome, probability_zero)?;
}
self.retire_fixed_axes();
}
Ok(())
}
fn measure_active_pauli(
&mut self,
q: usize,
basis: MeasurementBasis,
pauli: &Pauli,
rng: &mut impl Rng,
) -> Result<bool, String> {
let (mask, independent) = self.coordinate_mask(&pauli.x);
let probability_zero = self.pauli_probability_zero(pauli, mask, independent);
if independent {
let outcome = rng.r#gen::<f64>() >= probability_zero;
self.absorb_independent_measurement(q, basis, outcome, pauli)?;
return Ok(outcome);
}
let mask = self.ensure_axis_with_coordinates(&pauli.x, mask, independent)?;
let outcome = rng.r#gen::<f64>() >= probability_zero;
self.project_active_measurement(q, basis, pauli, mask, outcome, probability_zero)?;
Ok(outcome)
}
fn canonicalize_active_axes(&mut self) -> Vec<usize> {
self.rebase_origin_into_frame();
if self.axes_are_canonical {
return self
.axes
.iter()
.map(|axis| {
axis.iter()
.position(|&bit| bit)
.expect("active axis is nonzero")
})
.collect();
}
let mut pivots = Vec::with_capacity(self.axes.len());
let frame = Arc::make_mut(&mut self.frame);
for axis_index in 0..self.axes.len() {
let pivot = (0..self.num_qubits)
.find(|&bit| self.axes[axis_index][bit] && !pivots.contains(&bit))
.expect("active axes remain independent");
let mut changed = false;
for (bit, &selected) in self.axes[axis_index].iter().enumerate() {
if bit != pivot && selected {
frame.right_cx(pivot, bit);
changed = true;
}
}
if !changed {
pivots.push(pivot);
continue;
}
let (processed, remaining) = self.axes.split_at_mut(axis_index + 1);
let axis = &mut processed[axis_index];
axis[pivot] = false;
for follower in remaining {
if follower[pivot] {
xor(follower, axis);
}
}
axis.fill(false);
axis[pivot] = true;
pivots.push(pivot);
}
self.axes_are_canonical = true;
pivots
}
fn project_active_measurement(
&mut self,
q: usize,
basis: MeasurementBasis,
pauli: &Pauli,
mask: usize,
outcome: bool,
probability_zero: f64,
) -> Result<(), String> {
let selected_probability = if outcome {
1.0 - probability_zero
} else {
probability_zero
};
let (sign_origin, sign_mask) = self.sign_coordinates(&pauli.z);
if selected_probability <= 1e-12
|| !selected_probability.is_finite()
|| (mask == 0 && sign_mask == 0)
{
self.collapse_pauli_measurement(pauli, mask, outcome, probability_zero)?;
if mask != 0 {
self.retire_nondiagonal_measurement(q, basis)?;
}
return Ok(());
}
let pivot_index = if mask == 0 {
sign_mask.trailing_zeros()
} else {
mask.trailing_zeros()
} as usize;
let pivot_z = (mask & sign_mask).count_ones() & 1 != 0;
let phase = (pauli.phase + 2 * u8::from(sign_origin) + 4 - u8::from(pivot_z)) % 4;
debug_assert_eq!(phase % 2, 0);
let fixed = outcome ^ (phase == 2);
let reduced =
self.project_reduced_coefficients(mask, sign_mask, pivot_index, pivot_z, fixed)?;
if mask == 0 {
self.retire_parity_basis(sign_mask, fixed);
} else {
let pivots = self.canonicalize_active_axes();
let pivot = pivots[pivot_index];
let frame = Arc::make_mut(&mut self.frame);
for (index, &bit) in pivots.iter().enumerate() {
if index != pivot_index && mask & (1 << index) != 0 {
frame.right_cx(pivot, bit);
}
}
for (index, &bit) in pivots.iter().enumerate() {
if index != pivot_index && sign_mask & (1 << index) != 0 {
frame.right_cz(pivot, bit);
}
}
if pivot_z {
frame.right_s(pivot);
}
frame.right_h(pivot);
self.axes.remove(pivot_index);
if fixed {
self.origin[pivot] ^= true;
}
}
self.coefficients = reduced;
if mask != 0 {
self.retire_fixed_axes();
}
Ok(())
}
fn project_reduced_coefficients(
&self,
mask: usize,
sign_mask: usize,
pivot_index: usize,
pivot_z: bool,
fixed: bool,
) -> Result<Vec<ComplexAmp>, String> {
let pivot_mask = 1usize << pivot_index;
let low_mask = pivot_mask - 1;
let other_signs = sign_mask & !pivot_mask;
let mut reduced = Vec::with_capacity(self.coefficients.len() / 2);
let mut norm_sqr = 0.0;
for index in 0..self.coefficients.len() / 2 {
let without_pivot = (index & low_mask) | ((index & !low_mask) << 1);
let amplitude = if mask == 0 {
let pivot_value = fixed ^ ((without_pivot & other_signs).count_ones() & 1 != 0);
let amplitude =
self.coefficients[without_pivot | (usize::from(pivot_value) << pivot_index)];
amplitude * 0.5 + amplitude * 0.5
} else {
let left = self.coefficients[without_pivot];
let right = self.coefficients[without_pivot ^ mask];
let sign = if fixed ^ ((without_pivot & other_signs).count_ones() & 1 != 0) {
-1.0
} else {
1.0
};
let right = if pivot_z {
ComplexAmp::new(right.im, -right.re)
} else {
right
};
(left + right * sign) * std::f64::consts::FRAC_1_SQRT_2
};
norm_sqr += amplitude.norm_sqr();
reduced.push(amplitude);
}
let norm = norm_sqr.sqrt();
if norm <= 1e-15 {
return Err("near-Clifford measurement selected zero-probability outcome".into());
}
for amplitude in &mut reduced {
*amplitude = *amplitude * (1.0 / norm);
}
Ok(reduced)
}
fn absorb_independent_measurement(
&mut self,
q: usize,
basis: MeasurementBasis,
outcome: bool,
measured_pauli: &Pauli,
) -> Result<(), String> {
let unchanged_frame = self.axes_are_canonical && !self.origin.contains(&true);
let pivots = self.canonicalize_active_axes();
let transformed;
let pauli = if unchanged_frame {
measured_pauli
} else {
transformed = self.single_qubit_pauli(q, basis)?;
&transformed
};
let dormant = (0..self.num_qubits)
.find(|&bit| pauli.x[bit] && !pivots.contains(&bit))
.expect("independent Pauli has a dormant X pivot");
let frame = Arc::make_mut(&mut self.frame);
for bit in 0..self.num_qubits {
if bit != dormant && pauli.x[bit] {
frame.right_cx(dormant, bit);
}
}
for &bit in &pivots {
if pauli.z[bit] {
frame.right_cz(dormant, bit);
}
}
for _ in 0..((pauli.phase + if outcome { 2 } else { 0 }) % 4) {
frame.right_s(dormant);
}
frame.right_h(dormant);
Ok(())
}
fn retire_nondiagonal_measurement(
&mut self,
q: usize,
basis: MeasurementBasis,
) -> Result<(), String> {
let pivots = self.canonicalize_active_axes();
let mut pauli = self.single_qubit_pauli(q, basis)?;
let pivot_index = pivots
.iter()
.position(|&bit| pauli.x[bit])
.expect("non-diagonal active Pauli has an X pivot");
let pivot = pivots[pivot_index];
let pivot_mask = 1usize << pivot_index;
for (index, &bit) in pivots.iter().enumerate() {
if bit == pivot || !pauli.x[bit] {
continue;
}
let other_mask = 1usize << index;
for coefficient in 0..self.coefficients.len() {
if coefficient & pivot_mask != 0 && coefficient & other_mask == 0 {
self.coefficients
.swap(coefficient, coefficient ^ other_mask);
}
}
Arc::make_mut(&mut self.frame).right_cx(pivot, bit);
pauli.x[bit] = false;
pauli.z[pivot] ^= pauli.z[bit];
}
for (index, &bit) in pivots.iter().enumerate() {
if bit == pivot || !pauli.z[bit] {
continue;
}
let other_mask = 1usize << index;
for coefficient in 0..self.coefficients.len() {
if coefficient & pivot_mask != 0 && coefficient & other_mask != 0 {
self.coefficients[coefficient] = self.coefficients[coefficient] * -1.0;
}
}
Arc::make_mut(&mut self.frame).right_cz(pivot, bit);
pauli.z[bit] = false;
}
if pauli.z[pivot] {
for coefficient in 0..self.coefficients.len() {
if coefficient & pivot_mask != 0 {
let old = self.coefficients[coefficient];
self.coefficients[coefficient] = ComplexAmp::new(old.im, -old.re);
}
}
Arc::make_mut(&mut self.frame).right_s(pivot);
}
let scale = std::f64::consts::FRAC_1_SQRT_2;
for coefficient in 0..self.coefficients.len() {
if coefficient & pivot_mask == 0 {
let partner = coefficient ^ pivot_mask;
let zero = self.coefficients[coefficient];
let one = self.coefficients[partner];
self.coefficients[coefficient] = (zero + one) * scale;
self.coefficients[partner] =
ComplexAmp::new(zero.re - one.re, zero.im - one.im) * scale;
}
}
Arc::make_mut(&mut self.frame).right_h(pivot);
self.retire_fixed_axes();
Ok(())
}
fn collapse_pauli_measurement(
&mut self,
pauli: &Pauli,
mask: usize,
outcome: bool,
probability_zero: f64,
) -> Result<(), String> {
let eigenvalue = if outcome { -1.0 } else { 1.0 };
let selected_probability = if outcome {
1.0 - probability_zero
} else {
probability_zero
};
let backup = if selected_probability <= 1e-12 || !selected_probability.is_finite() {
Some(self.coefficients.clone())
} else {
None
};
let (sign_origin, sign_mask) = self.sign_coordinates(&pauli.z);
let phase = i_pow(pauli.phase);
let image = |index: usize, amplitude: ComplexAmp| {
let sign = if sign_origin ^ ((index & sign_mask).count_ones() & 1 != 0) {
-1.0
} else {
1.0
};
phase * (amplitude * (sign * eigenvalue))
};
let mut norm_sqr = 0.0;
if mask == 0 {
for (index, coefficient) in self.coefficients.iter_mut().enumerate() {
let amplitude = *coefficient;
*coefficient = amplitude * 0.5 + image(index, amplitude) * 0.5;
norm_sqr += coefficient.norm_sqr();
}
} else {
let pivot = 1usize << (usize::BITS - 1 - mask.leading_zeros());
for block in (0..self.coefficients.len()).step_by(pivot * 2) {
for offset in 0..pivot {
let index = block + offset;
let partner = index ^ mask;
let left = self.coefficients[index];
let right = self.coefficients[partner];
self.coefficients[index] = left * 0.5 + image(partner, right) * 0.5;
self.coefficients[partner] = image(index, left) * 0.5 + right * 0.5;
norm_sqr += self.coefficients[index].norm_sqr();
norm_sqr += self.coefficients[partner].norm_sqr();
}
}
}
let norm = norm_sqr.sqrt();
if norm <= 1e-15 {
if let Some(backup) = backup {
self.coefficients = backup;
}
return Err("near-Clifford measurement selected zero-probability outcome".into());
}
for amplitude in &mut self.coefficients {
*amplitude = *amplitude * (1.0 / norm);
}
if mask == 0 && sign_mask != 0 {
debug_assert!(pauli.phase == 0 || pauli.phase == 2);
let fixed_parity = outcome ^ sign_origin ^ (pauli.phase == 2);
self.retire_fixed_parity(sign_mask, fixed_parity);
}
Ok(())
}
fn retire_parity_basis(&mut self, parity_mask: usize, fixed_parity: bool) {
let pivot = parity_mask.trailing_zeros() as usize;
let other_mask = parity_mask ^ (1 << pivot);
let pivot_axis = self.axes.remove(pivot);
if other_mask != 0 {
self.axes_are_canonical = false;
}
if fixed_parity {
xor(&mut self.origin, &pivot_axis);
}
for (index, axis) in self.axes.iter_mut().enumerate() {
let old_index = index + usize::from(index >= pivot);
if other_mask & (1 << old_index) != 0 {
xor(axis, &pivot_axis);
}
}
}
fn retire_fixed_parity(&mut self, parity_mask: usize, fixed_parity: bool) {
self.retire_parity_basis(parity_mask, fixed_parity);
let pivot = parity_mask.trailing_zeros() as usize;
let pivot_bit = 1 << pivot;
let other_mask = parity_mask ^ pivot_bit;
let low_mask = pivot_bit - 1;
self.coefficients = (0..self.coefficients.len() / 2)
.map(|index| {
let without_pivot = (index & low_mask) | ((index & !low_mask) << 1);
let pivot_value =
fixed_parity ^ ((without_pivot & other_mask).count_ones() & 1 != 0);
self.coefficients[without_pivot | (usize::from(pivot_value) << pivot)]
})
.collect();
}
fn rebase_origin_into_frame(&mut self) {
if !self.origin.contains(&true) {
return;
}
let frame = Arc::make_mut(&mut self.frame);
for (q, bit) in self.origin.iter_mut().enumerate() {
if *bit {
self.global_phase = self.global_phase * i_pow(frame.canonical_row(q).2);
frame.right_x(q);
*bit = false;
}
}
}
pub fn measure_reset(
&mut self,
q: usize,
basis: MeasurementBasis,
rng: &mut impl Rng,
) -> Result<bool, String> {
let outcome = self.measure(q, basis, rng)?;
if outcome {
let correction = match basis {
MeasurementBasis::Z => CliffordGate::X(q),
MeasurementBasis::X | MeasurementBasis::Y => CliffordGate::Z(q),
};
self.apply_clifford(correction)?;
}
self.retire_fixed_axes();
Ok(outcome)
}
pub fn reset(
&mut self,
q: usize,
basis: MeasurementBasis,
rng: &mut impl Rng,
) -> Result<(), String> {
self.measure_reset(q, basis, rng).map(|_| ())
}
pub fn retire_fixed_axes(&mut self) -> usize {
let mut retired = 0;
let mut axis_index = 0;
let mut witness = self
.coefficients
.iter()
.position(|coefficient| coefficient.norm_sqr() >= 1e-24);
while axis_index < self.axes.len() {
if let Some(witness) = witness
&& self.coefficients[witness ^ (1 << axis_index)].norm_sqr() >= 1e-24
{
axis_index += 1;
continue;
}
let mut half_norm = [0.0, 0.0];
for (index, coefficient) in self.coefficients.iter().enumerate() {
half_norm[(index >> axis_index) & 1] += coefficient.norm_sqr();
if half_norm[0] >= 1e-24 && half_norm[1] >= 1e-24 {
break;
}
}
let fixed = if half_norm[0] < 1e-24 && half_norm[1] > 1e-24 {
Some(1)
} else if half_norm[1] < 1e-24 && half_norm[0] > 1e-24 {
Some(0)
} else {
None
};
if let Some(fixed) = fixed {
let axis = self.axes.remove(axis_index);
if fixed == 1 {
xor(&mut self.origin, &axis);
}
let low_mask = (1 << axis_index) - 1;
let reduced_len = self.coefficients.len() / 2;
let reduced = (0..reduced_len)
.map(|index| {
let old_index =
(index & low_mask) | (fixed << axis_index) | ((index & !low_mask) << 1);
self.coefficients[old_index]
})
.collect();
self.coefficients = reduced;
retired += 1;
witness = self
.coefficients
.iter()
.position(|coefficient| coefficient.norm_sqr() >= 1e-24);
} else {
axis_index += 1;
}
}
retired
}
fn single_qubit_pauli(&self, q: usize, basis: MeasurementBasis) -> Result<Pauli, String> {
let n = self.num_qubits();
if q >= n {
return Err(format!("qubit {q} outside near-Clifford state"));
}
let has_x = matches!(basis, MeasurementBasis::X | MeasurementBasis::Y);
let has_z = matches!(basis, MeasurementBasis::Y | MeasurementBasis::Z);
let mut virtual_x = vec![false; n];
let mut virtual_z = vec![false; n];
for i in 0..n {
let (x, z, _) = self.frame.canonical_row(n + i);
virtual_x[i] = (has_x && z[q]) ^ (has_z && x[q]);
let (x, z, _) = self.frame.canonical_row(i);
virtual_z[i] = (has_x && z[q]) ^ (has_z && x[q]);
}
let product_phase = self.reconstruct_physical_phase(&virtual_x, &virtual_z);
#[cfg(debug_assertions)]
{
let product = self.reconstruct_physical_pauli(&virtual_x, &virtual_z);
assert_eq!(product.phase, product_phase);
assert!(
product
.x
.iter()
.enumerate()
.all(|(i, &bit)| bit == (has_x && i == q))
);
assert!(
product
.z
.iter()
.enumerate()
.all(|(i, &bit)| bit == (has_z && i == q))
);
}
let desired_phase = u8::from(has_x && has_z);
Ok(Pauli {
x: virtual_x,
z: virtual_z,
phase: (desired_phase + 4 - product_phase) % 4,
})
}
fn ensure_axis(&mut self, x: &[bool]) -> Result<usize, String> {
let (mask, independent) = self.coordinate_mask(x);
self.ensure_axis_with_coordinates(x, mask, independent)
}
fn ensure_axis_with_coordinates(
&mut self,
x: &[bool],
mask: usize,
independent: bool,
) -> Result<usize, String> {
if !independent {
return Ok(mask);
}
let rank = self.axes.len();
let expanded_len = self
.coefficients
.len()
.checked_mul(2)
.ok_or_else(|| "near-Clifford active-state size overflow".to_string())?;
if rank >= self.max_active_qubits
|| rank >= usize::BITS as usize - 1
|| expanded_len > isize::MAX as usize / size_of::<ComplexAmp>()
{
return Err(format!(
"near-Clifford active-state limit exceeded at rank {}",
rank + 1
));
}
if self.axes_are_canonical {
self.axes_are_canonical = x.iter().filter(|&&bit| bit).take(2).count() == 1;
}
self.axes.push(x.to_vec());
self.coefficients
.resize(expanded_len, ComplexAmp::default());
Ok(expanded_len / 2)
}
fn sign_coordinates(&self, z: &[bool]) -> (bool, usize) {
let mask = self
.axes
.iter()
.enumerate()
.fold(0, |mask, (i, axis)| mask | ((dot(z, axis) as usize) << i));
(dot(z, &self.origin), mask)
}
fn coordinate_mask(&self, x: &[bool]) -> (usize, bool) {
if x.len() <= 64 {
let pack = |bits: &[bool]| {
bits.iter()
.enumerate()
.fold(0u64, |word, (i, &b)| word | ((b as u64) << i))
};
let mut rows = [0u64; 64];
let mut masks = [0usize; 64];
for (index, axis) in self.axes.iter().enumerate() {
let mut row = pack(axis);
let mut mask = 1usize << index;
while row != 0 {
let pivot = row.trailing_zeros() as usize;
if rows[pivot] != 0 {
row ^= rows[pivot];
mask ^= masks[pivot];
} else {
rows[pivot] = row;
masks[pivot] = mask;
break;
}
}
}
let mut row = pack(x);
let mut mask = 0usize;
while row != 0 {
let pivot = row.trailing_zeros() as usize;
if rows[pivot] == 0 {
return (0, true);
}
row ^= rows[pivot];
mask ^= masks[pivot];
}
return (mask, false);
}
let n = x.len();
let mut pivots: Vec<Option<(Vec<bool>, usize)>> = vec![None; n];
for (index, axis) in self.axes.iter().enumerate() {
let mut row = axis.clone();
let mut mask = 1 << index;
while let Some(pivot) = row.iter().position(|&value| value) {
if let Some((basis_row, basis_mask)) = &pivots[pivot] {
xor(&mut row, basis_row);
mask ^= basis_mask;
} else {
pivots[pivot] = Some((row, mask));
break;
}
}
}
let mut row = x.to_vec();
let mut mask = 0;
while let Some(pivot) = row.iter().position(|&value| value) {
if let Some((basis_row, basis_mask)) = &pivots[pivot] {
xor(&mut row, basis_row);
mask ^= basis_mask;
} else {
return (0, true);
}
}
(mask, false)
}
fn physical_pauli(&self, physical_x: &[bool], physical_z: &[bool]) -> Result<Pauli, String> {
let n = self.num_qubits();
let mut virtual_x = vec![false; n];
let mut virtual_z = vec![false; n];
for i in 0..n {
let (x, z, _) = self.frame.canonical_row(n + i);
virtual_x[i] = dot(physical_x, z) ^ dot(physical_z, x);
let (x, z, _) = self.frame.canonical_row(i);
virtual_z[i] = dot(physical_x, z) ^ dot(physical_z, x);
}
let product = self.reconstruct_physical_pauli(&virtual_x, &virtual_z);
if product.x != physical_x || product.z != physical_z {
return Err("Clifford frame failed to reconstruct physical Pauli".into());
}
let desired_phase = (physical_x
.iter()
.zip(physical_z)
.filter(|(x, z)| **x && **z)
.count()
% 4) as u8;
let phase = (desired_phase + 4 - product.phase) % 4;
Ok(Pauli {
x: virtual_x,
z: virtual_z,
phase,
})
}
fn reconstruct_physical_phase(&self, virtual_x: &[bool], virtual_z: &[bool]) -> u8 {
let n = self.num_qubits();
let mut left_z = vec![false; n];
let mut phase = 0u32;
for (i, &selected) in virtual_x.iter().chain(virtual_z).enumerate() {
if selected {
let (x, z, row_phase) = self.frame.canonical_row(i);
phase += u32::from(row_phase);
for ((left_z, &right_x), &right_z) in left_z.iter_mut().zip(x).zip(z) {
phase = phase.wrapping_add(
u32::from(right_x & right_z) + 2 * u32::from(*left_z & right_x),
);
*left_z ^= right_z;
}
phase &= 3;
}
}
phase as u8
}
fn reconstruct_physical_pauli(&self, virtual_x: &[bool], virtual_z: &[bool]) -> Pauli {
let n = self.num_qubits();
let mut product = Pauli::identity(n);
for (i, &selected) in virtual_x.iter().enumerate() {
if selected {
product.multiply_tableau_row(&self.frame, i);
}
}
for (i, &selected) in virtual_z.iter().enumerate() {
if selected {
product.multiply_tableau_row(&self.frame, n + i);
}
}
product
}
}
#[derive(Clone)]
struct Pauli {
x: Vec<bool>,
z: Vec<bool>,
phase: u8,
}
impl Pauli {
fn identity(n: usize) -> Self {
Self {
x: vec![false; n],
z: vec![false; n],
phase: 0,
}
}
#[cfg(test)]
fn from_snapshot_row(snapshot: &CanonicalTableauSnapshot, row: usize) -> Self {
let y_count = snapshot.x[row]
.iter()
.zip(&snapshot.z[row])
.filter(|(x, z)| **x && **z)
.count();
Self {
x: snapshot.x[row].clone(),
z: snapshot.z[row].clone(),
phase: (snapshot.phase[row] + (y_count % 4) as u8) % 4,
}
}
fn multiply_tableau_row(&mut self, frame: &StabilizerState, row: usize) {
let (x, z, phase) = frame.canonical_row(row);
let mut exponent = u32::from(self.phase) + u32::from(phase);
for (((left_x, left_z), &right_x), &right_z) in
self.x.iter_mut().zip(&mut self.z).zip(x).zip(z)
{
exponent = exponent
.wrapping_add(u32::from(right_x & right_z) + 2 * u32::from(*left_z & right_x));
*left_x ^= right_x;
*left_z ^= right_z;
}
self.phase = (exponent & 3) as u8;
}
}
fn dot(a: &[bool], b: &[bool]) -> bool {
a.iter().zip(b).filter(|(x, y)| **x && **y).count() & 1 == 1
}
fn xor(a: &mut [bool], b: &[bool]) {
for (left, right) in a.iter_mut().zip(b) {
*left ^= *right;
}
}
fn i_pow(exponent: u8) -> ComplexAmp {
match exponent % 4 {
0 => ComplexAmp::new(1.0, 0.0),
1 => ComplexAmp::new(0.0, 1.0),
2 => ComplexAmp::new(-1.0, 0.0),
_ => ComplexAmp::new(0.0, -1.0),
}
}
#[derive(Clone, Debug)]
pub struct NearCliffordExecutor {
instructions: Vec<StimInstr>,
num_qubits: usize,
measurement_count: usize,
max_active_qubits: usize,
prefix_len: usize,
terminal_plan: Option<TerminalPlan>,
}
#[derive(Clone, Debug)]
struct TerminalMeasurement {
q: usize,
basis: MeasurementBasis,
inverted: bool,
record_index: usize,
}
#[derive(Clone, Debug)]
enum TerminalOutput {
Detector(Vec<usize>),
Observable(u32, Vec<usize>),
}
#[derive(Clone, Debug, Default)]
struct TerminalPlan {
measurements: Vec<TerminalMeasurement>,
outputs: Vec<TerminalOutput>,
schedule: OnceLock<Vec<usize>>,
}
impl TerminalPlan {
const MAX_ACTIONS: usize = 65_536;
fn from_instructions(instructions: &[StimInstr]) -> Option<Self> {
let mut plan = Self::default();
let mut budget = Self::MAX_ACTIONS;
plan.append(instructions, &mut budget)?;
(!plan.measurements.is_empty()).then_some(plan)
}
fn append(&mut self, instructions: &[StimInstr], budget: &mut usize) -> Option<()> {
for instruction in instructions {
*budget = (*budget).checked_sub(1)?;
match instruction {
StimInstr::Repeat { count, body } => {
if *count > Self::MAX_ACTIONS as u64 {
return None;
}
for _ in 0..*count {
*budget = (*budget).checked_sub(1)?;
self.append(body, budget)?;
}
}
StimInstr::Op {
name,
args,
targets,
..
} => match name.as_str() {
"M" | "MZ" | "MX" | "MY" => {
let basis = match name.as_str() {
"MX" => MeasurementBasis::X,
"MY" => MeasurementBasis::Y,
_ => MeasurementBasis::Z,
};
for target in targets {
self.measurements.push(TerminalMeasurement {
q: target.qubit_index()? as usize,
basis,
inverted: matches!(target, StimTarget::QubitInv(_)),
record_index: self.measurements.len(),
});
}
}
"DETECTOR" | "OBSERVABLE_INCLUDE" => {
let available = self.measurements.len();
let mut positions = Vec::with_capacity(targets.len());
for target in targets {
let StimTarget::Rec(offset) = target else {
return None;
};
let distance = usize::try_from(offset.unsigned_abs()).ok()?;
if *offset >= 0 || distance == 0 || distance > available {
return None;
}
positions.push(available - distance);
}
if name == "DETECTOR" {
self.outputs.push(TerminalOutput::Detector(positions));
} else {
self.outputs
.push(TerminalOutput::Observable(args[0] as u32, positions));
}
}
"TICK" | "QUBIT_COORDS" | "SHIFT_COORDS" => {}
_ => return None,
},
}
if self.measurements.len() + self.outputs.len() > Self::MAX_ACTIONS {
return None;
}
}
Some(())
}
fn add_outputs(&self, shot: &mut NearCliffordShot) {
for output in &self.outputs {
let (positions, observable) = match output {
TerminalOutput::Detector(positions) => (positions, None),
TerminalOutput::Observable(index, positions) => (positions, Some(*index)),
};
let parity = positions.iter().fold(false, |parity, &position| {
parity ^ shot.measurements[position]
});
if let Some(index) = observable {
shot.observables.push((index, parity));
} else {
shot.detectors.push(parity);
}
}
}
fn ordered_measurements(&self, prepared: &ActiveState) -> Vec<TerminalMeasurement> {
let order = self.schedule.get_or_init(|| self.plan_order(prepared));
order
.iter()
.map(|&index| self.measurements[index].clone())
.collect()
}
fn plan_order(&self, prepared: &ActiveState) -> Vec<usize> {
let identity = || (0..self.measurements.len()).collect::<Vec<_>>();
if self.measurements.len() > 64 {
return identity();
}
let mut seen = vec![None; prepared.num_qubits];
let mut first_repeat = None;
for (index, measurement) in self.measurements.iter().enumerate() {
if let Some(basis) = seen[measurement.q] {
if basis != measurement.basis {
return identity();
}
first_repeat.get_or_insert(index);
} else {
if first_repeat.is_some() {
return identity();
}
seen[measurement.q] = Some(measurement.basis);
}
}
let first_pass_len = first_repeat.unwrap_or(self.measurements.len());
let mut state = prepared.clone();
let mut remaining = (0..first_pass_len).collect::<Vec<_>>();
let mut order = Vec::with_capacity(self.measurements.len());
while !remaining.is_empty() {
let next = remaining
.iter()
.position(|&index| {
let measurement = &self.measurements[index];
let Ok(pauli) = state.single_qubit_pauli(measurement.q, measurement.basis)
else {
return false;
};
let (mask, independent) = state.coordinate_mask(&pauli.x);
!independent && (mask != 0 || state.sign_coordinates(&pauli.z).1 != 0)
})
.unwrap_or(0);
let index = remaining.remove(next);
let measurement = &self.measurements[index];
let Ok((probability_zero, _)) =
state.measurement_probabilities(measurement.q, measurement.basis)
else {
return identity();
};
if state
.measure_forced(measurement.q, measurement.basis, probability_zero < 0.5)
.is_err()
{
return identity();
}
order.push(index);
}
order.extend(first_pass_len..self.measurements.len());
order
}
fn restore_record_order(&self, shot: &mut NearCliffordShot, ordered: &[TerminalMeasurement]) {
let mut original = vec![false; ordered.len()];
for (bit, measurement) in shot.measurements.iter().zip(ordered) {
original[measurement.record_index] = *bit;
}
shot.measurements = original;
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct NearCliffordShot {
pub measurements: Vec<bool>,
pub detectors: Vec<bool>,
pub observables: Vec<(u32, bool)>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct NearCliffordMeasurementBatch {
pub shots: usize,
pub measurements_per_shot: usize,
pub measurements: Vec<u8>,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct NearCliffordPostselectedCounts {
pub attempted: usize,
pub accepted: usize,
pub logical_errors: usize,
}
fn rotation_coefficients(half_turns: f64) -> (f64, f64) {
let angle = half_turns % 4.0;
match angle {
0.0 => (1.0, 0.0),
1.0 | -3.0 => (0.0, 1.0),
-1.0 | 3.0 => (0.0, -1.0),
2.0 | -2.0 => (-1.0, 0.0),
_ => {
let radians = angle * (std::f64::consts::PI / 2.0);
(radians.cos(), radians.sin())
}
}
}
fn rotation_clifford_quarters(half_turns: f64) -> Option<u8> {
let quarters = (half_turns % 4.0) * 2.0;
(quarters.fract() == 0.0).then(|| quarters.rem_euclid(8.0) as u8)
}
fn quarter_rotation_gates(q: usize, basis: MeasurementBasis) -> [Option<CliffordGate>; 3] {
use CliffordGate::{H, S, Z};
match basis {
MeasurementBasis::X => [Some(H(q)), Some(S(q)), Some(H(q))],
MeasurementBasis::Y => [Some(Z(q)), Some(H(q)), None],
MeasurementBasis::Z => [Some(S(q)), None, None],
}
}
const MAX_NEAR_CLIFFORD_QUBITS: usize = 4096;
impl NearCliffordExecutor {
pub fn compile(instructions: Vec<StimInstr>) -> Result<Self, String> {
Self::compile_with_limit(instructions, 16)
}
pub fn compile_text(text: &str) -> Result<Self, String> {
Self::compile(crate::parser::parse_lines(text)?)
}
pub fn compile_with_limit(
instructions: Vec<StimInstr>,
max_active_qubits: usize,
) -> Result<Self, String> {
let mut max_qubit = None;
let mut records = 0;
validate_near_block(&instructions, &mut max_qubit, &mut records)?;
let measurement_count = usize::try_from(records)
.map_err(|_| "near-Clifford measurement count exceeds platform capacity")?;
let num_qubits = max_qubit
.map(|q| {
usize::try_from(q)
.ok()
.and_then(|q| q.checked_add(1))
.ok_or_else(|| {
"near-Clifford qubit index exceeds platform capacity".to_string()
})
})
.transpose()?
.unwrap_or(0);
if num_qubits > MAX_NEAR_CLIFFORD_QUBITS {
return Err(format!(
"near-Clifford circuit exceeds {MAX_NEAR_CLIFFORD_QUBITS} physical qubits"
));
}
let prefix_len = instructions
.iter()
.take_while(|instruction| is_deterministic_near_instruction(instruction))
.count();
let terminal_plan = TerminalPlan::from_instructions(&instructions[prefix_len..]);
Ok(Self {
instructions,
num_qubits,
measurement_count,
max_active_qubits,
prefix_len,
terminal_plan,
})
}
pub fn run(&self, rng: &mut impl Rng) -> Result<NearCliffordShot, String> {
self.run_with_sweep(&[], rng)
}
pub fn run_with_sweep(
&self,
sweep_bits: &[bool],
rng: &mut impl Rng,
) -> Result<NearCliffordShot, String> {
let mut state = ActiveState::new(self.num_qubits, self.max_active_qubits);
if let Some(plan) = &self.terminal_plan {
run_near_block(
&self.instructions[..self.prefix_len],
&mut state,
&mut Vec::new(),
&mut Vec::new(),
&mut Vec::new(),
sweep_bits,
rng,
)?;
let ordered = plan.ordered_measurements(&state);
let mut shot = NearCliffordShot {
measurements: Vec::with_capacity(ordered.len()),
detectors: Vec::new(),
observables: Vec::new(),
};
for target in &ordered {
let bit = state.measure(target.q, target.basis, rng)?;
state.retire_fixed_axes();
shot.measurements.push(bit ^ target.inverted);
}
plan.restore_record_order(&mut shot, &ordered);
plan.add_outputs(&mut shot);
return Ok(shot);
}
let mut measurements = Vec::new();
let mut detectors = Vec::new();
let mut observables = Vec::new();
run_near_block(
&self.instructions,
&mut state,
&mut measurements,
&mut detectors,
&mut observables,
sweep_bits,
rng,
)?;
Ok(NearCliffordShot {
measurements,
detectors,
observables,
})
}
pub fn sample(
&self,
shots: usize,
rng: &mut impl Rng,
) -> Result<Vec<NearCliffordShot>, String> {
self.sample_with_sweep(shots, &[], rng)
}
pub fn sample_with_sweep(
&self,
shots: usize,
sweep_bits: &[bool],
rng: &mut impl Rng,
) -> Result<Vec<NearCliffordShot>, String> {
if shots <= 1 {
return (0..shots)
.map(|_| self.run_with_sweep(sweep_bits, rng))
.collect();
}
let prefix_len = self.prefix_len;
if prefix_len == 0 && self.terminal_plan.is_none() {
return (0..shots)
.map(|_| self.run_with_sweep(sweep_bits, rng))
.collect();
}
self.prepare_sampler()?
.sample_with_sweep(shots, sweep_bits, rng)
}
pub fn prepare_sampler(&self) -> Result<NearCliffordSampler<'_>, String> {
let mut prepared = ActiveState::new(self.num_qubits, self.max_active_qubits);
let mut unused_rng = StdRng::seed_from_u64(0);
run_near_block(
&self.instructions[..self.prefix_len],
&mut prepared,
&mut Vec::new(),
&mut Vec::new(),
&mut Vec::new(),
&[],
&mut unused_rng,
)?;
let terminal = self.terminal_plan.as_ref().map(|plan| {
let ordered = plan.ordered_measurements(&prepared);
let max_cached_nodes = terminal_cache_node_limit(prepared.num_qubits, ordered.len());
PreparedTerminalSampler {
cached: CachedTerminalSampler::new(prepared.clone(), &ordered, max_cached_nodes),
record_order_swaps: record_order_swaps(&ordered),
ordered,
}
});
Ok(NearCliffordSampler {
executor: self,
prepared,
terminal,
})
}
}
pub struct NearCliffordSampler<'a> {
executor: &'a NearCliffordExecutor,
prepared: ActiveState,
terminal: Option<PreparedTerminalSampler>,
}
struct PreparedTerminalSampler {
ordered: Vec<TerminalMeasurement>,
cached: CachedTerminalSampler,
record_order_swaps: Vec<(usize, usize)>,
}
fn record_order_swaps(ordered: &[TerminalMeasurement]) -> Vec<(usize, usize)> {
let mut destinations = ordered
.iter()
.map(|measurement| measurement.record_index)
.collect::<Vec<_>>();
let mut swaps = Vec::new();
for index in 0..destinations.len() {
while destinations[index] != index {
let target = destinations[index];
destinations.swap(index, target);
swaps.push((index, target));
}
}
swaps
}
impl NearCliffordSampler<'_> {
pub fn sample(
&mut self,
shots: usize,
rng: &mut impl Rng,
) -> Result<Vec<NearCliffordShot>, String> {
self.sample_with_sweep(shots, &[], rng)
}
pub fn sample_with_sweep(
&mut self,
shots: usize,
sweep_bits: &[bool],
rng: &mut impl Rng,
) -> Result<Vec<NearCliffordShot>, String> {
if let Some(terminal) = &mut self.terminal {
let mut results = terminal.cached.sample(&terminal.ordered, shots, rng)?;
let plan = self.executor.terminal_plan.as_ref().unwrap();
for result in &mut results {
for &(left, right) in &terminal.record_order_swaps {
result.measurements.swap(left, right);
}
plan.add_outputs(result);
}
return Ok(results);
}
(0..shots)
.map(|_| self.run_unplanned_shot_with_sweep(sweep_bits, rng))
.collect()
}
fn run_unplanned_shot_with_sweep(
&self,
sweep_bits: &[bool],
rng: &mut impl Rng,
) -> Result<NearCliffordShot, String> {
let mut state = self.prepared.clone();
let mut measurements = Vec::new();
let mut detectors = Vec::new();
let mut observables = Vec::new();
run_near_block(
&self.executor.instructions[self.executor.prefix_len..],
&mut state,
&mut measurements,
&mut detectors,
&mut observables,
sweep_bits,
rng,
)?;
Ok(NearCliffordShot {
measurements,
detectors,
observables,
})
}
pub fn sample_measurements_u8(
&mut self,
shots: usize,
rng: &mut impl Rng,
) -> Result<NearCliffordMeasurementBatch, String> {
self.sample_measurements_u8_with_sweep(shots, &[], rng)
}
pub fn sample_measurements_u8_with_sweep(
&mut self,
shots: usize,
sweep_bits: &[bool],
rng: &mut impl Rng,
) -> Result<NearCliffordMeasurementBatch, String> {
let width = self.executor.measurement_count;
let capacity = shots
.checked_mul(width)
.ok_or("near-Clifford measurement batch size overflow")?;
let measurements = if let Some(terminal) = &mut self.terminal {
debug_assert_eq!(terminal.ordered.len(), width);
let in_record_order = terminal.record_order_swaps.is_empty();
let ordered = &terminal.ordered;
let cached = &mut terminal.cached;
let measurements = cached.sample_flat(ordered, in_record_order, shots, rng)?;
if measurements.len() != capacity {
return Err("near-Clifford terminal measurement count changed".into());
}
measurements
} else {
let mut measurements = Vec::with_capacity(capacity);
for _ in 0..shots {
let shot = self.run_unplanned_shot_with_sweep(sweep_bits, rng)?;
if shot.measurements.len() != width {
return Err("near-Clifford measurement count changed between shots".into());
}
measurements.extend(shot.measurements.into_iter().map(u8::from));
}
measurements
};
Ok(NearCliffordMeasurementBatch {
shots,
measurements_per_shot: width,
measurements,
})
}
}
struct TerminalMeasurementNode {
state: ActiveState,
measurement: Option<PreparedTerminalMeasurement>,
symbolic_suffix: Option<Option<CliffordSuffixPlan>>,
children: [Option<Box<TerminalMeasurementNode>>; 2],
}
struct CachedTerminalSampler {
root: TerminalMeasurementNode,
cached_nodes: usize,
max_cached_nodes: usize,
cached_depth: usize,
reserved_cache_bytes: usize,
}
impl CachedTerminalSampler {
fn new(
prepared: ActiveState,
targets: &[TerminalMeasurement],
max_cached_nodes: usize,
) -> Self {
debug_assert!(max_cached_nodes > 0);
let reserved_cache_bytes = terminal_cache_state_bytes(&prepared, targets.len());
Self {
root: TerminalMeasurementNode::new(prepared),
cached_nodes: 1,
max_cached_nodes,
cached_depth: targets.len().min(16),
reserved_cache_bytes,
}
}
}
struct SymbolicStabilizerState<M: SymbolicMask> {
frame: StabilizerState,
signs: Vec<M>,
random_count: usize,
words: usize,
}
struct SymbolicMeasurement<M: SymbolicMask> {
mask: M,
constant: bool,
}
impl<M: SymbolicMask> SymbolicStabilizerState<M> {
fn new(frame: StabilizerState, words: usize) -> Self {
Self {
signs: vec![M::zero(words); frame.num_qubits() * 2],
frame,
random_count: 0,
words,
}
}
fn h(&mut self, q: usize) {
self.frame.h(q);
}
fn s(&mut self, q: usize) {
self.frame.s(q);
}
fn s_dag(&mut self, q: usize) {
self.frame.s_dag(q);
}
fn measure_z(&mut self, q: usize) -> Option<SymbolicMeasurement<M>> {
let (mask, constant, _) = self.frame.measure_z_symbolic(
&mut self.signs,
&mut self.random_count,
self.words,
q,
)?;
Some(SymbolicMeasurement { mask, constant })
}
}
struct CliffordSuffixPlanImpl<M: SymbolicMask> {
steps: Vec<SymbolicMeasurement<M>>,
random_count: usize,
words: usize,
}
enum CliffordSuffixPlan {
Compact(CliffordSuffixPlanImpl<u64>),
DoubleWord(CliffordSuffixPlanImpl<u128>),
Wide(CliffordSuffixPlanImpl<Vec<u64>>),
}
impl<M: SymbolicMask> CliffordSuffixPlanImpl<M> {
fn from_state(state: &ActiveState, targets: &[TerminalMeasurement]) -> Option<Self> {
let mut frame = (*state.frame).clone();
for (q, &bit) in state.origin.iter().enumerate() {
if bit {
let (x_row, z_row, _) = state.frame.canonical_row(q);
for (physical_q, (&x, &z)) in x_row.iter().zip(z_row).enumerate() {
match (x, z) {
(true, true) => frame.y_gate(physical_q),
(true, false) => frame.x_gate(physical_q),
(false, true) => frame.z_gate(physical_q),
(false, false) => {}
}
}
}
}
let words = targets.len().div_ceil(64);
let mut symbolic = SymbolicStabilizerState::<M>::new(frame, words);
let mut steps = Vec::with_capacity(targets.len());
for target in targets {
match target.basis {
MeasurementBasis::Z => {}
MeasurementBasis::X => symbolic.h(target.q),
MeasurementBasis::Y => {
symbolic.s_dag(target.q);
symbolic.h(target.q);
}
}
steps.push(symbolic.measure_z(target.q)?);
match target.basis {
MeasurementBasis::Z => {}
MeasurementBasis::X => symbolic.h(target.q),
MeasurementBasis::Y => {
symbolic.h(target.q);
symbolic.s(target.q);
}
}
}
Some(Self {
steps,
random_count: symbolic.random_count,
words,
})
}
#[inline(always)]
fn sample(
&self,
targets: &[TerminalMeasurement],
mut push: impl FnMut(bool),
rng: &mut impl Rng,
) {
let mut random_bits = M::zero(self.words);
for index in 0..self.random_count {
if rng.r#gen::<bool>() {
random_bits.set_bit(index);
}
}
for (step, target) in self.steps.iter().zip(targets) {
let outcome = step.constant ^ step.mask.parity_with(&random_bits);
push(outcome ^ target.inverted);
}
}
}
impl CliffordSuffixPlan {
fn from_state(state: &ActiveState, targets: &[TerminalMeasurement]) -> Option<Self> {
CliffordSuffixPlanImpl::<u64>::from_state(state, targets)
.map(Self::Compact)
.or_else(|| {
CliffordSuffixPlanImpl::<u128>::from_state(state, targets).map(Self::DoubleWord)
})
.or_else(|| {
CliffordSuffixPlanImpl::<Vec<u64>>::from_state(state, targets).map(Self::Wide)
})
}
#[cfg(test)]
fn random_count(&self) -> usize {
match self {
Self::Compact(plan) => plan.random_count,
Self::DoubleWord(plan) => plan.random_count,
Self::Wide(plan) => plan.random_count,
}
}
fn sample(&self, targets: &[TerminalMeasurement], push: impl FnMut(bool), rng: &mut impl Rng) {
match self {
Self::Compact(plan) => plan.sample(targets, push, rng),
Self::DoubleWord(plan) => plan.sample(targets, push, rng),
Self::Wide(plan) => plan.sample(targets, push, rng),
}
}
}
enum PreparedTerminalMeasurement {
Active {
probability_zero: f64,
pauli: Pauli,
mask: usize,
independent: bool,
},
Clifford {
probability_zero: f64,
},
}
impl TerminalMeasurementNode {
fn new(state: ActiveState) -> Self {
Self {
state,
measurement: None,
symbolic_suffix: None,
children: [None, None],
}
}
}
const MAX_CACHED_COEFFICIENTS: usize = 2048;
const MAX_CACHE_BYTES: usize = 64 * 1024 * 1024;
fn terminal_cache_node_bytes(
num_qubits: usize,
target_count: usize,
coefficient_capacity: usize,
) -> usize {
let wide_words = target_count.div_ceil(64);
let symbolic_step_bytes = std::mem::size_of::<SymbolicMeasurement<Vec<u64>>>()
.saturating_add(wide_words.saturating_mul(std::mem::size_of::<u64>()));
num_qubits
.saturating_mul(num_qubits)
.saturating_mul(4)
.saturating_add(num_qubits.saturating_mul(256))
.saturating_add(coefficient_capacity.saturating_mul(std::mem::size_of::<ComplexAmp>()))
.saturating_add(target_count.saturating_mul(symbolic_step_bytes))
.saturating_add(std::mem::size_of::<TerminalMeasurementNode>())
}
fn terminal_cache_node_limit(num_qubits: usize, target_count: usize) -> usize {
(MAX_CACHE_BYTES / terminal_cache_node_bytes(num_qubits, target_count, MAX_CACHED_COEFFICIENTS))
.clamp(1, 1024)
}
fn terminal_cache_state_bytes(state: &ActiveState, target_count: usize) -> usize {
let axes_bytes = state.axes.iter().fold(
state
.axes
.capacity()
.saturating_mul(std::mem::size_of::<Vec<bool>>()),
|sum, axis| sum.saturating_add(axis.capacity()),
);
terminal_cache_node_bytes(
state.num_qubits,
target_count,
state.coefficients.capacity(),
)
.saturating_add(axes_bytes)
.saturating_add(state.origin.capacity())
}
impl CachedTerminalSampler {
fn sample(
&mut self,
targets: &[TerminalMeasurement],
shots: usize,
rng: &mut impl Rng,
) -> Result<Vec<NearCliffordShot>, String> {
let mut results = Vec::with_capacity(shots);
for _ in 0..shots {
let mut measurements = Vec::with_capacity(targets.len());
self.sample_one(targets, |bit| measurements.push(bit), rng)?;
results.push(NearCliffordShot {
measurements,
detectors: Vec::new(),
observables: Vec::new(),
});
}
Ok(results)
}
fn sample_flat(
&mut self,
targets: &[TerminalMeasurement],
in_record_order: bool,
shots: usize,
rng: &mut impl Rng,
) -> Result<Vec<u8>, String> {
let capacity = shots
.checked_mul(targets.len())
.ok_or("near-Clifford measurement batch size overflow")?;
if in_record_order {
let mut measurements = Vec::with_capacity(capacity);
for _ in 0..shots {
self.sample_one(targets, |bit| measurements.push(u8::from(bit)), rng)?;
}
return Ok(measurements);
}
let mut measurements = vec![0u8; capacity];
for shot in 0..shots {
let row_start = shot * targets.len();
let mut target_index = 0;
let mut write_bit = |bit| {
let record_index = targets[target_index].record_index;
measurements[row_start + record_index] = u8::from(bit);
target_index += 1;
};
self.sample_one(targets, &mut write_bit, rng)?;
if target_index != targets.len() {
return Err("near-Clifford terminal measurement count changed".into());
}
}
Ok(measurements)
}
#[inline(always)]
fn sample_one(
&mut self,
targets: &[TerminalMeasurement],
mut push: impl FnMut(bool),
rng: &mut impl Rng,
) -> Result<(), String> {
let mut node = &mut self.root;
let mut depth = 0;
let mut uncached_state = None;
while depth < self.cached_depth && self.reserved_cache_bytes <= MAX_CACHE_BYTES {
if node.state.axes.is_empty() {
if node.symbolic_suffix.is_none() {
node.symbolic_suffix = Some(CliffordSuffixPlan::from_state(
&node.state,
&targets[depth..],
));
}
if let Some(plan) = node.symbolic_suffix.as_ref().unwrap() {
plan.sample(&targets[depth..], &mut push, rng);
depth = targets.len();
break;
}
}
let TerminalMeasurement {
q, basis, inverted, ..
} = &targets[depth];
let (q, basis, inverted) = (*q, *basis, *inverted);
if node.measurement.is_none() {
node.measurement = Some(if node.state.axes.is_empty() {
let probability_zero = node.state.measurement_probabilities(q, basis)?.0;
PreparedTerminalMeasurement::Clifford { probability_zero }
} else {
let pauli = node.state.single_qubit_pauli(q, basis)?;
let (mask, independent) = node.state.coordinate_mask(&pauli.x);
let probability_zero =
node.state.pauli_probability_zero(&pauli, mask, independent);
PreparedTerminalMeasurement::Active {
probability_zero,
pauli,
mask,
independent,
}
});
}
let outcome = match node.measurement.as_ref().unwrap() {
PreparedTerminalMeasurement::Active {
probability_zero, ..
} => rng.r#gen::<f64>() >= *probability_zero,
PreparedTerminalMeasurement::Clifford { probability_zero } => {
if *probability_zero == 0.5 {
rng.r#gen::<bool>()
} else {
*probability_zero < 0.5
}
}
};
let branch = usize::from(outcome);
if node.children[branch].is_none() {
let mut state = node.state.clone();
match node.measurement.as_ref().unwrap() {
PreparedTerminalMeasurement::Clifford { .. } => {
state.measure_clifford_forced(q, basis, outcome);
}
PreparedTerminalMeasurement::Active {
probability_zero,
pauli,
mask,
independent,
} => {
if *independent {
state.absorb_independent_measurement(q, basis, outcome, pauli)?;
} else {
state.project_active_measurement(
q,
basis,
pauli,
*mask,
outcome,
*probability_zero,
)?;
}
}
}
state.retire_fixed_axes();
let child_bytes = terminal_cache_state_bytes(&state, targets.len() - depth - 1);
let retains_large_state = state.coefficients.len() > MAX_CACHED_COEFFICIENTS
&& state.coefficients.len() >= node.state.coefficients.len();
if self.cached_nodes == self.max_cached_nodes
|| retains_large_state
|| child_bytes > MAX_CACHE_BYTES.saturating_sub(self.reserved_cache_bytes)
{
push(outcome ^ inverted);
depth += 1;
uncached_state = Some(state);
break;
}
node.children[branch] = Some(Box::new(TerminalMeasurementNode::new(state)));
self.cached_nodes += 1;
self.reserved_cache_bytes += child_bytes;
}
push(outcome ^ inverted);
node = node.children[branch].as_mut().unwrap();
depth += 1;
}
if depth < targets.len() {
let mut state = uncached_state.unwrap_or_else(|| node.state.clone());
for target in &targets[depth..] {
let outcome = state.measure(target.q, target.basis, rng)?;
state.retire_fixed_axes();
push(outcome ^ target.inverted);
}
}
Ok(())
}
}
fn is_deterministic_near_instruction(instruction: &StimInstr) -> bool {
let StimInstr::Op { name, targets, .. } = instruction else {
let StimInstr::Repeat { body, .. } = instruction else {
unreachable!()
};
return body.iter().all(is_deterministic_near_instruction);
};
match name.as_str() {
"I" | "H" | "S" | "SQRT_Z" | "S_DAG" | "SQRT_Z_DAG" | "X" | "Y" | "Z" | "T" | "T_DAG"
| "R_X" | "R_Y" | "R_Z" | "SQRT_X" | "SQRT_X_DAG" | "SQRT_Y" | "SQRT_Y_DAG" | "TICK"
| "QUBIT_COORDS" | "SHIFT_COORDS" => true,
"CX" | "CNOT" | "ZCX" | "CY" | "ZCY" | "CZ" | "ZCZ" | "SWAP" => targets
.iter()
.all(|target| matches!(target, StimTarget::Qubit(_))),
_ => false,
}
}
fn validate_near_block(
instructions: &[StimInstr],
max_qubit: &mut Option<u32>,
records: &mut u64,
) -> Result<(), String> {
for instruction in instructions {
match instruction {
StimInstr::Repeat { count, body } => {
if *count == 0 {
return Err("near-Clifford REPEAT count must be positive".into());
}
let before = *records;
validate_near_block(body, max_qubit, records)?;
let per_iteration = *records - before;
*records = per_iteration
.checked_mul(*count)
.and_then(|total| before.checked_add(total))
.ok_or("near-Clifford measurement record count overflow")?;
}
StimInstr::Op {
name,
args,
targets,
..
} => {
let gate = name.as_str();
let single = matches!(
gate,
"I" | "H"
| "S"
| "SQRT_Z"
| "S_DAG"
| "SQRT_Z_DAG"
| "X"
| "Y"
| "Z"
| "T"
| "T_DAG"
| "R_X"
| "R_Y"
| "R_Z"
| "SQRT_X"
| "SQRT_X_DAG"
| "SQRT_Y"
| "SQRT_Y_DAG"
| "R"
| "RZ"
| "RX"
| "RY"
);
let pair = matches!(
gate,
"CX" | "CNOT" | "ZCX" | "CY" | "ZCY" | "CZ" | "ZCZ" | "SWAP"
);
let measure = matches!(
gate,
"M" | "MZ" | "MX" | "MY" | "MR" | "MRZ" | "MRX" | "MRY"
);
let noise_single =
matches!(gate, "X_ERROR" | "Y_ERROR" | "Z_ERROR" | "DEPOLARIZE1");
let noise_pair = gate == "DEPOLARIZE2";
let annotation = matches!(
gate,
"DETECTOR" | "OBSERVABLE_INCLUDE" | "TICK" | "QUBIT_COORDS" | "SHIFT_COORDS"
);
if !(single || pair || measure || noise_single || noise_pair || annotation) {
return Err(format!("near-Clifford unsupported gate {name}"));
}
if matches!(gate, "R_X" | "R_Y" | "R_Z") {
if args.len() != 1 || !args[0].is_finite() {
return Err(format!(
"near-Clifford {name} requires one finite half-turn angle"
));
}
} else if noise_single || noise_pair {
if args.len() != 1 || !args[0].is_finite() || !(0.0..=1.0).contains(&args[0]) {
return Err(format!(
"near-Clifford {name} requires one probability in [0,1]"
));
}
} else if gate == "OBSERVABLE_INCLUDE" {
if args.len() != 1
|| !args[0].is_finite()
|| args[0].fract() != 0.0
|| args[0] < 0.0
|| args[0] > u32::MAX as f64
{
return Err("near-Clifford OBSERVABLE_INCLUDE requires one nonnegative integer index".into());
}
} else if matches!(gate, "DETECTOR" | "QUBIT_COORDS" | "SHIFT_COORDS") {
if args.iter().any(|value| !value.is_finite()) {
return Err(format!("near-Clifford {name} requires finite coordinates"));
}
} else if !args.is_empty() {
return Err(format!("near-Clifford {name} takes no arguments"));
}
if pair || noise_pair {
if !targets.len().is_multiple_of(2) {
return Err(format!("near-Clifford {name} requires qubit pairs"));
}
for targets in targets.chunks_exact(2) {
let second = match targets[1] {
StimTarget::Qubit(q) => q,
_ => {
return Err(format!(
"near-Clifford {name} requires a qubit as second target"
));
}
};
*max_qubit =
Some(max_qubit.map_or(second, |previous| previous.max(second)));
match targets[0] {
StimTarget::Qubit(first) => {
if first == second {
return Err(format!(
"near-Clifford {name} requires distinct qubits"
));
}
*max_qubit =
Some(max_qubit.map_or(first, |previous| previous.max(first)));
}
StimTarget::Rec(offset) if pair && gate != "SWAP" && offset < 0 => {
validate_near_record(offset, *records)?;
}
StimTarget::Sweep(_) if pair && gate != "SWAP" => {}
_ => {
return Err(format!(
"near-Clifford {name} requires qubit pairs or supported feedback"
));
}
}
}
} else if matches!(gate, "DETECTOR" | "OBSERVABLE_INCLUDE") {
for target in targets {
let StimTarget::Rec(offset) = target else {
return Err(format!(
"near-Clifford {name} requires negative rec targets"
));
};
validate_near_record(*offset, *records)?;
}
} else if matches!(gate, "SHIFT_COORDS" | "TICK") {
if !targets.is_empty() {
return Err(format!("near-Clifford {name} takes no targets"));
}
} else {
if matches!(
gate,
"T" | "T_DAG"
| "R_X"
| "R_Y"
| "R_Z"
| "X_ERROR"
| "Y_ERROR"
| "Z_ERROR"
| "DEPOLARIZE1"
) && targets.is_empty()
{
return Err(format!("near-Clifford {name} requires a qubit target"));
}
for target in targets {
let q = match target {
StimTarget::Qubit(q) => *q,
StimTarget::QubitInv(q) if measure => *q,
_ => {
return Err(format!("near-Clifford {name} requires qubit targets"));
}
};
*max_qubit = Some(max_qubit.map_or(q, |previous| previous.max(q)));
}
if measure {
*records =
records
.checked_add(u64::try_from(targets.len()).map_err(
|_| "near-Clifford measurement record count overflow",
)?)
.ok_or("near-Clifford measurement record count overflow")?;
}
}
}
}
}
Ok(())
}
fn validate_near_record(offset: i32, records: u64) -> Result<(), String> {
if offset >= 0 || u64::from(offset.unsigned_abs()) > records {
return Err("near-Clifford rec out of range".into());
}
Ok(())
}
fn run_near_block(
instructions: &[StimInstr],
state: &mut ActiveState,
measurements: &mut Vec<bool>,
detectors: &mut Vec<bool>,
observables: &mut Vec<(u32, bool)>,
sweep_bits: &[bool],
rng: &mut impl Rng,
) -> Result<(), String> {
for instruction in instructions {
match instruction {
StimInstr::Repeat { count, body } => {
for _ in 0..*count {
run_near_block(
body,
state,
measurements,
detectors,
observables,
sweep_bits,
rng,
)?;
}
}
StimInstr::Op {
name,
args,
targets,
..
} => {
if matches!(
name.as_str(),
"CX" | "CNOT" | "ZCX" | "CY" | "ZCY" | "CZ" | "ZCZ" | "SWAP"
) {
for pair in targets.chunks_exact(2) {
let b = pair[1].qubit_index().unwrap() as usize;
match pair[0] {
StimTarget::Qubit(a) => apply_near_pair(state, name, a as usize, b)?,
StimTarget::Rec(offset) => {
if near_record(measurements, offset)? {
apply_near_feedback(state, name, b)?;
}
}
StimTarget::Sweep(k) => {
if sweep_bits.get(k as usize).copied().unwrap_or(false) {
apply_near_feedback(state, name, b)?;
}
}
_ => unreachable!("validated near-Clifford pair target"),
}
}
continue;
}
if name == "DEPOLARIZE2" {
for pair in targets.chunks_exact(2) {
if near_noise_occurs(args[0], rng) {
let branch = rng.gen_range(1..16);
apply_near_pauli(
state,
pair[0].qubit_index().unwrap() as usize,
branch / 4,
)?;
apply_near_pauli(
state,
pair[1].qubit_index().unwrap() as usize,
branch % 4,
)?;
}
}
continue;
}
if matches!(name.as_str(), "DETECTOR" | "OBSERVABLE_INCLUDE") {
let mut parity = false;
for target in targets {
let StimTarget::Rec(offset) = target else {
unreachable!("validated record target")
};
parity ^= near_record(measurements, *offset)?;
}
if name == "DETECTOR" {
detectors.push(parity);
} else {
observables.push((args[0] as u32, parity));
}
continue;
}
if matches!(name.as_str(), "TICK" | "QUBIT_COORDS" | "SHIFT_COORDS") {
continue;
}
for target in targets {
let q = target.qubit_index().unwrap() as usize;
match name.as_str() {
"I" => {}
"H" => state.apply_clifford(CliffordGate::H(q))?,
"S" | "SQRT_Z" => state.apply_clifford(CliffordGate::S(q))?,
"S_DAG" | "SQRT_Z_DAG" => state.apply_clifford(CliffordGate::SDag(q))?,
"X" => state.apply_clifford(CliffordGate::X(q))?,
"Y" => state.apply_clifford(CliffordGate::Y(q))?,
"Z" => state.apply_clifford(CliffordGate::Z(q))?,
"SQRT_X" | "SQRT_X_DAG" => {
state.apply_clifford(CliffordGate::H(q))?;
state.apply_clifford(if name == "SQRT_X" {
CliffordGate::S(q)
} else {
CliffordGate::SDag(q)
})?;
state.apply_clifford(CliffordGate::H(q))?;
}
"SQRT_Y" => {
state.apply_clifford(CliffordGate::Z(q))?;
state.apply_clifford(CliffordGate::H(q))?;
}
"SQRT_Y_DAG" => {
state.apply_clifford(CliffordGate::H(q))?;
state.apply_clifford(CliffordGate::Z(q))?;
}
"R_X" | "R_Y" | "R_Z" => {
let basis = match name.as_str() {
"R_X" => MeasurementBasis::X,
"R_Y" => MeasurementBasis::Y,
_ => MeasurementBasis::Z,
};
state.rotate_axis(q, basis, args[0])?;
}
"T" => state.t(q)?,
"T_DAG" => state.t_dag(q)?,
"X_ERROR" | "Y_ERROR" | "Z_ERROR" | "DEPOLARIZE1" => {
if near_noise_occurs(args[0], rng) {
let branch = match name.as_str() {
"X_ERROR" => 1,
"Y_ERROR" => 2,
"Z_ERROR" => 3,
_ => rng.gen_range(1..4),
};
apply_near_pauli(state, q, branch)?;
}
}
"R" | "RZ" | "RX" | "RY" => {
let basis = match name.as_str() {
"RX" => MeasurementBasis::X,
"RY" => MeasurementBasis::Y,
_ => MeasurementBasis::Z,
};
state.reset(q, basis, rng)?;
}
"M" | "MZ" | "MX" | "MY" => {
let basis = match name.as_str() {
"MX" => MeasurementBasis::X,
"MY" => MeasurementBasis::Y,
_ => MeasurementBasis::Z,
};
let mut result = state.measure(q, basis, rng)?;
state.retire_fixed_axes();
result ^= matches!(target, StimTarget::QubitInv(_));
measurements.push(result);
}
"MR" | "MRZ" | "MRX" | "MRY" => {
let basis = match name.as_str() {
"MRX" => MeasurementBasis::X,
"MRY" => MeasurementBasis::Y,
_ => MeasurementBasis::Z,
};
let mut result = state.measure_reset(q, basis, rng)?;
result ^= matches!(target, StimTarget::QubitInv(_));
measurements.push(result);
}
_ => unreachable!("validated near-Clifford operation"),
}
}
}
}
}
Ok(())
}
fn near_record(measurements: &[bool], offset: i32) -> Result<bool, String> {
let distance =
usize::try_from(offset.unsigned_abs()).map_err(|_| "near-Clifford rec out of range")?;
if offset >= 0 || distance == 0 || distance > measurements.len() {
return Err("near-Clifford rec out of range".into());
}
Ok(measurements[measurements.len() - distance])
}
fn near_noise_occurs(probability: f64, rng: &mut impl Rng) -> bool {
probability >= 1.0 || (probability > 0.0 && rng.r#gen::<f64>() < probability)
}
fn apply_near_pauli(state: &mut ActiveState, q: usize, branch: usize) -> Result<(), String> {
let gate = match branch {
0 => return Ok(()),
1 => CliffordGate::X(q),
2 => CliffordGate::Y(q),
3 => CliffordGate::Z(q),
_ => unreachable!("validated Pauli branch"),
};
state.apply_clifford(gate)
}
fn apply_near_feedback(state: &mut ActiveState, name: &str, target: usize) -> Result<(), String> {
let branch = match name {
"CX" | "CNOT" | "ZCX" => 1,
"CY" | "ZCY" => 2,
"CZ" | "ZCZ" => 3,
_ => unreachable!("validated near-Clifford feedback"),
};
apply_near_pauli(state, target, branch)
}
fn apply_near_pair(state: &mut ActiveState, name: &str, a: usize, b: usize) -> Result<(), String> {
match name {
"CX" | "CNOT" | "ZCX" => state.apply_clifford(CliffordGate::CX(a, b)),
"CZ" | "ZCZ" => state.apply_clifford(CliffordGate::CZ(a, b)),
"SWAP" => state.apply_clifford(CliffordGate::Swap(a, b)),
"CY" | "ZCY" => {
state.apply_clifford(CliffordGate::SDag(b))?;
state.apply_clifford(CliffordGate::CX(a, b))?;
state.apply_clifford(CliffordGate::S(b))
}
_ => unreachable!("validated near-Clifford pair gate"),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn parametric_axis_probabilities_follow_half_turn_bloch_coordinates() {
for alpha in [
-0.7,
-0.3040867239846964,
-0.25,
0.0,
0.02,
0.25,
0.5,
1.0,
2.0,
5.25,
] {
let theta = alpha * std::f64::consts::PI;
for (axis, basis, expected) in [
(
MeasurementBasis::X,
MeasurementBasis::Z,
(1.0 + theta.cos()) / 2.0,
),
(
MeasurementBasis::X,
MeasurementBasis::Y,
(1.0 - theta.sin()) / 2.0,
),
(
MeasurementBasis::Y,
MeasurementBasis::X,
(1.0 + theta.sin()) / 2.0,
),
(
MeasurementBasis::Z,
MeasurementBasis::X,
(1.0 + theta.cos()) / 2.0,
),
(
MeasurementBasis::Z,
MeasurementBasis::Y,
(1.0 + theta.sin()) / 2.0,
),
] {
let mut state = ActiveState::new(1, 2);
if axis == MeasurementBasis::Z {
state.apply_clifford(CliffordGate::H(0)).unwrap();
}
state.rotate_axis(0, axis, alpha).unwrap();
let actual = state.measurement_probabilities(0, basis).unwrap().0;
assert!(
(actual - expected).abs() < 1e-13,
"alpha={alpha}, axis={axis:?}, basis={basis:?}: {actual} != {expected}"
);
}
}
}
use rand::{RngCore, SeedableRng, rngs::StdRng};
fn multiply_snapshot_row_reference(
product: &mut Pauli,
snapshot: &CanonicalTableauSnapshot,
row: usize,
) {
let right = Pauli::from_snapshot_row(snapshot, row);
let sign = if dot(&product.z, &right.x) { 2 } else { 0 };
product.phase = (product.phase + right.phase + sign) % 4;
xor(&mut product.x, &right.x);
xor(&mut product.z, &right.z);
}
#[test]
fn pauli_row_products_preserve_signed_local_phases_and_wide_chains() {
for basis in [
MeasurementBasis::X,
MeasurementBasis::Y,
MeasurementBasis::Z,
] {
for negative in [false, true] {
let mut frame = StabilizerState::new(1);
match basis {
MeasurementBasis::X => {}
MeasurementBasis::Y => frame.s(0),
MeasurementBasis::Z => frame.h(0),
}
if negative {
if basis == MeasurementBasis::Z {
frame.x_gate(0);
} else {
frame.z_gate(0);
}
}
let snapshot = frame.canonical_snapshot();
for left in 0..4 {
for phase in 0..4 {
let mut actual = Pauli {
x: vec![left & 1 != 0],
z: vec![left & 2 != 0],
phase,
};
let mut expected = actual.clone();
multiply_snapshot_row_reference(&mut expected, &snapshot, 0);
actual.multiply_tableau_row(&frame, 0);
assert_eq!(
(actual.x, actual.z, actual.phase),
(expected.x, expected.z, expected.phase)
);
}
}
}
}
let mut rng = StdRng::seed_from_u64(20261005);
for width in [1, 2, 63, 64, 65, 127, 128, 129, 193, 260, 4096] {
let mut frame = StabilizerState::new(width);
frame.h(0);
for q in 1..width {
frame.cx(0, q);
}
for q in 0..width {
frame.s(q);
}
for _ in 0..64 {
let q = rng.gen_range(0..width);
frame.h(q);
frame.s(q);
frame.y_gate(q);
if width > 1 {
let target = (q + rng.gen_range(1..width)) % width;
frame.cx(q, target);
frame.right_cz(q, target);
}
}
let snapshot = frame.canonical_snapshot();
let mut actual = Pauli::identity(width);
let mut expected = actual.clone();
for row in std::iter::once(width).chain((0..64).map(|_| rng.gen_range(0..2 * width))) {
multiply_snapshot_row_reference(&mut expected, &snapshot, row);
actual.multiply_tableau_row(&frame, row);
assert_eq!(actual.x, expected.x, "width={width}, row={row}");
assert_eq!(actual.z, expected.z, "width={width}, row={row}");
assert_eq!(actual.phase, expected.phase, "width={width}, row={row}");
}
}
}
#[test]
fn near_clifford_row_products_match_legacy_phases_and_wide_rows() {
StabilizerState::check_near_clifford_local_products();
let mut rng = StdRng::seed_from_u64(20261003);
for width in [1, 2, 63, 64, 65, 127, 128, 129, 193, 4096] {
let mut state = StabilizerState::new(width);
for _ in 0..128 {
let q = rng.gen_range(0..width);
state.h(q);
state.s(q);
if rng.r#gen::<bool>() {
state.x_gate(q);
}
if width > 1 {
let target = (q + rng.gen_range(1..width)) % width;
state.cx(q, target);
}
}
for _ in 0..if width == 4096 { 8 } else { 128 } {
let h = rng.gen_range(0..2 * width);
let i = (h + rng.gen_range(1..2 * width)) % (2 * width);
let mut reference = state.clone();
reference.row_mult_reference(h, i);
state.row_mult_near_clifford(h, i);
assert_eq!(state.canonical_snapshot(), reference.canonical_snapshot());
}
}
}
#[test]
fn single_qubit_coordinates_match_general_conversion_on_signed_entangled_frames() {
let mut rng = StdRng::seed_from_u64(20260930);
for n in [1, 4, 64, 65, 128, 129, 193] {
let mut state = ActiveState::new(n, 8);
for _ in 0..12 {
for _ in 0..24 {
let q = rng.gen_range(0..n);
let other = if n == 1 {
q
} else {
(q + rng.gen_range(1..n)) % n
};
let gate = match rng.gen_range(0..6) {
0 => CliffordGate::H(q),
1 => CliffordGate::S(q),
2 => CliffordGate::SDag(q),
3 => CliffordGate::Y(q),
4 if n > 1 => CliffordGate::CX(q, other),
_ if n > 1 => CliffordGate::CZ(q, other),
_ => CliffordGate::X(q),
};
state.apply_clifford(gate).unwrap();
}
for q in [0, n / 2, n - 1, rng.gen_range(0..n)] {
for basis in [
MeasurementBasis::X,
MeasurementBasis::Y,
MeasurementBasis::Z,
] {
let mut x = vec![false; n];
let mut z = vec![false; n];
x[q] = matches!(basis, MeasurementBasis::X | MeasurementBasis::Y);
z[q] = matches!(basis, MeasurementBasis::Y | MeasurementBasis::Z);
let expected = state.physical_pauli(&x, &z).unwrap();
let actual = state.single_qubit_pauli(q, basis).unwrap();
assert_eq!(actual.x, expected.x, "n={n}, q={q}, basis={basis:?}");
assert_eq!(actual.z, expected.z, "n={n}, q={q}, basis={basis:?}");
assert_eq!(
actual.phase, expected.phase,
"n={n}, q={q}, basis={basis:?}"
);
}
}
}
}
}
#[test]
fn record_order_swaps_restore_nontrivial_cycle_in_place() {
let ordered = [2, 0, 1].map(|record_index| TerminalMeasurement {
q: record_index,
basis: MeasurementBasis::Z,
inverted: false,
record_index,
});
let mut bits = vec![true, false, false];
for (left, right) in record_order_swaps(&ordered) {
bits.swap(left, right);
}
assert_eq!(bits, [false, false, true]);
}
#[test]
fn symbolic_suffix_rebases_multiple_virtual_origin_bits() {
let mut state = ActiveState::new(3, 16);
for gate in [
CliffordGate::H(0),
CliffordGate::CX(0, 1),
CliffordGate::S(1),
CliffordGate::H(2),
CliffordGate::CX(2, 0),
] {
state.apply_clifford(gate).unwrap();
}
let targets = [
(0, MeasurementBasis::X),
(1, MeasurementBasis::Y),
(2, MeasurementBasis::Z),
(0, MeasurementBasis::Z),
]
.map(|(q, basis)| TerminalMeasurement {
q,
basis,
inverted: false,
record_index: q,
});
for origin in [
[true, false, true],
[true, true, true],
[false, true, false],
] {
state.origin.copy_from_slice(&origin);
let plan = CliffordSuffixPlan::from_state(&state, &targets).unwrap();
for seed in 0..32 {
let mut symbolic_rng = StdRng::seed_from_u64(seed);
let mut reference_rng = StdRng::seed_from_u64(seed);
let mut actual = Vec::new();
plan.sample(&targets, |bit| actual.push(bit), &mut symbolic_rng);
let mut reference_state = state.clone();
let expected = targets
.iter()
.map(|target| {
reference_state
.measure(target.q, target.basis, &mut reference_rng)
.unwrap()
})
.collect::<Vec<_>>();
assert_eq!(actual, expected, "origin={origin:?}, seed={seed}");
assert_eq!(symbolic_rng.next_u64(), reference_rng.next_u64());
}
}
}
#[test]
fn symbolic_suffix_preserves_rng_at_64_random_bits() {
let mut state = ActiveState::new(64, 16);
for q in 0..64 {
state.apply_clifford(CliffordGate::H(q)).unwrap();
}
let targets = (0..64)
.chain([63, 0])
.enumerate()
.map(|(record_index, q)| TerminalMeasurement {
q,
basis: MeasurementBasis::Z,
inverted: false,
record_index,
})
.collect::<Vec<_>>();
let plan = CliffordSuffixPlan::from_state(&state, &targets).unwrap();
assert_eq!(plan.random_count(), 64);
assert!(matches!(plan, CliffordSuffixPlan::Compact(_)));
for seed in [0, 17, 739] {
let mut symbolic_rng = StdRng::seed_from_u64(seed);
let mut reference_rng = StdRng::seed_from_u64(seed);
let mut actual = Vec::new();
plan.sample(&targets, |bit| actual.push(bit), &mut symbolic_rng);
let mut reference_state = state.clone();
let expected = targets
.iter()
.map(|target| {
reference_state
.measure(target.q, target.basis, &mut reference_rng)
.unwrap()
})
.collect::<Vec<_>>();
assert_eq!(actual, expected, "seed={seed}");
assert_eq!(symbolic_rng.next_u64(), reference_rng.next_u64());
}
}
#[test]
fn symbolic_suffix_preserves_cross_word_correlations_at_128_random_bits() {
let mut state = ActiveState::new(130, 16);
for q in 0..128 {
state.apply_clifford(CliffordGate::H(q)).unwrap();
}
state.apply_clifford(CliffordGate::CX(63, 128)).unwrap();
state.apply_clifford(CliffordGate::CX(64, 128)).unwrap();
let targets = (0..129)
.chain([63, 64, 127])
.enumerate()
.map(|(record_index, q)| TerminalMeasurement {
q,
basis: MeasurementBasis::Z,
inverted: false,
record_index,
})
.collect::<Vec<_>>();
let plan = CliffordSuffixPlan::from_state(&state, &targets).unwrap();
assert_eq!(plan.random_count(), 128);
assert!(matches!(plan, CliffordSuffixPlan::DoubleWord(_)));
for seed in [0, 17, 739] {
let mut symbolic_rng = StdRng::seed_from_u64(seed);
let mut reference_rng = StdRng::seed_from_u64(seed);
let mut actual = Vec::new();
plan.sample(&targets, |bit| actual.push(bit), &mut symbolic_rng);
let mut reference_state = state.clone();
let expected = targets
.iter()
.map(|target| {
reference_state
.measure(target.q, target.basis, &mut reference_rng)
.unwrap()
})
.collect::<Vec<_>>();
assert_eq!(actual, expected, "seed={seed}");
assert_eq!(actual[128], actual[63] ^ actual[64]);
assert_eq!(symbolic_rng.next_u64(), reference_rng.next_u64());
}
state.apply_clifford(CliffordGate::H(129)).unwrap();
let extra = TerminalMeasurement {
q: 129,
basis: MeasurementBasis::Z,
inverted: false,
record_index: targets.len(),
};
let mut too_wide = targets;
too_wide.insert(128, extra);
let wide_plan = CliffordSuffixPlan::from_state(&state, &too_wide).unwrap();
assert_eq!(wide_plan.random_count(), 129);
assert!(matches!(wide_plan, CliffordSuffixPlan::Wide(_)));
for seed in [0, 17, 739] {
let mut symbolic_rng = StdRng::seed_from_u64(seed);
let mut reference_rng = StdRng::seed_from_u64(seed);
let mut actual = Vec::new();
wide_plan.sample(&too_wide, |bit| actual.push(bit), &mut symbolic_rng);
let mut reference_state = state.clone();
let expected = too_wide
.iter()
.map(|target| {
reference_state
.measure(target.q, target.basis, &mut reference_rng)
.unwrap()
})
.collect::<Vec<_>>();
assert_eq!(actual, expected, "seed={seed}");
assert_eq!(symbolic_rng.next_u64(), reference_rng.next_u64());
}
}
#[test]
fn terminal_cache_caps_distinct_wide_frames_and_long_symbolic_plans() {
assert_eq!(terminal_cache_node_limit(20, 20), 1024);
assert_eq!(terminal_cache_node_limit(4096, 20), 1);
assert!(terminal_cache_node_limit(512, 20) < 1024);
assert!(terminal_cache_node_limit(20, 65_536) < 128);
}
#[test]
fn high_rank_cache_respects_byte_budget_and_falls_back_with_identical_rng() {
let text = (0..12)
.map(|q| format!("H {q}\nT {q}\n"))
.collect::<String>()
+ "MX 0 1 2 3 4 5 6 7 8 9 10 11";
let executor = NearCliffordExecutor::compile_text(&text).unwrap();
let prepared = executor.prepare_sampler().unwrap().prepared;
let targets = (0..12)
.map(|q| TerminalMeasurement {
q,
basis: MeasurementBasis::X,
inverted: false,
record_index: q,
})
.collect::<Vec<_>>();
let mut full = CachedTerminalSampler::new(prepared.clone(), &targets, 1024);
let mut bounded = CachedTerminalSampler::new(prepared, &targets, 1024);
let mut child = bounded.root.state.clone();
child
.measure(0, MeasurementBasis::X, &mut StdRng::seed_from_u64(739))
.unwrap();
child.retire_fixed_axes();
let reserve = terminal_cache_state_bytes(&child, 11);
bounded.reserved_cache_bytes = MAX_CACHE_BYTES - reserve;
let mut a = StdRng::seed_from_u64(739);
let mut b = StdRng::seed_from_u64(739);
for shots in [1, 0, 64, 256] {
assert_eq!(
full.sample(&targets, shots, &mut a).unwrap(),
bounded.sample(&targets, shots, &mut b).unwrap()
);
assert!(bounded.reserved_cache_bytes <= MAX_CACHE_BYTES);
}
assert_eq!(a.next_u64(), b.next_u64());
assert!(full.cached_nodes > 2);
assert_eq!(bounded.cached_nodes, 2);
}
#[test]
fn high_rank_independent_branches_do_not_retain_dense_children() {
let text = (0..12)
.map(|q| format!("H {q}\nT {q}\n"))
.collect::<String>()
+ "H 12\nM 12\nMX 0 1 2 3 4 5 6 7 8 9 10 11";
let executor = NearCliffordExecutor::compile_text(&text).unwrap();
let prepared = executor.prepare_sampler().unwrap().prepared;
let targets = std::iter::once(TerminalMeasurement {
q: 12,
basis: MeasurementBasis::Z,
inverted: false,
record_index: 0,
})
.chain((0..12).map(|q| TerminalMeasurement {
q,
basis: MeasurementBasis::X,
inverted: false,
record_index: q + 1,
}))
.collect::<Vec<_>>();
let mut cached = CachedTerminalSampler::new(prepared, &targets, 1024);
let mut rng = StdRng::seed_from_u64(739);
cached.sample(&targets, 256, &mut rng).unwrap();
assert_eq!(cached.cached_nodes, 1);
assert!(cached.root.measurement.is_some());
assert!(cached.root.children.iter().all(Option::is_none));
assert!(cached.reserved_cache_bytes < MAX_CACHE_BYTES);
}
#[test]
fn terminal_plan_bounds_nested_metadata_expansion() {
let instructions =
crate::parser::parse_lines("M 0\nREPEAT 65536 {\nREPEAT 65536 {\nTICK\n}\n}").unwrap();
assert!(TerminalPlan::from_instructions(&instructions).is_none());
}
#[test]
fn wide_tableau_row_y_phase_does_not_overflow() {
let n = 260;
let mut frame = StabilizerState::new(n);
frame.h(0);
for q in 1..n {
frame.cx(0, q);
}
for q in 0..n {
frame.s(q);
}
let (_, _, row_phase) = frame.canonical_row(n);
let mut product = Pauli::identity(n);
product.multiply_tableau_row(&frame, n);
assert!(product.x.iter().all(|&bit| bit));
assert!(product.z.iter().all(|&bit| bit));
assert_eq!(product.phase, (row_phase + (n % 4) as u8) % 4);
}
#[test]
fn forced_tableau_measurement_matches_legacy_branch() {
let mut state = StabilizerState::new(3);
for step in 0..18 {
match step % 6 {
0 => state.h(step % 3),
1 => state.cx(0, 1),
2 => state.s(1),
3 => state.cx(1, 2),
4 => state.h(2),
_ => state.cz(0, 2),
}
for q in 0..3 {
let mut rng = StdRng::seed_from_u64((step * 3 + q) as u64);
let mut reference = state.clone();
let mut forced = state.clone();
let expected = reference.measure_z(q, &mut rng);
let actual = forced.measure_z_with_forced_random_outcome(q, expected.0);
assert_eq!(actual, expected);
assert_eq!(forced.canonical_snapshot(), reference.canonical_snapshot());
}
}
}
#[test]
fn terminal_schedule_retires_active_axis_and_preserves_record_references() {
let circuit = NearCliffordExecutor::compile_text(
"H 0\nT 0\nH 0\nH 1\nM 1 0\nDETECTOR rec[-1]\nOBSERVABLE_INCLUDE(2) rec[-2]",
)
.unwrap();
let mut prepared = ActiveState::new(2, 16);
let mut rng = StdRng::seed_from_u64(17);
run_near_block(
&circuit.instructions[..circuit.prefix_len],
&mut prepared,
&mut Vec::new(),
&mut Vec::new(),
&mut Vec::new(),
&[],
&mut rng,
)
.unwrap();
assert_eq!(
circuit
.terminal_plan
.as_ref()
.unwrap()
.plan_order(&prepared),
vec![1, 0]
);
let shots = circuit.sample(512, &mut rng).unwrap();
for shot in shots {
assert_eq!(shot.detectors, vec![shot.measurements[1]]);
assert_eq!(shot.observables, vec![(2, shot.measurements[0])]);
}
}
#[test]
fn repeated_terminal_schedule_reorders_first_pass_only() {
fn order(source: &str) -> Vec<usize> {
let circuit = NearCliffordExecutor::compile_text(source).unwrap();
let sampler = circuit.prepare_sampler().unwrap();
circuit
.terminal_plan
.as_ref()
.unwrap()
.plan_order(&sampler.prepared)
}
let first_pass = order(include_str!(
"../tests/fixtures/near_clifford_batch_20q_8t.stim"
));
assert_ne!(first_pass, (0..20).collect::<Vec<_>>());
let repeated = order(include_str!(
"../tests/fixtures/near_clifford_batch_20q_8t_repeated.stim"
));
assert_eq!(&repeated[..20], first_pass);
assert_eq!(&repeated[20..], (20..40).collect::<Vec<_>>());
assert_eq!(order("H 0\nT 0\nM 0\nMX 0"), vec![0, 1]);
assert_eq!(order("H 0 1\nT 0\nM 0\nM 0\nM 1"), vec![0, 1, 2]);
}
#[test]
fn terminal_cache_limit_falls_back_without_changing_shots_or_rng() {
let circuit = NearCliffordExecutor::compile_text("H 0\nT 0\nH 0\nH 1\nM 0 1").unwrap();
let mut prepared = ActiveState::new(2, 16);
prepared.apply_clifford(CliffordGate::H(0)).unwrap();
prepared.t(0).unwrap();
prepared.apply_clifford(CliffordGate::H(0)).unwrap();
prepared.apply_clifford(CliffordGate::H(1)).unwrap();
let targets = [0, 1].map(|q| TerminalMeasurement {
q,
basis: MeasurementBasis::Z,
inverted: false,
record_index: q,
});
for max_cached_nodes in [1, 2, 3] {
let mut batch_rng = StdRng::seed_from_u64(739);
let mut reference_rng = StdRng::seed_from_u64(739);
let mut sampler =
CachedTerminalSampler::new(prepared.clone(), &targets, max_cached_nodes);
for shots in [512, 0, 64] {
let batch = sampler.sample(&targets, shots, &mut batch_rng).unwrap();
let reference = (0..shots)
.map(|_| circuit.run(&mut reference_rng).unwrap())
.collect::<Vec<_>>();
assert_eq!(batch, reference, "max_cached_nodes={max_cached_nodes}");
assert!(sampler.cached_nodes <= max_cached_nodes);
}
assert_eq!(batch_rng.next_u64(), reference_rng.next_u64());
}
}
#[test]
fn independent_measurement_reuses_pauli_only_in_the_unchanged_frame() {
let mut rng = StdRng::seed_from_u64(20261004);
for width in [16, 65, 129, 193] {
for mode in 0..4 {
let mut state = dense_coordinate_state(width, &mut rng);
if mode == 1 || mode == 2 {
state.canonicalize_active_axes();
}
if mode == 0 {
state.origin.fill(false);
}
if mode == 2 || mode == 3 {
state.origin[0] = true;
}
let mut checked = 0;
for q in 0..width {
for basis in [
MeasurementBasis::X,
MeasurementBasis::Y,
MeasurementBasis::Z,
] {
let pauli = state.single_qubit_pauli(q, basis).unwrap();
if !state.coordinate_mask(&pauli.x).1 {
continue;
}
for outcome in [false, true] {
let mut actual = state.clone();
let mut expected = state.clone();
let before = expected.frame_snapshot();
expected.canonicalize_active_axes();
if mode == 0 {
assert_ne!(
before,
expected.frame_snapshot(),
"noncanonical axes must actually change the frame"
);
}
let transformed = expected.single_qubit_pauli(q, basis).unwrap();
expected
.absorb_independent_measurement(q, basis, outcome, &transformed)
.unwrap();
actual
.absorb_independent_measurement(q, basis, outcome, &pauli)
.unwrap();
assert_eq!(
actual.frame_snapshot(),
expected.frame_snapshot(),
"width={width} mode={mode} q={q} basis={basis:?}"
);
assert_eq!(actual.origin, expected.origin);
assert_eq!(actual.axes, expected.axes);
assert_eq!(actual.coefficients, expected.coefficients);
assert_eq!(actual.global_phase, expected.global_phase);
}
checked += 1;
if checked == 6 {
break;
}
}
if checked == 6 {
break;
}
}
assert_eq!(
checked, 6,
"each frame must exercise independent measurements"
);
}
}
}
fn dense_coordinate_state(n: usize, rng: &mut StdRng) -> ActiveState {
let rank = n.min(8);
let mut state = ActiveState::new(n, rank);
state.axes_are_canonical = false;
for q in 0..rank {
state.apply_clifford(CliffordGate::H(q)).unwrap();
let mut axis = vec![false; n];
axis[q] = true;
state.axes.push(axis);
}
state.coefficients = (0..1 << rank)
.map(|_| ComplexAmp::new(rng.r#gen::<f64>() - 0.5, rng.r#gen::<f64>() - 0.5))
.collect();
let norm = state
.coefficients
.iter()
.map(|a| a.norm_sqr())
.sum::<f64>()
.sqrt();
for amplitude in &mut state.coefficients {
*amplitude = *amplitude * (1.0 / norm);
}
for bit in &mut state.origin {
*bit = rng.r#gen();
}
for _ in 0..4 * n {
let control = rng.gen_range(0..n);
let target = (control + rng.gen_range(1..n)) % n;
Arc::make_mut(&mut state.frame).right_cx(control, target);
for axis in &mut state.axes {
axis[target] ^= axis[control];
}
state.origin[target] ^= state.origin[control];
}
for _ in 0..48 {
let q = rng.gen_range(0..rank);
let other = (q + rng.gen_range(1..rank)) % rank;
let gate = match rng.gen_range(0..7) {
0 => CliffordGate::H(q),
1 => CliffordGate::S(q),
2 => CliffordGate::SDag(q),
3 => CliffordGate::Y(q),
4 => CliffordGate::CX(q, other),
5 => CliffordGate::CZ(q, other),
_ => CliffordGate::X(q),
};
state.apply_clifford(gate).unwrap();
}
state
}
fn rebase_origin_reference(state: &mut ActiveState) {
if !state.origin.contains(&true) {
return;
}
let snapshot = state.frame.canonical_snapshot();
for (q, bit) in state.origin.iter_mut().enumerate() {
if *bit {
let pauli = Pauli::from_snapshot_row(&snapshot, q);
let y_count = pauli
.x
.iter()
.zip(&pauli.z)
.filter(|(x, z)| **x && **z)
.count() as u8;
state.global_phase =
state.global_phase * i_pow((pauli.phase + 4 - y_count % 4) % 4);
for (physical_q, (&x, &z)) in pauli.x.iter().zip(&pauli.z).enumerate() {
match (x, z) {
(true, true) => Arc::make_mut(&mut state.frame).y_gate(physical_q),
(true, false) => Arc::make_mut(&mut state.frame).x_gate(physical_q),
(false, true) => Arc::make_mut(&mut state.frame).z_gate(physical_q),
(false, false) => {}
}
}
*bit = false;
}
}
}
fn assert_same_rebased_state(actual: &ActiveState, expected: &ActiveState) {
assert_eq!(actual.frame_snapshot(), expected.frame_snapshot());
assert_eq!(actual.origin, expected.origin);
assert_eq!(actual.axes, expected.axes);
assert_eq!(actual.axes_are_canonical, expected.axes_are_canonical);
assert_eq!(actual.num_qubits, expected.num_qubits);
assert_eq!(actual.max_active_qubits, expected.max_active_qubits);
let bits = |a: ComplexAmp| (a.re.to_bits(), a.im.to_bits());
assert_eq!(bits(actual.global_phase), bits(expected.global_phase));
assert_eq!(
actual
.coefficients
.iter()
.copied()
.map(bits)
.collect::<Vec<_>>(),
expected
.coefficients
.iter()
.copied()
.map(bits)
.collect::<Vec<_>>()
);
}
#[test]
fn origin_rebasing_matches_physical_paulis_on_signed_entangled_frames() {
let mut rng = StdRng::seed_from_u64(20261005);
for n in [0, 1, 3, 8, 63, 64, 65, 127, 128, 129, 193] {
for variant in 0..4 {
let mut state = if n >= 3 {
dense_coordinate_state(n, &mut rng)
} else {
ActiveState::new(n, 2)
};
for q in 0..n {
state.apply_clifford(CliffordGate::S(q)).unwrap();
state.apply_clifford(CliffordGate::Y(q)).unwrap();
if n > 1 {
state
.apply_clifford(CliffordGate::CX(q, (q + 1) % n))
.unwrap();
}
}
state.origin = (0..n)
.map(|q| match variant {
0 => false,
1 => q == 0 || q == n - 1,
2 => true,
_ => rng.r#gen(),
})
.collect();
state.global_phase = match variant {
0 => ComplexAmp::new(-0.0, 0.0),
1 => ComplexAmp::new(0.0, -0.0),
2 => ComplexAmp::new(-0.3, 0.4),
_ => ComplexAmp::new(0.6, -0.8),
};
for shared in [false, true] {
let mut actual = state.clone();
let mut expected = state.clone();
actual.frame = Arc::new((*actual.frame).clone());
let fork = shared.then(|| actual.clone());
let pointer = Arc::as_ptr(&actual.frame);
actual.rebase_origin_into_frame();
rebase_origin_reference(&mut expected);
assert_same_rebased_state(&actual, &expected);
if !state.origin.contains(&true) {
assert_eq!(pointer, Arc::as_ptr(&actual.frame));
}
if let Some(fork) = fork {
assert_same_rebased_state(&fork, &state);
if state.origin.contains(&true) {
assert!(!Arc::ptr_eq(&actual.frame, &fork.frame));
}
}
actual.rebase_origin_into_frame();
assert_same_rebased_state(&actual, &expected);
if n > 0 && variant == 3 {
let mut a = StdRng::seed_from_u64(711);
let mut b = StdRng::seed_from_u64(711);
for basis in [
MeasurementBasis::X,
MeasurementBasis::Y,
MeasurementBasis::Z,
] {
assert_eq!(
actual.measure(n - 1, basis, &mut a),
expected.measure(n - 1, basis, &mut b)
);
actual.t(0).unwrap();
expected.t(0).unwrap();
assert_same_rebased_state(&actual, &expected);
}
assert_eq!(a.next_u64(), b.next_u64());
}
}
}
}
}
#[test]
fn origin_rebasing_preserves_all_small_bit_strings_and_large_y_counts() {
for n in [1, 2, 3, 4, 257] {
let mut state = ActiveState::new(n, 4);
for q in 1..n {
state.apply_clifford(CliffordGate::CX(0, q)).unwrap();
}
for q in 0..n {
state.apply_clifford(CliffordGate::S(q)).unwrap();
}
state.apply_clifford(CliffordGate::Z(0)).unwrap();
let snapshot = state.frame_snapshot();
assert_eq!(
snapshot.x[0]
.iter()
.zip(&snapshot.z[0])
.filter(|(x, z)| **x && **z)
.count(),
n
);
for mask in 0..1usize << n.min(4) {
let mut actual = state.clone();
for q in 0..n.min(4) {
actual.origin[q] = mask & (1 << q) != 0;
}
let mut expected = actual.clone();
actual.rebase_origin_into_frame();
rebase_origin_reference(&mut expected);
assert_same_rebased_state(&actual, &expected);
}
}
}
fn previous_pauli_probability(state: &ActiveState, pauli: &Pauli, mask: usize) -> f64 {
let (origin, signs) = state.sign_coordinates(&pauli.z);
let phase = i_pow(pauli.phase);
let image = |index: usize| {
let sign = if origin ^ ((index & signs).count_ones() & 1 != 0) {
-1.0
} else {
1.0
};
phase * (state.coefficients[index] * sign)
};
let expectation = if mask == 0 {
state
.coefficients
.iter()
.enumerate()
.map(|(index, amplitude)| (amplitude.conj() * image(index)).re)
.sum::<f64>()
} else {
let pivot = 1usize << (usize::BITS - 1 - mask.leading_zeros());
let mut expectation = 0.0;
for block in (0..state.coefficients.len()).step_by(pivot * 2) {
for offset in 0..pivot {
let index = block + offset;
expectation +=
2.0 * (state.coefficients[index ^ mask].conj() * image(index)).re;
}
}
expectation
};
((1.0 + expectation) / 2.0).clamp(0.0, 1.0)
}
#[test]
fn scalar_probability_preserves_general_formula_rounding_for_signed_pauli_orbits() {
let mut rng = StdRng::seed_from_u64(20261005);
for rank in [1, 2, 4, 8, 12, 16] {
let n = rank + 2;
let mut state = ActiveState::new(n, rank);
for q in 0..rank {
let mut axis = vec![false; n];
axis[q] = true;
state.axes.push(axis);
}
state.coefficients = (0..1 << rank)
.map(|index| match index % 17 {
0 => ComplexAmp::new(-0.0, 0.0),
1 => ComplexAmp::new(1e-160, -1e-160),
_ => ComplexAmp::new(rng.r#gen::<f64>() - 0.5, rng.r#gen::<f64>() - 0.5),
})
.collect();
let norm = state
.coefficients
.iter()
.map(|a| a.norm_sqr())
.sum::<f64>()
.sqrt();
for a in &mut state.coefficients {
*a = *a * (1.0 / norm);
}
let mut masks: Vec<usize> = vec![0, (1 << rank) - 1];
masks.extend((0..rank).map(|q| 1 << q));
masks.extend((0..16).map(|_| rng.gen_range(0..1 << rank)));
for mask in masks {
for signs in [
0usize,
1,
1 << (rank - 1),
(1 << rank) - 1,
rng.gen_range(0..1 << rank),
] {
let mut pauli = Pauli::identity(n);
for q in 0..rank {
pauli.x[q] = mask & (1 << q) != 0;
pauli.z[q] = signs & (1 << q) != 0;
}
pauli.z[rank] = true;
for origin in [false, true] {
state.origin[rank] = origin;
for negative in [false, true] {
pauli.phase =
((mask & signs).count_ones() & 1) as u8 + 2 * u8::from(negative);
let expected = previous_pauli_probability(&state, &pauli, mask);
let actual = state.pauli_probability_zero(&pauli, mask, false);
assert_eq!(
actual.to_bits(),
expected.to_bits(),
"rank={rank} mask={mask} signs={signs} origin={origin} phase={}",
pauli.phase
);
assert_eq!(state.pauli_probability_zero(&pauli, mask, true), 0.5);
}
}
}
}
}
}
#[test]
fn bulk_axis_canonicalization_matches_sequential_cnot_updates() {
let mut rng = StdRng::seed_from_u64(20261001);
for n in [3, 8, 64, 65, 129, 193] {
for _ in 0..4 {
let mut actual = dense_coordinate_state(n, &mut rng);
let mut expected = actual.clone();
expected.rebase_origin_into_frame();
let mut pivots = Vec::new();
for index in 0..expected.axes.len() {
let pivot = (0..n)
.find(|&bit| expected.axes[index][bit] && !pivots.contains(&bit))
.unwrap();
for bit in 0..n {
if bit != pivot && expected.axes[index][bit] {
Arc::make_mut(&mut expected.frame).right_cx(pivot, bit);
for axis in &mut expected.axes {
axis[bit] ^= axis[pivot];
}
}
}
pivots.push(pivot);
}
assert_eq!(actual.canonicalize_active_axes(), pivots);
assert_eq!(actual.frame_snapshot(), expected.frame_snapshot());
assert_eq!(actual.axes, expected.axes);
assert_eq!(actual.origin, expected.origin);
assert_eq!(actual.coefficients, expected.coefficients);
assert_eq!(actual.global_phase, expected.global_phase);
}
}
}
#[test]
fn direct_projection_matches_general_projection_on_dense_signed_coordinates() {
let mut rng = StdRng::seed_from_u64(20261002);
let mut diagonal = 0;
let mut nondiagonal = 0;
let mut odd_phase = 0;
for n in [3, 8, 64, 65, 129, 193] {
for _ in 0..4 {
let state = dense_coordinate_state(n, &mut rng);
for q in 0..n.min(8) {
for basis in [
MeasurementBasis::X,
MeasurementBasis::Y,
MeasurementBasis::Z,
] {
let pauli = state.single_qubit_pauli(q, basis).unwrap();
let (mask, independent) = state.coordinate_mask(&pauli.x);
assert!(!independent);
if mask == 0 {
diagonal += 1;
} else {
nondiagonal += 1;
}
odd_phase += usize::from(pauli.phase % 2 != 0);
let probability = state.pauli_probability_zero(&pauli, mask, false);
for outcome in [false, true] {
let mut expected = state.clone();
expected
.collapse_pauli_measurement(&pauli, mask, outcome, probability)
.unwrap();
if mask != 0 {
expected.retire_nondiagonal_measurement(q, basis).unwrap();
}
let mut actual = state.clone();
actual
.project_active_measurement(
q,
basis,
&pauli,
mask,
outcome,
probability,
)
.unwrap();
assert_eq!(
actual.frame_snapshot(),
expected.frame_snapshot(),
"n={n} q={q} basis={basis:?}"
);
assert_eq!(actual.axes, expected.axes);
assert_eq!(actual.origin, expected.origin);
assert_eq!(actual.global_phase, expected.global_phase);
assert_eq!(actual.coefficients.len(), expected.coefficients.len());
for (a, b) in actual.coefficients.iter().zip(&expected.coefficients) {
assert!(
(a.re - b.re).abs() < 1e-12 && (a.im - b.im).abs() < 1e-12,
"{a:?} != {b:?}"
);
}
assert!(
(actual
.coefficients
.iter()
.map(|a| a.norm_sqr())
.sum::<f64>()
- 1.0)
.abs()
< 1e-12
);
}
}
}
}
}
assert!(diagonal > 0 && nondiagonal > 0 && odd_phase > 0);
}
#[test]
fn rejected_direct_projection_preserves_all_state_fields() {
let mut state = ActiveState::new(3, 3);
state.apply_clifford(CliffordGate::H(0)).unwrap();
state.t(0).unwrap();
state.coefficients[0] = ComplexAmp::new(1.0, 0.0);
state.coefficients[1] = ComplexAmp::new(1e-16, 0.0);
let before = state.clone();
let pauli = state.single_qubit_pauli(0, MeasurementBasis::X).unwrap();
let (mask, independent) = state.coordinate_mask(&pauli.x);
assert!(!independent);
let probability = state.pauli_probability_zero(&pauli, mask, false);
let error = state
.project_active_measurement(0, MeasurementBasis::X, &pauli, mask, true, probability)
.unwrap_err();
assert!(error.contains("zero-probability"));
assert_eq!(state.coefficients, before.coefficients);
assert_eq!(state.frame_snapshot(), before.frame_snapshot());
assert_eq!(state.axes, before.axes);
assert_eq!(state.origin, before.origin);
assert_eq!(state.global_phase, before.global_phase);
}
#[test]
fn zero_probability_collapse_leaves_coefficients_unchanged() {
let mut state = ActiveState::new(1, 1);
let before = state.coefficients.clone();
let error = state
.collapse_pauli_measurement(&Pauli::identity(1), 0, true, 1.0)
.unwrap_err();
assert!(error.contains("zero-probability"));
assert_eq!(state.coefficients, before);
}
}