Abstract:
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)$.