One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.


翻译:质询模型在量子复杂性方面的突出地位,主要原因之一是存在具体的较低约束技术:多式方法和对称方法。我们付出了相当大的努力,不仅对使用这些方法的下限进行下限,甚至对之进行比较和联系。我们探索了对称函数类别量子查询复杂性的这些界限的价值,可以说是布林函数中最自然和最基本的一组。我们(使用最近引入的光谱敏感度)显示,这两个界限(正对数和近似度)都给每一种对称布林函数带来相同的价值。我们还审视了差距多数的量子查询复杂性,即部分对称功能。我们最近越来越重视随机查询复杂性的构成。我们在量子查询复杂性(Ben-David和Blax,FOCS 2020)上调随机复杂性(Ben-David和Blabs,FOCS )上下限。我们研究,在量子查询复杂性方面,与敏感度(持续因素)相比,证书复杂性和块灵敏度有多大,对于对称性功能的敏感度(我们展示了高度分立功能。我们展示了可能达到的高度分立的分函数。

0
下载
关闭预览

相关内容

【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
专知会员服务
76+阅读 · 2021年3月16日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
3+阅读 · 2018年10月11日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
0+阅读 · 2021年12月22日
Arxiv
0+阅读 · 2021年12月21日
Arxiv
0+阅读 · 2021年12月17日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
专知会员服务
76+阅读 · 2021年3月16日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Top
微信扫码咨询专知VIP会员