1
$\begingroup$

I was running instances of $3$-regular graphs with small number of vertices on Qiskit, and for $p=1$ the algorithm was giving always the exact solution for the MaxCut problem, after optimizing the parameters. I was wondering though, how do we know if a specific graph can't be solved on $p=1$ ? Do we know the limits of QAOA for $p=1$ in order to decide with certainty that extra layers are required, given the graph?

$\endgroup$
2
$\begingroup$

We don't in general.

There are instances where $p=2,3$ or $4$ might still be not enough. QAOA is an approximate algorithm as the name suggested, so you don't expect it to find the exact answer.

You should take a look at this paper: Quantum Approximate Optimization Algorithm: Performance, Mechanism, andImplementation on Near-Term Devices

| improve this answer | |
$\endgroup$
1
$\begingroup$

In general, we don't know. It is mostly trial and error, depending on the graph instance. There exist a few examples in the literature where it is pointed out that the probability of getting the optimum is very low such as this paper. One could try to characterize such situations with a few graph properties that can help decide whether or not QAOA at depth 1 is "enough" depending how you define it. For instance by using Machine Learning but this requires finding those graph characteristics but that is likely hard to find. As a Machine Learning methodology reference, there is this article.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.