  We propose an approach for quantifying a quantum circuit's quantumness as a
means to understand the nature of quantum algorithmic speedups. Since quantum
gates that do not preserve the computational basis are necessary for achieving
quantum speedups, it appears natural to define the quantumness of a quantum
circuit using the number of such gates. Intuitively, a reduction in the
quantumness requires an increase in the amount of classical computation, hence
giving a ``quantum and classical tradeoff''.
  In this paper we present two results on this direction. The first gives an
asymptotic answer to 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 l levels of non-basis-preserving gates must have
k*l=\Omega(n).
