Perturbative gadgets at arbitrary orders

Adiabatic quantum algorithms are often most easily formulated using many-body interactions. However, experimentally available interactions are generally two-body. In 2004, Kempe, Kitaev, and Regev introduced perturbative gadgets, by which arbitrary three-body effective interactions can be obtained using Hamiltonians consisting only of two-body interactions. These three-body effective interactions arise from the third order in perturbation theory. Since their introduction, perturbative gadgets have become a standard tool in the theory of quantum computation. Here we construct generalized gadgets so that one can directly obtain arbitrary $\mathit{k}$-body effective interactions from two-body Hamiltonians. These effective interactions arise from the $\mathit{k}$th order in perturbation theory.

Figure 1

The ancilla qubits are all coupled together using $ZZ$ couplings. This gives a unit energy penalty for each pair of unaligned qubits. If there are $\mathit{k}$ bits, of which $\mathit{j}$ are in the state $|1⟩$ and the remaining $k-j$ are in the state $|0⟩$, then the energy penalty is $j\left(k-j\right)$. In the example shown in this diagram, the 1 and 0 labels indicate that the qubits are in the state $|0001⟩$, which has energy penalty 3.

Figure 2

Here the ratio of the error terms to the ideal Hamiltonian $H^{\text{id}}\equiv \frac{-k{\left(-\lambda \right)}^k}{\left(k-1\right)!}{H}^{\text{comp}}$ is plotted. We examine three examples, a third-order gadget simulating a single $XYZ$ interaction, a third-order gadget simulating a pair of interactions $XYZ+XYY$, and a fourth-order gadget simulating a fourth-order interaction $XYZZ$. Here ${\tilde{H}}_{\text{eff}}$ is calculated by direct numerical computation without using perturbation theory. As expected the ratio of the norm of the error terms to $H^{\text{id}}$ goes linearly to zero with shrinking $\lambda$.

Figure 3

From a given $\mathit{m}$-tuple $\left(l_1,l_2,\dots ,l_m\right)$ we construct a corresponding stair-step diagram by making the $\mathit{j}$th step have height ${\mathit{l}}_{\mathit{j}}$, as illustrated.

Figure 4

A convex diagram must have either $l_1=1$ or $l_1>1$. In either case, the diagram can be decomposed as a concatenation of lower-order convex diagrams.