We initiate the study of quantifying the quantumness of
a quantum circuit by the number of gates that do not preserve
the computational basis, as a means to understand the nature
of quantum algorithmic speedups.
Intuitively, a reduction in the quantumness requires
an increase in the amount of classical computation, thus giving
a ``quantum and classical tradeoff''.

In this paper we present two results on this measure of quantumness.
The first gives almost matching upper and lower bounds on the question:
``what is the minimum number of non-basis-preserving gates required
to generate a good approximation to a given state''.
This question is the quantum analogy of
the following classical question, ``how many fair coins
are needed to generate a given probability distribution'',
which was studied and resolved by Knuth and Yao in 1976.
Our second result shows that any quantum algorithm
that solves Grover's Problem of size $n$ using $k$ queries and
$\ell$ levels of non-basis-preserving gates must have $k\cdot\ell=\Omega(n)$.