## Abstract

In a recent paper, Lechner, Hauke, and Zoller (LHZ) described a means to translate a Hamiltonian of *N* spin-^{1}/_{2} particles with “all-to-all” interactions into a larger physical lattice with only on-site energies and local parity constraints. LHZ used this mapping to propose a novel form of quantum annealing. We provide a stabilizer-based formulation within which we can describe both this prior approach and a wide variety of variants. Examples include a triangular array supporting all-to-all connectivity as well as arrangements requiring only 2*N* or *N* log *N* spins but providing interesting bespoke connectivities. Further examples show that arbitrarily high-order logical terms can be efficiently realized, even in a strictly two-dimensional layout. Our stabilizers can correspond to either even-parity constraints, as in the LHZ proposal, or odd-parity constraints. Considering the latter option applied to the original LHZ layout, we note that it may simplify the physical realization because the required ancillas are only spin-^{1}/_{2} systems (that is, qubits rather than qutrits); moreover, the interactions are very simple. We make a preliminary assessment of the impact of these design choices by simulating small (few-qubit) systems; we find some indications that the new variant may maintain a larger minimum energy gap during the annealing process.

## INTRODUCTION

Quantum annealing (QA) is an approach to solving optimization problems, a family of tasks that includes many important examples ranging from financial portfolio management to vehicle routing (*1*, *2*). Typically, the task can be thought of as minimizing a cost function that depends on many variables. In QA, this is done by considering a physical system whose energy corresponds to the cost and by seeking that system’s ground state. One can implement the QA approach using conventional hardware by running an algorithm that mimics quantum behavior (*3*); this is thus a variant of classical simulated annealing (*4*). Alternatively, one can aim to construct real quantum technologies whose components are quantum entities capable of superposition and entanglement. The annealing process can exploit the adiabatic theorem to remain in, or near, the system’s ground state when sufficiently slowly changing parameters (such as a global field). By starting from a Hamiltonian whose ground state can be reliably achieved and morphing slowly into a final Hamiltonian whose energies reflect the cost in the optimization problem, the hope is that measuring the final state reveals a low-cost solution.

There are many interesting questions associated with this approach. The prospects of reaching the ground state of the final Hamiltonian will depend on the rate at which the Hamiltonian is changed versus the size of the gap from the ground state to the lowest excited states; the smaller the gap, the slower the evolution must be (*5*). However, because the gap size cannot be precomputed for problems of meaningful size, it is difficult to be definite about how fast the system can be permitted to evolve or whether the approach can succeed at all given finite temperatures. Thus, the performance of a QA system is hard to predict analytically. Prototype systems have been produced by D-Wave Systems, and several studies have sought to evaluate the power of these systems by empirical testing [see, for example, Rønnow *et al*. (*6*)]. One can also make comparisons with QA simulated by quantum Monte Carlo, although this must be done with caution because there are subtleties with the discretization of time (*7*).

Another important question is that of connectivity. In contrast to conventional computers and circuit model quantum computers, the adiabatic approach involves keeping interactions between qubits “always on” to maintain the energy gap. This implies that the qubits, or spins as we will henceforth refer to them, should continuously maintain direct physical interactions. Ideally, one might wish to be able to connect any physical spin in the device to any other, but in practice, this is inconsistent with interactions that are implemented through short-range physical links. In the D-Wave chips, the set of permitted nonzero links between the physical spins is called the Chimera graph [see Bunyk *et al*. (*8*)]. It is locally rich, but on the large scale, it has the form of a two-dimensional (2D), nearest-neighbor lattice. Typically for a real-world optimization problem, such as the satisfiability problems (*9*, *10*), one would not expect that the variables are tensioned against each other in a pattern that respects any particular geometry. Therefore, for the logical problem to be realized as a physical annealing task, it must be reexpressed in some way.

One solution is based on minor embedding (*11*–*14*): In effect, groups of physical spins are bound together with very strong interactions to form extended single-spin entities. These larger entities have correspondingly more connections to one another. To achieve all-to-all connectivity in this way, the *N* spins of the logical problem must be encoded into Order(*N*^{2}) physical spins. However, even assuming that this cost is permissible (and one should expect that the increased number of physical spins corresponds to a reduction in the crucial energy gap), there is the question of whether this approach is practical. When a large number of physical spins are bound together with achievable interaction strengths, it is not clear whether the extended objects will function as equivalent to single logical spins.

An alternative formulation of the mapping was recently proposed by Lechner, Hauke, and Zoller (LHZ) (*15*). According to this approach, the physical spins now represent the links, or relative orientations, between the logical spins. Thus, there is one physical spin whose role is to represent the relative orientation of logical spins 1 and 2: If they are aligned (↑↑ or ↓↓), then the physical spin will take one value (say ↑), whereas if the logical spins are antialigned (↓↑ or ↑↓), then the physical spin takes the opposite orientation (↓). Because there are *N*(*N* − 1)/2 possible pairings of the *N* logical spins, this leads to the same Order(*N*^{2}) resource cost as the minor embedding approach; however, one avoids the need to bind multiple physical spins into single entities, and the coupling strengths in the logical model conveniently map to single-spin energies in the physical hardware. We note that a paper by Albash *et al*. (*16*), which makes a detailed comparison of minor embedding versus the LHZ approach, has been posted very recently.

Here, we view the LHZ approach within a stabilizer formalism. By means of this general framework, we introduce three new features that significantly extend the potential applications and implementations of the LHZ annealer.

