WorksPhysics and Astronomy
Constrained Adiabatic Quantum Programming
Abstract
To find a -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 subsets of the vertices, although only the subsets of size 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 . 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 , one whose minimum is easy to prepare, and then deforms the cost function slowly along into the problem cost function , 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 . 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 -clique graph problem [59]. It puts a binary variable on every vertex of a graph , so a configuration is a 0/1 labeling of all vertices; its cost is computed by the formula
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 ; the second grows as the 1-valued vertices miss the edges of a clique. The cost is zero exactly on a -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 -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 simply suggests that one needs to look at every pair of configuration nodes in 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 part, while the initial Hamiltonian () is not clearly explained. The initial state is required to be an eigenstate of the initial Hamiltonian , but the model provides no additional information on how users can understand and program . 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 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 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 ; . 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 , where we map each basis-ket state in to a configuration in the graph and each data-point vertex is a bit in the basis-ket, e.g., the left configuration represents , so we mark the blue vertices for the and positions.
MWC graphs support AQC constraints: initial Hamiltonians () define the relational constraint relating edges in the MWC graph, and final Hamiltonians () 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 ((, ), (, ), (, ), (, ), (, ), (, )), 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 (, ) at the configuration .
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 and configurations, the and data points differ. In , 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 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. 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 programs to quantum computers. Using the certified compiler, we uncover a long-standing issue in Hamiltonian-simulation-based AQC compilation.
Contributions and Roadmap
is based on AQC and builds on prior work. The detailed AQC background and the difference between 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 ; details are in § 3.1.
We extend [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 programs. To the best of our knowledge, this is the first step-wise transition semantics for AQC for the specific 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 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 , , , , , and the chord . The graph has exactly one triangle, .
Figure 2. Our graph. Its only triangle, , 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 , slowly from an initial Hamiltonian with a known ground state to a final Hamiltonian whose ground state encodes the solution. The evolution adjusts 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 that varies with time from to . 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 for a small time period . Note that a Hamiltonian is a Hermitian matrix (Hermitian ) and that Hamiltonian simulation 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 and applying a sequence of unitary quantum operations, each of which is of the form for a different .
Understand Constraints based on MWC Graphs. We first show the EnQ interpretation of data constraints on the MWC graphs, corresponding to the final Hamiltonian () 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 , where Yes means the vertex is included in the clique. A configuration is one such labeling of all five vertices, and there can be of them. For example, Table 1 marks the vertices , , and to be Yes, and the others to be No. In EnQ, we define the data constraint to be as follows.
| candidate | candidate | ||
| 0 | 1 | ||
| 2 | 1 | ||
| 1 | 2 | ||
| 1 | 2 | ||
| 1 | 1 |
Table 1. The ten three-vertex candidates and their cost . Only 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 (), blue costs 1, red costs 2.
Given two vertices, and , in a graph, if they are considered in the subgraph and there is no edge between them, we assign an energy loss to them; otherwise, the loss is 0, e.g., Table 1; only 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 with score 0, the Yes vertices in 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.
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.
Here, we examine pairs of configurations, connected by edges . The bindings and indicate that the constraint applies to two data points in , e.g., in the configurations and of Figure 3, we examine the two data points and 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 ( or ) is swapped from one configuration () to the other (). 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 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,
defines a relational constraint describing a swap among three vertices in a configuration pair.
Another constraint is , which defines a relation that moves in the same direction in a configuration pair. Consider a Bell pair , which can be thought of as two qubits measuring into the same bits. Viewing a Bell pair in can be thought of as a relational constraint that two qubits move in the same direction, i.e., the basis-vector set contains , where the two sites are always moving in the same direction, as . 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, , , , and , with the following operational behavior.
To compile data constraints, we use the and operations. In clique finding, we essentially enumerate Yes and No as and , respectively. For every configuration, we generate every possible pair and of data points, and interpret the two choices in the data-constraint , where is the energy loss score for . We then summarize all the energy scores for each possible pair as the final energy loss for the configuration. Essentially, we can view as a function that interprets the choices for a data-point pair. For example, in the configuration of Figure 3, we interpret the pairs , , with different choice combination. To interpret , we take its choice value, , 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., is represented as . A quantum state is not observable, so we use the operators and to represent and , respectively. For example, is represented as and we assign the energy score as the amplitude, . Finally, we sum all the generated operations, e.g., , 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 and . For example, to compile the relational constraint above, we consider two configurations connected by an edge . We then compare the same name (id) data-points across and , having different choices, such as and in the pairs and . A choice changes and across the two data points, yielding a and operation, respectively, e.g., the pair is compiled to , 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 with , via the rules below.
After producing a linear sum of Pauli strings, , 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 , assumed to contain data points with type .
Definition 3.1 (Data Structure and Configuration). We define to be a data structure containing data-points with type . Each data-point object must at least contain the fields of identity
(id), datum (data()), and choice (choice()). We assume data (data()) has an energy value type () and a set of choices choice() = that turns a choice into an energy value. Given , a configuration is a data structure , with choice assignments () in to every data-points in .
The example graph in Figure 2 has 5 data-points, . There is no need to use the data fields in clique finding, where we can define the data as , and choices for each node can be . The solution has the assignment . We show the MWC graph definition below.
Definition 3.2 (MWC Graph). We define to be a MWC graph, containing a set of configurations () and edges (). Each configuration contains a data-structure (content) and an amplitude field (amp) having type , while each edge contains a weight field (weight) having type . All configurations in have the same set of data-points, where and .
A MWC graph 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, ) containing a set of distinct data-points (), a set of choices (choices, ), an initial state (initS, ) acting as the initial set of configurations with data-points being assigned with different choice values, a data constraint (constraint, ), and a relational constraint (relation, ). The program syntax extends EnQ with an initial starting state and a second syntactic category, relational constraints , that let the programmer declare the structure of the initial Hamiltonian directly. Figure 4 gives the extended grammar; shaded productions are new.

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 , the trivial relational constraint whose semantics is the uniform-superposition initial Hamiltonian. : a set of data-points.
When defining a data constraint (), we assign an energy-loss value to unwanted cases. Users are able to access the data value of a data-point (data()), turn a choice into an energy loss (choice()), or use classical arithmetic () and Boolean () 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 is a sum of singleton relational constraints, allowing the programmer to specify relations among edges in MWC graphs. Such a constraint is defined by a list of variables () and a relational flag . 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., . In a singleton data constraint and singleton relational constraint , users can bind a site tuple (a singleton tuple is a variable) via -binders. The binder or binds a variable to a data-point, selected from the data-point set , and used in (or ). 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., . means that every choice is a pair and we establish the relation on the second part of each pair as 0-flagged.
The -binders quantify the atom over all tuples of nodes defined in , 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 () to refer to choosing from the whole data-point set, and selects two tuples and , where they must be distinct data-points.
Typing. Figure 5 defines the type system, which has the top-level judgment , as well as the expression judgment , where is the type environment, mapping from variables to data-point sets; could be a program , an arithmetic () and Boolean () expression; is the type construct, defined as follows.

