Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1312.1027 · Quantum Information and Computation

A note on the quantum collision and set equality problems

Mark Zhandry

Published May 1, 2015• 99 citations
arXivHTMLPDF

Abstract

A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/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 $\Theta(N^{1/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 $\Omega(M^{1/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.

DOI
10.26421/qic15.7-8-2

Related papers

A quantum lower bound for distinguishing random functions from random permutations

Henry Yuen

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.

arXiv:1310.2885•Quantum Information and Computation•Oct 1, 2014•17 citations

On finding quantum multi-collisions in non-uniform random functions

Tianci Peng, Rui Xue

Abstract Collision resistance is one of the most fundamental properties in cryptography. With the development of quantum computing, significant attention has been directed toward understanding the quantum query complexity of collision-finding problems in hash functions. The quantum query complexity of collision-finding in general non-uniform random functions remained an open problem until the recent work of Peng et al. (ASIACRYPT 2025), who nearly resolved it by introducing a novel parameter $$\gamma$$ γ . Based on this parameter, they established an upper bound of $$O(\gamma ^{1/6})$$ O ( γ 1 / 6 ) and a matching lower bound of $$\tilde{\Omega }(\gamma ^{1/6})$$ Ω ~ ( γ 1 / 6 ) . However, the quantum query complexity of finding multi-collisions in non-uniform random functions has remained open. A s -collision to a function f is a set of distinct input $$x_1,\dots , x_s$$ x 1 , ⋯ , x s such that $$f(x_1)=f(x_2)\dots =f(x_s)$$ f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter $$\gamma _s$$ γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of $$O(\gamma _s)$$ O ( γ s ) and a lower bound of $$\tilde{\Omega }(\gamma _s)$$ Ω ~ ( γ s ) —thereby nearly resolving this open problem. Moreover, although the existing results for 2-collisions do not generalize straightforwardly to the case of s -collision ( $$s>2$$ s > 2 ), we demonstrate that the result of Peng et al. can be viewed as a special case of our more general framework. This clearly establishes our work as a direct generalization of their contribution.

Cybersecurity•May 8, 2026•0 citations

A note on the quantum collision and set equality problems

ZhandryMark

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 [9, 2...

Quantum Information and Computation•May 1, 2015•4 citations

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry

Frédéric Magniez, Sebastian Zur

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$$ For the setting where $M=N$, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.

quant-pharXiv:2609.10808•Sep 11, 2026•0 citations

Quantum lower bounds for the collision and the element distinctness problems

Scott Aaronson, Yaoyun Shi

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.

Journal of the ACM•Jul 1, 2004•329 citations

Quantum lower bounds for the collision and the element distinctness problems

Yaoyun Shi

Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).

arXiv:quant-ph/0112086•Annual Symposium on Foundations of Computer Science•Jun 26, 2003•100 citations
A collision for a function fff is two distinct inputs x1≠x2x_1\neq x_2x1​=x2​ such that fff outputs the same value on both inputs: f(x1)=f(x2)f(x_1)=f(x_2)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)\Theta(N^{1/3})Θ(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the Ω(N1/3)\Omega(N^{1/3})Ω(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 rrr-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)\Theta(N^{1/3})Θ(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)\Omega(M^{1/3})Ω(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.
The problem of distinguishing between a random function and a random permutation on a domain of size NNN 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.
Abstract Collision resistance is one of the most fundamental properties in cryptography. With the development of quantum computing, significant attention has been directed toward understanding the quantum query complexity of collision-finding problems in hash functions. The quantum query complexity of collision-finding in general non-uniform random functions remained an open problem until the recent work of Peng et al. (ASIACRYPT 2025), who nearly resolved it by introducing a novel parameter γ\gammaγ γ . Based on this parameter, they established an upper bound of O(γ1/6)O(\gamma ^{1/6})O(γ1/6) O ( γ 1 / 6 ) and a matching lower bound of Ω~(γ1/6)\tilde{\Omega }(\gamma ^{1/6})Ω~(γ1/6) Ω ~ ( γ 1 / 6 ) . However, the quantum query complexity of finding multi-collisions in non-uniform random functions has remained open. A s -collision to a function f is a set of distinct input x1,…,xsx_1,\dots , x_sx1​,…,xs​ x 1 , ⋯ , x s such that f(x1)=f(x2)⋯=f(xs)f(x_1)=f(x_2)\dots =f(x_s)f(x1​)=f(x2​)⋯=f(xs​) f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter γs\gamma _sγs​ γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of O(γs)O(\gamma _s)O(γs​) O ( γ s ) and a lower bound of Ω~(γs)\tilde{\Omega }(\gamma _s)Ω~(γs​) Ω ~ ( γ s ) —thereby nearly resolving this open problem. Moreover, although the existing results for 2-collisions do not generalize straightforwardly to the case of s -collision ( s>2s>2s>2 s > 2 ), we demonstrate that the result of Peng et al. can be viewed as a special case of our more general framework. This clearly establishes our work as a direct generalization of their contribution.
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function f:[N]→[N]f:[N]\to [N]f:[N]→[N], the BHT algorithm finds a collision using O(N1/3)O(N^{1/3})O(N1/3) queries and a quantumly accessible classical table containing O(N1/3)O(N^{1/3})O(N1/3) input-output pairs, whereas a logarithmic-space Grover search uses O(N)O(\sqrt N)O(N​) queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function fff's output labels as interchangeable. We prove that such algorithm that makes TTT queries, uses SSS qubits, and finds a collision in a uniformly random function f:[M]→[N]f:[M]\to [N]f:[M]→[N] with constant probability satisfies T=Ω(N1/3)andT2S=Ω(Nlog⁡N).T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).T=Ω(N1/3)andT2S=Ω(NlogN). For the setting where M=NM=NM=N, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on f:[n]→[n2]f: [n] \to [n^2]f:[n]→[n2] must satisfy T=Ω(n2/3)andT2S=Ω(n2log⁡n),T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),T=Ω(n2/3)andT2S=Ω(n2logn), matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using SSS qubits can effectively retain information about only O(S/log⁡N)O(S/\log N)O(S/logN) collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.
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.
Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).