Tight Quantum Time-Space Tradeoffs for Function Inversion

• URL: http://arxiv.org/abs/2006.05650v2
• Date: Sun, 22 Nov 2020 19:44:59 GMT
• Title: Tight Quantum Time-Space Tradeoffs for Function Inversion
• Authors: Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian
• Abstract summary: We show that even with quantum advice, $ST + T2 = tildeOmega(N)$ is required for an algorithm to invert random functions. We also prove quantum time-space lower bounds for Yao's box problem and salted cryptography.
• Score: 7.895232155155041
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 = \tilde\Omega(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\Omega(N)$. In this work, we prove that even with quantum advice, $ST + T^2 = \tilde\Omega(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.

Related papers

• Achieving quantum advantage in a search for a minimal Goldbach partition with driven atoms in tailored potentials [15.236546465767026]
  Goldbach conjecture states that any even natural number $N$ greater than $2$ can be written as the sum of two prime numbers $p$ and $p'$. We present a quantum analogue protocol for detecting -- given a even number $N$ -- the existence of a so-called minimal Goldbach partition $N=p+p'$.
  arXiv  Detail & Related papers  (2024-03-31T01:29:16Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
  Estimating the entropy of a quantum state is a basic problem in quantum information. We introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(rho)$ and R'enyi entropy $S_alpha(rho)$ of an $N$-dimensional quantum state $rho.
  arXiv  Detail & Related papers  (2024-01-18T12:50:20Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture [0.8924669503280332]
  We show that an $n1.5-epsilon$ time quantum algorithm for either of these two graph problems would imply faster quantum algorithms for k-SAT, 3SUM, and APSP. We also present quantum algorithms that require careful use of data structures and Ambainis' variable time search.
  arXiv  Detail & Related papers  (2022-07-22T13:16:50Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
  Controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0nrangle to |irangle |psi_irangle $ for all $iin 0,1k$ for the given $n$-qubit states. We construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac2n+kn+k+mright)$ and size $Oleft(2n+kright)$
  arXiv  Detail & Related papers  (2022-02-23T04:19:57Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
  arXiv  Detail & Related papers  (2020-07-23T10:50:42Z)
• Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
  We study the problem of finding $K$ collision pairs in a random function $f : [N] rightarrow [N]$ by using a quantum computer. We prove that the number of queries to the function must increase significantly when the size of the available memory is limited.
  arXiv  Detail & Related papers  (2020-02-20T18:48:51Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.