Optimizing the depth of variational quantum algorithms is strongly
QCMA-hard to approximate
Optimizing the depth of variational quantum algorithms is strongly
QCMA-hard to approximate
Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the \emph{depth} of the variational ``ansatz'' used -- the smaller the depth, the more amenable the ansatz …