论文标题
功能反转的紧密量子时间空间折衷
Tight Quantum Time-Space Tradeoffs for Function Inversion
论文作者
论文摘要
在函数倒转中，我们获得了一个函数$ f：[n] \ mapsto [n] $，并希望准备一些尺寸$ s $的建议，以便我们可以在时间$ t $中有效地转化任何图像。这是一个经过深入研究的问题，与密码学，数据结构，通信复杂性和电路下限有深刻的联系。 Nayebi，Aaronson，Belovs和Trevisan（2015）发起了对量子环境中此问题的调查，他们证明了$ st^2 = \tildeΩ（n）$的下限，以进行对经典建议的随机排列，以使Grover的搜索可能会引起搜索的可能性，以至于Grover的搜索可能是$ \ tilde的$ \ tilde o（sq）。 Hhan，Xagawa和Yamakawa（2019）以及Chung，Liao和Qian（2019）的最新作品扩大了随机功能和量子建议的论点，但下限保留$ st^2 = \tildeΩ（n）$。 在这项工作中，我们证明，即使有量子建议，算法也需要$ st + t = \tildeΩ（n）$转化随机函数。这表明Grover的搜索对于$ s = \ tilde o（\ sqrt {n}）$是最佳的，即使有量子建议，也排除了Grover搜索的任何实质性加速。如Corrigan-Gibbs和Kogan（2019）所示，对我们边界的进一步改进将暗示新的古典电路下限。 为了证明这一结果，我们开发了一个通用框架来建立量子时间空间下限。我们通过证明Yao的盒子问题和咸密码学的量子时间空间下限来进一步证明框架的力量。
In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of $ST^2 = \tildeΩ(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time $\tilde O(\sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains $ST^2 = \tildeΩ(N)$. In this work, we prove that even with quantum advice, $ST + T^2 = \tildeΩ(N)$ is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for $S = \tilde O(\sqrt{N})$, ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving quantum time-space lower bounds for Yao's box problem and salted cryptography.
