The idea of perturbation gadgets is to introduce a mediator qubit in a system with the effect of simulating the low–energy spectrum of a target Hamiltonian via local interactions between the mediator qubit and the system qubits. A prototypical example is the simulation of ferromagnetic spin interactions using antiferromagnetic ones. To elaborate, consider a rudimentary example involving a two–particle ferromagnetic interaction, where spins tend to align. Here, we introduce a mediator gadget that engages in an antiferromagnetic interaction with each of the original particles. Assuming, without loss of generality, that the original spins are vertically aligned, the net outcome of the mediator particle being in a downward spin state is an effective ferromagnetic interaction between the original particles. Moreover, this interaction indirectly connects the two original particles.

Figure (a): A ferromagnetic interaction between two spin particles.

Figure (b): A system of three spins with the top particle local interacting antiferromagnetically with the others. The local antiferromagnetic interactions simulate a ferromagnetic interaction between the two bottom particles. The solid lines represent proper interactions and the dashed line represents a simulated interaction (as in these particles do not directly interact).

The two main methods used in the literature to study this effect are the self–energy method and the Schrieffer–Wolff transformation. The self–energy method is a perturbative method that uses the Dyson equation to calculate the effective Hamiltonian. The Schrieffer–Wolff transformation uses a unitary transformation to calculate the effective Hamiltonian. The unitary transformation decouples the low–energy subspace from the high–energy subspace.

The usual format of reduction proofs is to start from a known problem that is complete for some complexity class. We commonly refer to this as the target Hamiltonian, $H_{\text{targ.}}$, which acts on an $2^n$–dimensional Hilbert space $\mathcal{H} = \mathcal{L}_- \oplus \mathcal{L}_+$; $\mathcal{L}_-$ refers to the low–energy eigenspace and $\mathcal{L}_+$ the high–energy eigenspace. The reduction aims to show that a Hamiltonian, $H_{\text{sim}}$ that acts on a larger Hilbert space $\widetilde {\mathcal{H}} = \widetilde {\mathcal{L}}_- \oplus \widetilde {\mathcal{L}}_+$, can be constructed to have a low–energy subspace that approximates that of the target Hamiltonian. To formalise this, we say there exists an isometry $\widetilde {\mathcal{E}}: \mathcal{H} \rightarrow \mathcal{H}_{\text{sim}}$ such that $\text{Im}(\widetilde {\mathcal{E}}) := \mathcal{L}_-(H_{\text{targ.}})$ and $||\widetilde {\mathcal{E}}^\dagger H_{\text{sim}} \widetilde {\mathcal{E}}|| \approx ||H_{\text{targ.}}||$.

Definition ([PM15]) Let $H$ be a Hamiltonian acting on a $2^n$–dimensional Hilbert space $\mathcal{H} = \mathcal{L}_- \oplus \mathcal{L}_+$. Let $H_{\text{sim}}$ be a Hamiltonian acting on a $2^m$–dimensional Hilbert space, with $m \gt n$ and where $\widetilde {\mathcal{H}} = \widetilde {\mathcal{L}}_- \oplus \widetilde {\mathcal{L}}_+$. Let $\mathcal{E}: \mathcal{H}\rightarrow \widetilde {\mathcal{H}}$ be an isometry. We say that $H_{\text{sim}}$ is an effective Hamiltonian, or a $(\eta, \epsilon)$ simulator, for $H$ if these exists an isometry $\widetilde {\mathcal{E}}: \mathcal{H} \rightarrow \mathcal{H}_{\text{sim}}$ such that
  1. $\text{Im}(\widetilde {\mathcal{E}}) := \mathcal{L}_-(H)$.
  2. $||H - \widetilde {\mathcal{E}}^\dagger H_{\text{sim}} \widetilde {\mathcal{E}}|| \leq \epsilon$.
  3. $||\mathcal{E} - \widetilde {\mathcal{E}}|| \leq \eta$.

