  Mapping functions on bits to Hamiltonians acting on qubits has many
applications in quantum computing. In particular, Hamiltonians representing
Boolean functions are required for applications of quantum annealing or the
quantum approximate optimization algorithm to combinatorial optimization
problems. We show how such functions are naturally represented by Hamiltonians
given as sums of Pauli $Z$ operators (Ising spin operators) with the terms of
the sum corresponding to the function's Fourier expansion. For many classes of
functions which are given by a compact description, such as a Boolean formula
in conjunctive normal form that gives an instance of the satisfiability
problem, it is #P-hard to compute its Hamiltonian representation. On the other
hand, no such difficulty exists generally for constructing Hamiltonians
representing a real function such as a sum of local Boolean clauses. We give
composition rules for explicitly constructing Hamiltonians representing a wide
variety of Boolean and real functions by combining Hamiltonians representing
simpler clauses as building blocks. We apply our results to the construction of
controlled-unitary operators, and to the special case of operators that compute
function values in an ancilla qubit register. Finally, we outline several
additional applications and extensions of our results.
  A primary goal of this paper is to provide a $\textit{design toolkit for
quantum optimization}$ which may be utilized by experts and practitioners alike
in the construction and analysis of new quantum algorithms, and at the same
time to demystify the various constructions appearing in the literature.
