7.1 Hamiltonians, observables, and their expectation values

So far, we’ve found in Hamiltonians a way to encode combinatorial optimization problems. As you surely remember, in these optimization problems, we start with a function that assigns real numbers to binary strings of a certain length , and we seek to find a binary string with minimum cost . In order to do that with quantum algorithms, we define a Hamiltonian such that

holds for every binary string of length . Then, we can solve our original problem by finding a ground state of (that is, a state such that the expectation value is minimum).

This was just a very quick summary of Chapter 3, Working with Quadratic Unconstrained Binary Optimization Problems. When you read that chapter, you may have noticed that the Hamiltonian associated to has an additional, very remarkable property. We have mentioned this a couple of times already, but it is worth remembering that, for every computational basis state , it holds...