Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight Quantum Time-Space Tradeoffs for Function Inversion
117
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 = tildeOmega(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grovers 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 = tildeOmega(N)$. In this work, we prove that even with quantum advice, $ST + T^2 = tildeOmega(N)$ is required for an algorithm to invert random functions. This demonstrates that Grovers search is optimal for $S = tilde O(sqrt{N})$, ruling out any substantial speed-up for Grovers 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 Yaos box problem and salted cryptography.
rate research
Read More
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 Grovers algorithm, which does not leverage the power of preprocessing. Nayebi et al. proved a lower bound $ST^2 ge tildeOmega(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.
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the Disjointness function. Our direct product theorems imply a time-space tradeoff T^2*S=Omega(N^3) for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time-space and communication-space tradeoffs for the problems of Boolean matrix-vector multiplication and matrix multiplication.
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
We explore bounds of {em time-space tradeoffs} in language recognition on {em two-way finite automata} for some special languages. We prove: (1) a time-space tradeoff upper bound for recognition of the languages $L_{EQ}(n)$ on {em two-way probabilistic finite automata} (2PFA): $TS={bf O}(nlog n)$, whereas a time-space tradeoff lower bound on {em two-way deterministic finite automata} is ${bf Omega}(n^2)$, (2) a time-space tradeoff upper bound for recognition of the languages $L_{INT}(n)$ on {em two-way finite automata with quantum and classical states} (2QCFA): $TS={bf O}(n^{3/2}log n)$, whereas a lower bound on 2PFA is $TS={bf Omega}(n^2)$, (3) a time-space tradeoff upper bound for recognition of the languages $L_{NE}(n)$ on exact 2QCFA: $TS={bf O}(n^{1.87} log n)$, whereas a lower bound on 2PFA is $TS={bf Omega}(n^2)$. It has been proved (Klauck, STOC00) that the exact one-way quantum finite automata have no advantage comparing to classical finite automata in recognizing languages. However, the result (3) shows that the exact 2QCFA do have an advantage in comparison with their classical counterparts, which has been the first example showing that the exact quantum computing have advantage in time-space tradeoff comparing to classical computing. Usually, two communicating parties, Alice and Bob, are supposed to have an access to arbitrary computational power in {em communication complexity} model that is used. Instead of that we will consider communication complexity in such a setting that two parties are using only finite automata and we prove in this setting that quantum automata are better than classical automata and also probabilistic automata are better than deterministic automata for some well known tasks.
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithms success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