Our analysis begins by noting that the parity constraints of the original LHZ construction correspond to a set of stabilizers. Each stabilizer is a product of physical *z* operators, which we can constrain to one of its eigenvalues, either +1 (even parity) or −1 (odd parity). After recovering the original LHZ construction, we introduce three generalizations: first, a new layout that makes use of all odd-parity constraints. Such a device can make use of a simpler ancillary structure that should prove easier to implement and, as our simple numerical simulations indicate, might present less frequent level crossings. Second, we show that the stabilizer formalism can be used to discover more efficient physical architectures when some of the couplings in the logical spin system are zero. This is significant given that certain NP (nondeterministic, polynomial time) problems, such as graph coloring, are most challenging to solve when their connectivity graph is not complete (*17*, *18*). Whereas the LHZ paper (*15*) established the principle that physical spins can be removed when the logical model has certain simple restrictions, here, we identify general principles that can permit one to tailor a “bespoke” architecture for a given task. We provide examples where 2*N* − 1 and *N* log *N* physical spins realize nontrivial connectivities between *N* logical spins. Finally, our third generalization introduces structures that encode arbitrarily high-order terms in the logical Hamiltonian (such as ) as individual physical spins in a simple 2D layout [in Lechner *et al*. (*15*), three-body terms were realized by moving to a 3D lattice].

Our approach is conceptually straightforward. We take a candidate layout of *N*_{P} physical spins, and we specify *N*_{S} = *N*_{P} − *N* stabilizer constraints. We then nominate *N* of the physical spins, each of which will correspond to a logical spin in the following sense: The *z* operator of a physical spin is identified with the same operator on the logical spin. Finally, we identify the logical *x* operators that are implied by these earlier choices; each will be a product of operators forming a chain that crosses the layout, rather analogously to logical operators in topological codes such as Kitaev’s surface code (*19*). Intersections between these logical *x* chains allow us to find the meaning of each individual physical spin, that is, to identify what product of logical *z* spins it represents.

## RESULTS

### Parity constraint annealing and stabilizer code

We define the logical spin glass model, in which each spin can have an interaction with every other spin as well as an arbitrary local field, as follows(1)

Note that this Hamiltonian is general in the sense that the local fields *h*_{i} and the interaction strengths *J*_{i,j} can take any value. However, it does not contain three-body or higher interaction terms, which would be convenient for optimizing functions containing terms with three or more variables involved. In the final part of the analysis presented here, we will extend our considerations to logical Hamiltonians that do contain arbitrarily higher-order terms. For simplicity, we will now focus on the case where the logical Hamiltonian has the form given above.

The task now is to successfully emulate the physics of this ideal, logical Hamiltonian using real architecture in which a larger number of physical spins interact only locally. We begin by selecting a layout for the physical spins; our first choice will be the 2D lattice with a square unit cell as proposed by LHZ (see Fig. 1). This structure contains *N*(*N* + 1)/2 physical spins; therefore, its full Hilbert space is vastly greater than that of the logical Hamiltonian: We must apply constraints to define a suitable subspace. We will specify a set of mutually commuting stabilizers, each being an operator formed by a product of single-spin Pauli operators. We will require that the state of the system be a mutual eigenstate of all these stabilizers with a specified eigenvalue in each case: either +1 or −1. (Note that this is a slight departure from the usual convention where all stabilizer eigenvalues are +1 because any negative value is absorbed into the definition of the stabilizer itself.) As we enforce each such stabilizer, we will halve the dimension of the compatible Hilbert space. Therefore, we will require *N*(*N* + 1)/2 − *N* = *N*(*N* − 1)/2 stabilizers so that the compliant subspace has the desired dimension, 2^{N}. Our remaining task will be to identify observables in the physical lattice that correspond to the measurement of single spins in the logical Hamiltonian and establish the conditions under which the correspondence is correct.

As shown in Fig. 1A, the physical layout is a lattice of square cells forming a triangular shape. The lattice is composed of *N*(*N* + 1)/2 spins. Figure 1B also introduces the use of additional spins called ancillas, which will be required to enforce the stabilizer constraints in a physically natural way. Their role and structure will be discussed in more detail in the next section. Here, we simply note that when we allude to physical spins without explicitly using the term “ancilla,” we are referring to the *N*(*N* + 1)/2 spins that form the direct physical embodiment. We label each physical spin with two coordinates (*i*, *j*) and each plaquette according to the spin at the top corner; for example, the top plaquette is labeled as [0, 5] in Fig. 1. The reason for this labeling will become apparent; for now, it is simply a systematic way to uniquely tag each spin.

For this formulation to be consistent with the LHZ approach, we select a family of stabilizers that can constrain the parity of the physical spins around each plaquette of the lattice. Plaquette [*i*, *j*] corresponds to a stabilizer(2)where the second case *i* + 2 = *j* simply corresponds to the triangular plaquettes along the base of the lattice. The tilde symbol is used to indicate that the sigma operators apply to physical spins. Each stabilizer is thus the product of Pauli operators acting on the physical spins around the plaquette. Because each Pauli operator has eigenvalues ± 1 corresponding to its spin being oriented in the positive/negative *z* direction, it follows that the stabilizer’s eigenvalues are ± 1. This value can be interpreted as a parity if we take + 1 to indicate “even” and −1 to indicate “odd” in terms of the number of spins aligned along the negative *z* direction. This odd/even label is natural for four-body stabilizers but can be less intuitive for other stabilizers—therefore, we will use the term “odd/even” only for the four-body case, and more generally, we will speak of positive and negative stabilizers.

We will require that the states of interest |*L*〉 be good eigenstates of all these stabilizers, that iswhere we will specify, for every plaquette [*i*, *j*], each individual ν_{i,j} as + 1 or −1. Equivalently, writing *P*_{0} as the projector into the legitimate subspace, we require *S*_{[i,j]}*P*_{0} = ν_{i,j}*P*_{0}. We easily verify that this set of stabilizers mutually commute (all are *z* basis operators) and, moreover, that they are independent: Specifying the eigenvalues of any subset does not constrain the eigenvalues of the remaining ones. This latter property is confirmed by noting that as we consider each new plaquette of the lattice, we are encountering at least one new qubit. (Note that, in contrast, a feature of the 2D toric stabilizer code us that specifying all but one of the stabilizers in a given basis will logically imply the value of the last one.) It is worth remarking that the legitimate states of the physical spins are formally stabilizer states if we opt to absorb the ν_{i,j} factors into the stabilizers, but we find it convenient to regard the stabilizers as fixed entities and ν_{i,j} as their required eigenvalues.

