  Quantum algorithms manipulate the amplitudes of quantum states to find
solutions to computational problems. In this work, we present a framework for
applying a general class of non-linear functions to the amplitudes of quantum
states, with up-to an exponential improvement over the previous work. Our
framework accepts a state preparation unitary (or block-encoding), specified as
a quantum circuit, defining an $N$-dimensional quantum state. We then construct
a diagonal block-encoding of the amplitudes of the quantum state, building on
and simplifying previous work. Techniques from the QSVT literature are then
used to process this block-encoding. The source of our exponential speedup
comes from the quantum analog of importance sampling. We then derive new
error-bounds relevant for end-to-end applications, giving the error in terms of
$\ell_2$-norm error. We demonstrate the power of this framework with four key
applications. First, our algorithm can apply the important function $\tanh(x)$
to the amplitudes of an arbitrary quantum state with at most an $\ell_2$-norm
error of $\epsilon$, with worst-case query complexity of $O(\log(N/\epsilon))$,
in comparison to the $O(\sqrt{N}\log(N/\epsilon))$ of prior work. Second, we
present an algorithm solving a new formulation of maximum finding in the
unitary input model. Third, we prove efficient end-to-end complexities in
applying a number of common non-linear functions to arbitrary quantum states.
Finally, we generalize and unify existing quantum arithmetic-free
state-preparation techniques. Our work provides an important and efficient
algorithmic building block with potentially numerous applications in areas such
as optimization, state preparation, quantum chemistry, and machine learning.
