__
TR04-023 | 21st January 2004 00:00
__

#### Quantum and Classical Tradeoffs

**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)$.