The observable properties of the physical lattice, which will correspond to the single-spin operators (and ) in the logical Hamiltonian, remain to be identified. We call these the logical spin operators. We will simply choose one set, the set, and then attempt to identify the appropriate . Remaining consistent with the LHZ construction, we assign our logical *Z* operators to the individual physical spins on the left side diagonal, that is(3)

Clearly, these logical operators commute both with one another and with the stabilizers (all are *z* basis), and they are independent from one another and from the stabilizers (specifying the states of these logical observables would not constrain any of the stabilizer eigenvalues). Therefore, this choice is valid. With this choice, it is of course possible to read the state of logical spins in the *z* basis by measuring physical spins on the left side of the lattice.

We must now identify the logical spin *x* operators with the same properties of commutation and independence, except that the *z* and *x* operators for the same logical spin should anticommute. No set of operators on single physical spins will have this property; instead, we should look for products of physical spin operators. Consider the logical *x* operator for logical spin *i* = 3. Because it must anticommute with the logical operator , we include in the product of operators. However, it should commute with all our earlier stabilizers; thus, it should include zero, two, or four operators around each plaquette of the lattice (that is, each stabilizer). Finally, it should not include for any *k* ≠ 3 or else it will not commute with other logical spins. Considering these constraints, we are led to a unique solution: a product of operators along the path indicated in red in Fig. 1. The other logical *x* operators have analogous forms, descending from the left side and “bouncing” from the base, as shown in the upper left inset in Fig. 1. Formally(4)where *k* = 1, 2, …, *N*, that is, the logical operator is the product of Pauli operators of the set of physical spins with a label of either *i* = *k* or *j* = *k*.

At this point, we are ready to rewrite the original logical spin Hamiltonian in terms of operators on the physical lattice. Each term of the form simply translates to . Meanwhile, each term translates directly to , but crucially, this can be rewritten as a single physical spin operator , where μ_{i,j} is a certain product of our ν_{i,j} = ± 1 eigenvalues. To see this, consider first the physical spin at (1,2) and, moreover, the value of the operator . For all legitimate states, *S*_{[0,2]}|*L*〉 = ν_{0,2}|*L*〉. However, *S*_{[0,2]} is defined as , and the first two of these operators are logical *Z* operators and therefore must be free to take any value; that is, we can make no constraint on , or their product. Then, to ensure that *S*_{[0,2]}|*L*〉 = ν_{0,2}|*L*〉, we must insist that . Thus, the physical spin at (1,2) is entirely dependent on the physical spins at (0,1) and (0,2), in such a way that the plaquette stabilizer is satisfied. Consequently for the legitimate subspace, we can rewrite the term as .

Having thus established the dependent nature of the physical spin at (1,2), one can repeat the argument for the physical spin at (1,3): The plaquette stabilizer [0,3] involves two logical spins and the spin whose dependence we have just determined; thus, the dependence of the fourth spin is implied. We find that to ensure *S*_{[0,3]}|*L*〉 = ν_{0,3}|*L*〉, we will require . One can proceed to establish the dependence of every remaining physical spin; it is always of the form , where μ_{i,j} is simply a certain product of our chosen stabilizer eigenvalues(5)

In general, this is the product of the ν values in a block of the array; in Fig. 1, the green block corresponds to the set of ν values that must be multiplied to determine μ_{2,4}.

Now, since we chose to identify with the logical *z* operator , we can conclude that each spin (*i*, *j*) encodes the logical product (up to the sign μ_{i,j}). Thus, the motivation for our labeling scheme is apparent. We note from the Fig. 1A inset that physical spin (*i*, *j*) also lies at the intersection of the logical *x* operator chains for logical spins *i* and *j*. In a later section, we will show that this is generally the case, for any lattice: If the logical *x* operator for logical spin *i* intersects with a given physical spin, then is in the product of logical *z* operators to which that spin’s physical *z* operator corresponds. This is a more efficient way to identify the roles of physical spins rather than the step-by-step construction described in the previous paragraph.

We can now conclude that the original logical spin system is realized in a subspace of the physical Hamiltonian(6)

Here, *H*_{C} encapsulates the physics that forces the physical spins to respect the stabilizer constraints. We see that if we make the choice ν_{i,j} = +1 for all *i*, *j*, then we recover exactly the same physical prescription proposed by LHZ.

Presently, we also note that this construction allows us to recover the entire spectrum of the logical Hamiltonian, provided that a parity constraint with sufficient strength is introduced. We prove this statement rigorously (and provide bounds on the relevant parameters that guarantee the equivalence) in Materials and Methods.

The constraint Hamiltonian can always be expressed as(7)

Here, {*E*_{n}} are eigenenergies and {*P*_{n}} are projectors corresponding to eigenstates of *H*_{C}. *E*_{0} is the ground energy, and *P*_{0} corresponds to the ground-state subspace of *H*_{C}.

If *H*_{C} satisfies the following conditions, logical spins are in the ground state of *H*_{logic} (the logical model) when physical spins are in the ground state of *H*_{phys}:

(i) [*P*_{0}, *H*_{phys}] = 0;

(ii) ∀ [*i*, *j*] : *S*_{[i,j]}*P*_{0} = ν_{i,j}*P*_{0} and ;

(iii) , where *U*_{k} and *V*_{k} are unitary operators; and

(iv) , where *E*_{g} is the ground-state energy of *H*_{logic}, (*E*_{0} + *E*_{g}) is the lowest eigenenergy of *H*_{phys} in the subspace 1 − *P*_{0} (*P*_{0}), and 1 is the identity operator.

The proof is given in Materials and Methods. The energy gap between the ground state and the first excited state in the physical model is , where *e*_{logic} is the energy gap in the logical model.

Obviously, one way to write down a suitable constraint Hamiltonian is to simply use the stabilizers themselves. For example, if we choose ν_{i,j} = +1, ∀*i*, *j*, which corresponds to the approach by Lechner *et al*. (*15*), then we can write(8)

