Here the authors argue that the efforts of creating a scalable quantum neural network using a set of parameterized gates are deemed to fail for a large number of qubits. This is due to the fact that, due to the Levy's Lemma, the gradient of a function in high dimensional spaces is almost zero everywhere.

I was wondering if this argument can be also applied to other hybrid quantum-classical optimization methods, like VQE (Variational Quantum Eigensolver) or QAOA (Quantum Approximate Optimization Algorithm).

What do you think?

  • $\begingroup$ "using a set of parametrized gates" What set? Is it random by any chance? $\endgroup$
    – rrtucci
    Jun 11, 2018 at 20:27
  • $\begingroup$ The article was written by Jarrod McClean, who is also the pioneer of VQE. I imagine Jarrod does not believe that VQE is deemed to fail for a larger number of qubits. I think your description of Levy's Lemma is a bit different from what the paper suggests. You say "the gradient of a function in high dimensional spaces is almost zero everywhere," but the paper only says that this is the case in the particular context of the QNNs described in the paper. $\endgroup$ Jun 11, 2018 at 20:28
  • $\begingroup$ To elaborate a bit on my last comment: One can just construct a high-dimensional function that changes very rapidly everywhere, it will not have a gradient of "almost zero" everywhere. The conclusion based on Levy's lemma in the paper, is for the specific function that they are optimizing, not for "any" function in a high-dimensional space. $\endgroup$ Jun 11, 2018 at 20:54
  • 1
    $\begingroup$ @asdf: After spending most of the day looking back and forth at the paper, I've finally come up with an answer for you. Take a look. $\endgroup$ Jun 12, 2018 at 0:48
  • $\begingroup$ related quantumcomputing.stackexchange.com/q/2056/55 $\endgroup$
    – glS
    Jun 12, 2018 at 19:36

1 Answer 1


First: The paper references [37] for Levy's Lemma, but you will find no mention of "Levy's Lemma" in [37]. You will find it called "Levy's Inequality", which is called Levy's Lemma in this, which is not cited in the paper you mention.

Second: There is an easy proof that this claim is false for VQE. In quantum chemistry we optimize the parameters of a wavefunction ansatz $|\Psi(\vec{p})\rangle$ in order to get the lowest (i.e. most accurate) energy. The energy is evaluated by:

$$ E_{\vec{p}} = \frac{\left\langle \Psi(\vec{p})\right|H\left|\Psi(\vec{p})\right\rangle}{\left\langle\Psi(\vec{p}) \right|\left.\Psi(\vec{p}) \right\rangle}. $$

VQE just means we use a quantum computer to evaluate this energy, and a classical computer to choose how to improve the parameters in $\vec{p}$ so that the energy will be lower in the next quantum iteration.

So whether or not the "gradient will be will be 0 almost everywhere when the number of parameters in $\vec{p}$ is large" does not depend at all on whether we are using VQE (on a quantum computer) or just running a standard quantum chemistry program (like Gaussian) on a classical computer. Quantum chemists typically variationally optimize the above energy with up to $10^{10}$ parameters in $\vec{p}$, and the only reason we don't go beyond that is because we run out of RAM, not because the energy landscape starts to become flat. In this paper you can see at the end of the abstract that they calculated the energy for a wavefunction with about $10^{12}$ parameters, where the parameters are coefficients of Slater determinants. It is generally known that the energy landscape is not so flat (like it would be if the gradient were 0 almost everywhere) even when there's a trillion parameters or even more.

Conclusion: The application of Levy's Lemma is going to depend on the particular energy landscape that you have, which will depend on both $H$ and your ansatz $|\Psi(\vec{p})\rangle$. In the case of their particular implementation of QNN's, they have found an application of Levy's Lemma to be appropriate. In the case of VQE, we have a counter-example to the claim that Levy's Lemma "always" applies. The counter example where Levy's Lemma does not apply is when $H$ is a molecular Hamiltonian and $|\Psi\rangle$ is a CI wavefunction.

  • $\begingroup$ There is an important difference between VQE and classical quantum chemistry programs. In the former, the parameters adjust the angles of unitary transformations like $\exp(i \theta F)$. In this setup, all implications of the paper in question do seem to apply to VQE just like they do to quantum machine learning. $\endgroup$ May 20, 2021 at 14:14
  • 1
    $\begingroup$ Unitary coupled cluster has also been done on classical computers but I've never heard of a case where the "gradient is almost 0 everywhere" .. Or at least, with an HF or MP2 initial condition, the "almost 0 everywhere" is irrelevant even if it were true. $\endgroup$ May 20, 2021 at 14:20
  • 1
    $\begingroup$ That's an important point about initial conditions! The McClean et al. paper considers the average over all possible assignments of parameters, while real computations start with some sensible initial guess. There's been some development in this regard, people discuss it in another question: quantumcomputing.stackexchange.com/questions/2056 $\endgroup$ May 20, 2021 at 14:26
  • $\begingroup$ Also, I think that UCC may not necessarily satisfy the conditions for the plateaus, as its structure is different from the "hardware efficient ansatz" states often considered for VQE $\endgroup$ May 20, 2021 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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