Quantum Lower Bounds by Polynomials
arXiv:quant-ph/9802049
Abstract
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.
10 pages, LaTeX, no figures, final version to appear in FOCS'98
References in corpus (5)
Cited by in corpus (69)
- The Physical Implementation of Quantum Computation
- Random Oracles in a Quantum World
- Quantum Counting
- Quantum communication complexity of symmetric predicates
- Quantum Computers and Quantum Coherence
- Quantum Search on Bounded-Error Inputs
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum Computation
- An Introduction to Quantum Complexity Theory
- Improved Bounds on Quantum Learning Algorithms
- Superiority of exact quantum automata for promise problems
- Improved Quantum Communication Complexity Bounds for Disjointness and Equality
- Introduction to Quantum Algorithms for Physics and Chemistry
- Bounds for Small-Error and Zero-Error Quantum Algorithms
- How many functions can be distinguished with k quantum queries?
- Theory of quantum computation
- A quantum lower bound for the collision problem
- On the Quantum Black-Box Complexity of Majority
- Local Hamiltonians in Quantum Computation
- Quantum lower bounds by quantum arguments
- Lower Bounds for Quantum Search and Derandomization
- A Limit on the Speed of Quantum Computation for Insertion into an Ordered List
- Communication Complexity Lower Bounds by Polynomials
- Robust Quantum Algorithms for Oracle Identification
- The quantum query complexity of approximating the median and related statistics
- Classical and Quantum Complexity of the Sturm-Liouville Eigenvalue Problem
- The Quantum Complexity of Set Membership
- From Monte Carlo to Quantum Computation
- An Almost-Quadratic Lower Bound for Quantum Formula Size
- Bounds on quantum ordered searching
- A better lower bound for quantum algorithms searching an ordered list
- Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds
- Robust Quantum Algorithms with $\eps$-Biased Oracles
- Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces
- Query complexity for searching multiple marked states from an unsorted database
- Quantum search processes in the cyclic group state spaces
- Almost-Everywhere Superiority for Quantum Computing
- Comparative Computational Strength of Quantum Oracles
- Quantum lower bound for sorting
- Tight adaptive reprogramming in the QROM
- The Structure of Promises in Quantum Speedups
- Quantum versus Classical Learnability
- Quantum Computation Relative to Oracles
- Block Sensitivity of Minterm-Transitive Functions
- Quantum Evaluation of Multi-Valued Boolean Functions
- A note on quantum black-box complexity of almost all Boolean functions
- Quantum Property Testing
- The Quantum Setting with Randomized Queries for Continuous Problems
- On the Complexity of Searching Maximum of a Function on a Quantum Computer
- The basic principles to construct a generalized state-locking pulse field and simulate efficiently the reversible and unitary halting protocol of a universal quantum computer
- Query Complexity: Worst-Case Quantum Versus Average-Case Classical
- Quantum Lower Bounds by Entropy Numbers
- Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers
- Quantum Zero-Error Algorithms Cannot be Composed
- Quantum NP and a Quantum Hierarchy
- Average case quantum lower bounds for computing the boolean mean
- One Complexity Theorist's View of Quantum Computing
- Quantum optical device accelerating dynamic programming
- A note on quantum one-way permutations
- On a Problem in Quantum Summation
- Unconditionally-secure and reusable public-key authentication
- Algorithms for Boolean Function Query Properties
- Quantum Summation with an Application to Integration
- Quantum Formulas: a Lower Bound and Simulation
- Quantum Money from Quaternion Algebras
- Entropy lower bounds of quantum decision tree complexity
- The unitary dynamical state-locking process, the HSSS quantum search process, and the quantum-computing speedup theory
- On deciding whether a Boolean function is constant or not
- A Super-Grover Separation Between Randomized and Quantum Query Complexities