betaFeedback

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 m/2km/2^k, 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 Πk\Pi_k, 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 HH, its evolution is e−itHe^{-itH}, and the snapshot at a time tt is a gate. For example, the state of a qubit is a pair of amplitudes, written α∣0⟩+β∣1⟩\alpha\lvert0\rangle+ \beta\lvert1\rangle, and the Hamiltonian X=(0110)X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} drives ∣0⟩\lvert0\rangle along cos⁡t∣0⟩−isin⁡t∣1⟩\cos t\lvert0\rangle- i\sin t\lvert1\rangle, a wave that oscillates between ∣0⟩\lvert0\rangle and ∣1⟩\lvert1\rangle. At t=π/2t = \pi/2 the snapshot is the NOT gate, which swaps the two amplitudes, up to a global phase −i-i; 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 XX together with Z=(100−1)Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, whose snapshot at t=π/2t = \pi/2 is the phase-flip gate, taking α∣0⟩+β∣1⟩\alpha\lvert0\rangle+ \beta\lvert1\rangle to α∣0⟩−β∣1⟩\alpha|0\rangle-\beta|1\rangle. In Figure 1, time spent running XX is drawn horizontally in orange and time spent running ZZ 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 XZXZ and ZXZX, which differ only by an overall sign, so the order is unobservable. Run halfway, the order becomes observable. Write X\sqrt{X} and Z\sqrt{Z} for the half runs: X\sqrt{X} turns each amplitude into an even blend of the two, and Z\sqrt{Z} multiplies the second amplitude by ii, halfway around the circle from 11 to −1-1. From the initial state 12(∣0⟩+∣1⟩)\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle), the two evolutions proceed as:

Interleavings of $X$ and $Z$ at levels $n=0,\ldots,3$

Figure 1. Interleavings of XX and ZZ at levels n=0,…,3n=0,\ldots,3: orange steps run XX, blue steps run ZZ, and the dashed diagonal runs both at once. The path below the diagonal runs XX first, the path above runs ZZ 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.

12(∣0⟩+∣1⟩)→X12(∣0⟩+∣1⟩)→Z12(∣0⟩+i∣1⟩)12(∣0⟩+∣1⟩)→Z12(∣0⟩+i∣1⟩)→X∣0⟩\begin{aligned} \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)&\xrightarrow{\sqrt{X}}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\xrightarrow{\sqrt{Z}}\frac{1}{\sqrt{2}}(|0\rangle+i|1\rangle)\\ \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)&\xrightarrow{\sqrt{Z}}\frac{1}{\sqrt{2}}(|0\rangle+i|1\rangle)\xrightarrow{\sqrt{X}}|0\rangle \end{aligned}

In the first line, X\sqrt{X} blends equal amplitudes, which leaves them equal, and Z\sqrt{Z} then only turns the phase of the second. In the second, Z\sqrt{Z} first turns the amplitudes into 11 and ii, and X\sqrt{X} blends these so that their contributions to ∣1⟩|1\rangle cancel, leaving ∣0⟩|0\rangle. 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 XX and ZZ. 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 eA+Be^{A+B} as the limit of (eA/NeB/N)N(e^{A/N}e^{B/N})^N, a round-robin schedule that gives each term a time slice of 1/N1/N.

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 ∥\parallel, with no order among them, and denotes the sum of their Hamiltonians. Programs compile to circuits of the calculus Πk\Pi_k [3, 4]. This is an ideal target, as Πk\Pi_k extends the calculus Π\Pi of classical reversible computing [5, 15] with a square root of not and with the 2k2^k-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 nn times, for a chosen level nn, so that every duration in it is a dyadic rational (a fraction of the form m/2km/2^k for m∈Zm \in\mathbb{Z} and k∈Nk \in\mathbb{N}), and to unroll it into a schedule of 2n2^n Trotter steps, each a Πk\Pi_k circuit.

Outline. Section 2 gives background on Πk\Pi_k 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 HH, which is an operator on the state space of the system satisfying H†=HH^\dagger= H (with H†H^\dagger the conjugate transpose of HH). Solutions to this equation turn out to be given by families of operators U(t)=e−itHU(t) = e^{-itH} with tt 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 ii, the Hamiltonians themselves belong to the corresponding Lie algebra: a vector space together with a bilinear map [−,−][-,-], the Lie bracket, that satisfies alternation [x,x]=0[x,x] = 0 for all xx, and the Jacobi identity [x,[y,z]]+[z,[x,y]]+[y,[z,x]]=0[x,[y,z]] + [z,[x,y]] + [y,[z,x]] = 0 for all x,y,zx,y,z. Every Lie group is associated with a Lie algebra (and vice versa) via exponentiation and logarithms. Quintessential examples are the Lie group U(2n)U(2^n) of 2n2^n-by-2n2^n unitary matrices, with associated Lie algebra u(2n)\mathfrak{u}(2^n).

Free Quantum Computing. Hamilton compiles to circuits of Πk\Pi_k, the free model of quantum computing [3, 4], so we begin there. Its ancestor Π\Pi is a calculus of type isomorphisms: in the standard model, types are finite sets built from 00, 11, sums and products, a term is a permutation of their elements [5, 15], and the calculus is sound and complete for reversible classical computation. Πk\Pi_k adds ∨\vee, a square root of not, and the scalar phase ζk=e2πi/2k\zeta_k = e^{2\pi i/2^k}, the principal 2k2^k-th root of unity, so that ζ2=i\zeta_2 = i. With these extensions, the language becomes complete for quantum computing with terms denoting unitary matrices. The index kk can be any positive integer: since ζk=ζk+12\zeta_k = \zeta_{k+1}^2, each Πk\Pi_k embeds in Πk+1\Pi_{k+1}. The equational theory of Πk\Pi_k 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 ∣0⟩|0\rangle and ∣1⟩|1\rangle at the poles and the states with even split probabilities 12(∣0⟩+eiϕ∣1⟩)\frac{1}{\sqrt{2}}(|0\rangle+ e^{i\phi}|1\rangle) around the equator. Running the Hamiltonian ZZ rotates around the ZZ axis, i.e., turns the sphere about the axis through the poles, which changes only the phase ϕ\phi; running the Hamiltonian XX turns it about an axis through the equator, which moves states between the poles. Running both at once, X+ZX+Z 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 ZZ-rotation followed by one long XX-rotation produces a trajectory that is quite far from the great circle. Alternating four short turns about XX and ZZ follows that great circle more closely (Figure 2). In the limit, the alternation defined by the Lie-Trotter product formula [27]

The example of Section 2 on the sphere of one-qubit states

Figure 2. The example of § 2 on the sphere of one-qubit states, drawn with ZZ up, XX to the left and YY towards the reader. From the marked start, e−iθ(X+Z)e^{-i\theta(X+Z)} for θ∈[0,π/4]\theta\in[0,\pi/4] turns about the axis of X+ZX+Z along a great circle (thick), crossing the equator. One turn about ZZ followed by one about XX ends far from it (dashed); four alternating turns of a quarter the size stay close all the way (blue).

e−i(A+B)=lim⁡n→∞(e−iA/ne−iB/n)n(1)e^{-i(A+B)}=\lim_{n\to\infty}\left(e^{-iA/n}e^{-iB/n}\right)^n \tag*{(1)}

converges to the great circle perfectly.

X+ZX+Z is a Hamiltonian, and Figure 2 runs it for a chosen angle, following e−iθ(X+Z)e^{-i\theta(X+Z)} up to θ=π/4\theta=\pi/4. A Hamilton program builds the angle into its Hamiltonian instead: a program with Hamiltonian HH runs it for one unit, as the unitary e−2πiHe^{-2\pi iH}. The motion of Figure 2, e−i(π/4)(X+Z)e^{-i(\pi/4)(X+Z)}, is therefore the program with Hamiltonian (X+Z)/8(X+Z)/8, written with the phases and gates of Πk\Pi_k as the parallel composition x∥zx\mathbin{\|}z of the two actions

x=H(δ3⊕−δ3)H†andz=δ3⊕−δ3.x=\mathrm{H}(\delta_3\oplus-\delta_3)\mathrm{H}^{\dagger}\qquad\text{and}\qquad z=\delta_3\oplus-\delta_3.

Here δ3\delta_3 is the 1-by-1 Hamiltonian 1/8, whose unitary is the Π3\Pi_3 phase ζ3\zeta_3, so zz, a direct sum, is the diagonal Z/8Z/8; conjugating it by the Hadamard gate H\mathrm{H} gives xx, which is X/8X/8; and ∥\mathbin{\|} adds the two. The index 3 is the precision: running an action for half as long replaces δ3\delta_3 by δ4\delta_4, a phase of Π4\Pi_4.

Every Hamiltonian in Hamilton has this form. On nn qubits it is a real weighted sum of Pauli strings, tensor products of nn matrices drawn from II, XX, Y=iXZY=iXZ and ZZ, 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 kk, 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 x∥zx\mathbin{\|}z are [x,z][x,z] and [z,x][z,x] (which are lists, not to be confused with the Lie bracket). At level nn, a schedule runs each action for 1/2n1/2^n of the time, so that δ3\delta_3 becomes δ3+n\delta_{3+n} and repeats 2n2^n times; Figure 2 draws [z,x][z,x] 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 zz by two copies of its half, δ4⊕−δ4\delta_4 \oplus-\delta_4; it asks for equations between Πk\Pi_k circuits, and the full abstraction of Πk\Pi_k 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 δk\delta_k runs at rate 1/2k1/2^k, its opposite −δk-\delta_k at rate −1/2k-1/2^k, 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 δk\delta_k gives δk+1\delta_{k+1}, every slice is again made of scalars. Every scalar also compiles exactly: running δk\delta_k for one unit of time multiplies by a 2k2^k-th root of unity, which Πk\Pi_k provides. Placing scalars side by side along a diagonal, with the direct sum ⊕\oplus, gives a bare action. For instance, the action zz of Section 2 places δ3\delta_3 beside −δ3-\delta_3, rotating the phase of ∣0⟩\lvert0\rangle by an eighth of a circle in one direction and that of ∣1⟩\lvert1\rangle by an eighth in the other; its Hamiltonian is Z/8Z/8.

A bare action only rotates the phases of the basis vectors. To drive ∣0⟩\lvert0\rangle towards ∣1⟩\lvert1\rangle, as XX 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 xx of Section 2 runs zz in the basis of the Hadamard gate, which makes its Hamiltonian X/8X/8. 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 II and ZZ 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 x∥zx \mathbin{\|} z of Section 2 is such a process, with Hamiltonian (X+Z)/8(X+Z)/8.

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.

The syntax and type system of Hamilton

Figure 3. The syntax and type system of Hamilton. Types are positive integers n,m∈Z+n,m \in\mathbb{Z}_+ 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 diag⁡(1,i)\operatorname{diag}(1,i).