Figure 5. Type rules.
Here, , , and 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 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., means and must be two distinct data points. Rule T-Rel partitions the type environment 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 , because selecting the data-point set might empty a constraint. For example, since . . requires that and to be two distinct data-points, if , 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 ’s data-point set lies within a region with variable set . We also ensure that the sets can be ordered as , and every set in is a subset of . Then, the cardinality of exceeds the number of variables and , ensuring no empty constraint. In rule T-Top, collects all the mentioned data points and ensures that the configurations in 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 , where is a program and are MWC graphs. A data constraint might contain an expression with the type , where we can interpret with , so produces an energy loss ; such rules are shown in Figure 6.
We now define the constraint semantics as a function interpreting a MWC graph , with each node having a fixed set of data-points , coming from the user-defined data structure . For simplicity, we linearize the tuples in each binding, as in the following example.
We first define the data constraint semantics.
Fig. 6. Expression Level Constraint Semantics
Definition 3.3 (Data Constraint Semantics). Given a data constraint and a MWC graph , we define data-constraint interpretation function , adding the amplitude (amp) for every , as , where we define the rules as follows.
Here, is the interpretation function in Figure 6, is a function sum, with , and the gen function is defined as follows.
The iterative function gen generates a list of data points () for calculating the energy loss values. Every singleton data constraint has the form , and each variable is selected from the set subtracting the data-points selected for .
We define the relational constraint below as the production of the edge set , i.e., configuration pairs connected by edges.
Definition 3.4 (Relational Constraint Semantics). Given a constant weight , given a data constraint and a MWC graph , we define data-constraint interpretation function , adding the weight (weight) for every edge , as if is true, where we define the rules as follows.
when and .
Here, is a function sum, with , and the Boolean function is defined as follows.
The function checks whether and are an -order permutation, which refers to that and have the same set of choices, and there are positions in and 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 , defined as follows.
With the constraint semantics, we show the type soundness theorem below.
Theorem 3.5 (Type Soundness). For a program , with , where is the initial state, there are valid interpretations of .
Proof. We prove by induction on the type rules in Figure 5. □
Dynamic Semantics. The constraint semantics of an EnQ+ program is a function on the MWC graph , 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 , where comes from the relational constraint and 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, and , that produce rotations in . Here, we mainly develop the theory for the system constructed by EnQ+ and evolved by Hamiltonian simulation , though other AQC systems may apply. Given a program and an MWC graph , the definition partitions configurations and edges into relevant and irrelevant sets. Given a data constraint , the relevant sets contain configurations that yield a non-zero value when is applied, while configurations in the irrelevant set yield a 0 when is applied.
Theorem 3.6 (Data Constraint Evolution). Given a data constraint and an -dimensional MWC graph , for every , the instantaneous effect , evolving the system for an evolution time , compilation factor , on the relevant set is an update on ’s amplitude, as , where . The effect on the irrelevant set is neutral, as .
The relevant sets have a different definition for a relational constraint . Essentially, 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 and an -dimensional MWC graph , for every , the instantaneous effect , evolving the system for a small time , compilation factor , on the relevant set is as , where , where is the number of nonzero increment in , i.e., the number of edges such that . The effect on the irrelevant set is neutral, as .
The above unveils the dynamic semantics for evolving the data and relational constraints individually, yielding two angle functions and in the range , respectively interpreting each configuration and edge in a MWC graph. In fact, both angles must be .
With the definition for individual constraints, we define the dynamic semantics of the whole system, based on two-step operations, and , which are two monotonic functions within the AQC evolution steps, i.e., given a single step time factor , evolution stops exactly at the 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 ’s time factor from 0 to 1 and ’s factor from 1 to 0 by .
Theorem 3.8 (Dynamic Semantics). Given an initial state as MWC graph , for every , we have an angle , and for every relevant edge , we have an angle function ; we define the dynamic transition steps based on relevant edges, and , as the likelihood multiplication on configuration’s amplitude, i.e., given step, the evolution transitions ’s amplitude as for good states and the amplitude for bad states.
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 , i.e., , is a monotonic decreasing function, while is a monotonic increasing function.
Proof. The proof proceeds by induction on the steps for and . □
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 and , 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 is the eigenstate of a relational constraint (), where . We define such a relation as , with being the eigenstate of and all non-zero configurations and edges in are defined in . Under this definition, the following theorem relates and .
Theorem 3.10 (Good Approximation). Given , with being the relational constraint and being the initial state, assume , with , partitions into relevant () and irrelevant () sets, as keeps the two sets being orthonormal; for every , the AQC evolution results keep the final amplitudes the same as the initial one in .
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 variables with two options each would generate combinations. Instead of iterating through each combination, we prepare a quantum superposition that represents all 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 , 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.
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 is transformed to . For binary variables, this yields a uniform superposition of all combinations, which can be transformed to the form listed on the right side above. The state has different basis-kets, each with amplitude being and a basis-vector . Here, denotes the binary string representation of the number . In the quantum setting of the clique-finding example, we want to start with an -qubit initial superposition state of -th Dicke state, , where checks the bitstring representation of having exactly copies of 1. Different selections of initial states might affect the convergence speed of the AQC computation.
C-EU
C-Bind
C-ES
C-Sum
Compiling EnQ+ Programs to Pauli-strings
We examine the compilation of constraint expressions and to Pauli-string forms , as the extension of the EnQ+ type system, , with having the form . The rules are in Figure 8.
Figure 8. Compilation Rules. is the program and points produces data-points of a configuration in .
Rule C-Sum turns an EnQ+ composition operation into a linear sum; C-Bind turns the data-point choice for into a linear sum over ’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 . 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 (), we examine the pair and yield an operator in . We name the procedure state marking, because applying an operator to an unqualified vector yields , e.g., .
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 , we use a 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, . Here, we can use two qubits per node to represent the four colors as , , , and , respectively. We can extend this idea to an -qubit state marking, , using the following operations.
where
Here, converts to a bitstring, and the operations in can be compiled to Pauli operators as follows.
The state marking function essentially utilizes the bitstring representations of and . For the -th bit position and , 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 , to mark a specific state as , we model in rule C-EU as follows.
Here, we include the data-point location as the target for applying the generated Pauli strings in . The end result of compiling a data constraint is a final Hamiltonian , as a sum of weighted Pauli operators (single-qubit s, two-qubit interactions, etc., depending on the structure of the data constraints).
The above generate Pauli strings representing non-zero data points, with assigning the energy scores for these data points. The function interprets the expression by assigning variables to numbers representing data-point locations. Additionally, for generic energy-score constructs in , we try different real-number assignments and minimize the steps using the function for estimation. We list the minimization function below.
Finally, the negative sign in C-EU ensures the correctness for the Hamiltonian-simulation-based AQC compilation.
Compiling relational constraints. We mainly explain here. We first define useful helper functions. For the vector , the function rewrites those cases to . For an arbitrary input, we can utilize linear sum operations to construct the following operator.
Given a quantum state , the addition and subtraction operations add or subtract to a basis vector; e.g., we turn into and , respectively. However, we cannot predetermine the specific for a quantum state, so we use a linear sum operator to prepare the addition and subtraction operations for all possible .
The two operations above allow us to move and 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 in from the data-point set . We define the constraint as follows, with and denoting linear summation.
The key in the modeling is that we let all single data-points to perform the same addition or subtraction, where refers to the sequencing operation, , and applies the Pauli-string on the qubits in the data-point .
The modeling of the 1-flagged constraint is similar to 1-flagged one, but we ensure that every data-point adds or subtracts a different number.
where
When we pick the data-points , we find all -length choice combinations , where we have possible combinations. For each combination, we let each data point add or subtract the value picked at .
The modeling of the swap constraint utilizes a similar combination concept, but we are picking different combinations of permutations; i.e., given data points with the assumption of , we perform the operations based on the permuted value, as . The modeling is listed below.
For example, when dealing with the clique-finding problem, to handle the constraint , we need to consider permutations of two data points, e.g., and . Since the choice set is binary, we can write the constraint as follows.
Compiling the Adiabatic Process to Quantum Circuits and the Theory
After generating the Pauli-string forms for and , we apply the standard approximation method for AQC in § 2, which compiles the AQC process to a sequence of Hamiltonian simulation operations, each computing with . 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 , , and a desired error , with data-constraint and relational constraint , we compile them as , , , and the AQC compilation as . The result is bounded by , compared against to ’s dynamic semantics, as .
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 step function becomes monotonic decreasing within the bounded steps . 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.
Note that the identity operators have no effect in compilation, so this means that we have negative signs in both the initial () and final () 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.
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, is typically negative, while a ferromagnetic model, with positive , 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 , , and , the three-dimensional matching problem is to find a subset such that no two triples in share an element. For simplicity, we assume there is a number such that selects elements from each of the sets , , and . Additionally, we add an equational constraint across the three different sets, as follows.
To program the problem in EnQ+, we assume a data structure with three sets , , and ; each element in the sets has a data field containing the element value and a choice field as a pair . The first element is a Boolean value , implementable as a single qubit, indicating whether an element is included in the set . The second element is a qubit value, representing the remainder , , and .
We first model the relational constraint, as follows.
In the above relational constraint, the first three lines define the swap constraint for the first pair of elements in the sets , , and , 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 , we constrain on the elements, , , , and , to ensure that they move in the same direction. For example, if , the three elements form the superposition state as follows.
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 , , and , 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.
Finally, we model the data constraint above using the generic energy values L and O mentioned in § 2. In , the first three lines constrain that if two elements from the three sets are included in 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 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, introduces an MWC graph view of quantum states, enabling users to develop high-level programs with arbitrary data structures. 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, 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 (, , and ), 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 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 , 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, 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 programs and use them to certify compilation from an 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 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 and , we leverage AQC to find the optimum. The principle of AQC is to slowly interpolate between and 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 that evolves from to as a function of a normalized time parameter . For example, a linear schedule would use . Initially (), the system is in the ground state of (the uniform superposition). As 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 . By the end (), the system will be in the ground state of , 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 . 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 expressed as a sum of basic operators, the next step is to turn the continuous evolution into a sequence of gates. EnQ+ uses a Trotter-Suzuki decomposition to approximate the exponential of a sum of operators. In brief, if (where and are operators that act on possibly different sets of qubits), we can approximate for a small time slice , with the error of order . By splitting the total evolution time into small slices () and alternating the application of and , the accumulated error becomes negligible for large . 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.
We approximate by setting to be , i.e., for each Pauli string , we construct an application sequence , where we repeat the simulation of for times with a scaled time slot . Each is defined as
with and . For example, to simulate the Pauli-string-based Hamiltonian with a time slot and splitting number , we compute the approximation of the exponent as follows.
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 , it is enough to describe the synthesization of a single matrix exponential term . We discuss the digital and analog-based synthesization below.
We synthesize the simulation of a Pauli string, , 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() controlling on and applying X gate on ).
The procedure focuses on the non- terms in a Pauli string . If has only one non- 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()() applies a -axis rotation in the -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 generates an Rx gate, as Rx()(). We describe the algorithm in Figure 9 for a Pauli string with more than one non- term, i.e., a -local Pauli string with .
Figure 9. Pauli matrices simulated to rotation gates. can be thought as simulating on time .
We first show the gate synthesization of the simple Ising model in Equation (3), which produces a sequence of and operations (the sequence length is related to ). If is large enough, the operation sequence is a good approximation to . The operation produces a Rx gate [61], while produces a digital circuit as the left in Figure 10, performing two controlled-not gates and an Rz() gate in the middle for the -th and -th qubits, i.e., Rz() is an -axis phase rotation gate.

