本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果,其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题,并提高了期望严格学习的新下界,以达到经典 PAC 学习的已知上界。
Nov, 2004
通过量子计算,我们提出了一个具有改进复杂性的量子算法来解决有限和优化问题,使得我们可以找到一个 ε- 最优解点。
Jun, 2024
采用量子对手来证明问题下界的新方法,通过设法获得足够的纠缠状态来限制计算的查询数,推出 AND 的 OR、排列倒置等计算所需的最小查询数。
Feb, 2000
本文研究了关于 Junta 学习问题的变体,分析了广义情况及量子查询复杂度,并展示了当预定义函数为 OR 函数或精确一半函数时最优的解决方案,对于大多数函数实现了二次优化。
Nov, 2013
本研究介绍了两种针对随机过程的量子算法,分别用于热吉布斯态的准备和马尔可夫链的命中时间估计,并使用哈密顿模拟、谱间隙放大和线性方程组解法等工具进行实现。
Mar, 2016
本研究提出了三种不同的量子算法,可以解决最大二分匹配问题,最大非二分匹配问题以及整数网络中的最大流问题。
Aug, 2005
本文针对量子计算机的性能和量子电路等问题,探讨了量子优越性、采样、复杂度等方面的理论基础及相关算法,并展示了量子优越性相对于多项式层次、BPP、BQP 等的可行性及其假设。
Dec, 2016
通过对 Pauli 谱的 2 - 范数或归一化 Frobenius 范数的演化算符进行查询,构建了 “n” 量子比特 “k” 局域哈密顿的测试和学习问题。通过我们的研究,解决了在 Bluhm,Caro 和 Oufkir 最近的工作中提出的两个问题,并展示了简洁、基于 Pauli 分析技术的证明。
Apr, 2024
使用 IQP 计算加强量子计算难以经典模拟的猜想,研究了推断两个可信度均值情况下的 IQP 计算难度和经典模拟误差大小;一个关于计算随机基态因子函数硬度,另一个探究低阶多项式零点的计算难度,这两个猜想在最坏情况下得以验证。
Apr, 2015
该论文通过对量子对手界限进行综合分析和研究,得出了其适用于任意单量子比特部分函数、状态生成和状态转换问题以及实现任意幺正变换的版本,并获得了一些关于一般性输入预言机的函数和关系的量子查询复杂度的下界。