Halving extends from scalars to every process, running it for 1/2n1/2^n of its duration.

Definition 1. The nn-way halving p/2np/2^n of a process pp is given by 0/2n=00/2^n = 0, δk/2n=δk+n\delta_k/2^n = \delta_{k+n} and −δk/2n=−δk+n-\delta_k/2^n = -\delta_{k+n}, and commutes with the other constructs: (d⊕d′)/2n=d/2n⊕d′/2n(d \oplus d')/2^n = d/2^n \oplus d'/2^n, (uau†)/2n=u(a/2n)u†(uau^\dagger)/2^n = u(a/2^n)u^\dagger and (p∥p′)/2n=p/2n∥p′/2n(p \mathbin{\|} p')/2^n = p/2^n \mathbin{\|} p'/2^n.

Derived forms

The core syntax is minimal, and examples use a few shorthands that expand into it. We write 0n0_n for the action 0⊕⋯⊕00 \oplus\cdots\oplus0 of type nn, and ∥i=1npi\mathbin{\|}_{i=1}^n p_i for p1∥⋯∥pnp_1 \mathbin{\|} \cdots\mathbin{\|} p_n, which needs no parentheses since ∥\mathbin{\|} is associative (Theorem 7). Conjugating a composite process conjugates each part, u(∥ipi)u†=∥iupiu†u\left(\mathbin{\|}_{i} p_i\right)u^\dagger= \mathbin{\|}_{i} up_i u^\dagger. Repetition n⋆p=∥i=1npn \star p = \mathbin{\|}_{i=1}^n p, combined with halving, multiplies a process by a positive dyadic rational, n2m⋆p=n⋆(p/2m)\frac{n}{2^m} \star p = n \star(p/2^m); every process pp has an inverse −p-p (Theorem 8), and −n2m⋆p=n⋆((−p)/2m)-\frac{n}{2^m} \star p = n \star((-p)/2^m).

Tensor products of actions build Pauli strings. On scalars, δk⊗δm=δk+m\delta_k \otimes\delta_m = \delta_{k+m}, with signs multiplying as for numbers, and d⊗0=0⊗d=0d \otimes0 = 0 \otimes d = 0. On bare actions ⊗\otimes distributes over ⊕\oplus, (⨁idi)⊗(⨁jdj′)=⨁i⨁jdi⊗dj′\left(\bigoplus_i d_i\right) \otimes\left(\bigoplus_j d'_j\right) = \bigoplus_i \bigoplus_j d_i \otimes d'_j, and on actions it tensors the transformations and the bare actions separately, uau†⊗vbv†=(u⊗v)(a⊗b)(u⊗v)†uau^\dagger\otimes vbv^\dagger= (u \otimes v)(a \otimes b)(u \otimes v)^\dagger, padding a bare action with the identity transformation I. For example, with Z=δ0⊕−δ0Z = \delta_0 \oplus-\delta_0 and X=HZH†X = HZH^\dagger,

Z⊗X=(I⊗H)(δ0⊕−δ0⊕−δ0⊕δ0)(I⊗H)†Z \otimes X = (I \otimes H)(\delta_0 \oplus-\delta_0 \oplus-\delta_0 \oplus\delta_0)(I \otimes H)^\dagger

which denotes the Pauli string Z⊗XZ \otimes X (§ 4). Weighting Pauli strings by dyadic rationals approximates any Hamiltonian, since the dyadic rationals are dense in the reals: with I=δ0⊕δ0I = \delta_0 \oplus\delta_0, the two-qubit Hamiltonian aI⊗X+bX⊗I+cZ⊗Za I \otimes X + b X \otimes I + c Z \otimes Z with real weights is approximated by (n12m1⋆I⊗X)∥(n22m2⋆X⊗I)∥(n32m3⋆Z⊗Z)\left(\frac{n_1}{2^{m_1}} \star I \otimes X\right) \mathbin{\|} \left(\frac{n_2}{2^{m_2}} \star X \otimes I\right) \mathbin{\|} \left(\frac{n_3}{2^{m_3}} \star Z \otimes Z\right), with each ni2mi\frac{n_i}{2^{m_i}} 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

⟦∣∣⟧Π=id2\llbracket\mathord{||} \rrbracket_{\Pi} = \mathrm{id}_{2}
⟦H⟧Π=ζ3†∙V(id1+ζ2)V\llbracket H \rrbracket_{\Pi} = \zeta_{3}^{\dagger} \mathbin{\bullet} V(\mathrm{id}_{1}+\zeta_{2})V
⟦S⟧Π=id1+ζ2\llbracket S \rrbracket_{\Pi} = \mathrm{id}_{1}+\zeta_{2}
⟦CX⟧Π=id2+X\llbracket CX \rrbracket_{\Pi} = \mathrm{id}_{2}+X
⟦SWAP⟧Π=σ×\llbracket SWAP \rrbracket_{\Pi} = \sigma_{\times}
⟦u⋅v⟧Π=⟦u⟧Π⟦v⟧Π\llbracket u\mathbin{\cdot}v \rrbracket_{\Pi} = \llbracket u \rrbracket_{\Pi}\llbracket v \rrbracket_{\Pi}
⟦u⊗v⟧Π=⟦u⟧Π×⟦v⟧Π\llbracket u\otimes v \rrbracket_{\Pi} = \llbracket u \rrbracket_{\Pi}\times\llbracket v \rrbracket_{\Pi}

Actions

⟦0⟧Π=id1\llbracket0 \rrbracket_{\Pi} = \mathrm{id}_{1}
⟦δk⟧Π=ζk†\llbracket\delta_k \rrbracket_{\Pi} = \zeta_k^{\dagger}
⟦−δk⟧Π=ζk\llbracket-\delta_k \rrbracket_{\Pi} = \zeta_k
⟦d⊕d′⟧Π=⟦d⟧Π+⟦d′⟧Π\llbracket d\oplus d' \rrbracket_{\Pi} = \llbracket d \rrbracket_{\Pi}+\llbracket d' \rrbracket_{\Pi}
⟦uau†⟧Π=⟦u⟧Π⟦a⟧Π⟦u⟧Π†\llbracket u a u^{\dagger} \rrbracket_{\Pi} = \llbracket u \rrbracket_{\Pi}\llbracket a \rrbracket_{\Pi}\llbracket u \rrbracket_{\Pi}^{\dagger}

fig:4. The interpretation of Hamilton transformations and actions as terms in the complete calculus of sequential quantum programs Πk\Pi_k. Terms of Πk\Pi_k compose in sequence by juxtaposition, and by direct sum ++ and tensor product ×\times; idn\mathrm{id}_n is the identity on nn elements, and 2=1+12=1+1 is a qubit; XX exchanges the two summands of 22 (the not gate) and σ×\sigma_{\times} the two factors of a product, matching the XX and σ⊗\sigma_{\otimes} of Carette et al. [ [3]; V=12(1+i1−i1−i1+i)V=\frac{1}{2}\begin{pmatrix}1+i&1-i\\1-i&1+i\end{pmatrix} is the square root of not; ζk=e2πi/2k\zeta_k=e^{2\pi i/2^k} is a scalar, ∙\bullet multiplies by a scalar, and (−)†(-)^{\dagger} inverts. Since ⟦δk⟧U=e−2πi/2k\llbracket\delta_k\rrbracket_U=e^{-2\pi i/2^k}, the action δk\delta_k becomes ζk†\zeta_k^{\dagger}.

Definition 2. A schedule is a list of actions [a1,…,am][a_1,\ldots,a_m]. The schedule of a process lists its actions, sch⁡(a)=[a]\operatorname{sch}(a)=[a] and sch⁡(q∥r)=sch⁡(q)@sch⁡(r)\operatorname{sch}(q\mathbin{\|}r)=\operatorname{sch}(q)@\operatorname{sch}(r), where @ concatenates lists, and halving acts on schedules element-wise, [a1,…,am]/2n=[a1/2n,…,am/2n][a_1,\ldots,a_m]/2^n=[a_1/2^n,\ldots,a_m/2^n].

Equating schedules needs the sequential behaviour of actions, and Πk\Pi_k is a complete calculus for sequential quantum programs: Hamilton actions are exactly representable as Πk\Pi_k terms by the function ⟦−⟧Π\llbracket-\rrbracket_{\Pi} of Figure 4. With this in hand, we are ready to define schedule equivalence:

Definition 3. Define schedule equivalence ∼\sim as the least equivalence relation satisfying the following:

[a1,a2,…,am]∼[aσ(1),aσ(2),…,aσ(m)][a_1,a_2,\ldots,a_m]\sim[a_{\sigma(1)},a_{\sigma(2)},\ldots,a_{\sigma(m)}]
[a1,…,aj−1,aj,aj+1,…,am]∼[a1,…,aj−1,b1,…,bl,aj+1,…,am][a_1,\ldots,a_{j-1},a_j,a_{j+1},\ldots,a_m]\sim[a_1,\ldots,a_{j-1},b_1,\ldots,b_l,a_{j+1},\ldots,a_m]

where in (R1), σ\sigma is any permutation of mm elements, and (R2) can be applied iff there exist actions b1,…,blb_1,\ldots,b_l and a proof in Πk\Pi_k that ⟦aj/2n⟧Π=⟦b1/2n⟧Π⋯⟦bl/2n⟧Π\llbracket a_j/2^n\rrbracket_{\Pi}=\llbracket b_1/2^n\rrbracket_{\Pi}\cdots\llbracket b_l/2^n\rrbracket_{\Pi} for all n∈Nn\in\mathbb{N}.

Definition 4. Define process equivalence ≈\approx as p≈p′p\approx p' if and only if sch⁡(p)∼sch⁡(p′)\operatorname{sch}(p)\sim\operatorname{sch}(p').

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 ∥\mathbin{\|}; 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 δ0⊕0\delta_0\oplus0 turns the phase of ∣1⟩|1\rangle once around the circle, so its unitary is the identity, like that of 0⊕00\oplus0. parallel with the process H(δ2⊕−δ2)HH(\delta_2 \oplus-\delta_2)H, whose Hamiltonian is X/4X/4, the two differ: started in ∣0⟩\lvert0\rangle, the composition with 0⊕00 \oplus0 ends in ∣1⟩\lvert1\rangle with probability 1.000, and the composition with δ0⊕0\delta_0 \oplus0 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 x:=x+1; x:=x−1x := x+1; \ x := x-1 have the same input-output behaviour, yet a concurrent y:=xy := x 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 ≈\approx is an equivalence relation.

Proof. Immediate, since ∼\sim is an equivalence relation by construction. □

Proposition 6. Process equivalence is congruent under ∥\parallel: p≈p′p \approx p' implies p∥q≈p′∥qp \parallel q \approx p' \parallel q and similarly on the right.

Proof. Suppose that p≈p′p \approx p', i.e., sch⁡(p)∼sch⁡(p′)\operatorname{sch}(p) \sim\operatorname{sch}(p'), and let qq be some other process. By definition sch⁡(p∥q)=sch⁡(p)@sch⁡(q)\operatorname{sch}(p \parallel q) = \operatorname{sch}(p) @ \operatorname{sch}(q). That sch⁡(p)∼sch⁡(p′)\operatorname{sch}(p) \sim\operatorname{sch}(p') means sch⁡(p)\operatorname{sch}(p) can be turned into sch⁡(p′)\operatorname{sch}(p') by a sequence of applications of the permutation and/or the substitution rule. But these can be directly extended to applications on sch⁡(p∥q)=sch⁡(p)@sch⁡(q)\operatorname{sch}(p \parallel q) = \operatorname{sch}(p) @ \operatorname{sch}(q) 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 sch⁡(p∥q)∼sch⁡(p′∥q)\operatorname{sch}(p \parallel q) \sim\operatorname{sch}(p' \parallel q), so p∥q≈p′∥qp \parallel q \approx p' \parallel q. The analogous argument applies on the other side. □

Proposition 7. Up to process equivalence, the set of Hamilton processes of type nn forms a commutative monoid with ∥\parallel as composition and 0n0_n as identity.

Proposition 8. Every process p:np : n has an inverse process −p:n-p : n such that p∥(−p)≈0np \parallel(-p) \approx0_n.

Process equivalence is defined by rules on syntax, but rule (R2) brings in the semantics through Πk\Pi_k. Its side condition asks for a proof in Πk\Pi_k, and such a proof exists exactly when both sides denote the same unitary after every halving, because the equational theory of Πk\Pi_k is complete [3]. This is what provides inverses: the inverse −a-a of an action negates its scalars, so that ⟦(−a)/2n⟧Π=⟦a/2n⟧Π†\llbracket(-a)/2^n\rrbracket_{\Pi} = \llbracket a/2^n\rrbracket_{\Pi}^{\dagger} for every nn, and rule (R2) rewrites the schedule [0n][0_n] into [a,−a][a,-a], as the supplementary material demonstrates.

Corollary 9. Up to process equivalence, the set of Hamilton processes of type nn forms an abelian group with ∥\parallel as composition and 0n0_n 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 mm and in the limit as m→∞m \to\infty. In fact, we will do all four things, and discuss how these relate.

Unitary transformations

⟦I⟧U=(1001)⟦H⟧U=12(111−1)⟦S⟧U=(100i)\llbracket\mathbb{I} \rrbracket_U = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \qquad \llbracket H \rrbracket_U = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \qquad \llbracket S \rrbracket_U = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}
⟦CX⟧U=(1000010000010010)⟦SWAP⟧U=(1000001001000001)\llbracket\mathrm{CX} \rrbracket_U = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \qquad \llbracket\mathrm{SWAP} \rrbracket_U = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}
⟦u⋅v⟧U=⟦u⟧U⟦v⟧U⟦u⊗v⟧U=⟦u⟧U⊗⟦v⟧U\llbracket u \cdot v \rrbracket_U = \llbracket u \rrbracket_U \llbracket v \rrbracket_U \qquad \llbracket u \otimes v \rrbracket_U = \llbracket u \rrbracket_U \otimes\llbracket v \rrbracket_U

Hamiltonian actions

⟦0⟧H=(0)⟦δk⟧H=(12k)⟦−δk⟧H=(−12k)\llbracket0 \rrbracket_H = (0) \qquad \llbracket\delta_k \rrbracket_H = \begin{pmatrix} \frac{1}{2^k} \end{pmatrix} \qquad \llbracket-\delta_k \rrbracket_H = \begin{pmatrix} -\frac{1}{2^k} \end{pmatrix}
⟦d⊕d′⟧H=⟦d⟧H⊕⟦d′⟧H⟦uau†⟧H=⟦u⟧U⟦a⟧H⟦u⟧U†\llbracket d \oplus d' \rrbracket_H = \llbracket d \rrbracket_H \oplus\llbracket d' \rrbracket_H \qquad \llbracket u a u^\dagger\rrbracket_H = \llbracket u \rrbracket_U \llbracket a \rrbracket_H \llbracket u \rrbracket_U^\dagger

Schedules

⟦[a1,…,ak]⟧U=∏j=1k⟦aj⟧U\llbracket[a_1,\ldots,a_k] \rrbracket_U = \prod_{j=1}^{k} \llbracket a_j \rrbracket_U

Processes

⟦∥j=1npj⟧H=∑j=1n⟦pj⟧H⟦p⟧U=exp⁡(−2πi⟦p⟧H)\llbracket\mathop{\|}_{j=1}^{n} p_j \rrbracket_H = \sum_{j=1}^{n} \llbracket p_j \rrbracket_H \qquad \llbracket p \rrbracket_U = \exp\left(-2\pi i\llbracket p \rrbracket_H\right)
⟦p⟧Sm=⟦sch⁡(p)/2m⟧U⟦p⟧S∞=lim⁡m→∞⟦p⟧Sm\llbracket p \rrbracket_{S_m} = \llbracket\operatorname{sch}(p)/2^m \rrbracket_U \qquad \llbracket p \rrbracket_{S_\infty} = \lim_{m\to\infty}\llbracket p \rrbracket_{S_m}

We define the unitary semantics ⟦−⟧U\llbracket-\rrbracket_U, the Hamiltonian semantics ⟦−⟧H\llbracket-\rrbracket_H, and the approximate schedule semantics ⟦−⟧Sm\llbracket-\rrbracket_{S_m} at level m∈Nm \in\mathbb{N}, and the limit schedule semantics ⟦−⟧S∞\llbracket-\rrbracket_{S_\infty} 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 UHU†UHU^\dagger is Hermitian whenever UU is unitary and HH is Hermitian since

Semantics of transformations, actions, schedules, and processes

Figure 5. The Hamiltonian semantics ⟦−⟧H\llbracket-\rrbracket_H, unitary semantics ⟦−⟧U\llbracket-\rrbracket_U, approximate schedule semantics ⟦−⟧Sm\llbracket-\rrbracket_{S_m} at level m∈Nm \in\mathbb{N}, and limit schedule semantics ⟦−⟧S∞\llbracket-\rrbracket_{S_\infty} of processes. On matrices MM and NN, M⊕NM \oplus N denotes the block diagonal matrix which has MM and NN as diagonal blocks (in that order) and zeros everywhere else, while M⊗NM \otimes N denotes the Kronecker product of MM and NN.

(UHU†)†=U††H†U†=UHU†\left(UHU^\dagger\right)^\dagger= U^{\dagger\dagger}H^\dagger U^\dagger= UHU^\dagger

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: ⟦p⟧H=⟦q⟧H\llbracket p \rrbracket_H = \llbracket q \rrbracket_H implies ⟦p⟧U=⟦q⟧U\llbracket p \rrbracket_U = \llbracket q \rrbracket_U but not vice versa.

Proof. If ⟦p⟧H=⟦q⟧H\llbracket p \rrbracket_H = \llbracket q \rrbracket_H then by definition ⟦p⟧U=exp⁡(−2πi⟦p⟧H)=exp⁡(−2πi⟦q⟧H)=⟦q⟧U\llbracket p \rrbracket_U = \exp(-2\pi i\llbracket p \rrbracket_H) = \exp(-2\pi i\llbracket q \rrbracket_H) = \llbracket q \rrbracket_U. The converse implication does not hold since exponentiation mods out eigenvalues by 2π2\pi: e.g., ⟦δ0⟧U=exp⁡(−2πi⟦δ0⟧H)=exp⁡(−2πi)=1=exp⁡(0)=⟦0⟧U\llbracket\delta_0 \rrbracket_U = \exp(-2\pi i\llbracket\delta_0 \rrbracket_H) = \exp(-2\pi i) = 1 = \exp(0) = \llbracket0 \rrbracket_U. □

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 pp, ⟦p/2m⟧H=⟦p⟧H/2m\llbracket p/2^m\rrbracket_H=\llbracket p\rrbracket_H/2^m.

Proof sketch. By straightforward algebraic manipulation. □

Proposition 12. For all processes pp, ⟦p⟧S∞=⟦p⟧U\llbracket p\rrbracket_{S_\infty}=\llbracket p\rrbracket_U.

Proof. By definition a process pp is of the form p=∥j=1najp=\mathbin{\|}_{j=1}^{n}a_j for actions aja_j up to a choice of bracketing, but since ∥\mathbin{\|} is fully associative on the nose in its schedule semantics, this choice is semantically irrelevant in that sch⁡(p)/2m=[a1/2m,a2/2m,…,an/2m]\operatorname{sch}(p)/2^m=[a_1/2^m,a_2/2^m,\ldots,a_n/2^m] regardless. Then

\begin{aligned} \llbracket p\rrbracket_{S_\infty} &=\lim_{m\to\infty}\left\llbracket\mathop{\|}_{j=1}^{n}a_j\right\rrbracket_{S_m}\\ &=\lim_{m\to\infty}\llbracket\operatorname{sch}(p)/2^m\rrbracket_U^{2^m}\\ &=\lim_{m\to\infty}\left(\prod_{j=1}^{n}\llbracket a_j/2^m\rrbracket_U\right)^{2^m}\\ &=\lim_{m\to\infty}\left(\prod_{j=1}^{n}\exp(-2\pi i\llbracket a_j/2^m\rrbracket_H)\right)^{2^m}\\ &=\lim_{m\to\infty}\left(\prod_{j=1}^{n}\exp(-2\pi i\llbracket a_j\rrbracket_H/2^m)\right)^{2^m}\\ &=\exp\left(-2\pi i\sum_{j=1}^{n}\llbracket a_j\rrbracket_H\right)\\ &=\exp\left(-2\pi i\llbracket\mathop{\|}_{j=1}^{n}a_j\rrbracket_H\right)\\ &=\exp(-2\pi i\llbracket p\rrbracket_H)\\ &=\llbracket p\rrbracket_U \end{aligned}

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 mm-level schedule semantics, since these are not exact but approximate semantics. That is, ⟦p⟧Sm\llbracket p\rrbracket_{S_m} does not correspond to the true semantics of pp, merely an approximation only given access to subdivisions of pp of size 2m2^m. As such, we cannot expect ⟦p⟧S∞=⟦q⟧S∞\llbracket p\rrbracket_{S_\infty}=\llbracket q\rrbracket_{S_\infty} to imply ⟦p⟧Sm=⟦q⟧Sm\llbracket p\rrbracket_{S_m}=\llbracket q\rrbracket_{S_m} since the latter could be false simply due to ⟦p⟧Sm\llbracket p\rrbracket_{S_m} and ⟦q⟧Sm\llbracket q\rrbracket_{S_m} 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 m∈Nm\in\mathbb{N}: ⟦p⟧S∞=⟦q⟧S∞\llbracket p\rrbracket_{S_\infty}=\llbracket q\rrbracket_{S_\infty} implies that ∥⟦p⟧Sm−⟦q⟧Sm∥→0\lVert\llbracket p\rrbracket_{S_m}-\llbracket q\rrbracket_{S_m}\rVert\to0 as m→∞m\to\infty, where ∥⋅∥\lVert\cdot\rVert is the operator norm.

Proof idea. Use that ⟦p⟧Sm=⟦sch⁡(p)/2m⟧U2m\llbracket p\rrbracket_{S_m} = \llbracket\operatorname{sch}(p)/2^m\rrbracket_U^{2^m} and ⟦q⟧Sm=⟦sch⁡(q)/2m⟧U2m\llbracket q\rrbracket_{S_m} = \llbracket\operatorname{sch}(q)/2^m\rrbracket_U^{2^m} both converge to ⟦p⟧S∞=⟦q⟧S∞.\llbracket p\rrbracket_{S_\infty} = \llbracket q\rrbracket_{S_\infty}.

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 pp and qq, p≈qp \approx q implies ⟦p⟧H=⟦q⟧H\llbracket p\rrbracket_H = \llbracket q\rrbracket_H.

Proof. We start by noticing that if pp has the schedule [a1,…,ak][a_1,\ldots,a_k] then ⟦p⟧H=∑j=1k⟦aj⟧H\llbracket p\rrbracket_H = \sum_{j=1}^{k}\llbracket a_j\rrbracket_H. 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 ⟦p⟧H=⟦q⟧H\llbracket p\rrbracket_H = \llbracket q\rrbracket_H directly. In the inductive case, we assume that all proofs using nn applications of (R1) and (R2) are sound, and must show that all proofs using n+1n+1 applications are sound, too. This yields two cases depending on which rule is applied. If the final rule is (R1) by some permutation σ\sigma, then ∑j=1k⟦aj⟧H=∑j=1k⟦aσ(j)⟧H\sum_{j=1}^{k}\llbracket a_j\rrbracket_H = \sum_{j=1}^{k}\llbracket a_{\sigma(j)}\rrbracket_H since summation is commutative. If the final rule is (R2), notice first that exp⁡(−2πi⟦p⟧H)=exp⁡(−2πi⟦q⟧H)\exp(-2\pi i\llbracket p\rrbracket_H)=\exp(-2\pi i\llbracket q\rrbracket_H) iff ⟦p⟧H=⟦q⟧H\llbracket p\rrbracket_H = \llbracket q\rrbracket_H when ∥⟦p⟧H∥,∥⟦q⟧H∥<12\lVert\llbracket p\rrbracket_H\rVert,\lVert\llbracket q\rrbracket_H\rVert< \frac{1}{2} (where ∥⋅∥\lVert\cdot\rVert denotes the operator norm), since the function x↦exp⁡(−ix)x\mapsto\exp(-ix) is bijective on the half-open interval [−π,π)[-\pi,\pi). Further, we remark that ⟦p⟧H=⟦q⟧H\llbracket p\rrbracket_H = \llbracket q\rrbracket_H iff α⟦p⟧H=α⟦q⟧H\alpha\llbracket p\rrbracket_H=\alpha\llbracket q\rrbracket_H for (real) nonzero α\alpha, so by choosing mm to be sufficiently large, we have that ⟦p/2m⟧H=⟦p⟧H/2m=⟦q⟧H/2m=⟦q/2m⟧H\llbracket p/2^m\rrbracket_H=\llbracket p\rrbracket_H/2^m=\llbracket q\rrbracket_H/2^m=\llbracket q/2^m\rrbracket_H iff ⟦p/2m⟧U=⟦q/2m⟧U\llbracket p/2^m\rrbracket_U=\llbracket q/2^m\rrbracket_U. Suppose now that ⟦a/2m⟧Π=⟦b1/2m⟧Π⋯⟦bk/2m⟧Π\llbracket a/2^m\rrbracket_\Pi=\llbracket b_1/2^m\rrbracket_\Pi\cdots\llbracket b_k/2^m\rrbracket_\Pi for all mm, and choose nn such that both ∥⟦a⟧H∥/2n<12\lVert\llbracket a\rrbracket_H\rVert/2^n<\frac{1}{2} and ∥∑j=1k⟦bj⟧H∥/2n<12\lVert\sum_{j=1}^{k}\llbracket b_j\rrbracket_H\rVert/2^n<\frac{1}{2}. Then

exp⁡(−2πi⟦a⟧H/2n)=lim⁡m→∞exp⁡(−2πi⟦a⟧H/2n)=lim⁡m→∞exp⁡(−2πi⟦a/2n⟧H)=lim⁡m→∞(exp⁡(−2πi⟦a/2n⟧H/2m))2m=lim⁡m→∞(exp⁡(−2πi⟦a/2n+m⟧H))2m=lim⁡m→∞⟦a/2n+m⟧U2m=lim⁡m→∞(∏j=1k⟦bj/2n+m⟧U)2m=lim⁡m→∞(∏j=1kexp⁡(−2πi⟦bj/2m+n⟧H))2m=lim⁡m→∞(∏j=1kexp⁡(−2πi⟦bj⟧H/2m+n))2m=exp⁡(−2πi(∑j=1k⟦bj⟧H)/2n)\begin{aligned} \exp(-2\pi i\llbracket a\rrbracket_H/2^n) &= \lim_{m\to\infty}\exp(-2\pi i\llbracket a\rrbracket_H/2^n) \\ &= \lim_{m\to\infty}\exp(-2\pi i\llbracket a/2^n\rrbracket_H) \\ &= \lim_{m\to\infty}\left(\exp(-2\pi i\llbracket a/2^n\rrbracket_H/2^m)\right)^{2^m} \\ &= \lim_{m\to\infty}\left(\exp(-2\pi i\llbracket a/2^{n+m}\rrbracket_H)\right)^{2^m} \\ &= \lim_{m\to\infty}\llbracket a/2^{n+m}\rrbracket_U^{2^m} \\ &= \lim_{m\to\infty}\left(\prod_{j=1}^{k}\llbracket b_j/2^{n+m}\rrbracket_U\right)^{2^m} \\ &= \lim_{m\to\infty}\left(\prod_{j=1}^{k}\exp(-2\pi i\llbracket b_j/2^{m+n}\rrbracket_H)\right)^{2^m} \\ &= \lim_{m\to\infty}\left(\prod_{j=1}^{k}\exp(-2\pi i\llbracket b_j\rrbracket_H/2^{m+n})\right)^{2^m} \\ &= \exp\left(-2\pi i\left(\sum_{j=1}^{k}\llbracket b_j\rrbracket_H\right)/2^n\right) \end{aligned}

using the fact that ⟦p/2n⟧H=⟦p⟧H/2n\llbracket p/2^n\rrbracket_H=\llbracket p\rrbracket_H/2^n for all pp and nn by Lemma 11, soundness of Πk\Pi_k (so that ⟦u⟧Π=⟦v⟧Π\llbracket u\rrbracket_\Pi=\llbracket v\rrbracket_\Pi implies ⟦u⟧U=⟦v⟧U\llbracket u\rrbracket_U=\llbracket v\rrbracket_U), and the Lie-Trotter product formula for the final limit. Since both ⟦a⟧H/2n\llbracket a\rrbracket_H/2^n and ∑j=1k⟦bj⟧H/2n\sum_{j=1}^{k}\llbracket b_j\rrbracket_H/2^n have norm below 12\frac{1}{2}, it follows that ⟦a⟧H/2n=∑j=1k⟦bj⟧H/2n\llbracket a\rrbracket_H/2^n=\sum_{j=1}^{k}\llbracket b_j\rrbracket_H/2^n, so ⟦a⟧H=∑j=1k⟦bj⟧H.\llbracket a\rrbracket_H=\sum_{j=1}^{k}\llbracket b_j\rrbracket_H.

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 Cm\mathbb{C}^{m} form a real vector space H(m)\mathcal{H}(m) of dimension m2m^{2}. Focusing, as is commonly done, on the qubit case where m=2nm=2^{n}, a convenient basis for H(2n)\mathcal{H}(2^{n}) is given by the Pauli strings. We show that Hamilton can express essentially all Hamiltonians in H(2n)\mathcal{H}(2^{n}), by showing that Hamilton processes of type 2n2^{n} are in a semantic one-to-one correspondence with Hamiltonians in H(2n)\mathcal{H}(2^{n}) whose Pauli coefficients fall in the ring Z[12]\mathbb{Z}[\frac{1}{2}] 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 H(2n)\mathcal{H}(2^{n}) 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 p:2np : 2^{n}, ⟦p⟧H\llbracket p \rrbracket_{H} has Pauli coefficients in the ring Z[12]\mathbb{Z}[\frac{1}{2}] of dyadic rationals.

Proof. Let p=∥jajp = \mathbin{\|}_{j} a_{j} for actions aja_{j}, so ⟦p⟧H=∥j⟦aj⟧H=∑j⟦aj⟧H\llbracket p \rrbracket_{H} = \mathbin{\|}_{j} \llbracket a_{j} \rrbracket_{H} = \sum_{j} \llbracket a_{j} \rrbracket_{H}, and it suffices to show that each aja_{j} has Pauli coefficients in the dyadic rationals.

If aja_{j} is a bare action then ⟦aj⟧H\llbracket a_{j} \rrbracket_{H} is a diagonal matrix with entries of the form ⟦0⟧H=0\llbracket0 \rrbracket_{H}=0, ⟦δk⟧H=12k\llbracket\delta_{k} \rrbracket_{H}=\frac{1}{2^{k}}, or ⟦−δk⟧H=−12k\llbracket-\delta_{k} \rrbracket_{H}=-\frac{1}{2^{k}}, which are all dyadic rational. This diagonal matrix can be expressed as a sum of Pauli strings with only ZZ and II factors using the fact that

12(Z+I)=12((100−1)+(1001))=(1000)\frac{1}{2}(Z+I)=\frac{1}{2}\left(\begin{pmatrix}1&0\\0&-1\end{pmatrix}+\begin{pmatrix}1&0\\0&1\end{pmatrix}\right)=\begin{pmatrix}1&0\\0&0\end{pmatrix}

and

12(Z−I)=12((100−1)−(1001))=(0001).\frac{1}{2}(Z-I)=\frac{1}{2}\left(\begin{pmatrix}1&0\\0&-1\end{pmatrix}-\begin{pmatrix}1&0\\0&1\end{pmatrix}\right)=\begin{pmatrix}0&0\\0&1\end{pmatrix}.

so all matrix units ∣i⟩⟨i∣|i\rangle\langle i| in the diagonal can be constructed by Kronecker products of these. Denoting the ithi^{\text{th}} component in the diagonal of ⟦aj⟧H\llbracket a_{j} \rrbracket_{H} by αj,i\alpha_{j,i}, we have ⟦aj⟧H=∑iαj,i∣i⟩⟨i∣\llbracket a_{j} \rrbracket_{H}=\sum_{i}\alpha_{j,i}|i\rangle\langle i|, and since αj,i\alpha_{j,i} is dyadic rational, and ∣i⟩⟨i∣|i\rangle\langle i| was constructed above as a sum of Pauli strings with dyadic rational coefficients, we have shown that ⟦aj⟧H\llbracket a_{j} \rrbracket_{H} has dyadic rational Pauli coefficients.

In the case where aja_{j} is not a bare action so that aj=ubju†a_{j}=ub_{j}u^{\dagger} for a bare action bjb_{j}, we have that ⟦aj⟧H=⟦ubju†⟧H=⟦u⟧U⟦bj⟧H⟦u⟧U†\llbracket a_{j} \rrbracket_{H}=\llbracket ub_{j}u^{\dagger}\rrbracket_{H}=\llbracket u\rrbracket_{U}\llbracket b_{j}\rrbracket_{H}\llbracket u\rrbracket_{U}^{\dagger}. In this case, we decompose ⟦bj⟧H\llbracket b_{j}\rrbracket_{H} exactly as above, and remark that ⟦u⟧U\llbracket u\rrbracket_{U} is a Clifford group operation (so conjugates Pauli strings to Pauli strings), so ⟦u⟧U⟦bj⟧H⟦u⟧U†\llbracket u\rrbracket_{U}\llbracket b_{j}\rrbracket_{H}\llbracket u\rrbracket_{U}^{\dagger} is already a sum of Pauli strings with dyadic rational coefficients.

:::

Theorem 16. For every 2n×2n2^{n}\times2^{n} Hamiltonian HH with Pauli coefficients in the ring Z[12]\mathbb{Z}[\frac{1}{2}] of dyadic rationals, there exists a process p:2np : 2^{n} such that ⟦p⟧H=H\llbracket p \rrbracket_{H}=H.

Proof. Expressing HH in the Pauli basis H=∑j=1qαjPjH=\sum_{j=1}^{q}\alpha_jP_j, by assumption αj∈Z[12]\alpha_j\in\mathbb{Z}\left[\frac{1}{2}\right] and PjP_j is some Pauli string. By the assumption, we are free to let αj=n2m\alpha_j=\frac{n}{2^m} for some nn and mm. Since PjP_j is Pauli string, it follows that it has eigenvalues ±1\pm1, and so αjPj\alpha_jP_j has eigenvalues ±n2m\pm\frac{n}{2^m}. Since ⟦δm⟧H=12m\llbracket\delta_m\rrbracket_H=\frac{1}{2^m} and ⟦−δm⟧H=−12m\llbracket-\delta_m\rrbracket_H=-\frac{1}{2^m}, it follows that we can represent the diagonal matrix of eigenvalues of PjP_j as

\begin{aligned} \alpha_jP_j&=\sum_i |i\rangle\langle i|(-1)^{f(i)}\frac{n}{2^m}\\ &=n\sum_i |i\rangle\langle i|(-1)^{f(i)}\frac{1}{2^m}\\ &=n\sum_i |i\rangle\langle i|\llbracket(-1)^{f(i)}\delta_m\rrbracket_H\\ &=n\left\llbracket\bigoplus_i(-1)^{f(i)}\delta_m\right\rrbracket_H\\ &=\sum_{j=1}^{n}\left\llbracket\bigoplus_i(-1)^{f(i)}\delta_m\right\rrbracket_H\\ &=\left\llbracket\bigparallel_{j=1}^{n}\bigoplus_i(-1)^{f(i)}\delta_m\right\rrbracket_H \end{aligned}

where ff is a binary valued function indicating whether the ithi^{\mathrm{th}} component is positive or negative, and we use the abuse of notation (−1)f(i)δm(-1)^{f(i)}\delta_m to mean δm\delta_m when f(i)=0f(i)=0 and −δm-\delta_m when f(i)=1f(i)=1. In the case where PjP_j is not diagonal, it must have XX or YY tensor factors: for each such factor, we conjugate the Hamilton term above by H if it is an XX, and by H; S if it is YY. (For example if Pj=IXZP_j=IXZ, we represent the eigenvalue diagonal as above and conjugate the resulting process by I⊗H⊗II\otimes H\otimes I.)

Representing each Pauli term αjPj\alpha_jP_j in this way with a process pjp_j satisfying ⟦pj⟧H=αjPj\llbracket p_j\rrbracket_H=\alpha_jP_j, it follows that

H=\sum_{j=1}^{q}\alpha_jP_j=\sum_{j=1}^{q}\llbracket p_j\rrbracket_H=\left\llbracket\bigparallel_{j=1}^{q}p_j\right\rrbracket_H

as desired. □

In principle, combining these two theorems yields a procedure for normalisation by evaluation. However, doing so is not always efficient since H(2n)\mathcal{H}(2^n) has dimension 4n4^n, 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 p≈qp\approx q iff ⟦p⟧H=⟦q⟧H\llbracket p\rrbracket_H=\llbracket q\rrbracket_H for all processes p,qp,q of type 2n2^n.

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.

  1. 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 ≈\approx 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 pp is simple if p=∥jajp = \mathbin{\|}_j a_j with each aja_j a bare action.

In other words, a simple process is a process that is free of transformations.

Lemma 18. If p:np : n is a simple process then ⟦p⟧H\llbracket p \rrbracket_H is a diagonal matrix.

Proof. Suppose p=∥jajp = \mathbin{\|}_j a_j where each aja_j is a bare action. Since each aja_j is a bare action, it follows that aj=⨁k=1nsj,ka_j = \bigoplus_{k=1}^{n} s_{j,k} where sj,ks_{j,k} is either some δm\delta_m, −δm-\delta_m, or 00. As such,

\llbracket a_j \rrbracket_H = \left\llbracket\bigoplus_{k=1}^{n} s_{j,k} \right\rrbracket_H = \bigoplus_{k=1}^{n} \llbracket s_{j,k} \rrbracket_H

so ⟦aj⟧H\llbracket a_j \rrbracket_H is diagonal. But then

\llbracket p \rrbracket_H = \left\llbracket\mathbin{\|}_j a_j \right\rrbracket_H = \sum_j \llbracket a_j \rrbracket_H = \sum_j \bigoplus_{k=1}^{n} \llbracket s_{j,k} \rrbracket_H

so ⟦p⟧H\llbracket p \rrbracket_H 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 a:na : n and b:mb : m, it is the case that

(i) a⊕b≈a⊕0m∥0n⊕ba \oplus b \approx a \oplus0_m \mathbin{\|} 0_n \oplus b,

(ii) 0n⊕0m≈0n+m0_n \oplus0_m \approx0_{n+m},

(iii) u(a⊕b)u†≈u(a⊕0m)u†∥u(0n⊕b)u†u(a \oplus b)u^\dagger\approx u(a \oplus0_m)u^\dagger\mathbin{\|} u(0_n \oplus b)u^\dagger,

(iv) u0nu†≈0nu0_nu^\dagger\approx0_n.

Lemma 20. For all k,l,n∈Nk,l,n \in\mathbb{N},

(i) 0l⊕δk+1⊕0n∥0l⊕δk+1⊕0n≈0l⊕δk⊕0n0_l \oplus\delta_{k+1} \oplus0_n \mathbin{\|} 0_l \oplus\delta_{k+1} \oplus0_n \approx0_l \oplus\delta_k \oplus0_n and

(ii) 0l⊕−δk+1⊕0n∥0l⊕−δk+1⊕0n≈0l⊕−δk⊕0n0_l \oplus-\delta_{k+1} \oplus0_n \mathbin{\|} 0_l \oplus-\delta_{k+1} \oplus0_n \approx0_l \oplus-\delta_k \oplus0_n.

Definition 21. Say that a simple process p=∥jajp = \mathbin{\|}_j a_j is a 1-level process if there exist n,m∈Nn,m \in\mathbb{N} such that each aj=0n⊕bj⊕0ma_j = 0_n \oplus b_j \oplus0_m for bjb_j of the form 00, δk\delta_k, or −δk-\delta_k for some kk.

Lemma 22. If pp is a 1-level process then either p≈0p \approx0 or p≈±a2b⋆0n⊕δ0⊕0mp \approx\pm\frac{a}{2^b} \star0_n \oplus\delta_0 \oplus0_m for unique a,b,n,m∈Z+a,b,n,m \in\mathbb{Z}_+ such that aa is odd.

Proof. Since p=∥j0n⊕bj⊕0mp = \mathbin{\|}_j 0_n \oplus b_j \oplus0_m for bjb_j scalars, and since ∥\mathbin{\|} is unital with 00 as unit by Proposition 7, we are free to assume that either p≈0p \approx0 (in case all bj=0b_j = 0) or no bj=0b_j = 0. If the former is the case, we are done. If the latter is the case, all bjb_j are of the form ±δk\pm\delta_k. In this case, we use the following procedure to normalise pp:

  1. Find the largest kk such that 0n⊕δk⊕0m0_n \oplus\delta_k \oplus0_m or 0n⊕(−δk)⊕0m0_n \oplus(-\delta_k) \oplus0_m appears in pp, and use Lemma 20 to express every action of the form 0n⊕δk′⊕0m0_n \oplus\delta_{k'} \oplus0_m as a composition of a number of 0n⊕δk⊕0m0_n \oplus\delta_k \oplus0_m, and every action of the form 0n⊕(−δk′)⊕0m0_n \oplus(-\delta_{k'}) \oplus0_m as a composition of a number of 0n⊕(−δk)⊕0m0_n \oplus(-\delta_k) \oplus0_m.

  1. If both 0n⊕δk⊕0m0_n \oplus\delta_k \oplus0_m and 0n⊕(−δk)⊕0m0_n \oplus(-\delta_k) \oplus0_m appear in this expansion, pair up each 0n⊕δk⊕0m0_n \oplus\delta_k \oplus0_m with a 0n⊕(−δk)⊕0m0_n \oplus(-\delta_k) \oplus0_m until the remaining terms are either all 0n⊕δk⊕0m0_n \oplus\delta_k \oplus0_m or all 0n⊕(−δk)⊕0m0_n \oplus(-\delta_k) \oplus0_m, then use Proposition 7 to get rid of all matching pairs.

  1. At this point, the expansion is either 0 or consists of either all 0n⊕δk⊕0m0_n \oplus\delta_k \oplus0_m or all 0n⊕(−δk)⊕0m0_n \oplus(-\delta_k) \oplus0_m. 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 a/2b⋆0n⊕δ0⊕0m=0n⊕δb⊕0m∥⋯∥0n⊕δb⊕0m⏟a timesa/2^b \star0_n \oplus\delta_0 \oplus0_m = \underbrace{0_n \oplus\delta_b \oplus0_m \mathbin{\|} \cdots\mathbin{\|} 0_n \oplus\delta_b \oplus0_m}_{a\ \text{times}} and analogously for −a/2b⋆0n⊕δ0⊕0m-a/2^b \star0_n \oplus\delta_0 \oplus0_m, after normalisation the process is on the required form. To see that this is unique, we notice that

\left\llbracket a/2^b \star0_n \oplus\delta_0 \oplus0_m \right\rrbracket_H = \left\llbracket\underbrace{0_n \oplus\delta_b \oplus0_m \mathbin{\|} \cdots\mathbin{\|} 0_n \oplus\delta_b \oplus0_m}_{a\ \text{times}} \right\rrbracket_H = a\left\llbracket0_n \oplus\delta_b \oplus0_m\right\rrbracket_H = a\frac{1}{2^b}|n\rangle\langle n| = \frac{a}{2^b}|n\rangle\langle n|

which is a normal representation of a dyadic rational (as a single entry in a 1-level diagonal matrix) since aa is odd.

Proposition 23. Every simple process is equivalent to a composition of 1-level processes of the form ±aj2bj⋆0nj⊕δ0⊕0mj\pm\frac{a_j}{2^{b_j}} \star0_{n_j} \oplus\delta_0 \oplus0_{m_j} for unique aja_j, bjb_j, njn_j, mjm_j where aja_j is odd.

Proof. Let p=∥j=1Jcjp = \mathbin{\|}_{j=1}^{J} c_j where each cjc_j is a bare action, i.e., of the form cj=⨁ldj,lc_j = \bigoplus_l d_{j,l} for scalars dj,ld_{j,l}. Applying Lemma 19 on each cjc_j yields that cjc_j is a composition of 1-level processes, namely

cj≈dj,1⊕0n−1∥01⊕dj,2⊕0n−2∥⋯∥0n−1⊕dj,lc_j \approx d_{j,1} \oplus0_{n-1} \mathbin{\|} 0_1 \oplus d_{j,2} \oplus0_{n-2} \mathbin{\|} \cdots\mathbin{\|} 0_{n-1} \oplus d_{j,l}

Grouping the resulting 1-level processes by index using associativity and commutativity (Proposition 7), we get that pp is equivalent to a big parallel composition of 1-level processes acting on each component,

p≈(d1,1⊕0n−1∥⋯∥dJ,1⊕0n−1)∥p \approx(d_{1,1} \oplus0_{n-1} \mathbin{\|} \cdots\mathbin{\|} d_{J,1} \oplus0_{n-1}) \mathbin{\|}
(01⊕d1,2⊕0n−1∥⋯∥01⊕dJ,2⊕0n−1)∥(0_1 \oplus d_{1,2} \oplus0_{n-1} \mathbin{\|} \cdots\mathbin{\|} 0_1 \oplus d_{J,2} \oplus0_{n-1}) \mathbin{\|}
⋯∥\cdots\mathbin{\|}
(0n−1⊕d1,n∥⋯∥0n−1⊕dJ,n)(0_{n-1} \oplus d_{1,n} \mathbin{\|} \cdots\mathbin{\|} 0_{n-1} \oplus d_{J,n})

