Implementation details, conventions, and FAQ
- Sign of the mixer Hamiltonian
In the original paper on QAOA (Ref 1), Farhi et al use \(\sum_i \hat{X}_i\) as the mixer Hamiltonian, with the initial state being its maximum eigenstate \(\left|+ \cdots +\right>\). In OpenQAOA, we instead choose our mixer Hamiltonian to be \(-\sum_i \hat{X}_i\), so that the initial state \(\left|+ \cdots +\right>\) is now its minimum energy eigenstate. Conceptually this makes the analogy to adiabatic computing clear, since we seek to transform from the ground state of the mixer Hamiltonian to the ground state of the cost Hamiltonian.
- Implementation of circuit rotation angles
In quantum mechanics, the basic time evolution operator is \(\exp(-iHt)\) for a Hamiltonian H and total evolution time t. Generically, in the QAOA mixer Hamiltonian, the operator \(-X\) is to be applied for a total time \(\beta\), which is one of the parameters we seek to optimise. We therefore need to implement the time evolution \(\exp(i\beta X)\), which can be achieved using the RX(\(\theta\)) operator if we set \(\theta = -2\beta\).
Similarly, the cost Hamiltonian operator \(\exp(-i\gamma hZ)\) can be implemented via an RZ(\(\theta\)) rotation, setting \(\theta = 2\gamma h\). You can verify these details in the methods that relate to the creation of these angles in
openqaoa.qaoa_parameters.standardparams.QAOAVariationalStandardParams.- Where does the factor
0.7 * n_stepsin thelinear_ramp_from_hamiltonian()method come from? The
.linear_ramp_from_hamiltonian()parameters are inspired by analogy between QAOA and a discretised adiabatic annealing process. If we pick a linear ramp annealing schedule, i.e. \(s(t) = \frac{t}{\tau}\), where \(\tau\) is the total annealing time, we need to specify two numbers: the total annealing time \(\tau\) and the step width \(\Delta t\). Equivalently, we can also specify the total annealing time \(\tau\) together with the number of steps \(n_{\textrm{steps}}\), which is also called p in the context of QAOA. A good discretised annealing schedule has to strike a balance between a long annealing time \(\tau\) and a small step width \(\Delta t = \frac{\tau}{n_{\textrm{steps}}}\). We have found in numerical experiments that \(\Delta t = 0.7 = \frac{\tau}{n_{\textrm{steps}}}\) strikes a reasonably good balance for many problem classes and instances, at least for the small system sizes one can feasibly simulate. For larger systems or smaller energy gaps, it might be necessary to choose smaller values of \(\Delta t\). The implementation of this method can be found in the subclasses ofQAOAVariationalBaseParams.- Discrete sine and cosine transformations for the
QAOAVariationalFourierParamsclass In converting between the \(\beta\) and \(\gamma\) parameters of the
QAOAVariationalStandardParamsclass, and the u and v parameters of theQAOAVariationalFourierParamsclass, we use the type II versions of the discrete sine and cosine transformations. These are included in Scipy’s fast Fourier transforms module fftpack. With the conventions used therein, in OpenQAOA the transformations are then given by:\[ \begin{align}\begin{aligned}\gamma_i = 2 \sum_{k=0}^{q-1} u_k \sin\left[ (k + 1/2) (i+1) \frac{\pi}{p} \right]\\\beta_i = 2 \sum_{k=0}^{q-1} v_k \cos\left[ (2k + 1) i\frac{\pi}{2p} \right]\end{aligned}\end{align} \]While these differ from the versions used in Ref 2, this is merely a convention.