Characterization of Exact One-Query Quantum Algorithms for Partial Boolean Functions  

作　　者：叶泽坤 李绿周 Ze-Kun Ye;Lv-Zhou Li(Institute of Quantum Computing and Computer Theory,School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou 510006,China;Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing,Sun Yat-sen University,Guangzhou 510006,China)

机构地区：[1]Institute of Quantum Computing and Computer Theory,School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou 510006,China [2]Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing,Sun Yat-sen University,Guangzhou 510006,China

出　　处：《Journal of Computer Science & Technology》2023年第6期1423-1430,共8页计算机科学技术学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.61772565 and 62272492;the Guangdong Basic and Applied Basic Research Foundation under Grant No.2020B1515020050;the Key Research and Development Program of Guangdong Province of China under Grant No.2018B030325001.

摘　　要：The query model(or black-box model)has attracted much attention from the communities of both classical and quantum computing.Usually,quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart.In the history of quantum algorithms,the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum algorithms.This leads us to con-sider the problem:what functions can be computed by exact one-query quantum algorithms?This problem has been ad-dressed in the literature for total Boolean functions and symmetric partial Boolean functions,but is still open for general partial Boolean functions.Thus,in this paper,we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean functions.First,we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum algorithms.Second,inspired by these conditions,we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ones.Specially,it is worth pointing out that before our work,the known func-tions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algo-rithm used is essentially the Deutsch-Jozsa algorithm,whereas the functions discovered in this paper are generally asym-metric and new algorithms to compute these functions are required.Thus,this expands the class of functions that can be computed by exact one-query quantum algorithms.

关 键 词：quantum computing quantum query complexity quantum algorithm 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]