and applying Lemma 22 to each group yields the desired result.

Definition 24. For a process pp, call the process qq extracted from ⟦p⟧H\llbracket p\rrbracket_H in Theorem 16 the Pauli representation of pp.

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 pp to a composition of 1-level processes rr (using Proposition 23) yields p≈rp \approx r, and doing the same for its Pauli representation qq yields q≈rq \approx r, so p≈qp \approx q since ≈\approx is an equivalence relation.

Corollary 26. For simple processes pp and qq, ⟦p⟧H=⟦q⟧H\llbracket p\rrbracket_H = \llbracket q\rrbracket_H implies p≈qp \approx q.

Proof. Since ⟦p⟧H=⟦q⟧H\llbracket p\rrbracket_H = \llbracket q\rrbracket_H it follows that pp and qq have the same Pauli representation rr, and since p≈rp \approx r and q≈rq \approx r by Corollary 25, it follows that p≈qp \approx q by ≈\approx an equivalence relation. □\square

Lemma 27. p≈∥jajp \approx\mathop{\|}_{j} a_j implies upu†≈∥juaju†upu^\dagger\approx\mathop{\|}_{j} ua_ju^\dagger when pp and all aja_j are bare actions.

Proof. We proceed by induction on the number nn of rule applications in the proof that p≈∥jajp \approx\mathop{\|}_{j} a_j. In the base case n=0n = 0, so no rules are applied, and we are done. In the inductive case, we assume that p≈∥jajp \approx\mathop{\|}_{j} a_j implies upu†≈∥juaju†upu^\dagger\approx\mathop{\|}_{j} ua_ju^\dagger when the proof requires nn rule applications, and must show that the same is the case for n+1n + 1 rule applications.

