  What is the power of polynomial-time quantum computation with access to an NP
oracle? In this work, we focus on two fundamental tasks from the study of
Boolean satisfiability (SAT) problems: search-to-decision reductions, and
approximate counting. We first show that, in strong contrast to the classical
setting where a poly-time Turing machine requires $\Theta(n)$ queries to an NP
oracle to compute a witness to a given SAT formula, quantumly $\Theta(\log n)$
queries suffice. We then show this is tight in the black-box model - any
quantum algorithm with "NP-like" query access to a formula requires
$\Omega(\log n)$ queries to extract a solution with constant probability.
Moving to approximate counting of SAT solutions, by exploiting a quantum link
between search-to-decision reductions and approximate counting, we show that
existing classical approximate counting algorithms are likely optimal. First,
we give a lower bound in the "NP-like" black-box query setting: Approximate
counting requires $\Omega(\log n)$ queries, even on a quantum computer. We then
give a "white-box" lower bound (i.e. where the input formula is not hidden in
the oracle) - if there exists a randomized poly-time classical or quantum
algorithm for approximate counting making $o(log n)$ NP queries, then
$\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete
problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$
contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is
quantum.
