ECCC-Report TR04-023https://eccc.weizmann.ac.il/report/2004/023Comments and Revisions published for TR04-023en-usTue, 06 Apr 2004 22:32:01 +0200
Paper TR04-023
| Quantum and Classical Tradeoffs |
Yaoyun Shi
https://eccc.weizmann.ac.il/report/2004/023We 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)$.
Tue, 06 Apr 2004 22:32:01 +0200https://eccc.weizmann.ac.il/report/2004/023