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

IEEE Access

An Efficient Quantum Multi-Collision Search Algorithm

Jian Xiao Zou, Yongyang Liu, Le Dong

Published Jan 1, 2020• 3 citations
Publisher

Abstract

In this article, we propose an efficient quantum k-collision search algorithm with low quantum memory O(n). The previous quantum k-collision algorithms can not be converted into a low quantum memory k-collision algorithm directly, because the time complexity of the converted algorithm is larger than the basic k-collision algorithm. To solve this problem, we shall not only divide our low memory quantum k-collision algorithm into several subroutines, but also need to achieve some balances between these subrou tines. The time complexity of our k-collision search algorithm is O(2(2k-2)n/2k+1-3 ), and the classical memory and quantum memory complexities are O(2(2k-2)n/2k+1-3 ) and O(n) respectively. In addition, we propose an efficient k-claw search algorithm, which can output a k-claw with O(n) qubits. Given 2squantum processors, we can construct our quantum k-collision and k-claw parallel algorithm with the time of O(2(2k-2)n-(2k+1-2k-1-3)s/2k+1-3 )while the classical memory and quantum memory complexities are O(2(2k-1-1)n+s-2k-2/2k+1-3 ) and O(n), respectively.

DOI
10.1109/access.2020.3028736

Related papers

Efficient distributed quantum computing

Robert Beals, STEPHEN D. BRIERLEY, Oliver Gray +5 more

Abstract We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memory-intensive quantum algorithms. We present a parallel quantum search algorithm and improve the time–space trade-off for the element distinctness and collision finding problems.

arXiv:1207.2307•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Feb 20, 2013•213 citations

Quantum cryptanalysis of hash and claw-free functions

Gilles Brassard A, Peter Høyer, Alain Tapp

In this note, we give a quantum algorithm that finds collisions in arbitrary τ-to-one functions after only O ( 3 √ N /τ) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.

ACM SIGACT News•Jun 1, 1997•132 citations

How significant are the known collision and element distinctness quantum algorithms?

Lov K. Grover, Terry Rudolph

Quantum search is a technique for searching $N$ possibilities for a desired target in $O(\sqrt{N})$ steps. It has been applied in the design of quantum algorithms for several structured problems. Many of these algorithms require significant amount of quantum hardware. In this paper we propose the criterion that an algorithm which requires $O(S)$ hardware should be considered significant if it produces a speedup of better than $O\left(\sqrt{S}\right)$ over a simple quantum search algorithm. This is because a speedup of $O\left(\sqrt{S}\right)$ can be trivially obtained by dividing the search space into $S$ separate parts and handing the problem to $S$ independent processors that do a quantum search (in this paper we drop all logarithmic factors when discussing time/space complexity). Known algorithms for collision and element distinctness exactly saturate the criterion.

arXiv:quant-ph/0309123•Quantum Information and Computation•May 1, 2004•23 citations

Quantum Time–Space Tradeoff for Finding Multiple Collision Pairs

Yassine Hamoudi, Frédéric Magniez

We study the problem of finding K collision pairs in a random function f : [N] → [N] by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited. Namely, we demonstrate that any algorithm using S qubits of memory must perform a number T of queries that satisfies the tradeoff T 3 S ≥ Ω (K 3 N) . Classically, the same question has only been settled recently by Dinur [ 22 ], who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener [ 36 ] achieves the optimal time–space tradeoff of T 2 S = Θ (K 2 N) . Our result limits the extent to which quantum computing may decrease this tradeoff. Our method is based on a novel application of Zhandry’s recording query technique [ 42 ] for proving lower bounds in the exponentially small success probability regime. As a second application, we give a simpler proof of the time–space tradeoff T 2 S ≥ Ω (N 3 ) for sorting N numbers on a quantum computer, which was first obtained by Klauck, Špalek, and de Wolf [ 30 ].

arXiv:2002.08944•ACM Transactions on Computation Theory•Apr 13, 2023•13 citations

A Tight Quantum Algorithm for Multiple Collision Search

Xavier Bonnetain, Johanna Loyer, André Schrottenloher +1 more

Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms. At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound $Ω(2^{m/3 + 2k/3})$ for finding $2^k$ collisions in a random function with m-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of $m$ and $k$, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision. In this paper, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the ``walks'' themselves only perform a single diffusion layer.

