Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR04-023 | 21st January 2004 00:00

TR04-023
Authors: Yaoyun Shi
Publication: 6th April 2004 22:32
Keywords:

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

ISSN 1433-8092 | Imprint