To understand what this definition is saying we can again turn to the ferromagnetic example above. Here we can envision the initial system of two spins having a Hamiltonian of the form $H = -\frac{\Delta}{2} ZZ$. Clearly this has a low–energy subspace of $\mathcal{L}_- = \{\ket{00}, \ket{11}\}$ (aligned spins) and a high–energy subspace of $\mathcal{L}_+ = \{\ket{01}, \ket{10}\}$ (anti–aligned spins). The spectral gap is $\Delta$. We can now discuss the form of the three spin situation (where particles interact antiferromagnetically); the Hamiltonian for this system is over three spins rather than two. Its exact form is inferred from the ideas below but we can still describe certain pieces of it. Recall that the two non–mediator spins do not interact directly. The antiferromagnetic interaction is one that tends to anti–align the spins; an antiferromagnetic interaction can be described by the Hamiltonian $H = \alpha ZZ$ where $\alpha \gt 0$. Notice that we also wanted the simulator Hilbert space to be split. One way to achieve this is to split energy levels of the mediator spin. For example, consider the Hamiltonian $H = \beta (\mathbb{I} - Z)$ where $\beta \gt 0$; this Hamiltonian has a low–energy subspace of $\mathcal{L}_- = \{\ket{0}\}$ and a high–energy subspace of $\mathcal{L}_+ = \{\ket{1}\}$. If we are then able to find an approximate isometry that has the properties of the above definition, we can say that the three spin system is a $(\eta, \epsilon)$ simulator for the two spin system.

We will denote a perturbed operator using the tilde hat, $\widetilde{O}$. A perturbated Hamiltonian $\widetilde {H}$ is comprised of two key components: an unperturbed Hamiltonian $H$ and a perturbation term $V$. The unperturbed Hamiltonian has a split Hilbert space, $\mathcal{H} = \mathcal{L}_- \oplus \mathcal{L}_+$. By split, we mean that there is a significantly sized spectral gap, $\Delta\gg 1$, between the two subspaces. The perturbation term is chosen such that $||V||\leq \Delta/2$ to avoid mixing the low–energy subspace with the high–energy subspace. Define the projector onto the low–energy subspace as $\Pi_-$ and the projector onto the high–energy subspace as $\Pi_+$. Then, $O_{\pm\pm} = \Pi_\pm O \Pi_\pm$.

The Schrieffer–Wolff transformation is a unitary transformation on the simulator Hilbert space defined as $e^S$ where $S$ is an anti–Hermitian operator. The operator requires the transformed Hamiltonian to be block diagonal with respect to the projectors $\Pi_\pm$. The effective Hamiltonian is then defined as $H_{\text{eff.}} = (e^{-S} H_{\text{sim}} e^S)_{--}$ which can be approximated using a truncated series. For the purposes of this work we need only go to second–order in the series. There are Lemmas that completely specify the form of the effective Hamiltonian for first–, second– and third–order terms [BH16]. A simplified version of the second–order Lemma is

Lemma (Second–order Reduction [BH16]) Let $H_{\text{sim}} = H + \sqrt{\Delta}\;V_{\text{main}} + V_{\text{extra}}$ be chosen such that $\lambda(H_{++})\geq \Delta$, $H_{--}, H_{-+} = 0$, $(V_{\text{extra}})_{-+}, (V_{\text{main}})_{--} = 0$ and $$ ||\bar{H}_{\text{targ.}} - (V_{\text{extra}})_{--} + (V_{\text{main}})_{-+}H^{-1}(V_{\text{main}})_{+-}|| \leq \epsilon/2. $$ For appropriate choices of $||V_{\text{main}}||, ||V_{\text{extra}}||$ and $\Delta$, $H_{\text{sim}}$ is an $(\eta, \epsilon)$ simulator for $H_{\text{targ.}}$.

The term $\bar{H}_{\text{targ.}} = \mathcal{E}^\dagger H_{\text{targ.}}\mathcal{E}$ is commonly called the logical encoding of the target Hamiltonian. Using the above Lemma, the general recipe for finding the effective Hamiltonian of the perturbative reductions, up to second–order, is $$ H_{\text{eff.}} = V_{--} - V_{-+}H^{-1}V_{+-}. $$

