prism_q/circuit/dynamic/
mod.rs

1//! Programs with runtime control flow: basic blocks of ordinary circuits joined
2//! by branches on classical expressions, run once per shot.
3//!
4//! [`openqasm::parse_dynamic`](super::openqasm::parse_dynamic) builds one from
5//! source, [`DynamicProgramBuilder`] builds one directly, and
6//! [`simulate_program`](crate::sim::simulate_program) runs it.
7
8mod builder;
9mod expr;
10
11pub use builder::DynamicProgramBuilder;
12pub(crate) use expr::check_bit;
13pub use expr::{BinaryOp, ClassicalExpr, ClassicalType, ClassicalValue, UnaryOp, VarId};
14
15use super::{Circuit, ClassicalCondition, Instruction, SmallVec};
16use crate::error::{PrismError, Result};
17use crate::gates::Gate;
18
19/// Index of a basic block in a [`DynamicProgram`]. Block 0 is the entry.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
21pub struct BlockId(u32);
22
23impl BlockId {
24    /// # Panics
25    ///
26    /// Panics when `index` does not fit in 32 bits.
27    pub fn new(index: usize) -> Self {
28        Self(u32::try_from(index).expect("block index fits in 32 bits"))
29    }
30
31    pub fn index(self) -> usize {
32        self.0 as usize
33    }
34}
35
36/// A runtime classical variable. Every shot starts it at `initial`, stored
37/// through `ty`.
38#[derive(Debug, Clone, PartialEq)]
39pub struct Variable {
40    pub name: String,
41    pub ty: ClassicalType,
42    pub initial: ClassicalValue,
43}
44
45/// Rotation whose angle a dynamic program computes at runtime.
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47#[non_exhaustive]
48pub enum RotationKind {
49    Rx,
50    Ry,
51    Rz,
52    /// The phase gate `P(theta)`.
53    Phase,
54    /// `exp(-i theta Z⊗Z / 2)` on two qubits.
55    Rzz,
56}
57
58impl RotationKind {
59    pub(crate) fn gate(self, angle: f64) -> Gate {
60        match self {
61            RotationKind::Rx => Gate::Rx(angle),
62            RotationKind::Ry => Gate::Ry(angle),
63            RotationKind::Rz => Gate::Rz(angle),
64            RotationKind::Phase => Gate::P(angle),
65            RotationKind::Rzz => Gate::Rzz(angle),
66        }
67    }
68
69    fn arity(self) -> usize {
70        match self {
71            RotationKind::Rzz => 2,
72            _ => 1,
73        }
74    }
75}
76
77/// A step a block takes after its circuit, in order.
78#[derive(Debug, Clone, PartialEq)]
79#[non_exhaustive]
80pub enum Action {
81    /// Store `value` into `var`, converted to the variable's type.
82    Assign { var: VarId, value: ClassicalExpr },
83    /// Apply `kind` at the angle `angle` evaluates to, in radians.
84    Rotation {
85        kind: RotationKind,
86        targets: SmallVec<[usize; 4]>,
87        angle: ClassicalExpr,
88    },
89}
90
91/// Where control goes after a block.
92#[derive(Debug, Clone, PartialEq)]
93#[non_exhaustive]
94pub enum Terminator {
95    Jump(BlockId),
96    /// Go to `then` when `condition` is truthy (a nonzero number or `true`),
97    /// to `otherwise` when it is not.
98    Branch {
99        condition: ClassicalExpr,
100        then: BlockId,
101        otherwise: BlockId,
102    },
103    End,
104}
105
106/// One basic block: its circuit runs first, then its actions, then its
107/// terminator picks the next block.
108///
109/// `circuit` is an ordinary [`Circuit`] over the program's full width, and may
110/// carry guarded regions on classical bits. Fusion runs on it once, when the
111/// program is prepared for a backend.
112#[derive(Debug, Clone)]
113pub struct BasicBlock {
114    pub circuit: Circuit,
115    pub actions: Vec<Action>,
116    pub terminator: Terminator,
117    /// The loop this block belongs to, which the step-limit error names.
118    pub loop_name: Option<String>,
119}
120
121/// A program whose instruction count can depend on measurement outcomes: a
122/// control-flow graph of [`BasicBlock`]s plus runtime classical variables.
123///
124/// Construction validates the graph: every block target, variable, qubit, and
125/// classical bit a block names exists, and no block carries a save point.
126#[derive(Debug, Clone)]
127pub struct DynamicProgram {
128    num_qubits: usize,
129    num_classical_bits: usize,
130    variables: Vec<Variable>,
131    blocks: Vec<BasicBlock>,
132}
133
134impl DynamicProgram {
135    /// Validate and assemble a program. Each variable's `initial` value is
136    /// stored through its type, so an out-of-range integer wraps here.
137    ///
138    /// # Errors
139    ///
140    /// [`PrismError::InvalidQubit`] and [`PrismError::InvalidClassicalBit`] for
141    /// an index past the program's width, and [`PrismError::InvalidParameter`]
142    /// for anything else malformed: no blocks, a block circuit of the wrong
143    /// width, a missing block or variable, a save point, a bitwise operator on
144    /// a float, or a rotation with the wrong number of targets.
145    pub fn new(
146        num_qubits: usize,
147        num_classical_bits: usize,
148        mut variables: Vec<Variable>,
149        blocks: Vec<BasicBlock>,
150    ) -> Result<Self> {
151        if blocks.is_empty() {
152            return Err(invalid("a dynamic program needs at least one block"));
153        }
154        for variable in &mut variables {
155            variable.ty.check()?;
156            variable.initial = variable.ty.store(variable.initial);
157        }
158        let types: Vec<ClassicalType> = variables.iter().map(|variable| variable.ty).collect();
159        let check_target = |id: BlockId| {
160            if id.index() >= blocks.len() {
161                return Err(invalid(format!(
162                    "a terminator names block {} of {}",
163                    id.index(),
164                    blocks.len()
165                )));
166            }
167            Ok(())
168        };
169        for (at, block) in blocks.iter().enumerate() {
170            let circuit = &block.circuit;
171            if circuit.num_qubits != num_qubits || circuit.num_classical_bits != num_classical_bits
172            {
173                return Err(invalid(format!(
174                    "block {at} holds a circuit of {} qubits and {} bits in a program of {} and {}",
175                    circuit.num_qubits, circuit.num_classical_bits, num_qubits, num_classical_bits
176                )));
177            }
178            check_instructions(&circuit.instructions, num_qubits, num_classical_bits)?;
179            for action in &block.actions {
180                match action {
181                    Action::Assign { var, value } => {
182                        if var.index() >= variables.len() {
183                            return Err(invalid(format!(
184                                "block {at} assigns variable {} of {} declared",
185                                var.index(),
186                                variables.len()
187                            )));
188                        }
189                        value.check(&types, num_classical_bits)?;
190                    }
191                    Action::Rotation {
192                        kind,
193                        targets,
194                        angle,
195                    } => {
196                        if targets.len() != kind.arity() {
197                            return Err(PrismError::GateArity {
198                                gate: format!("{kind:?}").to_lowercase(),
199                                expected: kind.arity(),
200                                got: targets.len(),
201                            });
202                        }
203                        check_qubits(targets, num_qubits)?;
204                        if targets.len() == 2 && targets[0] == targets[1] {
205                            return Err(invalid(format!(
206                                "block {at} applies a two-qubit rotation to qubit {} twice",
207                                targets[0]
208                            )));
209                        }
210                        angle.check(&types, num_classical_bits)?;
211                    }
212                }
213            }
214            match &block.terminator {
215                Terminator::Jump(target) => check_target(*target)?,
216                Terminator::Branch {
217                    condition,
218                    then,
219                    otherwise,
220                } => {
221                    condition.check(&types, num_classical_bits)?;
222                    check_target(*then)?;
223                    check_target(*otherwise)?;
224                }
225                Terminator::End => {}
226            }
227        }
228        Ok(Self {
229            num_qubits,
230            num_classical_bits,
231            variables,
232            blocks,
233        })
234    }
235
236    pub fn num_qubits(&self) -> usize {
237        self.num_qubits
238    }
239
240    pub fn num_classical_bits(&self) -> usize {
241        self.num_classical_bits
242    }
243
244    pub fn variables(&self) -> &[Variable] {
245        &self.variables
246    }
247
248    /// Blocks in index order; block 0 is the entry.
249    pub fn blocks(&self) -> &[BasicBlock] {
250        &self.blocks
251    }
252
253    /// The program's circuit when it has no runtime control flow: one block,
254    /// no actions, and nothing after it. Such a program runs exactly as that
255    /// circuit does, through every sampling shortcut the circuit qualifies for.
256    pub fn static_circuit(&self) -> Option<&Circuit> {
257        match self.blocks.as_slice() {
258            [block] if block.actions.is_empty() && block.terminator == Terminator::End => {
259                Some(&block.circuit)
260            }
261            _ => None,
262        }
263    }
264
265    /// Every block's instructions in one circuit, with each runtime rotation
266    /// standing in at a generic angle, for the routing decisions that read a
267    /// circuit's gate set.
268    pub(crate) fn summary_circuit(&self) -> Circuit {
269        let mut summary = Circuit::new(self.num_qubits, self.num_classical_bits);
270        for block in &self.blocks {
271            summary
272                .instructions
273                .extend(block.circuit.instructions.iter().cloned());
274            for action in &block.actions {
275                if let Action::Rotation { kind, targets, .. } = action {
276                    summary.instructions.push(Instruction::Gate {
277                        gate: kind.gate(1.0),
278                        targets: targets.clone(),
279                    });
280                }
281            }
282        }
283        summary
284    }
285}
286
287fn invalid(message: impl Into<String>) -> PrismError {
288    PrismError::InvalidParameter {
289        message: message.into(),
290    }
291}
292
293fn check_qubits(qubits: &[usize], num_qubits: usize) -> Result<()> {
294    match qubits.iter().find(|&&qubit| qubit >= num_qubits) {
295        Some(&index) => Err(PrismError::InvalidQubit {
296            index,
297            register_size: num_qubits,
298        }),
299        None => Ok(()),
300    }
301}
302
303fn check_condition(condition: &ClassicalCondition, num_classical_bits: usize) -> Result<()> {
304    match condition {
305        ClassicalCondition::BitIsOne(bit) | ClassicalCondition::BitIsZero(bit) => {
306            check_bit(*bit, num_classical_bits)
307        }
308        ClassicalCondition::RegisterEquals { offset, size, .. }
309        | ClassicalCondition::RegisterNotEquals { offset, size, .. } => match size {
310            0 => Ok(()),
311            _ => check_bit(offset + size - 1, num_classical_bits),
312        },
313        ClassicalCondition::Parity { bits, .. } => bits
314            .iter()
315            .try_for_each(|&bit| check_bit(bit, num_classical_bits)),
316    }
317}
318
319fn check_instructions(
320    instructions: &[Instruction],
321    num_qubits: usize,
322    num_classical_bits: usize,
323) -> Result<()> {
324    for instruction in instructions {
325        match instruction {
326            Instruction::Gate { gate, targets } => {
327                if gate.num_qubits() != targets.len() {
328                    return Err(PrismError::GateArity {
329                        gate: gate.name().to_string(),
330                        expected: gate.num_qubits(),
331                        got: targets.len(),
332                    });
333                }
334                check_qubits(targets, num_qubits)?;
335            }
336            Instruction::Measure {
337                qubit,
338                classical_bit,
339            } => {
340                check_qubits(&[*qubit], num_qubits)?;
341                check_bit(*classical_bit, num_classical_bits)?;
342            }
343            Instruction::Reset { qubit } => check_qubits(&[*qubit], num_qubits)?,
344            Instruction::Barrier { qubits } => check_qubits(qubits, num_qubits)?,
345            Instruction::Conditional {
346                condition,
347                gate,
348                targets,
349            } => {
350                check_condition(condition, num_classical_bits)?;
351                if gate.num_qubits() != targets.len() {
352                    return Err(PrismError::GateArity {
353                        gate: gate.name().to_string(),
354                        expected: gate.num_qubits(),
355                        got: targets.len(),
356                    });
357                }
358                check_qubits(targets, num_qubits)?;
359            }
360            Instruction::Region(region) => {
361                check_condition(region.condition(), num_classical_bits)?;
362                check_instructions(region.body(), num_qubits, num_classical_bits)?;
363            }
364            Instruction::Save { label, .. } => {
365                return Err(invalid(format!(
366                    "save point `{label}` in a dynamic program, whose shots have nowhere to \
367                     return it"
368                )));
369            }
370        }
371    }
372    Ok(())
373}
374
375#[cfg(test)]
376mod tests;
prism_q/circuit/dynamic/mod.rs

prism_q/circuit/dynamic/
mod.rs
