The complexity of quantum query algorithms computing booleanfunctions is related to the degree of the algebraic polynomial representing this boolean function. Hence to find a boolean function with quantum query compl...
详细信息
ISBN:
(纸本)1932415718
The complexity of quantum query algorithms computing booleanfunctions is related to the degree of the algebraic polynomial representing this boolean function. Hence to find a boolean function with quantum query complexity being smaller than the deterministic query complexity, one needs to find booleanfunctions with low degree of the representing polynomial and high deterministic query complexity. We have noticed that the existing examples of such booleanfunctions involve usage of combinatorial block designs being Kirkman triple systems. We have constructed new combinatorial block designs related to the Kirkman's schoolgirl problem hoping to use these designs to construct new booleanfunctions with a large gap between the quantum and deterministic query complexity.
暂无评论