2
$\begingroup$

In the paper Quantum Observables for continuous control of the Quantum Approximate Optimization Algorithm via Reinforcement Learning, an Hamiltonian is defined in order to solve the MAXCUT problem :

$$ C = \sum_{<i,j>} \frac{1}{2} (I -\sigma_i^z \sigma_j^z) = \sum_{<i,j>} C_{i,j} $$

with $\sigma_j^z$ the pauli matrix $\sigma^z$ applied to the $j^{th}$ qubit. The sum is taken over all adjacent edge in the original graph problem.

The paper indicates the following result :

$$ \lim_{p \rightarrow \infty} [\max_{\beta,\gamma} \langle \beta,\gamma |_p C | \beta,\gamma \rangle_p] = \max C $$.

consider $|\beta,\gamma \rangle_p$ some states produced by the QAOA algorithm and $p$ an integer, their value do not matter for my question.

The quantity $\max_{\beta,\gamma} \langle \beta,\gamma |_p C | \beta,\gamma \rangle_p$ is clearly scalar, whereas I can't make sense of the expression $\max C$.

My question is then, what does $\max C$ means in this context ?

I believe the answer is not given in this paper. I might have the answer from this documentation, where it is said that the Hamiltonian is constructed from the classical function,

$$C(z_1,...,z_n) = \sum_{<i,j>} \frac{1}{2} (1 -z_i z_j)$$

Where the sum is taken over all adjacent edges in the original graph problem, with $z_i = 1$ if $z_i \in S$ or $z_i = -1$ if $z_i \in \bar{S}$ (same for $z_j$) with $S$ and $\bar{S}$ the bipartition of the original graph. I believe the authors of the first paper I linked were referring to this classical function and not to the Hamiltonian when speaking about $\max C$.

My second guess is that it might refers to some matrix norms but none is defined in the article. What do you think ?

$\endgroup$
4
  • 1
    $\begingroup$ I suspect your first guess is the right one. I've not looked at this in-depth, but my impression is that the paper you give is rather too brief on the setup and the connection to the actual problem it's trying to solve. I think the use of the $C_{i,j}$ in your first equation adds weight to this as those are probably supposed to be classical variables of whether or not a particular edge is cut. $\endgroup$ – DaftWullie Apr 6 '20 at 14:33
  • 1
    $\begingroup$ Of course, there is also a connection to matrix norms: basically what you're interested in is the maximum eigenvalue of the matrix. $\endgroup$ – DaftWullie Apr 6 '20 at 14:35
  • $\begingroup$ ok thank you @DaftWullie, I'll go with that definition for now for $\max C$. Would you be kind enough to explain me this sentence ? "Of course, there is also a connection to matrix norms: basically what you're interested in is the maximum eigenvalue of the matrix". I fail to see the link between the maximum eigenvalue of the Hamiltonian operator and the solution to the MAXCUT problem. $\endgroup$ – nathan raynal Apr 7 '20 at 14:22
  • $\begingroup$ That is the whole purpose of this scheme - to make the connection between the classical problem and a quantum problem! $\endgroup$ – DaftWullie Apr 7 '20 at 15:03
3
$\begingroup$

$C$ is a diagonal matrix, and $\max{C}$ is simply the maximum element (which is also the maximum eigenvalue, since the matrix is already diagonal).

This is also what is usually meant by "maximum" and "minimum" in this "quantum optimization" literature, which includes adiabatic quantum computing (AQC), quantum annealing, and QAOA.

$\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.