8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "using a set of parametrized gates" What set? Is it random by any chance? $\endgroup$ – rrtucci Jun 11 '18 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$ – user1271772 Jun 11 '18 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$ – user1271772 Jun 11 '18 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$ – user1271772 Jun 12 '18 at 0:48
  • $\begingroup$ related quantumcomputing.stackexchange.com/q/2056/55 $\endgroup$ – glS Jun 12 '18 at 19:36
3
$\begingroup$

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.

$\endgroup$

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.