. 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

DOI: 10.26421/qic15.11-12-1

Related papers

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$ .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.3193Aug 14, 20140 citations

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] \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.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.

arXiv:2006.05650Jun 10, 20201 citation

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.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.09176Leibniz international proceedings in informaticsNov 20, 20197 citations

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.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 ScienceNov 1, 202040 citations

Quantum lower bounds by quantum arguments

Andris Ambainis

We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $Ω(\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $Ω(\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.

arXiv:quant-ph/0002066Feb 24, 200013 citations

On the Two-sided Permutation Inversion Problem

Gorjan Alagic, Chen Bai, Alexander Poremba +1 more

In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation—except that the challenge value cannot be submitted to the latter. Within that setting, we consider three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself.In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation—except that the challenge value cannot be submitted to the latter. Within that setting, we consider three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself.

arXiv:2306.13729IACR Communications in CryptologyApr 9, 20246 citations

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

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

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.

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.

Ω(\sqrt{N})

lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.