A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, $\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) $ quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

Jan 1, 20180 citations

Lecture notes in computer science

On Finding Quantum Multi-collisions

Qipeng Liu, Mark Zhandry

Published Jan 1, 2019• 42 citations

Publisher

DOI: 10.1007/978-3-030-17659-4_7

Related papers

Quantum Multi-Collision Distinguishers.

Zhenzhen Bao, Jian Guo, Shun Li +1 more

Jan 1, 20213 citations

INVESTIGATION OF QUANTUM THEORY OF COLLISIONS

V. D. Kamenetskii

Jan 1, 19640 citations

Collision-free Path Planning in Multi-vehicle Deployments – A Quantum Approach

Poojith U Rao, Balwinder Sodhi

A crucial factor that can severely limit the success and performance of Multi-Robot Systems (MRS) is the possibility of collisions among the robots in a deployment. The MRS deployment in real-world applications has increased almost exponentially in recent years. Thus, finding efficient and fast methods to identify collision-free paths for MRS environments becomes very important.A common objective in such applications is to generate a collision-free path for all the vehicles between two points and minimize the total distance covered while reaching the destination. Since these problems are known to be NP-hard (i.e., no classical algorithm can solve the problem in polynomial time), a heuristics-based approach is usually applied to obtain an acceptable solution.We derive a novel Quantum Alternating Operator Ansatz (QAOA) construction for collision-free path planning in MRS deployment. A heuristic approach such as the QAOA is well suited for combinatorial optimization problems that need to satisfy multiple hard constraints. We also derive the approximate resource estimates in terms of universal quantum gates for our QAOA constructions.A crucial factor that can severely limit the success and performance of Multi-Robot Systems (MRS) is the possibility of collisions among the robots in a deployment. The MRS deployment in real-world applications has increased almost exponentially in recent years. Thus, finding efficient and fast methods to identify collision-free paths for MRS environments becomes very important.A common objective in such applications is to generate a collision-free path for all the vehicles between two points and minimize the total distance covered while reaching the destination. Since these problems are known to be NP-hard (i.e., no classical algorithm can solve the problem in polynomial time), a heuristics-based approach is usually applied to obtain an acceptable solution.We derive a novel Quantum Alternating Operator Ansatz (QAOA) construction for collision-free path planning in MRS deployment. A heuristic approach such as the QAOA is well suited for combinatorial optimization problems that need to satisfy multiple hard constraints. We also derive the approximate resource estimates in terms of universal quantum gates for our QAOA constructions.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 1, 20221 citation

Particle collisions on a quantum computer

Torsten V. Zache

Nature PhysicsOct 23, 20260 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.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.

CybersecurityMay 8, 20260 citations

On Finding Quantum Multi-collisions.

Qipeng Liu, Mark Zhandry

A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, $\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right)$ quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, $\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) $ quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

Jan 1, 20180 citations

\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.

A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k,

\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right)

quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.