In the ground state of *H*_{C}, *E*_{0} = 0 and *S*_{[i,j]} = + 1;, that is, the ground-state subspace is the subspace encoding *N* logical spins and is 2^{N}-dimensional. The projector to the ground subspace can be written as(9)

Because μ_{i,j} = +1 (*S*_{[i,j]}*P*_{0} = *P*_{0}) and *U*_{k} = *V*_{k} = 1, conditions (i), (ii), and (iii) are satisfied. When Δ is large enough, condition (iv) can also be satisfied.

However, a Hamiltonian formed by stabilizers involves three- and four-body interactions, which are unphysical. The use of ancilla qutrits to achieve an equivalent but physically realistic *H*_{C} is discussed further in the next section.

Making other choices for the stabilizer values ν_{i,j} can lead to interesting variants. Consider, for example, the choice ν_{i,j} = −1 for all *i* and *j*. This means that each local stabilizer requires odd parity among its group of physical spins. Consequently, some of the μ values will be −1 according to Eq. 6. Specifically, μ_{i,j} = −1 when *i* is odd and *j* is even. The three cases that occur for the *N* = 5 system are marked in Fig. 1B. Thus, these particular *J*_{i,j} couplings from the original, logical Hamiltonian are multiplied by −1 in the physical Hamiltonian. Presumably, this will not present difficulties for any relevant hardware system because such a system will need to handle both positive and negative *J* values in any case to tackle nontrivial computation problems. However, there is a more profound consequence for the hardware implementation: All our stabilizers now seek to constrain their local groups of spins to odd parities, and this may be easier to realize than the even-parity constraint. Formally, a suitable *H*_{C} can be written in analogous terms to Eq. 9 as , but again, this uses unphysical three- and four-body terms. The interesting distinction is that there is now a natural way of achieving an equivalent *H*_{C} using only a single ancilla qubit for each stabilizer group, as we now discuss.

### Ancillary qubit Ising model

Summarizing the paper so far, the previous section introduced a stabilizer formalism and used it to map a Hamiltonian with *N* logical spins having “all-to-all” interactions to a physical Hamiltonian with *N*(*N* + 1)/2 physical spins but requiring only local interactions. The nature of the local stabilizer rules was defined by our choice of constants ν_{i,j}. We noted that the choice of setting ν_{i,j} = +1 for all *i*, *j* results in the prescription given in LHZ; that is, the local constraints on groups of four or three spins are equivalent to demanding even parity in the number of spins aligned to the negative *z* direction. The next most natural choice is ν_{i,j} = −1 for all *i*, *j*. This leads to some μ_{i,j} = −1 factors in the physical Hamiltonian, but moreover, it inverts the parity requirements on all local groups from even to odd. The distinction between even- and odd-parity constraints seems relatively minor when the constraining Hamiltonian *H*_{C} is written formally using the stabilizers, as in Eq. 9. However, because the stabilizers are three- and four-body terms, this does not suffice as a physical prescription, and instead, one must find a realizable *H*_{C} that is equivalent.

For the even-parity case, LHZ suggested the introduction of an ancilla qutrit, that is, a spin-1 system, for each group of physical spins (they remark that the role can be played equivalently with qubits rather than qutrits). Following their prescription, we can writewhere(10)where is the spin-1 (qutrit) ancilla associated with lattice plaquette [*i*, *j*], with eigenvalues −1, 0, and +1. The sums run over the cases (*i*, *j*), (*i*, *j* − 1), (*i* + 1, *j*), and (*i* + 1, *j* − 1) or just the first three for the *i* + 2 = *j* instances. For these latter instances, as an alternative to giving them a distinct *H*_{[i,j]}, it is possible to instead introduce “dummy” physical spin-^{1}/_{2} systems that form an additional row beneath but which are “locked” to the eigenstate; the physics is identical.

The degenerate ground state of is a subspace formed from all the “correct” even-parity configurations of physical spins where each is matched with a correlated state of the ancilla spin. Note that the ancilla has no role in *H*_{phys} outside of . An intuition behind the use of the ancilla is as follows: Because the term is squared, the lowest energy contribution it can make is 0. Note that the sum of the four operators can take values equal to −4, −2, 0, 2, or 4, and the value of the 4*T*^{Z} operator can be equal to −4, 0, or 4. Therefore, if the physical spins sum to ± 2, there is no assignment of the qutrit that can achieve a total energy of zero, but −4, 0, and 4 are acceptable. These are of course precisely the even-parity states.

Now, we consider the equivalent cases for our “always odd-parity” scenario, which we obtained by considering the ν_{i,j} = − 1 case. Again, we must identify a simple physical *H*_{C} with a correct degenerate ground state. As with the LHZ example, we again use the technique of squaring a sum of operators, but now, we find that the ancilla needs to take only two values. Specifically, we opt forwhere(11)

Here, (note the square brackets [ ] in the subscript) is the spin-^{1}/_{2} ancilla associated with lattice plaquette [*i*, *j*]. As before, the sums run over the cases (*i*, *j*), (*i*, *j* − 1), (*i* + 1, *j*), and (*i* + 1, *j* − 1) or just the first three for the *i* + 2 = *j* instances. Again, one could introduce a row of dummy physical spins below the active array to make all plaquettes of the array square so that the *i* + 2 = *j* cases are no longer special. This follows the form of the LHZ construct exactly, except for the term, which, of course, has values ± 2. The same intuition just described therefore leads us to see that the ground state will be spanned by states where the yields ± 2, that is, the odd-parity states. In Materials and Methods, we show that such a constraint Hamiltonian satisfies conditions (i) to (iv) if Δ is large enough.

The required interactions are encouragingly simple. Assuming that the physical implementation uses row dummy spins, then expanding the squared expression in Eq. 14 and neglecting global shifts gives(12)where the *a* and *b* indices here run over the local physical spins as usual. This appears to be a potential advantage over the even-parity solution with its qutrit (spin-1) ancilla, not only because qubit (spin-^{1}/_{2}) systems may be easier to realize but also because the expansion of Eq. 12 has terms (*T*^{Z})^{2}, that may be awkward to realize; for the odd-parity version, the equivalent terms are merely the identity and can be neglected.