Figure 10. Circuit and unitary for Interaction. The left circuit applies on and qubits.
We show an example of a long Pauli string synthesization in Figure 11. After applying Trotterization on the , we generate a sequence of Hamiltonian simulations of Pauli strings. Some possible Pauli string terms might be 4-local, as (abbreviated as ), (abbreviated as ) and (abbreviated as ). The simulation of the term results in a quadruple interaction in Figure 11a, containing a interaction application in the middle, shown in Figure 10, with the surrounding of controlled-not gates. The digital gate synthesization of and is based on the quadruple interaction with repairs for and conversion, which results in the circuits in Figure 11b and Figure 11c.

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 minimum | Hamiltonian; ground state |
| data constraint | problem Hamiltonian; phase separator (QAOA) |
| relational constraint | driver Hamiltonian (annealing); mixer (QAOA) |
| quantity a relational constraint preserves | conserved quantity; symmetry |
| candidates (nodes of the MWC graph) | symmetry sector; feasible subspace |
| swap of a chosen and an unchosen vertex | XY exchange; hard-core boson hopping; Kawasaki move |
| uniform start over the -subsets | Dicke state |
| penalty | energy 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 vertices corresponds to the -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, : it transfers a particle from an occupied mode to an empty one while preserving the total particle number. For such modes, the Hilbert space decomposes into fixed-particle-number sectors:
Here counts occupied modes, and is the subspace with exactly 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 -particle subspace remains there. The Dicke state [24] used by the program is the uniform superposition of all occupation patterns with exactly 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 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 vertices, the struct defines the set of vertices (cities), and the available choices correspond to the ranks 0 through . The constraints function then evaluates whether an edge exists between the chosen vertex at rank and the vertex at rank . If , 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 (), where 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 () 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 and lowering operators over the binary representations of the sequence ranks. For our four ranks, , each rank is encoded using two qubits as , , , and .
Suppose the evolution requires shifting a rank by . The corresponding raising operator induces the following state transitions:
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 requires applying the creation operator to the first qubit while projecting the second qubit onto . The resulting tensor-product representation is:
Similarly, the transition keeps the second qubit in the state by applying the projector giving:
Therefore, the complete raising operator over the rank subspace is obtained by summing the two transitions:
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 graph again. If city 0 currently holds rank 0 () and city 2 holds rank 2 (), 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:
Likewise, the reverse transition is represented by
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 (). 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 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 ) 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 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 , , and , the classic Three-Dimensional Matching (3DM) problem seeks a subset such that no two triples share an element. For this case study, we assume the subset selects exactly elements from each set. Furthermore, we expand the classical formulation by introducing a global equational constraint across the chosen elements:
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 (, , ) and encode each element’s MatchChoice as a tuple: a Boolean for inclusion in , and an integer representing its remainder modulo .
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 . 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 elements from each of , , and is enforced separately by the Dicke initial state of weight per set together with the Swap mixer on inclusion bits.) A second term compares each site’s value modulo (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 .
Relational Constraints and State Preparation
The true expressiveness of is demonstrated in how it restricts the massive search space to only valid subset sizes and consistent remainders. The relational constraint () 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 , , and . This ensures that if an element is added to , another from the exact same set must be removed, rigidly preserving the constraint that exactly 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 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 , , and . Concurrently, the system initializes the remainder fields into a globally entangled, uniform 0-flagged superposition (e.g., ).
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]2023. Blogade.jl: Package for the quantum computation and quantum simulation based on the neutral-atom architecture. https://github.com/QuEraComputing/Blogade.jl/
- [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]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]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]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]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]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]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]Rodney J. Baxter. 1982. Exactly Solved Models in Statistical Mechanics. Academic Press.
- [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]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]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]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]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]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]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]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]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]Andrew Cross. 2018. The IBM Q experience and Qiskit open-source quantum computing software. In APS Meeting Abstracts.
- [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]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]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]Cirq Developers. 2023. Cirq. https://doi.org/10.5281/zenodo.10247207
- [24]Robert H. Doecke. 1954. Coherence in Spontaneous Radiation Processes. Physical Review 93, 1 (1954), 99–110.
- [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]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]Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph]arxiv.org/abs/1411.4028
- [28]Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, 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]Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106DOI
- [30]A.B. Finnila, M.A. Gomez, C. Sebenik, 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]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]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]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]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]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]Jonathan James Grattage. 2006. A functional quantum programming language. Ph.D. Dissertation. University of Nottingham. http://eprints.nottingham.ac.uk/10250/
- [37]J. B. Graves. 2025. aAB: Anyonic Quantum Simulation of the Aharonov–Bohm Effect. Master’s thesis. Indiana University.
- [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]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]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]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]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]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]D-Wave Quantum Systems Inc. 2025. *D-Wave Quantum Systems Inc.* https://www.dwavesys.com/
- [45]Quantinuum Inc. 2025. *InQuant: Quantum Computational Chemistry.* https://www.quantinuum.com/products-solutions/inquanto
- [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]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]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]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]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]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]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]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]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]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]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]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]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]Andrew Lucas. 2014. Ising formulations of many NP problems. *Frontiers in Physics* 2 (2014). https://doi.org/10.3389/fphy.2014.00005
- [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]Michael A. Nielsen and Isaac L. Chuang. 2011. *Quantum Computation and Quantum Information* (10th anniversary ed.). Cambridge University Press, USA.
- [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]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]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]Robert Rand. 2018. Formally verified quantum programming. Ph. D. Dissertation. University of Pennsylvania.
- [66]Robert Rand, Jennifer Kayin, Dong-Ho Lee, and S. Zdanciewic. 2018. ReQWIRE: Reasoning about Reversible Quantum Circuits. In QPL.DOI
- [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]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]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]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]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]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]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]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]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]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]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]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]Quanlong Wang. 2023. Completeness of the ZX-calculus. arXiv:2209.14894 [quant-ph]arxiv.org/abs/2209.14894
- [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]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]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]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]Mingsheng Ying. 2016. Foundations of Quantum Programming. Elsevier Science, Cambridge, MA. xii + 357 pages.
- [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






