betaFeedback

WorksPhysics and Astronomy

Constrained Adiabatic Quantum Programming

Abstract

To find a kk-clique in a graph, adiabatic quantum computation (AQC) evolves a quantum system from the minimum of an initial cost function to the minimum of a problem cost function that penalizes non-cliques. Existing AQC languages fix the initial cost function, so the search ranges over all 2n2^n subsets of the nn vertices, although only the subsets of size kk can be answers. We present ENQ+, an AQC language in which the programmer writes both cost functions. Data constraints define the problem cost function. Relational constraints, a new construct, declare the moves the search may make between configurations and define the initial cost function. For the clique, a single relational constraint, which exchanges a chosen vertex with an unchosen one, confines the search to the subsets of size kk. ENQ+ thereby turns constrained quantum annealing, which physicists set up by hand for individual problems, into a programming construct. We give ENQ+ a semantics in many-world configuration (MWC) graphs, whose nodes are configurations and whose edges are moves, and derive from it a step-wise semantics of adiabatic evolution. We prove that a run stays within the component of the MWC graph that contains its initial state, and that a run from an approximate initial state still reaches the answer, with probability equal to its squared overlap with the exact one. We compile ENQ+ to quantum circuits, prove the compilation correct with respect to the semantics, and use ENQ+ to program the Three-Dimensional Matching, Hamiltonian Cycle, and Traveling Salesperson problems.

Introduction

Quantum computers aim to solve highly complex problems by leveraging quantum superposition, which enables substantially faster algorithms, such as Shor’s algorithm, than classical algorithms. A key issue in quantum computation is a high-level program abstraction, beyond the current digital circuit based model. Adiabatic quantum computation (AQC) is a model for optimization problems [29] and has been proven equivalent to the digital circuit model [4]. We intend to develop a high-level programming paradigm, EnQ+^{+}, based on AQC by connecting it with classical constraint programming.

An AQC problem is presented as a cost function over candidate solutions whose minimum is the answer; physically, this cost function is a Hamiltonian and its minimum a ground state, but we use the programming terminology throughout. The minimum cannot be prepared directly, since that is the problem itself, so AQC reaches it through a pair of cost functions. It initializes the system at the minimum of an initial cost function H^i\hat{H}_i, one whose minimum is easy to prepare, and then deforms the cost function slowly along (1−t)H^i+tH^f(1-t)\hat{H}_i + t\hat{H}_f into the problem cost function H^f\hat{H}_f, whose minimum is the answer. The adiabatic theorem guarantees that, deformed slowly enough, the system stays at the minimum the whole way and hence ends at the minimum of H^f\hat{H}_f. How slow “slowly enough” must be is governed by the spectral gap, the energy separating the minimum from the next configuration during the deformation; the smaller the gap, the longer the run.

A Motivation Example: Clique Finding

To see what is at stake, consider the standard Hamiltonian encoding of the kk-clique graph problem [59]. It puts a binary variable xv∈{0,1}x_v \in\{0,1\} on every vertex of a graph G=(V,E)G = (V,E), so a configuration is a 0/1 labeling of all vertices; its cost is computed by the formula

(k−∑v∈Vxv)2+(k(k−1)2−∑(u,v)∈Exuxv)2\left(k-\sum_{v\in V}x_v\right)^2+\left(\frac{k(k-1)}{2}-\sum_{(u,v)\in E}x_ux_v\right)^2

Authors’ Contact Information: Liyi Li, [email protected]; Mahir Anand, [email protected], Iowa State University, USA; James Bryan Graves, [email protected]; Amr Sabry, [email protected], Indiana University, USA. The first term grows as the number of 1s departs from kk; the second grows as the 1-valued vertices miss the k(k−1)2\frac{k(k-1)}{2} edges of a clique. The cost is zero exactly on a kk-clique. The search ranges over configurations with every number of 1s, which is clearly inefficient. Furthermore, a clique with the wrong count is penalized but not ruled out, so the run can still settle into a near-miss, such as a (k−1)(k-1)-clique.

The AQC model has several issues. First, the energy constraints above focus too much on developing a matrix form and include many compilation details. Essentially, the (k(k−1)2−∑(u,v)∈Exuxv)2\left(\frac{k(k-1)}{2}-\sum_{(u,v)\in E}x_u x_v\right)^2 simply suggests that one needs to look at every pair of configuration nodes in GG and examine if there is an edge connecting them; the sum and square operations exist because they are required by the compilation. Second, the above expression defines only the HfH_f part, while the initial Hamiltonian (HiH_i) is not clearly explained. The initial state ∣φ⟩\lvert\varphi\rangle is required to be an eigenstate of the initial Hamiltonian HiH_i, but the model provides no additional information on how users can understand and program HiH_i. Third, a more essential issue is the interpretability of the relationship between the elements in the Hamiltonians and the elements in the initial quantum state. For example, the binary variables xvx_v can indeed be thought of as qubits in the quantum state, but it is unclear what happens if users want more than binary variables, what it might affect the quantum state to put two items xuxvx_u x_v together, and what the hidden constraints are for the relations.

Our first contribution is developing an interpretation of the AQC model based on a data structure rather than a pure quantum state. We develop a many-world configuration graph for interpreting the quantum states used in the model. Figure 1 shows an example many-world configuration (MWC) graph for a Dicke state used in the clique-finding problem. Assuming the data-structure graph in clique finding has four data-point vertices, with each data-point containing a field indicating its subgraph inclusion; e.g., blue vertices are included in the subgraph when considering a clique.

Figure 1. Example many-world configuration graph for the state 16(∣1100⟩+∣1010⟩+∣1001⟩+∣0011⟩+∣0101⟩+∣0110⟩)\frac{1}{\sqrt{6}}(\lvert1100\rangle+\lvert1010\rangle+\lvert1001\rangle+\lvert0011\rangle+\lvert0101\rangle+\lvert0110\rangle); z=16z=\frac{1}{\sqrt{6}}. Two configurations are connected with a gray line only if they are exactly different by two data points.

The MWC graph can be viewed as a high-level abstraction of a quantum state ∣φ⟩\lvert\varphi\rangle, where we map each basis-ket state in ∣φ⟩\lvert\varphi\rangle to a configuration in the graph and each data-point vertex is a bit in the basis-ket, e.g., the left configuration represents 16∣1100⟩\frac{1}{\sqrt{6}}\lvert1100\rangle, so we mark the blue vertices for the aa and bb positions.

MWC graphs support AQC constraints: initial Hamiltonians (HiH_i) define the relational constraint relating edges in the MWC graph, and final Hamiltonians (HfH_f) define the data constraint within a configuration. In the clique finding example, a data constraint is defined for every data-point pair in a configuration, e.g., for every data-point pair ((aa, bb), (aa, cc), (aa, dd), (bb, cc), (bb, dd), (cc, dd)), we give an energy penalty if the pair is included in the subgraph and there is no edge between them; e.g., there is an energy penalty for (bb, dd) at the configuration ∣0101⟩\lvert0101\rangle.

Relational constraints are defined among MWC graph edges connecting two configurations. A valid edge depends on the specific relational constraint being defined. In clique finding, we look at data-point pairs; thus, an edge connects two configurations that differ in exactly two data points, e.g., in the edge connecting the ∣1100⟩\lvert1100\rangle and ∣0110⟩\lvert0110\rangle configurations, the aa and cc data points differ. In EnQ+\mathrm{EnQ}^{+}, we can constrain this relation by swapping the choice values between the two data points in the two configurations.

As mentioned above, a typical requirement is that the program’s initial state is the ground eigenstate of the relational constraint (initial Hamiltonian), but many initial states are hard to prepare. A key EnQ+\mathrm{EnQ}^{+} contribution examines the case where we have an ideal relational constraint but an easy-to-prepare initial state that is not the relational constraint eigenstate, detailed in Theorem 3.10.

Another major contribution is a certified compiler that relies on developing a dynamic semantics for AQC, with a theorem that shows the final outcome, though it omits many details in the step-wise transition semantics. With the added probabilistic feature and without dynamic semantics, users who compile an AQC problem to quantum computers may struggle to tell whether the issue is a compilation problem or simply that they need to wait a long time. Even if a good outcome is produced eventually, it is hard to evaluate the compilation’s effectiveness. EnQ+\mathrm{EnQ}^{+} develops the first dynamic semantics for AQC based on a widely used setting [16, 21, 26, 33, 39, 41, 56, 64] and uses the semantics to certify our AQC compilation from EnQ+\mathrm{EnQ}^{+} programs to quantum computers. Using the certified compiler, we uncover a long-standing issue in Hamiltonian-simulation-based AQC compilation.

Contributions and Roadmap

EnQ+\mathrm{EnQ}^{+} is based on AQC and builds on prior work. The detailed AQC background and the difference between EnQ+\mathrm{EnQ}^{+} and previous works in physics are given in Section B. We identify the following contributions.

  • We develop the MWC graph as an interpretation of quantum states as high-level data structures, serving as the state representation for EnQ+\mathrm{EnQ}^{+}; details are in § 3.1.

  • We extend EnQ\mathrm{EnQ} [56] with additional relational constraints, permitting users to constrain the initial starting points when solving a problem, detailed in § 3.2.

  • We define the formal constraint semantics and derive the dynamic transition semantics for EnQ+\mathrm{EnQ}^{+} programs. To the best of our knowledge, this is the first step-wise transition semantics for AQC for the specific EnQ+\mathrm{EnQ}^{+} setting, detailed in § 3.3.

  • Using the formal semantics, we prove a good approximation theorem, examining the situation where the initial state is not the eigenstate of a relational constraint, detailed in § 3.3.

  • Using the type system § 3.2, we develop a certified compiler that compiles EnQ+\mathrm{EnQ}^{+} programs to quantum computers and uncover an issue in the previous AQC compilation (§ 4.4).

Overview through a Worked Example: Finding a 3-Clique

This section provides an EnQ+^{+} overview based on an example of finding a 3-clique in the five-vertex graph of Figure 2, whose edges are abab, bcbc, cdcd, dede, eaea, and the chord acac. The graph has exactly one triangle, {a,b,c}\{a,b,c\}.

Figure 2. Our graph. Its only triangle, {a,b,c}\{a,b,c\}, is shaded.

Background. Adiabatic Quantum Computation (AQC) is a model of quantum computation that solves optimization problems by evolving a quantum system, defined by a Hamiltonian H^(t)=(1−t)H^i+tH^f\hat{H}(t)=(1-t)\hat{H}_{i}+t\hat{H}_{f}, slowly from an initial Hamiltonian H^i\hat{H}_{i} with a known ground state to a final Hamiltonian H^f\hat{H}_{f} whose ground state encodes the solution. The evolution adjusts tt slowly every step from 0 to 1. By maintaining the system in its lowest energy state throughout the process, AQC leverages the adiabatic theorem to find optimal solutions efficiently. The first line below shows the Hamiltonian HH that varies with time tt from HiH_i to HfH_f. The exact evolution of this Hamiltonian would be given by the Schrödinger equation on the right. A typical way of approximating the AQC solution uses Hamiltonian simulation consisting of the sequence on the second line, where each step generates a quantum operation via a matrix exponential operation (exp⁡(−iH^(t)Δt))(\exp(-i\hat{H}(t)\Delta t)) for a small time period Δt\Delta t. Note that a Hamiltonian is a Hermitian matrix (Hermitian H=H†H=H^{\dagger}) and that Hamiltonian simulation (exp⁡(−iH^t))(\exp(-i\hat{H}t)) generates a unitary matrix that can be implemented as a quantum circuit. Therefore, the AQC procedure can be understood as starting with an initial quantum state ∣φ(0)⟩\lvert\varphi(0)\rangle and applying a sequence of unitary quantum operations, each of which is of the form exp⁡(−iH^(t)Δt)\exp(-i\hat{H}(t)\Delta t) for a different t∈{Δt,2Δt,3Δt,…,T}t\in\{\Delta t,2\Delta t,3\Delta t,\ldots,T\}.

H^(t)=(1−tT)H^i+tTH^fiddt∣φ(t)⟩=H^(t)∣φ(t)⟩∣φ(T)⟩≈exp⁡(−iH^(T)Δt)…exp⁡(−iH^(2Δt)Δt)exp⁡(−iH^(Δt)Δt)∣φ(0)⟩\begin{aligned} \hat{H}(t)&=\left(1-\frac{t}{T}\right)\hat{H}_{i}+\frac{t}{T}\hat{H}_{f} \\ i\frac{d}{dt}\lvert\varphi(t)\rangle&=\hat{H}(t)\lvert\varphi(t)\rangle\\ \lvert\varphi(T)\rangle&\approx\exp(-i\hat{H}(T)\Delta t)\ldots\exp(-i\hat{H}(2\Delta t)\Delta t)\exp(-i\hat{H}(\Delta t)\Delta t)\lvert\varphi(0)\rangle \end{aligned}

Understand Constraints based on MWC Graphs. We first show the EnQ+^{+} interpretation of data constraints on the MWC graphs, corresponding to the final Hamiltonian (H^f\hat{H}_{f}) in an AQC pair. Figure 3 is an example MWC graph for the clique-finding problem in Figure 2, based on an initial-and-data-constraint setting; discussed shortly below. In clique finding, each vertex has a binary choice value, denoted xv∈{Yes,No}x_v\in\{\mathrm{Yes},\mathrm{No}\}, where Yes means the vertex is included in the clique. A configuration is one such labeling of all five vertices, and there can be 25=322^5=32 of them. For example, Table 1 marks the vertices aa, bb, and cc to be Yes, and the others to be No. In EnQ+^{+}, we define the data constraint to be as follows.

candidateH^f\hat{H}_fcandidateH^f\hat{H}_f
{a,b,c}\{a,b,c\}0{a,d,e}\{a,d,e\}1
{a,b,d}\{a,b,d\}2{b,c,d}\{b,c,d\}1
{a,b,e}\{a,b,e\}1{b,c,e}\{b,c,e\}2
{a,c,d}\{a,c,d\}1{b,d,e}\{b,d,e\}2
{a,c,e}\{a,c,e\}1{c,d,e}\{c,d,e\}1

Table 1. The ten three-vertex candidates and their cost H^f=xaxd+xbxd+xbxe+xcxe\hat{H}_f = x_a x_d + x_b x_d + x_b x_e + x_c x_e. Only {a,b,c}\{a,b,c\} costs 0.

Figure 3. The many-world configuration graph: the ten candidates, joined wherever a single swap turns one into another. Green is the clique (H^f=0\hat{H}_f = 0), blue costs 1, red costs 2.

∂x∂y if ¬edge⁡(x,y)∧Yes⁡(y)∧Yes⁡(x) then 10 else 0\partial_x\partial_y\text{ if }\neg\operatorname{edge}(x,y)\land\operatorname{Yes}(y)\land\operatorname{Yes}(x)\text{ then }10\text{ else }0

Given two vertices, xx and yy, in a graph, if they are considered in the subgraph (Yes⁡(y)∧Yes⁡(x))(\operatorname{Yes}(y)\land\operatorname{Yes}(x)) and there is no edge between them, we assign an energy loss to them; otherwise, the loss is 0, e.g., Table 1; only {a,b,c}\{a,b,c\} is minimal; the others each pay for one or two of the missing edges they contain. We apply the constraint to every vertex pair in the graph and sum the energy scores. If we find a configuration φ\varphi with score 0, the Yes vertices in φ\varphi form a clique. As in the example above, a data constraint on a MWC graph examines the relations among data points inside a configuration node.

One issue is setting the energy scores. For example, the energy scores for the above data constraint can be set to different values; such differences might affect the evolution time but not the final result. When dealing with an AQC problem, users might not know the exact energy scores to set but can identify a direction to set the energy scores, because setting the exact energy scores depends on many factors, such as compilation and quantum hardware. For example, in the above example, it might be more precise to do the following.

v≔L∣O ∂x. ∂y. if ¬edge⁡(x,y)∧Yes⁡(y)∧Yes⁡(x) then L else Ov \coloneqq L \mid O\ \partial x.\ \partial y.\ \text{if }\neg\operatorname{edge}(x,y) \land\operatorname{Yes}(y) \land\operatorname{Yes}(x)\text{ then }L\text{ else }O

Here, we set the energy loss to L, meaning there is some energy loss, but we leave the exact values to the compiler. Similarly, O means a lowest energy state, not necessarily to be 0. In EnQ+^{+}, we use an abstract data type and allow both exact and relative energy scores. When compiling the former, we encode exact energy values; for the latter, we use an optimal energy-score calculation.

A MWC graph is essentially a reinterpretation of a quantum state, serving as the data domain to which the EnQ+^{+} constraints apply. In a many-worlds interpretation, a quantum state can be viewed as a set of possible "events", which is expressed as a linear sum of basis-kets; i.e., the basis-vector of a basis-ket is a possible world, and its amplitude represents the probability of the world happening. MWC follows the many-worlds interpretation, where each basis-ket is a possible configuration, and the whole quantum state is the collection of all possible configurations.

Developing Relational Constraints. Beyond data constraints, we develop relational constraints based on MWC graph edges that connect data points across configurations. The clique-finding example in Figure 2 can have 32 different configurations, while the MWC graph in Figure 3 has 10 valid configurations, because we develop the following relational constraint to trim unqualified configurations.

∂x. ∂y. {x,y}∼∗(1)\partial x.\ \partial y.\ \{x,y\}\sim^{*} \tag*{(1)}

Here, we examine pairs of configurations, connected by edges (ϕ1,ϕ2)(\phi_1,\phi_2). The bindings xx and yy indicate that the constraint applies to two data points in (ϕ1,ϕ2)(\phi_1,\phi_2), e.g., in the configurations {a,c,d}\{a,c,d\} and {a,c,e}\{a,c,e\} of Figure 3, we examine the two data points dd and ee and relate the choices in the two data points. The ∗* flag suggests that the symmetry relation is a swap, i.e., the choice in a data-point (dd or ee) is swapped from one configuration (ϕ1\phi_1) to the other (ϕ2\phi_2). In the MWC graph, two configurations are connected by an edge only if exactly one pair of data points satisfies the relational constraint, while the other data points remain the same across the configuration pair. The swap constraint ensures that 1) only two data-points in a configuration pair admit a choice swap relation, and 2) the other data-points remain the same. Thus, the number of Yes choices is the same across different configurations. The MWC graph Figure 3 is initialized as each configuration having exactly 3 choices; thus, it contains (53)=10\binom{5}{3}=10 configurations. These ten configurations are the entire search space and are formalized using the many-world configuration (MWC) graph of Figure 3: a node for each candidate, and an edge wherever a single swap turns one into another.

