Physics – Quantum Physics
Scientific paper
1998-02-18
Physics
Quantum Physics
10 pages, LaTeX, no figures, final version to appear in FOCS'98
Scientific paper
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
Beals Robert
Buhrman Harry
Cleve Richard
Mosca Michele
Wolf Ronald de
No associations
LandOfFree
Quantum Lower Bounds by Polynomials 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 Lower Bounds by Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Lower Bounds by Polynomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-386693