Quantum lower bounds by polynomials

TLDR

The polynomial method, a classical complexity tool, is extended to quantum decision trees, building on Nisan’s results linking randomized and deterministic decision‑tree complexities. The study investigates the query complexity required by quantum algorithms to compute Boolean functions on {0,1}^N in the black‑box model. The authors analyze how many black‑box queries a quantum algorithm needs, deriving bounds for total Boolean functions. They show that exponential quantum speed‑ups for partial functions cannot be achieved for any total function, proving that a quantum algorithm using T queries implies a deterministic algorithm with O(T^6) queries; they also give tight bounds for all symmetric functions and precise limits for AND, OR, and PARITY.

Abstract

We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 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.