The above relational constraint defines the swapping relation, but other kinds of relational constraints may exist. For example,

∂x. ∂y. ∂z. {x,y,z}∼∗\partial x.\ \partial y.\ \partial z.\ \{x,y,z\}\sim^{*}

defines a relational constraint describing a swap among three vertices in a configuration pair.

Another constraint is {x,y}∼0\{x,y\}\sim^{0}, which defines a relation that moves in the same direction in a configuration pair. Consider a Bell pair 12(∣00⟩+∣11⟩)\frac{1}{\sqrt{2}}(|00\rangle+ |11\rangle), which can be thought of as two qubits measuring into the same bits. Viewing a Bell pair in EnQ+\mathrm{EnQ}^{+} can be thought of as a relational constraint that two qubits move in the same direction, i.e., the basis-vector set contains {∣00⟩,∣11⟩}\{|00\rangle, |11\rangle\}, where the two sites are always moving in the same direction, as ∣00⟩↔∣11⟩|00\rangle\leftrightarrow|11\rangle. An example of using such a constraint is in § 5.

One question is left: where does the search begin? We permit users to define an initial state, interpreted as a MWC graph, as the starting point, so we start somewhere easy and well defined and let the evolution carry us the rest of the way. In the above example, the natural choice treats all ten candidates alike: the uniform superposition over them, known as the Dicke state; it minimizes precisely the relational constraint we wrote, so the programmer gets a sound starting point for free.

The issue is that an arbitrary initial state might be hard to prepare; for example, a quantum superposition of all permutations might be hard to prepare. We want to examine the possibility that an initial state is not the eigenstate of the relational constraint (initial Hamiltonian). For example, instead of having a MWC graph with 10 configurations, as in Figure 3, what happens if we use a full MWC graph with 32 configuration nodes, while keeping the relational constraint in Equation (1)?

The good approximation theorem in Theorem 3.10 shows that if we can partition all configurations into relevant and irrelevant sets, with the condition that the two sets are clearly separated, the AQC evolution procedure does not affect the configurations in the irrelevant set, i.e., the amplitudes of configurations are not affected during computation, while the configurations in the relevant set are evolved in a trend similar to the case when the irrelevant set is empty; therefore, the configuration with the highest probability at the end is still the solution for the problem.

Dynamic Semantics and Optimal Compilation. The above interpretation of a constraint provides the constraint semantics, which constrains the user-desired system outcome, while we need dynamic semantics as a standard for guaranteeing compilation correctness. We can derive such a dynamic semantics from the constraint semantics, as shown in Theorem 3.8.

For compilation, the key is an enumeration process that recognizes a quantum state change, relying on four operations, 00, 11, ↑\uparrow, and ↓\downarrow, with the following operational behavior.

0∣0⟩:=∣0⟩0∣1⟩:=01∣0⟩:=01∣1⟩:=∣1⟩↑∣0⟩:=∣1⟩↑∣1⟩:=0↓∣0⟩:=0↓∣1⟩:=∣0⟩0\lvert0\rangle:= \lvert0\rangle\qquad0\lvert1\rangle:= 0 \qquad1\lvert0\rangle:= 0 \qquad1\lvert1\rangle:= \lvert1\rangle\qquad\uparrow\lvert0\rangle:= \lvert1\rangle\qquad\uparrow\lvert1\rangle:= 0 \qquad\downarrow\lvert0\rangle:= 0 \qquad\downarrow\lvert1\rangle:= \lvert0\rangle

To compile data constraints, we use the 00 and 11 operations. In clique finding, we essentially enumerate Yes and No as ∣1⟩\lvert1\rangle and ∣0⟩\lvert0\rangle, respectively. For every configuration, we generate every possible pair (x(x and y)y) of data points, and interpret the two choices in the data-constraint ff, where f(choice⁡(x),choice⁡(y))f(\operatorname{choice}(x), \operatorname{choice}(y)) is the energy loss score for (x,y)(x,y). We then summarize all the energy scores for each possible pair as the final energy loss for the configuration. Essentially, we can view ff as a function that interprets the choices for a data-point pair. For example, in the {a,c,d}\{a,c,d\} configuration of Figure 3, we interpret the pairs (a,b)(a,b), (a,c)(a,c), (c,d)(c,d) with different choice combination. To interpret (a,b)(a,b), we take its choice value, (1,0)(1,0), and input it into the data constraint to query the energy score.

Recall that the choices are represented as basis-vectors in a quantum state, e.g., (1,0)(1,0) is represented as ∣1⟩∣0⟩\lvert1\rangle\lvert0\rangle. A quantum state is not observable, so we use the operators 00 and 11 to represent ∣0⟩\lvert0\rangle and ∣1⟩\lvert1\rangle, respectively. For example, (1,0)(1,0) is represented as 1⊗01 \otimes0 and we assign the energy score as the amplitude, f(1,0)⋅1⊗0f(1,0) \cdot1 \otimes0. Finally, we sum all the generated operations, e.g., f(1,0)⋅1⊗0f(1,0) \cdot1 \otimes0, together via a linear sum. In EnQ+^{+}, we also instantiate the abstract energy scores with actual values to optimize the process.

Similarly, we can compile a relational constraint as a combination of ↑\uparrow and ↓\downarrow. For example, to compile the relational constraint above, we consider two configurations connected by an edge (ϕ1,ϕ2)(\phi_1,\phi_2). We then compare the same name (id) data-points across ϕ1\phi_1 and ϕ2\phi_2, having different choices, such as dd and ee in the pairs {a,c,d}\{a,c,d\} and {a,c,e}\{a,c,e\}. A choice changes 1→01 \to0 and 0→10 \to1 across the two data points, yielding a ↓\downarrow and ↑\uparrow operation, respectively, e.g., the pair (d,e)(d,e) is compiled to ↓⊗↑+↑⊗↓\downarrow\otimes\uparrow+ \uparrow\otimes\downarrow, where the linear sum ensures the symmetry property. The above compilation compares a single configuration pair; to compile all configuration pairs, we use linear sums.

Apparently, the above procedure generates a linear sum of four operations, which is a syntactic sugar of Pauli operations. We then rewrite the operation into Pauli-string format ∑j⨂k=0nPk\sum_j \bigotimes_{k=0}^{n} \mathcal{P}_k with P∈{X,Y,Z,I}\mathcal{P} \in\{X,Y,Z,I\}, via the rules below.

0:=I+Z1:=I−Z↑:=X−iY↓:=X+iY0 := I + Z \qquad1 := I - Z \qquad\uparrow:= X - iY \qquad\downarrow:= X + iY

After producing a linear sum of Pauli strings, H^=∑j⨂k=0nPk\hat{H} = \sum_j \bigotimes_{k=0}^{n} \mathcal{P}_k, via distributive rewrites, we then utilize the approximation procedure in § 2 to compute the AQC of the Pauli-string formula, while compiling the Hamiltonian simulation procedure via Trotterization.

While developing our certified compiler, we discovered a fault in previous AQC compilation papers; see § 4.4.

The EnQ+^{+} Formalism

This section discusses the syntax, semantics, type system, and meta-theorems for EnQ+^{+}. We use the running example of the clique finding problem (Figure 2) with the MWC graphs in Figure 3.

State Representation

We discuss the state used in EnQ+^{+}, built on an MWC graph, where each node contains a configuration for a user-defined problem. We first define user-defined data structures below, having type G(δ)\mathcal{G}(\delta), assumed to contain data points with type δ\delta.

Definition 3.1 (Data Structure and Configuration). We define G∈G(δ)G \in\mathcal{G}(\delta) to be a data structure containing data-points with type δ\delta. Each data-point object must at least contain the fields of identity

