Find in Library

We provide two sufficient and necessary conditions to characterize any <i>n</i>-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all <i>n</i>-bit partial Boolean functions that depend on <i>n</i> bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function <i>F</i> that maps any <i>n</i>-bit partial Boolean function to some integer, and if an <i>n</i>-bit partial Boolean function <i>f</i> depends on <i>k</i> bits and can be computed exactly by a 1-query quantum algorithm, then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>F</mi><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> is non-positive. In addition, we show that the number of all <i>n</i>-bit partial Boolean functions that depend on <i>k</i> bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on <i>n</i> and <i>k</i>. Most importantly, the upper bound is far less than the number of all <i>n</i>-bit partial Boolean functions for all efficiently big <i>n</i>.