4
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – MonteNero
    Mar 1 at 1:24
  • $\begingroup$ @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. $\endgroup$
    – Juri V
    Mar 1 at 8:30
  • $\begingroup$ 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$? $\endgroup$
    – MonteNero
    Mar 1 at 13:54
  • $\begingroup$ @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$? $\endgroup$
    – Juri V
    Mar 1 at 17:28
  • $\begingroup$ 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. $\endgroup$
    – MonteNero
    Mar 1 at 18:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.