论文标题
所有线性问题的量子最差案例减少平均值减少
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
论文作者
论文摘要
我们研究了设计最差的量子算法算法算法的问题的问题。对于所有线性问题，我们提供了量子算法的显式，有效的转换，这些算法仅在其输入的小（甚至子恒定）上正确的量子算法，这些算法在所有输入上都正确。这与经典环境相反，在经典环境中，这种结果仅因少量特定问题或受限计算模型而知。在途中，我们获得了一个紧密的$ω（n^2）$下限，对矩阵矢量乘法问题的平均量子量子查询复杂性。 我们的技术增强并概括了最近引入的添加剂组合框架，用于将经典的最差案例降低到平均案例降低（STOC 2022）到量子设置。我们依靠量子奇异值转换来构建量子算法，以从嘈杂的量子甲壳中叠加和学习Bogolyubov子空间中的线性验证。我们使用这些工具证明了量子局部校正引理，这是我们减少的核心，基于添加剂组合物中Bogolyubov的引理的噪声概率概括。
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands in contrast to the classical setting, where such results are only known for a small number of specific problems or restricted computational models. En route, we obtain a tight $Ω(n^2)$ lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem. Our techniques strengthen and generalise the recently introduced additive combinatorics framework for classical worst-case to average-case reductions (STOC 2022) to the quantum setting. We rely on quantum singular value transformations to construct quantum algorithms for linear verification in superposition and learning Bogolyubov subspaces from noisy quantum oracles. We use these tools to prove a quantum local correction lemma, which lies at the heart of our reductions, based on a noise-robust probabilistic generalisation of Bogolyubov's lemma from additive combinatorics.