One subtle condition that influences the construction of the gadgets is the allowed interaction terms of the Hamiltonian in question. For example, as will be demonstrated, introducing a mediator qubit $c$ that interacts with some system qubit $i$ via the Pauli–$X$ unitary demands that the original Hamiltonian must permit such interactions. To delve further into this point, let's consider a Hamiltonian instance with interactions from the set ${Y, Z}$. In this case, the interaction term between a mediator and a system qubit of the form $X_c\otimes Y_j$ is illegal, as such a term is not allowed in this system. This restriction underscores the importance of aligning the chosen mediator interactions with the permissible terms dictated by the Hamiltonian.

It should be noted that there are certain conditions that must be in place in order for the proper use of the perturbation gadgets. For example, requiring the interaction strengths to be particular large is a common condition. These ideas are not developed here, rather we provide an overview of a use case for each gadget.

As a concluding remark, one can conceptualize perturbation gadget reductions as follows: "The complexity of determining the ground state energy of Hamiltonian $A$ is known. If I can utilise Hamiltonian $A$ to emulate Hamiltonian $B$", ensuring their low–energy sectors are $\epsilon$–close, "then, deducing the ground state energy of Hamiltonian $B$ becomes, at the very least, as challenging as solving the same problem for Hamiltonian $A$." To illustrate this concept with a straightforward example from the initial discussion, consider the scenario where an antiferromagnetic system has the capacity to simulate the general system. Consequently, the antiferromagnetic system is at least as hard as the general system. This serves as a highlight as to the potential for perturbation gadgets to establish connections between the complexity of different Hamiltonian systems.

Oliveira and Terhal Gadgets

Given two disjoint subsets of qubits $a$ and $b$, influenced by some $k$–local interactions, succinctly expressed as $A\otimes B$, where $A$ acts over qubits $a$ and $B$ over qubits $b$. More specifically, $A = \bigotimes_{a_i \in a}A_{a_i}$ and $B = \bigotimes_{b_i \in b}B_{b_i}$. Let the cardinality of $a$ and $b$ be upper bounded by $\lceil k/2 \rceil$; the goal of the subdivision gadget is to introduce a mediator qubit, $c$, to reduce the degree of locality and approximate the original $k$–local interaction $A\otimes B$, using $(\lceil k/2 \rceil + 1)$–local interactions.

This gadget can be used to reduce $k$–local interactions, for $k\gt3$, to $3$–local ones via repeated application 'in parallel'. This can trivially be seen with a small calculation. For this example, the isometry is defined as, $\bar{H}_{\text{targ}} \sim H_{\text{targ}}\otimes\ketbra{0}{0}$; where the final '$\ketbra{0}{0}$' is for the mediator qubit and, as we will see, is the ground state. We define the following equations: $$\widetilde{H} = H + V$$ $$H = \Delta \ketbra{1}{1}_c$$ $$V_{\text{main}} = (A - B)X_c$$ $$V_{\text{extra}} = \frac{1}{2}(A^2 + B^2)$$

Up to second order in the self–energy expansion, we have $$ \begin{align*} H_{\text{eff.}} &= H_{-} + V_{-} + V_{-+}\frac{-1}{\Delta}V_{+-} \\ &= 0 + \frac{1}{2}\left(A^2 + B^2 \right)\ketbra{0}{0} - \frac{1}{\Delta}\left(\frac{\Delta}{2} (A^2+B^2 - 2AB) \right)\ketbra{0}{0} \\ &= AB\ketbra{0}{0} \end{align*} $$

Given a set of qubits interacting as shown below (left), the goal of this gadget is to introduce a mediator qubit that produces an effective target interaction of the form, $H_{\text{targ.}} = A\otimes B + A\otimes C$. Notice, this gadget reduces the locality of certain qubits and also separates the local interactions.

