7
$\begingroup$

Is VQE a class of algorithms or a specific algorithm? For example, is QAOA a VQE or is VQE an algorithm distinct from QAOA that solves the same class of problems?

If VQE is a specific algorithm, what are its defining features that distinguish it from other algorithms such as QAOA?

$\endgroup$
  • $\begingroup$ For reference, VQE was introduced in this paper as an alternative to quantum phase estimation with lower requirements for coherence time. $\endgroup$ – Jonathan Trousdale Oct 25 '19 at 12:46
9
$\begingroup$

I view QAOA as an algorithm for solving (approximately) a special class of problems, namely combinatorial problems and VQE as a possible subroutine to QAOA (but not necessarily as in the case of MaxCut). Let me explain

The VQE - Variational Quantum Eigensolver - solves the problem of approximating the smallest eigenvalue of some Hermitian operator $H$ which we usually just call Hamiltonian. As a byproduct, we also obtain a classical description of the approximate ground state. It does so by classically varying over efficiently preparable ansatz states $|\psi(\theta)\rangle$ and a quantum subroutine determines the expectation value $$\mu=\langle \psi (\theta)|H|\psi(\theta)\rangle$$ by a sampling procedure.

In QAOA (Quantum Approximate Optimization Algorithm), your cost function (or Hamiltonian if you will) is given by $H=\sum_i C_i(z)$ where the $C_i(z)$ are operators diagonal in the computational basis. Importantly, the eigenbasis of $H$ is thus the computational basis and one of the computational eigenstates encodes the solution to the problem! This, is not the case in VQE! So how does QAOA procece? On a high level, without going into too many details, it procedes very similarly to VQE:

  1. Optimize over variational parameters in some ansatz state. The state is called $|\gamma, \beta \rangle$ in QAOA and it ought to minimize/maximize the expectation value $$\langle \gamma, \beta|H|\gamma, \beta\rangle$$ In this step, VQE can be used as a subroutine as this is precisely the task VQE can achieve (finding good parameters $\beta, \gamma$) but it might not be necessary. In the original QAOA paper, the authors argued, that for particular instances of MaxCut (i.e. some particular classes of graphs), an efficient classical optimization method exists, that is, they could optimize over the ansatz state without ever preparing it (no quantum device involved)!
  2. Here, we necessarily go quantum (here you need a quantum device): Prepare the optimized ansatz state $|\psi_{opt} \rangle$ over and over again and measure it in the computational basis until you statistically converged enough to be able to pick the right computational basis state encoding the solution with high probability. (Note that because of the previous optimization routine, the state $|\psi_{opt} \rangle$ should have a large overlap with the eigenstate to the smallest eigenvalue which I stress once again is one of the basis vectors of the computational basis)

How is QAOA approximate you might ask now: Well, depending on how much computational resources you are willing to invest into finding good parameters, your $|\psi_{opt} \rangle$ might vary in quality. A bad quality state might not be close enough fidelity-wise to the eigenstate one is looking for. So the algorithm is approximate in the sense, that it tries to find a trade-off in the optimization procedure between optimization rounds and fidelity of the optimized state.

Note, that QAOA is just one possible application of VQE and there are many more, first and foremost quantum chemistry problems!

| improve this answer | |
$\endgroup$
  • $\begingroup$ excellent answer thank you $\endgroup$ – Malcolm Regan Oct 25 '19 at 15:03

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.