Physics – Quantum Physics
Scientific paper
2003-12-30
Physics
Quantum Physics
Scientific paper
10.1016/j.tcs.2005.03.053
We propose an approach for quantifying a quantum circuit's quantumness as a means to understand the nature of quantum algorithmic speedups. Since quantum gates that do not preserve the computational basis are necessary for achieving quantum speedups, it appears natural to define the quantumness of a quantum circuit using the number of such gates. Intuitively, a reduction in the quantumness requires an increase in the amount of classical computation, hence giving a ``quantum and classical tradeoff''. In this paper we present two results on this direction. The first gives an asymptotic answer to 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 l levels of non-basis-preserving gates must have k*l=\Omega(n).
No associations
LandOfFree
Quantum and Classical Tradeoffs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum and Classical Tradeoffs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum and Classical Tradeoffs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-600288