For this gadget we choose, $$ \begin{align*} \widetilde{H} &= H+V \\ H &= \Delta\ketbra{1}{1}_d \\ V &= \sqrt{\frac{\Delta}{2}}V_{\text{main}} + V_{\text{extra,1}} + V_{\text{extra,2}}\\ V_{\text{main}} &= \left(A-B-C\right)X_d \\ V_{\text{extra,1}} &= \frac{1}{2}\left(A^2+B^2+C^2\right) \\ V_{\text{extra,2}} &= - BC \end{align*} $$ In this example we have two extra perturbation terms. This is because without the second the gadget produces and extra connection between qubits $b$ and $c$. By including $V_{\text{extra,2}}$ we can remove this unwanted term. Taking the series expansion, we have, $$ H_{\text{eff}} = (AB+AC)\ketbra{0}{0} $$

This gadget can be seen as a combination of the previous gadgets. The goal is to introduce a mediator qubit where there exists a crossing in the underlying interaction graph, such that the interaction with said mediator produces the effective tagret interaction of the form, $H_{\text{targ.}} = AD + BC$. This gadget removes the non--planar crossing but increases the degree of the mediator qubit to $4$. This construction also suffers from many unwanted extra interaction terms.

We therefore choose, $$ \begin{align*} \widetilde{H} &= H+V \\ H &= \Delta\ketbra{1}{1}_e \\ V &= \sqrt{\frac{\Delta}{2}}V_{\text{main}} + V_{\text{extra,1}} + V_{\text{extra,2}}\\ V_{\text{main}} &= \left(A-C+B-D\right)X_e \\ V_{\text{extra,1}} &= \frac{1}{2}\left(A^2+B^2+C^2+D^2\right) \\ V_{\text{extra,2}} &= - (AB+BC+CD+DA) \end{align*} $$ Taking the series expansion, we have, $$ H_{\text{eff}} = (AC + BD)\ketbra{0}{0}_e $$

The triangle gadget is a combination of both the subdivision and fork gadgets. The goal is to reduce the degree of one qubit in a triad and create no additional edges between the system qubits. The gadget first subdivides the edges then forks the mediator qubits.

The 3–to–2 local gadget presented by [OT08] is not the only gadget of this type. Work by Kempe, Kitaev and Regev, [KKR05] previously introduce a 3–to–2 local gadget in their proof that $2$–local Hamiltonians are QMA–complete. The gadget here takes a different appoach to acheive the same answer. The 3–to–2 local gadget here uses third–order perturbation theory, unlike the previous examples that use only second–order. The desired target Hamiltonian, $H_{\text{targ.}} = A\otimes B\otimes C$. A diagrammatic representation for this gadget is difficult to define, however, intuition from previous constructions renders the understanding of the perturbation term $V$ much easier. We choose, $$ \begin{align*} \widetilde{H} &= H+V \\ H &= \Delta\ketbra{1}{1}_d \\ V &= \Delta^{2/3}V_{\text{main}} + \Delta^{1/3}V_{\text{extra}}' + V_{\text{extra}}\\ V_{\text{main}} &= \frac{1}{\sqrt{2}}\left(A-B\right)X_d + C\otimes\ketbra{1}{1}_d \\ V_{\text{extra}}' &= \frac{1}{2}\left(A-B\right)^2 \\ V_{\text{extra}} &= \frac{1}{2}\left(A^2+B^2\right)\otimes C \end{align*} $$ Taking the series expansion to third order, we have, $$ H_{\text{eff}} = (ABC)\ketbra{0}{0} $$

Biamonte and Love Gadgets

