On the power of Ambainis's lower bounds
Author:
Preprint
Abstract
The polynomial method and Ambainis's lower bound method are two main quantum lower bound techniques. Recently Ambainis showed that the polynomial method is not tight. The present paper aims at studying the limitation of Ambainis's lower bounds. We first give a generalization of the three known Ambainis's lower bound theorems. Then it is shown that all these four Ambainis's lower bounds have an upper bound, which is in terms of certificate complexity. This implies that for some problems such as TRIANGLE, $k$-CLIQUE, and BIPARTITE/GRAPH MATCHING whose quantum query complexities are still open, the best known lower bounds cannot be further improved by using Ambainis's techniques. Another consequence is that all the Ambainis's lower bounds are not tight. Finally, we show that for total functions, this upper bound for Ambainis's lower bounds can be further improved. This also implies limitation of Ambainis's method on some specific problems such as AND-OR TREE, whose precise quantum complexity is still unknown.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- A lower bound on the quantum query complexity of read-once functionsJournal of Computer and System Sciences, 2004
- Quantum query complexity and semi-definite programming2004
- A better lower bound for quantum algorithms searching an ordered list2003
- Quantum Lower Bounds by Quantum ArgumentsJournal of Computer and System Sciences, 2002
- Quantum lower bounds for the collision and the element distinctness problems2001
- Quantum oracle interrogation: getting all information for almost half the price1998
- Quantum vs. classical communication and computation1998
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992