# Probability inequality for Quantum Approximate Optimization Algorithm (QAOA)

In arXiv:2207.14734 the authors claim that it is "straightforward to show that" their equation 8 holds:

$$\mathrm{Pr}_{x\sim q}[x:f(x)\geq \mu] \geq \frac{1}{M}$$

where we have an objective function maps a bitstring to some value $$f:( 0,1)^n\rightarrow[0,M]$$. Moreover, $$q(x)=|\langle x|\gamma\beta\rangle|^2$$ with $$|\gamma,\beta\rangle$$ being the state after a run of the QAOA circuit. $$\gamma$$ is the expectation value of this objective function, i.e. $$\mu = E_{x\sim q} f(x)$$. Furthermore, the problem graph is $$G=(V,E)$$ and the values $$n$$ and $$M$$ are defined as $$n=|V|$$ and $$M=|E|\leq n^2$$.

From which theorem/lemma can the above equation be derived? Intuitively, I guess I understand what it means, but I do not know how it is derived even though it is supposed to be "straightforward to show".

Cross-posted on physics.SE

• In the paper, after Eq 8, the authors state that $M$ is the number of trials. So if we peform a single trial, the probability is $\geq$ 1, which is not true in general. So, to me, it is not clear if $M$ should be the number of trials or the size of the maxcut. Mar 1 at 1:24
• @MonteNero I see your problem, however, $M=|E|$ so $M$ is the same as the number of edges in the problem graph. If we had $M=1$ a Max Cut Problem would be trivial. Thus I guess your case should not be the issue - nevertheless, I think they say that $M$ is the number of trials is only due to the fact that $M$ is in the denominator in equ. 8. If you check out Equ. 13, they arrive at the conclusion that one will need at most $5^k$. So they do not define $M$ to be the number of trials, it's just implied by the structure of the equation. Mar 1 at 8:30
• If $M=1$, maxcut is not trivial: there will be 4 candidate solutions (assuming there are 2 adjacent vertices) and half of these solutions give maxcut of size 0. Yet Eq 8 tells that the sample is higher than the average with probability 1. So this formula may already break at a very simple case where we have $n=2$. Additional assumptions on $q(x)$ are needed to guarantee Eq 8. So, now, why should it hold for $n>2$? Mar 1 at 13:54
• @MonteNero Ok yes sorry, I withdraw this claim with the triviality. However, they seem to assume that $q(x)=|\langle{x}| \gamma,\beta \rangle|^2$ is based on the already optimized parameters $\gamma$ and $\beta$. Thus it is maybe more reasonable that the LHS of Eq. 8 will be fulfilled with certainty in the case of $M=1$? Mar 1 at 17:28
• It is clear from the get go that they mean gamma and beta are optimized. But what does it really mean mathematically for $q(x)$? I can say, gamma and beta are such that $q(x)=1$ for an optimal $x$ and $q(x)=0$ otherwise. Or I could also say optimal parameters are such that $q(x) = .00001$ for all optimal $x$. In the first case, equality obviously holds. But this is not a reasonable assumption in general. Mar 1 at 18:19