betaFeedback

WorksPhysics and Astronomy

Quantum Lower Bounds for Collision Problems

Abstract

We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised kk-to-one Finding on an exactly kk-to-one input string x∈Zqnx\in\mathbb Z_q^n, for every fixed k≥2k\ge2 and every feasible alphabet size q≥n/kq\ge n/k. The lower bounds are Ωk(n1/2−1/(2(2k−1)))Ω_k(n^{1/2-1/(2(2^k-1))}) for unrestricted adaptive algorithms and Ωk(n1−1/k)Ω_k(n^{1-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)Ω_k(\sqrt{n/k}) for kk-to-one Testing when q≥nq\ge 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.

Introduction

Collision problems are fundamental to quantum query complexity. Given oracle access to a string

x=(x1,…,xn)∈Zqnx=(x_1,\ldots,x_n)\in\mathbb{Z}_q^n

a kk-collision is a set of kk distinct indices i1,…,iki_1,\ldots,i_k such that xi1=⋯=xikx_{i_1}=\cdots=x_{i_k}. Throughout this paper, k≥2k\ge2 is a fixed constant, nn is the input length, and qq is the alphabet size. The string partitions [n][n] into blocks of equal-valued positions; collision problems ask us to find these hidden blocks or distinguish their possible structures.

One of the most basic versions of the collision problems is Promised kk-to-one Finding. Here n=kNn=kN, and the input x∈Zqnx\in\mathbb{Z}_q^n is promised to be exactly kk-to-one: every symbol that appears in xx appears exactly kk times. Equivalently, its equality partition consists of NN blocks of size kk. The task is to output all kk positions in any one block. A related decision problem, kk-to-one Testing, asks whether the input is injective or exactly kk-to-one, under the promise that one of these cases holds. Note that it suffices to find a pair of equal entries to rule out the injective case, whereas Promised kk-to-one Finding requires a full block of kk positions.

Collision finding (k=2k=2) and multicollision finding (k≥3k\ge3) capture a basic difficulty in query computation: learning one input value need not reveal where to find another occurrence. These problems model attacks on hash functions and related cryptographic constructions, where an adversary seeks several inputs with the same output [7, 16, 20, 27]. They have also motivated quantum algorithms and lower-bound methods, including the polynomial method [4, 19, 1], quantum walks [2, 22], learning graphs [5], adversary methods [8], and compressed-oracle and Fourier methods [27, 6]. The exact kk-to-one promise lets us study full multicollisions when many of them exist. One example is a truncated permutation: discarding dd output bits gives an exactly 2d2^d-to-one function, and the algorithm sees only the truncated output. Such truncation is used in constructions of pseudorandom functions [14]. There is also a graph interpretation: draw an edge from each position ii to its value xix_i. A kk-collision is then a set of kk edges with the same endpoint. This relates collision finding to testing for directed stars [3, 23].

Query count and adaptivity. Collision problems provide a natural setting for separating the benefits of quantum computation from those of adaptivity. Classically, non-adaptive sampling is already optimal even among adaptive randomized algorithms: for fixed kk, finding a complete block of a kk-to-one input requires Θk(n1−1/k)\Theta_k(n^{1-1/k}) queries, whereas distinguishing an injective input from a kk-to-one input requires Θ(n/k)\Theta(\sqrt{n/k}) queries. Appendix § 11 gives self-contained proofs.

For quantum algorithms, the relationship between query count and adaptivity is more subtle. We distinguish the two models illustrated in Figure 1. An adaptive algorithm may use information acquired through earlier oracle calls to prepare later queries; this dependence may remain entirely coherent and need not involve intermediate measurements. A non-adaptive, or one-round, algorithm makes all its queries in a single parallel layer. Its queries may be arbitrarily entangled, and it may perform arbitrary quantum postprocessing and a joint measurement, but it cannot use the returned information to prepare another query layer. Thus, non-adaptivity restricts sequential oracle access, not the coherence or computational power available within a query layer.

The adaptive and non-adaptive models

Figure 1. The adaptive and non-adaptive models. Each UjU_j may act jointly on all accessible registers. An oracle acts on the index and answer registers and leaves the workspace unchanged. The non-adaptive layer contains tt simultaneous calls, followed by an unrestricted joint measurement. Dashed vertical cuts mark the states at the indicated stages, as in [6 Figures 3.1–3.2].

Known quantum collision-finding algorithms exploit precisely this sequential dependence. Brassard, Høyer, and Tapp [7] gave an adaptive quantum algorithm for k=2k=2. For general kk, Hosoya-mada, Sasaki, and Xagawa [13] developed a recursive algorithm that constructs smaller collisions and extends them using quantum search, with expected query complexity Ok(n1/2−1/(2⋅3k−1))O_k(n^{1/2-1/(2\cdot3^{k-1})}). Liu and Zhandry [20] improved this approach by constructing lists of partial collisions and reusing each list as the target set for the next stage. Their algorithm uses

Ok(nαk)queries, whereαk=12−12(2k−1).O_k(n^{\alpha_k}) \quad\text{queries, where} \quad\alpha_k = \frac{1}{2} - \frac{1}{2(2^k-1)}.

These algorithms beat the classical birthday scale, but their successive stages leave open how much of the improvement comes from quantum coherence alone and how much requires adaptivity.

This raises two complementary lower-bound questions. First, is the Liu–Zhandry query bound optimal under the exact kk-to-one promise, even with unrestricted quantum adaptivity? Their matching lower bound is proved for uniformly random functions (see § 1.7) and does not establish this optimality for general kk. Resolving the adaptive complexity determines the largest possible quantum query advantage for this task, rather than merely the performance of the known algorithms.

Second, can a single layer of entangled queries achieve any asymptotic improvement over classical sampling? Classical sampling gives a one-round upper bound of Ok(n1−1/k)O_k(n^{1-1/k}), but a quantum algorithm need not query a fixed classical sample or explicitly observe a collision before producing its output. A matching non-adaptive lower bound must therefore rule out all coherent parallel strategies and joint measurements. Such a bound would show that the sequential dependence in the known algorithms is essential, rather than an artifact of their design, and quantify the query cost of eliminating that dependence.

We determine both the adaptive and one-round non-adaptive quantum query complexities under the exact kk-to-one promise, for every feasible alphabet size. Together, these results identify the optimal quantum speedup and show that achieving it requires adaptivity. Our comparison with kk-TO-ONE TESTING further separates the cost of recovering a complete collision from that of merely detecting the promised equality structure.

Our Contribution

We prove matching lower bounds for Promised kk-to-one Finding in the adaptive and non-adaptive models (Theorems 1.1 and 1.2, respectively). Both proofs represent information about a random permutation by a compressed database of input–output pairs. For adaptive algorithms, we bound how quickly queries can build larger partial collisions. For one-round non-adaptive algorithms, we directly bound the probability that the encoded final state contains a full collision. This direct analysis avoids accumulating simulation error across all parallel queries.

Theorem 1.1 (Adaptive Promised kk-to-one Finding). Let k>2k > 2 be fixed, n=kNn = kN, and q>Nq > N. Every quantum algorithm for Promised kk-to-one Finding that succeeds with constant probability on every promised input in Zqn\mathbb{Z}_q^n requires Ωk(n(2k−1−1)/(2k−1))\Omega_k\left(n^{(2^{k-1}-1)/(2^k-1)}\right) queries.

This is the exact-promise counterpart of the random-function multicollision lower bound of Liu and Zhandry [20]. Their lower bound does not extend to the exact kk-to-one promise. Their proof uses Zhandry’s compressed-oracle method to bound the accumulation of partial collisions and relies on the independence of random-function values. Under the exact kk-to-one promise, every used value must occur exactly kk times, so the entries are dependent. Their recording representation and single-query amplitude bounds therefore do not directly apply. Moreover, exactly kk-to-one inputs form an exponentially small fraction of all functions from [n][n] to [N][N], so conditioning on this event does not directly transfer their average-case lower bound to our setting. We handle these dependencies by generating balanced inputs from a random permutation and tracking partial collisions with a compressed permutation oracle.

With all queries restricted to one parallel layer, this gradual construction of larger collisions is unavailable. The next theorem gives a one-round non-adaptive lower bound that matches the cost of classical sampling.

Theorem 1.2 (Non-adaptive Promised kk-to-one Finding). Let k≥2k \ge2 be fixed, n=kNn = kN, and q≥Nq \ge N. Every one-round quantum algorithm for Promised kk-to-one Finding that succeeds with constant probability on every promised input in Zqn\mathbb{Z}_q^n requires Ωk(n1−1/k)\Omega_k(n^{1-1/k}) parallel queries.

Theorem 1.2 allows arbitrary entanglement across the entire parallel layer, even at the smallest feasible alphabet size. The proof controls the success of the final measurement, including outputs containing positions that were not explicitly queried in a classical sense.

Our third main result shows that one-round quantum algorithms for kk-to-one Testing require as many queries as classical birthday sampling.

Theorem 1.3 (Non-adaptive kk-to-one Testing). Let k≥2k \ge2 be fixed, k∣nk \mid n, q≥nq \ge n, and 0<ε<1/20 < \varepsilon< 1/2. Every one-round quantum algorithm for kk-to-one Testing that succeeds with probability at least 1/2+ε1/2+\varepsilon on every promised input in Zqn\mathbb{Z}_q^n requires Ω(εn/k)\Omega(\varepsilon\sqrt{n/k}) parallel queries.

For k=2k = 2, Theorem 1.3 answers the non-adaptive collision question posed by Koiran, Landes, Portier, and Yao [18]. Their weighted adversary bounds treat a parallel layer as a single query to a tuple of input positions. Our proof compares the algorithm’s reduced states under independent and distinct block labels, allowing qq to be as small as nn.

Tightness. All three lower bounds are tight for constant success probability (constant bias for kk-to-one Testing), as summarized in Table 1. For Theorem 1.1, the Liu–Zhandry algorithm described above uses Ok(nαk)O_k(n^{\alpha_k}) adaptive queries [20]. Its cost depends on the NN symbols actually used, rather than the ambient alphabet size, so the bound holds for every q≥Nq \ge N.

ProblemAlphabetNon-adaptive quantumNon-adaptive & adaptive classicalAdaptive quantum
Promised kk-to-one Findingq≥n/kq \ge n/kΘk(n1−1/k)\Theta_k(n^{1-1/k})<br>Theorem 1.2Θk(n1−1/k)\Theta_k(n^{1-1/k})Θk(nαk)\Theta_k(n^{\alpha_k})2<br>Theorem 1.1
kk-to-one Testingq≥nq \ge nΘ(n/k)\Theta(\sqrt{n/k})<br>Theorem 1.3Θ(n/k)\Theta(\sqrt{n/k})Θk((n/k)1/3)\Theta_k((n/k)^{1/3})3

Table 1. Constant-error query complexity for fixed kk. Here αk=12−122k−1\alpha_k = \frac{1}{2} - \frac{1}{2^{2k-1}}. Bold entries are the tight complexities established by this paper’s lower bounds together with the matching algorithms described above. The classical bounds are the same with and without adaptivity.

The matching one-round upper bounds are classical: sampling Ok(n1−1/k)O_k(n^{1-1/k}) positions suffices to find a full kk-collision, while sampling O(n/k)O(\sqrt{n/k}) positions and checking for an equal pair suffices to distinguish the two promise cases with constant bias. Both algorithms query uniformly chosen positions; see Appendix § 11.

The alphabet conditions are minimal: Promised kk-to-one Finding requires q≥n/kq \ge n/k, and kk-to-one Testing requires q≥nq \ge n for the injective case to exist. Theorem 1.3 allows variable bias, although we do not optimize the dependence on ε\varepsilon.

Technical Overview

We first explain the adaptive lower bound: we construct the hard distribution, bound the growth of recorded collisions using compressed permutation oracle techniques [9], and relate these records to successful outputs. We then use the additional structure of a single query round to prove the non-adaptive finding bound, and conclude with the decision bound for kk-to-one Testing. Throughout the overview, k≥2k \ge2 is fixed and n=kNn = kN.

From balanced inputs to Permutation Bucket Finding

To prove the adaptive lower bound for Promised kk-to-one Finding, we reduce the analysis to Permutation Bucket Finding. Intuitively, a uniformly random permutation π\pi generates a balanced kk-to-one input as follows. Group the permutation’s output slots into public buckets B1,…,BNB_1,\ldots,B_N of size kk, and assign a distinct input symbol to each bucket. The input value xiπx_i^\pi is the symbol of the bucket containing π(i)\pi(i). Every symbol then appears exactly kk times, and a full

kk-collision consists of the kk input positions whose images under π\pi fill one bucket. Finding these positions is precisely the task of Permutation Bucket Finding (Definition 5.23).

To simulate one input query, use a forward permutation query to compute π(i)\pi(i), apply the phase determined by its bucket label, and use a second query to uncompute π(i)\pi(i). Reversing the forward query has the same query cost and does not require evaluating π−1\pi^{-1}. Thus a T0T_0-query algorithm for Promised kk-to-one Finding gives a 2T02T_0-query algorithm for Permutation Bucket Finding with the same average success probability (Lemma 6.2). Access to π−1\pi^{-1} is excluded: kk inverse queries would find all positions mapping to a public bucket. For the one-round lower bound, we analyze the original input queries directly to preserve the number of query layers.

Recording information about a random permutation

The reduction lets us study queries to a uniform permutation using recording techniques. Zhandry’s compressed oracle [27] records information about a random function in a small database. Carolan [9] constructs a unitary recorder for permutations and bounds its difference from the genuine oracle. We use his forward-query construction. A permutation database assigns distinct output slots to its recorded positions, so the available values at one position depend on the assignments elsewhere.

We apply a projection after each forward recording query to obtain total error O(T2/n)O(T^2/n) after TT queries. This projection acts within each subspace with a fixed set of recorded output slots. It can reduce the probability mass in a bucket-occupancy class, but cannot move mass between classes. This domain-harmonic projection is defined below. Let ϱT\varrho_T and ϱ~T\widetilde{\varrho}_T be the reduced states on the algorithm register A\mathcal{A} for the genuine and projected recording processes. Then

∥ϱT−ϱ~T∥1=O(T(T+1)n)(T+3≤n/8).\lVert\varrho_T-\widetilde{\varrho}_T\rVert_1=O\left(\frac{T(T+1)}{n}\right) \qquad(T+3\le n/8).

The projected process may have norm less than one, and Tr⁡ϱ~T\operatorname{Tr}\widetilde{\varrho}_T may therefore be less than one. We never renormalize it. Lemma 5.20 proves the stronger joint-state estimate in Eq. (61).

The database encoding and query comparison

To analyze the information learned from the permutation oracle, we introduce an auxiliary database register, initialized to the empty database. Let P=C[Sn]\mathcal{P}=\mathbb{C}[S_n] be the genuine permutation register, and let In\mathcal{I}_n be the set of partial injections d:[n]⇀[n]d : [n] \rightharpoonup[n]. The auxiliary register is

D=C[In]=⨁s=0nDs,Ds=Span⁡{∣d⟩:∣d∣=s},D≤t=⨁s≤tDs.\mathcal{D} = \mathbb{C}[\mathcal{I}_n] = \bigoplus_{s=0}^{n} \mathcal{D}_s,\qquad\mathcal{D}_s = \operatorname{Span}\{|d\rangle: |d| = s\},\qquad\mathcal{D}_{\le t} = \bigoplus_{s\le t} \mathcal{D}_s.

Here ∣d∣|d| is the number of assigned positions. For a residual database rr, an unassigned position i∉Dom⁡ri \notin\operatorname{Dom} r, and an unused output slot y∉Im⁡ry \notin\operatorname{Im} r, define the two uniform extensions

References

  1. [1][Amb05] Andris Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1(1):37–46, 2005.
  2. [2]Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007.
  3. [3]Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó. Quantum property testing in sparse directed graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 of Leibniz International Proceedings in Informatics, pages 32:1–32:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.arxiv.org/abs/2410.05001
  4. [4]Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM (JACM), 51(4):595–605, 2004.DOI
  5. [5]Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 207–216. IEEE, 2012.arxiv.org/abs/1205.1534
  6. [6]Aleksandrs Belovs. Tight quantum lower bound for k-distinctness. In 2026 IEEE 67th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2026. To appear. Preprint: arXiv:2604.05133v2 (October 19, 2026).arxiv.org/abs/2604.05133
  7. [7]Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. ACM Sigact News, 28(2):14–19, 1997.
  8. [8]Aleksandrs Belovs and Ansis Rosmanis. Adversary lower bounds for the collision and the set equality problems. Quantum Information & Computation, 18(3-4):198–222, 2018.arxiv.org/abs/1310.5185
  9. [9]Joseph Carolan. Compressed permutation oracles. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 150–161. ACM, 2026.arxiv.org/abs/2509.18586
  10. [10]Joseph Carolan and Christian Majenz. Compressed permutation oracles revisited. arXiv:2609.28469, September 2026. Version 1, 23 September 2026.arxiv.org/abs/2609.28469
  11. [11]Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob, and Elena Yudovina. Introduction to Representation Theory, volume 59 of Student Mathematical Library. American Mathematical Society, 2011.
  12. [12]Uma Girish, Makrand Sinha, Avishay Tal, and Kewen Wu. The power of adaptivity in quantum query algorithms. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1488–1497, 2024.arxiv.org/abs/2311.16057
  13. [13]Akinori Hosoyamada, Yu Sasaki, and Keita Xagawa. Quantum multicollision-finding algorithm. In International Conference on the Theory and Application of Cryptology and Information Security, pages 179–210. Springer, 2017.DOI
  14. [14]Chris Hall, David Wagner, John Kelsey, and Bruce Schneier. Building PRFs from PRPs. In Advances in Cryptology – CRYPTO ’98, volume 1462 of Lecture Notes in Computer Science, pages 370–389. Springer, 1998.
  15. [15]Stacey Jeffery, Frederic Magniez, and Ronald De Wolf. Optimal parallel quantum query algorithms. Algorithmica, 79(2):509–529, 2017.
  16. [16]Antoine Joux. Multicollisions in iterated hash functions. Application to cascaded constructions. In CRYPTO 2004, pages 306–316. Springer, 2004.DOI
  17. [17]Sunyeop Kim. Improved soundness for compressed permutation oracles and tight quantum preimage and collision bounds for the sponge. Cryptology ePrint Archive, Paper 2026/2135, 2026.
  18. [18]Pascal Koiran, Jürgen Landes, Natacha Portier, and Penghui Yao. Adversary lower bounds for nonadaptive quantum algorithms. Journal of Computer and System Sciences, 76(5):347–355, 2010.
  19. [19]Samuel Kutin. Quantum lower bound for the collision problem with small range. Theory of Computing, 1(1):29–36, 2005.
  20. [20]Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part III, volume 11478 of Lecture Notes in Computer Science, pages 189–218. Springer, 2019.
  21. [21]Ashley Montanaro. Nonadaptive quantum query complexity. Information Processing Letters, 110(24):1110–1113, 2010.
  22. [22]Frédéric Magniez, Miklos Santha, and Mario Szegedy. Quantum algorithms for the triangle problem. SIAM Journal on Computing, 37(2):413–424, 2007.
  23. [23]Pan Peng and Jingyu Wu. Quantum property testing for bounded-degree directed graphs. In Proceedings of the Thirty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2027). Society for Industrial and Applied Mathematics, 2027. To appear.arxiv.org/abs/2604.07954
  24. [24]Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments. arXiv preprint arXiv:2103.08975, 2021. Version 1, March 16, 2021.arxiv.org/abs/2103.08975
  25. [25]Bruce E. Sagan. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, volume 203 of Graduate Texts in Mathematics. Springer, 2 edition, 2001.
  26. [26]Wim Van Dam. Quantum oracle interrogation: Getting all information for almost half the price. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 362–367. IEEE, 1998.
  27. [27]Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Annual International Cryptology Conference, 2019.DOI

Paper details

vlnc:W_hcav665r
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents