💻 computer science

A Graded Modal Type Theory for Pulse Schedules

This paper introduces GRAMPUS, a graded modal type theory that uses temporal grades to formally specify and reason about quantum pulse schedules, providing both categorical and syntactic models to establish its soundness and completeness.

Original authors: Robin Adams, Jean-Philippe Bernardy, Lorenzo Perticone, Jeremy Pope

Published 2026-03-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Robin Adams, Jean-Philippe Bernardy, Lorenzo Perticone, Jeremy Pope

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive, invisible orchestra. Your musicians are qubits (the tiny bits of information in a quantum computer), and your baton is a series of microwave pulses.

In the world of quantum computing, we usually write down the music as a "circuit diagram"—a picture showing which notes (gates) happen and in what order. But a real quantum computer doesn't read pictures; it needs a very specific, timed list of instructions: "At exactly 10 nanoseconds, send a pulse to Channel A. At 15 nanoseconds, send a pulse to Channel B."

This list is called a Pulse Schedule.

The problem is that writing these schedules by hand is like trying to write a symphony by counting every single second of silence and sound. It's messy, hard to check for errors, and if you get the timing wrong by a fraction of a nanosecond, the whole song falls apart.

This paper introduces a new language called GRAMPUS (which stands for GRAded Modal type theory for PUlse Schedules) to solve this problem. Here is how it works, explained simply:

1. The "Time-Traveling" Variables

In normal programming, if you say x = 5, you just mean "x is 5." In GRAMPUS, variables carry a time stamp with them.

Think of it like a delivery service:

Normal Variable: "Here is a package."
GRAMPUS Variable: "Here is a package that will arrive 50 seconds from now."
Another GRAMPUS Variable: "Here is a package that arrived 75 seconds ago."

The authors call these "graded" variables. The number (the grade) tells the computer exactly when a piece of data becomes available.

If you have a variable x : 50 Q1, it means "Qubit 1's state is ready in 50 nanoseconds."
If you have y : -75 Q2, it means "Qubit 2's state was ready 75 nanoseconds ago."

This allows the language to naturally handle the fact that quantum gates take time to happen. If a gate takes 100 nanoseconds to run, the language forces you to acknowledge that the inputs had to be prepared 100 nanoseconds before the gate started.

2. The "Box" and the "Delay"

The language has two special tools to manage this time:

The Box: Imagine putting a task in a time capsule. If you say box 100 (do something), you are saying, "This whole operation will take 100 nanoseconds to complete, and the result won't be ready until then."
The Delay: Sometimes you just need to wait. The delay command is like hitting the "pause" button on a video. It tells the hardware, "Don't send any signal for these 10 nanoseconds." In a real quantum computer, doing nothing is actually very important because qubits are fragile; if you don't control them, they lose their energy (decohere).

3. The "Perfect Translator" (The Compiler)

The paper proves that GRAMPUS is a "perfect translator."

Imagine you have a recipe (the quantum circuit) and a chef (the compiler).

The Recipe: "Mix flour, then bake for 30 minutes."
The Chef's Job: Turn that into a specific timeline: "Preheat oven at 12:00. Put cake in at 12:05. Take out at 12:35."

GRAMPUS ensures that if you write a recipe using its strict time rules, the resulting timeline (the pulse schedule) is guaranteed to be correct. The authors proved mathematically that if you follow the rules of GRAMPUS, the physical machine will perform exactly the math you intended, no more and no less.

4. Why This Matters (The "Commuting Square")

The paper uses a fancy math diagram (a "commuting square") to explain the goal. Think of it like this:

Path A: You write a circuit $\rightarrow$ Translate it to a pulse schedule $\rightarrow$ Run it on the machine.
Path B: You write a circuit $\rightarrow$ Translate it directly to the math (the "unitary operator") that describes what the circuit should do.

The paper proves that Path A and Path B lead to the exact same result.

This is huge because it means we can build a formally verified compiler. Instead of hoping our code works, we can mathematically prove that the microwave pulses we send to the quantum chip will do exactly what the quantum algorithm requires.

Summary Analogy

Think of a quantum computer as a high-speed train network.

The Circuit is the map of the stations.
The Pulse Schedule is the train timetable.
GRAMPUS is a new way of writing the timetable where every train car is labeled with its exact arrival and departure time.

Before GRAMPUS, writing the timetable was like guessing. You might say, "Train A leaves, then Train B leaves." But you didn't know if Train B would arrive at the right station before Train A needed to switch tracks.

With GRAMPUS, the language forces you to say, "Train A leaves at 10:00 and arrives at 10:05. Train B must leave at 10:04 to arrive at 10:09." Because the language enforces these rules, the "train network" (the quantum computer) never crashes, and the passengers (the quantum data) always arrive safely at their destination.

In short: GRAMPUS is a programming language that treats time as a first-class citizen, ensuring that the complex, time-sensitive instructions for quantum computers are written correctly, verified mathematically, and executed perfectly.

1. Problem Statement

Quantum computing operations are typically defined via quantum circuits, which have well-understood semantics (unitary operators). However, to execute these circuits on physical hardware (specifically superconducting qubits), the abstract circuit must be compiled into pulse schedules. A pulse schedule is a precise specification of microwave control signals sent to input channels at specific times.

