# Convexity of cost function in quantum machine learning

I have a small confusion on convexity of the most typical cost function considered in many qml papers: $$\text{Tr}(\rho O)$$, where $$O$$ is a Hermitian operator and $$\rho$$ is a quantum state. This is indeed a convex function in terms of $$\rho$$ because this is linear in $$\rho$$. However, as soon as we parameterize $$\rho$$ in terms of parameterized quantum gates $$U(\theta)$$ so that we have $$\rho(\theta) = U(\theta) \rho(0) U^\dagger(\theta)$$, the cost function $$\text{Tr}(\rho(\theta) O)$$ is usually not convex function wrt $$\theta$$ (and I assume that's why VQE is not a convex optimization).

So this seems a little bit interesting to me, which I want to understand a bit deeper. Can anyone give a nice intuitive picture of why this is happening?

In fact, if we choose $$U(\theta)$$ to be SU(n) gate so that we can express any $$n$$ qubit states via $$U(\theta) \rho(0) U^\dagger(\theta)$$, then does the cost function would not be a convex function wrt $$\theta$$? (My guess would be no, but I'm curious to know more rigorously!)

• One important thing to note is that the more expressive your ansatz is, the less trainable it will be as the landscape becomes flatter. In the fact it was recently proven that if your ansatz $U(\theta)$ is sufficiently random that it matches the uniform distribution of unitaries up to the second moment, then the variance in the cost gradient will vanish exponentially with the number of qubits. arxiv.org/abs/2101.02138 So choosing $U(\theta)$ to be $SU(n)$ wouldn't be a good idea, let alone the fact that you would need an exponential number of gates to even achieve it. Commented Jun 8, 2022 at 13:03
You are of course exactly right that for generic parametrized unitaries $$U(\theta)$$ a typical cost function will be non-convex. In fact, the problem is so bad that the presence of local minimums makes the optimization NP-hard https://arxiv.org/abs/2101.07267 .
Your second question is very interesting: if $$U(\theta)$$ can cover the whole of $$SU(n)$$, does the optimization become convex? I do not think there is a proof, but empirically it seems that for reasonable parametrizations this is indeed the case. Something like a general argument can be found here https://arxiv.org/abs/2201.07448. You might also take a look at the discussion and further links in introduction here https://arxiv.org/abs/2204.07179 and in sec.III here https://arxiv.org/abs/2205.01121 (disclaimer: I am one of the authors).
Note that it takes exponentially large circuits to build $$U(\theta)$$ that are expressive enough to cover $$SU(n)$$.