I have seen the recent paper "Training Variational Quantum Algorithms Is NP-Hard (Phys. Rev. Lett. 127, 120502)" and the authors stated that training the classical optimization in variational quantum algorithms is NP-Hard.

Does it mean we cannot achieve a significant quantum computational advantage over classical computing in solving certain problems via variational quantum algorithms?

I am fresh in the quantum computing field and cannot fully understand its meaning. It would be really appreciated if someone can show what the results really imply.


The paper doesn't address very much the "fully classical" approach to their problems, so I don't think they are making a judgment one way or another about quantum advantage with VQA. But they are part of a growing body of literature arguing very wisely that the complexity of classical optimization cannot be ignored, when assessing the complexity of hybrid quantum-classical algorithms.

In particular, this paper proves that optimizing even the simplest cost-functions and ansatze is generally NP-hard. I've not dug into the details of the proof, so I hope someone else can fill in my answer with the appropriate nuance, but I think their proof implies that any polynomial implementation of a classical optimization cannot guarantee the error in optimization is polynomially bounded, even when restricted to the simplest quantum problems. (Unless $P=NP$, that is.)

Super-polynomial error, or a super-polynomial algorithm, in your hybrid algorithm does not strictly preclude computational advantage over fully classical techniques, but it is certainly disheartening. That said, the authors do offer consolation in the last couple paragraphs. The penultimate paragraph concludes:

This result emphasizes the need for effective initialization procedures for VQA algorithms and poses the challenge of finding nonlocal heuristics for VQA optimization ... to reach smaller optimization errors.

In other words, the general solution might be NP-hard, but if we're careful and clever, we might still get answers that are "good enough".

(Of course, the same might be said of fully classical approaches. But the authors don't. ^_^)

  • 1
    $\begingroup$ Thanks a lot for your clarification! Really help me understand it. $\endgroup$ Sep 29 at 4:44

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.