6533b82cfe1ef96bd128ea74

RESEARCH PRODUCT

Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

R. FreivaldsL. Garkaje

subject

CombinatoricsComplexity indexDiscrete mathematicsZero of a functionKarp–Lipton theoremHomogeneous polynomialBoolean expressionDegree of a polynomialBoolean functionMathematicsMatrix polynomial

description

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.

yearjournalcountryeditionlanguage
2007-05-0137th International Symposium on Multiple-Valued Logic (ISMVL'07)
https://doi.org/10.1109/ismvl.2007.11