6533b7d4fe1ef96bd12633e1

RESEARCH PRODUCT

Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms

Elīna KalniņaJevgeņijs IvanovsLelde LāceDaina TaimiņaHisayuki TatsumiRūsiņš FreivaldsRaitis OzolsMasahiro Miyakawa

subject

Complexity indexDiscrete mathematicsProduct termTheoretical computer scienceParity functionKarp–Lipton theoremBoolean circuitMaximum satisfiability problemBoolean expressionBoolean functionAlgorithmComputer Science::DatabasesMathematics

description

The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.

yearjournalcountryeditionlanguage
2005-01-01
https://doi.org/10.1007/978-3-540-30577-4_50