Metavariablesx,y∈Variables,ζ∈C,m,n,j,k∈N,r∈R,G∈G(δ)Energy Datav::=r∣data⁡(δ)∣choice⁡(δ)Energy expressionε::=v∣ε+ε∣ε×ε∣if g then ε else εGuardg::=f(ε1,…,εk) (f∈Σ)g::=∣ε=ε∣g∧g∣¬gSingleton constraint (U)μU::=ε∣∂x∈D. μUData constrainteU::=μU∣eU+eUTupleχ::=(x1,…,xk)Constraint Flagι::=∗∣0∣1Singleton constraint (S)μS::={x}ι∣∂χ∈D. μSRelational constrainteS::=μS∣eS+eSProgramP::={struct⁡:G(δ),choices⁡:C,initS⁡:Φ,constraint⁡:eU,relation⁡:eS\begin{aligned} \text{Metavariables}\quad&x,y\in\mathrm{Variables},\quad\zeta\in\mathcal{C},\quad m,n,j,k\in\mathbb{N},\quad r\in\mathbb{R},\quad G\in\mathcal{G}(\delta)\\ \text{Energy Data}\quad&v ::= r \mid\operatorname{data}(\delta) \mid\operatorname{choice}(\delta)\\ \text{Energy expression}\quad&\varepsilon::= v \mid\varepsilon+\varepsilon\mid\varepsilon\times\varepsilon\mid\text{if }g\text{ then }\varepsilon\text{ else }\varepsilon\\ \text{Guard}\quad&g ::= f(\varepsilon_{1},\ldots,\varepsilon_{k})\ (f\in\Sigma)\\ &\phantom{g ::=}\mid\varepsilon=\varepsilon\mid g\land g \mid\neg g\\ \text{Singleton constraint (U)}\quad&\mu_{U} ::= \varepsilon\mid\partial x\in\mathcal{D}.\ \mu_{U}\\ \text{Data constraint}\quad&e_{U} ::= \mu_{U}\mid e_{U}+e_{U}\\ \text{Tuple}\quad&\chi::= (x_{1},\ldots,x_{k})\\ \text{Constraint Flag}\quad&\iota::= *\mid0\mid1\\ \text{Singleton constraint (S)}\quad&\mu_{S} ::= \{x\}^{\iota}\mid\partial\chi\in\mathcal{D}.\ \mu_{S}\\ \text{Relational constraint}\quad&e_{S} ::= \mu_{S}\mid e_{S}+e_{S}\\ \text{Program}\quad&P ::= \left\{ \begin{array}{l} \operatorname{struct}: \mathcal{G}(\delta),\\ \operatorname{choices}: \mathcal{C},\\ \operatorname{initS}: \Phi,\\ \operatorname{constraint}: e_{U},\\ \operatorname{relation}: e_{S} \end{array} \right. \end{aligned}

(id), datum (data(δ\delta)), and choice (choice(δ\delta)). We assume data (data(δ\delta)) has an energy value type (R\mathbb{R}) and a set of choices choice(δ\delta) = ζ∈C\zeta\in\mathcal{C} that turns a choice into an energy value. Given C\mathcal{C}, a configuration is a data structure GG, with choice assignments (δ→C\delta\to\mathcal{C}) in C\mathcal{C} to every data-points in GG.

The example graph in Figure 2 has 5 data-points, {a,b,c,d,e}\{a,b,c,d,e\}. There is no need to use the data fields in clique finding, where we can define the data as ∀x.data⁡(x)=0\forall x.\operatorname{data}(x)=0, and choices for each node can be {no,yes}\{\text{no},\text{yes}\}. The solution has the assignment {a↦yes,b↦yes,c↦yes,d↦no,e↦no}\{a\mapsto\text{yes},b\mapsto\text{yes},c\mapsto\text{yes},d\mapsto\text{no},e\mapsto\text{no}\}. We show the MWC graph definition below.

Definition 3.2 (MWC Graph). We define Φ=(V,E)\Phi=(\mathcal{V},\mathcal{E}) to be a MWC graph, containing a set of configurations (V\mathcal{V}) and edges (E\mathcal{E}). Each configuration contains a data-structure (content) and an amplitude field (amp) having type R\mathbb{R}, while each edge contains a weight field (weight) having type R\mathbb{R}. All configurations in Φ\Phi have the same set D\mathcal{D} of data-points, where ∀ϕ∈V.points⁡(ϕ)=D\forall\phi\in\mathcal{V}.\operatorname{points}(\phi)=\mathcal{D} and points⁡(ϕ)≔{id⁡(δ)∣δ∈ϕ}\operatorname{points}(\phi)\coloneqq\{\operatorname{id}(\delta)\mid\delta\in\phi\}.

A MWC graph Φ\Phi essentially represents a quantum superposition state, while configurations are basis-ket states. We assume that configurations and edges not mentioned in a MWC graph have zero amplitudes and weights, respectively. In Figure 1, we assume the case with all four nodes empty has amplitude 0, and every connected edge has weight 0 as well.

Syntax and Typing

An EnQ+ program (Figure 4) contains five components: a data-structure (struct, GG) containing a set of distinct data-points (δ\delta), a set of choices (choices, C\mathcal{C}), an initial state (initS, Φ\Phi) acting as the initial set of configurations with data-points being assigned with different choice values, a data constraint (constraint, eUe_U), and a relational constraint (relation, eSe_S). The program syntax extends EnQ with an initial starting state and a second syntactic category, relational constraints eSe_S, that let the programmer declare the structure of the initial Hamiltonian directly. Figure 4 gives the extended grammar; shaded productions are new.

Grammar of EnQ+

Figure 4. Grammar of EnQ+. Shaded productions are new relative to EnQ [56]. The original EnQ program form (without relation) is a special case corresponding to eS=Id⁡e_{S}=\operatorname{Id}, the trivial relational constraint whose semantics is the uniform-superposition initial Hamiltonian. D\mathcal{D}: a set of data-points.

When defining a data constraint (eUe_U), we assign an energy-loss value to unwanted cases. Users are able to access the data value of a data-point (data(δ\delta)), turn a choice into an energy loss (choice(δ\delta)), or use classical arithmetic (ε\varepsilon) and Boolean (gg) expressions. In EnQ{sup}+, we allow a generic definition of energy loss, and the EnQ{sup}+ compiler finds the best fit by assigning real numbers to the generic energy loss, while ensuring every energy loss value is positive.

A relational constraint eSe_S is a sum of singleton relational constraints, allowing the programmer to specify relations among edges in MWC graphs. Such a constraint {x‾}∼ι\{\overline{x}\}^{\sim\iota} is defined by a list of variables (x‾\overline{x}) and a relational flag ι\iota. The former indicates the number of data points to examine together, and the latter indicates the movement relation among them; for example, § 2 shows how to examine every two data points with the swap relation between them. The other two flags, 0 and 1, constrain whether the movement is in the same or a different direction, as in § 2.

To specify the number of data points to examine, we permit binders, e.g., ∂x.∂y.{x,y}∼∗\partial x.\partial y.\{x,y\}^{\sim*}. In a singleton data constraint μU\mu_U and singleton relational constraint μS\mu_S, users can bind a site tuple (a singleton tuple is a variable) via ∂\partial-binders. The binder ∂x∈x‾.μS\partial x \in\overline{x}.\mu_S or (∂x∈D.μU)(\partial x \in D.\mu_U) binds a variable xx to a data-point, selected from the data-point set DD, and used in μS\mu_S (or μU\mu_U). In EnQ{sup}+, we permit a choice to be a tuple data-structure, and users are able to mention a subcomponent of a tuple in a binder, e.g., ∂(x,y)∈∂(u,v).{y,v}∼0\partial(x,y) \in\partial(u,v).\{y,v\}^{\sim0}. means that every choice is a pair and we establish the relation on the second part of each pair as 0-flagged.

The ∂\partial-binders quantify the atom over all tuples of nodes defined in x‾\overline{x}, a data-point subset of struct, producing a sum of two-site operators that define the full initial Hamiltonian. One can omit the set notation in a binder (∂χ.μ\partial\chi.\mu) to refer to choosing χ\chi from the whole data-point set, and ∂χ.∂χ′.μ\partial\chi.\partial\chi'.\mu selects two tuples χ\chi and χ′\chi', where they must be distinct data-points.

Typing. Figure 5 defines the type system, which has the top-level judgment ⊢P\vdash P, as well as the expression judgment Γ⊢−:τ\Gamma\vdash- : \tau, where Γ\Gamma is the type environment, mapping from variables to data-point sets; −- could be a program PP, an arithmetic (ε\varepsilon) and Boolean (gg) expression; τ\tau is the type construct, defined as follows.

Type rules

Figure 5. Type rules.

τ::=R∣bool∣S\tau::= \mathcal{R} \mid\mathsf{bool} \mid S

Here, R\mathcal{R}, bool\mathsf{bool}, and SS indicate an arithmetic expression, a Boolean expression, and a constraint expression, respectively.

The type system guarantees three properties. First, it guarantees the right types for the right expressions: rule T-Plus types the addition expression with the R\mathcal{R} type, rule T-And types a Boolean expression, and rule T-Sum types a constraint choice operator. Second, the type system ensures that type variables are properly scoped. Rules T-Data and T-Choice ensure variables are properly scoped in the type environment, while rule T-Bind binds a variable in the type environment and maps it to its right data-point set. Rules T-Sum and T-Top ensure that the top-level constraints have no free variables.

Third, we ensure that constraint variables are disjoint and that no constraints are empty. In EnQ{sup}+, nested constraint variables must represent distinct data points; e.g., ∂x.∂y.μ\partial x.\partial y.\mu means xx and yy must be two distinct data points. Rule T-Rel partitions the type environment (x‾:D)(\overline{x} : \mathcal{D}) into distinct subsets to type the subterms.

In rule T-Bind, we use several premises to compute the correct data-point set for the variable yy, because selecting the data-point set might empty a constraint. For example, since ∂x∈D\partial x \in\mathcal{D}. ∂y∈D\partial y \in\mathcal{D}. μ\mu requires that xx and yy to be two distinct data-points, if ∣D∣=1|\mathcal{D}| = 1, the constraint becomes empty. To avoid an empty constraint, we ensure that all data points mentioned in the type environment can be partitioned into regions, and that yy’s data-point set D‾\overline{D} lies within a region D‾\overline{D} with variable set x‾\overline{x}. We also ensure that the sets D‾\overline{D} can be ordered as D‾0⊆⋯⊆D‾∣D‾∣−1\overline{D}_0 \subseteq\cdots\subseteq\overline{D}_{|\overline{D}|-1}, and every set in D‾={D‾1}\overline{D} = \{\overline{D}_1\} is a subset of D‾0\overline{D}_0. Then, the cardinality of D‾1\overline{D}_1 exceeds the number of variables (x‾(\overline{x} and y‾)\overline{y}), ensuring no empty constraint. In rule T-Top, dom⁡(eU)∪dom⁡(eS)⊢Φ\operatorname{dom}(e_U) \cup\operatorname{dom}(e_S) \vdash\Phi collects all the mentioned data points and ensures that the configurations in Φ\Phi cover the data points.

We discuss type soundness in the next section.

Semantics

The semantics of EnQ+ is divided into two categories: constraint semantics and dynamic semantics, as discussed below.

Constraint Semantics. Constraint semantics is a function that yields the judgment ⟦P⟧ΦΦ′\llbracket P \rrbracket_{\Phi}^{\Phi'}, where PP is a program and Φ/Φ′\Phi/\Phi' are MWC graphs. A data constraint might contain an expression ε\varepsilon with the type U(x‾)U(\overline{x}), where we can interpret x‾\overline{x} with δ‾\overline{\delta}, so ε[δ‾/x‾]\varepsilon[\overline{\delta}/\overline{x}] produces an energy loss rr; such rules are shown in Figure 6.

We now define the constraint semantics as a function interpreting a MWC graph Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}), with each node ϕ∈V\phi\in\mathcal{V} having a fixed set of data-points δ‾\overline{\delta}, coming from the user-defined data structure struct⁡(P)\operatorname{struct}(P). For simplicity, we linearize the tuples in each binding, as in the following example.

∂(x‾)∈(D‾1). ∂(y‾)∈(D‾2). e=∂(x‾,y‾)∈(D‾1,D‾2). e\partial(\overline{x}) \in(\overline{D}_1).\,\partial(\overline{y}) \in(\overline{D}_2).\,e = \partial(\overline{x},\overline{y}) \in(\overline{D}_1,\overline{D}_2).\,e

We first define the data constraint semantics.

⟦r⟧v=r⟦data⁡(δ)⟧v=data⁡(v(δ))⟦choice⁡(δ)⟧v=choice⁡(v(δ))⟦ε1+ε2⟧v=⟦ε1⟧v+⟦ε2⟧v\llbracket r \rrbracket^{v} = r \qquad\llbracket\operatorname{data}(\delta) \rrbracket^{v} = \operatorname{data}(v(\delta)) \qquad\llbracket\operatorname{choice}(\delta) \rrbracket^{v} = \operatorname{choice}(v(\delta)) \qquad\llbracket\varepsilon_1+\varepsilon_2 \rrbracket^{v} = \llbracket\varepsilon_1 \rrbracket^{v}+\llbracket\varepsilon_2 \rrbracket^{v}
⟦ε1×ε2⟧v=⟦ε1⟧v×⟦ε2⟧v⟦if⁡ g then⁡ ε1 else⁡ ε2⟧v=if⁡ ⟦g⟧v then⁡ ⟦ε1⟧v else⁡ ⟦ε2⟧v⟦¬ε⟧v=¬⟦ε⟧\llbracket\varepsilon_1 \times\varepsilon_2 \rrbracket^{v} = \llbracket\varepsilon_1 \rrbracket^{v}\times\llbracket\varepsilon_2 \rrbracket^{v} \qquad\llbracket\operatorname{if}\ g\ \operatorname{then}\ \varepsilon_1\ \operatorname{else}\ \varepsilon_2 \rrbracket^{v} = \operatorname{if}\ \llbracket g \rrbracket^{v}\ \operatorname{then}\ \llbracket\varepsilon_1 \rrbracket^{v}\ \operatorname{else}\ \llbracket\varepsilon_2 \rrbracket^{v} \qquad\llbracket\neg\varepsilon\rrbracket^{v} = \neg\llbracket\varepsilon\rrbracket
⟦f(ε1,…,εk)⟧v=f(⟦ε1⟧v,…,⟦εk⟧v)⟦ε1=ε2⟧v=⟦ε1⟧v=⟦ε2⟧v⟦ε1∧ε2⟧v=⟦ε1⟧v∧⟦ε2⟧v\llbracket f(\varepsilon_1,\ldots,\varepsilon_k) \rrbracket^{v} = f(\llbracket\varepsilon_1 \rrbracket^{v},\ldots,\llbracket\varepsilon_k \rrbracket^{v}) \qquad\llbracket\varepsilon_1=\varepsilon_2 \rrbracket^{v} = \llbracket\varepsilon_1 \rrbracket^{v}=\llbracket\varepsilon_2 \rrbracket^{v} \qquad\llbracket\varepsilon_1\land\varepsilon_2 \rrbracket^{v} = \llbracket\varepsilon_1 \rrbracket^{v}\land\llbracket\varepsilon_2 \rrbracket^{v}

Fig. 6. Expression Level Constraint Semantics

Definition 3.3 (Data Constraint Semantics). Given a data constraint eUe_U and a MWC graph Φ=(V,E)\Phi=(\mathcal{V},\mathcal{E}), we define data-constraint interpretation function ⟦−⟧Φ\llbracket-\rrbracket^\Phi, adding the amplitude (amp) for every ϕ∈V\phi\in\mathcal{V}, as V[ϕ↦ϕ[amp⁡(ϕ)↦⟦eU⟧ϕ+amp⁡(ϕ)]]\mathcal{V}[\phi\mapsto\phi[\operatorname{amp}(\phi)\mapsto\llbracket e_U\rrbracket^\phi+\operatorname{amp}(\phi)]], where we define the rules as follows.

⟦e1+e2⟧ϕ:=⟦e1⟧ϕ+⟦e2⟧ϕ\llbracket e_1+e_2\rrbracket^\phi:=\llbracket e_1\rrbracket^\phi+\llbracket e_2\rrbracket^\phi
⟦∂x‾∈D‾.ε⟧ϕ:=∑δ‾∈gen⁡(D‾,points⁡(ϕ))⟦ε[δ‾/x‾]⟧ϕ\llbracket\mathop{\overline{\partial x}\in\overline{D}}.\varepsilon\rrbracket^\phi:=\sum_{\overline{\delta}\in\operatorname{gen}(\overline{D},\operatorname{points}(\phi))}\llbracket\varepsilon[\overline{\delta}/\overline{x}]\rrbracket^\phi

Here, ⟦ε⟧ϕ\llbracket\varepsilon\rrbracket^\phi is the interpretation function in Figure 6, ++ is a function sum, with f1+f2:=∀ϕ∈V.V[amp⁡(ϕ)↦f1(ϕ)+f2(ϕ)]f_1+f_2:=\forall\phi\in\mathcal{V}.\mathcal{V}[\operatorname{amp}(\phi)\mapsto f_1(\phi)+f_2(\phi)], and the gen function is defined as follows.

gen⁡(D‾0,D′):=D‾0∩D′∧∀j. gen⁡(D‾j+1,Dj+1′):=D‾j+1∩(D′∖{δj})\operatorname{gen}(\overline{D}_0,\mathcal{D}'):=\overline{D}_0\cap\mathcal{D}' \qquad\land\qquad\forall j.\ \operatorname{gen}(\overline{D}_{j+1},\mathcal{D}'_{j+1}):=\overline{D}_{j+1}\cap(\mathcal{D}'\setminus\{\delta_j\})

The iterative function gen generates a list of data points (δ‾\overline{\delta}) for calculating the energy loss values. Every singleton data constraint has the form ∂x0∈D0.…∂xn∈Dn. ε\partial x_0\in D_0.\ldots\partial x_n\in D_n.\ \varepsilon, and each variable xjx_j is selected from the set DjD_j subtracting the data-points selected for x0,…,xj−1x_0,\ldots,x_{j-1}.

We define the relational constraint below as the production of the edge set E\mathcal{E}, i.e., configuration pairs connected by edges.

Definition 3.4 (Relational Constraint Semantics). Given a constant weight rar_a, given a data constraint eSe_S and a MWC graph Φ=(V,E)\Phi=(\mathcal{V},\mathcal{E}), we define data-constraint interpretation function ⟦−⟧(ϕ,ϕ′)\llbracket-\rrbracket^{(\phi,\phi')}, adding the weight (weight) for every edge (ϕ,r,ϕ′)∈E(\phi,r,\phi')\in\mathcal{E}, as E[(ϕ,r,ϕ′)↦(ϕ,r+ra,ϕ)]\mathcal{E}[(\phi,r,\phi')\mapsto(\phi,r+r_a,\phi)] if ⟦eS⟧(ϕ,ϕ′)\llbracket e_S\rrbracket^{(\phi,\phi')} is true, where we define the rules as follows.

⟦e1+e2⟧(ϕ,ϕ′):=⟦e1⟧(ϕ,ϕ′)+⟦e2⟧(ϕ,ϕ′)\llbracket e_1+e_2\rrbracket^{(\phi,\phi')}:=\llbracket e_1\rrbracket^{(\phi,\phi')}+\llbracket e_2\rrbracket^{(\phi,\phi')}
⟦∂x‾∈D‾.μ⟧(ϕ,ϕ′):=∑δ‾∈gen⁡(D‾,points⁡(ϕ))⟦μ⟧(δ‾1,δ‾2)\llbracket\mathop{\overline{\partial x}\in\overline{D}}.\mu\rrbracket^{(\phi,\phi')}:=\sum_{\overline{\delta}\in\operatorname{gen}(\overline{D},\operatorname{points}(\phi))}\llbracket\mu\rrbracket^{(\overline{\delta}_1,\overline{\delta}_2)}

when points⁡(ϕ)=δ‾1∪δ‾′\operatorname{points}(\phi)=\overline{\delta}_1\cup\overline{\delta}' and points⁡(ϕ′)=δ‾2∪δ‾′∧id⁡(δ‾1)=id⁡(δ‾2)\operatorname{points}(\phi')=\overline{\delta}_2\cup\overline{\delta}'\land\operatorname{id}(\overline{\delta}_1)=\operatorname{id}(\overline{\delta}_2).

Here, ++ is a function sum, with f1+f2:=∀ϕ∈V.E[(ϕ,r,ϕ′)↦(ϕ,f1(r)+f2(r),ϕ)]f_1+f_2:=\forall\phi\in\mathcal{V}.\mathcal{E}[(\phi,r,\phi')\mapsto(\phi,f_1(r)+f_2(r),\phi)], and the Boolean function ⟦μ⟧(δ‾1,δ‾2)\llbracket\mu\rrbracket^{(\overline{\delta}_1,\overline{\delta}_2)} is defined as follows.

⟦{x}∼0⟧(δ‾1,δ‾2):=∃n. ∀i. choice⁡(δ‾1[i])=choice⁡(δ‾2[i])+n\llbracket\{x\}^{\sim0}\rrbracket^{(\overline{\delta}_1,\overline{\delta}_2)}:=\exists n.\ \forall i.\ \operatorname{choice}(\overline{\delta}_1[i])=\operatorname{choice}(\overline{\delta}_2[i])+n
⟦{x}∼1⟧(δ‾1,δ‾2):=∀n. ∀i. choice⁡(δ‾1[i])≠choice⁡(δ‾2[i])+n\llbracket\{x\}^{\sim1}\rrbracket^{(\overline{\delta}_1,\overline{\delta}_2)}:=\forall n.\ \forall i.\ \operatorname{choice}(\overline{\delta}_1[i])\ne\operatorname{choice}(\overline{\delta}_2[i])+n
⟦{x}∼∗⟧(δ‾1,δ‾2):=perm⁡∣x∣(δ‾1,δ‾2)\llbracket\{x\}^{\sim*}\rrbracket^{(\overline{\delta}_1,\overline{\delta}_2)}:=\operatorname{perm}^{|x|}(\overline{\delta}_1,\overline{\delta}_2)

The function perm⁡n(δ‾1,δ‾2)\operatorname{perm}^{n}(\overline{\delta}_1,\overline{\delta}_2) checks whether δ‾1\overline{\delta}_1 and δ‾2\overline{\delta}_2 are an nn-order permutation, which refers to that δ‾1\overline{\delta}_1 and δ‾2\overline{\delta}_2 have the same set of choices, and there are nn positions in δ‾1\overline{\delta}_1 and δ‾2\overline{\delta}_2 having different choices. For example, 1, 2, 3 and 1, 3, 2 is a 2-order permutation while 1, 2, 3 and 2, 3, 1 is a 3-order permutation.

Finally, the constraint semantics is a function ⟦P⟧(V,E)\llbracket\mathcal{P}\rrbracket^{(\mathcal{V},\mathcal{E})}, defined as follows.

⟦eU⟧(V,E):=∑ϕ∈V⟦eU⟧ϕ⟦eS⟧(V,E):=∑(ϕ,r,ϕ′)∈E⟦eS⟧(ϕ,ϕ′)\llbracket e_U\rrbracket^{(\mathcal{V},\mathcal{E})}:=\sum_{\phi\in\mathcal{V}}\llbracket e_U\rrbracket^\phi \qquad \llbracket e_S\rrbracket^{(\mathcal{V},\mathcal{E})}:=\sum_{(\phi,r,\phi')\in\mathcal{E}}\llbracket e_S\rrbracket^{(\phi,\phi')}
endsmid=1{ends_mid=1}

With the constraint semantics, we show the type soundness theorem below.

Theorem 3.5 (Type Soundness). For a program PP, with ⊢P\vdash P, where Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}) is the initial state, there are valid interpretations of ⟦P⟧Φ\llbracket P\rrbracket^\Phi.

Proof. We prove by induction on the type rules in Figure 5. □

Dynamic Semantics. The constraint semantics of an EnQ+ program (P)(P) is a function ⟦−⟧Φ\llbracket-\rrbracket^\Phi on the MWC graph Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}), and the dynamic semantics applies the AQC evolution on the graph. The result follows the AQC theorem: given an initial ground state (minimized eigenstate) of the initial Hamiltonian, i.e., the relational constraint, AQC evolution slowly drives the state toward the ground state of the final Hamiltonian, i.e., the data constraint. In EnQ+, users can define initial states, while the AQC theorem guarantee holds only for the initial state that is the ground state of the relational constraint.

The AQC theorem unveils the result of applying an EnQ+ program in an AQC system. However, it does not unveil the dynamic semantics of a single-step evolution. Essentially, the AQC evolution follows H^(t)=(1−t)H^i+tH^f\hat{H}(t) = (1-t)\hat{H}_i + t\hat{H}_f, where H^i\hat{H}_i comes from the relational constraint and H^f\hat{H}_f from the data constraint.

In EnQ+, the dynamic semantics are theorems derived from the constraint semantics and the AQC evolution theorem. We list them as theorems below. To examine a single transition step, we first examine the evolution of individual constraints, yielding two rotation functions, ψ\psi and θ\theta, that produce rotations in [0,π2)[0,\frac{\pi}{2}). Here, we mainly develop the theory for the system constructed by EnQ+ and evolved by Hamiltonian simulation (eiH^t)(e^{i\hat{H}t}), though other AQC systems may apply. Given a program PP and an MWC graph Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}), the definition partitions configurations and edges into relevant and irrelevant sets. Given a data constraint (eU)(e_U), the relevant sets contain configurations that yield a non-zero value when eUe_U is applied, while configurations in the irrelevant set yield a 0 when eUe_U is applied.

Theorem 3.6 (Data Constraint Evolution). Given a data constraint eUe_U and an nn-dimensional MWC graph Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}), for every ϕ∈V\phi\in\mathcal{V}, the instantaneous effect ϕ′\phi', evolving the system for an evolution time ss, compilation factor ω\omega, on the relevant set is an update on ϕ\phi’s amplitude, as amp⁡(ϕ′)=eiψ(s)∗amp⁡(ϕ)\operatorname{amp}(\phi') = e^{i\psi(s)} * \operatorname{amp}(\phi), where ψ(s)∝s∗ω(amp⁡(⟦eU⟧ϕ)−amp⁡(ϕ))n\psi(s) \propto\frac{s\ast\omega(\operatorname{amp}(\llbracket e_U\rrbracket^\phi)-\operatorname{amp}(\phi))}{n}. The effect on the irrelevant set is neutral, as amp⁡(ϕ′)=amp⁡(ϕ)\operatorname{amp}(\phi') = \operatorname{amp}(\phi).

The relevant sets have a different definition for a relational constraint (eS)(e_S). Essentially, eSe_S is a Boolean function determining whether an edge, containing two configurations, is in the relevant set or in the irrelevant set.

Theorem 3.7 (Relational Constraint Evolution). Given a relational constraint eSe_S and an nn-dimensional MWC graph Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}), for every (ϕ,r,ϕ′)∈E(\phi, r, \phi') \in\mathcal{E}, the instantaneous effect r′r', evolving the system for a small time ss, compilation factor ω\omega, on the relevant set is as r′=eiθ(s)∗rr' = e^{i\theta(s)} * r, where θ(s)∝s∗ω∗mn2\theta(s) \propto\frac{s\ast\omega\ast m}{n^2}, where mm is the number of nonzero increment in E\mathcal{E}, i.e., the number of edges (ϕ,r,ϕ′)(\phi, r, \phi') such that weight⁡([ ⁣[eS] ⁣](ϕ,ϕ′))−r≠0\operatorname{weight}([\![e_S]\!]^{(\phi,\phi')}) - r \ne0. The effect on the irrelevant set is neutral, as r′=rr' = r.

The above unveils the dynamic semantics for evolving the data and relational constraints individually, yielding two angle functions ψ(s)\psi(s) and θ(s)\theta(s) in the range [0,π2)[0,\frac{\pi}{2}), respectively interpreting each configuration and edge in a MWC graph. In fact, both angles must be ≪π2\ll\frac{\pi}{2}.

With the definition for individual constraints, we define the dynamic semantics of the whole system, based on two-step operations, step⁡b(ψ(s),θ(s))\operatorname{step}^{b}(\psi(s), \theta(s)) and step⁡g(ψ(s),θ(s))\operatorname{step}^{g}(\psi(s), \theta(s)), which are two monotonic functions within the AQC evolution steps, i.e., given a single step time factor Δt\Delta t, evolution stops exactly at the ⌈1Δt⌉\left\lceil\frac{1}{\Delta t} \right\rceil steps. The former defines the step behavior of a relevant configuration, essentially a bad state with energy loss, and the latter defines the step behavior of a good state, an irrelevant configuration with 0 energy loss. The step evolution of the two operations modifies the likelihood of good and bad states. In each step, we modify ψ\psi’s time factor from 0 to 1 and θ\theta’s factor from 1 to 0 by Δt\Delta t.

Theorem 3.8 (Dynamic Semantics). Given an initial state as MWC graph Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}), for every ϕ∈V\phi\in\mathcal{V}, we have an angle ψ(s)\psi(s), and for every relevant edge (ϕ,r,ϕ′)(\phi, r, \phi'), we have an angle function θ(s)\theta(s); we define the dynamic transition steps based on relevant edges, step⁡b(ψ(s),θ(s))\operatorname{step}^{b}(\psi(s), \theta(s)) and step⁡g(ψ(s),θ(s))\operatorname{step}^{g}(\psi(s), \theta(s)), as the likelihood multiplication on configuration’s amplitude, i.e., given nn step, the evolution transitions ϕ\phi’s amplitude as step⁡ng∗amp⁡(ϕ)\operatorname{step}^{g}_{n} * \operatorname{amp}(\phi) for good states and the amplitude step⁡nb∗amp⁡(ϕ)\operatorname{step}^{b}_{n} * \operatorname{amp}(\phi) for bad states.

step⁡0b=1step⁡0g=1step⁡j+1b=eiψ(jΔt)cos⁡[θ(1−jΔt)]∗step⁡jb−isin⁡[θ(1−jΔt)]∗step⁡jgstep⁡j+1g=cos⁡[θ(1−jΔt)]∗step⁡jg−eiψ(jΔt)isin⁡[θ(1−jΔt)]∗step⁡jb\begin{aligned} \operatorname{step}^{b}_{0} &= 1 & \operatorname{step}^{g}_{0} &= 1 \\ \operatorname{step}^{b}_{j+1} &= e^{i\psi(j\Delta t)}\cos[\theta(1-j\Delta t)] * \operatorname{step}^{b}_{j} - i\sin[\theta(1-j\Delta t)] * \operatorname{step}^{g}_{j} \\ \operatorname{step}^{g}_{j+1} &= \cos[\theta(1-j\Delta t)] * \operatorname{step}^{g}_{j} - e^{i\psi(j\Delta t)}i\sin[\theta(1-j\Delta t)] * \operatorname{step}^{b}_{j} \end{aligned}

Proof. The proofs of Theorems 3.6 to 3.8 rely on the case analysis on individual configurations and edges. We assume a restricted AQC where the program data constraints are diagonal and the compilation is Hamiltonian-simulation-based; therefore, we can analyze Theorems 3.6 and 3.7 by applying Hamiltonian-simulation operators to compiled Pauli-string programs. The proof for Theorem 3.8 alters the effects of the two simulation results in Theorems 3.6 and 3.7. □

Based on Theorem 3.8, we have the following lemma regarding the monotonicity of the two-step operations.

Theorem 3.9 (Step Operation Monotonicity). For the evolution steps ⌈1Δt⌉\left\lceil\frac{1}{\Delta t} \right\rceil, i.e., j∈[0,⌈1Δt⌉)j \in[0, \left\lceil\frac{1}{\Delta t} \right\rceil), step⁡jb\operatorname{step}^{b}_{j} is a monotonic decreasing function, while step⁡jg\operatorname{step}^{g}_{j} is a monotonic increasing function.

Proof. The proof proceeds by induction on the steps for step⁡b\operatorname{step}^{b} and step⁡g\operatorname{step}^{g}. □

Theorems 3.8 and 3.9 cover the case where all edges are relevant. They also assume that relevant and irrelevant edges are orthonormal. As shown in § 2, the EnQ+ relational constraints are compiled to ↑\uparrow and ↓\downarrow, which might modify basis-vectors, i.e., an edge in the relevant set might be modified to one in the irrelevant set. In this paper, we assume such a case does not occur and leave it as future work.

To ensure that all nonzero weighted edges are relevant, the initial MWC graph is the eigenstate of the relational constraint. An interesting study is what if we do not start with the right initial state. Some initial state preparations, such as states of distinct elements, are costly to implement on a quantum computer. We show in the good approximation theorem below that starting with an ideal relational constraint but an easily prepared, imperfect initial state—one that is not the eigenstate of the relational constraint—can still produce meaningful results.

Assume that Φ1=(V1,E1)\Phi_1 = (\mathcal{V}_1, \mathcal{E}_1) is the eigenstate of a relational constraint (eSe_S), where V1⊆V\mathcal{V}_1 \subseteq\mathcal{V}. We define such a relation as Φ1⊨eSΦ\Phi_1 \models_{e_S} \Phi, with Φ1\Phi_1 being the eigenstate of eSe_S and all non-zero configurations and edges in Φ1\Phi_1 are defined in Φ\Phi. Under this definition, the following theorem relates Φ1\Phi_1 and Φ\Phi.

Theorem 3.10 (Good Approximation). Given PP, with eSe_S being the relational constraint and Φ1=(V1,E1)\Phi_1 = (\mathcal{V}_1, \mathcal{E}_1) being the initial state, assume Φ=(V,E)\Phi= (\mathcal{V}, \mathcal{E}), with Φ1⊨eSΦ\Phi_1 \models_{e_S} \Phi, PP partitions V\mathcal{V} into relevant (Vr\mathcal{V}_r) and irrelevant (Vi\mathcal{V}_i) sets, as PP keeps the two sets being orthonormal; for every ϕ∈Vi\phi\in\mathcal{V}_i, the AQC evolution results keep the final amplitudes the same as the initial one in Φ\Phi.

Proof. The proof follows through the dynamic semantics analysis in Theorems 3.6 to 3.8. The key is that Hamiltonian-simulation-based AQC requires alternating between the two constraints to drive state evolution. If a configuration (or configurations connected by an edge) is only relevant for a single constraint (data or relational), its AQC evolution effect is only a phase rotation. □

The EnQ+ Compilation Procedure

This section introduces the EnQ+ compilation procedure, shown in Figure 7, which can be divided into the following steps.

Figure 7. The ENQ+ Compiler Flow

  • We compile the initial MWC graph into an initial quantum state, prepared as a superposition containing all candidate solutions, as the eigenstate of the relational constraint.

  • Translate both the relational and data constraints, written in the syntax in Figure 4, to Pauli-string-based Hamiltonians.

  • Guide the system toward that ground state, either via gate-based AQC, compiled by Trotterization.

Generating Initial Quantum State

The classical implementation explicitly traverses all possible choices to build the solution space. For instance, a list of nn variables with two options each would generate N=2nN = 2^n combinations. Instead of iterating through each combination, we prepare a quantum superposition that represents all NN possible solutions simultaneously. We allocate a set of qubits to encode the choice variables (e.g., one qubit per binary choice).

In AQC, we start with an initial quantum superposition state ∣φ(0)⟩\lvert\varphi(0)\rangle, the eigenstate of the relational constraint. There is no algorithm to prepare an arbitrary quantum state, but there are some algorithms to prepare special kinds. In EnQ+, we allow users to start with several initial states, including the uniform superposition state, Hamming weight state, permutation state, and distinct element state. For each state, we can attach special amplitudes to different basis-ket states.

∣φ⟩=∑j=02n−1αj∣bj⟩∣φ(0)⟩=∑j=02n−112n∣j⟩\lvert\varphi\rangle= \sum_{j=0}^{2^n-1} \alpha_j \lvert b_j\rangle\qquad\lvert\varphi(0)\rangle= \sum_{j=0}^{2^n-1} \frac{1}{\sqrt{2^n}} \lvert j\rangle

We provide two examples here. A typical initial quantum state is a uniform superposition. For example, if a variable has two choices, a single qubit in state ∣0⟩\lvert0\rangle is transformed to 12(∣0⟩+∣1⟩)\frac{1}{\sqrt{2}}(\lvert0\rangle+ \lvert1\rangle). For nn binary variables, this yields a uniform superposition of all 2n2^n combinations, which can be transformed to the form listed on the right side above. The state has 2n2^n different basis-kets, each with amplitude being 12n\frac{1}{\sqrt{2^n}} and a basis-vector ∣j⟩\lvert j\rangle. Here, jj denotes the binary string representation of the number jj. In the quantum setting of the clique-finding example, we want to start with an nn-qubit initial superposition state of KK-th Dicke state, (nK)−12∑h(j)=K∣j⟩\binom{n}{K}^{-\frac{1}{2}} \sum_{h(j)=K} \lvert j\rangle, where h(j)h(j) checks the bitstring representation of jj having exactly KK copies of 1. Different selections of initial states might affect the convergence speed of the AQC computation.

C-EU

x‾:D‾,Γ⊢e:R▹∑k∈C−fit⁡(e[k‾/x‾])⋅◯x‾∈⟦∣k⟩⟧C(x)\overline{x} : \overline{D},\Gamma\vdash e : R \triangleright\sum_{k\in C} -\operatorname{fit}(e[\overline{k}/\overline{x}])\cdot\bigcirc_{\overline{x}\in\llbracket|k\rangle\rrbracket^{C}(x)}

C-Bind

y:D,x‾:D‾,Γ⊢e:S▹H^y:D,\overline{x}:\overline{D},\Gamma\vdash e:S\triangleright\hat{H}
x‾:D‾,Γ⊢∂y∈D.e:S▹∑y∈D∖{x‾}H^(y)\overline{x}:\overline{D},\Gamma\vdash\partial y\in D.e:S\triangleright\sum_{y\in D\setminus\{\overline{x}\}}\hat{H}(y)

C-ES

x‾:D‾,Γ⊢{x‾}∼:S▹∑δ‾∈gen⁡(D‾,points⁡(struct⁡(P)))⟦{δ‾}∼⟧C\overline{x}:\overline{D},\Gamma\vdash\{\overline{x}\}^{\sim}:S\triangleright\sum_{\overline{\delta}\in\operatorname{gen}(\overline{D},\operatorname{points}(\operatorname{struct}(P)))}\llbracket\{\overline{\delta}\}^{\sim}\rrbracket^{C}

C-Sum

∅⊢e1:S▹H^1∅⊢e2:S▹H^2\varnothing\vdash e_{1}:S\triangleright\hat{H}_{1}\qquad\varnothing\vdash e_{2}:S\triangleright\hat{H}_{2}
∅⊢e1+e2:S▹H^1+H^2\varnothing\vdash e_{1}+e_{2}:S\triangleright\hat{H}_{1}+\hat{H}_{2}

Compiling EnQ+ Programs to Pauli-strings

We examine the compilation of constraint expressions eUe_U and eSe_S to Pauli-string forms H^\hat{H}, as the extension of the EnQ+ type system, Γ⊢e:S▹H^\Gamma\vdash e:S\triangleright\hat{H}, with H^\hat{H} having the form ∑j⨂k=0nPk\sum_j\bigotimes_{k=0}^{n}\mathcal{P}_k. The rules are in Figure 8.

Figure 8. Compilation Rules. PP is the program and points produces data-points of a configuration in struct⁡(P)\operatorname{struct}(P).

Rule C-Sum turns an EnQ+ composition operation into a linear sum; C-Bind turns the data-point choice for yy into a linear sum over yy’s possible selections, while C-EU and C-ES are respectively the data and relational constraint rules for a fixed selection of data-points referred to by x‾\overline{x}. We discuss the data and constraint individual compilation functions below.

Marking Choice States. The key step in generating Pauli strings turns basis-vector states into Pauli-string operations. As demonstrated in § 2, given an input/output pair ∣b⟩→∣b′⟩|b\rangle\to|b'\rangle (b∈[0,1]b\in[0,1]), we examine the (b,b′)(b,b') pair and yield an operator in {↑,↓,0,1}\{\uparrow,\downarrow,0,1\}. We name the procedure state marking, because applying an operator to an unqualified vector yields OO, e.g., 0∣1⟩=O0|1\rangle=O.

The procedure extends to the high-order case. In EnQ+, a solution for a problem contains many nodes, each of which needs some qubits to represent a choice. Given a choice set CC, we use a ⌈log⁡(∣C∣)⌉\lceil\log(|C|)\rceil number of qubits to represent all the choices. For example, in the graph coloring problem, users might want to use a choice set of colors, C={Black,Red,Blue,White}C=\{\mathrm{Black},\mathrm{Red},\mathrm{Blue},\mathrm{White}\}. Here, we can use two qubits per node to represent the four colors as ∣00⟩|00\rangle, ∣01⟩|01\rangle, ∣10⟩|10\rangle, and ∣11⟩|11\rangle, respectively. We can extend this idea to an nn-qubit state marking, ∣j⟩n→∣k⟩n|j\rangle_n\to|k\rangle_n, using the following operations.

⟦∣i⟩→∣j⟩⟧C≜⨂u=0⌈log⁡(∣C∣)⌉−1Au(i,j)(2)\llbracket|i\rangle\to|j\rangle\rrbracket^{C}\triangleq\bigotimes_{u=0}^{\lceil\log(|C|)\rceil-1}\mathcal{A}^{u}(i,j) \tag*{(2)}

where

∣j⟩n=⟦j⟧[0]⟧⟦j⟧[1]⟧⋯⟦j⟧[n−1]⟧|j\rangle_n=\llbracket j\rrbracket[0]\rrbracket\llbracket j\rrbracket[1]\rrbracket\cdots\llbracket j\rrbracket[n-1]\rrbracket
Ak(j,m)=↑ if ⟦j⟧[k]=0∧⟦m⟧[k]=1Ak(j,m)=1 if ⟦j⟧[k]=⟦m⟧[k]=1\mathcal{A}^{k}(j,m)=\uparrow\ \text{if}\ \llbracket j\rrbracket[k]=0\land\llbracket m\rrbracket[k]=1 \qquad \mathcal{A}^{k}(j,m)=1\ \text{if}\ \llbracket j\rrbracket[k]=\llbracket m\rrbracket[k]=1
Ak(j,m)=↓ if ⟦j⟧[k]=1∧⟦m⟧[k]=0Ak(j,m)=0 if ⟦j⟧[k]=⟦m⟧[k]=0\mathcal{A}^{k}(j,m)=\downarrow\ \text{if}\ \llbracket j\rrbracket[k]=1\land\llbracket m\rrbracket[k]=0 \qquad \mathcal{A}^{k}(j,m)=0\ \text{if}\ \llbracket j\rrbracket[k]=\llbracket m\rrbracket[k]=0

Here, ⟦j⟧\llbracket j\rrbracket converts jj to a bitstring, and the operations in {↑,↓,0,1}\{\uparrow,\downarrow,0,1\} can be compiled to Pauli operators as follows.

↑≜X−iY↓≜X+iY0≜I+Z1≜I−Z\uparrow\triangleq X-iY\qquad\downarrow\triangleq X+iY\qquad0\triangleq I+Z\qquad1\triangleq I-Z

The state marking function (⟦∣i⟩→∣j⟩⟧C)(\llbracket|i\rangle\to|j\rangle\rrbracket^{C}) essentially utilizes the bitstring representations of ii and jj. For the kk-th bit position (⟦i⟧[k](\llbracket i\rrbracket[k] and ⟦j⟧[k])\llbracket j\rrbracket[k]), we compare the values and produce a Pauli operator for the position.

Compiling data constraints. The compilation of data constraints directly utilizes Equation (2). Given a choice set CC, to mark a specific state as k∈Ck\in C, we model ⟦∣k⟩⟧C(x)\llbracket|k\rangle\rrbracket^{C}(x) in rule C-EU as follows.

⟦j⟧C(x)≜⟦∣k⟩→∣k⟩⟧C(x)\llbracket j\rrbracket^{C}(x) \triangleq\llbracket|k\rangle\to|k\rangle\rrbracket^{C}(x)

Here, we include the data-point location (x)(x) as the target for applying the generated Pauli strings in ⟦∣k⟩→∣k⟩⟧C\llbracket|k\rangle\to|k\rangle\rrbracket^{C}. The end result of compiling a data constraint is a final Hamiltonian HfH_f, as a sum of weighted Pauli operators (single-qubit ZZs, two-qubit Z⊗ZZ \otimes Z interactions, etc., depending on the structure of the data constraints).

The above generate Pauli strings representing non-zero data points, with fit⁡(ε[kˉ/xˉ])\operatorname{fit}(\varepsilon[\bar{k}/\bar{x}]) assigning the energy scores for these data points. The fit⁡\operatorname{fit} function interprets the expression ε\varepsilon by assigning variables to numbers representing data-point locations. Additionally, for generic energy-score constructs (vˉ)(\bar{v}) in ε\varepsilon, we try different real-number assignments (rˉ)(\bar{r}) and minimize the steps using the step⁡g\operatorname{step}^{g} function for estimation. We list the minimization function below.

min⁡n,rstep⁡ng(ψ[rˉ/vˉ](s),θ(s))\min_{n,r}\operatorname{step}^{g}_{n}\bigl(\psi[\bar{r}/\bar{v}](s),\theta(s)\bigr)

Finally, the negative sign in C-EU ensures the correctness for the Hamiltonian-simulation-based AQC compilation.

Compiling relational constraints. We mainly explain ⟦{δˉ}∼1⟧C\llbracket\{\bar{\delta}\}^{\sim1}\rrbracket^{C} here. We first define useful helper functions. For the vector ≠i\ne i, the function rewrites those cases to OO. For an arbitrary input, we can utilize linear sum operations to construct the following operator.

⟦+k⟧C=∑j∈[0,∣C∣−k)⟦∣j⟩→∣j+k⟩⟧C⟦−k⟧C=∑j∈[k,∣C∣)⟦∣j⟩→∣j−k⟩⟧C\llbracket+k\rrbracket^{C}=\sum_{j\in[0,|C|-k)}\llbracket|j\rangle\to|j+k\rangle\rrbracket^{C} \qquad \llbracket-k\rrbracket^{C}=\sum_{j\in[k,|C|)}\llbracket|j\rangle\to|j-k\rangle\rrbracket^{C}

Given a quantum state φ\varphi, the addition and subtraction operations add or subtract kk to a basis vector; e.g., we turn ∣j⟩|j\rangle into ∣j+k⟩|j+k\rangle and ∣j−k⟩|j-k\rangle, respectively. However, we cannot predetermine the specific jj for a quantum state, so we use a linear sum operator to prepare the addition and subtraction operations for all possible j∈[0,∣C∣−k)j\in[0,|C|-k).

The two operations above allow us to move ∣j+k⟩|j+k\rangle and ∣j−k⟩|j-k\rangle for a single data point. Now, we use these operations to define relational constraints. We first define the 0-flagged relational constraint, meaning all data points move in the same direction. Here, we can pick every data-points (δj)(\delta_j) in δˉ\bar{\delta} from the data-point set Dj∈D‾\mathcal{D}_j\in\overline{\mathcal{D}}. We define the constraint as follows, with ∑\sum and ++ denoting linear summation.

⟦{δˉ}∼0⟧C≜∑k∈[0,∣C∣)◯δ∈δˉ⟦+k⟧C(location⁡(δ))+∑k∈[0,∣C∣)◯δ∈δˉ⟦−k⟧C(location⁡(δ))\llbracket\{\bar{\delta}\}^{\sim0}\rrbracket^{C}\triangleq\sum_{k\in[0,|C|)}\bigcirc_{\delta\in\bar{\delta}}\llbracket+k\rrbracket^{C}(\operatorname{location}(\delta))+\sum_{k\in[0,|C|)}\bigcirc_{\delta\in\bar{\delta}}\llbracket-k\rrbracket^{C}(\operatorname{location}(\delta))

The key in the modeling is that we let all single data-points to perform the same addition or subtraction, where ◯δ∈δˉ⟦+k⟧C(δ)\bigcirc_{\delta\in\bar{\delta}}\llbracket+k\rrbracket^{C}(\delta) refers to the sequencing operation, ⟦+k⟧C(δˉ0)∘…∘⟦+k⟧C(δˉ∣δˉ∣−1)\llbracket+k\rrbracket^{C}(\bar{\delta}_0)\circ\ldots\circ\llbracket+k\rrbracket^{C}(\bar{\delta}_{|\bar{\delta}|-1}), and ⟦+k⟧C(δ)\llbracket+k\rrbracket^{C}(\delta) applies the Pauli-string on the qubits in the data-point δ\delta.

The modeling of the 1-flagged ({xˉ}∼1)(\{\bar{x}\}^{\sim1}) constraint is similar to 1-flagged one, but we ensure that every data-point adds or subtracts a different number.

⟦{δˉ}∼1⟧C≜∑k∈Cˉ∖{k∣k=∣δˉ∣}∑jˉ∈Cˉ∖{j∣j=∣δˉ∣}◯k∈δˉ,δˉ⟦compare⁡(k,j)⟧C(δ)\llbracket\{\bar{\delta}\}^{\sim1}\rrbracket^{C}\triangleq\sum_{k\in\bar{C}\setminus\{k\mid k=|\bar{\delta}|\}}\sum_{\bar{j}\in\bar{C}\setminus\{j\mid j=|\bar{\delta}|\}}\bigcirc_{k\in\bar{\delta},\bar{\delta}}\llbracket\operatorname{compare}(k,j)\rrbracket^{C}(\delta)

where

compare⁡(k,j)=+(j−k)if k<jcompare⁡(k,j)=−(k−j)if k>j\operatorname{compare}(k,j)=+(j-k)\quad\text{if }k<j \qquad \operatorname{compare}(k,j)=-(k-j)\quad\text{if }k>j

When we pick the data-points δˉ\bar{\delta}, we find all ∣δˉ∣|\bar{\delta}|-length choice combinations (kˉ∈Cˉ)(\bar{k} \in\bar{C}), where we have (∣Cˉ∣∣δˉ∣)\binom{|\bar{C}|}{|\bar{\delta}|} possible combinations. For each combination, we let each data point (δ)(\delta) add or subtract the value picked at kk.

The modeling of the swap constraint ({xˉ}∼∗)(\{\bar{x}\}^{\sim*}) utilizes a similar combination concept, but we are picking different combinations of permutations; i.e., given data points δˉ\bar{\delta} with the assumption of kˉ∈Cˉ\bar{k} \in\bar{C}, we perform the operations based on the permuted value, as perm⁡(kˉ)\operatorname{perm}(\bar{k}). The modeling is listed below.

⟦{δˉ}∼∗⟧Cˉ≔∑kˉ∈Cˉ∧∣kˉ∣=∣δˉ∣∑j∈perm⁡(kˉ)◯k∈kˉ,j∈jˉ,δ∈δˉ⟦compare⁡(k,j)⟧C(δ)\llbracket\{\bar{\delta}\}^{\sim*}\rrbracket^{\bar{C}} \coloneqq\sum_{\bar{k}\in\bar{C}\land|\bar{k}|=|\bar{\delta}|}\sum_{j\in\operatorname{perm}(\bar{k})}\bigcirc_{k\in\bar{k},j\in\bar{j},\delta\in\bar{\delta}}\llbracket\operatorname{compare}(k,j)\rrbracket^{C}(\delta)

For example, when dealing with the clique-finding problem, to handle the constraint {x,y}∼∗\{x,y\}^{\sim*}, we need to consider permutations of two data points, e.g., uu and vv. Since the choice set is binary, we can write the constraint as follows.

⟦+1⟧(u)∘⟦−1⟧(v)+⟦−1⟧(u)∘⟦+1⟧(v)\llbracket+1\rrbracket(u)\circ\llbracket-1\rrbracket(v)+\llbracket-1\rrbracket(u)\circ\llbracket+1\rrbracket(v)

Compiling the Adiabatic Process to Quantum Circuits and the Theory

After generating the Pauli-string forms for HiH_i and HfH_f, we apply the standard approximation method for AQC in § 2, which compiles the AQC process to a sequence of Hamiltonian simulation operations, each computing e−iH^(s)te^{-i\hat{H}(s)t} with H^(s)=(1−s)Hi+sHf\hat{H}(s)=(1-s)H_i+sH_f. We compile a single Hamiltonian simulation into a quantum circuit using the optimal Trotterization method [54]. We give the detailed circuit compilation in Section A. Below is the compilation correctness theorem.

Theorem 4.1 (Compilation Correctness). Given Φ\Phi, PP, and a desired error rr, with data-constraint eUe_U and relational constraint eSe_S, we compile them as dom⁡(P)⊢Φ≫φ\operatorname{dom}(P)\vdash\Phi\gg\varphi, Γ⊢eS:S▹H^i\Gamma\vdash e_S:S\triangleright\hat{H}_i, Γ⊢eU:S▹H^f\Gamma\vdash e_U:S\triangleright\hat{H}_f, and the AQC compilation as AQC⁡r(H^i,H^f)\operatorname{AQC}_r(\hat{H}_i,\hat{H}_f). The result is bounded by rr, compared against to PP’s dynamic semantics, as ∥AQC⁡r(H^i,H^f)(φ)−⟦P⟧∥<r\lVert\operatorname{AQC}_r(\hat{H}_i,\hat{H}_f)(\varphi)-\llbracket P\rrbracket\lVert<r.

Proof. The proof has two stages. First, we show that the compilation in Figure 8 generates Pauli-string formulas with the same semantics as the EnQ+ constraint semantics in § 3.3. The proof is via induction on the compilation rules in Figure 8. Next, we show that AQC evolution via Hamiltonian simulation yields a unitary circuit that differs from the EnQ+ dynamic semantics in Theorem 3.8 within a given bound. We utilize the compilation proof result in Theorem 5.8 of the QBlue compiler [54].

Discussion: An Issue in the AQC Compilation

To ensure compiler correctness, we must ensure that energy loss values in every EnQ+ program are positive, while the data-constraint compilation (rule C-EU) in Figure 8 is applied. Without the signs being added, the stepg^{g} function becomes monotonic decreasing within the bounded steps (⌈1λ⌉)(\lceil\frac{1}{\lambda}\rceil). This fact is established in the proof of compilation correctness.

Because few studies have examined dynamic semantics and certified compilers, many previous works either made mistakes in their programs or did not explain why they performed such sign manipulation. Boros et al. [11, 12] did not add negative signs because they focused on developing the general concept of AQC without specifying how an AQC procedure can be compiled to quantum computers.

In Farhi et al. [29], one example, 2-SAT on a Ring, has the sign issue, as shown below.

H^(s)=(1−s)∑j(I−X(j))+s∑j(I−Z(j)Z(j+1))\hat{H}(s)=(1-s)\sum_j(I-X(j))+s\sum_j(I-Z(j)Z(j+1))

Note that the identity operators II have no effect in compilation, so this means that we have negative signs in both the initial (∑j−1⋅X(j)\sum_j -1 \cdot X^{(j)}) and final (∑j−1⋅Z(j)Z(j+1)\sum_j -1 \cdot Z^{(j)}Z^{(j+1)}) Hamiltonians. This setting might work for the specific example, but it fails when we try to compile the problem for quantum computers via Hamiltonian-simulation-based compilation.

H^′(s)=∑j,k−rj,k⋅Z(j)Z(k)+∑j−rb⋅Xj\hat{H}'(s)=\sum_{j,k}-r_{j,k}\cdot Z^{(j)}Z^{(k)}+\sum_j-r_b\cdot X_j

The work of Kadowaki and Nishimori [48] and Brooke et al. [13] develops the AQC procedure based on the classical Ising model in physics, shown above. In the model, rbr_b is typically negative, while a ferromagnetic model, with positive rj,kr_{j,k}, might be better for implementing the system on a quantum computer. However, this description is restricted to the Ising model and assumes readers have deep knowledge of physics. The work is also experimental for several benchmark tests, without a firm conclusion on why the signs might affect the correctness guarantee.

In industry, the Qiskit tutorial [19] provides a programming pattern for negating the signs of the final Hamiltonian without explaining why users need such sign flips.

Discovering the sign issue highlights the value of developing EnQ+ dynamic semantics and a certified compiler.

Case Study: Three-Dimensional Matching Problem

In this section, we show case studies of EnQ+, which has a Haskell implementation. We show example programs below for solving some NP problems, and there are Haskell programs listed in Section C.

Given three finite sets XX, YY, and ZZ, the three-dimensional matching problem is to find a subset M⊆X×Y×ZM \subseteq X \times Y \times Z such that no two triples in MM share an element. For simplicity, we assume there is a number nn such that MM selects nn elements from each of the sets XX, YY, and ZZ. Additionally, we add an equational constraint across the three different sets, as follows.

∀(x,y,z)∈M⇒x%m=y%m=z%m\forall(x,y,z) \in M \Rightarrow x \mathbin{\%} m = y \mathbin{\%} m = z \mathbin{\%} m

To program the problem in EnQ+, we assume a data structure with three sets DxD_x, DyD_y, and DzD_z; each element in the sets has a data field containing the element value and a choice field as a pair (ζ1,ζ2)(\zeta_1,\zeta_2). The first element is a Boolean value {Yes,No}\{\mathrm{Yes},\mathrm{No}\}, implementable as a single qubit, indicating whether an element is included in the set MM. The second element is a ll qubit value, representing the remainder x%mx \mathbin{\%} m, y%my \mathbin{\%} m, and z%mz \mathbin{\%} m.

We first model the relational constraint, as follows.

eS=(∂(x,y)∈Dx.∂(u,v)∈Dx.{x,u}∼∗)+(∂(x,y)∈Dy.∂(u,v)∈Dy.{x,u}∼∗)+(∂(x,y)∈Dz.∂(u,v)∈Dz.{x,u}∼∗)+(∂(x,y)∈Dx.∂(u,v)∈Dy.{x,v,t}∼0)\begin{aligned} e_S={}&(\partial(x,y)\in D_x.\partial(u,v)\in D_x.\{x,u\}^{\sim*})\\ &+(\partial(x,y)\in D_y.\partial(u,v)\in D_y.\{x,u\}^{\sim*})\\ &+(\partial(x,y)\in D_z.\partial(u,v)\in D_z.\{x,u\}^{\sim*})\\ &+(\partial(x,y)\in D_x.\partial(u,v)\in D_y.\{x,v,t\}^{\sim0}) \end{aligned}

In the above relational constraint, the first three lines define the swap constraint for the first pair of elements in the sets DxD_x, DyD_y, and DzD_z, where each of them constrains a MWC subgraph, similar to Figure 3. The last line is a 0-flagged constraint on the second pair of elements. For every element ((x,y),(u,v),(s,t))∈(Dx,Dy,Dz)((x,y),(u,v),(s,t)) \in(D_x,D_y,D_z), we constrain on the elements, yy, vv, uu, and tt, to ensure that they move in the same direction. For example, if m=4m=4, the three elements form the superposition state as follows.

12(∣0⟩∣0⟩∣0⟩+∣1⟩∣1⟩∣1⟩+∣2⟩∣2⟩∣2⟩+∣3⟩∣3⟩∣3⟩)\frac{1}{2}(|0\rangle|0\rangle|0\rangle+|1\rangle|1\rangle|1\rangle+|2\rangle|2\rangle|2\rangle+|3\rangle|3\rangle|3\rangle)

To prepare the initial state, we first prepare three Dicke states, as described in § 2, on an MWC graph similar to Figure 3. The three states are for DxD_x, DyD_y, and DzD_z, respectively. We then compose the three MWC subgraphs; for each element with the same id in the three subgraphs, we combine the three configurations. We then prepare the 0-flagged state for each of the three elements in the three sets, and we join the above Dicke state with the 0-flagged state.

eU=(∂(x,y)∈Dx.∂(u,v)∈Dx.if choice(x)=choice(u)=Yes∧data(x)=data(u) then L else O)+(∂(x,y)∈Dy.∂(u,v)∈Dy.if choice(x)=choice(u)=Yes∧data(x)=data(u) then L else O)+(∂(x,y)∈Dz.∂(u,v)∈Dz.if choice(x)=choice(u)=Yes∧data(x)=data(u) then L else O)+(∂(x,y)∈Dx.if data(x)%m≠choice(y) then L else O)+(∂(x,y)∈Dy.if data(x)%m≠choice(y) then L else O)+(∂(x,y)∈Dz.if data(x)%m≠choice(y) then L else O)\begin{aligned} e_U ={}& (\partial(x,y) \in D_x . \partial(u,v) \in D_x . \text{if choice}(x) = \text{choice}(u) = \text{Yes} \land\text{data}(x) = \text{data}(u) \text{ then L else O}) \\ &+(\partial(x,y) \in D_y . \partial(u,v) \in D_y . \text{if choice}(x) = \text{choice}(u) = \text{Yes} \land\text{data}(x) = \text{data}(u) \text{ then L else O}) \\ &+(\partial(x,y) \in D_z . \partial(u,v) \in D_z . \text{if choice}(x) = \text{choice}(u) = \text{Yes} \land\text{data}(x) = \text{data}(u) \text{ then L else O}) \\ &+(\partial(x,y) \in D_x . \text{if data}(x) \mathbin{\%} m \ne\text{choice}(y) \text{ then L else O}) \\ &+(\partial(x,y) \in D_y . \text{if data}(x) \mathbin{\%} m \ne\text{choice}(y) \text{ then L else O}) \\ &+(\partial(x,y) \in D_z . \text{if data}(x) \mathbin{\%} m \ne\text{choice}(y) \text{ then L else O}) \end{aligned}

Finally, we model the data constraint above using the generic energy values L and O mentioned in § 2. In eUe_U, the first three lines constrain that if two elements from the three sets are included in MM and share the same data, we incur an energy loss L; otherwise, there is no loss. The last three lines constrain the data values in the elements to satisfy the modular equation above, and we apply an energy penalty L if they do not.

With the above modeling for the data structure, choice set, initial state, data constraint, and relational constraint, we utilize the EnQ+ compiler in Haskell to compile the program to produce an SQIR circuit [43], and we successfully execute the program for the setting of m=2m = 2 and each set containing 2 elements, via an effective simulator [55]. More case studies with Haskell programs are given in Section C.

Related Work

We provide related work studies for AQC and quantum computation here.

AQC. The concept of quantum computation based on the adiabatic procedure, as proposed by Farhi et al. [29], and related ideas were suggested by Kadowaki and Nishimori [48] and Brooke et al. [13]. A closely related concept is quantum annealing, a physical process that implements AQC algorithms, first proposed by Chakrabarti [14], with many subsequent developments [13, 30, 48, 67, 82]. It incorporates algorithms and hardware designed to solve computational problems via quantum evolution towards the ground states of final Hamiltonians that encode classical optimization problems, without necessarily insisting on universality or adiabaticity.

Many NP-complete problems are framed in terms of the Ising model [8], a physical and mathematical model of ferromagnetism in statistical mechanics. The idea is to frame NP-complete problems as constraint-programming problems using the Ising model and solve them in AQC or via quantum annealing [22, 28]. Many previous AQC-related works have been proposed to solve NP-complete problems [6, 16, 17, 32, 49] by framing them as Ising models. Lucas [59] provides a good overview of framing different NP-problems in the Ising model. Our clique finding algorithm is more similar to the algorithm in Wu [81]. Note that the Ising model-framed AQC problems often go by the name QUBO (quadratic unconstrained binary optimization) in much of the mathematical literature [11, 12]. QUBO is a mathematical formalism for solving combinatorial optimization problems [50]. QUBO is closely related to Ising model-based ECC problems. D-Wave [44] is a quantum computer provider that mainly uses quantum annealing to solve AQC problems with Ising-model-based Hamiltonian programs. EnQ [56] develops a quantum library, demonstrating how to specify Hamiltonians as data constraints that can be compiled to quantum computers.

Compared to prior work, EnQ+\mathrm{EnQ}^{+} introduces an MWC graph view of quantum states, enabling users to develop high-level programs with arbitrary data structures. EnQ+\mathrm{EnQ}^{+} lets users define relational constraints to specify initial Hamiltonians, and develops constraint and dynamic semantics to classify the AQC procedure. With the development of dynamic semantics, EnQ+\mathrm{EnQ}^{+} produces a certified compiler for compiling AQC problems to quantum computers, supported by theorems such as the good approximation theorem.

Hamiltonian-Simulation-Based Quantum Computation. There are a few quantum computation prototypes allowing users to define Hamiltonians based on Pauli groups (XX, YY, and ZZ), then they are able to compile the simulation of the Hamiltonians with respect to time to quantum computers. These works include IBM Qiskit Nature [20], QuEra Bloqade [1], OpenFermion [60], InQuanto [45], SimuQ [63], and Pasqal Pulser [71] developed by hardware service providers. QuTip [47], supporting Hamiltonian simulation in a classical computer. These works are inspired by many classical analog compilations [2, 3]. Li et al. [54] develops a certified compiler for Hamiltonian simulation based on the Pauli-string formalism. Most of these works support scientific computation in physics, chemistry, and biology. The EnQ+\mathrm{EnQ}^{+} circuit compilation step follows Li et al. [54].

Quantum Circuit-based Programming Languages. Quantum circuit-based language developments are focal. Q# [75], Quilc [72], ScaffCC [46], ProjectQ [74], Cirq [23], Qiskit [5] are industrial quantum circuit languages, without formal semantics, but based on a standardized denotational quantum circuit semantics. There are formally verifying quantum circuit programs, including Qwire [65], SQIR [42], and QBricks [15], quantum Hoare logic and its subsequent works [58, 83, 85], Qafny [57]. These tools have been used to verify a range of quantum algorithms, from Grover’s search to quantum phase estimation. There are works verifying quantum circuit optimizations (e.g., voqc [43], CertiQ [70]), as well as verifying quantum circuit compilation procedures, including ReVerC [7] and ReQWIRE [66].

There are functional language interpretations for quantum circuits [25, 31, 34, 35, 36, 38, 68, 69, 76, 77, 78, 84], with formal semantics. These languages mainly encode quantum circuits as functional language constructs, such as quantum pattern matching. Silq [10] proposed a language for automatic uncomputation, with denotational semantics to describe circuit behavior. ZX-calculus [18, 79] turns elements appearing in quantum semantics into a diagram calculus for expressing unitary operations without measurement.

Conclusion

We present EnQ+\mathrm{EnQ}^{+}, a programming language and certified compiler for describing AQC problems. Most AQC problems are classical NP and P problems, such as clique finding, Hamiltonian cycle, and three-dimensional matching. Instead of low-level programming, EnQ+\mathrm{EnQ}^{+} supports high-level program descriptions based on classical constraint programming. To help users better understand AQC problems, we develop an MWC graph-based constraint and dynamic semantics for EnQ+\mathrm{EnQ}^{+} programs and use them to certify compilation from an EnQ+\mathrm{EnQ}^{+} program to quantum computers. While verifying the compiler, we discover a long-standing issue in Hamiltonian simulation-based AQC compilation and provide a correctness guarantee. The good approximation theorem examines what happens when users plug in an initial state that is not an eigenstate of the relational constraint in a program.

For future work, we plan to develop software toolchains based on EnQ+\mathrm{EnQ}^{+} and explore other compilations, including classical-quantum hybrid compilation, such as QAOA [27].

Data-Availability Statement

The software mentioned in Sections C and 5 is available at https://doi.org/10.5281/zenodo.24137515. The artifact is produced in the described experimental setting.

References

Compiling Hamiltonian Simulation via Trotterization

Performing Adiabatic Evolution. Once we have HiH_i and HfH_f, we leverage AQC to find the optimum. The principle of AQC is to slowly interpolate between HiH_i and HfH_f over time, adiabatically guiding the quantum state from the known easy ground state to the unknown solution state. § 2 introduces AQC, and we examine the intuition of performing AQC for EnQ+ programs.

We conceptually define a time-dependent Hamiltonian H(s)H(s) that evolves from H(0)=HiH(0) = H_i to H(1)=HfH(1) = H_f as a function of a normalized time parameter s∈[0,1]s \in[0,1]. For example, a linear schedule would use H(s)=(1−s)Hi+sHfH(s) = (1-s)H_i+sH_f. Initially (s=0s = 0), the system is in the ground state of HiH_i (the uniform superposition). As ss increases, the Hamiltonian gradually incorporates the problem constraints. If the change is slow enough, the quantum adiabatic theorem guarantees that the state of the system will remain in the instantaneous ground state of H(s)H(s). By the end (s=1s = 1), the system will be in the ground state of HfH_f, which is exactly the state encoding the optimal solution of our problem.

In practice, this continuous adiabatic evolution is realized through a sequence of many small discrete steps. Each step applies a slight alteration to the Hamiltonian and consequently a quantum operation on the state. Eventually, after the full schedule, the system’s state ideally encodes the solution in its qubit amplitudes. Finally, we measure the qubits in the computational basis. With high probability (if the adiabatic process succeeded and if decoherence and other errors are minimal), the measurement will collapse the system into the basis state corresponding to the lowest energy, i.e., the optimal solution.

Adiabatic evolution replaces the explicit search or brute-force classical process with a physical process. As the Hamiltonian changes, the quantum state naturally “searches” the landscape of possibilities by continuously adjusting the amplitudes of basis states, concentrating more weight on low-energy (better) solutions. By the end, the amplitude is ideally concentrated on the optimal solution. This is analogous to a landscape where the system begins as a liquid spread out over all valleys and then slowly freezes into the lowest valley (the global minimum) due to the energy bias introduced by HfH_f. The power of this approach is that it exploits quantum parallelism and tunneling: the state can explore many solutions concurrently and avoid getting stuck in local minima under the right conditions, potentially outperforming certain classical algorithms on hard problems.

Compiling the Adiabatic Process to Quantum Circuits. Given H(s)H(s) expressed as a sum of basic operators, the next step is to turn the continuous evolution e−iH(s)Δte^{-iH(s)\Delta t} into a sequence of gates. EnQ+ uses a Trotter-Suzuki decomposition to approximate the exponential of a sum of operators. In brief, if H=A+BH = A+B (where AA and BB are operators that act on possibly different sets of qubits), we can approximate e−i(A+B)Δt≈e−iAΔte−iBΔte^{-i(A+B)\Delta t} \approx e^{-iA\Delta t}e^{-iB\Delta t} for a small time slice Δt\Delta t, with the error of order O((Δt)2)O((\Delta t)^2). By splitting the total evolution time TT into mm small slices (Δt=T/m\Delta t = T/m) and alternating the application of e−iAΔte^{-iA\Delta t} and e−iBΔte^{-iB\Delta t}, the accumulated error becomes negligible for large mm. This idea generalizes to more than two terms using Suzuki’s higher-order formulas, but the principle remains: we trade a continuous time evolution for a sequence of short gate operations corresponding to each term in the Hamiltonian.

The EnQ+ Trotterization step is implemented based on the MuQ compiler [54]. We provide an example here for the following simple Ising model and present its Trotterized results.

H^I1=∑jrjX(j)+∑jZ(j)⊗Z(j+1)(3)\hat{H}_{I1} = \sum_j r_j X(j) + \sum_j Z(j) \otimes Z(j+1) \tag*{(3)}

We approximate exp⁡(−irH^)\exp(-i r \hat{H}) by setting ∏k=0N−1Uk(d,λ,N,r)\prod_{k=0}^{N-1} U_k(d,\lambda,N,r) to be ∏k=0N−1Πmexp⁡(−irmθjP^j)\prod_{k=0}^{N-1}\Pi^{m}\exp(-i\frac{r}{m}\theta_j\hat{P}_j), i.e., for each Pauli string θjP^j\theta_j\hat{P}_j, we construct an application sequence Πmexp⁡(−irmθjP^j)\Pi^{m}\exp(-i\frac{r}{m}\theta_j\hat{P}_j), where we repeat the simulation of θjP^j\theta_j\hat{P}_j for mm times with a scaled time slot rm\frac{r}{m}. Each Uk(d,λ,N,r)U_k(d,\lambda,N,r) is defined as

exp⁡(−irmθjP^j)\exp(-i\frac{r}{m}\theta_j\hat{P}_j) with N=d∗mN=d*m and λ=m\lambda=m. For example, to simulate the Pauli-string-based Hamiltonian H^I1\hat{H}_{I_1} with a time slot rr and splitting number mm, we compute the approximation of the exponent exp⁡(−irH^I1)\exp(-ir\hat{H}_{I_1}) as follows.

exp⁡(−irH^I1)=∏mλ(exp⁡(−irm(∑jZ(j)Z(j+1)+rh∑jX(j))))=∏mλ(exp⁡(−irmZ(0)Z(1))exp⁡(−irmZ(1)Z(2))⋯exp⁡(−irmrhX(0))exp⁡(−irmrhX(1))⋯ )\exp(-ir\hat{H}_{I_1})=\prod_{m}^{\lambda}\left(\exp\left(-i\frac{r}{m}\left(\sum_j Z^{(j)}Z^{(j+1)}+r h\sum_j X^{(j)}\right)\right)\right) =\prod_{m}^{\lambda}\left(\exp\left(-i\frac{r}{m}Z^{(0)}Z^{(1)}\right)\exp\left(-i\frac{r}{m}Z^{(1)}Z^{(2)}\right)\cdots\exp\left(-i\frac{r}{m}rhX^{(0)}\right)\exp\left(-i\frac{r}{m}rhX^{(1)}\right)\cdots\right)

Synthesization applies the application sequence of matrix exponentials of Pauli strings generated from Trotterization to quantum circuits, either digital or analog. In synthesizing an application sequence ∏jexp⁡(−iθjP^j)\prod_j\exp(-i\theta_j\hat{P}_j), it is enough to describe the synthesization of a single matrix exponential term exp⁡(−iθjP^j)\exp(-i\theta_j\hat{P}_j). We discuss the digital and analog-based synthesization below.

We synthesize the simulation of a Pauli string, exp⁡(−iθjP^j)\exp(-i\theta_j\hat{P}_j), to elementary quantum gates, e.g., single-qubit gates, such as H, Rz, Ry, and Rx gates, as well as two qubit controlled-not gate CX (CX(x,yx,y) controlling on xx and applying X gate on yy).

The procedure focuses on the non-II terms in a Pauli string P^=⨂j=0n−1Pj\hat{P}=\bigotimes_{j=0}^{n-1}P_j. If P^\hat{P} has only one non-II term, the compilation generates a rotation gate, listed in Figure 9. In the Bloch qubit sphere interpretation [61], the rotation gate Rx, Ry, Rz can be expressed as some Hamiltonian simulations of Pauli matrices (Rz(2θ2\theta)(jj) applies a ZZ-axis rotation in the jj-th qubit), which essentially suggests that the simulation of singleton Pauli X, Y, and Z terms are the above phase rotation gates. For example, the gate synthesis of exp⁡(−irnX(j))\exp(-i\frac{r}{n}X(j)) generates an Rx gate, as Rx(2rn\frac{2r}{n})(jj). We describe the algorithm in Figure 9 for a Pauli string with more than one non-II term, i.e., a kk-local Pauli string with k>1k>1.

Figure 9. Pauli matrices simulated to rotation gates. exp⁡(−iθP)\exp(-i\theta P) can be thought as simulating PP on time θ\theta.

We first show the gate synthesization of the simple Ising model H^I1\hat{H}_{I_1} in Equation (3), which produces a sequence of exp⁡(−irnZ(j)∘Z(j+1))\exp(-i\frac{r}{n}Z(j)\circ Z(j+1)) and exp⁡(−irnrhX(j))\exp(-i\frac{r}{n}rhX(j)) operations (the sequence length is related to nn). If nn is large enough, the operation sequence is a good approximation to exp⁡(−irH^I1)\exp(-ir\hat{H}_{I_1}). The exp⁡(−irnrhX(j))\exp(-i\frac{r}{n}rhX(j)) operation produces a Rx gate [61], while exp⁡(−irnZ(j)∘Z(j+1))\exp(-i\frac{r}{n}Z(j)\circ Z(j+1)) produces a digital circuit as the left in Figure 10, performing two controlled-not gates and an Rz(2rn\frac{2r}{n}) gate in the middle for the jj-th and j+1j+1-th qubits, i.e., Rz(2θ2\theta) is an zz-axis phase rotation gate.

Circuit and unitary for ZZ interaction

Figure 10. Circuit and unitary for ZZZZ Interaction. The left circuit applies on jj and j+1j+1 qubits.

We show an example of a long Pauli string synthesization in Figure 11. After applying Trotterization on the H^\hat{H}, we generate a sequence of Hamiltonian simulations of Pauli strings. Some possible Pauli string terms might be 4-local, as Z⊗Z⊗Z⊗ZZ \otimes Z \otimes Z \otimes Z (abbreviated as ZZZZZZZZ), X⊗X⊗X⊗XX \otimes X \otimes X \otimes X (abbreviated as XXXXXXXX) and X⊗X⊗Y⊗YX \otimes X \otimes Y \otimes Y (abbreviated as XXYYXXYY). The simulation of the ZZZZZZZZ term results in a quadruple ZZ interaction in Figure 11a, containing a ZZZZ interaction application in the middle, shown in Figure 10, with the surrounding of controlled-not gates. The digital gate synthesization of exp⁡(−iθXXXX)\exp(-i\theta XXXX) and exp⁡(−iθXXYY)\exp(-i\theta XXYY) is based on the quadruple ZZ interaction with repairs for XX and YY conversion, which results in the circuits in Figure 11b and Figure 11c.

Synthesized circuits for some long Pauli strings

Figure 11. Synthesized circuits for some long Pauli strings.

Relational Constraints in Physics

Relational constraints in the programming context express a familiar physical idea: restricting evolution to a chosen subspace by allowing only transitions that preserve it. In quantum annealing, these transitions define a driver Hamiltonian; in gate-based optimization, they define a mixer. When the constraints fix the value of a conserved quantity, the subspace is a symmetry sector. Table 2 summarizes these connections. This appendix reviews the physical foundations of relational constraints, the guarantees and limitations of existing constructions, and the tasks they leave to the programmer.

EnQ+Physics
cost function; its minimumHamiltonian; ground state
data constraint H^f\hat{H}_fproblem Hamiltonian; phase separator (QAOA)
relational constraint H^i\hat{H}_idriver Hamiltonian (annealing); mixer (QAOA)
quantity a relational constraint preservesconserved quantity; symmetry
candidates (nodes of the MWC graph)symmetry sector; feasible subspace
swap of a chosen and an unchosen vertexXY exchange; hard-core boson hopping; Kawasaki move
uniform start over the kk-subsetsDicke state
penalty (k−∑vxv)2(k-\sum_v x_v)^2energy penalty; grand-canonical control of particle number

Table 2. EnQ+ terms and their names in physics.

Conservation laws. When the Hamiltonian commutes with an observable throughout the evolution, it preserves each eigenspace of that observable. In our clique example, the conserved observable is particle number: each vertex is represented by a mode that is either empty or occupied, and selecting exactly kk vertices corresponds to the kk-particle subspace. This restriction to at most one particle per mode occurs for hard-core bosons, fermions, and hard-core anyons, although their exchange statistics differ [73]. Our relational swap corresponds to hard-core boson hopping, θ=2π\theta= 2\pi: it transfers a particle from an occupied mode to an empty one while preserving the total particle number. For nn such modes, the Hilbert space decomposes into fixed-particle-number sectors:

H=⨁k=0nHk,Hk=ker⁡(N^−kI),N^=∑v=1n∣1⟩⟨1∣v.\mathcal{H} = \bigoplus_{k=0}^{n} \mathcal{H}_k,\qquad\mathcal{H}_k = \ker(\hat{N}-kI),\qquad\hat{N} = \sum_{v=1}^{n} |1\rangle\langle1|_v.

Here N^\hat{N} counts occupied modes, and Hk\mathcal{H}_k is the subspace with exactly kk particles. An example of particle-number-preserving hopping appears in the resonant impurity scattering simulation reported by Ortiz et al. [62]. Conservation can be used to reduce the simulation space: Graves [37] restricts an anyonic Aharonov–Bohm Hamiltonian to fixed-particle-number subspaces while retaining their exact dynamics. In EnQ+, the diagonal data Hamiltonian also preserves particle number, so evolution initialized in the kk-particle subspace remains there. The Dicke state [24] used by the program is the uniform superposition of all occupation patterns with exactly kk particles. This enforces cardinality through conservation, whereas an energy penalty makes violations costly without itself forbidding transitions into them. The same principle gives invariant subspaces in spin systems: the zero-field Ising transfer matrix commutes with global spin reversal and therefore preserves sectors of even and odd spin-reversal parity [9].

Constraint-preserving drivers and mixers. Childs et al. [16] searched for cliques exactly this way. Their initial cost function summed swaps over all pairs of vertices, so the run stayed among the subsets of the target size, and it began in the uniform superposition of those subsets: the program of this section. Hen and Spedalieri [41] turned the construction into a general method, constrained quantum annealing. Later work expanded constraints [40, 51] and general linear equalities [52, 53]. QAOA mixers provide a gate-based counterpart to constraint-preserving drivers. In the quantum alternating operator ansatz [39], mixer unitaries preserve the feasible subspace, while cost unitaries encode the optimization objective. This parallels EnQ+’s separation of relational from data constraints. For example, XY mixers preserve Hamming weight and can therefore enforce one-hot and cardinality constraints [80]. The original EnQ implementation used a QAOA style mixer in its gate based circuit backend [56].

Additional Case Studies

In this section, we show three case studies for the utility of EnQ+.

The Compilation Pipeline of Hamiltonian Cycle

The Hamiltonian Cycle problem involves finding a closed loop through a given graph G=(V,E)G = (V, E) that visits every vertex exactly once. Formulating Hamiltonian Cycle within our Energy Constraint Computation (ECC) framework requires a careful encoding of both the vertex permutation and the graph’s adjacency constraints.

As shown in Figure 12, we model the cycle using a rank-based positional encoding. For a graph with NN vertices, the struct defines the set of vertices (cities), and the available choices correspond to the ranks 0 through N−1N - 1. The constraints function then evaluates whether an edge exists between the chosen vertex at rank ii and the vertex at rank i+1i + 1. If (vi,vi+1)∉E(v_i, v_{i+1}) \notin E, an energy penalty is applied. To ensure the path forms a closed loop, the constraints function also wraps around to evaluate the adjacency between the final step and the first step.

Figure 12. The Hamiltonian Cycle implementation in EnQ+

The data constraints define the problem’s energy landscape. By setting view to 2, the compiler evaluates pairwise relationships between the cities. For a given pair (cityA, rankA) and (cityB, rankB), the function calculates the absolute difference in their assigned ranks. We evaluate our compilation using a 4-node cycle graph (C4C_4), where V={0,1,2,3}V = \{0, 1, 2, 3\} and the valid edges form the perimeter of a square. If the difference is exactly 1, or 3 (enforcing the wrap-around condition to close the 4-step loop), the cities are deemed adjacent in the sequence. If these adjacent cities do not share a valid edge in the underlying graph, that is, if the sequence attempts to traverse the missing diagonal edges (0, 2) or (1, 3), a connectivity penalty of 50 is applied.

Relational Constraints: The Initial Hamiltonian

Relational Constraints: The Initial Hamiltonian. To avoid exploring a massive subspace of invalid configurations (e.g., assigning the same rank to multiple cities), EnQ+ restricts the Many-World Configuration (MWC) graph to search only over valid permutations. This is achieved by initializing the system in a valid permutation state and driving the evolution with a relational constraint that strictly enforces rank-swapping between nodes. As established in § 4.2, the compilation of the relational swap constraint (x~∗\tilde{x}^{*}) into a quantum circuit proceeds in two phases.

hamiltonianCycle :: [(Int, Int)] -> Program [] Int Int Int
hamiltonianCycle edges =
  let
    cities = getNodes edges
    numNodes = length cities
  in
    Program
      { dataProgram = DataProgram
          { choices = [0 .. numNodes-1]
          , struct = cities
          , view = 2
          , constraints = \case
              [(cityA, rankA), (cityB, rankB)] ->
                let
                  diff = abs (rankA - rankB)
                  isAdjacentRank = diff == 1 || diff == (numNodes - 1)

                  connectivityPenalty =
                    if isAdjacentRank
                    then if (cityA, cityB) `elem` edges || (cityB, cityA) `elem` edges
                         then 0
                         else 50
                    else 0
                in connectivityPenalty
              _ -> error "hamiltonianCycle: Expected exactly two choices"
          , choiceLayout = FlatEncoding
          }
      , relationalProgram = [mkRel Swap 2 ((-1.0) :+ 0.0)]
      , initialState = Permutation
      }

Implementing Addition and Subtraction Operators. The compiler first constructs the raising operators ⟦+k⟧C\llbracket+k\rrbracket^{C} and lowering operators ⟦−k⟧C\llbracket-k\rrbracket_{C} over the binary representations of the sequence ranks. For our four ranks, C={0,1,2,3}C = \{0, 1, 2, 3\}, each rank is encoded using two qubits as ∣00⟩\lvert00\rangle, ∣01⟩\lvert01\rangle, ∣10⟩\lvert10\rangle, and ∣11⟩\lvert11\rangle.

Suppose the evolution requires shifting a rank by +2+2. The corresponding raising operator induces the following state transitions:

∣00⟩→⟦+2⟧C∣10⟩,\lvert00\rangle\xrightarrow{\llbracket+2\rrbracket^{C}} \lvert10\rangle,
∣01⟩→⟦+2⟧C∣11⟩,\lvert01\rangle\xrightarrow{\llbracket+2\rrbracket^{C}} \lvert11\rangle,
∣10⟩, ∣11⟩→⟦+2⟧C0,\lvert10\rangle,\ \lvert11\rangle\xrightarrow{\llbracket+2\rrbracket^{C}} 0,

where the latter two states are annihilated because they cannot be shifted by two within the valid rank space.

At the Pauli level, the transition ∣00⟩→∣10⟩|00\rangle\to|10\rangle requires applying the creation operator a†=12(X−iY)a^\dagger= \frac{1}{2}(X-iY) to the first qubit while projecting the second qubit onto ∣0⟩⟨0∣=12(I+Z)|0\rangle\langle0| = \frac{1}{2}(I+Z). The resulting tensor-product representation is:

12(X−iY)⊗12(I+Z)\frac{1}{2}(X-iY) \otimes\frac{1}{2}(I+Z)

Similarly, the transition ∣01⟩→∣11⟩|01\rangle\to|11\rangle keeps the second qubit in the ∣1⟩|1\rangle state by applying the projector ∣1⟩⟨1∣=12(I−Z)|1\rangle\langle1| = \frac{1}{2}(I-Z) giving:

12(X−iY)⊗12(I−Z)\frac{1}{2}(X-iY) \otimes\frac{1}{2}(I-Z)

Therefore, the complete raising operator ⟦+2⟧C\llbracket+2\rrbracket^{C} over the rank subspace is obtained by summing the two transitions:

⟦+2⟧C=(12(X−iY)⊗12(I+Z))+(12(X−iY)⊗12(I−Z))\llbracket+2\rrbracket^{C} = \left(\frac{1}{2}(X-iY) \otimes\frac{1}{2}(I+Z)\right) + \left(\frac{1}{2}(X-iY) \otimes\frac{1}{2}(I-Z)\right)

Implementing the Relational Swap. With these base operators constructed, EnQ{sup}+ pre-generates the valid permutation set and examines the relations required to implement swaps for each transition in the Many-World Configuration (MWC) graph. For example, consider our C4C_4 graph again. If city 0 currently holds rank 0 (∣00⟩|00\rangle) and city 2 holds rank 2 (∣10⟩|10\rangle), swapping their sequence assignments requires applying a +2 shift to city 0 and a −2 shift to city 2. The compiler therefore constructs the joint transition:

⟦−2⟧(city 2)∘⟦+2⟧(city 0).\llbracket-2\rrbracket(\text{city 2}) \circ\llbracket+2\rrbracket(\text{city 0}).

Likewise, the reverse transition is represented by

⟦−2⟧(city 0)∘⟦+2⟧(city 2).\llbracket-2\rrbracket(\text{city 0}) \circ\llbracket+2\rrbracket(\text{city 2}).

By pre-generating the valid permutation set and applying the generalized compare summations described in § 4.2 across all node pairs, EnQ{sup}+ constructs the complete initial Hamiltonian (HiH_i). This guarantees that the initial Hamiltonian rigorously preserves the permutation subspace without leaking amplitude into invalid configurations. As the adiabatic evolution proceeds, the system explores only the valid paths defined by the edges of the MWC graph, significantly accelerating convergence toward the optimal Hamiltonian cycle encoded by the data constraints.

C.1.2 Execution and Evolution. Execution begins by initializing the quantum register into the permutation subspace using a Quantum Fisher–Yates Shuffle, which prepares an equal superposition over the 24 valid permutations of our C4C_4 graph. Driven by the relational constraints, the Trotterized adiabatic evolution swaps ranks between cities while strictly traversing the valid edges of the MWC graph. This strict confinement allows the system to effectively steer the quantum state toward the optimal Hamiltonian cycle.

Traveling Salesperson

The Traveling Salesperson Problem (TSP) is a natural extension of the Hamiltonian Cycle problem. Given a graph with weighted edges representing distances (or costs) between cities, the objective is to find a continuous closed loop that visits every city exactly once while minimizing the total accumulated travel cost.

Within our Energy Constraint Computation (ECC) framework, TSP utilizes the same positional encoding as the Hamiltonian Cycle. The data structure, struct, represents the set of cities, while choices represent the sequential ranks (0 to N−1N - 1) assigned to each city. The compiler evaluates pairs of cities. For a given pair (cityA, rankA) and (cityB, rankB), the function computes the absolute difference between their assigned ranks to determine adjacency, including the N−1N - 1 wrap-around condition. The key distinction is that TSP directly maps the continuous edge weights to the energy eigenvalues of the problem Hamiltonian, whereas the Hamiltonian Cycle problem applies a fixed penalty for missing edges.

Relational Constraints and Evolution

Because the structural requirement of TSP, namely visiting every city exactly once, is identical to that of the Hamiltonian Cycle problem, the search space and relational constraints established in § 4.2 can be reused without modification. The quantum register is initialized in the valid permutation subspace using the Quantum Fisher–Yates Shuffle. The adiabatic evolution then employs the same relational constraint that strictly enforces rank-swapping between nodes. Consequently, the compiler reuses the same addition and subtraction operators together with the multi-node swap operations to construct the initial Hamiltonian. As the adiabatic evolution proceeds, the system traverses only the valid edges of the Many-World Configuration (MWC) graph. The resulting energy landscape naturally guides the quantum state toward the sequence that minimizes the accumulated data constraints, driving the system toward the optimal Traveling Salesperson tour.

Equational Three-Dimensional Matching

Given three finite sets XX, YY, and ZZ, the classic Three-Dimensional Matching (3DM) problem seeks a subset M⊆X×Y×ZM \subseteq X \times Y \times Z such that no two triples share an element. For this case study, we assume the subset MM selects exactly nn elements from each set. Furthermore, we expand the classical formulation by introducing a global equational constraint across the chosen elements:

∀(x,y,z)∈M⟹x%m=y%m=z%m\forall(x, y, z) \in M \Longrightarrow x \mathbin{\%} m = y \mathbin{\%} m = z \mathbin{\%} m

EnQ+ allows us to model this complex variant seamlessly by structuring the elements and choices as follows:

-- | Which partite set an equational-3DM element belongs to.
data MatchSet = SetX | SetY | SetZ deriving (Show, Eq, Ord)

-- | Element: (set tag, numeric value).
type MatchElem = (MatchSet, Int)

-- | Choice: (in matching?, claimed remainder mod m).
type MatchChoice = (Bool, Int)

We structure elements into disjoint sets (DxD_x, DyD_y, DzD_z) and encode each element’s MatchChoice as a tuple: a Boolean for inclusion in MM, and an integer representing its remainder modulo mm.

Data Constraints: The Problem Hamiltonian

The data constraints evaluate the pairwise consistency of the elements to define the problem’s energy landscape.

, dataProgram = DataProgram
    { choices = choiceList
    , struct = elems
    , view = 2
    , constraints = \case
        [((setA, valA), (yesA, remA)), ((setB, valB), (yesB, remB))] ->
            let
                uniq =
                    if setA == setB && yesA && yesB && valA == valB
``
19        then penalty
20        else 0
21        remAOK = if valA `mod` m == remA then 0 else penalty
22        remBOK = if valB `mod` m == remB then 0 else penalty
23    in uniq + remAOK + remBOK
24    _ -> error "equational3DM: Expected exactly two choices"
25  , choiceLayout = InclusionRemainder m
26  }

By setting the view to 2, the compiler evaluates every pair of candidates. The constraint imposes an energy penalty if two elements belong to the same partite set (setA == setB), are both chosen for inclusion (yesA && yesB), and correspond to the same underlying value (valA == valB). This natively prevents invalid overlaps in MM. Additionally, the constraint calculates the actual arithmetic remainder of the data (valA ‘mod‘ m) and applies a penalty if it mismatches the dynamically chosen remainder state (remA).

By setting the view to 2, the compiler evaluates every pair of candidates. The constraint imposes an energy penalty if two elements belong to the same partite set (setA == setB), are both chosen for inclusion (yesA && yesB), and correspond to the same numeric value (valA == valB), guarding against duplicate labels within a partite set. (Selecting exactly nn elements from each of XX, YY, and ZZ is enforced separately by the Dicke initial state of weight nn per set together with the Swap mixer on inclusion bits.) A second term compares each site’s value modulo mm (valA ‘mod‘ m) with its claimed remainder register (remA) and penalizes mismatches, so feasible configurations are those whose selected values all leave the same residue modulo mm.

Relational Constraints and State Preparation

The true expressiveness of EnQ+\mathrm{EnQ}^{+} is demonstrated in how it restricts the massive search space to only valid subset sizes and consistent remainders. The relational constraint (eSe_S) for Equational 3DM is heavily stratified:

27  , relationalProgram =
28      [ swapOn xIxs
29      , swapOn yIxs
30      , swapOn zIxs
31      , RelationalProgram
32          { relationalView = 3
33          , rule = ZeroFlag
34          , theta = (-1.0) :+ 0.0
35          , siteMask = AllSites
36          , fieldMask = RemainderField
37          }
38      ]
39  , initialState = Equational3DM n m setSize

We apply independent swap rules (swapOn) exclusively on the inclusion bits within XX, YY, and ZZ. This ensures that if an element is added to MM, another from the exact same set must be removed, rigidly preserving the constraint that exactly nn elements are selected per set. Simultaneously, we apply a 0-flagged relational constraint (ZeroFlag) across the remainder fields of all elements. This dictates that the chosen remainder modulo mm must transition uniformly across every element simultaneously, enforcing the equational constraint inherently. To initialize this constrained subspace, the compiler constructs an initial quantum state by first preparing three independent Dicke states on the inclusion qubits of sets XX, YY, and ZZ. Concurrently, the system initializes the remainder fields into a globally entangled, uniform 0-flagged superposition (e.g., 1m∑r∣r⟩⋯∣r⟩\frac{1}{\sqrt{m}}\sum_r |r\rangle\cdots|r\rangle).

This synchronized state perfectly aligns with the ground state of the 0-flagged initial Hamiltonian, embedding the equational constraint from the outset.

C.3.3 Execution and Evolution. Driven by the relational constraints, the Trotterized adiabatic evolution independently swaps element inclusions within their respective partite boundaries while globally shifting the entangled remainder value in lockstep. By traversing only the valid edges of the MWC graph, this strict subspace confinement allows the energy landscape to effectively steer the adiabatic evolution toward the optimal set of valid triplets.

References

  1. [1]2023. Blogade.jl: Package for the quantum computation and quantum simulation based on the neutral-atom architecture. https://github.com/QuEraComputing/Blogade.jl/
  2. [2]Noise-Aware Dynamical System Compilation for Analog Devices with Legno. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (Lausanne, Switzerland) (ASPLOS ’20). Association for Computing Machinery, New York, NY, USA, 149–166. https://doi.org/10.1145/3373767.3378449
  3. [3]Sara Achour, Rahul Rameshparkar, and Martin C. Rinard. 2016. Configuration synthesis for programmable analog devices with Arco. SIGPLAN Not. 51, 6 (jun 2016), 177–193. https://doi.org/10.1145/2980983.2908116
  4. [4]D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev. 2004. Adiabatic quantum computation is equivalent to standard quantum computation. In 45th Annual IEEE Symposium on Foundations of Computer Science. 42–51. https://doi.org/10.1109/FOCS.2004.8
  5. [5]Gadi Aleksandrowicz, Thomas Alexander, Panagiotis Barkoutsos, Luciano Bello, Yael Ben-Haim, David Bucher, Francisco Jose Cabrera-Hernández, Jorge Carballo-Franquis, Adrian Chen, Chun-Fu Chen, Jerry M. Chow, Antonio D. Córcoles-Gonzales, Abigail J. Cross, Andrew Cross, Juan Cruz-Benito, Chris Culver, Salvador De La Puente González, Enrique De La Torre, Delton Ding, Eugene Dumitrescu, Ivan Duran, Pieter Eendebak, Mark Everitt, Ismael Faro Sertage, Albert Frisch, Andreas Fuh rer, Jay Gambetta, Borja Godoy Gago, Juan Gomez-Mosquera, Donny Greenberg, Ikko Hamamura, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Hiroshi Horii, Shaohan Hu, Takashi Imamichi, Toshinari Itoko, Alij Javadi-Abhari, Naoki Kazanawa, Anton Karazeev, Kevin Kruslich, Peng Liu, Yang Luh, Yunho Maeng, Manoel Marques, Francisco Jose Martín-Fernández, Douglas T. McClure, David McKay, Srujan Meesala, Antonio Mezzacapo, Nikolaj Moll, Diego Moreda Rodríguez, Giacomo Nannicini, Paul Nation, Pauline Ollitrault, Lee James O’Riordan, Hanhee Paik, Jesús Pérez, Anna Phan, Marco Pistoia, Viktor Prutyanov, Max Reuter, Julia Rice, Abdón Rodríguez Davila, Raymond Harry Putra Rudy, Mingi Ryu, Ninad Sathaye, Chris Schnabel, Eddie Schoute, Kanav Setia, Yunong Shi, Adenilton Silva, Yukio Siraichi, Seyon Sivarajah, John A. Smolin, Mathias Soeken, Hitomi Takahashi, Ivano Tavernelli, Charles Taylor, Pete Taylour, Kenso Trabing, Matthew Treinish, Wes Turner, Desiree Vogt-Lee, Christophe Vuillot, Jonathan A. Wildstrom, Jessica Wilson, Erick Winston, Christopher Wood, Stephen Wood, Stefan Wörner, Ismail Yunus Akhalwaya, and Christa Zoufal. 2019. Qiskit: An open-source framework for quantum computing. https://doi.org/10.5281/zenodo.2562110
  6. [6]Noga Alon, Michael Krivelevich, and Benny Sudakov. 1998. Finding a large hidden clique in a random graph. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, USA) (SODA ’98). Society for Industrial and Applied Mathematics, USA, 594–598.
  7. [7]Matthew Amy, Martin Roetteler, and Krysta M. Svore. 2017. Verified Compilation of Space-Efficient Reversible Circuits. In Computer Aided Verification, Rupak Majumdar and Viktor Kunčak (Eds.). Springer International Publishing, Cham, 3–21.DOI
  8. [8]F Barahona. 1982. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General 15, 10 (oct 1982), 3241. https://doi.org/10.1088/0305-4470/15/10/028
  9. [9]Rodney J. Baxter. 1982. Exactly Solved Models in Statistical Mechanics. Academic Press.
  10. [10]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 (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 286–300. https://doi.org/10.1145/3385412.3386007
  11. [11]Endre Boros and Peter L. Hammer. 1991. The max-cut problem and quadratic 0–1 optimization: polyhedral aspects, relaxations and bounds. Annals of Operations Research 33, 3 (01 Mar 1991), 151–180. https://doi.org/10.1007/BF02115753
  12. [12]Endre Boros and Peter L. Hammer. 2002. Pseudo-boolean optimization. Discrete Appl. Math. 123, 1–3 (Nov. 2002), 155–225. https://doi.org/10.1016/S0166-218X(01)00341-9
  13. [13]J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aepp li. 1999. Quantum Annealing of a Disordered Magnet. Science 284, 5415 (1999), 779–781. https://doi.org/10.1126/science.284.5415.779 arXiv:https://www.science.org/doi/pdf/10.1126/science.284.5415.779
  14. [14]B. K. Chakrabarti. 1981. Critical behavior of the Ising spin-glass models in a transverse field. Phys. Rev. B 24 (Oct 1981), 4062–4064. Issue 7. https://doi.org/10.1103/PhysRevB.24.4062
  15. [15]Christophe Chareton, Sébastien Bardin, François Bobot, Valentin Perrelle, and Benoît Valiron. 2021. An Automated Deductive Verification Framework for Circuit-building Quantum Programs. In Programming Languages and Systems - 30th European Symposium on Programming, ESOP 2021, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, Luxembourg City, Luxembourg, March 27 - April 1, 2021, Proceedings (Lecture Notes in Computer Science, Vol. 12648), Nobuko Yoshida (Ed.). Springer, 148–177. https://doi.org/10.1007/978-3-030-72019-3_6
  16. [16]Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2002. Finding cliques by quantum adiabatic evolution. Quantum Info. Comput. 2, 3 (apr 2002), 181–191.
  17. [17]Vicky Choi. 2010. Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems. arXiv:1004.2226 [quant-ph] https://arxiv.org/abs/1004.2226
  18. [18]Bob Coecke and Ross Duncan. 2011. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics 13, 4 (April 2011), 043016. https://doi.org/10.1088/1367-2630/13/4/043016
  19. [19]Andrew Cross. 2018. The IBM Q experience and Qiskit open-source quantum computing software. In APS Meeting Abstracts.
  20. [20]Andrew Cross, Ali Javadi-Abhari, Thomas Alexander, Niel De Beaudrap, Lev S. Bishop, Steven Heidel, Colm A. Ryan, Prashant Saravah, John Smolin, Jay M. Gambetta, and Blake R. Johnson. 2022. OpenQASM 3: A Broader and Deeper Quantum Assembly Language. ACM Transactions on Quantum Computing 3, 3, Article 12 (sep 2022), 50 pages. https://doi.org/10.1145/3505636
  21. [21]D-Wave Quantum Inc. 2026. dimod.cqm_to_bqm. Ocean SDK documentation. Retrieved October 30, 2026 from https://docs.dwavequantum.com/en/latest/ocean/api_ref_dimod/generated/dimod.cqm_to_bqm.html
  22. [22]Arnab Das and Bikas K. Chakrabarti. 2008. Colloquium: Quantum annealing and analog quantum computation. Rev. Mod. Phys. 80 (Sep 2008), 1061–1081. Issue 3. https://doi.org/10.1103/RevModPhys.80.1061
  23. [23]Cirq Developers. 2023. Cirq. https://doi.org/10.5281/zenodo.10247207
  24. [24]Robert H. Doecke. 1954. Coherence in Spontaneous Radiation Processes. Physical Review 93, 1 (1954), 99–110.
  25. [25]Alejandro Díaz-Caro, Gilles Dowek, and Juan Pablo Rinaldi. 2019. Two linearities for quantum computing in the lambda calculus. Biosystems 186 (2019), 104012. https://doi.org/10.1016/j.biosystems.2019.104012 Selected papers from the International Conference on the Theory and Practice of Natural Computing 2017.
  26. [26]Entropica Labs. 2026. Using Different Mixer Hamiltonians. OpenQAOA documentation. Retrieved October 30, 2026 from https://el-openqaoa.readthedocs.io/en/latest/notebooks/11_Mixer_example.html
  27. [27]Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph]arxiv.org/abs/1411.4028
  28. [28]Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lap​​an, Andrew Lundgren, and Daniel Preda. 2001. A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem. Science 292, 5516 (2001), 472–475. https://doi.org/10.1126/science.1057726 arXiv:https://www.science.org/doi/pdf/10.1126/science.1057726
  29. [29]Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106DOI
  30. [30]A.B. Finnila, M.A. Gomez, C. Seb​​enik, C. Stenson, and J.D. Doll. 1994. Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters 219, 5 (1994), 343–348. https://doi.org/10.1016/0009-2614(94)00117-0
  31. [31]Peng Fu, Kohei Kishida, Neil J. Ross, and Peter Selinger. 2023. Proto-Quipper with Dynamic Lifting. Proc. ACM Program. Lang. 7, POPL, Article 11 (jan 2023), 26 pages. https://doi.org/10.1145/3571204
  32. [32]Y Fu and P W Anderson. 1986. Application of statistical mechanics to NP-complete problems in combinatorial optimisation. Journal of Physics A: Mathematical and General 19, 9 (jun 1986), 1605. https://doi.org/10.1088/0305-4470/19/9/033
  33. [33]Franz G. Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander J. Stasik, and Giorgio Sartor. 2022. Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm. Algorithms 15, 6 (2022), 202. https://doi.org/10.3390/a15060202
  34. [34]Jonathan Grattage. 2005. A Functional Quantum Programming Language. In Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS ’05). IEEE Computer Society, USA, 249–258. https://doi.org/10.1109/LICS.2005.1
  35. [35]Jonathan Grattage. 2011. An Overview of QML With a Concrete Implementation in Haskell, In Proceedings of the Joint 5th International Workshop on Quantum Physics and Logic and 4th Workshop on Developments in Computational Models (QPL/DCM 2008). Electronic Notes in Theoretical Computer Science 270, 1, 165–174. https://doi.org/10.1016/j.entcs.2011.01.015 arXiv:0806.2735 [quant-ph]
  36. [36]Jonathan James Grattage. 2006. A functional quantum programming language. Ph.D. Dissertation. University of Nottingham. http://eprints.nottingham.ac.uk/10250/
  37. [37]J. B. Graves. 2025. aAB: Anyonic Quantum Simulation of the Aharonov–Bohm Effect. Master’s thesis. Indiana University.
  38. [38]Alexander Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoît Valiron. 2013. Quipper: A scalable quantum programming language. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2013). 333–342. https://doi.org/10.1145/2491956.2462177
  39. [39]Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. 2019. From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. Algorithms 12, 2 (2019), 34. https://doi.org/10.3390/a12020034
  40. [40]Itay Hen and Marcelo S. Sarandy. 2016. Driver Hamiltonians for Constrained Optimization in Quantum Annealing. Physical Review A 93, 6 (2016), 062312. https://doi.org/10.1103/PhysRevA.93.062312
  41. [41]Itay Hen and Federico M. Spedalieri. 2016. Quantum Annealing for Constrained Optimization. *Physical Review Applied* 5, 3 (2016), 034007. https://doi.org/10.1103/PhysRevApplied.5.034007
  42. [42]Kesha Hietala, Robert Rand, Shih-Han Hung, Liyi Li, and Michael Hicks. 2021. Proving Quantum Programs Correct. In *Proceedings of the Conference on Interactive Theorem Proving (ITP).*DOI
  43. [43]Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. 2021. A Verified Optimizer for Quantum Circuits. In *Proceedings of the ACM Conference on Principles of Programming Languages (POPL).*
  44. [44]D-Wave Quantum Systems Inc. 2025. *D-Wave Quantum Systems Inc.* https://www.dwavesys.com/
  45. [45]Quantinuum Inc. 2025. *InQuant: Quantum Computational Chemistry.* https://www.quantinuum.com/products-solutions/inquanto
  46. [46]Ali JavadiAbhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, and Margaret Martonosi. 2015. ScaffCC: Scalable compilation and analysis of quantum programs. *Parallel Comput.* 45 (June 2015), 2–17. https://doi.org/10.1016/j.parco.2014.12.001
  47. [47]J.R. Johansson, P.D. Nation, and Franco Nori. 2012. QuTiP: An open-source Python framework for the dynamics of open quantum systems. *Computer Physics Communications* 183, 8 (2012), 1760–1772. https://doi.org/10.1016/j.cpc.2012.02.021
  48. [48]Tadashi Kadowaki and Hidetoshi Nishimori. 1998. Quantum annealing in the transverse Ising model. *Physical Review E* 58, 5 (Nov. 1998), 5355–5363. https://doi.org/10.1103/physreve.58.5355
  49. [49]Richard M. Karp. 1972. *Reducibility among Combinatorial Problems.* Springer US, Boston, MA, 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9
  50. [50]Gary G. Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, and Yang Wang. 2014. The unconstrained binary quadratic programming problem: a survey. *J. Comb. Optim.* 28, 1 (July 2014), 58–81. https://doi.org/10.1007/s10878-014-9734-0
  51. [51]Kazue Kudo. 2018. Constrained Quantum Annealing of Graph Coloring. *Physical Review A* 98, 2 (2018), 022301. https://doi.org/10.1103/PhysRevA.98.022301
  52. [52]Hannes Leipold and Federico M. Spedalieri. 2022. Constructing Driver Hamiltonians for Optimization Problems with Linear Constraints. *Quantum Science and Technology* 7, 1 (2022), 015013. https://doi.org/10.1088/2058-9565/ac16b8
  53. [53]Hannes Leipold, Federico M. Spedalieri, Stuart Hadfield, and Eleanor Rieffel. 2024. Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation. https://doi.org/10.1145/3821414 arXiv:2407.01975 [quant-ph]
  54. [54]Liyi Li, Fenfen An, Federico Zahariev, Zhi Xiang Chong, Amr Sabry, and Mark S. Gordon. 2025. A Verified Compiler for Quantum Simulation. arXiv:2509.18583 [cs.PL]. https://arxiv.org/abs/2509.18583
  55. [55]Liyi Li, Anshu Sharma, Zoukarneini Difaizi Tagba, Sean Frett, and Alex Potanin. 2026. Validating Quantum State Preparation Programs. In *Programming Languages and Systems: 35th European Symposium on Programming, ESOP 2026, Held as Part of the International Joint Conferences on Theory and Practice of Software, ETAPS 2026, Turin, Italy, April 11–16, 2026, Proceedings, Part I.* Springer-Verlag, Berlin, Heidelberg, 432–462. https://doi.org/10.1007/978-3-032-22720-1_16
  56. [56]Liyi Li, David Young, James Bryan Graves, Chandeepa Dissanayake, and Amr Sabry. 2025. A Haskell Adiabatic DSL: Solving Classical Optimization Problems on Quantum Hardware. *Proc. ACM Program. Lang.* 9, ICFP, Article 252 (Aug. 2025), 31 pages. https://doi.org/10.1145/3747521
  57. [57]Liyi Li, Mingwei Zhu, Rance Cleveland, Alexander Nicollis, Yi Lee, Le Chang, and Xiaodi Wu. 2024. Qafny: A Quantum-Program Verifier. In *ECOOP 2024.*
  58. [58]Junyi Liu, Bohua Zhan, Shuling Wang, Shenggang Ying, Tao Liu, Yangjia Li, Mingsheng Ying, and Naijun Zhan. 2019. Formal Verification of Quantum Algorithms Using Quantum Hoare Logic. In *Computer Aided Verification*, Isil Dillig and Serdar Tasiran (Eds.). Springer International Publishing, Cham, 187–207.DOI
  59. [59]Andrew Lucas. 2014. Ising formulations of many NP problems. *Frontiers in Physics* 2 (2014). https://doi.org/10.3389/fphy.2014.00005
  60. [60]Jarrod R. McClean, Kevin J. Sung, Ian D. Kivlichan, Yudong Cao, Chengyu Dai, E. Schuyler Fried, Craig Gidney, Brendan Gimby, Pranav Gokhale, Thomas Häner, Tarini Hardikar, Vojtěch Havlíček, Oscar Higgott, Cupjin Huang, Josh Izaac, Zhang Jiang, Ximile Liu, Sam McArdle, Matthew Neeley, Thomas O’Brien, Bryan O’Gorman, Isil Ozfidan, Maxwell D. Radin, Jhonathan Romero, Nicholas Rubin, Nicolas P. D. Sawaya, Kanav Setia, Sukin Sim, Damian S. Steiger, Mark Steudtner, Qiming Sun, Wei Sun, Daochen Wang, Fang Zhang, and Ryan Babbush. 2019. OpenFermion: The Electronic Structure Package for Quantum Computers. arXiv:1710.07629 [quant-ph] https://arxiv.org/abs/1710.07629
  61. [61]Michael A. Nielsen and Isaac L. Chuang. 2011. *Quantum Computation and Quantum Information* (10th anniversary ed.). Cambridge University Press, USA.
  62. [62]G. Ortiz, E. Knill, and J. E. Gubernatis. 2002. The challenge of quantum computer simulations of physical phenomena. *Nuclear Physics B - Proceedings Supplements* 106–107 (2002), 151–158. https://doi.org/10.1016/S0920-5632(01)01654-1
  63. [63]Yuxiang Peng, Jacob Young, Pengyu Liu, and Xiaodi Wu. 2024. SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation. *Proc. ACM Program. Lang.* 8, POPL, Article 81 (jan 2024), 31 pages. https://doi.org/10.1145/3632923
  64. [64]Qiskit Community. 2026. QuadraticProgramToQubo. Qiskit Optimization 0.7 documentation. Retrieved October 30, 2026 from https://qiskit-community.github.io/qiskit-optimization/stubs/qiskit_optimization.converters.QuadraticProgramToQubo.html
  65. [65]Robert Rand. 2018. Formally verified quantum programming. Ph. D. Dissertation. University of Pennsylvania.
  66. [66]Robert Rand, Jennifer Kayin, Dong-Ho Lee, and S. Zdanciewic. 2018. ReQWIRE: Reasoning about Reversible Quantum Circuits. In QPL.DOI
  67. [67]P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti. 1989. Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations. Phys. Rev. B 39 (Jun 1989), 11828–11832. Issue 16. https://doi.org/10.1103/PhysRevB.39.11828
  68. [68]Amr Sabry, Benoît Valiron, and Juliana Kaizer Vizzotto. 2018. From Symmetric Pattern-Matching to Quantum Control. In Foundations of Software Science and Computation Structures, Christel Baier and Ugo Dal Lago (Eds.). Springer International Publishing, Cham, 348–364.DOI
  69. [69]Peter Selinger and Benoît Valiron. 2013. Quantum Lambda Calculus. Semantic Techniques in Quantum Computation (01 2013). https://doi.org/10.1017/CBO9781139193313.005
  70. [70]Yunong Shi, Xupeng Li, Runzhou Tao, Ali Javadi-Abhari, Andrew W. Cross, Frederic T. Chong, and Ronghui Gu. 2019. Contract-based verification of a realistic quantum compiler. arXiv e-prints (Aug 2019). arXiv:1908.08963 [quant-ph]
  71. [71]Henrique Silvério, Sebastián Grijalva, Constantin Dalyac, Lucas Leclerc, Peter J. Karalekas, Nathan Shammah, Mourad Beji, Louis-Paul Henry, and Loïc Henriet. 2022. Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays. Quantum 6 (Jan. 2022), 629. https://doi.org/10.22331/q-2022-01-24-629
  72. [72]Robert S. Smith, Eric C. Peterson, Mark G. Skilbeck, and Erik J. Davis. 2020. An Open-Source, Industrial-Strength Optimizing Compiler for Quantum Programs. arXiv:2003.13961 [quant-ph]arxiv.org/abs/2003.13961
  73. [73]R. D. Somma, G. Ortiz, E. H. Knill, and J. Gubernatis. 2003. Quantum Simulations of Physics Problems. In Quantum Information and Computation (Proceedings of SPIE, Vol. 5105). 96–103. https://doi.org/10.1117/12.487249 arXiv:quant-ph/0304063
  74. [74]Damian S. Steiger, Thomas Häner, and Matthias Troyer. 2018. ProjectQ: an open source software framework for quantum computing. Quantum 2 (Jan. 2018), 49. https://doi.org/10.22331/q-2018-01-31-49
  75. [75]Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz, and Martin Roetteler. 2018. Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL. In Proceedings of the Real World Domain Specific Languages Workshop 2018 (RWDSL2018). ACM. https://doi.org/10.1145/3183895.3183901
  76. [76]André van Tonder. 2004. A Lambda Calculus for Quantum Computation. SIAM J. Comput. 33, 5 (Jan. 2004), 1109–1135. https://doi.org/10.1137/S009753970342165
  77. [77]Juliana Kaizer Vizzotto, Bruno Chaves de Souza, and Eduardo Kessler Piveta. 2013. A Double Effect λ-calculus for Quantum Computation. In Programming Languages, André Rauber Du Bois and Phil Trinder (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 61–74.DOI
  78. [78]Finn Vojcik, Liyu Li, Robert Rand, and Michael Hicks. 2023. Qunity: A Unified Language for Quantum and Classical Computing. Proceedings of the ACM on Programming Languages 7, POPL (Jan. 2023), 921–951. https://doi.org/10.1145/3571225
  79. [79]Quanlong Wang. 2023. Completeness of the ZX-calculus. arXiv:2209.14894 [quant-ph]arxiv.org/abs/2209.14894
  80. [80]Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. 2020. XY Mixers: Analytical and Numerical Results for the Quantum Alternating Operator Ansatz. Physical Review A 101, 1 (2020), 012320. https://doi.org/10.1103/PhysRevA.101.012320
  81. [81]F. Y. Wu. 1982. The Potts model. Rev. Mod. Phys. 54 (Jan 1982), 235–268. Issue 1. https://doi.org/10.1103/RevModPhys.54.235
  82. [82]Wenhao Wu, B. Ellman, T. F. Rosenbaum, G. Aeppli, and D. H. Reich. 1991. From classical to quantum glass. Phys. Rev. Lett. 67 (Oct 1991), 2076–2079. Issue 15. https://doi.org/10.1103/PhysRevLett.67.2076
  83. [83]Mingsheng Ying. 2012. Floyd–Hoare Logic for Quantum Programs. ACM Trans. Program. Lang. Syst. 33, 6 (Jan. 2012), 49 pages. https://doi.org/10.1145/2049706.2049708
  84. [84]Mingsheng Ying. 2016. Foundations of Quantum Programming. Elsevier Science, Cambridge, MA. xii + 357 pages.
  85. [85]Li Zhou, Gilles Brassard, Pierre-Yves Strub, Junyi Liu, and Mingsheng Ying. 2023. QqQ: Quantum Control Verification of Quantum Programs. Proc. ACM Program. Lang. 7, POPL, Article 29 (Jan 2023), 33 pages. https://doi.org/10.1145/3571222

Paper details

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

views · 1

downloads · 0

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

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents