期刊
ENTROPY
卷 23, 期 2, 页码 -出版社
MDPI
DOI: 10.3390/e23020189
关键词
quantum computation; quantum query complexity; quantum query algorithm; partial Boolean function
资金
- National Natural Science Foundation of China [61572532, 61876195]
- Natural Science Foundation of Guangdong Province of China [2017B030311011]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据