Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2006.05650

Tight Quantum Time-Space Tradeoffs for Function Inversion

Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian

Published Jun 10, 2020• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2006.05650

Related papers

Tight Quantum Time-Space Tradeoffs for Function Inversion

Kai-Min Chung, Siyao Guo, Qipeng Liu +1 more

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 Õ(√{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=Õ(√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 the following results. (a) Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). (b) Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields the first quantum time-space lower bound for salted collision-finding, which in turn implies that PWPPO⊈ FBQPO/qpoly relative to a random oracle O.

Annual Symposium on Foundations of Computer Science•Nov 1, 2020•40 citations

Lower Bounds for Function Inversion with Quantum Advice

Kai-Min Chung, Tai-Ning Liao, Luowen Qian

Function inversion is the problem that given a random function $f: [M] \to [N]$, we want to find pre-image of any image $f^{-1}(y)$ in time $T$. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size $S$ that only depends on $f$ but not on $y$. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grover's algorithm, which does not leverage the power of preprocessing. Nayebi et al. proved a lower bound $ST^2 \ge \tildeΩ(N)$ for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where $M = O(N)$. In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al., to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.

arXiv:1911.09176•Leibniz international proceedings in informatics•Nov 20, 2019•7 citations

Quantum lower bound for inverting a permutation with advice

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs +1 more

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S = \tilde{\Omega}(\eps N)$ for quantum algorithms that invert a random permutation $f$ on an $\eps$ fraction of inputs, where $T$ is the number of queries to $f$ and $S$ is the amount of advice. This answers an open question of De et al. We also give a $\Omega(\sqrt{N/m})$ quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit $x_j$, given the ability to query an $N$-bit string $x$ at any index except the $j$-th, and also given $m$ bits of classical advice that depend on $x$ but not on $j$.

Quantum Information and Computation•Sep 1, 2015•17 citations

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds

Paul Beame, Blake Holman, Niels Kornerup

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

cs.CCCross-listedarXiv:2609.40334•Oct 1, 2026•0 citations

Quantum lower bound for inverting a permutation with advice

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs +1 more

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tildeΩ(εN)$ for quantum algorithms that invert a random permutation $f$ on an $ε$ fraction of inputs, where $T$ is the number of queries to $f$ and $S$ is the amount of advice. This answers an open question of De et al. We also give a $Ω(\sqrt{N/m})$ quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit $x_j$, given the ability to query an $N$-bit string $x$ at any index except the $j$-th, and also given $m$ bits of advice that depend on $x$ but not on $j$.

arXiv:1408.3193•Aug 14, 2014•0 citations

Quantum Search With Generalized Wildcards

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2 more

In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string $x \in \{-1,1\}^n$. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost $O(\sqrt{n} \log n)$ and a near-matching lower bound of $Ω(\sqrt{n})$. Belovs [Comput.~Comp.'15] subsequently showed a tight $O(\sqrt{n})$ upper bound. We consider a natural generalization of this problem, parametrized by a subset $\cal{Q} \subseteq 2^{[n]}$, where an algorithm may test whether $x_S = b$ for an arbitrary $S \in \cal{Q}$ and $b \in \{-1,1\}^S$ of its choice, at unit cost. We show near-tight bounds when $\cal{Q}$ is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning $x$ is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions $f : \{-1,1\}^n \to \mathbb{R}$ the ratio of the maximum value of $f$ to the maximum (over $T \in \cal{Q}$) standard deviation of $f$ on a subcube whose free variables are exactly $T$.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.

quant-pharXiv:2511.04669•Leibniz international proceedings in informatics•Nov 7, 2025•0 citations
In function inversion, we are given a function f:[N]↦[N]f: [N] \mapsto [N]f:[N]↦[N], and want to prepare some advice of size SSS, such that we can efficiently invert any image in time TTT. 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)ST^2 = \tildeΩ(N)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)\tilde O(\sqrt{N/S})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)ST^2 = \tildeΩ(N)ST2=Ω~(N). In this work, we prove that even with quantum advice, ST+T2=Ω~(N)ST + T^2 = \tildeΩ(N)ST+T2=Ω~(N) is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for S=O~(N)S = \tilde O(\sqrt{N})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.
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 Õ(√{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=Õ(√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 the following results. (a) Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). (b) Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields the first quantum time-space lower bound for salted collision-finding, which in turn implies that PWPPO⊈ FBQPO/qpoly relative to a random oracle O.
Function inversion is the problem that given a random function f:[M]→[N]f: [M] \to [N]f:[M]→[N], we want to find pre-image of any image f−1(y)f^{-1}(y)f−1(y) in time TTT. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size SSS that only depends on fff but not on yyy. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grover's algorithm, which does not leverage the power of preprocessing. Nayebi et al. proved a lower bound ST2≥Ω~(N)ST^2 \ge \tildeΩ(N)ST2≥Ω~(N) for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where M=O(N)M = O(N)M=O(N). In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al., to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.
Given a random permutation f:[N]→[N]f: [N] \to [N]f:[N]→[N] as a black box and y∈[N]y \in [N]y∈[N], we want to output x=f−1(y)x = f^{-1}(y)x=f−1(y). Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input yyy. Classically, there is a data structure of size O~(S)\tilde{O}(S)O~(S) and an algorithm that with the help of the data structure, given f(x)f(x)f(x), can invert fff in time O~(T)\tilde{O}(T)O~(T), for every choice of parameters SSS, TTT, such that S⋅T≥NS\cdot T \ge NS⋅T≥N. We prove a quantum lower bound of $T^2\cdot S = \tilde{\Omega}(\eps N)$ for quantum algorithms that invert a random permutation fff on an $\eps$ fraction of inputs, where TTT is the number of queries to fff and SSS is the amount of advice. This answers an open question of De et al. We also give a Ω(N/m)\Omega(\sqrt{N/m})Ω(N/m​) quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit xjx_jxj​, given the ability to query an NNN-bit string xxx at any index except the jjj-th, and also given mmm bits of classical advice that depend on xxx but not on jjj.
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an Ω(n4/3(log⁡log⁡n)/(S1/3log⁡n))Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))Ω(n4/3(loglogn)/(S1/3logn)) lower bound on the number of queries that a fully general quantum algorithm with at most SSS qubits of memory requires to sort nnn numbers from [n2][n^2][n2]. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family HHH from nnn bits to mmm bits, almost all hash functions in HHH require any algorithm with at most SSS qubits of memory to make Ω(nm/S)Ω(nm/S)Ω(nm/S) quantum queries to input xxx in order to compute h(x)h(x)h(x), even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing h(x)h(x)h(x) with both hhh and xxx as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.
Given a random permutation f:[N]→[N]f: [N] \to [N]f:[N]→[N] as a black box and y∈[N]y \in [N]y∈[N], we want to output x=f−1(y)x = f^{-1}(y)x=f−1(y). Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input yyy. Classically, there is a data structure of size O~(S)\tilde{O}(S)O~(S) and an algorithm that with the help of the data structure, given f(x)f(x)f(x), can invert fff in time O~(T)\tilde{O}(T)O~(T), for every choice of parameters SSS, TTT, such that S⋅T≥NS\cdot T \ge NS⋅T≥N. We prove a quantum lower bound of T2⋅S≥Ω~(εN)T^2\cdot S \ge \tildeΩ(εN)T2⋅S≥Ω~(εN) for quantum algorithms that invert a random permutation fff on an εεε fraction of inputs, where TTT is the number of queries to fff and SSS is the amount of advice. This answers an open question of De et al. We also give a Ω(N/m)Ω(\sqrt{N/m})Ω(N/m​) quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit xjx_jxj​, given the ability to query an NNN-bit string xxx at any index except the jjj-th, and also given mmm bits of advice that depend on xxx but not on jjj.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}nx \in \{-1,1\}^nx∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlog⁡n)O(\sqrt{n} \log n)O(n​logn) and a near-matching lower bound of Ω(n)Ω(\sqrt{n})Ω(n​). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n)O(\sqrt{n})O(n​) upper bound. We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n]\cal{Q} \subseteq 2^{[n]}Q⊆2[n], where an algorithm may test whether xS=bx_S = bxS​=b for an arbitrary S∈QS \in \cal{Q}S∈Q and b∈{−1,1}Sb \in \{-1,1\}^Sb∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q\cal{Q}Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning xxx is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→Rf : \{-1,1\}^n \to \mathbb{R}f:{−1,1}n→R the ratio of the maximum value of fff to the maximum (over T∈QT \in \cal{Q}T∈Q) standard deviation of fff on a subcube whose free variables are exactly TTT.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.