  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 is to near-term quantum
hardware in that it gives the circuit a chance to be fully executed before the
system decoheres. In this work, we show that approximating the optimal depth
for a given VQA ansatz is intractable. Formally, we show that for any constant
$\epsilon>0$, it is QCMA-hard to approximate the optimal depth of a VQA ansatz
within multiplicative factor $N^{1-\epsilon}$, for $N$ denoting the encoding
size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a
quantum generalization of NP.) We then show that this hardness persists in the
even ``simpler'' QAOA-type settings. To our knowledge, this yields the first
natural QCMA-hard-to-approximate problems.
