betaFeedback

WorksComputer Science

Simulating Quantum Computation Using Probabilistic Programming

Abstract

Developing quantum programs requires not only running them on quantum hardware but also simulating them on classical hardware. Because the meaning of a quantum program can be defined in terms of state vectors, it can be viewed as a form of weighted nondeterminism and simulated using any implementation of probabilistic programming that supports complex or at least negative weights. In this study, we compile a high-level quantum programming language to one such implementation of probabilistic programming, a solver for factor graph grammars. We also extend the solver with an optimization that commutes the tensor operations einsum\mathsf{einsum} and expand\mathsf{expand}. We prove that the compiler and the optimization preserve the denotational semantics of the source language. We perform benchmarks that show our straightforward implementation, by repurposing existing infrastructure for probabilistic programming, attains simulation performance in the ballpark of several other quantum simulators.

CCS Concepts: • Theory of computation → Probabilistic computation; • Computer systems organization → Quantum computing.

Additional Key Words and Phrases: probabilistic programming, quantum simulation, tensor

Introduction

Quantum computations are still tricky to design today. In order to understand and validate quantum programs, it is not enough to use quantum hardware to run them; we also need to use classical hardware to simulate them, even if we can only simulate toy problems. Due to the inherent probabilistic behavior of quantum computation, simulation often involves predicting—either exactly or approximately—the probability distribution of outcomes of a computation, possibly as a function of some variable input or initialization. The formal representation of the computation being simulated can be regarded as a quantum programming language. For instance, a quantum circuit is a program comprised of quantum gates operating on wires.

Typically, the semantics of quantum programs is defined by linear-algebra operations on vector spaces of quantum states. For instance, a quantum gate may denote a unitary linear transformation, and these denotations of individual quantum gates may be composed into the overall denotation of a program by additional operations such as tensor product. Simulating a program amounts to computing its overall denotation. However, denotations are vectors of high dimensionality (exponential in the number of qubits), so it can take too much time and memory for a simulator to naively represent them as arrays and iterate over them to compose them. Instead, quantum simulators incorporate various optimizations, which require either special hardware or algorithms based on the qubit model [12].

An alternative view of quantum computation focuses on interpreting the exponentially many dimensions of quantum state vectors as a form of nondeterminism. After all, it has long been known that quantum computation involves “negative probability” [15, 31]. More recently, researchers have explored the use of probabilistic programming to simulate quantum correlations [33] and understand quantum programming [22]. Nevertheless, there seems to be no conclusion on how much probabilistic programming can simulate quantum computation. Contemporaneously with quantum programming, many probabilistic programming languages have been designed in the past few decades [8, 25, 30, 40], among others, along with optimized algorithms for probabilistic inference. These developments lead to a natural question: can probabilistic programming help us simulate quantum computation?

In this paper, we show that yes, it can. This claim is supported by compiling a representative quantum language to a representative probabilistic language with little work and yielding competitive performance with other quantum simulators, instead of building a quantum simulator from scratch. This approach has several motivations:

  • Sharing techniques such as optimizations among implementations can help us understand and improve them.

  • An easy way to implement a classical simulator for a new quantum language may be to compile the language to an existing probabilistic language.

  • The relationship between quantum and probabilistic programming deserves investigation when it comes to questions such as expressivity.

Our contributions are as follows.

  1. We give the pure quantum programming language ISO [36] an elementary denotational semantics that differs from the standard qubit and state vector model.

  2. We formalize factor graph grammars (FGGs) [9], a graphical representation of probabilistic computation, as a language of tensor equations that includes einsum, expand, and scatter expressions. We give FGGs a denotational semantics that allows negative probability.

  3. We compile ISO to FGGs.

  4. We extend the existing FGG solver with a new optimization based on equation rewriting.

  5. We prove the semantic correctness of our compiler and our new optimization.

  6. We benchmark our and other simulators on a variety of quantum algorithms. These benchmarks show that our performance is in the ballpark of other simulators, thanks both to our new optimization and existing optimizations in the FGG solver. We hence demonstrate that quantum simulation can benefit from repurposing infrastructure for probabilistic programming.

In § 2, we give a motivating example that shows the similarity between quantum and probabilistic programming. After defining the source language in § 3 and the target language in § 4, we show in § 5 how to compile the source language to the target language while preserving denotational semantics. In § 6, we show optimizations that build on the efficiency of the current FGG solver. In § 7, we describe benchmarks that measure the efficiency of our and other simulators. We discuss related work in § 8 and future work in § 9.

Motivation

We first motivate the design of a quantum programming language, then highlight the promise of compiling it to a probabilistic programming language.

From Quantum Circuit to Higher-Level Quantum Programming

A standard way to describe a computation is to draw a circuit diagram. For instance, the following circuit shows a “fair quantum coin toss”:

∣0⟩  −  H  −(1)\lvert0 \rangle\;-\; \boxed{H}\;- \tag*{(1)}

This circuit initializes a qubit to the state ∣0⟩\lvert0 \rangle, then applies to it a Hadamard gate HH, which is one of the most fundamental quantum gates. The result is a superposition of two states ∣0⟩\lvert0 \rangle and ∣1⟩\lvert1 \rangle. It is only when we measure this quantum coin that we observe one of the two possible outcomes (head and tail, so to speak), each with probability 50%.

The quantum circuit above precisely describes the operations we want to perform, but as a description, it has three problems. First, it does not capture the intuition of a “quantum coin”: there is no nondeterminism construct in (1) where ∣1⟩|1\rangle appears alongside ∣0⟩|0\rangle. Second, circuits relegate us to drawing wires that represent qubits and gates that operate on qubits. Qubits are convenient for a quantum computer, but tedious for humans when the circuit gets bigger or repetitive. The third problem is there is no unified way to build a large circuit by composing parts already defined. Except for standard gates like Hadamard HH, there is no standard notation for one circuit to refer to another by name.

Fortunately, this is not the first time we encounter such problems. Experiences from classical programming tell us that a well-designed programming language can often alleviate the burden for programmers. For instance, pattern matching makes it possible to write clear conditions without the need of deeply nested if-statements. Therefore, researchers introduce many classical ideas from programming languages to quantum programming, thus providing higher abstraction and freeing programmers from qubits and wires.

To see how the three problems above can be addressed, consider how our source language ISO expresses the same “fair quantum coin toss”:

Hadamard::B↔B{ff↔12ff+12tt;tt↔12ff−12ttHadamard ff(2)\begin{aligned} \textbf{Hadamard} &:: \mathbb{B} \leftrightarrow\mathbb{B}\\ \left\{ \begin{aligned} \mathtt{ff} &\leftrightarrow\frac{1}{\sqrt{2}}\mathtt{ff}+\frac{1}{\sqrt{2}}\mathtt{tt};\\ \mathtt{tt} &\leftrightarrow\frac{1}{\sqrt{2}}\mathtt{ff}-\frac{1}{\sqrt{2}}\mathtt{tt} \end{aligned} \right.\\ \textbf{Hadamard}\ \mathtt{ff} \tag*{(2)} \end{aligned}

We define a function with the type B↔B\mathbb{B} \leftrightarrow\mathbb{B}. The type B\mathbb{B} represents one qubit, whose two basic values ff\mathtt{ff} and tt\mathtt{tt} correspond to ∣0⟩|0\rangle and ∣1⟩|1\rangle in popular notation. The bidirectional arrow ↔\leftrightarrow indicates that this function is reversible: it can be applied either left-to-right or right-to-left. The last line of (2) applies Hadamard left-to-right: Because the input ff\mathtt{ff} matches the left hand side of the first clause, the output is the linear combination 12ff+12tt\frac{1}{\sqrt{2}}\mathtt{ff}+\frac{1}{\sqrt{2}}\mathtt{tt} on the right hand side. For such a superposition state, the squares of the coefficients in front of basic values must add up to 1. If we were to apply Hadamard to ff\mathtt{ff} right-to-left instead, then the right sides of both clauses would match fractionally, to produce the corresponding linear combination 12ff+12tt\frac{1}{\sqrt{2}}\mathtt{ff}+\frac{1}{\sqrt{2}}\mathtt{tt} of the left hand sides.

Even though this representation of the Hadamard gate looks much longer than the circuit HH or the matrix 12[111−1]\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix} at first glance, it captures the intuition of a quantum coin by linear combinations of basic values. Since we use types like B\mathbb{B}, we can avoid mentioning qubits explicitly. Thus, we can replace the type B\mathbb{B} with a different one and represent a reversible gate on multiple qubits without the need of drawing all of them explicitly, which reduces the work tremendously when the circuit size becomes larger. For instance, if we have a type aa, we can use a⊕aa \mathbin{\oplus} a to represent the union type whose left and right values are both of type aa. Suppose we define injl\mathit{in}_{j_l} and injr\mathit{in}_{j_r}—and in turn, construct the left and right value of a union type respectively. We can define the following function:

Hadamard*::a⊕a↔a⊕a{injl x↔12(injl x)+12(injr x);injr x↔12(injl x)−12(injr x)(3)\begin{aligned} \textbf{Hadamard*} &:: a \mathbin{\oplus} a \leftrightarrow a \mathbin{\oplus} a\\ \left\{ \begin{aligned} \mathit{in}_{j_l}\ x &\leftrightarrow\frac{1}{\sqrt{2}}(\mathit{in}_{j_l}\ x)+\frac{1}{\sqrt{2}}(\mathit{in}_{j_r}\ x);\\ \mathit{in}_{j_r}\ x &\leftrightarrow\frac{1}{\sqrt{2}}(\mathit{in}_{j_l}\ x)-\frac{1}{\sqrt{2}}(\mathit{in}_{j_r}\ x) \end{aligned} \right. \tag*{(3)} \end{aligned}

Once we have these function definitions, we can invoke them later in new definitions. Thus, we get a larger quantum program by composing smaller ones.

Simulating Quantum Programming with Probabilistic Programming

Well-designed programming languages like above solve all three problems with the circuit model. But writing nice programs is not enough. We also want to run the programs. Since quantum computers are not widely available yet, we want to simulate the programs on a classical computer. Even without the consideration of optimization, implementing such a simulator already takes a lot of work [12]. Worse, a naive implementation can only simulate very few qubits and gates, thus making it infeasible.

Consider the programs Hadamard and Hadamard* in § 2.1. Whereas Hadamard denotes a 2×22 \times2 matrix 12[111−1]\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, the more general program Hadamard* denotes a 2n+1×2n+12^{n+1} \times2^{n+1} matrix

12[I2nI2nI2n−I2n](4)\frac{1}{\sqrt{2}} \begin{bmatrix} \mathbf{I}_{2^n} & \mathbf{I}_{2^n} \\ \mathbf{I}_{2^n} & -\mathbf{I}_{2^n} \end{bmatrix} \tag*{(4)}

where nn is the number of qubits required by the type aa. A naive implementation would use 4n+14^{n+1} locations to store all numbers in the matrix. Because of the exponential increase of memory requirement, a naive simulator cannot scale very well. But if we observe the structure of Hadamard*, we can see that it can be split into four 2n×2n2^n \times2^n blocks, each a scalar multiple of an identity matrix. Thus, we only need to store the size of each block and their coefficients, saving a lot of space.

This observation is not unique to this quantum computation, or to quantum programming. Probabilistic programming has been using inference algorithms that can be implemented as efficient tensor operations for a long time [7, 26, 35]. The implementations of these algorithms, such as sum-product networks, don’t assume that the probabilities have to be positive or even real numbers. Also, the linear combinations in (2) and (3) above resemble the ambiguous operator amb in probabilistic programming [8, 29]. The similarity in both implementation and syntax makes it promising to simulate quantum programming with probabilistic programming. If we have a new quantum language, it should be easy to simulate it by compiling it to a probabilistic language that already has efficient inference algorithms. Then we get a quantum simulator almost for free.

In this paper, we use factor graph grammars (FGGs) [9] as an instance of a probabilistic language that can serve as a compilation target. In the next few sections, we introduce in detail how to compile the pure quantum programming language ISO to FGGs.

Source Language: ISO

Recall that in order to justify our main claim—that probabilistic programming can help us simulate quantum computation—we compile a quantum language to a probabilistic language. To formulate this compilation, we require that the source language satisfy two criteria.

  1. First, we require that the source language expresses exactly terminating pure quantum programs. We eliminate non-terminating programs because most quantum algorithms terminate, and the meaning of non-terminating quantum programs is still ongoing research [2]. We eliminate non-pure programs, i.e., programs that have measurements and so are irreversible, because reversibility is a key postulate for quantum computation [32].

  1. Second, we require that the source language have a clear semantics. This way, to prove that the simulation does capture the meaning of a quantum program, we just need to prove that the compilation from quantum programs to probabilistic programs preserves the semantics.

Any quantum programming language satisfying the two criteria above can serve our purpose. Here, we choose ISO [36] as a representative quantum programming language. ISO satisfies the two criteria above.

  1. First, it is straightforward to pick a subset of ISO that expresses exactly terminating pure quantum programs. For the terminating part, ISO can be simplified or extended to serve different purposes easily. In fact, ISO has been tailored to demonstrate both the Curry-Howard correspondence between quantum programs and proofs as well as the Turing completeness of quantum computing [5]. Thus, we can choose a subset of ISO that allows only terminating programs. For the pure part, the support of reversibility is at the core of ISO. One of its main features, symmetric pattern matching, behaves like isomorphisms. This feature naturally models unitary gates in quantum computing.

  1. Second, ISO’s type system benefits our presentation of denotational semantics and correctness proof. Because ISO abstracts away qubits by algebraic data types, we can give it a clear denotational semantics, which in turn makes the correctness proof straightforward.

We give the syntax, the typing system, and the denotational semantics of ISO below.

Syntax

The syntax of ISO is shown in Figure 1. In ISO, a program is either an iso ω\omega or a term tt.

The syntax of ISO

Programs (Progiso)(Prog_{iso}) prog::=ω∣t\mathrm{prog} ::= \omega\mid t

Isos (Isoiso)(Iso_{iso}) ω::={v1↔e1⋯vn↔en}\omega::= \{v_1 \leftrightarrow e_1 \cdots v_n \leftrightarrow e_n\}

Terms (Termiso)(Term_{iso}) t::=()∣x∣inj⁡l t∣inj⁡r t∣⟨t1,t2⟩∣ω t∣let⁡ p=t1 in⁡ t2∣t1+t2∣αtt ::= () \mid x \mid\operatorname{inj}_{l}\ t \mid\operatorname{inj}_{r}\ t \mid\langle t_1,t_2\rangle\mid\omega\ t \mid\operatorname{let}\ p=t_1\ \operatorname{in}\ t_2 \mid t_1+t_2 \mid\alpha t

Extended values (ExtValueiso)(ExtValue_{iso}) e::=v∣e1+e2∣αe∣let⁡ p1=ω p2 in⁡ ee ::= v \mid e_1+e_2 \mid\alpha e \mid\operatorname{let}\ p_1=\omega\ p_2\ \operatorname{in}\ e

Pure values (Valueiso)(Value_{iso}) v::=()∣x∣inj⁡l v∣inj⁡r v∣⟨v1,v2⟩v ::= () \mid x \mid\operatorname{inj}_{l}\ v \mid\operatorname{inj}_{r}\ v \mid\langle v_1,v_2\rangle

Patterns (Patterniso)(Pattern_{iso}) p::=()∣x∣⟨p1,p2⟩p ::= () \mid x \mid\langle p_1,p_2\rangle

Value and term variables xx

Weights α∈C\alpha\in\mathbb{C}

Value types (Typeisoval)(Type^{\mathrm{val}}_{iso}) a,b::=1∣a⊗b∣a⊕ba,b ::= 1 \mid a \otimes b \mid a \oplus b

Iso types (Typeisoiso)(Type^{\mathrm{iso}}_{iso}) T::=a↔bT ::= a \leftrightarrow b

Figure 1. The syntax of ISO.

An iso consists of a collection of clauses v↔ev \leftrightarrow e, each with a pair of pure value vv on the left and an extended value ee on the right. Extended values extend pure values with combination (e1+e2)(e_1 + e_2), scale (αe)(\alpha e), and local binding (let). Thus, an iso has the syntax of pattern matching, and it represents a unitary operation.

A term is similar to an extended value. The difference is that in a let term, the right hand side can be any other term, while in an extended value, the right hand side has to be ω p\omega\ p. This requirement makes it easy to turn each iso term into another iso term that represents the inverse of the unitary operation. Pure values, extended values, and patterns are all subsets of terms.

The weights α\alpha in extended values and terms range over complex numbers.

With this syntax, Hadamard in Eq. (2) can be written as follows:

Hadamard::1⊕1↔1⊕1{inj⁡l()↔12inj⁡l()+12inj⁡r()inj⁡r()↔12inj⁡l()−12inj⁡r()(5)\begin{aligned} \textbf{Hadamard} &:: 1 \oplus1 \leftrightarrow1 \oplus1 \\ &\left\{ \begin{aligned} \operatorname{inj}_{l}() &\leftrightarrow\frac{1}{\sqrt{2}}\operatorname{inj}_{l}() + \frac{1}{\sqrt{2}}\operatorname{inj}_{r}() \\ \operatorname{inj}_{r}() &\leftrightarrow\frac{1}{\sqrt{2}}\operatorname{inj}_{l}() - \frac{1}{\sqrt{2}}\operatorname{inj}_{r}() \end{aligned} \right. \tag*{(5)} \end{aligned}

Hadamard inj⁡l()\operatorname{inj}_{l}()

Type System

ISO uses a standard linear type system, shown in Figure 2. We assume that a typing context Δ\Delta has no duplicate variable names. We write Δ1;Δ2\Delta_{1};\Delta_{2} to concatenate two typing contexts.

The type system of ISO (abridged)

Figure 2. The type system of ISO (abridged)

For every nonterminal in the syntax, we have a typing judgment form. For terms, we have typing judgments of the form Δ⊢tt:a\Delta\vdash_{t} t : a, where Δ\Delta is a typing context, tt is a term, and aa is a value type. Since pure values, extended values, and patterns are all subsets of terms, the typing judgments of pure values Δ⊢vv:a\Delta\vdash_{v} v : a, extended values Δ⊢ee:a\Delta\vdash_{e} e : a, and patterns Δ⊢pp:a\Delta\vdash_{p} p : a are defined in a similar way and omitted here.

Based on the typing rules of pure values, extended values, and patterns, we have the typing rule of isos at the bottom of Figure 2. The constraint OD⁡a({v1,…,vn})\operatorname{OD}_{a}(\{v_{1},\ldots,v_{n}\}) takes a value type aa and a set of pure values {v1,…,vn}\{v_{1},\ldots,v_{n}\} of type aa. It guarantees that v1,…,vnv_{1},\ldots,v_{n} cover all possible values of type aa (exhaustive) and no two vi,vjv_{i},v_{j} match the same value (non-overlapping). The constraint OD⁡bext\operatorname{OD}^{\mathrm{ext}}_{b} does the same work on extended values. The two constraints and the unitary side-condition together ensure that an iso is reversible and thus implementable as a quantum gate. Once a program satisfies these constraints, we can ignore them in the compilation and simulation, whose correctness does not depend on the constraints. Therefore, we omit the definitions of the constraints. We refer readers to Sabry et al. [36] for the details of OD and ODext\mathrm{OD}^{\mathrm{ext}}.

Denotational Semantics

There have been a lot of attempts to give a quantum programming language a denotational semantics [2, 11, 37, 39]. ISO and its variants also have different denotational semantics based on Hilbert spaces [36] or category theory [6, 13]. Instead of emphasizing the reversible behavior of quantum programs and using linear operators in Hilbert spaces, here we focus on the left-to-right direction of an iso and think of it as the quantum version of a conditional probability distribution. To define this denotational semantics of ISO, we first define semantic values of ISO:

Semantic Values(VI)VI::=()∣⟨VI1,VI2⟩∣inj⁡lVI∣inj⁡rVI\text{Semantic Values}\quad(\mathcal{V}_{I})\quad\mathcal{V}_{I} ::= () \mid\langle\mathcal{V}_{I1},\mathcal{V}_{I2}\rangle\mid\operatorname{inj}_{l}\mathcal{V}_{I} \mid\operatorname{inj}_{r}\mathcal{V}_{I}

For any type aa, its semantic values can then be thought to form a basis of a Hilbert space. Types in ISO also have their semantics. The semantics of a type aa in ISO is defined as a set ⟦a⟧\llbracket a \rrbracket of semantic values:

⟦1⟧={()}(6)\llbracket1 \rrbracket= \{()\} \tag*{(6)}
⟦a⊕b⟧={inj⁡lv∣v∈⟦a⟧}∪{inj⁡rv∣v∈⟦b⟧}(7)\llbracket a \oplus b \rrbracket= \{\operatorname{inj}_{l}v \mid v \in\llbracket a \rrbracket\} \cup\{\operatorname{inj}_{r}v \mid v \in\llbracket b \rrbracket\} \tag*{(7)}
⟦a⊗b⟧={⟨v1,v2⟩∣v1∈⟦a⟧,v2∈⟦b⟧}(8)\llbracket a \otimes b \rrbracket= \{\langle v_{1},v_{2}\rangle\mid v_{1} \in\llbracket a \rrbracket,v_{2} \in\llbracket b \rrbracket\} \tag*{(8)}

Based on semantic values, we can define ISO environments:

Definition 3.1 (ISO Environment). Given a typing context Δ\Delta, a corresponding environment δ\delta is a mapping that maps each variable x∈dom⁡(Δ)x \in\operatorname{dom}(\Delta) to a semantic value of type Δ(x)\Delta(x). We use ⟦Δ⟧\llbracket\Delta\rrbracket to represent the set of environments that correspond to a typing context Δ\Delta.

We write Env⁡I\operatorname{Env}_{I} to represent the collection of ISO environments. We use ∅\varnothing to represent an environment whose domain is empty, and {(x,v)}\{(x,v)\} to represent a singleton environment that maps one variable xx to vv.

A term denotes a function from an environment and a semantic value to a weight. Equations (9) to (17) define this denotation by induction on the typing judgment. The denotational semantics of patterns, pure values, and extended values are defined in a similar way and can be found in Appendix § 13.

⟦∅⊢t():1⟧(∅,())=1(9)\llbracket\varnothing\vdash_{t} () : 1 \rrbracket(\varnothing,()) = 1 \tag*{(9)}
⟦x:a⊢tx:a⟧({(x,v′)},v)={1if v′=v0otherwise(10)\llbracket x : a \vdash_{t} x : a \rrbracket(\{(x,v')\},v) = \begin{cases} 1 & \text{if } v' = v \\ 0 & \text{otherwise} \end{cases} \tag*{(10)}
⟦Δ⊢tinj⁡lt:a⊕b⟧(δ,inj⁡iv)={⟦Δ⊢tt:a⟧(δ,v)if i=l0if i=r(11)\llbracket\Delta\vdash_{t} \operatorname{inj}_{l}t : a \oplus b \rrbracket(\delta,\operatorname{inj}_{i}v) = \begin{cases} \llbracket\Delta\vdash_{t} t : a \rrbracket(\delta,v) & \text{if } i=l \\ 0 & \text{if } i=r \end{cases} \tag*{(11)}
⟦Δ⊢tinj⁡rt:a⊕b⟧(δ,inj⁡iv)={⟦Δ⊢tt:b⟧(δ,v)if i=r0if i=l(12)\llbracket\Delta\vdash_{t} \operatorname{inj}_{r}t : a \oplus b \rrbracket(\delta,\operatorname{inj}_{i}v) = \begin{cases} \llbracket\Delta\vdash_{t} t : b \rrbracket(\delta,v) & \text{if } i=r \\ 0 & \text{if } i=l \end{cases} \tag*{(12)}
⟦Δ1;Δ2⊢t⟨t1,t2⟩:a⊗b⟧(δ1∪δ2,⟨v1,v2⟩)=⟦Δ1⊢tt1:a⟧(δ1,v1)⋅⟦Δ2⊢tt2:b⟧(δ2,v2)(13)\llbracket\Delta_{1};\Delta_{2} \vdash_{t} \langle t_{1},t_{2}\rangle: a \otimes b \rrbracket(\delta_{1} \cup\delta_{2},\langle v_{1},v_{2}\rangle) = \llbracket\Delta_{1} \vdash_{t} t_{1} : a \rrbracket(\delta_{1},v_{1}) \cdot\llbracket\Delta_{2} \vdash_{t} t_{2} : b \rrbracket(\delta_{2},v_{2}) \tag*{(13)}
⟦Δ⊢tωt:b⟧(δ,v′)=∑v∈⟦a⟧⟦Γi ω:a↔b⟧(v,v′)⋅⟦Δ⊢tt:a⟧(δ,v)(14)\llbracket\Delta\vdash_{t} \omega t : b \rrbracket(\delta,v') = \sum_{v \in\llbracket a \rrbracket} \llbracket\Gamma_{i}\ \omega: a \leftrightarrow b \rrbracket(v,v') \cdot\llbracket\Delta\vdash_{t} t : a \rrbracket(\delta,v) \tag*{(14)}
⟦Δ1;Δ2⊢tlet⁡ p=t1 in⁡ t2:b⟧(δ1∪δ2,v′)=∑δ1′∈⟦Δ1⟧∑δ2′∈⟦Δ2⟧⟦Δ1⊢tt1:a⟧(δ1,v)⋅⟦Δ′⊢pp:a⟧(δ2′,v)⋅⟦Δ2;Δ2′⊢tt2:b⟧(δ2∪δ2′,v′)(15)\begin{aligned} \llbracket\Delta_{1};\Delta_{2} \vdash_{t} \operatorname{let}\ p=t_{1}\ \operatorname{in}\ t_{2}:b \rrbracket(\delta_{1}\cup\delta_{2},v') \\ &= \sum_{\delta'_1 \in\llbracket\Delta_1 \rrbracket} \sum_{\delta'_2 \in\llbracket\Delta_2 \rrbracket} \llbracket\Delta_1 \vdash_t t_1 : a \rrbracket(\delta_1,v) \cdot\llbracket\Delta' \vdash_p p : a \rrbracket(\delta'_2,v) \cdot\llbracket\Delta_2;\Delta'_2 \vdash_t t_2 : b \rrbracket(\delta_2 \cup\delta'_2,v') \tag*{(15)} \end{aligned}
⟦Δ⊢tt1+t2:a⟧(δ,v)=⟦Δ⊢tt1:a⟧(δ,v)+⟦Δ⊢tt2:a⟧(δ,v)(16)\llbracket\Delta\vdash_t t_1 + t_2 : a \rrbracket(\delta,v) = \llbracket\Delta\vdash_t t_1 : a \rrbracket(\delta,v) + \llbracket\Delta\vdash_t t_2 : a \rrbracket(\delta,v) \tag*{(16)}
⟦Δ⊢tαt:a⟧(δ,v)=α⋅⟦Δ⊢tt:a⟧(δ,v)(17)\llbracket\Delta\vdash_t \alpha t : a \rrbracket(\delta,v) = \alpha\cdot\llbracket\Delta\vdash_t t : a \rrbracket(\delta,v) \tag*{(17)}

An iso denotes a function from a pair of semantic values to a weight:

⟦⊢i{v1↔e1⋯vn↔en}:a↔b⟧(v,v′)=∑i=1n∑δ∈⟦Δ⟧⟦Δ⊢vvi:a⟧(δ,v)⋅⟦Δ⊢eei:b⟧(δ,v′)(18)\llbracket\vdash_i \{v_1 \leftrightarrow e_1 \cdots v_n \leftrightarrow e_n\} : a \leftrightarrow b \rrbracket(v,v') = \sum_{i=1}^{n} \sum_{\delta\in\llbracket\Delta\rrbracket} \llbracket\Delta\vdash_v v_i : a \rrbracket(\delta,v) \cdot\llbracket\Delta\vdash_e e_i : b \rrbracket(\delta,v') \tag*{(18)}

Target Language: Factor Graph Grammars

With the source language at hand, we can now consider the criteria for the target probabilistic language. We consider four criteria.

  1. First, the target language should be general enough to allow negative or complex weights. Without such generality, representing quantum amplitudes faithfully becomes difficult.

  1. Second, the target language should have a clear semantics. Without such a semantics, we cannot guarantee that the meanings of source programs and target programs match. In this case, even if we are able to run the simulation, we cannot guarantee correctness.

  1. Third, the target language should have an efficient solver. After all, our aim is to show that infrastructure of probabilistic programming can be repurposed for quantum simulation. If the target language doesn’t have a solver, there is little to reuse.

  1. Fourth, the existing solver should be easy to extend and optimize. This makes it possible to obtain a quantum simulator from the existing solver with minimal effort.

Any probabilistic programming language satisfying the four criteria above can serve our purpose. Here, we choose factor graph grammars (FGGs) [9] as a representative probability model. As the name implies, an FGG model is a grammar that generates a set of graphs, and the weight of each graph is a product of factors. FGGs satisfy the four criteria above.

  1. First, FGGs can be generalized to any semiring and thus support complex weights. In FGGs as defined by Chiang and Riley [9], the weights are non-negative and the operations are monotone, so even recursive grammars admit least-fixed-point solutions. But here, we do not consider recursive quantum programs or quantum loops [37], so the weights can be negative or even complex.

  1. Second, we can give FGGs a clear semantics by representing them as a finite set of tensor equations instead of a graph grammar. Though the two representations are equivalent, the former representation leads to a semantics closer to the ISO semantics in § 3.3, which makes the semantic preservation proof straightforward. In this representation, the left hand side of each equation is a tensor variable, and the right hand side of each equation is built out of tensor variables and operations. For instance, the following equations compute the probability of getting the same result from two flips of the same unfair coin:

coin⁡=23⋅[1 0]+13⋅[0 1]same⁡=coin⁡⋅[1001]⋅coin⁡t(19)\operatorname{coin} = \frac{2}{3} \cdot[1\ 0] + \frac{1}{3} \cdot[0\ 1] \qquad \operatorname{same} = \operatorname{coin} \cdot\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot\operatorname{coin}^{t} \tag*{(19)}
  1. Third, FGGs already have an efficient solver [8]. For instance, solving Eq. (19) gives us

coin⁡=[2313]same⁡=59.(20)\operatorname{coin} = \begin{bmatrix} \frac{2}{3} & \frac{1}{3} \end{bmatrix} \qquad \operatorname{same} = \frac{5}{9}. \tag*{(20)}

(4) Fourth, this solver is open source and turns out to be easy to extend and modify. Since its implementation is modular and doesn’t rely on the assumption that weights must be non-negative, it is also straightforward to add support for complex weights.

We give the syntax, the denotational semantics, and the sparse tensor representation of FGGs below.

Syntax

The syntax of FGGs is shown in Figure 3.

The syntax of FGGs, expressed as a system of tensor equations

Figure 3. The syntax of FGGs, expressed as a system of tensor equations.

A tensor equation t=Et = E defines the tensor variable tt by a tensor expression EE. Each tensor variable tt will turn out to denote a multidimensional array of numbers. The first four cases of tensor expressions are simple: a tensor can be a variable, a literal scalar α\alpha, the sum of two tensors, or the zero tensor of a specified shape (s,…)(s,\ldots), where each ss is a natural number.

The last three cases of tensor expressions—expand, einsum, and scatter—sport more elaborate syntax. They transform the shape of tensors. The expand operation adds dimensions to a tensor. The einsum operation generalizes scalar, vector, matrix, and elementwise multiplication. The scatter operation transforms a dense tensor to a sparse tensor.

To specify the shapes of input and output for each operation, we use index variable sequences. For instance, expand can transform the vector [6 7][6\ 7] to [6677]\left[\begin{smallmatrix}6&6\\7&7\end{smallmatrix}\right]

expand⁡([6 7][x(2)]→x(2)y(2))=[6677](21)\operatorname{expand}([6\ 7][x^{(2)}] \to x^{(2)}y^{(2)}) = \left[\begin{smallmatrix}6&6\\7&7\end{smallmatrix}\right] \tag*{(21)}

In this expression, an index variable sequence x(2)x^{(2)} is used to specify the shape of the input tensor, and another index variable sequence x(2)y(2)x^{(2)}y^{(2)} is used to specify the shape of the output tensor. Each index variable sequence consists of a sequence of index variables. Since all three tensor operations are based on index variables, below we first introduce index variables, then the three operations.

Index Variables

An index variable x(s)x^{(s)} specifies which tensor dimensions to operate on. For instance, in expand⁡([6 7][x(2)]→x(2)y(2))\operatorname{expand}([6\ 7][x^{(2)}] \to x^{(2)}y^{(2)}) from Eq. (21), the variable x(2)x^{(2)} specifies the only dimension of the input tensor [6 7][6\ 7] to be of size 2 and name it as xx. The variable y(2)y^{(2)} specifies the dimension that we want to add so that expand knows where to do the expansion. Since an index variable has an upper bound (s)(s), it iterates over integers between 0 and s−1s-1. We often elide the upper bound (s)^{(s)} even though it is formally present. We write x⃗\vec{x} or y⃗\vec{y} or z⃗\vec{z} for an index variable sequence. We denote concatenation of sequences by juxtaposition: x⃗y⃗\vec{x}\vec{y}. We define the union sequence x⃗∪y⃗\vec{x} \cup\vec{y} to be the concatenation x⃗y⃗\vec{x}\vec{y} with duplicates removed (leaving the first occurrence of each index variable, say, so x⃗y⃗∪x⃗z⃗x⃗=x⃗y⃗z⃗\vec{x}\vec{y} \cup\vec{x}\vec{z}\vec{x} = \vec{x}\vec{y}\vec{z}). The kind of equational reasoning we perform below lets us reorder tensor dimensions and corresponding sequences without loss of generality [10].

Index variables in different operations are interpreted in separate scopes. For instance, if we nest expand from Eq. (21) into another expand as below:

expand⁡(expand⁡([6 7][x(2)]→x(2)y(2))[z(2)w(2)]→x(2)z(2)w(2))(22)\operatorname{expand}(\operatorname{expand}([6\ 7][x^{(2)}] \to x^{(2)}y^{(2)})[z^{(2)}w^{(2)}] \to x^{(2)}z^{(2)}w^{(2)}) \tag*{(22)}

The underlined xx is interpreted as a new dimension added to the input of the outer expand, rather than referring to the one without underline from the inner expand. Depending on the operation, index variables in an operation can be used different numbers of times. These specific requirements are introduced below.

Two index variable sequences x⃗,y⃗\vec{x}, \vec{y} are disjoint if they share no index variable, which is written as x⃗⊥y⃗\vec{x} \perp\vec{y}. An index variable sequence x⃗\vec{x} is a subset of y⃗\vec{y} if every index variable occurring in x⃗\vec{x} also occurs in y⃗\vec{y}, which is written as x⃗⊑y⃗\vec{x} \sqsubseteq\vec{y}. We use these relations in the proof of Theorem 6.1.

expand

The expand operation adds dimensions to a tensor by repeating its existing dimensions. With this repetition, a large tensor can be represented efficiently in space and also give us a chance for further optimization (see § 6.1). Such representation is implemented in tensor libraries like PyTorch [1]. For instance, the vector [6 7][6\ 7] can be expanded in a variety of ways:

expand⁡([6 7][x(2)]→x(2))=[6677]\operatorname{expand}([6\ 7][x^{(2)}] \to x^{(2)}) = \begin{bmatrix} 6 & 6 \\ 7 & 7 \end{bmatrix}
expand⁡([6 7][x(2)]→x(2)y(2))=[6677]\operatorname{expand}([6\ 7][x^{(2)}] \to x^{(2)}y^{(2)}) = \begin{bmatrix} 6 & 6 \\ 7 & 7 \end{bmatrix}
expand⁡([6 7][x(2)]→z(2)x(2))=[6767]\operatorname{expand}([6\ 7][x^{(2)}] \to z^{(2)}x^{(2)}) = \begin{bmatrix} 6 & 7 \\ 6 & 7 \end{bmatrix}
expand⁡([6 7][x(2)]→z(2)x(2)y(3))=[666666777777]\operatorname{expand}([6\ 7][x^{(2)}] \to z^{(2)}x^{(2)}y^{(3)}) = \begin{bmatrix} 6 & 6 & 6 & 6 & 6 & 6 \\ 7 & 7 & 7 & 7 & 7 & 7 \end{bmatrix}

To take another example, the scalar 11 can be expanded to the vector [1 1]=expand⁡(1[]→x(2))[1\ 1] = \operatorname{expand}(1[] \to x^{(2)}). In the general form expand⁡(E[x⃗]→z⃗)\operatorname{expand}(E[\vec{x}] \to\vec{z}), the input index variables in x⃗\vec{x} must be distinct, the output index variables in z⃗\vec{z} must be distinct, and x⃗⊑z⃗\vec{x} \sqsubseteq\vec{z} (canonically, a prefix of z⃗\vec{z}, which is required by the optimization in § 6).

einsum

The einsum operation, or Einstein summation, generalizes scalar, vector, matrix, and elementwise multiplication, as can be seen in various tensor libraries [1, 20, 28]. These operations all define each output element as a sum of products of input elements. In order to specify which dimensions to sum over and which to multiply together, einsum uses index variables to relate the input tensors’ dimensions to the output tensor’s dimensions. For instance, multiplying two matrices E1E_1 and E2E_2 is denoted by einsum⁡(E1[xy],E2[yz]→xz)\operatorname{einsum}(E_1[xy], E_2[yz] \to xz). Also, the binary and ternary multiplications in (19) are expressed using einsum:

coin⁡=einsum⁡([23][],[1 0][x]→x)+einsum⁡([13][],[0 1][x]→x)(23)\operatorname{coin} = \operatorname{einsum}\left(\begin{bmatrix} 2 \\ 3 \end{bmatrix}[], [1\ 0][x] \to x\right) + \operatorname{einsum}\left(\begin{bmatrix} 1 \\ 3 \end{bmatrix}[], [0\ 1][x] \to x\right) \tag*{(23)}
same⁡=einsum⁡(coin⁡[x],[1001][xy],coin⁡[y]→)(24)\operatorname{same} = \operatorname{einsum}(\operatorname{coin}[x], \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}[xy], \operatorname{coin}[y] \to) \tag*{(24)}

Since coin is represented by a one-dimensional tensor, the two einsums on the right hand side of Eq. (23) both have one output index variable xx. Similarly, since same is a scalar, the einsum in Eq. (24) doesn’t have any output index variable.

In the general form einsum⁡(E1[x⃗1],…,Ek[x⃗k]→z⃗)\operatorname{einsum}(E_1[\vec{x}_1], \ldots, E_k[\vec{x}_k] \to\vec{z}), z⃗\vec{z} can be empty, or the output index variables in z⃗\vec{z} must be distinct and must each appear at least once among x⃗1,…,x⃗k\vec{x}_1, \ldots, \vec{x}_k, i.e., z⃗⊆⋃i=1kx⃗i\vec{z} \subseteq\bigcup_{i=1}^{k}\vec{x}_i.

scatter

The scatter operation transforms a dense tensor to a sparse tensor by embedding the dense tensor in a larger one and padding the rest of the output with zero. For instance, it can form the diagonal matrix [6007]\begin{bmatrix} 6 & 0 \\ 0 & 7 \end{bmatrix} from the vector [6 7][6\ 7], it can reshape a matrix into a vector, and it can enlarge a tensor along a dimension by surrounding it with zero padding. Each dimension of the output tensor is described using an axis expression ee. We explain axis expressions in § 4.6, but for now, note that one base case is that an axis expression can be an index variable. For instance, a diagonal tensor is formed by repeating the same index variable qua axis expression multiple times:

scatter⁡([6 7][x]→xx)=[6007](25)\operatorname{scatter}([6\ 7][x]\to xx)=\begin{bmatrix}6&0\\0&7\end{bmatrix} \tag*{(25)}

In the general form scatter⁡(E[x⃗]→e⋯ )\operatorname{scatter}(E[\vec{x}]\to e\cdots), the shape of the input tensor EE is the upper bounds of x⃗\vec{x}, and the shape of the output sparse tensor is the upper bounds of e⋯e\cdots. We require syntactically that each index variable in x⃗\vec{x} appear at least once in e⋯e\cdots somewhere.

Denotational Semantics

For our purposes, a tensor is a multidimensional array of numbers, indexed by tuples of non-negative integers. More specifically, each tensor has a shape, which is a tuple of positive integers (s1,…,sr)(s_1,\ldots,s_r), and the tuples I=(i1,…,ir)I=(i_1,\ldots,i_r) that index the tensor satisfy 0≤i1<s1,…,0≤ir<sr0\le i_1<s_1,\ldots,0\le i_r<s_r. The length rr of the shape is called the tensor’s rank; we say that the tensor has rr dimensions, whose sizes are s1,…,srs_1,\ldots,s_r. A rank-0 tensor is a scalar; a rank-1 tensor is a vector; a rank-2 tensor is a matrix. The element of TT at the index II is T[I]T[I].

An index function is a function δ\delta from some index variables to non-negative integers, such that 0≤δ(x(s))<s0\le\delta(x^{(s)})<s for each x(s)x^{(s)} in the domain of δ\delta. Let x⃗=x1(s1)⋯xr(sr)\vec{x}=x_1^{(s_1)}\cdots x_r^{(s_r)} be a sequence of rr index variables, not necessarily distinct. If δ\delta is an index function whose domain includes x⃗\vec{x}, then we write δ(x⃗)\delta(\vec{x}) for the index tuple (δ(x1),…,δ(xr))(\delta(x_1),\ldots,\delta(x_r)), which can be used to index a tensor of shape (s1,…,sr)(s_1,\ldots,s_r). Conversely, if II is an index tuple (i1,…,ir)(i_1,\ldots,i_r), then we write {x⃗↦I}\{\vec{x}\mapsto I\} for the index function {x1↦i1,…,xr↦ir}\{x_1\mapsto i_1,\ldots,x_r\mapsto i_r\}; here we do require the index variables in x⃗\vec{x} to be distinct. We also define the set funs⁡(x⃗)\operatorname{funs}(\vec{x}) to consist of all index functions whose domain is x⃗\vec{x}, and the set tups⁡(x⃗)\operatorname{tups}(\vec{x}) to consist of all index tuples (i1,…,ir)(i_1,\ldots,i_r) that satisfy 0≤i1<s1,…,0≤ir<sr0\le i_1<s_1,\ldots,0\le i_r<s_r.

The denotation of a tensor expression EE depends on the denotations of the tensor variables in EE. So let the environment γ\gamma be a function from tensor variables to tensors, and define the denotation ⟦E⟧γ\llbracket E\rrbracket_\gamma as follows:

⟦t⟧γ[I]=γ(t)[I](26)\llbracket t\rrbracket_\gamma[I]=\gamma(t)[I] \tag*{(26)}
⟦α⟧γ[()]=α(27)\llbracket\alpha\rrbracket_\gamma[()]=\alpha \tag*{(27)}
⟦E1+E2⟧γ[I]=⟦E1⟧γ[I]+⟦E2⟧γ[I](28)\llbracket E_1+E_2\rrbracket_\gamma[I]=\llbracket E_1\rrbracket_\gamma[I]+\llbracket E_2\rrbracket_\gamma[I] \tag*{(28)}
⟦0(s,…)⟧γ[I]=0(29)\llbracket0^{(s,\ldots)}\rrbracket_\gamma[I]=0 \tag*{(29)}
⟦expand⁡(E[x⃗]→z⃗)⟧γ[I]=⟦E⟧γ[{z⃗↦I}(x⃗)](30)\llbracket\operatorname{expand}(E[\vec{x}]\to\vec{z})\rrbracket_\gamma[I]=\llbracket E\rrbracket_\gamma[\{\vec{z}\mapsto I\}(\vec{x})] \tag*{(30)}
⟦einsum⁡(E1[x⃗1],…,Ek[x⃗k]→z⃗)⟧γ[I]=∑δ∈funs⁡(⋃i=1kx⃗i)δ(z⃗)=I∏i=1k⟦Ei⟧γ[δ(x⃗i)](31)\llbracket\operatorname{einsum}(E_1[\vec{x}_1],\ldots,E_k[\vec{x}_k]\to\vec{z})\rrbracket_\gamma[I] = \sum_{\substack{\delta\in\operatorname{funs}(\bigcup_{i=1}^{k}\vec{x}_i)\\\delta(\vec{z})=I}} \prod_{i=1}^{k}\llbracket E_i\rrbracket_\gamma[\delta(\vec{x}_i)] \tag*{(31)}
⟦scatter⁡(E[x⃗]→e⋯ )⟧γ[I]=∑δ∈funs⁡(x⃗)δ(e⋯)=I⟦E⟧γ[δ(x⃗)](32)\llbracket\operatorname{scatter}(E[\vec{x}]\to e\cdots)\rrbracket_\gamma[I] = \sum_{\substack{\delta\in\operatorname{funs}(\vec{x})\\\delta(e\cdots)=I}} \llbracket E\rrbracket_\gamma[\delta(\vec{x})] \tag*{(32)}

The first four cases are simple. Equation (27) says that a literal scalar has rank 0. Equation (28) requires two tensors to have the same shape in order to add them.

Equation (30) says that, to look up an element of an expanded tensor, we just look up the corresponding element of the original tensor, by removing from the index tuple the new dimensions introduced by expand. For instance, the element of ⟦expand⁡(E[x]→xy)⟧γ\llbracket\operatorname{expand}(E[x]\to xy)\rrbracket_\gamma at (i,j)(i,j) is defined to be the element of ⟦E⟧γ\llbracket E\rrbracket_\gamma at (i)(i).

Equation (31) defines the denotation of an einsum expression by iterating over all index tuples and summing out those index variables that do not appear in the output z⃗\vec{z}. (Recall that our syntax requires z⃗\vec{z} to be a subset of ⋃i=1kx⃗i\bigcup_{i=1}^{k}\vec{x}_i.) For instance, multiplying two matrices E1E_1 and E2E_2 is denoted by einsum⁡(E1[xy],E2[yz]→xz)\operatorname{einsum}(E_1[xy], E_2[yz] \to xz), which by (31) amounts to

⟦einsum⁡(E1[xy],E2[yz]→xz)⟧γ[(i,k)]=∑j⟦E1⟧γ[(i,j)]⟦E2⟧γ[(j,k)].(33)\llbracket\operatorname{einsum}(E_1[xy], E_2[yz] \to xz) \rrbracket_\gamma[(i,k)] = \sum_j \llbracket E_1 \rrbracket_\gamma[(i,j)]\llbracket E_2 \rrbracket_\gamma[(j,k)]. \tag*{(33)}

In the special case where z⃗=⋃i=1kx⃗i\vec{z} = \bigcup_{i=1}^{k}\vec{x}_i, we say that the einsum is summation-free:

⟦einsum⁡(E1[x⃗1],…,Ek[x⃗k]→z⃗)⟧γ[I]=∏i=1k⟦Ei⟧γ[{z⃗↦I}(x⃗i)](34)\llbracket\operatorname{einsum}(E_1[\vec{x}_1],\ldots,E_k[\vec{x}_k] \to\vec{z}) \rrbracket_\gamma[I] = \prod_{i=1}^{k}\llbracket E_i \rrbracket_\gamma[\{\vec{z} \mapsto I\}(\vec{x}_i)] \tag*{(34)}

The right hand side of (34) does not quite reduce to the right hand side of (30) when k=1k = 1, because expand allows z⃗\vec{z} to contain index variables not present in x⃗\vec{x}. This denotational semantics of einsum is similar to the one given by Wenig et al. [43].

Equation (32), for scatter, involves axis expressions, whose explanation we defer to § 4.6 below. For now, we promise that the summation on the right hand side iterates over at most one term; in other words, the δ∈funs⁡(x⃗)\delta\in\operatorname{funs}(\vec{x}) such that δ(e...)=I\delta(e\mathinner{\ldotp\ldotp\ldotp}) = I is unique. Consider the base case where e...e\mathinner{\ldotp\ldotp\ldotp} is a sequence entirely comprised of index variables. We require that x⃗\vec{x} and e...e\mathinner{\ldotp\ldotp\ldotp} contain the exact same set of index variables, and x⃗\vec{x} contain no duplicates. For instance, it could be that x⃗=x\vec{x} = x and e...=xxe\mathinner{\ldotp\ldotp\ldotp} = xx. Then, the index function δ∈funs⁡(x)\delta\in\operatorname{funs}(x) satisfies δ(e...)=δ(xx)=I\delta(e\mathinner{\ldotp\ldotp\ldotp}) = \delta(xx) = I just in case δ={x↦i}\delta= \{x \mapsto i\} and I=(i,i)I = (i,i) for some index ii. Hence (32) forms a diagonal matrix from a vector:

⟦scatter⁡(E[x]→xx)⟧γ[(i,j)]={⟦E⟧γ[(i)]if i=j0otherwise(35)\llbracket\operatorname{scatter}(E[x] \to xx) \rrbracket_\gamma[(i,j)] = \begin{cases} \llbracket E \rrbracket_\gamma[(i)] & \text{if } i=j \\ 0 & \text{otherwise} \end{cases} \tag*{(35)}

Representing Sparsity

Besides expansion and Einstein summation, our compiler makes heavy use of tensors with sparsity patterns such as diagonal matrices, zero-padded dimensions, and Kronecker products, in order to handle sum and product types. To represent such tensors compactly and operate on them efficiently, Chiang et al. [7] introduce axis expressions.

Intuitively, an axis expression denotes an injective function from some indices (into the input tensor of scatter) to an index (into the output tensor of scatter). For instance, the tensor expression scatter⁡(E[x(s)]→(s1⊕x(s)⊕s2))\operatorname{scatter}(E[x^{(s)}] \to(s_1 \oplus x^{(s)} \oplus s_2)) means to pad a vector EE with s1s_1 zeros at the beginning and s2s_2 zeros at the end, because the axis expression s1⊕x(s)⊕s2s_1 \oplus x^{(s)} \oplus s_2 denotes the injective function from the index function {x↦i}\{x \mapsto i\} to the index s1+is_1 + i, where i<si < s. And the tensor expression scatter⁡(E[x(s1)y(s2)]→(x(s1)⊗y(s2)))\operatorname{scatter}(E[x^{(s_1)}y^{(s_2)}] \to(x^{(s_1)} \otimes y^{(s_2)})) means to reshape a matrix EE into a vector, because the axis expression x(s1)⊗y(s2)x^{(s_1)} \otimes y^{(s_2)} denotes the injective function from the index function {x↦i,y↦j}\{x \mapsto i,y \mapsto j\} to the index i⋅s2+ji \cdot s_2 + j, where i<s1i < s_1 and j<s2j < s_2.

The general grammar for axis expressions ee is shown in Figure 3. Each axis expression ee has an upper bound ∣e∣\lvert e\rvert, which generalizes the upper bound of index variables:

∣x(s)∣=s∣()∣=1∣s1⊕e⊕s2∣=s1+∣e∣+s2∣e1⊗e2∣=∣e1∣⋅∣e2∣(36)\lvert x^{(s)} \rvert= s \qquad\lvert() \rvert= 1 \qquad\lvert s_1 \oplus e \oplus s_2 \rvert= s_1 + \lvert e\rvert+ s_2 \qquad\lvert e_1 \otimes e_2 \rvert= \lvert e_1\rvert\cdot\lvert e_2\rvert \tag*{(36)}

An axis expression ee denotes an integer ⟦e⟧δ\llbracket e\rrbracket_\delta between 00 and ∣e∣−1\lvert e\rvert- 1, depending on the index function δ\delta:

⟦x⟧δ=δ(x)⟦()⟧δ=0⟦s1⊕e⊕s2⟧δ=s1+⟦e⟧δ⟦e1⊗e2⟧δ=⟦e1⟧δ⋅∣e2∣+⟦e2⟧δ(37)\llbracket x\rrbracket_\delta= \delta(x) \qquad\llbracket()\rrbracket_\delta= 0 \qquad\llbracket s_1 \oplus e \oplus s_2\rrbracket_\delta= s_1 + \llbracket e\rrbracket_\delta\qquad\llbracket e_1 \otimes e_2\rrbracket_\delta= \llbracket e_1\rrbracket_\delta\cdot\lvert e_2\rvert+ \llbracket e_2\rrbracket_\delta \tag*{(37)}

For a sequence of axis expressions e...e\mathinner{\ldotp\ldotp\ldotp}, we write δ(e...)=⟦e⟧δ...\delta(e\mathinner{\ldotp\ldotp\ldotp}) = \llbracket e\rrbracket_\delta\mathinner{\ldotp\ldotp\ldotp}.

Recall that in scatter⁡(E[x⃗]→e...)\operatorname{scatter}(E[\vec{x}] \to e\mathinner{\ldotp\ldotp\ldotp}), each index variable in x⃗\vec{x} appears at least once in e...e\mathinner{\ldotp\ldotp\ldotp} somewhere, so that the function from δ∈funs⁡(x⃗)\delta\in\operatorname{funs}(\vec{x}) to δ(e...)\delta(e\mathinner{\ldotp\ldotp\ldotp}) is injective. That’s why the summation on the right hand side of Eq. (32) iterates over at most one term.

Compilation

We describe our compiler from ISO to FGGs, then prove that it preserves semantics. One feature of our approach is that the compilation is relatively straightforward to implement (about 1000 lines of Haskell).

Compiling ISO to FGGs

The key idea of our compiler is based on the denotational semantics of ISO. In § 3.3, we define the denotational semantics of ISO as a function from environments and semantic values to weights. For any given well-typed expression, if we iterate over all possible environments and semantic values, and tabulate the corresponding weights, we get a tensor that represents this function. For example, the term x:3⊢tinj⁡lx:6x : \mathbf{3} \vdash_{\mathrm{t}} \operatorname{inj}_{l} x : \mathbf{6} is typed in the context x:3x : \mathbf{3}, where 3\mathbf{3} is a shorthand for the type (1⊕1)⊕1(1 \oplus1) \oplus1, and 6\mathbf{6} is a shorthand for the type 3⊕3\mathbf{3} \oplus\mathbf{3}. An environment corresponding to x:3x : \mathbf{3} maps xx to inj⁡l(inj⁡l()),inj⁡l(inj⁡r()),\operatorname{inj}_{l}(\operatorname{inj}_{l}()), \operatorname{inj}_{l}(\operatorname{inj}_{r}()), or inj⁡r()\operatorname{inj}_{r}(). And there are six semantic values of type 6\mathbf{6}. Therefore, tabulating the possible weights of this term gives the 3×63 \times6 tensor (100000010000001000)\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix}. Based on this idea, we define a translation from ISO expressions to FGG tensor expressions. The compiler for terms and isos is shown in Figure 4. The compiler for patterns, pure values, and extended values is shown in Appendix § 14. A complete example that is based on Eq. (3) and extended from x:3⊢tinj⁡lx:6x : \mathbf{3} \vdash_{\mathrm{t}} \operatorname{inj}_{l} x : \mathbf{6} is shown in Figure 5.

Figure 4. The compiler from ISO terms and isos to FGGs

Tensor equations for the ISO program and Hadamard application

Figure 5. The ISO program in Eq. (3) with a=(1⊕1)⊕1a = (1 \oplus1) \oplus1 and an application Hadamard* (inj⁡l(inj⁡r())\operatorname{inj}_{l}(\operatorname{inj}_{r}())) can be compiled to the tensor equations above. We use 33 to represent the type (1⊕1)⊕1(1 \oplus1) \oplus1, 66 to represent the type 3⊕33 \oplus3, and 22 to represent the value inj⁡l(inj⁡r())\operatorname{inj}_{l}(\operatorname{inj}_{r}()) of type 66. These equations are labeled with the corresponding subexpressions from Eq. (3) on the left. The corresponding tensors are listed below the equations. Eqs. (a) and (k) to (m) represent rank-1 tensors; all other equations represent rank-2 tensors.

Compilation of types and typing contexts

From § 3.3, we know that every ISO value type corresponds to a finite set of semantic values. Since a semantic value can be thought of as an index, every type is compiled to a natural number—the size of the set—that indicates the upper bound of an index variable. The compiler for ISO value types is defined as follows.

comp⁡(1)=1(38)\operatorname{comp}(1) = 1 \tag*{(38)}
comp⁡(a⊕b)=comp⁡(a)+comp⁡(b)(39)\operatorname{comp}(a \oplus b) = \operatorname{comp}(a) + \operatorname{comp}(b) \tag*{(39)}
comp⁡(a⊗b)=comp⁡(a)⋅comp⁡(b)(40)\operatorname{comp}(a \otimes b) = \operatorname{comp}(a) \cdot\operatorname{comp}(b) \tag*{(40)}

Following the definition above, we can compile a typing context to an index variable sequence.

comp⁡(∅)=()(41)\operatorname{comp}(\varnothing) = () \tag*{(41)}
comp⁡(Δ,x:a)=comp⁡(Δ)xa(comp⁡(a))(42)\operatorname{comp}(\Delta, x : a) = \operatorname{comp}(\Delta)x_{a}^{(\operatorname{comp}(a))} \tag*{(42)}

Compilation of terms

The term compiler comp⁡\operatorname{comp} in Figure 4 takes a well-typed term Δ⊢tt:a\Delta\vdash_{\mathrm{t}} t : a and returns an FGG tensor expression of rank ∣Δ∣+1|\Delta| + 1. We write tt instead of the whole typing judgment for brevity. For a well-typed term tt, its denotation takes an environment corresponding to its typing context Δ\Delta and a semantic value of type aa. Therefore, the rank of the compiled tensor is ∣Δ∣+1|\Delta| + 1. Each variable x:τx : \tau in Δ\Delta has a corresponding index variable xτ(comp⁡(τ))x_{\tau}^{(\operatorname{comp}(\tau))}. The type aa corresponds to another fresh index variable xa(comp⁡(a))x_{a}^{(\operatorname{comp}(a))}. We omit the upper bound (s)(s) from an index variable x(s)x^{(s)}. Since pure values, extended values, and patterns are all subsets of terms, we relegate their compilation to Appendix § 14. We introduce comp⁡\operatorname{comp} case by case below.

The unit term ()() is compiled to an expanded vector [1][1], as shown in Eq. (m) in Figure 5.

A variable term xx is typed as x:a⊢tx:ax : a \vdash_{\mathrm{t}} x : a. As shown in § 3.3, the denotational semantics of such a term takes an environment {(x,v′)}\{(x, v')\} and a semantic value vv and returns 1 only when v′=vv' = v. Since both vv and v′v' have type aa, we should compile xx by making an identity matrix. Therefore, we start with the scalar 1 and extend it to a vector of size comp⁡(a)\operatorname{comp}(a) by expand⁡(1[])→xa\operatorname{expand}(1[]) \to x_a. Then we further extend it to an identity matrix by scatter⁡(expand⁡(1[])→xa)[xa]→xaxa\operatorname{scatter}(\operatorname{expand}(1[]) \to x_a)[x_a] \to x_a x_a. Equation (j) in Figure 5 shows an example.

comp⁡::Term⁡iso→Tensor⁡comp⁡(())=expand⁡(1[]→x1)comp⁡(x)=scatter⁡(expand⁡(1[]→xa)[xa]→xaxa)comp⁡(inj⁡l t)=einsum⁡(comp⁡(t)[comp⁡(Δ)xa],scatter⁡(expand⁡(1[]→xa)[xa]→xa(0⊕xa⊕comp⁡(b))[xaza⊕b]→comp⁡(Δ)za⊕b)if Δ⊢inj⁡l t:a⊕bcomp⁡(inj⁡r t)=einsum⁡(comp⁡(t)[comp⁡(Δ)yb],scatter⁡(expand⁡(1[]→yb)[yb]→yb(comp⁡(a)⊕yb⊕0)[ybza⊕b]→comp⁡(Δ)za⊕b)if Δ⊢inj⁡r t:a⊕bcomp⁡(⟨t1,t2⟩)=einsum⁡(comp⁡(t1)[comp⁡(Δ1)xa],comp⁡(t2)[comp⁡(Δ2)yb],scatter⁡(expand⁡(1[]→xayb)[xayb]→xayb(xa⊗yb)[xaybza⊗b]→comp⁡(Δ1)comp⁡(Δ2)za⊗b)if Δ⊢⟨t1,t2⟩:a⊗bcomp⁡(ω t)=einsum⁡(comp⁡(t)[comp⁡(Δ)xa],comp⁡(ω)[xayb]→comp⁡(Δ)yb)comp⁡(let⁡ x=t1 in⁡ t2)=comp⁡(t2[t1/x])comp⁡(let⁡ p=t1 in⁡ t2)=einsum⁡(comp⁡(t1)[comp⁡(Δ1)xa],comp⁡p(p)[comp⁡(Δ′)xa],comp⁡(t2)[comp⁡(Δ2)comp⁡(Δ′)yb]→comp⁡(Δ1)comp⁡(Δ2)yb)comp⁡(t1+t2)=comp⁡(t1)+comp⁡(t2)comp⁡(αt)=einsum⁡(α[],comp⁡(t)[comp⁡(Δ)xτ]→comp⁡(Δ)xτ)comp⁡::Iso⁡iso→Tensor⁡comp⁡({v1↔e1⋯vn↔en})=comp⁡(v1↔e1)+⋯+comp⁡(vn↔en)wherecomp⁡(v↔e)=einsum⁡(comp⁡v(v)[comp⁡(Δ)xa],comp⁡e(e)[comp⁡(Δ)yb]→xayb)comp⁡::Prog⁡iso→Prog⁡fggcomp⁡(ω)=(main⁡=comp⁡(ω))comp⁡(t)=(main⁡=comp⁡(t))\begin{aligned} \operatorname{comp} &:: \operatorname{Term}_{\mathrm{iso}} \to\operatorname{Tensor}\\ \operatorname{comp}(()) &= \operatorname{expand}(1[] \to x_{1})\\ \operatorname{comp}(x) &= \operatorname{scatter}(\operatorname{expand}(1[] \to x_{a})[x_{a}] \to x_{a}x_{a})\\ \operatorname{comp}(\operatorname{inj}_{l}\ t) &= \operatorname{einsum}(\operatorname{comp}(t)[\operatorname{comp}(\Delta)x_{a}],\\ &\qquad\operatorname{scatter}(\operatorname{expand}(1[] \to x_{a})[x_{a}] \to\\ &\qquad\qquad x_{a}(0 \oplus x_{a} \oplus\operatorname{comp}(b))[x_{a}z_{a\oplus b}] \to\\ &\qquad\qquad\operatorname{comp}(\Delta)z_{a\oplus b})\\ &\qquad\text{if }\Delta\vdash\operatorname{inj}_{l}\ t : a \oplus b\\ \operatorname{comp}(\operatorname{inj}_{r}\ t) &= \operatorname{einsum}(\operatorname{comp}(t)[\operatorname{comp}(\Delta)y_{b}],\\ &\qquad\operatorname{scatter}(\operatorname{expand}(1[] \to y_{b})[y_{b}] \to\\ &\qquad\qquad y_{b}(\operatorname{comp}(a) \oplus y_{b} \oplus0)[y_{b}z_{a\oplus b}] \to\\ &\qquad\qquad\operatorname{comp}(\Delta)z_{a\oplus b})\\ &\qquad\text{if }\Delta\vdash\operatorname{inj}_{r}\ t : a \oplus b\\ \operatorname{comp}(\langle t_{1},t_{2}\rangle) &= \operatorname{einsum}(\operatorname{comp}(t_{1})[\operatorname{comp}(\Delta_{1})x_{a}],\operatorname{comp}(t_{2})[\operatorname{comp}(\Delta_{2})y_{b}],\\ &\qquad\operatorname{scatter}(\operatorname{expand}(1[] \to x_{a}y_{b})[x_{a}y_{b}] \to\\ &\qquad\qquad x_{a}y_{b}(x_{a}\otimes y_{b})[x_{a}y_{b}z_{a\otimes b}] \to\\ &\qquad\qquad\operatorname{comp}(\Delta_{1})\operatorname{comp}(\Delta_{2})z_{a\otimes b})\\ &\qquad\text{if }\Delta\vdash\langle t_{1},t_{2}\rangle: a \otimes b\\ \operatorname{comp}(\omega\ t) &= \operatorname{einsum}(\operatorname{comp}(t)[\operatorname{comp}(\Delta)x_{a}],\operatorname{comp}(\omega)[x_{a}y_{b}] \to\operatorname{comp}(\Delta)y_{b})\\ \operatorname{comp}(\operatorname{let}\ x=t_{1}\ \operatorname{in}\ t_{2}) &= \operatorname{comp}(t_{2}[t_{1}/x])\\ \operatorname{comp}(\operatorname{let}\ p=t_{1}\ \operatorname{in}\ t_{2}) &= \operatorname{einsum}(\operatorname{comp}(t_{1})[\operatorname{comp}(\Delta_{1})x_{a}],\operatorname{comp}_{p}(p)[\operatorname{comp}(\Delta')x_{a}],\\ &\qquad\operatorname{comp}(t_{2})[\operatorname{comp}(\Delta_{2})\operatorname{comp}(\Delta')y_{b}] \to\\ &\qquad\operatorname{comp}(\Delta_{1})\operatorname{comp}(\Delta_{2})y_{b})\\ \operatorname{comp}(t_{1}+t_{2}) &= \operatorname{comp}(t_{1})+\operatorname{comp}(t_{2})\\ \operatorname{comp}(\alpha t) &= \operatorname{einsum}(\alpha[],\operatorname{comp}(t)[\operatorname{comp}(\Delta)x_{\tau}] \to\operatorname{comp}(\Delta)x_{\tau})\\ \operatorname{comp} &:: \operatorname{Iso}_{\mathrm{iso}} \to\operatorname{Tensor}\\ \operatorname{comp}(\{v_{1}\leftrightarrow e_{1}\cdots v_{n}\leftrightarrow e_{n}\}) &= \operatorname{comp}(v_{1}\leftrightarrow e_{1})+\cdots+\operatorname{comp}(v_{n}\leftrightarrow e_{n})\\ \text{where}\qquad\operatorname{comp}(v\leftrightarrow e) &= \operatorname{einsum}(\operatorname{comp}_{v}(v)[\operatorname{comp}(\Delta)x_{a}],\operatorname{comp}_{e}(e)[\operatorname{comp}(\Delta)y_{b}] \to x_{a}y_{b})\\ \operatorname{comp} &:: \operatorname{Prog}_{\mathrm{iso}} \to\operatorname{Prog}_{\mathrm{fgg}}\\ \operatorname{comp}(\omega) &= (\operatorname{main}=\operatorname{comp}(\omega))\\ \operatorname{comp}(t) &= (\operatorname{main}=\operatorname{comp}(t)) \end{aligned}

The sum terms inj⁡l t\operatorname{inj}_{l}\,t and inj⁡r t\operatorname{inj}_{r}\,t are compiled in the same way, as shown in Eqs. (h) and (i) in Figure 5. For x1:τ1,⋯ ,xn:τn⊢tinjlt:a⊕bx_1 : \tau_1, \cdots, x_n : \tau_n \vdash_{\mathrm{tinj}_{l}t} : a \oplus b, we first compile tt to a tensor of the shape (comp⁡(τ1),⋯ ,comp⁡(τn),comp⁡(a))(\operatorname{comp}(\tau_1), \cdots, \operatorname{comp}(\tau_n), \operatorname{comp}(a)). This tensor is then passed as an argument to einsum. The second argument to einsum is a sparse rank-2 tensor that has value 1 where semantic values from types aa and a⊕ba \oplus b match. For instance, if aa is 1\mathbf{1} and bb is 1⊗1\mathbf{1} \otimes\mathbf{1}, for semantic values ()() and inj⁡l()\operatorname{inj}_{l}(), this tensor has value 1; for ()() and inj⁡r((),())\operatorname{inj}_{r}((), ()), it has value 0. The result of einsum is a tensor of the shape (comp⁡(τ1),⋯ ,comp⁡(τn),comp⁡(a)+comp⁡(b))(\operatorname{comp}(\tau_1), \cdots, \operatorname{comp}(\tau_n), \operatorname{comp}(a) + \operatorname{comp}(b)).

The product term Δ1,Δ2⊢t⟨t1,t2⟩:a⊗b\Delta_1, \Delta_2 \vdash_{\mathrm{t}} \langle t_1, t_2\rangle: a \otimes b can be compiled in a similar way. The difference is we need to recursively compile two terms. Moreover, the third argument to einsum is a sparse rank-3 tensor that has 1 where semantic values from types aa, bb, and a⊗ba \otimes b match.

The application term ω t\omega\ t is compiled to an einsum whose two arguments are the results from recursively compiling the operator and the operand, as shown in Eq. (a) in Figure 5. See § 5.2 for how to compile an iso.

The let term is processed depending on what the left hand side pattern is. If the pattern is a single variable xx, we first substitute the right hand side term t1t_1 for xx in the body t2t_2, then we compile the substituted term t2[t1/x]t_2[t_1/x]. Such substitutions turn out to be beneficial for the FGG solver to detect sparsity in the quantum simulation. See § 7 for an analysis of this optimization. Otherwise, the let expression is processed in a similar way to application. The difference is there are three subterms in a let. Therefore, the compiled einsums have three arguments.

The linear combination term t1+t2t_1 + t_2 is compiled to a tensor sum, as shown in Eqs. (c) and (d).

The weighted term αt\alpha t is compiled to an einsum that multiplies a tensor by a scalar, as shown in Eqs. (e) to (g).

Compilation of isos

To compile an iso, we compile each clause to a tensor and sum them together. This compilation is therefore similar to a linear combination term. Each clause is an alternative outcome and compiled to an einsum with two arguments, which correspond to the pure value and the extended value respectively. Since the pure value and the extended value are typed in the same typing context, they share the indices corresponding to the same environment. The other index for them comes from their types. The result of the einsum is a rank-2 tensor with indices from the types of pure values and extended values. Equation (b) in Figure 5 shows an example of compiling an iso.

Compilation of programs

We compile an ISO program to an FGG equation. We generate a new tensor variable as the left hand side and compile the program to a tensor as the right hand side. As defined in Figure 4, the compiler turns repeated ISO subexpressions into repeated FGG subexpressions. Our implementation performs common subexpression elimination by introducing a distinct tensor variable for each unique ISO subexpression.

Correctness of the Compilation

To state the correctness of the compilation, we first define the compilation of semantic values and ISO environments.

For each type aa, we define a bijection comp⁡V(a,⋅)\operatorname{comp}_{\mathcal{V}}(a, \cdot) between the semantic values in ⟦a⟧\llbracket a \rrbracket and the natural numbers in {0,…,comp⁡(a)−1}\{0, \ldots, \operatorname{comp}(a) - 1\}:

comp⁡V(1,())=0(43)\operatorname{comp}_{\mathcal{V}}(\mathbf{1}, ()) = 0 \tag*{(43)}
comp⁡V(a⊕b,inj⁡l v)=comp⁡V(a,v)(44)\operatorname{comp}_{\mathcal{V}}(a \oplus b, \operatorname{inj}_{l}\ v) = \operatorname{comp}_{\mathcal{V}}(a, v) \tag*{(44)}
comp⁡V(a⊕b,inj⁡r v)=comp⁡(a)+comp⁡V(b,v)(45)\operatorname{comp}_{\mathcal{V}}(a \oplus b, \operatorname{inj}_{r}\ v) = \operatorname{comp}(a) + \operatorname{comp}_{\mathcal{V}}(b, v) \tag*{(45)}
comp⁡V(a⊗b,⟨v1,v2⟩)=comp⁡V(a,v1)⋅comp⁡(b)+comp⁡V(b,v2)(46)\operatorname{comp}_{\mathcal{V}}(a \otimes b, \langle v_1, v_2\rangle) = \operatorname{comp}_{\mathcal{V}}(a, v_1) \cdot\operatorname{comp}(b) + \operatorname{comp}_{\mathcal{V}}(b, v_2) \tag*{(46)}

This definition orders semantic values lexicographically, but any systematic ordering will work, as long as the inj⁡l\operatorname{inj}_{l}, inj⁡r\operatorname{inj}_{r}, and ⟨_,_⟩\langle\_,\_ \rangle cases in Figure 4 are adjusted accordingly.

Based on comp⁡v\operatorname{comp}_{v}, for each typing context Δ\Delta, we define a bijection comp⁡δ(Δ,⋅)\operatorname{comp}_{\delta}(\Delta,\cdot) between ISO environments in ⟦Δ⟧\llbracket\Delta\rrbracket and index tuples in tups⁡(comp⁡(Δ))\operatorname{tups}(\operatorname{comp}(\Delta)):

comp⁡δ(∅,∅)=()(47)\operatorname{comp}_{\delta}(\varnothing,\varnothing)=() \tag*{(47)}
comp⁡δ((Δ,x:a),(δ∪{(x,v)}))=comp⁡δ(Δ,δ),comp⁡v(a,v)(48)\operatorname{comp}_{\delta}((\Delta,x:a),(\delta\cup\{(x,v)\}))=\operatorname{comp}_{\delta}(\Delta,\delta),\operatorname{comp}_{v}(a,v) \tag*{(48)}

Then we can state the following theorem.

Theorem 5.1. The compilation in Figure 4 preserves the denotational semantics of well-typed ISO programs:

  • If Δ⊢tt:a\Delta\vdash_t t:a, then:

⟦Δ⊢tt:a⟧(δ,v)=⟦comp⁡(Δ⊢tt:a)⟧γ[(comp⁡δ(Δ,δ),comp⁡v(a,v))](49)\llbracket\Delta\vdash_t t:a\rrbracket(\delta,v)=\llbracket\operatorname{comp}(\Delta\vdash_t t:a)\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta,\delta),\operatorname{comp}_{v}(a,v))] \tag*{(49)}
  • If ⊢iω:a↔b\vdash_i\omega:a\leftrightarrow b, then:

⟦⊢iω:a↔b⟧(v1,v2)=⟦comp⁡(⊢iω:a↔b)⟧γ[(comp⁡v(a,v1),comp⁡v(b,v2))](50)\llbracket\vdash_i\omega:a\leftrightarrow b\rrbracket(v_1,v_2)=\llbracket\operatorname{comp}(\vdash_i\omega:a\leftrightarrow b)\rrbracket_{\gamma}[(\operatorname{comp}_{v}(a,v_1),\operatorname{comp}_{v}(b,v_2))] \tag*{(50)}

This theorem can be proved by induction on the denotational semantics of ISO. We show the proof for the let term in Appendix § 15. Other cases can be proved in a similar way.

Optimizing Einsum for Sparsity and Expansion

Once we compile ISO programs to FGGs, we can use the existing FGG solver2 to simulate quantum computation. However, large tensors encountered in probabilistic and quantum computation call for additional solver optimizations. These optimizations preserve the semantics of tensor expressions, as we prove below. They are also straightforward to implement (about 70 lines of Python added to the existing FGG solver).

Saving Space and Time with expand

Consider a quantum circuit with nn qubits initialized to state ∣0⟩|0\rangle, and the only operation in this circuit is a Hadamard gate applied to the last qubit.

Quantum circuit with $n-1$ qubits initialized to $|0\rangle$ and a Hadamard gate applied to the last qubit

Figure 9.

Since this circuit is so simple, we expect that our solver could simulate quite a few qubits. But it turns out that a naive solver—one that stores the state of nn qubits as 2n2^n numbers—cannot even simulate 30 qubits on a machine with 20 GB of RAM. Intuitively, such circuits contain a lot of repetitive patterns. We take advantage of those patterns to improve the simulator’s performance.

Suppose we have a rank-nn tensor. If every dimension has size 2, then the tensor contains 2n2^n elements, which is exponential in nn. However, if we know that every element of the tensor is 1, then we do not need to allocate memory for 2n2^n elements. We simply need to store the element 1 together with the tensor’s shape. Thus, using expand from FGGs, the tensor can be represented as expand⁡(1[]→x1(2)⋯xn(2))\operatorname{expand}(1[]\to x_1^{(2)}\cdots x_n^{(2)}), which only takes O(n)O(n) space. Similarly, scatter can be used to store sparse tensors compactly. In the representation expand⁡(E[x⃗]→z⃗)\operatorname{expand}(E[\vec{x}]\to\vec{z}) or scatter⁡(E[x⃗]→e⋯ )\operatorname{scatter}(E[\vec{x}]\to e\cdots) of a large tensor, we call the smaller tensor EE the kernel.

This representation saves not only memory but also computation. When an expanded tensor is passed as an argument to einsum, we can apply einsum to just the kernel of the tensor and expand the result to the actual shape. For example, the tensor expression

einsum⁡(expand⁡(4[]→x(2)y(3))[x(2)y(3)],expand⁡(5[]→y(3))[y(3)]→x(2)y(3))(51)\operatorname{einsum}(\operatorname{expand}(4[] \to x^{(2)}y^{(3)})[x^{(2)}y^{(3)}],\operatorname{expand}(5[] \to y^{(3)})[y^{(3)}] \to x^{(2)}y^{(3)}) \tag*{(51)}

computes the elementwise product between each row of the matrix [444444]\begin{bmatrix}4&4&4\\4&4&4\end{bmatrix} and the vector [5 5 5][5\ 5\ 5], giving [202020202020]\begin{bmatrix}20&20&20\\20&20&20\end{bmatrix}. Direct computation requires 6 multiplications. If we apply einsum to the two kernels and then expand, then since both kernels are scalars, we only need one multiplication:

expand⁡(einsum⁡(4[],5[]→[])[]→x(2)y(3))(52)\operatorname{expand}(\operatorname{einsum}(4[],5[] \to[])[] \to x^{(2)}y^{(3)}) \tag*{(52)}

In general, when an einsum is summation-free and some of its arguments are expanded tensors, we can swap the order of einsum and expand.

On the other hand, if einsum is not summation-free, swapping einsum and expand is not enough. For example, the tensor expression

einsum⁡(expand⁡(4[]→x(2)y(3))[x(2)y(3)],expand⁡(5[]→y(3))[y(3)]→x(2))(53)\operatorname{einsum}(\operatorname{expand}(4[] \to x^{(2)}y^{(3)})[x^{(2)}y^{(3)}],\operatorname{expand}(5[] \to y^{(3)})[y^{(3)}] \to x^{(2)}) \tag*{(53)}

computes the dot product between each row of the matrix [444444]\begin{bmatrix}4&4&4\\4&4&4\end{bmatrix} and the vector [5 5 5][5\ 5\ 5], giving [60 60][60\ 60]. If we do einsum first instead, by computing

expand⁡(einsum⁡(4[],5[]→[])[]→x(2)),(54)\operatorname{expand}(\operatorname{einsum}(4[],5[] \to[])[] \to x^{(2)}), \tag*{(54)}

we would get a different result [20 20][20\ 20]. We need to make up for it by multiplying a factor.

Correctness of the Optimization

Formally, our key optimization can be stated as follows. We use einsum with two arguments here. It can be generalized to einsum with more expanded arguments.

Theorem 6.1. The operations einsum and expand commute up to a factor:

⟦einsum⁡(F[x⃗],expand⁡(E[y⃗]→y⃗z⃗)[y⃗z⃗]→w⃗)⟧γ=f⋅⟦expand⁡(einsum⁡(F[x⃗],E[y⃗]→u⃗)[u⃗]→w⃗)⟧γ(55)\llbracket\operatorname{einsum}(F[\vec{x}],\operatorname{expand}(E[\vec{y}] \to\vec{y}\vec{z})[\vec{y}\vec{z}] \to\vec{w})\rrbracket_{\gamma} = f \cdot\llbracket\operatorname{expand}(\operatorname{einsum}(F[\vec{x}],E[\vec{y}] \to\vec{u})[\vec{u}] \to\vec{w})\rrbracket_{\gamma} \tag*{(55)}

where

u⃗=w⃗∖(z⃗∖x⃗),v⃗=(z⃗∖x⃗)∖w⃗,f=∏i∈v⃗∣i∣(56)\vec{u}=\vec{w}\setminus(\vec{z}\setminus\vec{x}),\qquad \vec{v}=(\vec{z}\setminus\vec{x})\setminus\vec{w},\qquad f=\prod_{i\in\vec{v}}|i| \tag*{(56)}

See Appendix § 16 for the proof of this theorem.

In Figure 4, we can see that einsum does not always take expanded tensors as arguments. Sometimes, expanded tensors are nested in scattered tensors (such as in the case for inj⁡lt\operatorname{inj}_{lt}). Fortunately, just as our optimization reduces einsum’s input from an expanded tensor to a smaller tensor, the FGG solver by Chiang et al. [7] already reduces einsum’s input from a scattered tensor to a smaller tensor. For instance, to store a diagonal matrix, it represents the matrix as scatter⁡(E[x]→xx)\operatorname{scatter}(E[x]\to xx), where EE is the vector consisting of the elements on the diagonal. To multiply a matrix FF by this diagonal matrix, the solver just multiplies FF by the vector EE:

⟦einsum⁡(F[xy],scatter⁡(E[x]→xx)[yz]→xz)⟧γ=⟦einsum⁡(F[xz],E[z]→xz)⟧γ.(57)\llbracket\operatorname{einsum}(F[xy],\operatorname{scatter}(E[x]\to xx)[yz]\to xz)\rrbracket_{\gamma} = \llbracket\operatorname{einsum}(F[xz],E[z]\to xz)\rrbracket_{\gamma}. \tag*{(57)}

After this existing einsum-scatter optimization takes effect, our new einsum-expand optimization can then take over.

Detecting Sparsity

Whereas the einsum-scatter and einsum-expand optimizations benefit both probabilistic and quantum applications, other optimizations have a much bigger impact on quantum simulation than on probabilistic inference. The reversible nature of quantum computation calls for one specific optimization: detecting when multiplying two dense matrices yields an identity matrix. In particular, the pervasive Hadamard matrix 12[111−1]\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} is its own inverse. Accordingly, after each einsum operation, our implementation checks for the specific dense result [1001]\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} and replaces it by the sparse equivalent scatter(expand(1[]→x1[] \to x) [x]→xx[x] \to xx). This sparsity detection is performed after we get the result of an einsum at runtime. Since this detection is restricted to a small matrix, it does not add much overhead to the solver. When many intermediate results match this pattern, however, it can improve the simulation performance a lot, as shown by experiment (2) in Figure 8.

Four-panel plots: (1) Hadamard to the last qubit; (2) Deutsch-Jozsa with the even oracle; (7) Bell state; (10) Hadamard in parallel with Deutsch-Jozsa. Axes show Number of qubits, Running time (seconds), and Compile time (seconds). Legend: FGG solver with expand and $\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}$ opts; FGG solver with expand opt; FGG solver with $\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}$ opt; FGG solver without any opt; FGG compiled from ISO.

Figure 8. Simulation and compilation times of our FGG-based simulators, comparing different sets of optimizations. For each plot, the xx-axis shows the number of qubits, the left yy-axis shows run time in seconds, and the right yy-axis shows compilation time in seconds.

Benchmark

We perform benchmarks to answer three questions about our approach of quantum simulation by compiling through FGGs.

  1. How does our approach compare in performance to other quantum simulators?

  2. On what kinds of problems does our implementation perform well?

  3. How do the components of our implementation (namely, the compiler and the solver optimizations) contribute to our performance?

It turns out that our approach attains performance in the ballpark of several other quantum simulators. It takes advantage of sparsity and preserves it through parallel composition. Each component of our implementation improves performance on some benchmarks. We first explain the design of our benchmarks in § 7.1, then discuss the results in § 7.2.

Benchmark Design

We measure the run times of the following simulators:

  1. Compile ISO to FGGs directly as described in § 5, then use the FGG solver.

  2. Compile ISO to PERPL, a higher-level probabilistic programming language [8], then use the existing compiler from PERPL to FGGs, followed by the FGG solver. We include this pipeline as another demonstration of reuse of existing probabilistic programming infrastructure.

  3. Qiskit with the Aer state-vector simulator [23].3

  4. Cirq with the qsim state-vector simulator [14].

  5. Quimb, a tensor network contraction simulator [18].

  6. qTorch, another tensor network contraction simulator [16]. Whereas the other simulators compute the entire state vector, qTorch only gives one measurement result at a time. Moreover, we observed no significant difference in performance across different measurement outcomes. Therefore, for qTorch simulating nn qubits, we run the experiment and multiply the run time by 2n2^n, which is the number of possible measurement outcomes in the computational basis (or, the length of the state vector). This choice is supported by the claim from the qTorch paper [16] itself: “To capture all the information of this final state of nn qubits, it generally requires O(2n)O(2^n) repetitions of the algorithm.”

We check that the results from all simulators match up to numerical precision.

We use each simulator to run the following experiments, which serve different purposes:

  1. Applying Hadamard to the last qubit. This is a simple circuit with a fixed number of operations.

  1. The Deutsch-Jozsa algorithm for nn qubits, with the oracle function that checks if a natural number is even,4 where the oracle is simplified to a C(X)C(X) on the last two qubits wrapped with two XX gates on the (n−1)(n-1)th qubit [32 Chapter 1]. In this experiment, the number of operations grows linearly with nn.

  1. The quantum part of Simon’s algorithm on nn qubits, with s=2n−1s = 2^n - 1, where the oracle is represented as a dense 2n×2n2^n \times2^n unitary matrix [32 Chapter 5]. This experiment uses dense matrices as part of the algorithm. For the two FGG-based simulators, we compile the oracle to an iso that enumerates all possible results. Because qsim does not support dense matrices larger than 26×262^6 \times2^6, we only run it up to 6 qubits. And because qTorch accepts a limited version of QASM that only supports 1- and 2-qubit gates, we exclude it from this experiment.

  1. Cn(X)C^n(X) with nn control qubits decomposed to 1- and 2-qubit gates [32 Chapter 4]. In this experiment, the circuit size grows superlinearly with nn. Because complex weights are required for larger nn, we cannot use PERPL to run this experiment, nor the next two.

  1. Quantum Fourier Transform on nn qubits [32 Chapter 5]. This quantum algorithm has repeated circuit structures.

  1. Grover’s algorithm on nn qubits with 2n2^n entries and 0 as the required entry, where all gates are decomposed to 1- and 2-qubit gates [32 Chapter 6]. This quantum algorithm also has repeated circuit structures.

  1. Bell state preparation of nn qubits [32 Chapter 1].

  1. A parallel composition of (1) and (7): for n+10n + 10 qubits, apply Hadamard to qubit nn and prepare a Bell state on qubits n+1n + 1 through n+10n + 10.

  1. Another parallel composition of (1) and (7): for 2n2n qubits, apply Hadamard to qubit nn and prepare a Bell state on qubits n+1n + 1 through 2n2n.

  1. A parallel composition of (1) and (2): for 2n2n qubits, apply Hadamard to qubit nn and the Deutsch-Jozsa algorithm to qubits n+1n + 1 through 2n2n.

We write the experiments in the same source language and compile them to ISO, Qiskit, Cirq, Quimb, and QASM programs while varying the number of qubits.

All experiments are performed on an Ubuntu 24.04 machine with a 2.50 GHz CPU of 48 cores and 503 GB of RAM. All simulators are configured to use at most 24 threads (50% of the core number) by their own settings. For each qubit number, we limit the run time to 5 minutes and memory to 452.7 GB (90% of the total memory). We increase the number of qubits for a simulator until timeout or reaching the memory limit. We configure the simulators as follows:

  • FGG solver: based on PyTorch 2.10.0.

  • Qiskit: Qiskit 1.1.1, Aer 0.17.2, StatevectorSimulator, and transpile optimization level 2.

  • Cirq: Cirq 1.6.1, qsim 0.22.0; the maximum number of qubits allowed per fused gate is 2 (max_fused_gate_size=2).

  • Quimb: Quimb 1.14.0, the auto-hq contraction path finding, the to_dense contraction method.

  • qTorch: v1.1-3-gd564ae6, the simple-stoch contraction method.

Benchmark Evaluation

Comparison among simulators

The run times of all simulators are shown in Figure 6 and Figure 7. Each plot shows one experiment and compares different simulators. For each plot, the xx-axis is the number of qubits, the left yy-axis is the run time in seconds (log scale), and the right yy-axis (used

Six-panel experiment results comparing FGG simulation with expand and $\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}$ opts, FGG simulation with expand and $\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}$ opts, through PERPL, Qiskit, Cirq, Quimb, and qTorch across Hadamard, Deutsch-Jozsa, Simon’s, decomposed $C^n(X)$, QFT, and Grover circuits

Figure 6. Experiment results, comparing all simulators. For each plot, the xx-axis shows the number of qubits, the left yy-axis shows run time in seconds, and the right yy-axis shows the number of gates.

Experiment results comparing all simulators, showing four plots for Bell state, Hadamard in parallel with 10-qubit Bell, Hadamard in parallel with $n$-qubit Bell, and Hadamard in parallel with Deutsch-Jozsa

Figure 7. Experiment results, comparing all simulators (continued). For each plot, the xx-axis shows the number of qubits, the left yy-axis shows run time in seconds, and the right yy-axis shows the number of gates. only by the dotted line) is the total number of gates (log scale). The run times shown for our two FGG-based simulators include both compiling from ISO and solving the resulting FGGs.

There is no single simulator that achieves the best performance across all experiments and sizes. Overall, our FGG-based simulators attain performance in the ballpark of the other simulators. For the single Hadamard gate (experiment (1)), both FGG implementations can simulate up to 40 qubits. For the Deutsch-Jozsa algorithm (experiment (2)), the FGG simulator is faster than qsim but slower than Qiskit and Quimb. For Simon’s algorithm (experiment (3)), Qiskit, Quimb, and the FGG implementations can simulate up to 8 qubits. For Cn(X)C^{n}(X) and Grover (experiments (4) and (6)), qsim achieves the best performance when the program size increases. For QFT and Bell state preparation (experiments (5) and (7)), Qiskit, qsim, and Quimb outperform FGG when the program size increases. For QFT, we also noticed that Qiskit introduces a global phase shift when the number of qubits exceeds 3.

Experiments (8) to (10) are parallel compositions of experiment (1), where our FGG-based simulators performed the best at high qubit counts, with experiments (2) and (7), where they did not. Parallel composition improved the standing of our FGG-based simulators relative to other simulators, so much so that our simulators outperform others at high qubit counts in experiments (8) and (10). The improvement is due to the fact that the FGG implementations can take advantage of the programs’ patterned sparsity and preserve it when the programs are composed in parallel.

Ablation of optimizations

To further study which components of our implementation contribute to the performance, we run the experiments with different optimizations and record the run times of the FGG solver and our compiler separately. We compile the same ISO source programs to FGGs directly. Then for each compilation result, we run the FGG solver with

  1. both the expand equation rewriting and sparsity detection enabled,

  2. the expand equation rewriting enabled and sparsity detection disabled,

(3) the expand equation rewriting disabled and sparsity detection enabled, and (4) no optimization enabled (but optimizations in the original FGG solver remain active).

This gives us four FGG solver run times and one compilation time. Four representative results are shown in Figure 8. The plots correspond to experiments (1), (2), (7), and (10) as shown in Figure 6 and Figure 7. The ablation experiments for the other benchmarks show similar patterns to these four plots. The compilation path through PERPL also shows similar results. For each plot, the xx-axis is the number of qubits, the left yy-axis is the run time in seconds (log scale), and the right yy-axis (used only by the dotted line) is the compilation time (log scale).

These experiments show that our optimizations are good at preserving sparsity under parallel composition. Experiments (1) and (2) show that both expand equation rewriting and sparsity detection can improve performance when the programs have the corresponding structure. The structure expand⁡(…einsum⁡…)\operatorname{expand}(\ldots\operatorname{einsum}\ldots) generated by comp helps the FGG solver rewrite expand expressions to smaller sizes. The inlining of single-variable let expressions in comp helps the FGG solver detect potentially sparse structures. For example, by substitution, let yy = Hadamard xx in let zz = Hadamard yy in zz is first converted to let zz = Hadamard (Hadamard xx) in zz, then it is compiled to an FGG tensor. Since two consecutive Hadamards are equivalent to identity, the sparsity detection can reduce it to a sparse tensor. Once such structures are recognized, tensor products of these sparse tensors can remain sparse. In the best case, a tensor of size 2n×2n2^n \times2^n can be represented by only 1 numerical element in memory, thus improving the overall memory usage and run times exponentially. Experiment (10) shows that the two optimizations together can make some programs outperform any single optimization. When programs don’t have the structure that the FGG solver recognizes, however, even if the final result is sparse, the solver might still need exponential time when the program size increases. In this case, neither optimization helps the performance, as shown in experiment (7).

Compilation becomes a significant bottleneck in experiments (3) to (6), and a sole bottleneck in experiment (3). This is unsurprising because encoding a dense 2n×2n2^n \times2^n unitary matrix is inherently exponential in nn. Our compilers need to traverse programs and generate a JSON file representing the FGGs, during which process they may print parts of a large program multiple times. In experiments (4) to (6), the significant compile time imposes one bottleneck, but another bottleneck is that the FGG solver runs out of memory.

Related Work

The design of quantum programming languages is an active research area [3, 13, 19, 34, 37, 41, 46]. As a representative, ISO models pure quantum programs with a linear type system and a syntax that follows pattern matching in functional programming. Other languages explore alternative design choices that can make quantum programming more accessible. It remains to be seen what is the best way to do high level quantum programming, design quantum control flow, and combine quantum programming with classical programming.

Various probabilistic graphical models have been proposed [24]. As described in § 4, FGGs are picked as a representative probabilistic graphical model. Other graphical models can also support our experiments if they satisfy our criteria.

Below we give a brief introduction to the interaction between probabilistic programming and quantum programming.

Generalizing classical probability models to quantum ones. Tucci [38] extends Bayesian networks to Quantum Bayesian networks, where probability amplitudes can be negative or complex. Yeang [44] defines a probabilistic graphical model for quantum systems. In this model, vertices are quantum states and edges are possible operations like unitary gates or measurements. Warmuth and Kuzmin [42] develop a probability calculus that generalizes the classical one to describe density matrices.

Inoue [22] takes the idea of negative probability from Feynman [15] and designs a universal quantum programming language with a two-layer probability model to support both classical probabilities and quantum amplitudes, which may be negative. These models study theoretical quantum generalizations of probabilistic models, but they address little about implementation, verification, or reuse of existing probabilistic infrastructures.

Extending quantum programming languages with probabilistic operations. Yuan [47] extends the quantum while-language designed by Ying [45] with a probabilistic operator observe and supports Bayesian inference for quantum programs. But they only give a prototype and don’t benchmark the performance or verify the language’s semantics. Gehnen et al. [17] make a similar extension and discuss the semantics of such a language through weakest precondition. But they don’t give an implementation.

Probabilistic simulation of quantum computation. Obeid et al. [33] simulate an EPR experiment using different probabilistic programming languages. This experiment demonstrates reuse of probabilistic programming infrastructure for EPR simulation, but does not address larger programs, performance, or formal semantics. Huang et al. [21] compile noisy quantum circuits into complex-valued Bayesian networks and use conjunctive normal form for optimization. They benchmark the performance of their simulator but don’t give a formal semantics or prove the correctness of the compilation. Machine learning models, such as Transformer [4, 27], are also used to encode quantum states and simulate quantum circuits, though their concern is less about the semantics and correctness.

Future Work

Our FGG solver supports auto-differentiation. It remains to be seen how to apply this feature to more quantum programs.

Our FGG solver already uses the PyTorch CPU parallelization. It remains to be seen if using PyTorch GPU parallelization can improve the performance.

PyTorch limits tensor ranks to a small number. For example, the operation torch.sum supports tensors up to rank 64 as of our test.5 If ISO’s typing context contains more variables than this limit, PyTorch simply rejects the compiled FGGs. Thus, the number of qubits that can be simulated is constrained by this limit. If we bypass this limit, we might be able to simulate more qubits.

In addition to symmetric pattern matching, ISO also supports higher-order isos and structural recursion on recursive data types like natural numbers and lists [36]. Probabilistic programming languages like PЕРPL [8] also support higher order functions, recursive data types, and recursive functions. PERPL uses defunctionalization and refunctionalization to eliminate recursive data types. Similar techniques should be applicable to higher-order and recursive isos.

Conclusion

We compile a high-level quantum language ISO to a probabilistic computation representation FGGs and simulate quantum programs using the existing FGG solver. We enhance the FGG solver to rewrite tensor expressions so as to perform eisum on smaller tensors. We prove that the compilation and the rewriting both preserve denotational semantics. We compare our implementations with other simulators on various quantum programs. The experiment results show that our approach achieves performance comparable to other quantum simulators, and the rewriting improves our simulation performance for quantum programs with repeated patterns. Our work establishes a connection between quantum programming and probabilistic programming, demonstrating benefits of reusing probabilistic programming techniques for quantum simulation.

Data-Availability Statement

We plan to submit an artifact. The artifact will include the following parts:

  1. The source code of our implementations, including the compilers and the FGG solver.

  2. The scripts to generate quantum programs and run the experiments.

  3. The performance data collected from running our experiments.

  4. Detailed instructions on how to reproduce our results.

References

Denotational Semantics of the Remaining ISO Constructs

The denotational semantics of ISO patterns, pure values, and extended values are shown in Fig. 9. We use ⟦_⟧p\llbracket\_ \rrbracket_p, ⟦_⟧v\llbracket\_ \rrbracket_v, and ⟦_⟧e\llbracket\_ \rrbracket_e for patterns, pure values, and extended values respectively. They follow the definitions in Eqs. (9) to (17), all denoting a function that takes an environment and a semantic value and returns a weight. For let p1=ω p2p_1 = \omega\ p_2 in ee, we iterate through the semantic values that p1p_1 and p2p_2 can take, and the environments corresponding to the typing context of p2p_2. Eq. (69) can be thought of as a combination of Eqs. (14) and (15).

Patterns

⟦∅⊢p():1⟧p(∅,())=1(58)\llbracket\varnothing\vdash_p () : 1 \rrbracket_p(\varnothing, ()) = 1 \tag*{(58)}
⟦x:a⊢px:a⟧p({(x,v′)},v)={1if v′=v0otherwise(59)\llbracket x : a \vdash_p x : a \rrbracket_p(\{(x,v')\},v) = \begin{cases} 1 & \text{if } v' = v \\ 0 & \text{otherwise} \end{cases} \tag*{(59)}
⟦Δ1;Δ2⊢p⟨p1,p2⟩:a⊗b⟧p(δ1∪δ2,⟨v1,v2⟩)=⟦Δ1⊢pp1:a⟧p(δ1,v1)⋅⟦Δ2⊢pp2:b⟧p(δ2,v2)(60)\llbracket\Delta_1;\Delta_2 \vdash_p \langle p_1,p_2\rangle: a \otimes b \rrbracket_p(\delta_1 \cup\delta_2,\langle v_1,v_2\rangle) = \llbracket\Delta_1 \vdash_p p_1 : a \rrbracket_p(\delta_1,v_1) \cdot\llbracket\Delta_2 \vdash_p p_2 : b \rrbracket_p(\delta_2,v_2) \tag*{(60)}

Pure Values

⟦∅⊢v():1⟧v(∅,())=1(61)\llbracket\varnothing\vdash_v () : 1 \rrbracket_v(\varnothing,()) = 1 \tag*{(61)}
⟦x:a⊢vx:a⟧v({(x,v′)},v)={1if v′=v0otherwise(62)\llbracket x : a \vdash_v x : a \rrbracket_v(\{(x,v')\},v) = \begin{cases} 1 & \text{if } v' = v \\ 0 & \text{otherwise} \end{cases} \tag*{(62)}
⟦Δ⊢vinj⁡lt:a⊕b⟧v(δ,inj⁡iv)={⟦Δ⊢vt:a⟧v(δ,v)if i=l0if i=r(63)\llbracket\Delta\vdash_v \operatorname{inj}_l t : a \oplus b \rrbracket_v(\delta,\operatorname{inj}_i v) = \begin{cases} \llbracket\Delta\vdash_v t : a \rrbracket_v(\delta,v) & \text{if } i = l \\ 0 & \text{if } i = r \end{cases} \tag*{(63)}
⟦Δ⊢vinj⁡rt:a⊕b⟧v(δ,inj⁡iv)={⟦Δ⊢vt:b⟧v(δ,v)if i=r0if i=l(64)\llbracket\Delta\vdash_v \operatorname{inj}_r t : a \oplus b \rrbracket_v(\delta,\operatorname{inj}_i v) = \begin{cases} \llbracket\Delta\vdash_v t : b \rrbracket_v(\delta,v) & \text{if } i = r \\ 0 & \text{if } i = l \end{cases} \tag*{(64)}
⟦Δ1;Δ2⊢v⟨v1,v2⟩:a⊗b⟧v(δ1∪δ2,⟨v1,v2⟩)=⟦Δ1⊢vv1:a⟧v(δ1,v1)⋅⟦Δ2⊢vv2:b⟧v(δ2,v2)(65)\llbracket\Delta_1;\Delta_2 \vdash_v \langle v_1,v_2\rangle: a \otimes b \rrbracket_v(\delta_1 \cup\delta_2,\langle v_1,v_2\rangle) = \llbracket\Delta_1 \vdash_v v_1 : a \rrbracket_v(\delta_1,v_1) \cdot\llbracket\Delta_2 \vdash_v v_2 : b \rrbracket_v(\delta_2,v_2) \tag*{(65)}

Extended Values

⟦Δ⊢ev:a⟧e(δ,v)=⟦Δ⊢vv:a⟧v(δ,v)(66)\llbracket\Delta\vdash_e v : a \rrbracket_e(\delta,v) = \llbracket\Delta\vdash_v v : a \rrbracket_v(\delta,v) \tag*{(66)}
⟦Δ⊢ee1+e2:a⟧e(δ,v)=⟦Δ⊢ee1:a⟧e(δ,v)+⟦Δ⊢ee2:a⟧e(δ,v)(67)\llbracket\Delta\vdash_e e_1 + e_2 : a \rrbracket_e(\delta,v) = \llbracket\Delta\vdash_e e_1 : a \rrbracket_e(\delta,v) + \llbracket\Delta\vdash_e e_2 : a \rrbracket_e(\delta,v) \tag*{(67)}
⟦Δ⊢eαe:a⟧e(δ,v)=α⋅⟦Δ⊢ee:a⟧e(δ,v)(68)\llbracket\Delta\vdash_e \alpha e : a \rrbracket_e(\delta,v) = \alpha\cdot\llbracket\Delta\vdash_e e : a \rrbracket_e(\delta,v) \tag*{(68)}
⟦Δ1;Δ2⊢elet⁡ p1=ω p2 in⁡ e:b⟧e(δ1∪δ2,v′)=∑δ2′∈⟦Δ2′⟧va∈⟦a⟧va′∈⟦a′⟧⟦Γi ω:a↔a′⟧(va,va′)⋅⟦Δ1⊢pp2:a⟧p(δ1,va)⋅⟦Δ2′⊢pp1:a′⟧p(δ2′,va′)⋅⟦Δ2;Δ2′⊢ee:b⟧e(δ2∪δ2′,v′)(69)\begin{aligned} \llbracket\Delta_1;\Delta_2 \vdash_e \operatorname{let}\ p_1 = \omega\ p_2\ \operatorname{in}\ e : b \rrbracket_e(\delta_1 \cup\delta_2,v') &= \sum_{\substack{\delta'_2 \in\llbracket\Delta'_2 \rrbracket\\ v_a \in\llbracket a \rrbracket\\ v'_a \in\llbracket a' \rrbracket}} \llbracket\Gamma_i\ \omega: a \leftrightarrow a' \rrbracket(v_a,v'_a) \cdot\llbracket\Delta_1 \vdash_p p_2 : a \rrbracket_p(\delta_1,v_a) \cdot\\ &\quad\llbracket\Delta'_2 \vdash_p p_1 : a' \rrbracket_p(\delta'_2,v'_a) \cdot\llbracket\Delta_2;\Delta'_2 \vdash_e e : b \rrbracket_e(\delta_2 \cup\delta'_2,v') \tag*{(69)} \end{aligned}

Fig. 9. The denotation of ISO patterns, pure values, and extended values

Compilation of the Remaining ISO Constructs

The compilers for ISO patterns, pure values, and extended values are shown in Figure 10. We first compile patterns, pure values, and extended values to terms with comp⁡pt(_)\operatorname{comp}^t_p(\_), comp⁡vt(_)\operatorname{comp}^t_v(\_), and comp⁡et(_)\operatorname{comp}^t_e(\_) respectively. Then we use comp⁡(_)\operatorname{comp}(\_) to compile the resulting terms to FGGs. Since patterns, pure values, and extended values are all subsets of terms, the translation from them to terms is straightforward. We can also prove the following lemma by induction on the typing judgments.

The compiler for ISO patterns, pure values, and extended values

Figure 10. The compiler for ISO patterns, pure values, and extended values

Lemma B.1. The compilation from ISO patterns, pure values, and extended values to ISO terms preserves types and semantics:

  • If Δ⊢pp:a\Delta\vdash_{\mathrm{p}} p : a, Δ⊢vv:a\Delta\vdash_{\mathrm{v}} v : a, and Δ⊢ee:a\Delta\vdash_{\mathrm{e}} e : a, then:

    Δ⊢tcomp⁡pt(p):a,Δ⊢tcomp⁡vt(v):a,Δ⊢tcomp⁡et(e):a\Delta\vdash_{\mathrm{t}} \operatorname{comp}_{\mathrm{p}}^{\mathrm{t}}(p) : a,\quad\Delta\vdash_{\mathrm{t}} \operatorname{comp}_{\mathrm{v}}^{\mathrm{t}}(v) : a,\quad\Delta\vdash_{\mathrm{t}} \operatorname{comp}_{\mathrm{e}}^{\mathrm{t}}(e) : a (70)

  • If Δ⊢pp:a\Delta\vdash_{\mathrm{p}} p : a, Δ⊢vv:a\Delta\vdash_{\mathrm{v}} v : a, and Δ⊢ee:a\Delta\vdash_{\mathrm{e}} e : a, then for any environment δ\delta of Δ\Delta and semantic value vv of aa:

    ⟦Δ⊢pp:a⟧p(δ,v)=⟦Δ⊢tcomp⁡pt(p):a⟧(δ,v)\llbracket\Delta\vdash_{\mathrm{p}} p : a \rrbracket_{\mathrm{p}}(\delta,v)=\llbracket\Delta\vdash_{\mathrm{t}} \operatorname{comp}_{\mathrm{p}}^{\mathrm{t}}(p) : a\rrbracket(\delta,v) (71)

    ⟦Δ⊢vv:a⟧v(δ,v)=⟦Δ⊢tcomp⁡vt(v):a⟧(δ,v)\llbracket\Delta\vdash_{\mathrm{v}} v : a \rrbracket_{\mathrm{v}}(\delta,v)=\llbracket\Delta\vdash_{\mathrm{t}} \operatorname{comp}_{\mathrm{v}}^{\mathrm{t}}(v) : a\rrbracket(\delta,v) (72)

    ⟦Δ⊢ee:a⟧e(δ,v)=⟦Δ⊢tcomp⁡et(e):a⟧(δ,v)\llbracket\Delta\vdash_{\mathrm{e}} e : a \rrbracket_{\mathrm{e}}(\delta,v)=\llbracket\Delta\vdash_{\mathrm{t}} \operatorname{comp}_{\mathrm{e}}^{\mathrm{t}}(e) : a\rrbracket(\delta,v) (73)

Proof of Theorem 5.1

Most cases in Theorem 5.1 can be proved by induction on the typing judgments. For let terms, we first prove the substitution lemma:

Lemma C.1. If Γ⊢tt1:a\Gamma\vdash_{\mathrm{t}} t_1 : a and Δ,x:a⊢tt2:b\Delta,x : a \vdash_{\mathrm{t}} t_2 : b, then Γ;Δ⊢tt2[t1/x]:b\Gamma;\Delta\vdash_{\mathrm{t}} t_2[t_1/x] : b.

This lemma can be proved by induction on Δ,x:a⊢tt2:b\Delta,x : a \vdash_{\mathrm{t}} t_2 : b. Then we can prove the denotational semantics of the substitution:

Lemma C.2. If Γ⊢tt1:a\Gamma\vdash_{\mathrm{t}} t_1 : a and Δ,x:a⊢tt2:b\Delta,x : a \vdash_{\mathrm{t}} t_2 : b, then for any environment δ\delta of Γ;Δ\Gamma;\Delta and semantic value vv of bb:

⟦Γ;Δ⊢tt2[t1/x]:b⟧(δ,v)=⟦Γ;Δ⊢tlet⁡ x=t1 in⁡ t2:b⟧(δ,v)\llbracket\Gamma;\Delta\vdash_{\mathrm{t}} t_2[t_1/x] : b\rrbracket(\delta,v)=\llbracket\Gamma;\Delta\vdash_{\mathrm{t}} \operatorname{let}\ x=t_1\ \operatorname{in}\ t_2 : b\rrbracket(\delta,v) (74)

This lemma can be proved by induction on Δ,x:a⊢tt2:b\Delta, x : a \vdash_{\mathrm{t}} t_2 : b. We pick the case t2=xt_2 = x below. Other cases can be proved in a similar way.

Proof. Let t2=xt_2 = x, then Δ=∅\Delta= \varnothing, t2[t1/x]=t1t_2[t_1/x] = t_1. Let δ\delta be an environment of Γ\Gamma, vv be a value of aa, we have

LHS=⟦t2[t1/x]⟧(δ,v)=⟦t1⟧(δ,v)(70)\mathrm{LHS} = \llbracket t_2[t_1/x] \rrbracket(\delta,v) = \llbracket t_1 \rrbracket(\delta,v) \tag*{(70)}
RHS=⟦let⁡ x=t1 in⁡ x⟧(δ,v)=∑δ2′∈⟦x:a⟧∑v′∈⟦a⟧⟦t1⟧(δ,v′)⋅⟦x⟧p(δ2′,v′)⋅⟦x⟧(δ2′,v)(71)\mathrm{RHS} = \llbracket\operatorname{let}\ x = t_1\ \operatorname{in}\ x \rrbracket(\delta,v) = \sum_{\delta'_2 \in\llbracket x:a \rrbracket} \sum_{v' \in\llbracket a \rrbracket} \llbracket t_1 \rrbracket(\delta,v') \cdot\llbracket x \rrbracket_{\mathrm{p}}(\delta'_2,v') \cdot\llbracket x \rrbracket(\delta'_2,v) \tag*{(71)}

Only when δ2′(x)=v\delta'_2(x) = v and v′=vv' = v, ⟦x⟧p(δ2′,v′)=1\llbracket x \rrbracket_{\mathrm{p}}(\delta'_2,v') = 1 and ⟦x⟧(δ2′,v)=1\llbracket x \rrbracket(\delta'_2,v) = 1. Therefore, LHS = RHS. □\square

Lemma C.3. The compiler comp⁡\operatorname{comp} on ISO terms terminates.

Proof. Let ρ\rho be a mapping from free variables in a term to N\mathbb{N}. For a variable xx not in ρ\rho, let ρ(x)=1\rho(x) = 1. Define the size of ISO terms as below:

∣ ⋅ ∣ρ:Term⁡iso→N∣()∣ρ=1∣x∣ρ=ρ(x)∣inj⁡l t∣ρ=∣t∣ρ+1∣inj⁡r t∣ρ=∣t∣ρ+1∣⟨t1,t2⟩∣ρ=∣t1∣ρ+∣t2∣ρ+1∣ω t∣ρ=∣t∣ρ+1∣let⁡ x=t1 in⁡ t2∣ρ=∣t1∣ρ+∣t2∣ρ∪{x↦∣t1∣ρ}+1∣t1+t2∣ρ=∣t1∣ρ+∣t2∣ρ+1∣let⁡ p=t1 in⁡ t2∣ρ=∣t1∣ρ+∣t2∣ρ+1∣αt∣ρ=∣t∣ρ+1\begin{aligned} |\,\cdot\,|_{\rho} &: \operatorname{Term}_{\mathrm{iso}} \to\mathbb{N}\\ |()|_{\rho} &= 1 & |x|_{\rho} &= \rho(x)\\ |\operatorname{inj}_{l}\ t|_{\rho} &= |t|_{\rho} + 1 & |\operatorname{inj}_{r}\ t|_{\rho} &= |t|_{\rho} + 1\\ |\langle t_1,t_2\rangle|_{\rho} &= |t_1|_{\rho} + |t_2|_{\rho} + 1 & |\omega\ t|_{\rho} &= |t|_{\rho} + 1\\ |\operatorname{let}\ x = t_1\ \operatorname{in}\ t_2|_{\rho} &= |t_1|_{\rho} + |t_2|_{\rho\cup\{x \mapsto|t_1|_{\rho}\}} + 1 & |t_1 + t_2|_{\rho} &= |t_1|_{\rho} + |t_2|_{\rho} + 1\\ |\operatorname{let}\ p = t_1\ \operatorname{in}\ t_2|_{\rho} &= |t_1|_{\rho} + |t_2|_{\rho} + 1 & |\alpha t|_{\rho} &= |t|_{\rho} + 1 \end{aligned}

It can be proved by induction that

∣t2[t1/x]∣ρ=∣t2∣ρ[x↦∣t1∣ρ]|t_2[t_1/x]|_{\rho} = |t_2|_{\rho[x \mapsto|t_1|_{\rho}]}

and

∣t2[t1/x]∣ρ<∣let⁡ x=t1 in⁡ t2∣ρ|t_2[t_1/x]|_{\rho} < |\operatorname{let}\ x = t_1\ \operatorname{in}\ t_2|_{\rho}

Since the recursive invocations of comp⁡\operatorname{comp} always operate on terms of smaller sizes, comp⁡\operatorname{comp} terminates. □\square

Lemma C.4. The compilation of substitution preserves semantics: If Γ⊢tt1:a\Gamma\vdash_{\mathrm{t}} t_1 : a and Δ,x:a⊢tt2:b\Delta, x : a \vdash_{\mathrm{t}} t_2 : b, then for any environment δ\delta of Γ;Δ\Gamma;\Delta and semantic value vv of bb:

⟦t2[t1/x]⟧(δ,v)=⟦comp⁡(t2[t1/x])⟧γ(comp⁡δ(Γ;Δ,δ),comp⁡v(b,v))(72)\llbracket t_2[t_1/x] \rrbracket(\delta,v) = \llbracket\operatorname{comp}(t_2[t_1/x]) \rrbracket_{\gamma}\bigl(\operatorname{comp}_{\delta}(\Gamma;\Delta,\delta),\operatorname{comp}_{v}(b,v)\bigr) \tag*{(72)}

This lemma can be proved by induction on Δ,x:a⊢tt2:b\Delta, x : a \vdash_{\mathrm{t}} t_2 : b.

With all the lemmas above, we can prove Theorem 5.1. We pick the case for the let terms. Other cases can be proved in a similar way.

Proof. For the let term, by Eq. (15), the left hand side has:

⟦Δ1;Δ2⊢tlet⁡ p=t1 in⁡ t2:b⟧(δ1∪δ2,v′)=∑δ2′∈⟦Δ2′⟧∑v∈⟦a⟧⟦t1⟧(δ1,v)⋅⟦p⟧(δ2′,v)⋅⟦t2⟧(δ2∪δ2′,v′)(73)\begin{aligned} \llbracket\Delta_1;\Delta_2 \vdash_{\mathrm{t}} \operatorname{let}\ p = t_1\ \operatorname{in}\ t_2 : b \rrbracket(\delta_1 \cup\delta_2,v') &= \sum_{\delta'_2 \in\llbracket\Delta'_2 \rrbracket} \sum_{v \in\llbracket a \rrbracket} \llbracket t_1 \rrbracket(\delta_1,v)\cdot\llbracket p \rrbracket(\delta'_2,v)\cdot\llbracket t_2 \rrbracket(\delta_2\cup\delta'_2,v') \tag*{(73)} \end{aligned}

By the definition of comp⁡\operatorname{comp} and Eq. (31), the right hand side has:

⟦comp⁡(Δ1;Δ2⊢tlet⁡ p=t1 in⁡ t2:b)⟧γ[(comp⁡δ(Δ1;Δ2,δ1∪δ2),comp⁡v(b,v′))]=⟦einsum⁡(comp⁡(t1)[comp⁡(Δ1)xa],comp⁡(p)[comp⁡(Δ2′)xa],comp⁡(t2)[comp⁡(Δ2)comp⁡(Δ2′)yb]→comp⁡(Δ1)comp⁡(Δ2)yb)⟧γ[(comp⁡δ(Δ1;Δ2,δ1∪δ2),comp⁡v(b,v′))](74)\begin{aligned} &\llbracket\operatorname{comp}(\Delta_1;\Delta_2 \vdash_{\mathrm{t}} \operatorname{let}\ p = t_1\ \operatorname{in}\ t_2 : b) \rrbracket_{\gamma}\bigl[(\operatorname{comp}_{\delta}(\Delta_1;\Delta_2,\delta_1\cup\delta_2),\operatorname{comp}_{v}(b,v'))\bigr]\\ &= \llbracket\operatorname{einsum}\bigl(\operatorname{comp}(t_1)[\operatorname{comp}(\Delta_1)x_a],\operatorname{comp}(p)[\operatorname{comp}(\Delta'_2)x_a],\\ &\qquad\operatorname{comp}(t_2)[\operatorname{comp}(\Delta_2)\operatorname{comp}(\Delta'_2)y_b]\to \operatorname{comp}(\Delta_1)\operatorname{comp}(\Delta_2)y_b\bigr)\rrbracket_{\gamma}\bigl[(\operatorname{comp}_{\delta}(\Delta_1;\Delta_2,\delta_1\cup\delta_2),\operatorname{comp}_{v}(b,v'))\bigr] \tag*{(74)} \end{aligned}
\begin{aligned} &= \sum_{\delta\in\operatorname{funs}(\operatorname{comp}(\Delta_1)x_a \cup\operatorname{comp}(\Delta'_2)x_a \cup\operatorname{comp}(\Delta_2)y_b)} \\ &\qquad\delta(\operatorname{comp}(\Delta_1)\operatorname{comp}(\Delta_2)y_b) = [(\operatorname{comp}_{\delta}(\Delta_1;\Delta_2,\delta_1\cup\delta_2),\operatorname{comp}_{v}(b,v'))] \\ &\qquad\left\llbracket\operatorname{comp}(t_1)\right\rrbracket_{\gamma}[\delta(\operatorname{comp}(\Delta_1)x_a)] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(p)\right\rrbracket_{\gamma}[\delta(\operatorname{comp}(\Delta'_2)x_a)] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(t_2)\right\rrbracket_{\gamma}[\delta(\operatorname{comp}(\Delta_2)\operatorname{comp}(\Delta'_2)y_b)] \tag*{(75)} \end{aligned}
\begin{aligned} &= \sum_{\delta\in\operatorname{funs}(\operatorname{comp}(\Delta'_2)x_a)} \left\llbracket\operatorname{comp}(t_1)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_1,\delta_1),\delta(x_a))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(p)\right\rrbracket_{\gamma}[(\delta(\operatorname{comp}(\Delta'_2)),\delta(x_a))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(t_2)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_2,\delta_2),\delta(\operatorname{comp}(\Delta'_2)),\operatorname{comp}_{v}(b,v'))] \tag*{(76)} \end{aligned}
\begin{aligned} &= \sum_{\delta' \in\operatorname{funs}(\operatorname{comp}(\Delta'_2))} \sum_{\delta'' \in\operatorname{funs}(x_a)} \left\llbracket\operatorname{comp}(t_1)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_1,\delta_1),\delta''(x_a))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(p)\right\rrbracket_{\gamma}[(\delta'(\operatorname{comp}(\Delta'_2)),\delta''(x_a))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(t_2)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_2,\delta_2),\delta'(\operatorname{comp}(\Delta'_2)),\operatorname{comp}_{v}(b,v'))] \tag*{(77)} \end{aligned}

To continue, we use the fact that there is a bijection between ⟦Δ2′⟧\llbracket\Delta'_2 \rrbracket and funs⁡(comp⁡(Δ2′))\operatorname{funs}(\operatorname{comp}(\Delta'_2)), namely, for every δ′∈⟦Δ2′⟧\delta' \in\llbracket\Delta'_2 \rrbracket we have {comp⁡(Δ2′)↦comp⁡δ(Δ2′,δ′)}∈funs⁡(comp⁡(Δ2′))\{\operatorname{comp}(\Delta'_2) \mapsto\operatorname{comp}_{\delta}(\Delta'_2,\delta')\} \in\operatorname{funs}(\operatorname{comp}(\Delta'_2)). Moreover, there is a bijection between ⟦a⟧\llbracket a \rrbracket and funs⁡(xa)\operatorname{funs}(x_a), namely, for every v∈⟦a⟧v \in\llbracket a \rrbracket we have {xa↦comp⁡v(a,v)}∈funs⁡(xa)\{x_a \mapsto\operatorname{comp}_{v}(a,v)\} \in\operatorname{funs}(x_a). Thus, Eq. (77) can be rewritten as:

\begin{aligned} &\sum_{\delta' \in\llbracket\Delta'_2 \rrbracket}\sum_{v \in\llbracket a \rrbracket} \left\llbracket\operatorname{comp}(t_1)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_1,\delta_1),\operatorname{comp}_{v}(a,v))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(p)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta'_2,\delta'),\operatorname{comp}_{v}(a,v))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(t_2)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_2,\delta_2),\operatorname{comp}_{\delta}(\Delta'_2,\delta'),\operatorname{comp}_{v}(b,v'))] \tag*{(78)} \end{aligned}
\begin{aligned} &= \sum_{\delta' \in\llbracket\Delta'_2 \rrbracket}\sum_{v \in\llbracket a \rrbracket} \left\llbracket\operatorname{comp}(t_1)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_1,\delta_1),\operatorname{comp}_{v}(a,v))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(p)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta'_2,\delta'),\operatorname{comp}_{v}(a,v))] \cdot\\ &\qquad\left\llbracket\operatorname{comp}(t_2)\right\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_2;\Delta'_2,\delta_2\cup\delta'),\operatorname{comp}_{v}(b,v'))] \tag*{(79)} \end{aligned}
\begin{aligned} &= \sum_{\delta' \in\llbracket\Delta'_2 \rrbracket}\sum_{v \in\llbracket a \rrbracket} \llbracket t_1\rrbracket(\delta_1,v) \cdot\llbracket p\rrbracket(\delta',v) \cdot\llbracket t_2\rrbracket(\delta_2\cup\delta',v') \end{aligned} \qquad\text{(by IH)} \tag*{(80)}\end{aligned}

Therefore,

⟦Δ1;Δ2⊢tlet⁡ p=t1 in⁡ t2:b⟧(δ1∪δ2,v′)=⟦comp⁡(Δ1;Δ2⊢tlet⁡ p=t1 in⁡ t2:b)⟧γ[(comp⁡δ(Δ1;Δ2,δ1∪δ2),comp⁡v(b,v′))](81)\begin{aligned} \llbracket\Delta_1;\Delta_2 \vdash_t \operatorname{let}\ p=t_1\ \operatorname{in}\ t_2:b\rrbracket(\delta_1\cup\delta_2,v') \\ = \llbracket\operatorname{comp}(\Delta_1;\Delta_2 \vdash_t \operatorname{let}\ p=t_1\ \operatorname{in}\ t_2:b)\rrbracket_{\gamma}[(\operatorname{comp}_{\delta}(\Delta_1;\Delta_2,\delta_1\cup\delta_2),\operatorname{comp}_{v}(b,v'))] \tag*{(81)} \end{aligned}

□

Proof of Theorem 6.1

Proof sketch. The denotation on the left hand side of (55) is a summation over indices of shape (x⃗y⃗z⃗)∖w⃗(\vec{x}\vec{y}\vec{z}) \setminus\vec{w}. This shape turns out to be the disjoint union of two shapes: v⃗\vec{v} consists of the dimensions that are not used to index any input tensor, and (x⃗∪y⃗)∖u⃗(\vec{x} \cup\vec{y}) \setminus\vec{u} consists of the dimensions that are used to index some input tensors. The main argument, then, is to split the summation into two nested summations. One of them ranges over indices of shape v⃗\vec{v}, and reduces to the constant factor ff because v⃗\vec{v} is unused.

Specifically, for any index tuple II such that {w⃗↦I}\{\vec{w} \mapsto I\}, using the conditions y⃗⊥z⃗\vec{y} \perp\vec{z} and w⃗⊑x⃗∪y⃗z⃗\vec{w} \sqsubseteq\vec{x} \cup\vec{y}\vec{z}, the two sides of (55) separately reduce to

\begin{aligned} \sum_{\delta' \in\operatorname{funs}(\vec{v})} \sum_{\delta\in\operatorname{funs}((\vec{x}\cup\vec{y})\setminus\vec{u})} &\left\llbracket F\right\rrbracket_{\gamma}[(\delta'\cup\delta\cup\{\vec{w}\mapsto I\})(\vec{x})] \\ &\cdot\left\llbracket E\right\rrbracket_{\gamma}[(\delta'\cup\delta\cup\{\vec{w}\mapsto I\})(\vec{y})] \end{aligned}
\begin{aligned} &= \left(\prod_{i\in\vec{v}} |i|\right) \cdot \sum_{\delta\in\operatorname{funs}((\vec{x}\cup\vec{y})\setminus\vec{u})} \left\llbracket F\right\rrbracket_{\gamma}[(\delta\cup\{\vec{w}\mapsto I\})(\vec{x})] \\ &\qquad\cdot\left\llbracket E\right\rrbracket_{\gamma}[(\delta\cup\{\vec{w}\mapsto I\})(\vec{y})] \tag*{(82)} \end{aligned}

Since v⃗\vec{v} doesn’t contain dimensions from x⃗\vec{x} or y⃗\vec{y}, we know v⃗\vec{v} is not used to index the denotations of FF and EE. Thus, the index function δ′\delta', whose domain is v⃗\vec{v}, is not used in the first summation in (82). Therefore, that summation reduces to the constant factor ∏i∈v⃗∣i∣\prod_{i\in\vec{v}}|i| on the right hand side. □

References

  1. [1]Jason Ansel, Edward Yang, Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesensky, Bin Bao, Peter Bell, David Berard, Evgeni Burovski, Geeta Chauhan, Anjali Chourdia, Will Constable, Alban Desmaison, Zachary DeVito, Elias Ellison, Will Feng, Jiong Gong, Michael Gschwind, Brian Hirsh, Sherlock Huang, Kshitee Kalamkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang, Yinghai Lu, CK Luk, Bert Maher, Yunjie Pan, Christian Puhlsch, Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk, Michael Suo, Phil Tillet, Eikan Wang, Xiaodong Wang, William Wen, Shunting Zhang, Xu Zhao, Keren Zhou, Richard Zou, Ajit Mathews, Gregory Chanan, Peng Wu, and Soumith Chintala. 2024. PyTorch 2: Faster Machine Learning through Dynamic Python Bytecode Transformation and Graph Compilation. In 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS ’24). ACM. doi:10.1145/3620665.3640366DOI
  2. [2]Nicola Assolini and Alessandra Di Pierro. 2025. A Denotational Semantics for Quantum Loops. arXiv:2506.23320 [cs] doi:10.48550/arXiv.2506.23320DOI
  3. [3]Benjamin Bichsel, Maximilian Baader, Timon Gehr, and Martin Vechev. 2020. Silq: A High-Level Quantum Language with Safe Uncomputation and Intuitive Semantics. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, London UK, 286–300. doi:10.1145/3385412.3386007DOI
  4. [4]Juan Carrasquilla, Di Luo, Felipe Pérez, Ashley Milsted, Bryan K. Clark, Maksims Volkovs, and Leandro Aolita. 2021. Probabilistic Simulation of Quantum Circuits Using a Deep-Learning Architecture. Physical Review A: Atomic, Molecular, and Optical Physics 104, 3 (Sept. 2021), 032610. doi:10.1103/PhysRevA.104.032610DOI
  5. [5]Kostia Chardonnnet. 2023. Towards a Curry-Howard Correspondence for Quantum Computation. Ph. D. Dissertation. Université Paris-Saclay.
  6. [6]Kostia Chardonnnet, Louis Lemonnier, and Benoît Valiron. 2023. Semantics for a Turing-complete Reversible Programming Language with Inductive Types. arXiv:2309.12151 [cs] doi:10.48550/arXiv.2309.12151
  7. [7]David Chiang, Darcey Masters, Grant Exley, Kenneth Sible, Yafei Yang, and Chung-chieh Shan. 2025. Factor Graph Grammars: Theory, Algorithms, and Implementation. (2025). Submitted to Journal of Machine Learning Research.
  8. [8]David Chiang, Colin McDonald, and Chung-chieh Shan. 2023. Exact Recursive Probabilistic Programming. Proceedings of the ACM on Programming Languages 7, OOPSLA1 (April 2023), 98:665–98:695. doi:10.1145/3586050DOI
  9. [9]David Chiang and Darcey Riley. 2020. Factor Graph Grammars. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 6648–6658.arxiv.org/abs/2010.12048
  10. [10]David Chiang, Alexander M Rush, and Boaz Barak. 2023. Named Tensor Notation. Transactions on Machine Learning Research (2023). https://openreview.net/forum?id=hVT7SHlix
  11. [11]Kenta Cho. 2014. Semantics for a Quantum Programming Language by Operator Algebras. Electronic Proceedings in Theoretical Computer Science 172 (Dec. 2014), 165–190. arXiv:1412.8545 [cs] doi:10.4204/EPTCS.172.12DOI
  12. [12]Alessio Cicero, Mohammad Ali Maleki, Muhammad Waqar Azhar, Anton Frisk Kockum, and Pedro Trancoso. 2025. Simulation of Quantum Computers: Review and Acceleration Opportunities. arXiv:2410.12660 [quant-ph] doi:10.48550/arXiv.2410.12660DOI
  13. [13]Kinnari Dave, Louis Lemonnier, Romain Péchoux, and Vladimir Zamdzhiev. 2025. Combining Quantum and Classical Control: Syntax, Semantics and Adequacy. In Foundations of Software Science and Computation Structures, Parosh Aziz Abdulla and Delia Kesner (Eds.). Springer Nature Switzerland, Cham, 155–175.DOI
  14. [14]Cirq Developers. 2025. Cirq. Zenodo. doi:10.5281/ZENODO.4064299
  15. [15]Richard P. Feynman. 1982. Simulating Physics with Computers. International Journal of Theoretical Physics 21, 6 (June 1982), 467–488. doi:10.1007/BF02650179DOI
  16. [16]E. Schuyler Fried, Nicolas P. D. Saway, Yudong Cao, Ian D. Kivlichan, Jhonathan Romero, and Alán Aspuru-Guzik. 2018. qTorch: The Quantum Tensor Contraction Handler. PLOS ONE 13, 12 (Dec. 2018), e0208510. arXiv:1709.03636 [quant-ph] doi:10.1371/journal.pone.0208510DOI
  17. [17]Christina Gehnen, Dominique Unruh, and Joost-Pieter Katoen. 2025. Bayesian Inference in Quantum Programs. arXiv:2504.20732 [cs.LO] https://arxiv.org/abs/2504.20732
  18. [18]Johnnie Gray. 2018. Quimb: A Python Package for Quantum Information and Many-Body Calculations. Journal of Open Source Software 3, 29 (Sept. 2018), 819. doi:10.21105/joss.00819DOI
  19. [19]Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoît Valiron. 2013. Quipper: A Scalable Quantum Programming Language. ACM SIGPLAN Notices 48, 6 (June 2013), 333–342. arXiv:1304.3390 [quant-ph] doi:10.1145/2499370.2462177DOI
  20. [20]Charles R. Harris, K. Jarrod Millman, Stéphán J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwiijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020. Array Programming with NumPy. Nature 585, 7825 (Sept. 2020), 357–362. doi:10.1038/s41586-020-2649-2DOI
  21. [21]Yipeng Huang, Steven Holtzen, Todd Millstein, Guy Van Den Broeck, and Margaret Martonosi. 2021. Logical Abstractions for Noisy Variational Quantum Algorithm Simulation. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, Virtual USA, 456–472. doi:10.1145/3445814.3446750DOI
  22. [22]Jun Inoue. 2024. Quantum Programming Without the Quantum Physics. In Proceedings of APLAS 2024: 22nd Asian Symposium on Programming Languages and Systems, Oleg Kiselyov (Ed.). Springer, 155–175.DOI
  23. [23]Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. 2024. Quantum Computing with Qiskit. arXiv:2405.08810 [quant-ph] doi:10.48550/arXiv.2405.08810
  24. [24]Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA, USA.
  25. [25]Daphne Koller, David Allen McAllester, and Avi Pfeffer. 1997. Effective Bayesian Inference for Stochastic Programs. In AAAI-97: Proceedings of the 14th National Conference on Artificial Intelligence. 740–747.
  26. [26]F.R. Kschischang, B.J. Frey, and H.-A. Loeliger. 2001. Factor Graphs and the Sum-Product Algorithm. IEEE Transactions on Information Theory 47, 2 (2001), 498–519. doi:10.1109/18.910572DOI
  27. [27]Hannah Lange, Guillaume Bornet, Gabriel Emperauger, Cheng Chen, Thierry Lahayе, Stefan Kienle, Antoine Browaeys, and Annabelle Bohrdt. 2025. Transformer Neural Networks and Quantum Simulators: A Hybrid Approach for Simulating Strongly Correlated Systems. Quantum 9 (March 2025), 1675. doi:10.22331/q-2025-03-26-1675DOI
  28. [28]Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathan Shlens, Benoit Steiner, llya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2015. TensorFlow: Large-scale Machine Learning on Heterogeneous Systems.arxiv.org/abs/1603.04467
  29. [29]John McCarthy. 1961. A Basis for a Mathematical Theory of Computation, Preliminary Report. In Papers Presented at the 1961 Western Joint IRE-AIEE-ACM Computer Conference, IRE-AIEE-ACM 1961 (Western), Los Angeles, California, USA, May 9–11, 1961, Walter F. Bauer (Ed.). ACM, 225–238. doi:10.1145/146090.1460715DOI
  30. [30]Cameron Moy, Jack Czenszak, John M. Li, Brianna Marshall, and Steven Holtzen. 2025. Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic Programming. Proceedings of the ACM on Programming Languages 9, PLDI (2025), 2081–2105. doi:10.1145/3729334DOI
  31. [31]Shin-Cheng Mu and Richard S. Bird. 2001. Functional Quantum Programming. In The Second Asian Workshop on Programming Languages and Systems, APLAS’01, Korea Advanced Institute of Science and Technology, Daejeon, Korea, December 17–18, 2001, Proceedings. Korea advanced institute of science and technology, Daejeon, Korea, 75–88.
  32. [32]Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information. Cambridge university press, Cambridge.
  33. [33]Abdul Obeid, Peter D. Bruza, and Peter Wittek. 2019. Evaluating Probabilistic Programming Languages for Simulating Quantum Correlations. PLOS ONE 14, 1 (Jan. 2019), e0208555. arXiv:1811.04424 [quant-ph] doi:10.1371/journal.pone.0208555DOI
  34. [34]Jennifer Paykin, Robert Rand, and Steve Zdancewic. 2017. QWIRE: A Core Language for Quantum Circuits. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. ACM, Paris France, 846–858. doi:10.1145/3009837.3009894DOI
  35. [35]Hoifung Poon and Pedro M. Domingos. 2011. Sum-Product Networks: A New Deep Architecture. In Proceedings of UAI 2011: 27th Conference on Uncertainty in Artificial Intelligence, Fábio Gagliardi Cozman and Avi Pfeffer (Eds.). AUAI Press, 337–346.arxiv.org/abs/1202.3732
  36. [36]Amr Sabry, Benoît Valiron, and Juliana Kaizer Vizzotto. 2018. From Symmetric Pattern-Matching to Quantum Control. In Proceedings of FoSSaCS 2018: Foundations of Software Science and Computational Structures, 21st International Conference (Lecture Notes in Computer Science, 10803), Christel Baier and Ugo Dal Lago (Eds.). Springer, 348–364.DOI
  37. [37]Peter Selinger. 2004. Towards a Quantum Programming Language. Mathematical Structures in Computer Science 14, 4 (Aug. 2004), 527–586. doi:10.1017/S0960129504004256DOI
  38. [38]Robert R. Tucci. 1995. Quantum Bayesian Nets. International Journal of Modern Physics B 09, 03 (Jan. 1995), 295–337. arXiv:quant-ph/9706039 doi:10.1142/S0217979295000148DOI
  39. [39]Benoît Valiron. 2022. Semantics of Quantum Programming Languages: Classical Control, Quantum Control. Journal of Logical and Algebraic Methods in Programming 128 (2022), 100790. doi:10.1016/j.jlamp.2022.100790DOI
  40. [40]Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, and Frank Wood. 2018. An Introduction to Probabilistic Programming. e-Print 1809.10756. arXiv. https://arxiv.org/abs/1809.10756
  41. [41]Finn Voichick, Liyi Li, Robert Rand, and Michael Hicks. 2023. Qunity: A Unified Language for Quantum and Classical Computing (Extended Version). Proceedings of the ACM on Programming Languages 7, POPL (Jan. 2023), 921–951. arXiv:2204.12384 [cs] doi:10.1145/3571225DOI
  42. [42]Manfred K. Warmuth and Dima Kuzmin. 2014. A Bayesian Probability Calculus for Density Matrices. arXiv:1408.3100 [quant-ph] doi:10.48550/arXiv.1408.3100DOI
  43. [43]Maurice Wenig, Paul G. Rump, Mark Blacher, and Joachim Giesen. 2025. The Syntax and Semantics of Einsum. arXiv:2509.20020 [cs] doi:10.48550/arXiv.2509.20020DOI
  44. [44]Chen-Hsiang Yang. 2010. A Probabilistic Graphical Model of Quantum Systems. In 2010 Ninth International Conference on Machine Learning and Applications. 155–162. doi:10.1109/ICMLA.2010.30
  45. [45]Mingsheng Ying. 2012. Floyd–Hoare Logic for Quantum Programs. ACM Trans. Program. Lang. Syst. 33, 6, Article 19 (Jan. 2012). doi:10.1145/2049706.2049708DOI
  46. [46]Mingsheng Ying, Nengkun Yu, and Yuan Feng. 2012. Defining Quantum Control Flow. arXiv:1209.4379 [quant-ph] doi:10.48550/arXiv.1209.4379DOI
  47. [47]Charles Yuan. 2021. Probabilistic Inference for Quantum Programs. In I2Q.

Paper details

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

views · 9

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents