The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problem's hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $\Omega(N^{1/5}/\polylog N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainis's adversary theorem.
The problem of distinguishing between a random function and a random permutation on a domain of size N is important in theoretical cryptography, where the security of many primitives depend on the problem's hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make Ω(N1/5/\polylogN) queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainis's adversary theorem.
A collision for a function f is two distinct inputs x1=x2 such that f outputs the same value on both inputs: f(x1)=f(x2). The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be Θ(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the Ω(N1/3) lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to r-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of Θ(N1/3) holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal Ω(M1/3) lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.
It is known since the work of [Aaronson and Ambainis, 2014] that for any permutation symmetric function f, the quantum query complexity is at most polynomially smaller than the classical randomized query complexity, more precisely that R(f) = O~(Q^7(f)). In this paper, we improve this result and show that R(f) = O(Q^3(f)) for a more general class of symmetric functions. Our proof is constructive and relies largely on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [Zhandry, 2015].
We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised k-to-one Finding on an exactly k-to-one input string x∈Zqn, for every fixed k≥2 and every feasible alphabet size q≥n/k. The lower bounds are Ωk(n1/2−1/(2(2k−1))) for unrestricted adaptive algorithms and Ωk(n1−1/k) for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound Ωk(n/k) for k-to-one Testing when q≥n, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10].
Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted and unweighted methods of Ambainis and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, it can be shown that adversary methods can only prove lower bounds for Boolean functions f in O(min(nC0(f),nC1(f))), where C0,C1 is the certificate complexity and n is the size of the input.
Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f ( i ) = f ( j ), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an r -to-one function must evaluate the function Ω(( n / r ) 1/3 ) times, where n is the size of the domain and r | n . This matches an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of Ω( n 2/3 ) queries for the element distinctness problem, which is to determine whether n integers are all distinct. The best previous lower bound was Ω(√ n ) queries.
The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube {0,1}n, we show a lower bound of Ω(2n/4/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of Ω(2n/2/n2) on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension d≥3.