量子布尔函数
该研究文章讨论了发展基于量子算法用于学习和测试仅依赖于 k 个输入变量的布尔函数(即 juntas)的有效算法,并着重于在没有经典或量子会员资格(“黑盒”)查询的情况下实现高效算法,其中量子算法仅需少量输入样本但可能需要许多经典随机样本,并阐述了算法的上下界。
Jul, 2007
本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果,其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题,并提高了期望严格学习的新下界,以达到经典 PAC 学习的已知上界。
Nov, 2004
该论文研究证明了所有基础一位量子门和两位 XOR 门可以作为量子通用门集,探究了构建所需的基本门数量,其中特别关注了广义的 Deutsch-Toffoli 门和任意 n 位酉操作所需门的数量。
Mar, 1995
该论文介绍了为了更好地实现、测试和资源评估量子算法,使用量子电路来评估量子算法文献中经常遇到的函数,以及借鉴目前高性能计算领域的经验优化这些电路,并实现了一个量子软件堆栈模块来自动生成用于计算基础函数的电路,以更详尽的成本分析启发未来量子计算设备的具体应用和降低计算基础算术成本的未来研究。
May, 2018
该研究论文证明了具有至多 k 非零傅里叶系数的函数在布尔超立方体上的上限,证明了学习 k-Fourier-sparse 布尔函数类所需的随机样本数量上限,同时也得出了傅里叶稀疏函数的布尔性测试的查询复杂性的上界。
Apr, 2015
本文针对傅里叶分析与高维几何中的一些经典问题做出了两个贡献,一个是证明了线性阈值函数最小傅里叶质量向量的一个下界,另一个则构建了一个算法来准确估算 Tomaszewski 常数。
Jul, 2012
本文研究了关于 Junta 学习问题的变体,分析了广义情况及量子查询复杂度,并展示了当预定义函数为 OR 函数或精确一半函数时最优的解决方案,对于大多数函数实现了二次优化。
Nov, 2013