  Perturbative gadgets are general techniques for reducing many-body spin
interactions to two-body ones using perturbation theory. This allows for
potential realization of effective many-body interactions using more physically
viable two-body ones. In parallel with prior work (arXiv:1311.2555 [quant-ph]),
here we consider minimizing the physical resource required for implementing the
gadgets initially proposed by Kempe, Kitaev and Regev (arXiv:quant-ph/0406180)
and later generalized by Jordan and Farhi (arXiv:0802.1874v4). The main
innovation of our result is a set of methods that efficiently compute tight
upper bounds to errors in the perturbation theory. We show that in cases where
the terms in the target Hamiltonian commute, the bounds produced by our
algorithm are sharp for arbitrary order perturbation theory. We provide
numerics which show orders of magnitudes improvement over gadget constructions
based on trivial upper bounds for the error term in the perturbation series. We
also discuss further improvement of our result by adopting the Schrieffer-Wolff
formalism of perturbation theory and supplement our observation with numerical
results.