arXiv:2509.13909•Sep 17, 2025•0 citations

Efficient Dictionary Search Quantum Algorithms

Farid Mansurovich Ablayev, Nailya Salikhova, Marat Ablayev

Abstract In this paper, we consider the problem of searching for an element in a dictionary. Various approaches to solving this problem have been proposed in recent decades: classical and quantum algorithms. We present two algorithms: a hybrid classical-quantum algorithm [1], that implements Grover’s search, and a “pure” quantum algorithm based on the quantum fingerprinting technique. Both algorithms work (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. Our algorithms are much more memory efficient in terms of the number of qubits used compared to previously known quantum algorithms.

Physics of Particles and Nuclei•Aug 1, 2025•2 citations
In this article, we propose an efficient quantum k-collision search algorithm with low quantum memory O(n). The previous quantum k-collision algorithms can not be converted into a low quantum memory k-collision algorithm directly, because the time complexity of the converted algorithm is larger than the basic k-collision algorithm. To solve this problem, we shall not only divide our low memory quantum k-collision algorithm into several subroutines, but also need to achieve some balances between these subrou tines. The time complexity of our k-collision search algorithm is O(2(2k-2)n/2k+1-3 ), and the classical memory and quantum memory complexities are O(2(2k-2)n/2k+1-3 ) and O(n) respectively. In addition, we propose an efficient k-claw search algorithm, which can output a k-claw with O(n) qubits. Given 2squantum processors, we can construct our quantum k-collision and k-claw parallel algorithm with the time of O(2(2k-2)n-(2k+1-2k-1-3)s/2k+1-3 )while the classical memory and quantum memory complexities are O(2(2k-1-1)n+s-2k-2/2k+1-3 ) and O(n), respectively.
Abstract We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memory-intensive quantum algorithms. We present a parallel quantum search algorithm and improve the time–space trade-off for the element distinctness and collision finding problems.
In this note, we give a quantum algorithm that finds collisions in arbitrary τ-to-one functions after only O ( 3 √ N /τ) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.
Quantum search is a technique for searching NNN possibilities for a desired target in O(N)O(\sqrt{N})O(N​) steps. It has been applied in the design of quantum algorithms for several structured problems. Many of these algorithms require significant amount of quantum hardware. In this paper we propose the criterion that an algorithm which requires O(S)O(S)O(S) hardware should be considered significant if it produces a speedup of better than O(S)O\left(\sqrt{S}\right)O(S​) over a simple quantum search algorithm. This is because a speedup of O(S)O\left(\sqrt{S}\right)O(S​) can be trivially obtained by dividing the search space into SSS separate parts and handing the problem to SSS independent processors that do a quantum search (in this paper we drop all logarithmic factors when discussing time/space complexity). Known algorithms for collision and element distinctness exactly saturate the criterion.
We study the problem of finding K collision pairs in a random function f : [N] → [N] by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited. Namely, we demonstrate that any algorithm using S qubits of memory must perform a number T of queries that satisfies the tradeoff T 3 S ≥ Ω (K 3 N) . Classically, the same question has only been settled recently by Dinur [ 22 ], who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener [ 36 ] achieves the optimal time–space tradeoff of T 2 S = Θ (K 2 N) . Our result limits the extent to which quantum computing may decrease this tradeoff. Our method is based on a novel application of Zhandry’s recording query technique [ 42 ] for proving lower bounds in the exponentially small success probability regime. As a second application, we give a simpler proof of the time–space tradeoff T 2 S ≥ Ω (N 3 ) for sorting N numbers on a quantum computer, which was first obtained by Klauck, Špalek, and de Wolf [ 30 ].
Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms. At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound Ω(2m/3+2k/3)Ω(2^{m/3 + 2k/3})Ω(2m/3+2k/3) for finding 2k2^k2k collisions in a random function with m-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of mmm and kkk, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision. In this paper, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the ``walks'' themselves only perform a single diffusion layer.
Abstract In this paper, we consider the problem of searching for an element in a dictionary. Various approaches to solving this problem have been proposed in recent decades: classical and quantum algorithms. We present two algorithms: a hybrid classical-quantum algorithm [1], that implements Grover’s search, and a “pure” quantum algorithm based on the quantum fingerprinting technique. Both algorithms work (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. Our algorithms are much more memory efficient in terms of the number of qubits used compared to previously known quantum algorithms.