WorksComputer Science
A Complete Calculus for Hamiltonian Quantum Programming
Abstract
Given the forces acting on a quantum particle, a Hamiltonian models its continuous evolution. Quantum computers evolve Hamiltonians to simulate physical systems, to solve optimisation problems, and to estimate eigenvalues, and even the popular circuit abstraction is compiled to Hamiltonians on the hardware. We introduce Hamilton, a process calculus whose parallel operator is the sum of interactions acting simultaneously. Its operational semantics is the Lie-Trotter product formula, which recovers a sum as the limit of ever finer sequential interleavings; compiling a program means halving it to a chosen precision and unrolling the interleaving into a circuit. The semantics is fully abstract, the expressible Hamiltonians are exactly those whose Pauli coefficients have the form , the precision that successive halving reaches, and the equational theory is complete and decidable. A full implementation compiles Hamilton programs to circuits and decides their equivalence, and Agda proofs sanity-check the core metatheory.
Introduction
Quantum programs are often expressed as circuits. Across quantum programming languages, from low-level assembly languages like OpenQASM to functional languages like Quipper to equational calculi like , a program denotes a sequence of gates: elementary unitary operations applied one after another to an array of qubits. Sequential composition is the primitive, and it makes these languages tractable: a circuit is an instruction stream, which compiler writers and type theorists know how to reason about.
Yet one of the most common modes of quantum computation, and the original motivation for quantum computers [11], expresses programs by Hamiltonians [18], as in simulation, optimisation [9, 10] and eigenvalue estimation [16]. A gate jumps from one state to another, whereas a Hamiltonian defines the continuous trajectory between them, of which a gate is a snapshot. Formally, a Hamiltonian is a self-adjoint matrix , its evolution is , and the snapshot at a time is a gate. For example, the state of a qubit is a pair of amplitudes, written , and the Hamiltonian drives along , a wave that oscillates between and . At the snapshot is the NOT gate, which swaps the two amplitudes, up to a global phase ; global phases are unobservable, and we ignore them from now on.
Hamiltonians become interesting when several act at once. Think of a Hamiltonian as a force driving a quantum particle: when several forces act on the particle simultaneously, they add. Take together with , whose snapshot at is the phase-flip gate, taking to . In Figure 1, time spent running is drawn horizontally in orange and time spent running vertically in blue, so running one and then the other goes around a square on one side or the other, to the same corner. Whether the two orders reach the same state depends on how long each runs. Run in full, they give the gates and , which differ only by an overall sign, so the order is unobservable. Run halfway, the order becomes observable. Write and for the half runs: turns each amplitude into an even blend of the two, and multiplies the second amplitude by , halfway around the circle from to . From the initial state , the two evolutions proceed as:

Figure 1. Interleavings of and at levels : orange steps run , blue steps run , and the dashed diagonal runs both at once. The path below the diagonal runs first, the path above runs first. To first order, an interleaving’s error is proportional to the shaded area between its path and the diagonal, which halves at each level.
In the first line, blends equal amplitudes, which leaves them equal, and then only turns the phase of the second. In the second, first turns the amplitudes into and , and blends these so that their contributions to cancel, leaving . The same two steps thus give a fair coin in one order and a certain outcome in the other. Running the two at once, the diagonal of Figure 1, is a third evolution, which interleavings of ever smaller slices approach from either side.
Formally, simultaneous interactions add: their Hamiltonians are summed in the Lie algebra of the unitary group, while the gates of a circuit are multiplied in the group itself. Such interactions behave like concurrent processes. Two processes are independent when the order in which they run does not affect the outcome; two interactions are independent in exactly this sense when their Hamiltonians commute, and otherwise their order shows in the result, as it does for and . Concurrency theory separates such events from a schedule that orders them [8, 24], and a single processor runs concurrent processes by interleaving time slices, approximating their simultaneous execution better as the slices shrink. Simultaneous quantum interactions are run the same way. The Lie-Trotter product formula [27], the bridge from the algebra back to the group, writes as the limit of , a round-robin schedule that gives each term a time slice of .
Circuit languages can be patched to reach such sums. Trotterisation [18] writes the round-robin schedule out as a circuit, and block encodings [19], which the language Cobble [28] compiles, realise a sum exactly at the cost of ancillary qubits. But, as Milner observed, concurrency “requires a new conceptual framework, not just a refinement of what we find natural for sequential computing” [21]. Rather than patch the circuit model, develop that conceptual framework for Hamiltonians, in a language called Hamilton. A Hamilton program composes interactions in parallel, written , with no order among them, and denotes the sum of their Hamiltonians. Programs compile to circuits of the calculus [3, 4]. This is an ideal target, as extends the calculus of classical reversible computing [5, 15] with a square root of not and with the -th roots of unity, phases of ever finer precision, each the square root of the one before. Approximation needs square roots, since a Trotter schedule interleaves ever smaller slices of each interaction, and running an interaction for half as long takes a square root of its evolution. Hamilton adds the matching capability to the process algebra of independent events: halving a process. Compilation is then the operational semantics: to run a program is to halve it times, for a chosen level , so that every duration in it is a dyadic rational (a fraction of the form for and ), and to unroll it into a schedule of Trotter steps, each a circuit.
Outline. Section 2 gives background on and on Hamiltonians, through examples. Section 3 fixes the syntax and type system of Hamilton, Section 4 its semantics and universality, and Section 5 full abstraction. Section 6 describes the implementation, and Section 7 applies it to a complete example. Section 8 compares Hamilton with SimuQ [23], Paulihedral [Li et al. 2022], Cobble [28] and equational reasoning about circuits built from Pauli rotations. Section 9 concludes.
From Hamiltonians to Circuits
Hamiltonians, Lie algebras, and Lie groups. The (time-independent) Schrödinger equation describes how physical systems evolve through time. The specification of the physical system to evolve is given by a Hamiltonian , which is an operator on the state space of the system satisfying (with the conjugate transpose of ). Solutions to this equation turn out to be given by families of operators with the time parameter. These solutions live in a Lie group: a group that is simultaneously a finite-dimensional real smooth manifold, such that group multiplication and inversion are smooth. Solutions can be thought of as continuous paths on the surface of this manifold. When multiplied by , the Hamiltonians themselves belong to the corresponding Lie algebra: a vector space together with a bilinear map , the Lie bracket, that satisfies alternation for all , and the Jacobi identity for all . Every Lie group is associated with a Lie algebra (and vice versa) via exponentiation and logarithms. Quintessential examples are the Lie group of -by- unitary matrices, with associated Lie algebra .
Free Quantum Computing. Hamilton compiles to circuits of , the free model of quantum computing [3, 4], so we begin there. Its ancestor is a calculus of type isomorphisms: in the standard model, types are finite sets built from , , sums and products, a term is a permutation of their elements [5, 15], and the calculus is sound and complete for reversible classical computation. adds , a square root of not, and the scalar phase , the principal -th root of unity, so that . With these extensions, the language becomes complete for quantum computing with terms denoting unitary matrices. The index can be any positive integer: since , each embeds in . The equational theory of is fully abstract for its unitary semantics [3]: two terms are provably equal exactly when they denote the same unitary.
Hamiltonians on the Sphere. On one qubit, the Hamiltonians of Section 1 have a geometric picture. The states of a qubit form a sphere, the Bloch sphere, with and at the poles and the states with even split probabilities around the equator. Running the Hamiltonian rotates around the axis, i.e., turns the sphere about the axis through the poles, which changes only the phase ; running the Hamiltonian turns it about an axis through the equator, which moves states between the poles. Running both at once, turns the sphere about the axis halfway between the two, and a state at right angles to that axis moves along a great circle, a circle centred at the centre of the sphere. One long -rotation followed by one long -rotation produces a trajectory that is quite far from the great circle. Alternating four short turns about and follows that great circle more closely (Figure 2). In the limit, the alternation defined by the Lie-Trotter product formula [27]