There are two cases depending on the final rule applied. When the final rule is the permutation rule, we have p≈∥jaj′p \approx\mathop{\|}_{j} a'_j in nn steps, and ∥jaj′=∥jaσ(j)\mathop{\|}_{j} a'_j = \mathop{\|}_{j} a_{\sigma(j)} for some permutation σ\sigma. By induction upu†≈∥juaj′u†upu^\dagger\approx\mathop{\|}_{j} ua'_ju^\dagger, so also ∥juaj′u†=∥juaσ(j)u†\mathop{\|}_{j} ua'_ju^\dagger= \mathop{\|}_{j} ua_{\sigma(j)}u^\dagger. As such, applying the permutation rule with σ\sigma yields upu†≈∥juaσ(j)u†upu^\dagger\approx\mathop{\|}_{j} ua_{\sigma(j)}u^\dagger.

When the final rule applied is the substitution rule, we have p≈∥jaj′p \approx\mathop{\|}_{j} a'_j in nn steps, so we must have that sch⁡(∥jaj′)=[a1′,…,aq′]\operatorname{sch}(\mathop{\|}_{j} a'_j) = [a'_1,\ldots,a'_q] and

sch⁡(∥jaj)=[a1′,…,ak−1′,b1,…,bl,ak+1′,…,aq′].\operatorname{sch}\left(\mathop{\|}_{j} a_j\right) = [a'_1,\ldots,a'_{k-1},b_1,\ldots,b_l,a'_{k+1},\ldots,a'_q].

where ⟦ak′/2m⟧Π=∏i=1l⟦bi/2m⟧Π\llbracket a'_k/2^m\rrbracket_\Pi= \prod_{i=1}^{l}\llbracket b_i/2^m\rrbracket_\Pi. But then

⟦(uak′u†)/2m⟧Π=⟦u(ak′/2m)u†⟧Π=⟦u⟧Π⟦ak′/2m⟧Π⟦u⟧Π†=⟦u⟧Π(∏i=1l⟦bi/2m⟧Π)⟦u⟧Π†\begin{aligned} \llbracket(ua'_ku^\dagger)/2^m\rrbracket_\Pi= \llbracket u(a'_k/2^m)u^\dagger\rrbracket_\Pi\\ &= \llbracket u\rrbracket_\Pi\llbracket a'_k/2^m\rrbracket_\Pi\llbracket u\rrbracket_\Pi^\dagger\\ &= \llbracket u\rrbracket_\Pi\left(\prod_{i=1}^{l}\llbracket b_i/2^m\rrbracket_\Pi\right)\llbracket u\rrbracket_\Pi^\dagger \end{aligned}
=(∗)∏i=1l⟦u⟧Π⟦bi/2m⟧Π⟦u⟧Π†=∏i=1l⟦u(bi/2m)u†⟧Π=∏i=1l⟦(ubiu†)/2m⟧Π.\begin{aligned} \overset{(*)}{=} \prod_{i=1}^{l}\llbracket u\rrbracket_\Pi\llbracket b_i/2^m\rrbracket_\Pi\llbracket u\rrbracket_\Pi^\dagger\\ &= \prod_{i=1}^{l}\llbracket u(b_i/2^m)u^\dagger\rrbracket_\Pi\\ &= \prod_{i=1}^{l}\llbracket(ub_iu^\dagger)/2^m\rrbracket_\Pi. \end{aligned}

