Abstract
Function inversion is the problem that given a random function f: [M] → [N], we want to find preimage 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 wellstudied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grover’s algorithm [Grover, 1996], which does not leverage the power of preprocessing.
Nayebi et al. [Nayebi et al., 2015] proved a lower bound ST² ≥ ̃Ω(N) for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. [Minki Hhan et al., 2019] 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. [Ambainis et al., 1999], to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variablelength 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.
BibTeX  Entry
@InProceedings{chung_et_al:LIPIcs:2020:12113,
author = {KaiMin Chung and TaiNing Liao and Luowen Qian},
title = {{Lower Bounds for Function Inversion with Quantum Advice}},
booktitle = {1st Conference on InformationTheoretic Cryptography (ITC 2020)},
pages = {8:18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771511},
ISSN = {18688969},
year = {2020},
volume = {163},
editor = {Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12113},
URN = {urn:nbn:de:0030drops121134},
doi = {10.4230/LIPIcs.ITC.2020.8},
annote = {Keywords: Cryptanalysis, Data Structures, Quantum Query Complexity}
}
Keywords: 

Cryptanalysis, Data Structures, Quantum Query Complexity 
Collection: 

1st Conference on InformationTheoretic Cryptography (ITC 2020) 
Issue Date: 

2020 
Date of publication: 

04.06.2020 