Figure 2. The example of § 2 on the sphere of one-qubit states, drawn with up, to the left and towards the reader. From the marked start, for turns about the axis of along a great circle (thick), crossing the equator. One turn about followed by one about ends far from it (dashed); four alternating turns of a quarter the size stay close all the way (blue).
converges to the great circle perfectly.
is a Hamiltonian, and Figure 2 runs it for a chosen angle, following up to . A Hamilton program builds the angle into its Hamiltonian instead: a program with Hamiltonian runs it for one unit, as the unitary . The motion of Figure 2, , is therefore the program with Hamiltonian , written with the phases and gates of as the parallel composition of the two actions
Here is the 1-by-1 Hamiltonian 1/8, whose unitary is the phase , so , a direct sum, is the diagonal ; conjugating it by the Hadamard gate gives , which is ; and adds the two. The index 3 is the precision: running an action for half as long replaces by , a phase of .
Every Hamiltonian in Hamilton has this form. On qubits it is a real weighted sum of Pauli strings, tensor products of matrices drawn from , , and , one per qubit, and its program is the parallel composition of its weighted strings. The weights are dyadic rationals, which are dense in the reals, so an arbitrary Hamiltonian is matched as closely as desired by refining , and Theorem 16 shows Hamilton expresses exactly all Pauli strings with dyadic weights.
A program runs through its schedules, the lists of its actions in some order. The schedules of are and (which are lists, not to be confused with the Lie bracket). At level , a schedule runs each action for of the time, so that becomes and repeats times; Figure 2 draws at levels 0 (dashed) and 2 (blue). The two schedules compile to different circuits at every level but converge to the same motion, so the theory should equate them. For this, two rules suffice.
first equates any two orders of a schedule, since order does not matter in the limit. The second replaces an action by actions with the same effect at every level, such as by two copies of its half, ; it asks for equations between circuits, and the full abstraction of supplies exactly the true ones. Section 3 defines processes, schedules and these two rules, Section 4 gives the semantics and shows the rules sound, and Section 5 shows them complete.
Processes
This section gives the syntax and types of Hamilton processes, the shorthands used in examples, and the rules that equate processes.
Syntax and types
The syntax of Hamilton follows the structure of a Hamiltonian. Every Hamiltonian is diagonal in a suitable basis, where it simply assigns a real number, its rate, to each basis vector; running the Hamiltonian for one unit of time rotates the phase of each basis vector by its rate, counted in full circles. Programs are built the same way, from a diagonal of rates and a basis in which to run it, and several of these can then run together.
The rates on a diagonal are written as scalars, which are chosen with compilation in mind. The scalar runs at rate , its opposite at rate , and 0 stands still. Compilation cuts a program into ever smaller slices, and a slice half as long is the same program at half the rate. Since halving gives , every slice is again made of scalars. Every scalar also compiles exactly: running for one unit of time multiplies by a -th root of unity, which provides. Placing scalars side by side along a diagonal, with the direct sum , gives a bare action. For instance, the action of Section 2 places beside , rotating the phase of by an eighth of a circle in one direction and that of by an eighth in the other; its Hamiltonian is .
A bare action only rotates the phases of the basis vectors. To drive towards , as does, an action runs a bare action in another basis. It does so by conjugation with a transformation, which switches to the new basis, lets the bare action run there, and switches back. The action of Section 2 runs in the basis of the Hadamard gate, which makes its Hamiltonian . The transformations are the Clifford circuits, built from the Hadamard gate, the phase gate, the controlled-not and the swap by sequential composition and tensor product, and they are chosen for their fit with Pauli strings. On the one hand, every Pauli string becomes diagonal, made of and alone, in one Clifford basis, so actions express every Pauli string. On the other hand, Clifford circuits map Pauli strings to Pauli strings, so the Pauli coefficients of every process remain dyadic (Theorem 15) and normal forms decide equivalence (Section 6). Two changes of basis in a row combine into one, so an action changes basis only once, around a whole diagonal; and direct sums combine only bare actions, because changing the basis of one block of a direct sum and not the other is a controlled operation, in general outside the Clifford circuits. Every action is therefore a diagonal of scalars in a single Clifford basis, just like the diagonalised Hamiltonian we started from.
Finally, several actions run simultaneously in a process, whose Hamiltonian is the sum of theirs; the program of Section 2 is such a process, with Hamiltonian .
Figure 3 gives the formal grammar, together with a type system that keeps dimensions consistent. The type of a term is the dimension of the space it acts on: a scalar has type one, a direct sum adds the types of its parts, and conjugation and parallel composition require their parts to have equal types. Transformations act on qubits, so their types are powers of two, and we focus on processes of these types, which act on registers of qubits.

