Training Variational Quantum Algorithms Is NP-Hard

Area of Science:

• Quantum Computing
• Computational Complexity Theory
• Quantum Chemistry

Background:

• Variational quantum algorithms (VQAs) like VQE and QAOA are prominent for near-term quantum devices.
• These algorithms train parametrized quantum circuits using classical optimization.

Purpose of the Study:

• To analyze the computational complexity of the classical optimization problems inherent in VQAs.
• To determine if the hardness of VQAs originates from the quantum problem or the classical optimization itself.

Main Methods:

• Theoretical analysis of the classical optimization landscape associated with VQAs.
• Investigation of worst-case instances for polynomial-time classical algorithms.
• Examination of specific cases like logarithmic qubits and free fermions.

Main Results:

• The classical optimization problems for VQAs are proven to be NP-hard.
• This hardness is robust, implying significant approximation errors for polynomial-time algorithms (assuming P≠NP).
• Optimization remains NP-hard even for classically tractable quantum systems, indicating intrinsic classical difficulty.

Conclusions:

• The classical optimization component of VQAs is intrinsically hard, not just a reflection of the underlying quantum problem.
• Training landscapes often contain numerous persistent local minima, impeding gradient-based optimization.
• VQAs may generally converge to suboptimal solutions due to these challenging optimization landscapes.