  We study quantum algorithms that are given access to trusted and untrusted
quantum witnesses. We establish strong limitations of such algorithms, via new
techniques based on Laurent polynomials (i.e., polynomials with positive and
negative integer exponents). Specifically, we resolve the complexity of
approximate counting, the problem of multiplicatively estimating the size of a
nonempty set $S \subseteq [N]$, in two natural generalizations of quantum query
complexity.
  Our first result holds in the standard Quantum Merlin--Arthur
($\mathsf{QMA}$) setting, in which a quantum algorithm receives an untrusted
quantum witness. We show that, if the algorithm makes $T$ quantum queries to
$S$, and also receives an (untrusted) $m$-qubit quantum witness, then either $m
= \Omega(|S|)$ or $T=\Omega \bigl(\sqrt{N/\left| S\right| } \bigr)$. This is
optimal, matching the straightforward protocols where the witness is either
empty, or specifies all the elements of $S$. As a corollary, this resolves the
open problem of giving an oracle separation between $\mathsf{SBP}$, the
complexity class that captures approximate counting, and $\mathsf{QMA}$.
  In our second result, we ask what if, in addition to a membership oracle for
$S$, a quantum algorithm is also given "QSamples" -- i.e., copies of the state
$\left| S\right\rangle = \frac{1}{\sqrt{\left| S\right| }} \sum_{i\in
S}|i\rangle$ -- or even access to a unitary transformation that enables
QSampling? We show that, even then, the algorithm needs either $\Theta
\bigl(\sqrt{N/\left| S\right| }\bigr)$ queries or else $\Theta \bigl(\min
\bigl\{\left| S\right| ^{1/3}, \sqrt{N/\left| S\right| }\bigr\}\bigr)$ QSamples
or accesses to the unitary.
  Our lower bounds in both settings make essential use of Laurent polynomials,
but in different ways.
