Polynomial representation of general partial Boolean functions with a single quantum query

作     者：Guoliang, Xu Daowen, Qiu 

作者机构：College of Information Technology Luoyang Normal University Luoyang471934 China Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-Sen University Guangzhou510006 China 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2021年

核心收录：

主　　题：Quantum computers 

摘      要：Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Until recent years, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Establishing a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one;(2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query;(3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm. Essentially, the first discovery represent a step forward for a fundamental conclusion that the polynomial degree of partial Boolean functions with a single quantum query is one or two, and the last two results contribute a way for searching more nontrival partial Boolean functions that have quantum advantages. Copyright © 2021, The Authors. All rights reserved.