ECCC-Report TR14-109https://eccc.weizmann.ac.il/report/2014/109Comments and Revisions published for TR14-109en-usFri, 10 Apr 2015 20:16:20 +0300
Revision 1
| Quantum lower bound for inverting a permutation with advice |
Aran Nayebi,
Scott Aaronson,
Aleksandrs Belovs,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2014/109#revision1Given 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{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ 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 advice
that depend on $x$ but not on $j$.Fri, 10 Apr 2015 20:16:20 +0300https://eccc.weizmann.ac.il/report/2014/109#revision1
Paper TR14-109
| Quantum lower bound for inverting a permutation with advice |
Aran Nayebi,
Scott Aaronson,
Aleksandrs Belovs,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2014/109Given 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{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ 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 advice
that depend on $x$ but not on $j$.Thu, 14 Aug 2014 18:15:24 +0300https://eccc.weizmann.ac.il/report/2014/109