Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I believe finding the optimal solution is guaranteed for Grover's Algorithm along with quadratic speed-up according to Nielsen and Chuang's book.
I wonder if there is any statement regarding QAOA and VQE for the performance such as success probability or/and speed aspect.
First of all, QAOA can be regarded as an application of VQE. (Take a look at this answer.) Therefore, we can consider their performance to be similar enough to talk about them together. Although for some particular cases, a quantum computer isn't even needed for QAOA, but let's consider only the cases in which quantum circuits are used.
Briefly, it is not known yet what the speed-up of these two algorithms is over classical algorithms; we don't even know if there's any. But we can still talk about their performance irrespective of their classical counterparts.
In the paper in which QAOA is introduced, the authors state that "the depth of the circuit grows linearly with $p$ times (at worst) the number of constraints. If $p$ is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing", (A Quantum Approximate Optimization Algorithm). Where $p \geq 1$ and the quality of the approximation grows with it.
Regarding the performance of VQE and ADAPT-VQE (which use adaptive derivative-assembled pseudo-trotter ansatzes), you can read Benchmarking Adaptive Variational Quantum Eigensolvers. Here, it is showed that ADAPT-VQE are more robust in certain cases and that regular VQE depends heavily in the optimizer performance. I recommend you reading this because novel approaches to VQE make its performance differ from that of QAOA, even though they are very similar.