This gadget and the one below take a slightly different approach that those above. Instead of approximating a completely new Hamiltonian using a gadgets, [OT08] aim to create additional terms for a given Hamiltonian. The $ZX$ gadget is used with the (x–z/x–z) Hamiltonian to create the full set of interactions: $\{\mathbb{I},\mathbb{I}\otimes X,\mathbb{I}\otimes Z,X\otimes \mathbb{I},Z\otimes \mathbb{I}, X\otimes X,X\otimes Z,Z\otimes X,Z\otimes Z\}$. As mentioned in the introductory section, not all Hamiltonians have all possible combinations of Pauli matrices. The (x–z/x–z) Hamiltonian does not have terms like $XZ$ and $ZX$. Such terms are what the $ZZXX$ gadget aim to create. This gadget exploits a pseudo–3–local term of the form, $A\otimes\mathbb{I}\otimes C$, where, $A, C \in \{X, Z\}$. Framing the problem this way allows for the use of the 3–to–2 local gadget from [OT08]. $$ \begin{align*} \widetilde{H} &= H+V \\ H &= \Delta\ketbra{1}{1}_d \\ V &= \Delta^{2/3}V_{\text{main}} + \Delta^{1/3}V_{\text{extra}}' + V_{\text{extra}} + \Gamma \\ V_{\text{main}} &= \frac{1}{\sqrt{2}}\left(X_i-\mathbb{I}\right)X_k + Z_j\otimes\ketbra{1}{1}_k \\ V_{\text{extra}}' &= \frac{1}{2}\left(X_i-\mathbb{I}\right)^2 = \mathbb{I} - X_i \\ V_{\text{extra}} &= \frac{1}{2}\left(X_i^2+\mathbb{I}\right)\otimes Z_j = Z_{j} \end{align*} $$ Where $\Gamma$ represents the original Hamiltonian terms. Notice all the interactions in the above terms are valid with respect to the (x–z/x–z) Hamiltonian. Up to third order, it can be shown, $$ H_{\text{eff}} = \left(\Gamma + X_iZ_j\right)\ketbra{0}{0}_k $$

The process for creating the additional $XX$ and $ZZ$ terms, absent in the ($[\![$xz$]\!]$*/x–z) Hamiltonian, is a simple application of the subdivision gadget seen in [OT08]. Here we cover how to construct $ZZ$ interactions, however, constructing $XX$ interactions is an analogus process and can easily be seen by a Hadamard conjugation mapping. We define, $$ \begin{align*} \widetilde{H} &= H+V \\ H &= \Delta\ketbra{1}{1}_c \\ V &= \Delta^{1/2}V_{\text{main}} + \Gamma \\ V_{\text{main}} &= \frac{1}{\sqrt{2}}\left(Z_a-Z_b\right)X_c \end{align*} $$ To second–order truncation, it can be shown, $$ H_{\text{eff}} = \left(\Gamma +Z_aZ_b\right)\ketbra{0}{0}_c $$

Schuch and Verstraete Gadgets

The goal of the parameter fixing gadget, as the name suggests, is a reduction from arbitrary Pauli couplings to ones with constant interaction strength and different Pauli operators. More formally, we start with, $\lambda_{ij} P_i \otimes Q_j$ where $P,Q \in \{\mathbb{I},X,Y,Z\}$, by using a strong magnetic field and a mediator gadget, the desired, tunable interaction can be found. The strngth of the interaction is given by the angle in a chosen plane, for this example, the $XY$ plane. From this point we drop the subscripts. To reiterate the motivation slightly, note the goal of this gadget is to simulate the ground state of some $\lambda P\otimes Q$ interaction using another, mediated interaction, that has a constant interaction strength. In this way, we can then say, the mediated interaction is sufficient to approximation the ground space. These reductions allow for external fields and hence the $V_{\text{extra}}$ terms present in previous constructions need not be present. We choose, $$ \begin{align} \widetilde{H} &= H+V \\ H &= \Delta_P\ketbra{e_\phi}{e_\phi}_k \\ V &= \sqrt{\frac{\Delta_P}{2}}V_{\text{main}}\\ V_{\text{main}} &= \left(PX_k - QY_k\right) \end{align} $$ Where $\ket{e_\phi} = \frac{1}{\sqrt{2}}\left(\ket{0} - e^{i\phi}\ket{1} \right)$. The projected $X$ and $Y$ matrices are no longer as straightforward as previous examples. $$ \begin{align} X_{--} &= \frac{1}{2}\cos\phi\ketbra{g}{g} \\ X_{+-} &= \frac{i}{2}\sin\phi\ketbra{e}{g} \\ X_{-+} &= \frac{-i}{2}\cos\phi\ketbra{g}{e} \\ Y_{--} &= \frac{1}{2}\sin\phi\ketbra{g}{g} \\ Y_{+-} &= \frac{-i}{2}\cos\phi\ketbra{e}{g} \\ Y_{-+} &= \frac{i}{2}\sin\phi\ketbra{g}{e} \end{align} $$

