3
$\begingroup$

So I know that in QAOA we have the two hamiltonians. Mixer and Cost Hamiltonian.

Lets start: First we have our Qubits which get in the Superposition if we add the Hadamard Gate. Then we have the both hamiltonians. Which are rotate one or all qubits. After that we are measure it and optimize the angles beta and gamma in the classical way and this process is going iterative.

That is a little bit clear for me.

BUT: What exactly is happening in the superposition that we have a benchmark where we know that our qubit on the Bloch Sphere is finding the global minimum. Because in the classical optimization for example gradient descent that depends from the gradient if it is good.

I hope that the question is clear 😅

$\endgroup$
2
  • 1
    $\begingroup$ This can help: quantumcomputing.stackexchange.com/questions/14038/… $\endgroup$ Feb 24, 2021 at 10:18
  • $\begingroup$ "* What exactly is happening in the superposition that we have a benchmark where we know that our qubit on the Bloch Sphere is finding the global minimum*" can you clarify what this sentence means? (editing the post to clarify, not just replying in the comments) $\endgroup$
    – glS
    Feb 24, 2021 at 10:33

2 Answers 2

7
$\begingroup$

A precursor to the canonical QAOA is the Quantum Adiabatic Algorithm (QAA). Since we want to end up in the ground state of the Cost Hamiltonian ($H_C$) but don't know how to construct it, we exploit adiabaticity by starting with the ground state $|+\rangle^{\otimes n}$ of the (mixing) Hamiltonian $H_M = \sum_i \sigma_i^x$.

Now, if we slowly change a Hamiltonian, $H = (1 - s) H_M + s H_C$ according to some parametrization $s \in [0, 1]$, the state would continue to remain in the instantaneous eigenstate and you would end up in the ground state of the Cost Hamiltonian when $s = 1$.

This is a precursor to QAOA, since, the time evolution of the initial state can be written as a Trotterization of $H_M$ and $H_C$ and instead of having the unitary time evolution depend on $s$, new degrees of freedom are added and $H_M$ is evolved by $\beta_i$ and $H_C$ by $\gamma_i$ for each Trotterization step, $i \in [0, p]$ (which is what QAOA does). This connection with QAA is the closest thing I can think of to a guarantee that the QAOA should find the global optima.

QAA fails when the instantaneous eigenvalues of H are too close, and the adiabaticity condition on the sweeping speed from $H_m \rightarrow H_C$ is so slow that the algorithm is ultimately inefficient. QAOA, however, circumvents that problem by adding additional dimensions to the evolution and "sweeping" around the critical points/avoided crossings.

In practise, when experimenting with QAOA, there's no guarantee that the algorithm has converged to a global optima for a given value of $p$. You could very well only have found a local minima. But, as $p \rightarrow \infty$, QAOA approaches the QAA and the final result should approach the global minimum.

$\endgroup$
1
$\begingroup$

$\lvert + \rangle^{\otimes n}$ state is the Eigenstate of the Mixer $H_M$. By keeping the adiabatic process you can satisfy,

$$ H\lvert \psi \rangle = E_0 \lvert \psi \rangle $$

And finally get the Eigenvalue and Eigenstate of the Cost $H_C$

$\endgroup$

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.

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