Quantum and classical tradeoffs

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 [Algorithms and Complexity: New Directions and Recent Results, Academic Press, New York, 1976, pp. 357-428]. Our second result shows that any quantum algorithm that solves Grover's Problem of size n using k queries and ℓ levels of non-basis-preserving gates must have kℓ=Ω(n).