{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T15:15:00Z","timestamp":1769094900774,"version":"3.49.0"},"reference-count":0,"publisher":"Rinton Press","issue":"11&12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>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$.<\/jats:p>","DOI":"10.26421\/qic15.11-12-1","type":"journal-article","created":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T02:51:47Z","timestamp":1614480707000},"page":"901-913","source":"Crossref","is-referenced-by-count":5,"title":["Quantum lower bound for inverting a permutation with advice"],"prefix":"10.26421","volume":"15","author":[{"given":"Aran","family":"Nayebi","sequence":"first","affiliation":[]},{"given":"Scott","family":"Aaronson","sequence":"additional","affiliation":[]},{"given":"Aleksandrs","family":"Belovs","sequence":"additional","affiliation":[]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[]}],"member":"10955","published-online":{"date-parts":[[2015,9]]},"container-title":["Quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T02:51:48Z","timestamp":1614480708000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC15.11-12-1.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":0,"journal-issue":{"issue":"11&12","published-online":{"date-parts":[[2015,9]]},"published-print":{"date-parts":[[2015,9]]}},"URL":"https:\/\/doi.org\/10.26421\/qic15.11-12-1","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}