Figure 3. The syntax and type system of Hamilton. Types are positive integers corresponding to the dimension of the space acted on by the process. Among the transformations, H is the Hadamard gate and S the phase gate .
Halving extends from scalars to every process, running it for of its duration.
Definition 1. The -way halving of a process is given by , and , and commutes with the other constructs: , and .
Derived forms
The core syntax is minimal, and examples use a few shorthands that expand into it. We write for the action of type , and for , which needs no parentheses since is associative (Theorem 7). Conjugating a composite process conjugates each part, . Repetition , combined with halving, multiplies a process by a positive dyadic rational, ; every process has an inverse (Theorem 8), and .
Tensor products of actions build Pauli strings. On scalars, , with signs multiplying as for numbers, and . On bare actions distributes over , , and on actions it tensors the transformations and the bare actions separately, , padding a bare action with the identity transformation I. For example, with and ,
which denotes the Pauli string (§ 4). Weighting Pauli strings by dyadic rationals approximates any Hamiltonian, since the dyadic rationals are dense in the reals: with , the two-qubit Hamiltonian with real weights is approximated by , with each close to its weight.
Process equivalence
When can one process replace another, or part of another, without changing the behaviour of the program? The answer licenses optimisation, and rewriting a process into one about which a property is easier to prove. We give it through schedules, which also define the sequential executions that, halved and repeated, approximate the concurrent one by the Lie–Trotter formula (§ 4).
Transformations
Actions
fig:4. The interpretation of Hamilton transformations and actions as terms in the complete calculus of sequential quantum programs . Terms of compose in sequence by juxtaposition, and by direct sum and tensor product ; is the identity on elements, and is a qubit; exchanges the two summands of (the not gate) and the two factors of a product, matching the and of Carette et al. [ [3]; is the square root of not; is a scalar, multiplies by a scalar, and inverts. Since , the action becomes .
Definition 2. A schedule is a list of actions . The schedule of a process lists its actions, and , where @ concatenates lists, and halving acts on schedules element-wise, .
Equating schedules needs the sequential behaviour of actions, and is a complete calculus for sequential quantum programs: Hamilton actions are exactly representable as terms by the function of Figure 4. With this in hand, we are ready to define schedule equivalence:
Definition 3. Define schedule equivalence as the least equivalence relation satisfying the following:
where in (R1), is any permutation of elements, and (R2) can be applied iff there exist actions and a proof in that for all .
Definition 4. Define process equivalence as if and only if .
Rule (R1) lets the actions of a schedule trade places freely, which may be surprising for a notion named after an order of events. A schedule carries two readings of a process. Read additively, as in the Hamiltonian semantics of § 4, its actions are summed and their order is immaterial; this is the reading that process equivalence captures. Read sequentially, as in the approximate semantics, its actions form one Trotter step and run in the order listed; the order then changes the approximation at each finite level, though never its limit, and § 6 shows by how much. Swapping two adjacent actions that commute changes nothing even at a finite level, so the finite levels respect the trace equivalence of Mazurkiewicz [ [20], with commutation as independence; rule (R1) extends it to all permutations, at the cost of Trotter error. Equivalence could equally be stated on processes, up to associativity and commutativity of ; we state it on schedules because a schedule is also the program compiler runs.
The side condition of rule (R2) quantifies over every halving, and it must. The action turns the phase of once around the circle, so its unitary is the identity, like that of . parallel with the process , whose Hamiltonian is , the two differ: started in , the composition with ends in with probability 1.000, and the composition with with probability 0.026. Run at level 0 their schedules agree (probability 1.000 for both); from level 2 on they do not (0.021 at level 2), because the other process acts between the slices of the full turn. Brookes [ [2] met the same phenomenon in shared-variable parallel programs: skip and have the same input-output behaviour, yet a concurrent tells them apart, so a compositional semantics must record behaviour wherever the environment can interfere. Here the environment interferes at every slice of every level, so actions may be exchanged only if they agree after every halving, which is equality of their Hamiltonians, the semantics for which the theory is complete (§ 5).
We conclude this section by establishing some properties of schedule and process equivalence, and of Hamilton processes under process equivalence. Some of the more straightforward proofs have been relegated to the supplementary material.
Proposition 5. Process equivalence is an equivalence relation.
Proof. Immediate, since is an equivalence relation by construction. □
Proposition 6. Process equivalence is congruent under : implies and similarly on the right.
Proof. Suppose that , i.e., , and let be some other process. By definition . That means can be turned into by a sequence of applications of the permutation and/or the substitution rule. But these can be directly extended to applications on only acting on the first part of the schedule: applications of the permutation rule can be extended by choosing a permutation that does the same on the first part while leaving the other intact, and similarly for the substitution rule. Thus , so . The analogous argument applies on the other side. □
Proposition 7. Up to process equivalence, the set of Hamilton processes of type forms a commutative monoid with as composition and as identity.
Proposition 8. Every process has an inverse process such that .
Process equivalence is defined by rules on syntax, but rule (R2) brings in the semantics through . Its side condition asks for a proof in , and such a proof exists exactly when both sides denote the same unitary after every halving, because the equational theory of is complete [3]. This is what provides inverses: the inverse of an action negates its scalars, so that for every , and rule (R2) rewrites the schedule into , as the supplementary material demonstrates.
Corollary 9. Up to process equivalence, the set of Hamilton processes of type forms an abelian group with as composition and as identity.
Proof. Combine Propositions 7 and 8. □
Semantics
There are several obvious candidates for a semantics of Hamilton processes: We can consider the direct Hamiltonian of a process, or the induced unitary semantics. We can also consider the schedule of a process as defining a semantics in terms of its sequential approximations, at both a level and in the limit as . In fact, we will do all four things, and discuss how these relate.
Unitary transformations
Hamiltonian actions
Schedules
Processes
We define the unitary semantics , the Hamiltonian semantics , and the approximate schedule semantics at level , and the limit schedule semantics in Figure 5. Note that the Hamiltonian semantics depends on the unitary semantics for defining the meaning of a conjugated action: this is justified by the fact that is Hermitian whenever is unitary and is Hermitian since

Figure 5. The Hamiltonian semantics , unitary semantics , approximate schedule semantics at level , and limit schedule semantics of processes. On matrices and , denotes the block diagonal matrix which has and as diagonal blocks (in that order) and zeros everywhere else, while denotes the Kronecker product of and .
Similarly, the schedule semantics depend on the unitary semantics of actions, which in turn is derived from the Hamiltonian semantics of actions. For this reason, it is more convenient to define the three simultaneously.
There are direct relationships between these semantics, and between the semantics and process equivalence, that we will explore in this section. One very direct relationship is between the Hamiltonian and unitary semantics:
Proposition 10. The Hamiltonian semantics are strictly more fine-grained than the unitary semantics: implies but not vice versa.
Proof. If then by definition . The converse implication does not hold since exponentiation mods out eigenvalues by : e.g., . □
As regards the schedule semantics, we will see in Proposition 12 that it does, in fact, produce the same semantics as the unitary semantics in the limit. To this end, we need a technical lemma.
Lemma 11. For all processes , .
Proof sketch. By straightforward algebraic manipulation. □
Proposition 12. For all processes , .
Proof. By definition a process is of the form for actions up to a choice of bracketing, but since is fully associative on the nose in its schedule semantics, this choice is semantically irrelevant in that regardless. Then
where the step that removes the limit is the Lie–Trotter product formula [14, 27], which holds for any finite family of matrices and so in particular along the subsequence of powers of two. The other steps rewrite by definition and by Theorem 11, so the argument takes a single limit and never exchanges two. □
Theorem 12 is a guarantee about compilation as a whole: every process compiles to circuits that converge to its unitary. Like type soundness, it is established once for the language, rather than checked on each compiled circuit.
The situation is a bit more delicate with the -level schedule semantics, since these are not exact but approximate semantics. That is, does not correspond to the true semantics of , merely an approximation only given access to subdivisions of of size . As such, we cannot expect to imply since the latter could be false simply due to and being different approximations of the same limit. Accounting for this fact leads to the following result:
Proposition 13. The limit schedule semantics are approximately more fine grained than the schedule semantics at any particular level : implies that as , where is the operator norm.
Proof idea. Use that and both converge to
We can wonder at this stage how the semantics relate to the notion of process equivalence we defined previously. We show below that process equivalence is sound with respect to the most fine-grained of these semantics, namely the Hamiltonian semantics—so also with respect to the unitary and limit schedule semantics. The converse direction is the subject of the next section.
Theorem 14 (Soundness). For processes and , implies .
Proof. We start by noticing that if has the schedule then . To prove soundness, we proceed by induction on the number of applications of (R1) and (R2) applied. In the base case, no rules are applied and directly. In the inductive case, we assume that all proofs using applications of (R1) and (R2) are sound, and must show that all proofs using applications are sound, too. This yields two cases depending on which rule is applied. If the final rule is (R1) by some permutation , then since summation is commutative. If the final rule is (R2), notice first that iff when (where denotes the operator norm), since the function is bijective on the half-open interval . Further, we remark that iff for (real) nonzero , so by choosing to be sufficiently large, we have that iff . Suppose now that for all , and choose such that both and . Then
using the fact that for all and by Lemma 11, soundness of (so that implies ), and the Lie-Trotter product formula for the final limit. Since both and have norm below , it follows that , so
We summarise the relationship between the different semantics in Figure 6.
Figure 6. The semantics of Hamilton and their relationships.
Universality
So far, we have introduced the syntax of Hamilton, its associated notion of process equivalence, and its semantics. Before moving on to full abstraction, we consider the important question of what can actually be expressed in Hamilton.
Recall that the Hermitian operators on form a real vector space of dimension . Focusing, as is commonly done, on the qubit case where , a convenient basis for is given by the Pauli strings. We show that Hamilton can express essentially all Hamiltonians in , by showing that Hamilton processes of type are in a semantic one-to-one correspondence with Hamiltonians in whose Pauli coefficients fall in the ring of dyadic rationals. Since the dyadic rationals are dense in the real numbers, any real number coefficient can be approximated to within an arbitrary error by a dyadic rational, allowing any Hamiltonian in to be approximated in this way by a process in Hamilton. This is entirely analogous to the usual notion of universality in the context of quantum circuits, where a gate set is universal if it allows any unitary to be approximated to with any desired error.
Theorem 15. For every process , has Pauli coefficients in the ring of dyadic rationals.
Proof. Let for actions , so , and it suffices to show that each has Pauli coefficients in the dyadic rationals.
If is a bare action then is a diagonal matrix with entries of the form , , or , which are all dyadic rational. This diagonal matrix can be expressed as a sum of Pauli strings with only and factors using the fact that
and
so all matrix units in the diagonal can be constructed by Kronecker products of these. Denoting the component in the diagonal of by , we have , and since is dyadic rational, and was constructed above as a sum of Pauli strings with dyadic rational coefficients, we have shown that has dyadic rational Pauli coefficients.
In the case where is not a bare action so that for a bare action , we have that . In this case, we decompose exactly as above, and remark that is a Clifford group operation (so conjugates Pauli strings to Pauli strings), so is already a sum of Pauli strings with dyadic rational coefficients.
:::
Theorem 16. For every Hamiltonian with Pauli coefficients in the ring of dyadic rationals, there exists a process such that .
Proof. Expressing in the Pauli basis , by assumption and is some Pauli string. By the assumption, we are free to let for some and . Since is Pauli string, it follows that it has eigenvalues , and so has eigenvalues . Since and , it follows that we can represent the diagonal matrix of eigenvalues of as
where is a binary valued function indicating whether the component is positive or negative, and we use the abuse of notation to mean when and when . In the case where is not diagonal, it must have or tensor factors: for each such factor, we conjugate the Hamilton term above by H if it is an , and by H; S if it is . (For example if , we represent the eigenvalue diagonal as above and conjugate the resulting process by .)
Representing each Pauli term in this way with a process satisfying , it follows that
as desired. □
In principle, combining these two theorems yields a procedure for normalisation by evaluation. However, doing so is not always efficient since has dimension , so normalising a process in this way may result in an exponentially large term. For processes whose actions are Pauli strings, the Pauli representation has one string per action, and § 6 computes it without building any matrix.
Full abstraction
The goal of this section is to show the converse of Theorem 14 to obtain a full abstraction result of process equivalence with regards to the Hamiltonian semantics, i.e., that iff for all processes of type .
The overall strategy is to use the normalisation procedure given by combining Theorems 15 and 16 to obtain a Pauli representation of a process, and show that every process is equivalent to its Pauli representation. This is done in several stages.
First, we consider the case of simple processes which are those that are free of unitary transformations. These are shown to have diagonal Hamiltonian semantics (Lemma 18), and
to normalise under to a form that (essentially) normalises each entry in the diagonal one-by-one. A consequence of this is that any simple process is equivalent to its Pauli representation (Corollary 25).
(2) Extending this to arbitrary processes relies on showing a few tricks: that this normalisation extends under conjugation by a unitary (Lemma 27), that the action of conjugating a Pauli string by a unitary can be normalised (Lemma 29), and that the only unitaries permitted to transform by are Clifford operations, which conjugate Pauli strings to Pauli strings. Together, these are used to show (Theorem 30) that processes normalise to their Pauli representations, and the desired result follows.
Definition 17. Say that a process is simple if with each a bare action.
In other words, a simple process is a process that is free of transformations.
Lemma 18. If is a simple process then is a diagonal matrix.
Proof. Suppose where each is a bare action. Since each is a bare action, it follows that where is either some , , or . As such,
so is diagonal. But then
so is a sum of diagonal matrices, i.e., diagonal. □
In this development, we will need some straightforward lemmas (whose proofs have be deferred to the supplementary material).
Lemma 19. For all bare actions and , it is the case that
(i) ,
(ii) ,
(iii) ,
(iv) .
Lemma 20. For all ,
(i) and
(ii) .
Definition 21. Say that a simple process is a 1-level process if there exist such that each for of the form , , or for some .
Lemma 22. If is a 1-level process then either or for unique such that is odd.
Proof. Since for scalars, and since is unital with as unit by Proposition 7, we are free to assume that either (in case all ) or no . If the former is the case, we are done. If the latter is the case, all are of the form . In this case, we use the following procedure to normalise :
Find the largest such that or appears in , and use Lemma 20 to express every action of the form as a composition of a number of , and every action of the form as a composition of a number of .
If both and appear in this expansion, pair up each with a until the remaining terms are either all or all , then use Proposition 7 to get rid of all matching pairs.
At this point, the expansion is either 0 or consists of either all or all . If the expansion is 0 or the number of terms is odd, we are done. If the number of terms is even, match up terms pairwise and apply Lemma 20 to combine terms, dividing the number of terms by 2, and continue this process until the number of terms is odd.
Since and analogously for , after normalisation the process is on the required form. To see that this is unique, we notice that
which is a normal representation of a dyadic rational (as a single entry in a 1-level diagonal matrix) since is odd.
Proposition 23. Every simple process is equivalent to a composition of 1-level processes of the form for unique , , , where is odd.
Proof. Let where each is a bare action, i.e., of the form for scalars . Applying Lemma 19 on each yields that is a composition of 1-level processes, namely
Grouping the resulting 1-level processes by index using associativity and commutativity (Proposition 7), we get that is equivalent to a big parallel composition of 1-level processes acting on each component,
and applying Lemma 22 to each group yields the desired result.
Definition 24. For a process , call the process extracted from in Theorem 16 the Pauli representation of .
Corollary 25. Every simple process is equivalent to its Pauli representation.
Proof. Simple processes have diagonal Hamiltonian semantics by Lemma 18, so their Pauli representation is simple. Normalising the process to a composition of 1-level processes (using Proposition 23) yields , and doing the same for its Pauli representation yields , so since is an equivalence relation.
Corollary 26. For simple processes and , implies .
Proof. Since it follows that and have the same Pauli representation , and since and by Corollary 25, it follows that by an equivalence relation.
Lemma 27. implies when and all are bare actions.
Proof. We proceed by induction on the number of rule applications in the proof that . In the base case , so no rules are applied, and we are done. In the inductive case, we assume that implies when the proof requires rule applications, and must show that the same is the case for rule applications.
There are two cases depending on the final rule applied. When the final rule is the permutation rule, we have in steps, and for some permutation . By induction , so also . As such, applying the permutation rule with yields .
When the final rule applied is the substitution rule, we have in steps, so we must have that and
where . But then
where the step marked follows since . Since we must then have and
that follows by the substitution rule using the proof that .
:::
Lemma 28. For all transformations , and action , it is the case that .
Proof. For any action (in particular any action of the form ) we have
so the statement follows by application of the substitution rule.
Lemma 29. When is a diagonal Pauli representation and is any transformation, there exists an action such that where is a Pauli representation.
Proof. When is a diagonal Pauli representation, it follows that it represents a Pauli string with only and as tensor factors. Since is a Clifford operation, it follows that is again a Pauli string, and by Theorem 16 that there exists some Pauli representation such that . But then it follows that
for all , and in turn that for all . Since is complete, it then follows that , so the statement follows by a single application of the substitution rule. □
Theorem 30. Every process is equivalent to its Pauli representation.
Proof. Let be a process. Without loss of generality we assume that each is a bare action, since if it isn’t, we can always use Lemma 28 to combine a multiply conjugated action into a bare action conjugated by a composition of transformations. Similarly, if some term in is not conjugated, we can always see it as conjugated by .
Applying Corollary 25, Lemma 27, and congruence of process equivalence under (Proposition 6) on each yields that
where each is a representation of a diagonal Pauli string, and is some transformation. However, since the permitted transformations are precisely the Clifford group operations, it follows that each is a Pauli string (as Clifford operations conjugate Pauli strings to Pauli strings by definition). However, it may not yet be a Pauli representation as extracted by Theorem 16, since there are many non-canonical ways of representing each Pauli string. However, using Lemma 29 we can always rewrite in into its Pauli representation.
In this way, where each is a Pauli representation. Using associativity and commutativity of (Proposition 7) to group all Pauli strings of the same type, we finally use the same technique as in Lemma 22 to combine the coefficients into one for each type of Pauli string, and we are done. □
Corollary 31 (Completeness). For all processes and , implies .
Proof. Since it follows that and have the same Pauli representation , and since and by Theorem 30, it follows that by equivalence relation. □
Theorem 32 (Full abstraction). For all processes and , iff .
Proof. Combine Corollary 31 and Theorem 14.
Full abstraction is what a compiler needs from the theory. Equivalent programs denote the same Hamiltonian but may compile to circuits that differ in error and size, so a compiler may replace a program, or any part of one, by a cheaper equivalent, and check the replacement by comparing Hamiltonians, which § 6 does by normal forms without building any matrix.
Lie structure
Full abstraction makes the correspondence with Lie algebras exact. Write for the set of matrices with a Hamiltonian whose Pauli coefficients are dyadic, and for the commutator. Like , define a derived form: the bracket of processes is any process with .
Proposition 33. (i) is closed under addition, negation and the commutator, so it is a Lie algebra over , and its real span is the Lie algebra of . (ii) The bracket of any two processes exists and is unique up to . (iii) The map is an isomorphism of Lie algebras from processes of type up to , with as addition and as bracket, onto .
Proof. (i) Two Pauli strings P and Q either commute or anticommute. If they anticommute, for a Pauli string R, so , with dyadic coefficient when and are dyadic; the commutator is bilinear, so closure follows. Pauli strings span all matrices, so the real span of is the space of matrices with Hermitian, which is [[14]]. (ii) By (i), is Hermitian with dyadic Pauli coefficients, so a process denoting it exists by Theorem 16, and any two such processes are equivalent by full abstraction. (iii) The map is well defined and injective by full abstraction and surjective by Theorem 16; it takes to addition by Figure 5; and . □
The exponential carries into , but in general outside the unitaries that terms denote: these have algebraic entries and so algebraic eigenvalues, while has eigenvalues , which are transcendental by the Gelfond-Schneider theorem. The schedule semantics replaces the exponential by circuits that converge to it (Theorem 12), and the bracket measures what that costs: one step differs from by to first order, and actions whose bracket is 0 are the independent actions of § 3, whose order no level can see.
Implementation
The semantics of the preceding sections is realised as a working compiler: a Haskell core that delegates linear algebra and gate synthesis to numpy and qiskit (both Python libraries). The pipeline takes a process term, forms the canonical schedule at a chosen refinement level, lowers it to a quantum circuit, and compares the result against the ideal continuous evolution for validation. The next three examples each isolate one characteristic behavior: Trotter convergence, schedule equivalence, and exact compilation of a commuting interaction. A larger, physically motivated instance follows in § 7.
A process term is represented directly as the abstract syntax of § 3:
data Proc
= Atom Action
| Proc :||: Proc
The compiler entry point is compileTrotter n p, which forms the canonical schedule at refinement level (repeated times):
compileTrotter :: Natural -> Proc -> QCircuit
compileTrotter n proc =
mconcat (replicate reps step)
where
step = compileSchedule (canonicalSchedule proc n)
reps = 2 ^ (fromIntegral n :: Int)
Each atomic action is a diagonal operator, possibly conjugated by a Clifford. The scalar generator compiles to a phase of :
diagonalAngles :: BareAction -> [Double]
diagonalAngles = \case
Id -> [0]
Delta k -> [phaseAngle k]
NegDelta k -> [-(phaseAngle k)]
DeltaPow k j -> [fromIntegral j * phaseAngle k]
a :⊕: b -> diagonalAngles a ++ diagonalAngles b
Although the formal syntax of § 3 treats as the derived abbreviation , the implementation promotes it to a primitive constructor DeltaPow k j. This keeps schedules compact: expanding a coefficient into parallel copies of before compilation would blow up schedule size on Hamiltonians with large integer coefficients. Diagonal operators are lowered to elementary gates through Qiskit’s DiagonalGate; conjugations become the corresponding basis-change gates surrounding the diagonal. For validation, compareToIdeal builds the exact unitary and reports the Frobenius distance to the compiled circuit, aligned up to global phase.
The building blocks for single-axis rotations are:
zK :: Natural -> Proc
zK k = act (Id ⊕ Delta k)
xK :: Natural -> Proc
xK k = conj H (Id ⊕ Delta k)
yK :: Natural -> Proc
yK k = conj (S · H) (Id ⊕ Delta k)
and the Hamiltonian of § 2, physically a single spin in a magnetic field with components along the and axes, is then:
zxK :: Natural -> Natural -> Proc
zxK kz kx = xK kx ∥ zK kz
Compiling zxK at increasing refinement levels and comparing against the exact evolution exhibits the central approximation behavior. At level the schedule alternates a -slice and an -slice times, each slice carrying an angle scaled by , and the circuit’s distance to the ideal falls accordingly:
| reps | Frobenius | |
| 0 | 1 | 0.4002 |
| 1 | 2 | 0.1933 |
| 2 | 4 | 0.0958 |
| 3 | 8 | 0.0478 |
| 4 | 16 | 0.0239 |
Table 2.
The error halves with each level, the expected first-order Trotter rate. Figure 7 shows the compiled circuit at levels and : at level 0 a single coarse -slice followed by an -slice; at level 1 two repetitions of half-angle slices, which halve the distance to the ideal. The process term is unchanged across both; only the refinement level varies. The distance compares endpoints, the evolutions after one unit of time; Figure 8 in § 7 shows how closely a refined circuit also follows the path in between.

Figure 7. Compiled circuits for at refinement levels and . denotes the single-qubit phase gate . Increasing the refinement level halves the angles and doubles the repetitions, which halves the distance from the ideal evolution at the endpoint; Figure 8 shows a refined circuit tracking the path as well.

Figure 8. Probability of finding the proton at at time , starting there: exact evolution under (solid), and compiled circuits for with at refinement levels (dashed) and (dots).
Because commits to no ordering, the canonical schedule is only one of several admissible realisations, and the implementation enumerates the others by permuting the schedule and scoring each against the ideal. Two cases are instructive. For the two-term the step contains a -slice and an -slice, which may be applied in either order:
| ordering | Frobenius |
| [Z, X] | 0.1933 |
| [X, Z] | 0.1933 |
Table 7.
The two circuits are genuinely different, yet they are equidistant from the ideal, and the reason is a symmetry of this example: and are real symmetric matrices, so reversing the order of the two slices transposes the unitary of each step, and hence of the whole circuit, while the exact evolution is itself symmetric, and transposition preserves the distance.
The orderings are always equivalent as realisations of the Hamiltonian, but without such a symmetry they need not be equally good approximations. Take a three-term single-qubit Hamiltonian, physically a spin in a field with components along all three axes:
zxyK :: Proc
zxyK = zK 1 ∥ xK 2 ∥ yK 3
A dominant at , a medium at , a small at , no two of which commute, and the term breaks the symmetry above: is antisymmetric, so transposition reverses its rotation. Enumerating its six orderings at level 1 produces a clear ranking:
| ordering | Frobenius |
| [X, Z, Y] | 0.4370 |
| [Y, X, Z] | 0.5276 |
| [Z, Y, X] | 0.5472 |
| [X, Y, Z] | 0.6355 |
| [Z, X, Y] | 0.6547 |
| [Y, Z, X] | 0.7292 |
Table 8.
The best and worst admissible circuits differ in accuracy by a factor of about 1.7, and the ranking is structured: the three best orderings are cyclic rotations of one another, and the three worst are the rotations of the reverse cycle. Every one of these circuits realizes the same Hamiltonian; the choice among them is pure optimisation within an equivalence class the theory certifies, and Trotter error plays the part that running time plays for classical programs. The equivalence makes any reordering safe; the quality spread makes the choice matter. A compiler can therefore search among reorderings for the most accurate one without re-checking what a candidate computes: soundness (Theorem 14) guarantees in advance that every reordering denotes the same Hamiltonian, so the search estimates only how well each candidate approximates it, and completeness (Theorem 31) guarantees that the same rules reach every other program with that Hamiltonian, beyond its reorderings.
Rewriting by the theory also reaches circuits that no circuit optimizer can. Any rewriting that preserves the unitary of a circuit preserves its Trotter error; the rules preserve only the Hamiltonian. Take, from a library, the four-qubit process , where applies to qubit and applies to qubits and , composed with a user’s term that cancels one of its terms. In every Trotter step the two are separated by -slices that anticommute with them, so the circuit offers nothing to cancel. In the program, rule (R1) and Theorem 8 cancel them, and the normal form needs 4 CNOT gates per step instead of 8, with less error at every level :
| composed | normal form | |
| 0 | 3.0975 | 2.1105 |
| 2 | 0.8681 | 0.4997 |
| 4 | 0.2186 | 0.1244 |
Table 3.
Rewriting can also make a circuit preserve a quantity exactly. Take the six-qubit process whose adjacent pairs of qubits carry and . The sum exchanges and on its pair, so it preserves the number of 1s in a basis state, as do the terms; but and alone do not. Scheduled by type, all terms, then all , then all , the circuit started in ends with a different number of 1s with the probability shown as the leak; scheduled pair by pair, a reordering by rule (R1), it preserves the count exactly at every level, at nearly the same error:
| leak, by type | leak, by bond | error, by type | error, by bond | |
| 0 | 1.7% | 0 | 1.0232 | 1.0496 |
| 2 | 0.1% | 0 | 0.2512 | 0.2657 |
| 4 | 0.0064% | 0 | 0.0627 | 0.0665 |
Table 4.
This is the invariant reasoning of concurrent programs [22]: a transfer a := a-1; b := b+1 preserves in every interleaving only if it is atomic. Here a block of consecutive commuting actions runs atomically in every step, and the count is preserved when the block’s sum commutes with ; whether a schedule preserves it at every level is a check on Pauli strings, made without any matrix. Merging the pair into one action does the same by construction: by normal forms, is equivalent to the single action with , which turns both strings into diagonals at once.
Not every Hamiltonian requires approximation. A single diagonal interaction commutes with itself, so its schedule is exact at every level, with no Trotter error to refine away. The two-qubit interaction :
zzParity :: Natural -> Proc
zzParity k = diag 0 k k 0
places a phase on the and states and compiles to a single CNOT-phase-CNOT circuit whose unitary matches the ideal exactly (Frobenius = 0.0000). The contrast with zxK is the point.
Refinement is the machinery for the non-commuting case; where terms commute, the compiler produces the exact evolution directly, and the schedule space collapses to a single circuit.
These examples are deliberately minimal, chosen to isolate one behavior each. The same pipeline, unchanged, compiles the multi-term molecular Hamiltonian of § 7: a nine-term, two-qubit Pauli sum taken from a published ion-trap experiment, whose Trotter schedule converges to the exact dynamics with the same first-order rate demonstrated here.
Deciding Equivalence. By full abstraction, is decided by comparing Pauli representations, and the implementation computes them symbolically. A bare action contributes the Walsh-Hadamard transform of its diagonal; conjugation by a Clifford maps each Pauli string to a signed Pauli string gate by gate, by the update rules of Aaronson and Gottesman [ [1]; coefficients stay exact dyadic rationals. Programs given as Pauli strings keep the tensor shorthand of § 3 symbolic and have one string per action, so the check is linear in the program. The table compares a family of Hamiltonians whose terms are the strings and on up to four adjacent qubits, plus single terms, written as Pauli strings, with the Pauli gadgets a compiler emits for it (one , a ladder of CNOT gates and a change of basis), on up to 256 qubits, where the operator either program denotes is a matrix. A gadget with a fault, the S of its factors dropped, shows up as two differing strings (column fault):
| qubits | terms | normal form | fault | time (ms) |
| 8 | 44 | 44 | 2 | 0.2 |
| 16 | 100 | 100 | 2 | 0.7 |
| 32 | 212 | 212 | 2 | 2.3 |
| 64 | 436 | 436 | 2 | 7.9 |
| 128 | 884 | 884 | 2 | 29.5 |
| 256 | 1780 | 1780 | 2 | 126.7 |
Table 1.
Reorderings need no check, by rule (R1); the check serves every other rewrite.
Sanity Checking. Leveraging a pre-existing implementation of in Agda, we formalised the core of HAMILTON, namely all the contents of § 3, and the contents of § 4 up to Proposition 14 over an abstract field and abstract matrices, as well as the first lemma of § 5. The statements of the other propositions in § 4 were also formalised. As usual, this caught a number of minor infelicities in the “paper math” version.
The main obstacles were the many occurrences of “ times” (and variants thereof), whose degenerate case is nonsensical, and the definition of schedule equivalence, whose obvious transcription would put defined functions into the indices of its type (what dependently typed programmers call green slime), making all subsequent reasoning unbearably difficult.
We expect the main difficulty in formalising the rest of § 4 and § 5 to lie in the universality theorems, which mix syntax and semantics, and in the normalisation procedure, whose current proof uses “without loss of generality” reasoning that will need to be made algorithmic.
Application: Simulating a Hydrogen Bond
Richerme et al. [ [25] used the QSCOUT trapped-ion quantum computer to simulate the hydrogen bond of the molecule DMANH. We summarise their experiment, then play the part of their machine: we take their Hamiltonian as given, compile it with HAMILTON, and compare the results with what they measured.
In DMANH, a proton sits between two nitrogen atoms; each attracts it, and repels it at close range. A classical particle under these forces would oscillate along the bond with a single period; the quantum proton oscillates with several periods. Discretizing the bond and using the mirror symmetry of the molecule, the experiment tracks the proton at four positions : at time it is in the superposition , whose amplitudes evolve under a Hamiltonian that they publish. The experiment prepares the proton at , say, evolves it for times , and measures its position, repeating each run to collect statistics. The resulting series is a sum of a few sinusoids whose frequencies are the gaps between the eigenvalues of ; the three gaps from the lowest eigenvalue are vibrational frequencies of the bond. A Fourier transform of the series recovered them with a typical uncertainty of 3.3 cm, the unit chemists use for frequencies. To run the experiment, they needed a small quantum circuit. For each , this circuit was computed on a classical computer by calculating and decomposing it into an optimal circuit of three CNOT gates and seven single-qubit rotations. This approach does not scale; for larger molecules, they propose compiling the Hamiltonian term by term instead, by Trotterisation, which is what Hamilton does.
To write in Hamilton, we turn each entry of the published matrix into the term , so that . Two qubits store as the binary numeral of , so that , and the identities
turn each term into Pauli strings: a diagonal entry needs only and , and an off-diagonal entry, together with its mirror image , has an or a at each bit in which and differ. For instance,
where stands for . Collecting terms, dropping the identity (which shifts all energies equally), and scaling and rounding the weights to fractional bits gives the process
built from , H and S as in § 3. The weights of , and come from the diagonal of , and the other six from its off-diagonal entries. Each term compiles to a single action.
Running the Program. In Hamilton, the snapshot at time runs , whose schedule is repetitions of one Trotter step: the nine actions in sequence, each for units of time. A simulation is thus a loop around one short circuit, with a snapshot after each iteration, and two numbers control its accuracy: the precision of the weights, which fixes the rounding error, and the refinement level , which fixes the Trotter error. No unitary is computed, and a step grows with the number of terms rather than with the dimension. At two qubits the price is circuit size: a step has 18 CNOT gates as emitted and 10 once adjacent pairs cancel, so the 219 steps of Figure 8 () add up to more than two thousand, where the experiment needs three for any . Smaller circuits for the same unitary are reachable by rewriting alone: the equational theory of is complete, so every circuit with the same unitary is derivable from ours, and cancelling CNOT pairs is the simplest such derivation. The experiment’s circuits are not among them: they implement the exact evolution rather than our rounded, Trotterised one, and their rotation angles, computed numerically, are in general not dyadic.
We computed the outputs of the compiled circuits exactly, without hardware noise. The eigenvalues of a compiled step determine the frequencies at which repeated steps oscillate, which are the ones a Fourier transform of the snapshots finds. The table gives the largest error in the three frequencies:
| frequency error (cm) | |||
| 1 | 243.0 | 225.5 | 220.2 |
| 2 | 72.8 | 70.3 | 59.8 |
| 3 | 23.3 | 25.4 | 13.3 |
| 4 | 23.6 | 13.8 | 2.5 |
| 8 | 25.3 | 9.9 | 2.8 |
| 25.3 | 9.9 | 2.8 |
Table 1 (PDF p. 24).
Down each column, refinement removes the Trotter error until only the rounding error of the bottom row, the exact evolution of , remains; more bits lower it. Figure 8 shows the same convergence along a trajectory: departs from the exact curve by up to 0.17 at , and by at most 0.0042 at . At and the frequency error is at most 2.8 cm, below the experiment’s 3.3 cm: compiling term by term costs no accuracy that the experiment could detect. The two numbers measure different things, though. Ours is the error of the algorithm, computed exactly; theirs is the noise of a physical measurement, on circuits with no algorithmic error. On hardware our longer circuits would add noise, so at two qubits the experiment’s compiler is the better choice; ours is for molecules whose unitaries are too large to compute.
Related Work
Languages and compilers for Hamiltonians. SimuQ [23] is closest in purpose. A program in its Hamiltonian Modeling Language describes the system to be simulated, hardware providers describe what their machines can do in an abstract analog instruction set, and a solver finds a pulse schedule that makes an analog machine follow the program. SimuQ thus targets machines that are programmed through their own Hamiltonian, where Hamilton targets circuits; it has no equational theory, and its notion of correctness is that of its solver. Paulidhedral [Li et al. 2022] compiles from an intermediate representation of blocks of weighted Pauli strings, which is the normal form of Hamilton, through scheduling passes and passes that synthesize, simplify and map the resulting circuits, for both near-term and error-corrected machines. Its scheduling changes the order of terms within a step, which rule (R1) certifies, and its outputs can be checked against its inputs by normal forms (§ 6). Cobble [28] is a language for quantum linear algebra, with simulation among its applications: programs manipulate matrices through block encodings and are compiled to circuits, with resource analyses and optimisations based on quantum singular value transformation [12]. A block encoding realises a sum of matrices exactly at the cost of extra qubits [19]; Hamilton approximates it with none. We claim no advantage in circuit size or fidelity over these systems; what Hamilton adds is an equational theory, complete for Hamiltonians, under which their transformations can be certified.
Equational reasoning about Pauli rotations. Phase gadgets, the ZX-calculus form of a rotation about a Pauli string, support equational reasoning about circuits made of such rotations and underlie gadget synthesis in the tket compiler [6]. That reasoning concerns the unitaries of circuits at a fixed level. Hamilton reasons about the Hamiltonians they approximate, so its rules also relate circuits whose unitaries differ, such as the reorderings and cancellations of § 6.
Calculi for quantum circuits. [3, 4], on which Hamilton builds, is complete for the unitaries of circuits; Hamilton adds parallel composition and halving on top of it and is complete for Hamiltonians (§ 5).
Conclusion
A circuit is a sequence of gates; a Hamiltonian is a sum of interactions. Hamilton is built on the second reading, taking additive combination of evolutions as primitive and recovering the sequential circuit only at compile time, through the Lie-Trotter formula that is its operational semantics. The result is a language in which Hamiltonians are first-class, with the metatheory one expects of a circuit calculus: an equational theory that is fully abstract, so process equivalence collapses to equality of dyadic-rational Pauli coefficients; a universality theorem fixing the expressible Hamiltonians exactly; and an execution model that is ordinary compilation. Used as a configurable simulator, its implementation compiles the published Hamiltonian of a hydrogen bond into circuits that recover vibrational frequencies of the bond to within the measurement uncertainty of the original experiment. Simulation is one use among several: any computation programmed by a Hamiltonian, from optimisation to eigenvalue estimation, can be written, checked and compiled the same way.
The schedules Hamilton compiles to are first-order Trotter, and higher-order splittings [26] and qubitised simulation [12] the natural next step for driving the residual error and fault-tolerant cost down. What most separates the language from practice, though, is maturity: it has so far been exercised only on small Hamiltonians, its circuits still await optimisation (one Trotter step of the molecular example emits 18 CNOT gates, where two-qubit resynthesis needs 3), and connecting it to the standard pipeline of electronic-structure packages and fermion-to-qubit mappings, and scaling to the many-term operators of real problems, is the work that adoption would require. One can additionally imagine compiling not just to simulation algorithms, but also to other algorithms where simulation is a key component, such as quantum phase estimation.
A deeper direction is to widen the language itself. So far we have built Hamilton on the pure, reversible core of , but the full calculus is richer: Carette et al. [ [3] extend with mid-computation measurement and with a theory of irreversible, open-system quantum computation, and show that these additions strengthen rather than disturb its completeness. Lifting the same extensions to Hamilton’s additive layer would let it express the eigenvalues and expectation values that estimation and variational algorithms return, and reach the dissipative and finite-temperature dynamics that a purely unitary language cannot.
Acknowledgments
RK was supported by the Independent Research Fund Denmark through Sapere Aude: DFF-Research Leader grant 5251-00024B, and the Norwegian Research Council through grant 361350. We would like thank Javaria Ghafoor for finding and correcting a bug in the compiler.
Data Availability Statement
The Haskell / Python implementation and the Agda verification are available at https://doi.org/10.5281/zenodo.23675392. The accompanying artifact also contains commands that rebuild every table and code listing the implementation.
Disclosure of Use in AI in Research
The code accompanying this paper was written by hand, with Claude generating parts of it in response to requests for specific rewrites. No generative AI was used for theory or proofs. The authors take full responsibility for all content, including the code.
References
References
- [1]S. Aaronson and D. Gottesman. 2004. Improved Simulation of Stabilizer Circuits. Physical Review A 70, 5 (2004), 052328. doi:10.1103/PhysRevA.70.052328DOI
- [3]J. Carette, C. Heunen, R. Kaarsgaard, N. J. Ross, and A. Sabry. 2026. Free quantum computing. Proceedings of the National Academy of Sciences 123, 8 (2026), e2510881123. doi:10.1073/pnas.2510881123DOI
- [4]J. Carette, C. Heunen, R. Kaarsgaard, and A. Sabry. 2024. With a Few Square Roots, Quantum Computing Is as Easy as Pi. Proceedings of the ACM on Programming Languages 8, POPL, Article 19 (2024). doi:10.1145/3632861
- [5]J. Carette and A. Sabry. 2016. Computing with Semirings and Weak Rig Groupoids. In Proceedings of the 25th European Symposium on Programming Languages and Systems - Volume 9632. Springer-Verlag, Berlin, Heidelberg, 123–148.DOI
- [6]A. Cowtan, S. Dilles, R. Duncan, W. Simmons, and S. Sivarajah. 2019. Phase Gadget Synthesis for Shallow Circuits. In Proceedings 16th International Conference on Quantum Physics and Logic (QPL) (Electronic Proceedings in Theoretical Computer Science, Vol. 318). 213–228. doi:10.4204/EPTCS.318.13DOI
- [8]L. Fajstrup, É. Goubault, E. Haucourt, S. Mimram, and M. Raussen. 2016. Directed Algebraic Topology and Concurrency. Springer. doi:10.1007/978-3-319-15398-8DOI
- [9]E. Farhi, J. Goldstone, and S. Gutmann. 2014. A Quantum Approximate Optimization Algorithm. (2014). arXiv:1411.4028.arxiv.org/abs/1411.4028
- [10]E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. 2001. A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem. Science 292, 5516 (2001), 472–475. doi:10.1126/science.1057726DOI
- [11]Richard P. Feynman. 1982. Simulating Physics with Computers. International Journal of Theoretical Physics 21, 6/7 (1982), 467–488. doi:10.1007/BF02650179DOI
- [12]A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. 2019. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing. 193–204.DOI
- [14]B. C. Hall. 2015. Lie Groups, Lie Algebras, and Representations (2nd ed.). Springer. doi:10.1007/978-3-319-13467-3DOI
- [15]R. P. James and A. Sabry. 2012. Information Effects. In Proceedings ACM Symposium on Principles of Programming Languages (POPL). 73–84. doi:10.1145/2103656.2103667DOI
- [16]A. Yu. Kitaev. 1995. Quantum measurements and the Abelian Stabilizer Problem. (1995). arXiv:quant-ph/9511026.
- [18]S. Lloyd. 1996. Universal quantum simulators. Science 273, 5278 (1996), 1073–1078. doi:10.1126/science.273.5278.1073 A Complete Calculus for Hamiltonian Quantum Programming
- [19]G. H. Low and I. L. Chuang. 2019. Hamiltonian Simulation by Qubitization. Quantum 3 (2019), 163. doi:10.22331/q-2019-07-12-163DOI
- [20]A. Mazurkiewicz. 1987. Trace Theory. In Petri Nets: Applications and Relationships to Other Models of Concurrency, Advances in Petri Nets 1986, Part II. Lecture Notes in Computer Science, Vol. 255. Springer, 279–324.
- [21]R. Milner. 2007. Elements of interaction. ACM, 1991. doi:10.1145/1283920.1283948
- [22]S. Owicki and D. Gries. 1976. An Axiomatic Proof Technique for Parallel Programs I. Acta Informatica 6, 4 (1976), 319–340. doi:10.1007/BF00268134DOI
- [23]Y. Peng, J. Young, P. Liu, and X. Wu. 2024. SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation. Proceedings of the ACM on Programming Languages 8, POPL, Article 81 (2024), 31 pages. doi:10.1145/3632923DOI
- [24]V. R. Pratt. 1991. Modeling Concurrency with Geometry. In Proceedings ACM Symposium on Principles of Programming Languages (POPL). 311–322. doi:10.1145/99583.99625DOI
- [25]P. Richerme, M. C. Revelle, C. G. Yale, D. Lobser, A. D. Burch, S. M. Clark, D. Saha, M. A. Lopez-Ruiz, A. Dwivedi, J. M. Smith, S. A. Norrell, A. Sabry, and S. S. Iyengar. 2023. Quantum Computation of Hydrogen Bond Dynamics and Vibrational Spectra. The Journal of Physical Chemistry Letters 14, 32 (2023), 7256–7263. arXiv:2204.08571 doi:10.1021/acs.jpclett.3c01601 PMID: 37555761.DOI
- [26]M. Suzuki. 1991. General theory of fractal path integrals with applications to many-body theories and statistical physics. J. Math. Phys. 32, 2 (1991), 400–407. doi:10.1063/1.529425DOI
- [27]H. F. Trotter. 1959. On the product of semi-groups of operators. Proc. Amer. Math. Soc. 10, 4 (1959), 545–551. doi:10.2307/2033649DOI
- [28]C. Yuan. 2025. Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra. Proceedings of the ACM on Programming Languages (2025). doi:10.1145/3808255DOI
