Partial Boolean functions with exact quantum 1-query complexity

Abstract

We provide two sufficient and necessary conditions to characterize any $n$-bit partial Boolean function with exact quantum 1-query complexity. Using the first characterization, we present all $n$-bit partial Boolean functions that depend on $n$ bits and have exact quantum 1-query complexity. Due to the second characterization, we construct a function $F$ that maps any $n$-bit partial Boolean function to some integer, and if an $n$-bit partial Boolean function $f$ depends on $k$ bits and has exact quantum 1-query complexity, then $F(f)$ is non-positive. In addition, we show that the number of all $n$-bit partial Boolean functions that depend on $k$ bits and have exact quantum 1-query complexity is not bigger than $n^2{2}^{2^{n-1}(1+2^{2-k})+2n^2}$ for all $n\ge 3$ and $k\ge 2$.

arXiv comment11pages; comments are welcome

References in corpus (11)

• Quantum algorithm for solving linear systems of equations
• Improved quantum algorithms for the ordered search problem via semidefinite programming
• On exact quantum query complexity
• Quantum Query Algorithms are Completely Bounded Forms
• Exact quantum query complexity of EXACT and THRESHOLD
• Characterization of exact one-query quantum algorithms
• Unbounded Error Quantum Query Complexity
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• Quantum Query as a State Decomposition
• On the sum-of-squares degree of symmetric quadratic functions
• Classical-Quantum Separations in Certain Classes of Boolean Functions-- Analysis using the Parity Decision Trees

Cited by in corpus (1)

• Oracle problems as communication tasks and optimization of quantum algorithms