bloq_utils/
qasm.rs

1//! Shared OpenQASM syntax for small Clifford+T components and Pauli feedback.
2//!
3//! This module parses instructions; it does not execute a circuit or depend on
4//! a quantum engine. Conditions use OpenQASM 2 register equality. Nested `if`s
5//! express conjunctions; several conditional Paulis can express XOR.
6
7use std::collections::BTreeMap;
8
9use num_traits::{CheckedAdd, CheckedMul, CheckedSub};
10use openqasm::GenericError as _;
11use openqasm::ast::{Decl, Expr, Reg, Stmt};
12use openqasm::translate::Value;
13use thiserror::Error;
14
15use crate::{Basis, PauliBasis};
16
17/// Gates accepted by the shared parser, without an execution representation.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum QasmGate {
20    /// Identity.
21    Identity,
22    /// Hadamard.
23    H,
24    /// A single-qubit Pauli.
25    Pauli(PauliBasis),
26    /// An X/Z phase in units of pi/4. Rotations have this form up to global phase.
27    Phase {
28        /// Rotation axis.
29        basis: Basis,
30        /// Signed angle in quarter turns of pi.
31        quarters: i64,
32    },
33    /// Controlled X.
34    Cx,
35    /// Controlled Z.
36    Cz,
37    /// X-basis controlled X.
38    Xcx,
39    /// Swap.
40    Swap,
41    /// Toffoli.
42    Ccx,
43    /// Controlled-controlled Z.
44    Ccz,
45}
46
47/// One parsed instruction. Indices address [`QasmProgram::qubits`] and `bits`.
48#[derive(Debug, Clone, PartialEq, Eq)]
49pub enum QasmInstruction {
50    /// A gate, optionally conditioned on a conjunction of `(bit, value)` tests.
51    Gate {
52        /// Gate kind.
53        gate: QasmGate,
54        /// Operand indices into [`QasmProgram::qubits`].
55        qubits: Vec<usize>,
56        /// Required classical bit values.
57        condition: Vec<(usize, bool)>,
58    },
59    /// A computational-basis measurement with a retained classical result.
60    Measure {
61        /// Index into [`QasmProgram::qubits`].
62        qubit: usize,
63        /// Index into [`QasmProgram::bits`].
64        bit: usize,
65    },
66    /// Reset to zero. Consumers decide which reset placements they support.
67    Reset {
68        /// Index into [`QasmProgram::qubits`].
69        qubit: usize,
70    },
71}
72
73/// Parsed registers and instructions, in declaration/program order.
74#[derive(Debug, Clone, PartialEq, Eq)]
75pub struct QasmProgram {
76    qubits: Vec<String>,
77    bits: Vec<String>,
78    instructions: Vec<QasmInstruction>,
79}
80
81impl QasmProgram {
82    /// Quantum wire names, always indexed (for example, `q[0]`).
83    pub fn qubits(&self) -> &[String] {
84        &self.qubits
85    }
86
87    /// Classical bit names, always indexed (for example, `m[0]`).
88    pub fn bits(&self) -> &[String] {
89        &self.bits
90    }
91
92    /// Instructions with barriers removed and register-wide gates expanded.
93    pub fn instructions(&self) -> &[QasmInstruction] {
94        &self.instructions
95    }
96}
97
98/// Errors in the supported OpenQASM subset.
99#[derive(Debug, Clone, PartialEq, Eq, Error)]
100pub enum QasmError {
101    /// Upstream syntax or type checking failed.
102    #[error("OpenQASM parse failed: {0}")]
103    Parse(String),
104    /// The program violates the supported component boundary.
105    #[error("invalid OpenQASM component: {0}")]
106    Boundary(String),
107    /// Register storage exceeds the supported bound.
108    #[error("too many quantum or classical register entries")]
109    TooManyQubits,
110    /// The program uses an unsupported gate or angle.
111    #[error("unsupported gate {0:?}")]
112    UnsupportedGate(String),
113}
114
115const BUILTINS: &str = "
116    opaque id q; opaque h q; opaque x q; opaque y q; opaque z q;
117    opaque s q; opaque sdg q; opaque t q; opaque tdg q;
118    opaque rx(phase) q; opaque rz(phase) q;
119    opaque cx a,b; opaque cz a,b; opaque xcx a,b; opaque swap a,b;
120    opaque ccx a,b,c; opaque ccz a,b,c;
121";
122
123#[derive(Clone, Copy)]
124struct Register {
125    offset: usize,
126    len: usize,
127}
128
129/// Parses the supported OpenQASM 2 subset.
130///
131/// Supports the usual Clifford+T gates, exact pi/4 rotations, resets, Z
132/// measurements, barriers, and `if (register == integer)` controlled X/Y/Z.
133/// Nested conditions are allowed. Classical bits are single assignment and
134/// must have been measured before use in a condition. Custom gates, decimal
135/// angles, arbitrary includes, and conditional non-Pauli gates are unsupported.
136/// `qelib1.inc` gates are built in; includes never read the filesystem.
137///
138/// # Errors
139///
140/// Returns a [`QasmError`] for unsupported syntax, invalid registers, repeated
141/// classical assignments, or a condition reading an unmeasured bit. Register
142/// storage is bounded to 65,536 quantum and 65,536 classical entries.
143/// Conditions allow at most 63 bits per compared register and 64 total bit tests.
144pub fn parse_qasm(input: &str) -> Result<QasmProgram, QasmError> {
145    let mut source = strip_comments(input)?.replace('\r', "\n");
146    // The upstream lexer treats this whole signature as one literal token.
147    if let Some((signature, rest)) = source.split_once(';')
148        && let Some(version) = signature.trim().strip_prefix("OPENQASM")
149        && version.starts_with(char::is_whitespace)
150    {
151        source = format!("OPENQASM {};{rest}", version.trim());
152    }
153    for statement in source.split(';') {
154        if let Some(include) = statement.trim().strip_prefix("include")
155            && include.trim() != "\"qelib1.inc\""
156        {
157            return Err(QasmError::Boundary(
158                "only the built-in qelib1.inc include is supported".into(),
159            ));
160        }
161    }
162    if source.contains('{') || source.contains('}') {
163        return Err(QasmError::Boundary(
164            "custom gate declarations are not supported".into(),
165        ));
166    }
167    let mut cache = openqasm::SourceCache::new();
168    let mut parser =
169        openqasm::Parser::new(&mut cache).with_file_policy(openqasm::parser::FilePolicy::Ignore);
170    parser.parse_source::<String>(source, None);
171    parser.parse_source::<String>(BUILTINS.into(), None);
172    let ast = parser
173        .done()
174        .to_errors()
175        .map_err(|error| QasmError::Parse(error.to_string()))?;
176    let mut program = QasmProgram {
177        qubits: Vec::new(),
178        bits: Vec::new(),
179        instructions: Vec::new(),
180    };
181    let mut quantum = BTreeMap::new();
182    let mut classical = BTreeMap::new();
183    for declaration in &ast.decls {
184        match &**declaration {
185            Decl::QReg { reg } => register(reg, &mut quantum, &mut program.qubits)?,
186            Decl::CReg { reg } => register(reg, &mut classical, &mut program.bits)?,
187            _ => {}
188        }
189    }
190    // Upstream type checking shifts `1_u64 << register_width` without a
191    // bound. Check condition widths first so malformed input cannot panic.
192    for declaration in &ast.decls {
193        if let Decl::Stmt(statement) = &**declaration {
194            let mut statement: &Stmt = statement;
195            let mut tests = 0;
196            while let Stmt::Conditional { reg, then, .. } = statement {
197                let width = classical.get(reg.name.as_str()).map_or(0, |register| {
198                    if reg.index.is_some() { 1 } else { register.len }
199                });
200                tests += width;
201                if width >= 64 || tests > 64 {
202                    return Err(QasmError::Boundary(
203                        "conditions allow at most 63 bits per register and 64 total bit tests"
204                            .into(),
205                    ));
206                }
207                statement = then;
208            }
209        }
210    }
211    ast.type_check()
212        .to_errors()
213        .map_err(|error| QasmError::Parse(error.to_string()))?;
214
215    let mut measured = vec![false; program.bits.len()];
216    for declaration in &ast.decls {
217        if let Decl::Stmt(statement) = &**declaration {
218            parse_statement(
219                statement,
220                &quantum,
221                &classical,
222                &mut measured,
223                &[],
224                &mut program.instructions,
225            )?;
226        }
227    }
228    Ok(program)
229}
230
231fn register(
232    reg: &Reg,
233    registers: &mut BTreeMap<String, Register>,
234    names: &mut Vec<String>,
235) -> Result<(), QasmError> {
236    let len = usize::try_from(reg.index.unwrap_or(1)).map_err(|_| QasmError::TooManyQubits)?;
237    if len == 0 {
238        return Err(QasmError::Boundary("register size must be nonzero".into()));
239    }
240    if len > 65_536 || names.len() > 65_536 - len {
241        return Err(QasmError::TooManyQubits);
242    }
243    registers.insert(
244        reg.name.to_string(),
245        Register {
246            offset: names.len(),
247            len,
248        },
249    );
250    names.extend((0..len).map(|index| format!("{}[{index}]", reg.name)));
251    Ok(())
252}
253
254fn operands(reg: &Reg, registers: &BTreeMap<String, Register>) -> Vec<usize> {
255    let register = registers[reg.name.as_str()];
256    match reg.index {
257        Some(index) => vec![register.offset + index as usize],
258        None => (register.offset..register.offset + register.len).collect(),
259    }
260}
261
262fn parse_statement(
263    statement: &Stmt,
264    quantum: &BTreeMap<String, Register>,
265    classical: &BTreeMap<String, Register>,
266    measured: &mut [bool],
267    condition: &[(usize, bool)],
268    output: &mut Vec<QasmInstruction>,
269) -> Result<(), QasmError> {
270    match statement {
271        Stmt::Conditional { reg, val, then } => {
272            let bits = operands(reg, classical);
273            let mut condition = condition.to_vec();
274            for (index, bit) in bits.into_iter().enumerate() {
275                if !measured[bit] {
276                    return Err(QasmError::Boundary(format!(
277                        "condition reads unmeasured bit {}[{index}]",
278                        reg.name
279                    )));
280                }
281                condition.push((bit, **val & (1_u64 << index) != 0));
282            }
283            parse_statement(then, quantum, classical, measured, &condition, output)
284        }
285        Stmt::Gate { name, params, args } => {
286            let name = name.as_str();
287            let phase = |basis| {
288                let value = exact_value(&params[0]).ok_or_else(|| {
289                    QasmError::UnsupportedGate(format!(
290                        "{name}: rotation must be an exact multiple of pi/4 using integer arithmetic and pi"
291                    ))
292                })?;
293                let denominator = *value.b.denom();
294                let quarters = (*value.b.numer()).checked_mul(4);
295                if *value.a.numer() != 0
296                    || 4 % denominator != 0
297                    || quarters.is_none_or(|value| value % denominator != 0)
298                {
299                    return Err(QasmError::UnsupportedGate(format!(
300                        "{name}: rotation must be an exact multiple of pi/4"
301                    )));
302                }
303                Ok(QasmGate::Phase {
304                    basis,
305                    quarters: quarters.expect("checked above") / denominator,
306                })
307            };
308            let gate = match name {
309                "id" => QasmGate::Identity,
310                "h" => QasmGate::H,
311                "x" => QasmGate::Pauli(PauliBasis::X),
312                "y" => QasmGate::Pauli(PauliBasis::Y),
313                "z" => QasmGate::Pauli(PauliBasis::Z),
314                "s" => QasmGate::Phase {
315                    basis: Basis::Z,
316                    quarters: 2,
317                },
318                "sdg" => QasmGate::Phase {
319                    basis: Basis::Z,
320                    quarters: -2,
321                },
322                "t" => QasmGate::Phase {
323                    basis: Basis::Z,
324                    quarters: 1,
325                },
326                "tdg" => QasmGate::Phase {
327                    basis: Basis::Z,
328                    quarters: -1,
329                },
330                "rx" => phase(Basis::X)?,
331                "rz" => phase(Basis::Z)?,
332                "cx" => QasmGate::Cx,
333                "cz" => QasmGate::Cz,
334                "xcx" => QasmGate::Xcx,
335                "swap" => QasmGate::Swap,
336                "ccx" => QasmGate::Ccx,
337                "ccz" => QasmGate::Ccz,
338                _ => return Err(QasmError::UnsupportedGate(name.to_string())),
339            };
340            if !condition.is_empty() && !matches!(gate, QasmGate::Pauli(_) | QasmGate::Identity) {
341                return Err(QasmError::Boundary(
342                    "only Pauli gates may be conditional".into(),
343                ));
344            }
345            let args = args
346                .iter()
347                .map(|reg| operands(reg, quantum))
348                .collect::<Vec<_>>();
349            append_gate(gate, &args, condition, output)
350        }
351        Stmt::CX { copy, xor } => {
352            if !condition.is_empty() {
353                return Err(QasmError::Boundary(
354                    "only Pauli gates may be conditional".into(),
355                ));
356            }
357            append_gate(
358                QasmGate::Cx,
359                &[operands(copy, quantum), operands(xor, quantum)],
360                condition,
361                output,
362            )
363        }
364        Stmt::Measure { from, to } => {
365            if !condition.is_empty() {
366                return Err(QasmError::Boundary(
367                    "conditional measurements are unsupported".into(),
368                ));
369            }
370            let from = operands(from, quantum);
371            let to = operands(to, classical);
372            if from.len() != to.len() {
373                return Err(QasmError::Boundary(
374                    "measurement register widths must match".into(),
375                ));
376            }
377            for (qubit, bit) in from.into_iter().zip(to) {
378                if std::mem::replace(&mut measured[bit], true) {
379                    return Err(QasmError::Boundary(
380                        "classical bits must be assigned only once".into(),
381                    ));
382                }
383                output.push(QasmInstruction::Measure { qubit, bit });
384            }
385            Ok(())
386        }
387        Stmt::Reset { reg } => {
388            if !condition.is_empty() {
389                return Err(QasmError::Boundary(
390                    "conditional resets are unsupported".into(),
391                ));
392            }
393            output.extend(
394                operands(reg, quantum)
395                    .into_iter()
396                    .map(|qubit| QasmInstruction::Reset { qubit }),
397            );
398            Ok(())
399        }
400        Stmt::Barrier { .. } => Ok(()),
401        Stmt::U { .. } => Err(QasmError::UnsupportedGate("U".into())),
402    }
403}
404
405fn append_gate(
406    gate: QasmGate,
407    operands: &[Vec<usize>],
408    condition: &[(usize, bool)],
409    output: &mut Vec<QasmInstruction>,
410) -> Result<(), QasmError> {
411    let width = operands.iter().map(Vec::len).max().unwrap_or(0);
412    for index in 0..width {
413        let qubits = operands
414            .iter()
415            .map(|arg| arg[if arg.len() == 1 { 0 } else { index }])
416            .collect::<Vec<_>>();
417        if qubits
418            .iter()
419            .enumerate()
420            .any(|(index, qubit)| qubits[..index].contains(qubit))
421        {
422            return Err(QasmError::Boundary("gate operands must be distinct".into()));
423        }
424        output.push(QasmInstruction::Gate {
425            gate,
426            qubits,
427            condition: condition.to_vec(),
428        });
429    }
430    Ok(())
431}
432
433// Keep every intermediate exactly a + b*pi, before any downstream conversion.
434fn exact_value(expr: &Expr) -> Option<Value> {
435    match expr {
436        Expr::Int(value) => Some(Value::int(i64::try_from(*value).ok()?)),
437        Expr::Pi => Some(Value::PI),
438        Expr::Neg(value) => exact_value(value)?.checked_neg(),
439        Expr::Add(left, right)
440        | Expr::Sub(left, right)
441        | Expr::Mul(left, right)
442        | Expr::Div(left, right) => {
443            let left = exact_value(left)?;
444            let right = exact_value(right)?;
445            match expr {
446                Expr::Add(..) => Some(Value {
447                    a: left.a.checked_add(&right.a)?,
448                    b: left.b.checked_add(&right.b)?,
449                }),
450                Expr::Sub(..) => Some(Value {
451                    a: left.a.checked_sub(&right.a)?,
452                    b: left.b.checked_sub(&right.b)?,
453                }),
454                Expr::Mul(..) if *left.b.numer() == 0 || *right.b.numer() == 0 => Some(Value {
455                    a: left.a.checked_mul(&right.a)?,
456                    b: left
457                        .a
458                        .checked_mul(&right.b)?
459                        .checked_add(&left.b.checked_mul(&right.a)?)?,
460                }),
461                Expr::Div(..) if *right.b.numer() == 0 => left.checked_div(right),
462                _ => None,
463            }
464        }
465        _ => None,
466    }
467}
468
469fn strip_comments(input: &str) -> Result<String, QasmError> {
470    let mut output = String::with_capacity(input.len());
471    let mut chars = input.chars().peekable();
472    while let Some(character) = chars.next() {
473        if character != '/' {
474            output.push(character);
475            continue;
476        }
477        match chars.peek().copied() {
478            Some('/') => {
479                chars.next();
480                for next in chars.by_ref() {
481                    if matches!(next, '\n' | '\r') {
482                        output.push('\n');
483                        break;
484                    }
485                }
486            }
487            Some('*') => {
488                chars.next();
489                let mut previous = '\0';
490                let mut closed = false;
491                for next in chars.by_ref() {
492                    if previous == '*' && next == '/' {
493                        closed = true;
494                        break;
495                    }
496                    previous = next;
497                }
498                if !closed {
499                    return Err(QasmError::Boundary("unterminated block comment".into()));
500                }
501                output.push(' ');
502            }
503            _ => output.push(character),
504        }
505    }
506    Ok(output)
507}
508
509#[cfg(test)]
510mod tests {
511    use super::*;
512
513    #[test]
514    fn measurements_and_nested_register_conditions_keep_their_identity() {
515        let source = "OPENQASM 2.0; qreg q[4]; creg c[2]; creg other[1];
516            reset q[2]; cx q[0],q[2]; cx q[1],q[2]; measure q[2] -> c[0];
517            measure q[3] -> c[1]; measure q[1] -> other[0];
518            if(c==3) if(other==0) y q[0];";
519        let parsed = parse_qasm(source).unwrap();
520        assert_eq!(parsed.bits(), ["c[0]", "c[1]", "other[0]"]);
521        assert!(
522            matches!(parsed.instructions().last(), Some(QasmInstruction::Gate {
523            gate: QasmGate::Pauli(PauliBasis::Y), qubits, condition
524        }) if qubits == &[0] && condition == &[(0,true), (1,true), (2,false)])
525        );
526        for body in [
527            "if(c==1) x q[0];",                      // Unmeasured condition.
528            "measure q[0] -> c; measure q[1] -> c;", // Overwritten result.
529            "measure q[0] -> c; if(c==1) h q[1];",
530            "cx q[0],q[0];",
531            "measure q[0] -> c; if(c==2) x q[1];",
532            "include \"unknown.inc\";",
533        ] {
534            assert!(
535                parse_qasm(&format!("OPENQASM 2.0; qreg q[2]; creg c[1]; {body}")).is_err(),
536                "{body}"
537            );
538        }
539        for width in [64, 65, 65_536] {
540            parse_qasm(&format!(
541                "OPENQASM 2.0; qreg q[1]; creg c[{width}]; if(c==1) x q;"
542            ))
543            .unwrap_err();
544        }
545        parse_qasm("OPENQASM 2.0; qreg q[63]; creg c[63]; measure q -> c; if(c==1) x q[0];")
546            .unwrap();
547    }
548
549    #[test]
550    fn rotations_are_checked_before_lossy_conversion() {
551        for angle in [
552            "100000000",
553            "0.7853982",
554            "pi/8",
555            "pi/(4+0.00000001)",
556            "sin(pi/4)",
557            "pi*pi-pi*pi+pi/4",
558            "9223372036854775807+1",
559        ] {
560            let source = format!("OPENQASM 2.0; qreg q[1]; rz({angle}) q;");
561            assert!(
562                matches!(parse_qasm(&source), Err(QasmError::UnsupportedGate(_))),
563                "{angle}"
564            );
565        }
566        for (angle, quarters) in [
567            ("pi/4", 1),
568            ("-3*pi/4", -3),
569            ("(2+1)*pi/(2*2)", 3),
570            ("(1-1)+pi/4", 1),
571            ("0", 0),
572        ] {
573            let parsed = parse_qasm(&format!("OPENQASM 2.0; qreg q[2]; rx({angle}) q;")).unwrap();
574            assert_eq!(parsed.instructions().len(), 2);
575            for instruction in parsed.instructions() {
576                assert!(
577                    matches!(instruction, QasmInstruction::Gate { gate: QasmGate::Phase { basis: Basis::X, quarters: actual }, .. } if *actual == quarters)
578                );
579            }
580        }
581        assert!(matches!(
582            parse_qasm("OPENQASM 2.0; qreg q[1]; U(100000000,0,0) q;"),
583            Err(QasmError::UnsupportedGate(_))
584        ));
585    }
586}
bloq_utils/qasm.rs

bloq_utils/
qasm.rs
