# Why is it hard to prove complexity bounds for variational algorithms?

I'm not very familiar with variational algorithms, but I've heard people say that they're "heuristic" and it's difficult to measure their performance via complexity analysis. Why is this the case? Are there any specific cases where, by further constraining the problem, we are able to perform a rigorous complexity analysis on a variational algorithm?

The goal of a variational quantum algorithm is to minimize a cost function $$f(\theta)$$ over $$\theta$$ where evaluating $$f$$ involves the output of a quantum computer. In short, the quantum computer helps us evaluate $$f(\theta)$$ and the classical computer uses some optimization algorithm to suggest new values of $$\theta$$ to try.

Take the case of the variational quantum eigensolver (VQE), where we are interested in finding the lowest energy eigenstate of a Hamiltonian $$H$$, with $$H|E_0\rangle=E_0|E_0\rangle$$. In this case, $$f(\theta) = \langle\psi(\theta)| H | \psi(\theta)\rangle$$ where $$H$$ is some Hamiltonian and $$|\psi(\theta)\rangle = U(\theta) |0\rangle$$ is some state prepared on the quantum computer by a circuit $$U(\theta)$$. There are a couple questions to ask:

1. Is $$|\psi(\theta)\rangle$$ actually capable of preparing $$|E_0\rangle$$? I.e. does there exist some $$\theta^*$$ such that $$|\psi(\theta^*)\rangle = |E_0\rangle$$?

2. If you've found some minimum of $$f$$, do you know whether it is a global or local minimum?

Without concrete answers to these questions, there's a sense in which $$f$$ is being treated as a black-box. Based on some knowledge of the physical system that $$H$$ represents, maybe you can come up with some heuristic about the properties that its ground state should have, etc.

As to your question of why people say that analyzing the complexity of these algorithms is hard: With VQEs, one reason is that the analysis usually requires making some assumptions about $$H$$ and $$U(\theta)$$.

Here are a few recent references on the complexity of these problems:

• Thanks for the detailed answer! Commented Nov 14, 2023 at 23:56

Looking for a solution by following a heuristic criteria means that you are proceeding by intuition, which has no proof of being correct nor efficient. You propose a heuristic, you show the results, but you are not fully characterising the solution space, so you do not know how far you actually are from optimal solutions.

People use heuristic approaches when these, for example, bring to better experimental solutions than, say, an algorithm with approximation boundary known. You don't know why, but it works.

Or whenever the problem is uncharted, any algorithm (computing a valid solution) can be proposed, such as variational quantum algorithms.