Current languages for describing pulse schedules (e.g., OpenPulse) lack a rigorous formal semantics. This absence hinders the development of formally verified quantum compilers. The core challenge is to create a language that:

Captures the timing constraints of quantum gates (e.g., gate durations, relative start times).
Allows for formal reasoning about the correctness of the compilation process from circuit to pulse schedule.
Ensures that the compiled pulse schedule implements the exact same unitary operator as the original circuit.

2. Methodology

The authors propose GRAMPUS (GRAded Modal type theory for PUlse Schedules), a graded modal type theory designed specifically for pulse scheduling.

Core Concepts

Graded Modalities for Time: The language augments linear type theory with grades (integers/real numbers) representing relative time.
- A type $d \ A$ indicates that data of type $A$ will be available $d$ time units in the future.
- A variable $x : d \ A$ represents a state existing $d$ units in the future.
- Negative grades (e.g., $-75$) represent states that existed in the past.
Two Variants of the Language:
1. Plain Language: Represents standard quantum circuits without explicit timing information.
2. Annotated Language: Represents pulse schedules where every variable and term carries timing annotations.
Syntax:
- Based on multiplicative intuitionistic linear logic (products, units).
- Includes base types for qubits ( $q_i$ ).
- Includes gate applications ( $G(t_1, \dots, t_n)$ ) with associated durations.
- Includes explicit timing constructs: delay (sending no signal) and box (time-shifting).
Semantics:
- Categorical Semantics: The languages are interpreted in Symmetric Monoidal Categories (SMCs).
  - The plain language maps to standard SMCs (e.g., Finite-dimensional Hilbert Spaces).
  - The annotated language maps to SMCs equipped with a monoidal endofunctor Shift(d) representing time shifts.
- Signal Model: The authors construct a specific SMC where objects are sequences of channels with start/end times, and morphisms are pulse schedules (functions mapping channels and time to signal values).
- Syntactic Model: They prove that the term model (the category of terms modulo equality) is initial, ensuring soundness and completeness.

3. Key Contributions

A. The GRAMPUS Type Theory

The authors define a formal syntax and typing rules where timing is intrinsic to the type system.

Gate Rules: If a gate $G$ takes duration $d$ , its inputs are annotated with $-d$ . This enforces that to produce an output "now," inputs must have been provided $d$ time units ago.
Erasure: A function $\lfloor \cdot \rfloor$ removes all timing annotations, mapping the annotated language back to the plain language (the circuit).

B. Categorical Models and Correctness

Hardware Model: The paper defines a category of signals ( $S$ ) where morphisms are actual pulse schedules. They prove that $S$ is a valid categorical model for the annotated language.
Commutative Diagram (Theorem 22): The central correctness result is a commutative diagram:
- Path 1: Circuit $\to$ Annotated Program (via scheduling) $\to$ Pulse Schedule $\to$ Unitary Operator (via hardware model).
- Path 2: Circuit $\to$ Unitary Operator (via standard interpretation).
- Result: If the hardware model is correct, both paths yield the same unitary operator. This guarantees that the compiled pulse schedule implements the intended quantum computation.

C. Normal Forms and Completeness

The authors define normal forms for GRAMPUS terms, decomposing them into input elimination, circuit application (gates/delays), and output construction.
They prove a Completeness Theorem: If two terms are semantically equal in all models, they are syntactically equal. This confirms that the syntax fully captures the semantics.

D. Implementation and Scheduling Algorithm

Intermediate Representations (IR): The paper describes an implementation in Agda using two IRs: Circuit (plain) and AC (annotated).
As-Late-As-Possible (ALAP) Scheduling: They implement a scheduling algorithm that takes a plain circuit and a target end-time, then generates an annotated circuit (pulse schedule) that pushes operations as late as possible to minimize idle time, while respecting gate durations and dependencies.
Verification: They show that the ALAP algorithm is a right inverse to the erasure function, ensuring the generated schedule corresponds to the original circuit.

4. Results

Formal Semantics Established: GRAMPUS provides the first type-theoretic framework with precise semantics for quantum pulse schedules.
Soundness and Completeness: The syntactic model is initial, and the interpretation into the signal category is sound.
Compiler Correctness: The paper proves that a compiler translating circuits to pulse schedules (via the annotated language) preserves the unitary operator semantics, provided the hardware model is correct.
Practical Prototype: A working implementation in Agda demonstrates the feasibility of the approach, including the ALAP scheduling algorithm.

5. Significance

Formal Verification of Quantum Compilers: This work lays the theoretical groundwork for building formally verified quantum compilers. By treating pulse schedules as typed terms, one can use proof assistants (like Agda) to verify that a compiler does not introduce timing errors or alter the quantum state evolution.
Bridging Abstraction Gaps: It creates a rigorous bridge between high-level quantum algorithms (circuits) and low-level hardware control (microwave pulses), a gap that currently relies on informal or semi-formal descriptions.
Extensibility: The framework is designed to be extensible. The authors note future work will include measurement and hybrid algorithms, which are critical for real-world quantum computing but difficult to model with current linear type theories.
Category Theoretic Insight: It demonstrates the utility of graded modal type theories and categorical semantics in modeling physical time constraints in quantum systems.

In summary, GRAMPUS transforms the problem of quantum pulse scheduling from an engineering heuristic into a formal type-theoretic problem, enabling rigorous proofs of correctness for the compilation of quantum programs to hardware.