Equation 15 involves interactions between all four spins defining the lattice plaquette and an interaction of the same form but double the strength between each of these and their shared ancilla spin. The ratio of 2 between these strengths is not required; it is optimal, but any ratio greater than 1 but less than 3 will correctly reproduce the effect of the stabilizers. It is interesting to speculate that this set of interactions might be very naturally realized by connecting the four physical spins to a common resonator and coupling this group’s ancilla to the same resonator with twice the coupling strength. This is indicated schematically in Fig. 1C.

We note that very recently, two new papers (*20*, *21*) that discuss superconducting systems capable of supporting *M*-body parity constraints (stabilizers, in our language) have been posted online. Another study (*22*) has shown how these *M*-body parity constraints can be implemented on the Chimera graph; it would be interesting to contrast implementations on that established platform with the new, dedicated stabilizer-based architectures we envisage here.

### Spectrum and numerical results

The preceding sections provide an analytic treatment within which both the LHZ proposal and a variant proposal based on odd parity have emerged as examples of local Hamiltonians that can simulate all-to-all interactions. Before moving on to considering new forms of physical spin layout, we wish to compare these two alternatives using a numerical study of small systems.

Generally, the analytic conclusions described earlier are valid when the energy Δ associated with the parity-constraining terms is sufficiently large compared to other terms. It is interesting to see how these two approaches perform for finite values of the parameters.

We performed our simulations using exact diagonalization. Because the number of ancillas required is (*N* − 1)*N*/2, the total number of physical spins required is (*N* + 1)*N*/2 + *N*(*N* − 1)/2 = *N*^{2} (if we consider triangular constraints in the bottom layer). This quadratic scaling severely limits our ability to simulate even small systems numerically, especially when using ancillary qutrits (see Table 1).

As discussed by Lechner *et al*. (*15*), the strength of the constraint terms Δ is one of the key adjustable parameters of the architecture. The analytic arguments in the preceding section rely on Δ being the dominant energy at the end of the adiabatic sweep such that the correct stabilizers are enforced. On the other hand, we also wish for the energy scales (*h* and *J*) to be as large as possible because their magnitude will influence the gap between the ground state of the logical Hamiltonian and its excited states and thus determine the speed and practicality of QA or other adiabatic processes. Consequently, it is interesting to see how close we can permit those lesser energy scales to come to Δ or, in other words, how modest a ratio will suffice.

Presently, we note that there is another reason to be interested in the modest values of this ratio: the detectability and correctability of errors in the system’s evolution. In our simulations, we benchmark the different parity-enforcing terms with two different metrics while varying the strength of Δ. We use a random Ising model where the *J*_{ij} elements are drawn from a uniform distribution in [−*J*, *J*]. The energies *h*_{i} are drawn from the same distribution. The quantity *J*_{av} is the average unsigned value, that is, *J*/2. We will be interested in the ratio *R* between Δ, the energy scale of the parity-constraining terms, and *J*_{av}.

Following along the same lines as the numerical analysis in Lechner *et al*. (*15*), for our first metric, we take the system to be at the end of its adiabatic sweep, and we find the gap between the ground state and lowest excited state(s). We find this gap for the physical system, that is, the *N*(*N* + 1)/2 array of physical spins, and see how it deviates from the same quantity found using the ideal logical Hamiltonian. That is to say, we plotwhere *e*_{logic} = λ_{logic}(1) − λ_{logic}(0), *e*_{phys} = λ_{phys}(1) − λ_{phys}(0), and λ(*i*) is the *i*th eigenvalue of a given architecture. Locating the value of Δ where this deviation largely vanishes gives insight into how large Δ should be for the mapping process to be successful. Figure 2 shows the results for systems of *N* = 3 and *N* = 4 logical spins (that is, 9 and 16 physical spins, respectively). The behavior is as expected; there is no significant difference between the even-parity physical architecture (with its spin-1 qutrit ancillas) and the odd-parity system (using spin-^{1}/_{2} qubit ancillas).

Perhaps the more crucial energy in a QA process is not the gap at the end of the anneal but rather the minimum gap that occurs at any time throughout the evolution. It is this gap that is usually used to characterize the stability of the process and the speed with which it can be completed. Our second metric concerns this minimum gap as we sweep between an initial Hamiltonian (where the sum runs over all the physical spins) and the final form. We plot the ratio χ of the minimum gap occurring in the physical architecture (which depends on *R*) to that which would occur in the logical system

In Fig. 3, we show the behavior of χ for the smallest two nontrivial systems: *N* = 2 and *N* = 3 logical spins. Each data point is an average of 400 simulations, and we have chosen to find the average of and then reciprocate; this emphasizes cases where the gap in the physical system vanishes (or nearly vanishes). We do see some variation between the behavior of the even-parity–constraining system with its spin-1 ancillas and the alternative odd-parity architecture using spin-^{1}/_{2} ancillas. The curve of the former approaches the *x* axis many times, suggesting level crossing for the ancillary qutrit implementation that is not present when using the ancillary qubit version.

### Remarks on error detection and correction

