use std::collections::BTreeMap;
use std::fmt;
use crate::AcceptedProgram;
use crate::ir::{ClassicalPhi, QuantumPhi, RawOp, SingleGate, WireId};
mod accepted {
pub trait Sealed {}
impl Sealed for crate::AcceptedProgram {}
}
pub trait ExecutableProgram: accepted::Sealed {
fn execution_view(&self) -> &crate::ir::RawProgram;
}
impl ExecutableProgram for AcceptedProgram {
fn execution_view(&self) -> &crate::ir::RawProgram {
self.raw()
}
}
mod circuit;
mod state;
use circuit::{apply_gate, run_circuit, run_protected_use, run_qif_arm};
use state::{Complex, Component};
mod sampling;
pub use sampling::{RandomSource, Sample, SampleError, SampleLimits, SplitMix64, sample_closed};
pub const MAX_SIMULATED_QUBITS: usize = 20;
const AUXILIARY_LEAKAGE_ALARM: f64 = 1e-12;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct SimulationLimits {
pub max_qubits: usize,
pub max_components: usize,
pub max_amplitude_cells: usize,
pub max_execution_steps: usize,
}
impl Default for SimulationLimits {
fn default() -> Self {
Self {
max_qubits: 16,
max_components: 65_536,
max_amplitude_cells: 1 << 20,
max_execution_steps: 1_000_000,
}
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum SimulationError {
NotClosed(&'static str),
DimensionLimit { required: usize, max: usize },
ComponentLimit { max: usize },
AmplitudeLimit { required: usize, max: usize },
ExecutionLimit { max: usize },
InconsistentVerifiedIr(&'static str),
}
impl fmt::Display for SimulationError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::NotClosed(reason) => write!(f, "a closed program is required: {reason}"),
Self::DimensionLimit { required, max } => {
write!(f, "simulation requires {required} qubits; limit is {max}")
}
Self::ComponentLimit { max } => {
write!(f, "simulation exceeds the {max}-component ensemble limit")
}
Self::AmplitudeLimit { required, max } => {
write!(
f,
"simulation requires {required} amplitude cells; limit is {max}"
)
}
Self::ExecutionLimit { max } => {
write!(f, "simulation exceeds the {max}-step execution limit")
}
Self::InconsistentVerifiedIr(reason) => {
write!(f, "verified IR is inconsistent during simulation: {reason}")
}
}
}
}
impl std::error::Error for SimulationError {}
struct ExecutionBudget {
copied_entries: usize,
remaining: usize,
max: usize,
}
impl ExecutionBudget {
fn charge_copies(&mut self, entries: usize) -> Result<(), SimulationError> {
self.charge(entries)?;
self.copied_entries += entries;
Ok(())
}
fn charge(&mut self, amount: usize) -> Result<(), SimulationError> {
self.remaining = self
.remaining
.checked_sub(amount)
.ok_or(SimulationError::ExecutionLimit { max: self.max })?;
Ok(())
}
}
fn check_dimension(required: usize, limits: SimulationLimits) -> Result<(), SimulationError> {
let max = limits.max_qubits.min(MAX_SIMULATED_QUBITS);
if required > max {
Err(SimulationError::DimensionLimit { required, max })
} else {
Ok(())
}
}
fn check_components(required: usize, limits: SimulationLimits) -> Result<(), SimulationError> {
if required > limits.max_components {
Err(SimulationError::ComponentLimit {
max: limits.max_components,
})
} else {
Ok(())
}
}
fn check_amplitude_cells(required: usize, limits: SimulationLimits) -> Result<(), SimulationError> {
if required > limits.max_amplitude_cells {
Err(SimulationError::AmplitudeLimit {
required,
max: limits.max_amplitude_cells,
})
} else {
Ok(())
}
}
fn bit(index: usize, axis: usize) -> bool {
(index >> axis) & 1 != 0
}
fn local_label(index: usize, axes: &[usize]) -> usize {
axes.iter().enumerate().fold(0, |label, (place, axis)| {
label | (usize::from(bit(index, *axis)) << place)
})
}
fn relabel_branch(
mut component: Component,
then_arm: bool,
quantum_phis: &[QuantumPhi],
classical_phis: &[ClassicalPhi],
budget: &mut ExecutionBudget,
) -> Result<Component, SimulationError> {
budget.charge_copies(classical_phis.len())?;
budget.charge_copies(quantum_phis.len())?;
for phi in quantum_phis {
budget.charge_copies(phi.output_wires.len())?;
budget.charge_copies(phi.output_wires.len())?;
}
let mut wire_renames = BTreeMap::new();
let mut outputs = Vec::with_capacity(quantum_phis.len());
for phi in quantum_phis {
let old_token = if then_arm {
phi.then_token
} else {
phi.else_token
};
let old_wires = component.take(old_token)?;
if old_wires.len() != phi.output_wires.len() {
return Err(SimulationError::InconsistentVerifiedIr("phi shape differs"));
}
for (old, new) in old_wires.iter().zip(&phi.output_wires) {
wire_renames.insert(*old, *new);
}
outputs.push((phi.output, phi.output_wires.clone()));
}
for axis in &mut component.axes {
if let Some(new) = wire_renames.get(axis) {
*axis = *new;
}
}
for (token, wires) in outputs {
component.tokens.insert(token, wires);
}
for phi in classical_phis {
let old = if then_arm { phi.then_id } else { phi.else_id };
let value = component.classical(old)?;
component.classical.insert(phi.output, value);
}
Ok(component)
}
fn execute_op(
mut component: Component,
operation: &RawOp,
limits: SimulationLimits,
budget: &mut ExecutionBudget,
) -> Result<Vec<Component>, SimulationError> {
budget.charge(1)?;
match operation {
RawOp::CertifiedCompute {
source,
source_out,
ancilla_wires,
function,
use_steps,
..
} => {
let wires = component.take(*source)?;
let data_axes = component.positions(&wires)?;
let auxiliary = ancilla_wires[0];
component.add_zero_wire(auxiliary, limits)?;
let aux_axis = component.position(auxiliary)?;
let compute = |state: &mut Component| {
let mut output = vec![Complex::ZERO; state.amplitudes.len()];
for (index, amplitude) in state.amplitudes.iter().copied().enumerate() {
let value = usize::from(function[local_label(index, &data_axes)]);
output[index ^ (value << aux_axis)] = amplitude;
}
state.amplitudes = output;
};
compute(&mut component);
let mut axes = data_axes.clone();
axes.push(aux_axis);
run_circuit(&mut component, &axes, use_steps, budget)?;
compute(&mut component);
component = component.remove_certified_zero(auxiliary, budget)?;
component.tokens.insert(*source_out, wires);
}
RawOp::ApplyUnitary {
input,
output,
steps,
} => {
let wires = component.take(*input)?;
let axes = component.positions(&wires)?;
run_circuit(&mut component, &axes, steps, budget)?;
component.tokens.insert(*output, wires);
}
RawOp::Init0 { output, wire } => {
component.add_zero_wire(*wire, limits)?;
component.tokens.insert(*output, vec![*wire]);
}
RawOp::Gate {
gate,
input,
output,
} => {
let wires = component.take(*input)?;
let axis = component.position(wires[0])?;
apply_gate(&mut component.amplitudes, axis, *gate, |_| true);
component.tokens.insert(*output, wires);
}
RawOp::Cnot {
control,
target,
control_out,
target_out,
} => {
let control_wires = component.take(*control)?;
let target_wires = component.take(*target)?;
let control_axis = component.position(control_wires[0])?;
let target_axis = component.position(target_wires[0])?;
apply_gate(
&mut component.amplitudes,
target_axis,
SingleGate::X,
|index| bit(index, control_axis),
);
component.tokens.insert(*control_out, control_wires);
component.tokens.insert(*target_out, target_wires);
}
RawOp::Toffoli {
control_a,
control_b,
target,
control_a_out,
control_b_out,
target_out,
} => {
let first = component.take(*control_a)?;
let second = component.take(*control_b)?;
let target_wires = component.take(*target)?;
let first_axis = component.position(first[0])?;
let second_axis = component.position(second[0])?;
let target_axis = component.position(target_wires[0])?;
apply_gate(
&mut component.amplitudes,
target_axis,
SingleGate::X,
|index| bit(index, first_axis) && bit(index, second_axis),
);
component.tokens.insert(*control_a_out, first);
component.tokens.insert(*control_b_out, second);
component.tokens.insert(*target_out, target_wires);
}
RawOp::QuantumIf {
control,
target,
control_out,
target_out,
zero_ops,
one_ops,
} => {
budget.charge(zero_ops.len())?;
budget.charge(one_ops.len())?;
let control_wires = component.take(*control)?;
let target_wires = component.take(*target)?;
let control_axis = component.position(control_wires[0])?;
let target_axes = component.positions(&target_wires)?;
run_qif_arm(&mut component, &target_axes, control_axis, false, zero_ops);
run_qif_arm(&mut component, &target_axes, control_axis, true, one_ops);
component.tokens.insert(*control_out, control_wires);
component.tokens.insert(*target_out, target_wires);
}
RawOp::Split {
input,
left,
right,
left_bits,
} => {
let wires = component.take(*input)?;
let split = usize::from(*left_bits);
component.tokens.insert(*left, wires[..split].to_vec());
component.tokens.insert(*right, wires[split..].to_vec());
}
RawOp::Join {
left,
right,
output,
} => {
let mut wires = component.take(*left)?;
wires.extend(component.take(*right)?);
component.tokens.insert(*output, wires);
}
RawOp::LiftBasis {
input,
output,
output_wires,
table,
} => {
let input_wires = component.take(*input)?;
let input_axes = component.positions(&input_wires)?;
let added = output_wires.len() - input_wires.len();
check_dimension(component.axes.len() + added, limits)?;
let old_len = component.amplitudes.len();
let old_axis_count = component.axes.len();
check_amplitude_cells(old_len << added, limits)?;
let mut new_amplitudes = vec![Complex::ZERO; old_len << added];
let output_axes: Vec<_> = output_wires
.iter()
.enumerate()
.map(|(place, wire)| {
if place < input_wires.len() {
component.position(*wire)
} else {
Ok(old_axis_count + place - input_wires.len())
}
})
.collect::<Result<_, _>>()?;
for (old_index, amplitude) in component.amplitudes.iter().copied().enumerate() {
let label = local_label(old_index, &input_axes);
let mapped = usize::from(table[label]);
let mut new_index = old_index;
for (place, axis) in output_axes.iter().copied().enumerate() {
let mask = 1usize << axis;
if bit(mapped, place) {
new_index |= mask;
} else {
new_index &= !mask;
}
}
new_amplitudes[new_index] += amplitude;
}
component
.axes
.extend_from_slice(&output_wires[input_wires.len()..]);
component.amplitudes = new_amplitudes;
component.tokens.insert(*output, output_wires.clone());
}
RawOp::MeasureZ { input, output } => {
let wires = component.take(*input)?;
let mut outcomes = Vec::with_capacity(2);
for outcome in [false, true] {
let mut branch = component.project_remove(wires[0], outcome, budget)?;
if branch.weight() > 0.0 {
branch.classical.insert(*output, outcome);
outcomes.push(branch);
}
}
return Ok(outcomes);
}
RawOp::Reset {
input,
output,
fresh_wire,
} => {
let wires = component.take(*input)?;
let mut branches = Vec::with_capacity(2);
for outcome in [false, true] {
let mut branch = component.project_remove(wires[0], outcome, budget)?;
if branch.weight() > 0.0 {
branch.add_zero_wire(*fresh_wire, limits)?;
branch.tokens.insert(*output, vec![*fresh_wire]);
branches.push(branch);
}
}
return Ok(branches);
}
RawOp::Discard { input } => {
let wires = component.take(*input)?;
let mut branches = vec![component];
for wire in wires {
branches = map_ensemble(branches, limits, |branch, available| {
let mut next = Vec::new();
for outcome in [false, true] {
let projected = branch.project_remove(wire, outcome, budget)?;
if projected.weight() > 0.0 {
next.push(projected);
check_components(next.len(), available)?;
}
}
Ok(next)
})?;
}
return Ok(branches);
}
RawOp::ClassicalConst { value, output } => {
component.classical.insert(*output, *value);
}
RawOp::ClassicalNot { input, output } => {
let value = !component.classical(*input)?;
component.classical.insert(*output, value);
}
RawOp::ClassicalXor {
left,
right,
output,
} => {
let value = component.classical(*left)? ^ component.classical(*right)?;
component.classical.insert(*output, value);
}
RawOp::ClassicalAnd {
left,
right,
output,
} => {
let value = component.classical(*left)? & component.classical(*right)?;
component.classical.insert(*output, value);
}
RawOp::ClassicalBranch {
condition,
then_ops,
else_ops,
quantum_phis,
classical_phis,
} => {
let then_arm = component.classical(*condition)?;
let arm = if then_arm { then_ops } else { else_ops };
let result = execute_ops(vec![component], arm, limits, budget)?;
return result
.into_iter()
.map(|branch| {
relabel_branch(branch, then_arm, quantum_phis, classical_phis, budget)
})
.collect();
}
RawOp::ComputeUseUncompute {
source,
source_out,
targets,
ancilla_wires,
function,
use_ops,
} => {
budget.charge(use_ops.len())?;
check_dimension(component.axes.len() + ancilla_wires.len(), limits)?;
let source_wires = component.take(*source)?;
let source_axes = component.positions(&source_wires)?;
let mut target_wires = Vec::with_capacity(targets.len());
for target in targets {
let wires = component.take(target.input)?;
target_wires.push(wires[0]);
}
run_protected_use(
&mut component,
&source_axes,
&target_wires,
function,
use_ops,
)?;
component.tokens.insert(*source_out, source_wires);
for (target, wire) in targets.iter().zip(target_wires) {
component.tokens.insert(target.output, vec![wire]);
}
}
}
Ok(vec![component])
}
fn map_ensemble(
ensemble: Vec<Component>,
limits: SimulationLimits,
mut execute: impl FnMut(Component, SimulationLimits) -> Result<Vec<Component>, SimulationError>,
) -> Result<Vec<Component>, SimulationError> {
let mut pending_cells = ensemble
.iter()
.fold(0usize, |sum, c| sum.saturating_add(c.amplitudes.len()));
let mut pending_count = ensemble.len();
check_amplitude_cells(pending_cells, limits)?;
check_components(pending_count, limits)?;
let mut next = Vec::new();
let mut next_cells = 0usize;
for component in ensemble {
pending_cells -= component.amplitudes.len();
pending_count -= 1;
let available = SimulationLimits {
max_amplitude_cells: limits.max_amplitude_cells - pending_cells - next_cells,
max_components: limits.max_components - pending_count - next.len(),
..limits
};
let successors = execute(component, available).map_err(|error| match error {
SimulationError::AmplitudeLimit { required, .. } => SimulationError::AmplitudeLimit {
required: required
.saturating_add(pending_cells)
.saturating_add(next_cells),
max: limits.max_amplitude_cells,
},
SimulationError::ComponentLimit { .. } => SimulationError::ComponentLimit {
max: limits.max_components,
},
error => error,
})?;
for successor in successors {
next_cells = next_cells.saturating_add(successor.amplitudes.len());
check_amplitude_cells(next_cells.saturating_add(pending_cells), limits)?;
check_components(
next.len().saturating_add(pending_count).saturating_add(1),
limits,
)?;
next.push(successor);
}
}
Ok(next)
}
fn execute_ops(
mut ensemble: Vec<Component>,
operations: &[RawOp],
limits: SimulationLimits,
budget: &mut ExecutionBudget,
) -> Result<Vec<Component>, SimulationError> {
for operation in operations {
ensemble = map_ensemble(ensemble, limits, |component, available| {
execute_op(component, operation, available, budget)
})?;
}
Ok(ensemble)
}
pub fn run_closed(
program: &(impl ExecutableProgram + ?Sized),
limits: SimulationLimits,
) -> Result<BTreeMap<Vec<bool>, f64>, SimulationError> {
let raw = program.execution_view();
if !raw.quantum_inputs.is_empty() {
return Err(SimulationError::NotClosed("quantum inputs are present"));
}
if !raw.classical_inputs.is_empty() {
return Err(SimulationError::NotClosed("classical inputs are present"));
}
if !raw.quantum_outputs.is_empty() {
return Err(SimulationError::NotClosed("quantum outputs are present"));
}
check_components(1, limits)?;
check_amplitude_cells(1, limits)?;
let mut budget = ExecutionBudget {
copied_entries: 0,
remaining: limits.max_execution_steps,
max: limits.max_execution_steps,
};
let ensemble = execute_ops(
vec![Component::vacuum()],
&raw.operations,
limits,
&mut budget,
)?;
let mut probabilities = BTreeMap::new();
for component in ensemble {
if !component.tokens.is_empty() || !component.axes.is_empty() {
return Err(SimulationError::InconsistentVerifiedIr(
"live quantum output remains",
));
}
let outcome = raw
.classical_outputs
.iter()
.map(|id| component.classical(*id))
.collect::<Result<Vec<_>, _>>()?;
*probabilities.entry(outcome).or_insert(0.0) += component.weight();
}
Ok(probabilities)
}
#[cfg(test)]
mod tests;