As requested in the comments, here is a worked example. The main body deals with minimizing $f(x)$ for a specific problem. At the bottom follows a brief discussion of constraints then a brief discussion about the general case.
Let's solve the Weighted Maximum Cut problem since this
- Is a relatively straight-forward example
- Is hard classically
- Is a relatively common example in the literature (e.g. https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.90.067903)
- Has a clear connection to a physical Hamiltonian (Ising spin-glasses)
To understand the problem, we start with an undirected graph of $n$ vertices $\{V\}$, where each vertex $v_i\in V$ has weight $w_i\geq0$ and each edge connecting $v_i$ and $v_j$ has a weight $w_{ij}\geq0$. We then cut the graph into two pieces. The cut need not be straight but must not self-intersect and cannot cut any edge twice. Then we calculate a "payout" $P$ for our cut. The payout is the sum of the weights of the edges we cut through, plus the sum of the weights of the vertices on one side of the cut.$^1$
Source
In this image, the payout would be, $1+4+3+3+2 = 13$ for the edges plus $5+6+1 = 12$ for the vertices $\to P=25$ (assuming the number inside each vertex is its weight). The optimization problem is to maximize $P$ for a given graph.$^2$
To write this mathematically, we can think in terms of bit strings. We define a cut by a string $s\in\{0,1\}^n$ where $s_i=0\to v_i$ is not counted in the sum and $s_i=1\to v_i$ is counted in the sum. To make the math a little cleaner, if the graph isn't fully connected, make the graph to be fully connected and set $w_{ij}=0$ for any unconnected pairs $v_i,v_j$.
For example, looking at the image above again, let's interpret the numbers inside the vertices to be the vertex index instead of the weight like we assumed above. Then the drawn cut corresponds to $s=100011$. $s_1=s_5=s_6=1\to v_1, v_5, v_6$ are on the "good" side of the cut and get counted, while $s_2=s_3=s_4=0$ are on the "bad" side of the cut and are not counted.
This then allows us to write $$P(s) = \sum_i s_i w_i + \sum_{i,j} s_i(1-s_j)w_{ij}$$
The first term just counts the weights of all the vertices on the "good" side of the cut. The second term counts the weight of an edge if the vertices it connects are on opposite sides of the cut. Note this doesn't double count since it only counts the edge when $s_i=1, s_j=0$ and not when $s_i=0, s_j=1$.
So now our optimization problem is find the string $s$ which maximizes $P(s)$. The idea here is to think of $P(s)$ as a measure of energy of a system and $s$ as the state of the system. This means we can relate $P(s)$ to our Hamiltonian. There's a slight subtly here that we're trying to maximize $P(s)$ but we usually talk about finding the ground state of a Hamiltonian. This isn't an issue but I wanted to point it out - we can instead look at the highest energy excited state (anti-ground state if you will) or use $-P(s)$ as our energy function then work with the ground state like normal. Let's work with the highest excited state and maximize $P$.
We'd like create a Hamiltonian such that its highest energy state is $|s_0\rangle$ such that $P(s_0)$ is maximal. Essentially we want to turn $P(s)$, an energy function, into $\hat{H}$, an energy operator. We do this by noting that for $|s\rangle\in\{|0\rangle,|1\rangle\}$ we have $$\frac{I-Z}{2}|s\rangle=s|s\rangle\to\text{ define } \hat{s}_i=\frac{I-Z_i}{2}$$
Where $Z_i$ is the Pauli $Z$ acting on qubit $i$. Now we get our Hamiltonian by replacing $s$ with $\hat{s}$ (and 1 with $I$) in $P$
$$H=\sum_i \hat{s}_i w_i + \sum_{i,j} \hat{s}_i(I-\hat{s}_j)w_{i,j}=\sum_i\frac{I-Z_i}{2} w_i + \sum_{i,j} \frac{I-Z_i}{2}\left(I-\frac{I-Z_j}{2}\right)w_{i,j}$$
This can be cleaned up by expanding and seeing $\sum_{i,j}(Z_i-Z_j)=0\to$
$$H=\sum_i \frac{w_i}{2}\left(I-Z_i\right) + \sum_{i,j} \frac{w_{ij}}{4}\left(I-Z_iZ_j\right)=\sum_i \frac{w_i}{2}\left(I-Z_i\right) + \sum_{i<j} \frac{w_{ij}}{2}\left(I-Z_iZ_j\right)$$
We can clean this up even further by multiplying by 2 and removing a constant energy shift (delete the $I$ terms). New Hamiltonian with same eigenstates with eigenvalues scaled and shifted (clearly the maximum energy is unaffected by these transformations)
$$H=-\sum_i w_iZ_i - \sum_{i<j} w_{ij}Z_iZ_j$$
If you're a condensed matter physicist you'll likely recognize this Hamiltonian as an Ising spin glass. Not really relevant to the problem, but I think it's cool.
So now we have a Hamiltonian whose (anti-)ground state encodes the bit string $s_0$ which maximizes $P(s)$ and solves the problem.
The last thing we need is an initial Hamiltonian $H_0$, which we slowly (adiabatically) transform into our final Hamiltonian $H$ so we can define the full Hamiltonian $$H_T(t)=(1-f(t))H_0 + f(t)H: f(0)=0, f(t_f)=1$$
As a starting point $f(t)\propto t$ is often used for simplicity. The minimum $t_f$ determined by the desired accuracy and the spectral gap$^3$. The spectral gap is the minimum energy difference, over all $t$, between the (anti-)ground state and the next energy state. The analysis of the gap is highly non-trivial (see https://arxiv.org/abs/quant-ph/0509162) and determines the complexity/efficiency of the algorithm. An algorithm with 0 gap is not guaranteed to work at all.
So we want an $H_0$ such that
- We can easily find and prepare its (anti-)ground state
- The spectral gap of $H$ is not exponentially small in the size of the problem
For this problem, a good initial Hamiltonian is $H_0 = \sum_i X_i$ because it's highest energy state is easy to find, it's $|+\rangle^{\otimes n}$. It's easy to prepare, just apply $H^{\otimes n}$ to $|0\rangle^{\otimes n}$. I don't have time to get into the analysis of the spectral gap but this Hamiltonian is unlikely to be ideal in that regard (see https://arxiv.org/abs/1701.05584).
With this choice of $H_0$ and taking $f(t)=t/t_f$ we are done. Our Hamiltonian is
$$ H(t) = \left(1-f(t)\right)\sum_i X_i-f(t)\left[\sum_i w_iZ_i + \sum_{i<j} w_{ij}Z_iZ_j\right]$$
Starting in state $|\psi_0\rangle = H^{\otimes n}|0\rangle^{\otimes n}$, evolving according to the above Hamiltonian for time $t_f$ (choosing a suitable $t_f$ is, again, generally highly non-trivial) then measuring in the computational basis should return (with high probability) the string $s=s_0$ which maximizes $P(s)$.
$^1$ This is ambiguous since by symmetry either side will do. We can make this rigorous by, for example, making the cut directed then taking the vertices to the left of the cut when walking along the direction of the cut.
$^2$ I had said in the comment we minimize a cost function, if you like this better just take cost $=-$ payout and minimize cost.
$^3$ I'm sweeping some details about what "slow" means under the rug but can be related to the energy scale of the problem (i.e. multiplying $H$ by a constant will change the speed).
Constraints
Let's say we want to modify the problem above to require that exactly $5$ vertices are on the "good" side of our cut. Mathematically this is $\sum_i s_i-5=0$. To enforce this, we add a penalty term into our Hamiltonian for solutions that break this constraint. So we add a term like $H_c = -\alpha\left(\sum_i \hat{s}_i -5I\right)^2$ choosing $\alpha$ big enough to ensure a state violating this constraint can't be the highest energy state.
Let's say instead we want to require that there are no more than $5$ vertices on the "good" side of our cut. This, it seems, is rather hard to do. In https://arxiv.org/abs/1702.06248 they state that approximating an inequality constraint to order $k$ requires $\mathcal{O}\left(N^{2k}\right)$ $k$-spin couplings which would require even more overhead to break them down into 2-qubit couplings which is often necessary on a given architecture. Essentially the strategy is to approximate a step function using a $k^\text{th}$ order polynomial. This seems like a terrible way to go about it - but I can't think of better way. This is coming from Troyer in 2017 so it's relatively unlikely, though certainly possible, that a better way is currently known.
The general case
The question asks about a general method for encoding an optimization problem into a Hamiltonian. Specifically we want to minimize $f(x)$ subject to a set of constraints. In the section above I discussed adding the constraints to the Hamiltonian. So for a completely general $f(x)$, is there a way to encode it into a Hamiltonian? The general method for this in the literature is to assume we have access to an efficient quantum oracle that implements $f(x)$. We can think of this as having a black box operation (i.e. quantum oracle) $\hat{f}(x)$ such that $\hat{f}(x)|x\rangle=f(x) |x\rangle$. Then we may construct our Hamiltonian as
$$
H = \sum_x \hat{f}(x)|x\rangle\langle x|
$$
Of course this just pushes the difficult part into finding/constructing $\hat{f}(x)$. In fact, simple counting arguments show that almost all (in the mathematical sense) quantum oracles are exponentially inefficient to implement (see http://www.ar-tiste.com/imp-oracles/imps2.pdf). So while this is a general encoding of an optimization problem into a Hamiltonian - it's not really practical. It would seem to be the case that if you want to encode your optimization problem into a Hamiltonian in a useful way - you'll need to leverage some structure of $f(x)$. My understanding is that the specifics of exactly how to do this and how to do this in the best manner is not fully understood and is the subject of active research.