The analytics portion of this paper stresses the significance of the stabilizer-enforcing terms and may lead to the supposition that we would like to have Δ ≫ *J*, *h*. However, from our small system numerics, we note that it can suffice for these energy ratios to be modest, and from Fig. 3, we see that larger values of this ratio can be associated with smaller values of the gap. This may lead to speculation that moderately large values of the ratio *R* = Δ/*J*_{av} are optimal, and the following speculative line of thought leads to the same conclusion.

As pointed out by Pastawski and Preskill (*23*), the multiple parity constraints applied to the physical system have the consequence that, if the final state is read out incorrectly, it is highly likely that classical postprocessing can recover the correct set of measurements. The threshold for error correction, that is, the number of spins that would need to be misread before the correct state cannot be inferred, is very high. Can this permit us to correct an error that occurs during the evolution, that is, a jump from the ground state to an excited state? This depends on whether the excited state in question has different parity values. If *R* is very large compared to other energies, then the spectrum will be such that that the low-lying excited states have correct parity, and therefore jumps to these states are uncorrectable (and undetectable, except that the final measured state constitutes a poor solution to the optimization problem). However, opting for a more modest *R* value may permit the low-lying excited states to violate the parity constraints and thus conceivably permit us to correct them after measurement. To explore this point further, suppose that a system is configured such that the constraints Δ will achieve the highest value possible at the end of the anneal, given the physical nature of the hardware; further, suppose that the strengths of the *J* and *h* terms can be freely adjusted. We hypothesize that, ideally, their strength should be some significant portion of Δ, so that *R* is only modest. In this way, we would hope to overlap the spectrum of the two parity subspaces without increasing the possibility of having an error. Exploring the validity of this principle would be an interesting challenge for future work.

### New layouts supporting arbitrary connectivity

So far, we have used our stabilizer formalism only to recover the proposal of LHZ, but including the freedom to choose odd- versus even-parity constraints. However, the stabilizer picture can allow us to design a wide range of physical layouts to realize different levels of connectivity and/or higher-order correlations compared to the two-body case.

Before varying the nature of the logical Hamiltonian, we note that our approach can guide us to layouts that support exactly the same logical Hamiltonian as the LHZ construction but which have different kinds of stabilizers (rather than merely different stabilizer signs, as considered earlier). Perhaps the simplest set of stabilizers is the triangular pattern shown in Fig. 4A. When finding sets of stabilizers such as these, it is helpful to remember the principle that any product of stabilizers is also a stabilizer. This can allow one to translate from stabilizers that are nonlocal in the physical layout to a local set. For example, the product of the three stabilizers within the large blue dashed triangle is equivalent to the stabilizer , which involves only the spins at the corners of that triangle (because each spin in the middle of an edge appears twice in the product, the spins canceled out). This layout, or others generated using the same principles, may prove to be more natural to implement with a given technology.

We now proceed to introduce the formalism that will allow us to embed Hamiltonians with bespoke connectivity. For the moment, we will continue to restrict our logical Hamiltonians to involve only one- and two-body terms. We therefore consider a connectivity graph with vertices *V*, representing the logical spins, and edges *E*, representing the required terms in the logical Hamiltonian (Eq. 1). That is to say, if *J*_{i,j} ≠ 0, then the edge linking vertex *i* and vertex *j* are present in set *E*. We will need |*V*| + |*E*| physical spins if we wish to encode |*V*| = *N* logical spins, that is, one physical spin (0, *i*) for each vertex *i* ∈ *V* and one physical spin (*i*, *j*) for each edge (*i*, *j*) ∈ *E*.

We only need to follow our earlier prescription: We select *N* of the physical spins to represent the logical *z* operators; that is, we identify the physical spins (0, *i*) for which is identified with . We then define |*E*| independent stabilizers, as before, specifying each stabilizer as a product of operators. Finally, we determine the logical *x* operators that are implied by these choices, recalling the following requirements: operator must commute with all other logical *x* operators and with all the stabilizers, and it must commute with all while anticommuting with . As before, this leads us to the rule that the product of physical operators, which constitutes a given logical *x* operator , must (i) include , (ii) exclude all , and (iii) include an even number (or zero) of operators that address spins in each stabilizer.

Assuming that all logical *x* operators have been identified, we can now identify the roles of the remaining physical spins using the following rule: The physical spin where logical *x* operators and intersect is to be labeled (*i*, *j*). This spin’s physical *z* operator is identical to the logical two-body term , up to a sign μ_{i,j}. The sign is simply a function of which stabilizers we have chosen to be negative, as in the example leading to Eq. 6. In an earlier section, we alluded to this convenient rule, and we now justify it.

Together, the logical σ^{Z} operators and the stabilizers form a total of |*V*| + |*E*| independent operators, each of which is either a physical operator or a product of such operators. From their independence, it follows that we must be able to express any operator as a product of logical operators and stabilizers, that is

We can determine which logical σ^{Z} operators are in this product by considering logical σ^{X} operators. If is in the product, anticommutes with ; otherwise, commutes with . However, from our definition of the logical *x* operators, only and anticommute with ; thus, we conclude that only and are in the product, that is

Therefore, the Ising interaction in the logical model can be mapped to in the physical model (up to a sign determined by the value of stabilizers).

In practice, this means that if we wish to have a physical spin representing a two-body term in the logical Hamiltonian, that is, if that edge exists in *E*, then the lines of physical spins associated with the two logical *x* operators must cross. This provides a design principle to create a bespoke physical array to represent a given logical Hamiltonian. We can see that the square lattice of LHZ in Fig. 1 and the triangular lattice in Fig. 4A meet this condition for a fully connected graph; that is, intersects with every other logical *x* operator, and so all edges exist. However, the layout in Fig. 4B supports a more restricted graph, that is, a three-tier hierarchical tree, and consequently requires only 2*N* − 1 physical spins for *N* logical variables. For a logical Hamiltonian with exactly this connectivity, this bespoke layout therefore provides a more efficient representation, and presumably, the gap during annealing may be larger.

Figure 5 (A and B) provides further examples of interesting bespoke layouts. The layout in Fig. 5A(i) is a simple pattern with a logical connectivity graph such that vertices (that is, logical spins) 1 to 5 are connected to all other vertices, whereas vertex 6 and higher do not interconnect among themselves. An interesting variant occurs if we remove one physical spin and correspondingly reduce the stabilizer count by one, as shown in Fig. 5A(ii). Note that a central group of four square stabilizers has been replaced with two triangular stabilizers and a single hexagonal stabilizer. [As an aside, we note that a suitable six-body, negative-parity stabilizer can be realized using only two ancilla qubits (see Materials and Methods).] The effect of this central disruption to the layout is that it effectively “reflects” the logical *x* operator chains that would have passed through it. This alters the logical connectivity graph (for example, logical spin number 2 now only connects to the logical spins numbered 1, 3, 4, and 5). There are now two physical spins for each of the labels , , and . This does not present an in-principle difficulty when translating from the logical Hamiltonian to the local fields on the physical spins; we simply need to ensure that the total field on the two spins labeled is equal to the factor *J*_{2,3} in the logical Hamiltonian and similarly for the other local fields.

The “reflecting” stabilizer in Fig. 5A(ii) can be used repeatedly within a larger lattice to control the interactions between logical *x* operators and thus define the logical connectivity graph. This is illustrated in Fig. 5B. Here, the layout realizes a rather complex connectivity graph in which there are a small number of highly connected vertices, a larger number of more modestly connected nodes, and so on. One might, for example, choose the width of the strip of physical spins to be log (*N*) while its length is *N*, where *N* is the number of logical spins. With these *N* log (*N*) spins, one could engineer a hierarchy where one logical spin connects to all others, two connect to 50% of the set, four connect to 25%, and so on.

### New layouts supporting higher-order interactions

Finally, we consider how the stabilizer picture presented here generalizes to support terms in the logical Hamiltonian that are higher than two-body terms. Previously, we noted that when two logical *x* operators *i* and *j* intersect, the physical spin at the intersection necessarily represents the two-body logical operator . However, it is possible for multiple logical operators to intersect at a specific physical spin, as shown in Fig. 6A. Then, the same arguments developed above apply, so that when the logical *x* operators for logical spins *i*, *j*,…, *p* all intersect, then the physical operator on that spin will correspond to the logical product , up to a sign determined by the use of negative stabilizer constraints.

Figure 6B provides a second illustration of how higher-order terms can be introduced. The figure shows a region of the standard LHZ layout, that is, a larger version of the pattern shown in Fig. 1. There are three additional physical spins (green circles) and, correspondingly, three additional stabilizers (gray-shaded regions). Each of the new physical spins provides a high-order logical correlation, as specified in the caption.

Note that the ideas presented here could potentially be used in addition to the principle of minor embedding rather than replacing that approach outright. Starting from the original logical Hamiltonian, which directly corresponds to the structure of some computational task, one might use the minor embedding principle to derive a second, intermediate logical Hamiltonian with a larger number of spins. This intermediate Hamiltonian could then be translated into a stabilizer-based layout as described here. The potential benefit would be an increased flexibility in the connectivity offered by a given layout pattern.

## DISCUSSION

We began by presenting a stabilizer formulation for the problem of mapping a Hamiltonian with *N* all-to-all interacting spins to a Hamiltonian of *N*(*N* + 1)/2 spins with only local interactions. As a first illustration of the approach, we took the recent work of Lechner *et al*. (*15*) and adopted their physical spin layout. We noted the resulting logical *z* and logical *x* operators; the latter are chains of operators that traverse the lattice (as occurs in topological error-correcting codes). We recovered the LHZ result, and we also identified an interesting variant based on constraining local groups of spins to odd parity, rather than to even parity. This variant has an attractively simple realization in terms of pure Ising interactions and ancilla qubits (rather than qutrits) and might perhaps be realized through commonly shared resonators. We numerically verified our results for small systems of *N* = 2, 3, 4 logical spins. There are some indications that our new odd-parity, qubit-ancilla model may maintain a more reliable energy gap during an anneal.

Having thus demonstrated our formalism in an established context, we proceed to show how it can be used for a wide range of different physical spin layouts. We display a triangle lattice for all-to-all connectivity, before moving on to create layouts, which support specific (less than all-to-all) connectivities with the advantage that fewer than Order (*N*^{2}) physical spins are needed. Our examples include a three-tier tree structure requiring 2*N* − 1 physical spins and a more complex pattern offering a range of connectivities with *N* log (*N*) physical spins. Finally, we show that there is no constraint to two-body logical terms; even within a strictly 2D layout, arbitrarily high-order logical terms can be realized in a natural way.

## MATERIALS AND METHODS

### Sufficient condition of the parity constraint

Because [*P*_{0}, *H*_{phys}] = 0, *P*_{0} is a subspace of *H*_{phys}, ; that is, *H*_{phys} can be rewritten as *H*_{phys} = *P*_{0}*H*_{phys}*P*_{0} + (1 − *P*_{0})*H*_{phys}(1 − *P*_{0}). In the subspace *P*_{0}, the spectrum is determined by the effective Hamiltonian *H*_{eff} = *P*_{0}*H*_{phys}*P*_{0} = *H*_{phys}*P*_{0}.

Using stabilizers, single-spin Pauli operators can be expressed as(13)where the product of stabilizers corresponds to a rectangular area (with a corner cut) composed of plaquettes in the lattice (see Fig. 1): The bottom plaquette is a triangle plaquette rather than a square, the top left side of the area connects spins (0, *i*) and (0, *j*), and the top right side of the area connects spins (*i*, 0) and (0, *j*). As an example, the area corresponding to is highlighted in green in Fig. 1. One can find that, in the product of stabilizers, each Pauli operator occurs for even times, except , , and . Using Eq. 16 and condition (ii), we have(14)*P*_{0} can be written as(15)where α = (α_{1}, α_{2}, …, α_{N}) is a string of α_{k} = ±1, and , with(16)being the projector to the subspace where logical spin operators take eigenvalues {α_{k}}. Because , {*P*_{0,α}} are projectors; that is, .

For any two sets of eigenvalues α and α′, we introduce a unitary operator(17)Then(18)

Here, we have used condition (iii). Therefore, dimensions of subspaces {*P*_{0,α}} are the same, and the dimension *D* = Tr(*P*_{0,α}) = Tr(*P*_{0})/2^{N}.

Common eigenstates of are eigenstates of *H*_{logic}, and the eigenvalue only depends on α, that is(19)where(20)

Then, the effective Hamiltonian can be rewritten in the diagonalized form(21)

Here, *E*_{0} is the ground-state energy of the constraint Hamiltonian *H*_{C}, is the energy of the logical-spin configuration α in the logical Hamiltonian *H*_{logic} and *P*_{0,α} is the projector to the corresponding eigenstate subspace. Therefore, we see that, in the subspace *P*_{0}, the physical Hamiltonian *H*_{phys} and the logical Hamiltonian *H*_{logic} have the same spectrum. We would like to remark that not only the spectrum but also the eigenstates of the two Hamiltonians coincide with each other in the subspace *P*_{0}, ; that is, the same eigenenergy corresponds to the same configuration α of logical spins.

The whole spectrum of *H*_{phys} is composed of the spectrum in the subspace *P*_{0} (the spectrum of *H*_{eff}) and the spectrum in other subspaces [the spectrum of (1 − *P*_{0})*H*_{phys}(1 − *P*_{0})]. Here, the ground-state energy of *H*_{eff} is and the ground-state energy of (1 − *P*_{0})*H*_{phys}(1 − *P*_{0}) is . Therefore, when , *E*_{0,g} is the ground-state energy of the whole spectrum; that is, the ground state of *H*_{phys} is the ground state of *H*_{eff}. We note that in the ground state of *H*_{eff}, the logical spins are in the ground state of *H*_{logic}.

Assuming that *E*_{1} is the first excited state energy of the constraint Hamiltonian *H*_{C}, the ground state energy of the (1 − *P*_{0})*H*_{phys}(1 − *P*_{0}) has a lower bound , where . Because , *E*_{g} has an upper bound *E*_{g} ≤ 0. Therefore, when *E*_{1} − *E*_{0} > *E*_{max}, the condition is satisfied, and the ground state of *H*_{phys} corresponds to the ground state of *H*_{logic}. Finally, because *E*_{max} is the upper bound of , when *E*_{1} − *E*_{0} > 2*E*_{max}, is higher than the energy of any state in the subspace *P*_{0}, and the whole spectrum of *H*_{logic} is reproduced by low-lying states of *H*_{phys}.

### Group subspace of the ancillary qubit model

We define *M*_{[i,j]} as the number of excitations (number of spins along the −*z* direction), and(22)

Here, the sums run over the cases (*i*, *j*), (*i*, *j* − 1), (*i* + 1, *j*), and (*i* + 1, *j* − 1) or just the first three for the *i* + 2 = *j* instances. Thus, in the ground state of *H*_{C}, *E*_{0} = 0, *M*_{[i,j]} = 1 or 3, and *S*_{[i,j]} = −1 for all stabilizers.

The projector to the ground state subspace is(23)where(24) is the projector to the subspace with *M*_{[i,j]} = *m*, and(25)

Here, *M*_{max} is the maximum number of excitations, that is(26)and(27)

Therefore, [*P*_{0}, *H*_{phys}] = 0 and *S*_{[i,j]}*P*_{0} = −*P*_{0}. Taking μ_{i,j} = (−1)^{i(j − i)}, conditions (i) and (ii) are satisfied.

We take(28)which are unitary operators describing controlled flip operations on ancillary spins. The ancillary spin [*i*, *j*] is flipped if and only if *M*_{[i,j]} = 1. Then, we have(29)that is, *P*_{0} is 2^{N}-dimensional. Because(30)we have . Therefore, , and condition (iii) is satisfied. When Δ is large enough, condition (iv) can be satisfied.

### Ancilla constructions for many-body stabilizers

Suppose that we wish to constrain some odd number *M* of physical spins to a given eigenvalue, + 1 or −1, of the stabilizer . We can do so by including the following term into the constraint Hamiltonian *H*_{C}

Here, as in the main text, the square brackets [ ] in the subscript denote an ancilla, and the number of ancillas *P* is (*M* − 1)/2. The term in the inner brackets has eigenvalues *M*, *M* − 4, …, 2 − *M*. These are precisely the permitted values of the sum if we are in a positive eigenstate of the stabilizer, so that subtracting them implies that only the acceptable states can achieve the minimum energy of this complete term (the minimum being zero since it is squared). The negative stabilizer is enforced by choosing to add rather than subtract the inner bracket for an analogous reason.

Multiplying out this term will produce terms between the various spins involved, as well as a series of single-spin terms, which must be accounted for (in the case of the physical spins) by adjusting the on-site *J* values.

Notice that for this case of odd *M*, the same number of ancilla spins is required regardless of whether we wish to enforce a positive or a negative value for the stabilizer. If instead we wish to constrain some even number *M* of physical spins to a given eigenvalue of our stabilizer, then the number of ancillas required depends on the chosen sign. In either case, the form of the term to include in *H*_{C} is the following

However, the number of ancillas *P* is equal to *M*/2 if the stabilizer constraint is negative and *M*/2 + 1 if the constraint is positive. This is because the positive stabilizer eigenstates have *M* − 1 different possible eigenvalues of the total *z* spin, (namely, *M*, *M* − 4, …, −*M*). Meanwhile, the negative stabilizer eigenstates have *M* − 2 possible eigenvalues of the total *z* spin (namely, *M* − 1, *M* − 5, …, 1 −*M*).

For the case of *M* = 4 spin stabilizers, following LHZ, one can use a qutrit rather than a qubit, but regardless of this choice, the ancilla structure is simpler if one opts to enforce negative stabilizers.

This is an open-access article distributed under the terms of the Creative Commons Attribution license, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

## REFERENCES AND NOTES

**Acknowledgments:**We would like to acknowledge the use of the University of Oxford Advanced Research Computing (ARC) facility in carrying out this work (

*24*).

**Funding:**This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) National Quantum Technology Hub in Networked Quantum Information Processing (EP/M013243/1). A.R. is supported by an EPSRC Doctoral Training Partnerships Scholarship.

**Author contributions:**Y.L. developed the theoretical framework. A.R. conducted the simulations. All authors developed the lattice designs and wrote the manuscript.

**Competing interests:**The authors declare that they have no competing interests.

**Data and materials availability:**All data needed to evaluate the conclusions in the paper are present in the paper. Additional data related to this paper may be requested from the authors.

- Copyright © 2016, The Authors