论文标题：On the exact quantum query complexity of MOD and EXACT functions

期刊：Frontiers of Computer Science

作者：Penghui YAO, Zekun YE

发表时间：15 Apr 2025

DOI： 10.1007/s11704-024-3770-4

微信链接：点击此处阅读微信文章

引用格式：

Penghui YAO, Zekun YE. On the exact quantum query complexity of MOD and EXACT functions. Front. Comput. Sci., 2025, 19(4): 194901

阅读原文：

问题概述

针对对称函数的精确量子查询复杂性，本文提出了关于MOD和EXACT函数的精确量子算法，对MOD和EXACT函数的精确量子查询复杂性进行刻画。

技术步骤

本文首先提出一个精确量子算法去计算n位布尔字符串的汉明权重模n的值，然后将该算法作为子程序去设计计算MOD和EXACT函数的精确量子算法。

实验结果

我们设计了计算MOD函数的最优量子查询算法，从而提供了对其精确量子查询复杂性的完美刻画。基于此算法，我们展示了在量子模型中许多对称函数不是诡的，即存在量子算法使用少于输入规模的查询次数去精确计算这些函数。 此外，对于特定的k和l，我们提出了最优的查询算法去精确计算EXACT函数，从而在这些情况下对其精确量子查询复杂性进行了完美的刻画。

期刊简介

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办，南京大学支持，SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐B类期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；两次入选“中国科技期刊卓越行动计划”（一期梯队、二期领军）。

中国学术前沿期刊网

http://journal.hep.com.cn