QLunch: Lennart Bittel

Speaker: Lennart Bittel, Heinrich-Heine-Universität Düsseldorf

Title: On the complexity theoretic hardness of VQAs and QAOAs.

Abstract: 

Variational Quantum Algorithms (VQAs), such as the Quantum Approximate

Optimization Algorithm (QAOA) have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the depth of the variational “ansatz” used — the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. This potential for depth reduction has made VQAs a staple of Noisy Intermediate-Scale Quantum (NISQ)-era research.

In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that it is QCMA-hard to approximate the optimal depth of a VQA ansatz within a multiplicative factor. Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP. We then show that this hardness persists even in the “simpler” setting of QAOAs.