2020/06/10 by Kai-Min Chung, Chung, Kai-Min, Siyao Guo +5 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2006.05650
openalex publication_date 2020/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
In function inversion, we are given a function f: [N] ↦ [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 ST2 = Ω(N) for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time O(√(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 ST2 = Ω(N). In this work, we prove that even with quantum advice, ST + T2 = Ω(N) is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for S = O(√(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.