To second order, the effective Hamiltonian can be shown as, $$ H_{\text{eff}} = \sin\phi\cos\phi\,PQ\ketbra{g}{g} + \Gamma $$ The term $\Gamma$ represents the residual local fields left from the perturbation analysis — these are important for subsequent gadgets. We mention here that the process shown above is different from that in the article. This is because here we are attempting a unified framework hence hsowcasing each gadget in a compramble manner. It takes a small calculation to translate the article's method to the one shown here. To note, the idea of the gadgets in [SV09] is to create a chain of gadget reduction that approximate a Heisenberg interaction, i.e. go from $$P_i \otimes Q_j \xmapsto{\text{Gadgets}} X_iX_j + Y_iY_j + Z_iZ_j + \text{ext. fields}$$

This gadget aims to take Pauli interactions of the form $P\otimes Q$ where $P$ and $Q$ are necessarily different and reduce to Ising type couplings, i.e. some interaction using $P\otimes P + Q\otimes Q$. We introduce two peices of notation to ease the analysis. In this gadget, the ground state is chosen to be $\ket{g_{\pi/4}}$, hence, we define, $$ \langle \sigma^{\mu}\rangle_{g_{\pi/4}} = \eta(\sigma) $$ and, $$ \sigma^{\mu}_{-+} = \xi(\sigma)\ketbra{e_{\pi/4}}{g_{\pi/4}} = (\sigma^{\mu}_{+-})^\dagger $$ Where the former notation signifies the inner product of a given Pauli operator with the defined ground state. It is simple to verify what these values are. Secondly, the latter notation is the projected Pauli operator value. This calculation is slighlty more involved but nonetheless straightforward. We note that the only Pauli operator that has no cross projector value is the identity. We choose, $$ \begin{align} \widetilde{H} &= H+V \\ H &= \Delta_I\ketbra{e_{\pi/4}}{e_{\pi/4}}_k \\ V &= \sqrt{\frac{\Delta_I}{2}}V_{\text{main}} + \Gamma \ketbra{g_{\pi/4}}{g_{\pi/4}}_k\\ V_{\text{main}} &= \left(P_iP_k - Q_kQ_j\right) \end{align} $$

It can be shown to second order, we retrive the interaction, $$ H_{\text{eff}} = (\eta(P)\bar{\eta}(Q) PQ + \Gamma)\ketbra{g}{g} $$

The term $XX$ is a physics term related to labeling Pauli interactions. Informally, it means two of the terms like $XX$, $YY$ or $ZZ$ conform to the same parameter. We do not delve into the name here and be faithful to the original work. We reduce the Ising interactions we saw previously into these $XX$–type interactions. The idea behind this gadget is to convert the Ising interactions, interactions like $PP$, into $XX$–type interactions. To motivate and introduce this gadget, we deviate from the general path and consider a specific example. It should be noted that similar gadgets can be constructed for the all $PP$ Ising terms via appropriate unitary conjugation of the perturation Hamiltonian. We consider the example of the $XX$ Ising term. By choosing, $$ \begin{align} \widetilde{H} &= H+V \\ H &= \Delta_{XX}/2(\mathbb{I} - Y)_k \\ V &= \sqrt{\frac{\Delta_{XX}}{2}}V_{\text{main}} + \Gamma \ketbra{g}{g}_k\\ V_{\text{main}} &= \left((X_iX_k + Y_iY_k)\otimes\mathbb{I}_j - \mathbb{I}_i \otimes(X_kX_j + Y_kY_j)\right) \end{align} $$

