  It has been known for almost three decades that many $\mathrm{NP}$-hard
optimization problems can be solved in polynomial time when restricted to
structures of constant treewidth. In this work we provide the first extension
of such results to the quantum setting. We show that given a quantum circuit
$C$ with $n$ uninitialized inputs, $\mathit{poly}(n)$ gates, and treewidth $t$,
one can compute in time $(\frac{n}{\delta})^{\exp(O(t))}$ a classical
assignment $y\in \{0,1\}^n$ that maximizes the acceptance probability of $C$ up
to a $\delta$ additive factor. In particular, our algorithm runs in polynomial
time if $t$ is constant and $1/poly(n) < \delta < 1$. For unrestricted values
of $t$, this problem is known to be complete for the complexity class
$\mathrm{QCMA}$, a quantum generalization of MA. In contrast, we show that the
same problem is $\mathrm{NP}$-complete if $t=O(\log n)$ even when $\delta$ is
constant.
  On the other hand, we show that given a $n$-input quantum circuit $C$ of
treewidth $t=O(\log n)$, and a constant $\delta<1/2$, it is
$\mathrm{QMA}$-complete to determine whether there exists a quantum state
$\mid\!\varphi\rangle \in (\mathbb{C}^d)^{\otimes n}$ such that the acceptance
probability of $C\mid\!\varphi\rangle$ is greater than $1-\delta$, or whether
for every such state $\mid\!\varphi\rangle$, the acceptance probability of
$C\mid\!\varphi\rangle$ is less than $\delta$. As a consequence, under the
widely believed assumption that $\mathrm{QMA} \neq \mathrm{NP}$, we have that
quantum witnesses are strictly more powerful than classical witnesses with
respect to Merlin-Arthur protocols in which the verifier is a quantum circuit
of logarithmic treewidth.
