How to calculate the approximation ratio of QAOA?

Question

In order to evaluate the QAOA circuit, we need to compute the approximation ratio, which is the expectation value of QAOA circuit divided by the best solution.

My question is, how to find the best solution? Should we use a purely classical approach to find it (if so, which function?) or we use a hybrid classical-quantum approach with the help of a classical solver? I found in Qiskit tutorial, it uses NumPyMinimumEigensolver to obtain the result. Should we just use this result and compute its expectation value as the best solution to obtain the approximation ratio?

Answer 1

You can try any way as both of them provide good results. The NumpyMinimumEigensolver is a slow and classical way to find the total ground state in the context of the question you are working on. The results of the NumpyMinimumEigensolver may differ from a purely classical one by a small factor. But, in reality, it is hard to find the exact and perfect ground state whether you try the hybrid-classical approach or the NumpyMinimumEigensolver approach. So, a little change would not hurt the results of your expected value in the question.

Then again, nature itself is not expected to be finding this perfect ground-state, so future experimentation is needed to see how close a given quantum computing solution approximates nature's solution:)