where the step marked (∗)(*) follows since ⟦u⟧Π†⟦u⟧Π=⟦u⟧Π⟦u⟧Π†=id⁡\llbracket u\rrbracket_\Pi^\dagger\llbracket u\rrbracket_\Pi= \llbracket u\rrbracket_\Pi\llbracket u\rrbracket_\Pi^\dagger= \operatorname{id}. Since we must then have sch⁡(∥juaj′u†)=[ua1′u†,…,uaq′u†]\operatorname{sch}(\mathop{\|}_{j} ua'_ju^\dagger) = [ua'_1u^\dagger,\ldots,ua'_qu^\dagger] and

sch⁡(∥juaju†)=[ua1′u†,…,uak−1′u†,ub1u†,…,ublu†,uak+1′u†,…,uaq′u†],\operatorname{sch}\left(\mathop{\|}_{j} ua_ju^\dagger\right) = [ua'_1u^\dagger,\ldots,ua'_{k-1}u^\dagger,ub_1u^\dagger,\ldots,ub_lu^\dagger,ua'_{k+1}u^\dagger,\ldots,ua'_qu^\dagger],

that upu†≈∥juaju†upu^\dagger\approx\mathop{\|}_{j} ua_ju^\dagger follows by the substitution rule using the proof that ⟦(uak′u†)/2m⟧Π=∏i=1l⟦(ubiu†)/2m⟧Π\llbracket(ua'_ku^\dagger)/2^m\rrbracket_\Pi= \prod_{i=1}^{l}\llbracket(ub_iu^\dagger)/2^m\rrbracket_\Pi. □\square

:::

Lemma 28. For all transformations uu, v:nv : n and action a:na : n, it is the case that u(vav†)u†≈(u⋅v)a(u⋅v)†u(vav^\dagger)u^\dagger\approx(u \cdot v)a(u \cdot v)^\dagger.

Proof. For any action aa (in particular any action of the form b/2mb/2^m) we have

⟦u(vav†)u†⟧Π=⟦u⟧Π⟦vav†⟧Π⟦u†⟧Π=⟦u⟧Π⟦v⟧Π⟦a⟧Π⟦v†⟧Π⟦u†⟧Π=(⟦u⟧Π⟦v⟧Π)⟦a⟧Π(⟦u⟧Π⟦v⟧Π)†=⟦u⋅v⟧Π⟦a⟧Π⟦u⋅v⟧Π†=⟦(u⋅v)a(u⋅v)†⟧Π\begin{aligned} \llbracket u(vav^\dagger)u^\dagger\rrbracket_{\Pi} &= \llbracket u \rrbracket_{\Pi}\llbracket vav^\dagger\rrbracket_{\Pi}\llbracket u^\dagger\rrbracket_{\Pi}\\ &= \llbracket u \rrbracket_{\Pi}\llbracket v \rrbracket_{\Pi}\llbracket a \rrbracket_{\Pi}\llbracket v^\dagger\rrbracket_{\Pi}\llbracket u^\dagger\rrbracket_{\Pi}\\ &= (\llbracket u \rrbracket_{\Pi}\llbracket v \rrbracket_{\Pi})\llbracket a \rrbracket_{\Pi}(\llbracket u \rrbracket_{\Pi}\llbracket v \rrbracket_{\Pi})^\dagger\\ &= \llbracket u \cdot v \rrbracket_{\Pi}\llbracket a \rrbracket_{\Pi}\llbracket u \cdot v \rrbracket_{\Pi}^\dagger\\ &= \llbracket(u \cdot v)a(u \cdot v)^\dagger\rrbracket_{\Pi} \end{aligned}

so the statement follows by application of the substitution rule.

Lemma 29. When p:2np : 2^n is a diagonal Pauli representation and uu is any transformation, there exists an action q:2nq : 2^n such that upu†≈vqv†upu^\dagger\approx vqv^\dagger where vqv†vqv^\dagger is a Pauli representation.

Proof. When pp is a diagonal Pauli representation, it follows that it represents a Pauli string with only ZZ and II as tensor factors. Since ⟦u⟧U\llbracket u \rrbracket_U is a Clifford operation, it follows that ⟦upu†⟧H=⟦u⟧U⟦p⟧H⟦u†⟧U\llbracket upu^\dagger\rrbracket_H = \llbracket u \rrbracket_U\llbracket p \rrbracket_H\llbracket u^\dagger\rrbracket_U is again a Pauli string, and by Theorem 16 that there exists some Pauli representation vqv†vqv^\dagger such that ⟦upu†⟧H=⟦vqv†⟧H\llbracket upu^\dagger\rrbracket_H = \llbracket vqv^\dagger\rrbracket_H. But then it follows that

⟦upu†/2m⟧H=⟦upu†⟧H/2m=⟦vqv†⟧H/2m=⟦vqv†/2m⟧H\llbracket upu^\dagger/2^m \rrbracket_H = \llbracket upu^\dagger\rrbracket_H/2^m = \llbracket vqv^\dagger\rrbracket_H/2^m = \llbracket vqv^\dagger/2^m \rrbracket_H

for all mm, and in turn that ⟦upu†/2m⟧U=⟦vqv†/2m⟧U\llbracket upu^\dagger/2^m \rrbracket_U = \llbracket vqv^\dagger/2^m \rrbracket_U for all mm. Since Πk\Pi_k is complete, it then follows that ⟦upu†/2m⟧Π=⟦vqv†/2m⟧Π\llbracket upu^\dagger/2^m \rrbracket_{\Pi} = \llbracket vqv^\dagger/2^m \rrbracket_{\Pi}, so the statement follows by a single application of the substitution rule. □

Theorem 30. Every process p:2np : 2^n is equivalent to its Pauli representation.

Proof. Let p=∥jujajuj†p = \mathbin{\|}_j u_j a_j u_j^\dagger be a process. Without loss of generality we assume that each aja_j 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 pp is not conjugated, we can always see it as conjugated by II.

Applying Corollary 25, Lemma 27, and congruence of process equivalence under ∥\| (Proposition 6) on each ujajuj†u_j a_j u_j^\dagger yields that

p≈∥iui(ni2mi⋆bi′)ui†p \approx\mathbin{\|}_i u_i\left(\frac{n_i}{2^{m_i}} \star b_i'\right)u_i^\dagger

where each bi′b_i' is a representation of a diagonal Pauli string, and uiu_i is some transformation. However, since the permitted transformations uiu_i are precisely the Clifford group operations, it follows that each ⟦ui(ni2mi⋆bi′)ui†⟧H\llbracket u_i\left(\frac{n_i}{2^{m_i}}\star b_i'\right)u_i^\dagger\rrbracket_H 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 uibi′ui†u_i b_i' u_i^\dagger in ui(ni2mi⋆bi′)ui†=ni2mi⋆uibi′ui†u_i\left(\frac{n_i}{2^{m_i}}\star b_i'\right)u_i^\dagger= \frac{n_i}{2^{m_i}}\star u_i b_i' u_i^\dagger into its Pauli representation.

In this way, p≈∥ini2mi⋆pip \approx\mathbin{\|}_i \frac{n_i}{2^{m_i}}\star p_i where each pip_i 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 ni2mi\frac{n_i}{2^{m_i}} into one for each type of Pauli string, and we are done. □

Corollary 31 (Completeness). For all processes p:2np : 2^n and q:2nq : 2^n, ⟦p⟧H=⟦q⟧H\llbracket p \rrbracket_H = \llbracket q \rrbracket_H implies p≈qp \approx q.

Proof. Since ⟦p⟧H=⟦q⟧H\llbracket p \rrbracket_H = \llbracket q \rrbracket_H it follows that pp and qq have the same Pauli representation rr, and since p≈rp \approx r and q≈rq \approx r by Theorem 30, it follows that p≈qp \approx q by ≈\approx equivalence relation. □

Theorem 32 (Full abstraction). For all processes p:2np : 2^n and q:2nq : 2^n, ⟦p⟧H=⟦q⟧H\llbracket p \rrbracket_H = \llbracket q \rrbracket_H iff p≈qp \approx q.

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 L(2n)\mathcal{L}(2^n) for the set of matrices −iH-iH with HH a 2n×2n2^n \times2^n Hamiltonian whose Pauli coefficients are dyadic, and [A,B]=AB−BA[A,B] = AB-BA for the commutator. Like ⋆\star, define a derived form: the bracket [p,q][p,q] of processes p,q:2np,q : 2^n is any process with ⟦[p,q]⟧H=−i[⟦p⟧H,⟦q⟧H]\llbracket[p,q] \rrbracket_H = -i[\llbracket p \rrbracket_H,\llbracket q \rrbracket_H].

Proposition 33. (i) L(2n)\mathcal{L}(2^n) is closed under addition, negation and the commutator, so it is a Lie algebra over Z[12]\mathbb{Z}[\frac{1}{2}], and its real span is the Lie algebra u(2n)\mathfrak{u}(2^n) of U(2n)U(2^n). (ii) The bracket of any two processes exists and is unique up to ≈\approx. (iii) The map p↦−i⟦p⟧Hp \mapsto-i\llbracket p \rrbracket_H is an isomorphism of Lie algebras from processes of type 2n2^n up to ≈\approx, with ∥\| as addition and [−,−][-,-] as bracket, onto L(2n)\mathcal{L}(2^n).

Proof. (i) Two Pauli strings P and Q either commute or anticommute. If they anticommute, [P,Q]=2PQ=±2iR[P,Q] = 2PQ = \pm2iR for a Pauli string R, so [−iαP,−iβQ]=−i(±2αβ)R[-i\alpha P,-i\beta Q] = -i(\pm2\alpha\beta)R, with dyadic coefficient when α\alpha and β\beta are dyadic; the commutator is bilinear, so closure follows. Pauli strings span all matrices, so the real span of L(2n)\mathcal{L}(2^n) is the space of matrices −iH-iH with HH Hermitian, which is u(2n)\mathfrak{u}(2^n) [[14]]. (ii) By (i), −i[⟦p⟧H,⟦q⟧H]-i[\llbracket p \rrbracket_H,\llbracket q \rrbracket_H] 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 −i⟦[p,q]⟧H=−[⟦p⟧H,⟦q⟧H]=[−i⟦p⟧H,−i⟦q⟧H]-i\llbracket[p,q] \rrbracket_H = -[\llbracket p \rrbracket_H,\llbracket q \rrbracket_H] = [-i\llbracket p \rrbracket_H,-i\llbracket q \rrbracket_H]. □

The exponential carries L(2n)\mathcal{L}(2^n) into U(2n)U(2^n), but in general outside the unitaries that Πk\Pi_k terms denote: these have algebraic entries and so algebraic eigenvalues, while e−2πi(X+Z)/8e^{-2\pi i(X+Z)/8} has eigenvalues e±iπ2/4e^{\pm i\pi\sqrt{2}/4}, which are transcendental by the Gelfond-Schneider theorem. The schedule semantics replaces the exponential by Πk\Pi_k circuits that converge to it (Theorem 12), and the bracket measures what that costs: one step eAeBe^Ae^B differs from eA+Be^{A+B} by 12[A,B]\frac{1}{2}[A,B] 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 nn (repeated 2n2^n 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 δkj\delta_k^j compiles to a phase of −2πj/2k-2\pi j/2^k:

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 δkj\delta_k^j as the derived abbreviation j⋆δkj \star\delta_k, the implementation promotes it to a primitive constructor DeltaPow k j. This keeps schedules compact: expanding a coefficient jj into jj parallel copies of δk\delta_k 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 e−2πi∥P∥He^{-2\pi i \lVert P\rVert_H} 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 X+ZX+Z Hamiltonian of § 2, physically a single spin in a magnetic field with components along the zz and xx 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 nn the schedule alternates a ZZ-slice and an XX-slice 2n2^n times, each slice carrying an angle scaled by 2−n2^{-n}, and the circuit’s distance to the ideal falls accordingly:

nnreps 2n2^nFrobenius
010.4002
120.1933
240.0958
380.0478
4160.0239

Table 2.

The error halves with each level, the expected first-order Trotter rate. Figure 7 shows the compiled circuit at levels n=0n=0 and n=1n=1: at level 0 a single coarse ZZ-slice followed by an XX-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.

Compiled circuits for $zxK_{2}^{3}$ at refinement levels $n=0$ and $n=1$

Figure 7. Compiled circuits for zxK23zxK_{2}^{3} at refinement levels n=0n = 0 and n=1n = 1. P(θ)P(\theta) denotes the single-qubit phase gate diag⁡(1,eiθ)\operatorname{diag}(1,e^{i\theta}). 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.

Probability of finding the proton at $x_3 = |11\rangle$

Figure 8. Probability ∣a3(t)∣2|a_3(t)|^2 of finding the proton at x3=∣11⟩x_3 = |11\rangle at time tt, starting there: exact evolution under H~\widetilde{H} (solid), and compiled circuits for pp with k=12k = 12 at refinement levels n=2n = 2 (dashed) and n=4n = 4 (dots).

Because ∥\parallel 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 zxKzxK the step contains a ZZ-slice and an XX-slice, which may be applied in either order:

orderingFrobenius
[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: ZZ and XX 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 ZZ at k=1k = 1, a medium XX at k=2k = 2, a small YY at k=3k = 3, no two of which commute, and the YY term breaks the symmetry above: YY is antisymmetric, so transposition reverses its rotation. Enumerating its six orderings at level 1 produces a clear ranking:

orderingFrobenius
[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 ∥18⋆ZiZi+1∥∥116⋆Xi∥\left\lVert\frac{1}{8} \star Z_iZ_{i+1} \right\rVert\left\lVert\frac{1}{16} \star X_i \right\rVert, where XiX_i applies XX to qubit ii and ZiZi+1Z_iZ_{i+1} applies ZZ to qubits ii and i+1i+1, composed with a user’s term −18⋆Z2Z3-\frac{1}{8} \star Z_2Z_3 that cancels one of its terms. In every Trotter step the two are separated by XX-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 nn:

nncomposednormal form
03.09752.1105
20.86810.4997
40.21860.1244

Table 3.

Rewriting can also make a circuit preserve a quantity exactly. Take the six-qubit process whose adjacent pairs of qubits carry 132⋆(XiXi+1∥YiYi+1)\frac{1}{32} \star(X_iX_{i+1} \mathbin{\|} Y_iY_{i+1}) and 164⋆ZiZi+1\frac{1}{64} \star Z_iZ_{i+1}. The sum XiXi+1+YiYi+1X_iX_{i+1} + Y_iY_{i+1} exchanges ∣01⟩\lvert01\rangle and ∣10⟩\lvert10\rangle on its pair, so it preserves the number of 1s in a basis state, as do the ZiZi+1Z_iZ_{i+1} terms; but XiXi+1X_iX_{i+1} and YiYi+1Y_iY_{i+1} alone do not. Scheduled by type, all XXXX terms, then all YYYY, then all ZZZZ, the circuit started in ∣010101⟩\lvert010101\rangle 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:

nnleak, by typeleak, by bonderror, by typeerror, by bond
01.7%01.02321.0496
20.1%00.25120.2657
40.0064%00.06270.0665

Table 4.

This is the invariant reasoning of concurrent programs [22]: a transfer a := a-1; b := b+1 preserves a+ba+b 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 M=∑iZiM = \sum_i Z_i; 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, 132⋆(XiXi+1∥YiYi+1)\frac{1}{32} \star(X_iX_{i+1} \mathbin{\|} Y_iY_{i+1}) is equivalent to the single action u(O⊕δ4O⊕−δ4)u†u(\mathbb{O} \oplus\delta_4 \mathbb{O} \oplus-\delta_4)u^\dagger with u=CX⁡⋅(H⊗I)u = \operatorname{CX} \cdot(H \otimes I), 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 Z⊗ZZ \otimes Z:

zzParity :: Natural -> Proc
zzParity k = diag 0 k k 0

places a phase on the ∣01⟩\lvert01\rangle and ∣10⟩\lvert10\rangle 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, p≈qp \approx q 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 XZ⋯ZXXZ\cdots ZX and YZ⋯ZYYZ\cdots ZY on up to four adjacent qubits, plus single ZZ terms, written as Pauli strings, with the Pauli gadgets a compiler emits for it (one ZZ, a ladder of CNOT gates and a change of basis), on up to 256 qubits, where the operator either program denotes is a 2256×22562^{256} \times2^{256} matrix. A gadget with a fault, the S of its YY factors dropped, shows up as two differing strings (column fault):

qubitstermsnormal formfaulttime (ms)
8444420.2
1610010020.7
3221221222.3
6443643627.9
128884884229.5
256178017802126.7

Table 1.

Reorderings need no check, by rule (R1); the check serves every other rewrite.

Sanity Checking. Leveraging a pre-existing implementation of Π\Pi 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 “nn times” (and variants thereof), whose degenerate case n=0n = 0 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 x0,…,x3x_0,\ldots,x_3: at time tt it is in the superposition a0(t) ∣x0⟩+⋯+a3(t) ∣x3⟩a_0(t)\,|x_0\rangle+\cdots+a_3(t)\,|x_3\rangle, whose amplitudes evolve under a Hamiltonian H~\widetilde{H} that they publish. The experiment prepares the proton at x3x_3, say, evolves it for times t0,…,tN−1t_0,\ldots,t_{N-1}, and measures its position, repeating each run to collect statistics. The resulting series ∣a3(t0)∣2,…,∣a3(tN−1)∣2|a_3(t_0)|^2,\ldots,|a_3(t_{N-1})|^2 is a sum of a few sinusoids whose frequencies are the gaps between the eigenvalues of H~\widetilde{H}; 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−1^{-1}, the unit chemists use for frequencies. To run the experiment, they needed a small quantum circuit. For each tt, this circuit was computed on a classical computer by calculating e−iH~te^{-i\widetilde{H}t} 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 H~\widetilde{H} in Hamilton, we turn each entry hijh_{ij} of the published 4×44 \times4 matrix into the term hij∣xi⟩⟨xj∣h_{ij}|x_i\rangle\langle x_j|, so that H~=∑i,jhij∣xi⟩⟨xj∣\widetilde{H}=\sum_{i,j}h_{ij}|x_i\rangle\langle x_j|. Two qubits store xix_i as the binary numeral of ii, so that x3=∣11⟩x_3=|11\rangle, and the identities

∣0⟩⟨0∣=12(I+Z),∣1⟩⟨1∣=12(I−Z),∣0⟩⟨1∣+∣1⟩⟨0∣=X,∣0⟩⟨1∣−∣1⟩⟨0∣=iY|0\rangle\langle0|=\frac{1}{2}(I+Z),\qquad|1\rangle\langle1|=\frac{1}{2}(I-Z),\qquad|0\rangle\langle1|+|1\rangle\langle0|=X,\qquad|0\rangle\langle1|-|1\rangle\langle0|=iY

turn each term into Pauli strings: a diagonal entry needs only II and ZZ, and an off-diagonal entry, together with its mirror image hji=hij∗h_{ji}=h_{ij}^{*}, has an XX or a YY at each bit in which ii and jj differ. For instance,

∣x3⟩⟨x3∣=14(II−ZI−IZ+ZZ),|x_3\rangle\langle x_3|=\frac{1}{4}(II-ZI-IZ+ZZ),
∣x2⟩⟨x3∣+∣x3⟩⟨x2∣=12(IX−ZX),|x_2\rangle\langle x_3|+|x_3\rangle\langle x_2|=\frac{1}{2}(IX-ZX),
∣x1⟩⟨x2∣+∣x2⟩⟨x1∣=12(XX+YY),|x_1\rangle\langle x_2|+|x_2\rangle\langle x_1|=\frac{1}{2}(XX+YY),

where ZIZI stands for Z⊗IZ\otimes I. Collecting terms, dropping the identity (which shifts all energies equally), and scaling and rounding the weights to k=12k=12 fractional bits gives the process

p=1024212⋆ZI∥752212⋆IZ∥−568212⋆IX∥448212⋆ZZ∥−305212⋆XX∥−305212⋆YY∥61212⋆XI∥−25212⋆ZX∥−5212⋆XZ\begin{aligned} p={}&\frac{1024}{2^{12}}\star ZI\mathbin{\|}\frac{752}{2^{12}}\star IZ\mathbin{\|}-\frac{568}{2^{12}}\star IX\mathbin{\|}\frac{448}{2^{12}}\star ZZ\mathbin{\|}-\frac{305}{2^{12}}\star XX\\ &\mathbin{\|}-\frac{305}{2^{12}}\star YY\mathbin{\|}\frac{61}{2^{12}}\star XI\mathbin{\|}-\frac{25}{2^{12}}\star ZX\mathbin{\|}-\frac{5}{2^{12}}\star XZ \end{aligned}

built from δ0\delta_0, H and S as in § 3. The weights of ZIZI, IZIZ and ZZZZ come from the diagonal of H~\widetilde{H}, and the other six from its off-diagonal entries. Each term m2k⋆P\frac{m}{2^k}\star P compiles to a single action.

Running the Program. In Hamilton, the snapshot at time t=j/2nt=j/2^n runs j2n⋆p\frac{j}{2^n}\star p, whose schedule is jj repetitions of one Trotter step: the nine actions in sequence, each for 2−n2^{-n} 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 kk of the weights, which fixes the rounding error, and the refinement level nn, 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 (n=4n = 4) add up to more than two thousand, where the experiment needs three for any tt. Smaller circuits for the same unitary are reachable by rewriting alone: the equational theory of Πk\Pi_k is complete, so every Πk\Pi_k 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^{-1})
nnk=8k = 8k=10k = 10k=12k = 12
1243.0225.5220.2
272.870.359.8
323.325.413.3
423.613.82.5
825.39.92.8
∞\infty25.39.92.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 pp, remains; more bits lower it. Figure 8 shows the same convergence along a trajectory: ∣a3(t)∣2|a_3(t)|^2 departs from the exact curve by up to 0.17 at n=2n = 2, and by at most 0.0042 at n=4n = 4. At k=12k = 12 and n≥4n \ge4 the frequency error is at most 2.8 cm−1^{-1}, below the experiment’s 3.3 cm−1^{-1}: 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. Πk\Pi_k [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 Πk\Pi_k 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 Πk\Pi_k, but the full calculus is richer: Carette et al. [ [3] extend Πk\Pi_k 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. [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
  2. [2]S. Brookes. 1993. Full Abstraction for a Shared Variable Parallel Language. In Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, 98–109.
  3. [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. [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. [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. [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
  7. [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
  8. [9]E. Farhi, J. Goldstone, and S. Gutmann. 2014. A Quantum Approximate Optimization Algorithm. (2014). arXiv:1411.4028.arxiv.org/abs/1411.4028
  9. [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
  10. [11]Richard P. Feynman. 1982. Simulating Physics with Computers. International Journal of Theoretical Physics 21, 6/7 (1982), 467–488. doi:10.1007/BF02650179DOI
  11. [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
  12. [14]B. C. Hall. 2015. Lie Groups, Lie Algebras, and Representations (2nd ed.). Springer. doi:10.1007/978-3-319-13467-3DOI
  13. [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
  14. [16]A. Yu. Kitaev. 1995. Quantum measurements and the Abelian Stabilizer Problem. (1995). arXiv:quant-ph/9511026.
  15. [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
  16. [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
  17. [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.
  18. [21]R. Milner. 2007. Elements of interaction. ACM, 1991. doi:10.1145/1283920.1283948
  19. [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
  20. [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
  21. [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
  22. [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
  23. [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
  24. [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
  25. [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

Paper details

vlnc:W_d8s8xkv6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 13

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude

View statement
Looking for related papers…
Contents