3.2 Enter quantum: formulating optimization problems the quantum way

In this section, we will unveil how all the work that we have done so far in this chapter has followed a secret plan! Was the choice of as the name for the variables in our problems completely arbitrary? Of course not! If it made you think of those lovely quantum gates and matrices that we introduced back in Chapter 1, Foundations of Quantum Computing, you were on the right track. It will be the key to introducing the quantum factor into our problems, as we will begin to see in the next subsection.

3.2.1 From classical variables to qubits

So far, the formulations that we have considered for the Max-Cut problem and for the Ising model are purely classical. They do not mention quantum elements such as qubits, quantum gates, or measurements. But we are closer than you might think to being able to give a quantum formulation for these problems. We will start with a very simple instance of the Max-Cut problem and show...