Quantum and Classical Tradeoffs
by
Yaoyun Shi
University of Michigan

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 talk I will present two results on this measure of quantumness, as well as some open problems. The first result 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. The 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=W(N).

Paper reference: arXiv:quant-ph/0312213

Date received: April 1, 2004