Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the Satisfiability of Quantum Circuits of Small Treewidth   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.

30
The categories of this paper are: q-alg
36
The categories of this paper are: cmp-lg
15
The categories of this paper are: nucl-ex
2
The categories of this paper are: math
18
The categories of this paper are: econ
29
The categories of this paper are: funct-an
10
The categories of this paper are: q-bio
4
The categories of this paper are: cond-mat
14
The categories of this paper are: math-ph
19
The categories of this paper are: eess
6
The categories of this paper are: astro-ph
12
The categories of this paper are: nucl-th
31
The categories of this paper are: ao-sci
25
The categories of this paper are: patt-sol
21
The categories of this paper are: adap-org
7
The categories of this paper are: hep-th