To second–order, it can be shown, $$ H_{\text{eff}} = (XX + \Gamma)\ketbra{g}{g} $$

The penultimate gadget in the Schuch and Verstraete line–up is the $XX$–to–Heisenberg gadget. The idea is that antiferromagnetic Heisenberg interaction with external $Z$ fields can simulate the $XX$–type interactions above. The roster of interactions to approximate are: $XX+YY$, $XX+ZZ$ and $YY+ZZ$. Similar to the previous example, appropriate unitary conjugation of the perturbation Hamiltonian will reveal the specific gadget for a given $XX$–type interaction. We follow the prvious example of $XX+YY$. Choosing, $$ \begin{align} \widetilde{H} &= H+V \\ H &= \Delta_{H}/2(\mathbb{I} - Z)_k \\ V &= \sqrt{\frac{\Delta_{H}}{2}}V_{\text{main}} + V_{\text{extra}} + \Gamma \ketbra{g}{g}_k\\ V_{\text{main}} &= \sum_{l\in\{1,2,3\}} \left(\sigma^{l}_i\otimes\sigma^{l}_k\otimes\mathbb{I}_j + \mathbb{I}_i\otimes\sigma^{l}_k\otimes\sigma^{l}_j \right) \\ V_{\text{extra}} &= \left(Z_i\otimes\mathbb{I}_k\otimes\mathbb{I}_j + \mathbb{I}_i\otimes\mathbb{I}_k\otimes Z_j \right) \end{align} $$

To second–order, it can be shown, $$ H_{\text{eff}} = (XX + YY + \Gamma)\ketbra{g}{g} $$ In a complete setting, the gadget outlined in this article create a chain of gadgets that approximate a Heisenberg interaction using a system of different Pauli interactions, vice versa. This is captured in the diagram below:

A pleasant way to think about this diagram is to think that a chain of specific Heisenberg interactions are sufficient to approximate a particular Pauli interaction.

This final gadget is used in the reduction from a sparse lattice to a full 2D lattice. Adding external fields to certain qubits creates a full lattice of Heisenberg interactions with local fields. We choose, $$ \begin{align} \widetilde{H} &= H+V \\ H &= \Delta_{B}/2(\mathbb{I} - Z)_k \\ V &= \sqrt{\frac{\Delta_{H}}{2}}V_{\text{main}} + \sum_{i \atop l\in\{1,2,3\}} B^{l}_i\;\sigma^{l}_i\\ V_{\text{main}} &= \sum_{\langle i,j \rangle \atop l\in\{1,2,3\}} \sigma^{l}_i \otimes \sigma^{l}_j \end{align} $$ The effective Hamiltonian here reproduces an approximation to the Heisenberg interaction on a sparse lattice. Since it is not trivial to see the resulting interaction is a sparse one we omit this analysis.

Piddock and Montonaro Gadgets

The gadgets proposed by Piddock and Montonaro are a generalisation of the gadgets shown above. For the context of their work, the gadgets of previous literature are not appropriate in the same manner. This links to the gadgets of Biamonte and Love where the interaction set of a given Hamiltonian restricted us from creating any old gadget. A similar principle applies here. The work [PM15] is heavily concerned with interactions of the form: $\alpha XX + \beta YY + \gamma ZZ$ without the addition of external fields. This clearly means the set of interactions present differs greatly from what we allowed previously. The role of the basic gadget is to identity to further subdivision gadgets, namely the positive and negative subdivision gadgets. The basic gadget lays the theoretical foundations. We do not cover an in–depth analysis here, just the important points.

