@inproceedings{deb1d29e0e544abab93faac8e5ae4deb,
title = "Combinatorial block designs for quantum computing problems",
abstract = "The complexity of quantum query algorithms computing Boolean functions 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 Boolean functions with low degree of the representing polynomial and high deterministic query complexity. We have noticed that the existing examples of such Boolean functions 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 Boolean functions with a large gap between the quantum and deterministic query complexity.",
keywords = "Block designs, Combinatorics, Kirkman's schoolgirl problem, Quantum query algorithms, Representing polynomials of Boolean functions",
author = "Rusiņ{\v s} Freivalds and Elina Kalniņa and Rihards Opmanis and Agnese Zalcmane",
year = "2005",
language = "English",
isbn = "9781932415711",
series = "Proceedings of the 2005 International Conference on Foundations of Computer Science, FCS'05",
pages = "176--182",
booktitle = "Proceedings of the 2005 International Conference on Foundations of Computer Science, FCS'05",
note = "2005 International Conference on Foundations of Computer Science, FCS'05 ; Conference date: 27-06-2005 Through 30-06-2005",
}