论文标题
巨大的量子加速需要多少结构？
How Much Structure Is Needed for Huge Quantum Speedups?
论文作者
论文摘要
对于一般科学的受众，我调查了三十年的研究，这些问题承认通过量子计算机进行指数加速，从经典（例如西蒙和肖尔的算法）到山川和Zhandry的突破，从2022年4月开始，我在范围或Quartium circuitt模型上进行了启动，我们是在范围内进行的。或查询复杂性模型，我们设法实现了更彻底的理解，从而告知我们对电路模型的猜想。我讨论了将注意力转移到抽样任务的优势和缺点，就像最近的量子至上实验中所做的那样。我对实用机器学习和优化问题的指数量子加速的广泛重复主张做出了一些怀疑的评论。通过许多示例，我试图传达“怪异的保护定律”，据此，每个承认指数量子加速的问题都必须具有一些不寻常的特性，以允许振幅集中在未知的正确答案上。
I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. I discuss both the quantum circuit model, which is what we ultimately care about in practice but where our knowledge is radically incomplete, and the so-called oracle or black-box or query complexity model, where we've managed to achieve a much more thorough understanding that then informs our conjectures about the circuit model. I discuss the strengths and weaknesses of switching attention to sampling tasks, as was done in the recent quantum supremacy experiments. I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s).
