Journal
ENTROPY
Volume 23, Issue 2, Pages -Publisher
MDPI
DOI: 10.3390/e23020189
Keywords
quantum computation; quantum query complexity; quantum query algorithm; partial Boolean function
Categories
Funding
- National Natural Science Foundation of China [61572532, 61876195]
- Natural Science Foundation of Guangdong Province of China [2017B030311011]
Ask authors/readers for more resources
The research provides two conditions to characterize n-bit partial Boolean functions with quantum query complexity 1, and presents the properties of functions that meet these conditions. Additionally, a function mapping partial Boolean functions to integers is constructed, and an upper bound on the number of such functions is determined.
We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. 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 can be computed exactly by a 1-query quantum algorithm, 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 can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available