Consider the interaction $\alpha XX + \beta YY + \gamma ZZ$ subject to the condition $(\alpha+\beta, \alpha+\gamma, \beta+\gamma)\gt0$. The matrix for this is trivially defined as, $$ \begin{bmatrix} \gamma&0&0&\alpha-\beta\\0&-\gamma&\alpha+\beta&0\\0&\alpha+\beta&-\gamma&0\\\alpha-\beta&0&0&\gamma \end{bmatrix} $$ Since the above condition is required, we find the unique "low–energy" state to be given by $\ket{\Psi^-}$. If the condition $(\alpha+\beta, \alpha+\gamma, \beta+\gamma)\gt0$ is not met we run into a degenerate ground space. As per the general idea, we want a block diagonal unperturbed Hamiltonian term $H$ such that the low–energy eigenvalue is $0$ and all other eigenvalues are greater than $1$. This gives a split Hilbert space. To this end, we deinfe the unpertutbed Hamiltonian as, $$ H = \Delta \big((\alpha+\beta)\ketbra{\Psi^+}{\Psi^+} +(\alpha+\gamma)\ketbra{\Phi^+}{\Phi^+} +(\beta+\gamma)\ketbra{\Phi^-}{\Phi^-} \big) $$

From the above ideas, the form of the perturbation term $V$ heavily influences the effective interaction produced. For the case here, there is a specific way of connecting the mediator qubits to the original system qubits such that positive and negative interactions can be simulated. This is why we have the two generalised gadgets below. The important thing to notice is that instead of a single mediator qubit, we now have two!

Let us denote the interaction between two qubits, $i$ and $j$ or the form $\alpha X_iX_j + \beta Y_iY_j + \gamma Z_iZ_j$ as $H_{ij}$. We also have the added condition that $(\alpha+\beta, \alpha+\gamma, \beta+\gamma)\gt0$. Consider choosing the following terms, $$ \begin{align} \widetilde{H} &= H+V \\ H &= \Delta\big((\alpha+\beta)\ketbra{\Psi^+}{\Psi^+}_{ab} +(\alpha+\gamma)\ketbra{\Phi^+}{\Phi^+}_{ab} +(\beta+\gamma)\ketbra{\Phi^-}{\Phi^-}_{ab} \big)\\ V &= \sqrt{\frac{\Delta}{2}}V_{\text{main}} \\ V_{\text{main}} &= H_{ia} + H_{jb} \\ &= \big(\alpha X_iX_a + \beta Y_iY_a + \gamma Z_iZ_a \big) + \big(\alpha X_jX_b + \beta Y_jY_b + \gamma Z_jZ_b \big) \end{align} $$ In this form, the mediator qubits are attached in the following way,

To second–order perturation theory, it can be shown, $$ H_{\text{eff}} = \left(\frac{\alpha^2}{\beta+\gamma} X_iX_j + \frac{\beta^2}{\alpha+\gamma} Y_iY_j + \frac{\gamma^2}{\alpha+\beta} Z_iZ_j \right)\ketbra{\Psi^-}{\Psi^-}_{ab} $$

The negative subdivision gadget uses the same basic framework as the positive subdivision gadget however we now attach the mediator qubits in a different fashion. Consider, $$ \begin{align} \widetilde{H} &= H+V \\ H &= \Delta\big((\alpha+\beta)\ketbra{\Psi^+}{\Psi^+}_{ab} +(\alpha+\gamma)\ketbra{\Phi^+}{\Phi^+}_{ab} +(\beta+\gamma)\ketbra{\Phi^-}{\Phi^-}_{ab} \big)\\ V &= \sqrt{\frac{\Delta}{2}}V_{\text{main}} \\ V_{\text{main}} &= H_{ia} + H_{ja} \\ &= \big(\alpha X_iX_a + \beta Y_iY_a + \gamma Z_iZ_a \big) + \big(\alpha X_jX_a + \beta Y_jY_a + \gamma Z_jZ_a \big) \end{align} $$ We show this example visually as,

A similar second–order analysis reveals, $$ H_{\text{eff}} = -\left(\frac{\alpha^2}{\beta+\gamma} X_iX_j + \frac{\beta^2}{\alpha+\gamma} Y_iY_j + \frac{\gamma^2}{\alpha+\beta} Z_iZ_j \right)\ketbra{\Psi^-}{\Psi^-}_{ab} $$

Bravyi, DiVincenzo, Oliveira and Terhal Gadgets
Coming soon!