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:2312.16897 · Russian Microelectronics

Quantum Algorithm for Searching of Two Sets Intersection

Kamil Ravilevich Khadiev, Elizaveta Krendeleva

Published Dec 1, 2023• 2 citations
arXivHTMLPDF

Abstract

Abstract In the paper we investigate Two Sets Intersection problem. Assume that we have two sets that are subsets of n objects. Sets are presented by two predicates that show which of n objects belong to these sets. We present a quantum algorithm that finds an element from the two sets intersection. It is a modification of the well-known Grover’s search algorithm that uses two Oracles with access to the predicates. The algorithm is faster than the naive application of Grover’s search.

DOI
10.1134/s106373972360084x

Related papers

Optimal quantum searching to find a common element of two sets

Avatar Tulsi

Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.

arXiv:1210.4648•Oct 17, 2012•1 citation

Exact quantum algorithm for searching of multiple sets intersection

Sheng-Ao Mao, Lin Zhang, Bo Li

Grover's algorithm achieves a quadratic speedup for unstructured search when a global oracle for the target set is available. However, its success probability is generally below $100\%$. To overcome this issue, Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition, which can search for the target set with zero theoretical failure rate. Nevertheless, in many applications, the target set is determined by the intersection of multiple constrained sets. Most existing Grover-based methods are limited to the intersection of only two sets and are not always successful in searching for the target set. In this work, based on Long's method, we propose an algorithm for exactly searching the intersection of multiple sets. We derive and prove a phase-matching condition for searching the intersection exactly. Furthermore, we present a quantum circuit that implements exact intersection search. Finally, we support our theoretical results with numerical simulations.

quant-pharXiv:2609.36908•Sep 30, 2026•0 citations

Quantum set intersection and its application to associative memory

Tamer Salman, Yoram Baram A

We describe a quantum algorithm for computing the intersection of two sets and its application to associative memory. The algorithm is based on a modification of Grover's quantum search algorithm (Grover, 1996). We present algorithms for pattern retrieval, pattern completion, and pattern correction. We show that the quantum associative memory can store an exponential number of memories and retrieve them in sub-exponential time. We prove that this model has advantages over known classical associative memories as well as previously proposed quantum models.

Journal of Machine Learning Research•Jan 1, 2012•5 citations

Quantum algorithms for fixed points and invariant subgroups

Marianna C. Bonanome, Stephen Majewicz

In this paper, we apply quantum algorithms to solve problems concerning fixed points and invariant subgroups of automorphisms. These efficient algorithms invoke a quantum algorithm which computes the intersection of multiple unsorted multisets whose elements originate from the same set. This intersection algorithm is an application of the Grover search procedure.

journal of Groups complexity cryptology•Jan 1, 2011•0 citations

A Modification of Grover’s Quantum Search Algorithm

I. Ashraf, T. Mahmood, Vasudevan Lakshminarayanan

Abstract-We propose a quantum search method based on Grover’s algorithm. This algorithm is described and we show that to search for a single marked element from an unsorted search space of N elements, the number of queries are required using this algorithm when compared to for the Grover algorithm.

•Aug 31, 2016•1 citation

Grover’s quantum search algorithm and Diophantine approximation

Shahar Dolev, Itamar Pitowsky, Boaz Tamir

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size $N$ by using only $O(\sqrt{N})$ queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either $M$ or $K$, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let $m$ be the required number of iterations; we prove that under certain restrictions on the sizes of $M$ and $K$ the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.

arXiv:quant-ph/0507234•Physical Review A•Feb 3, 2006•3 citations
Abstract In the paper we investigate Two Sets Intersection problem. Assume that we have two sets that are subsets of n objects. Sets are presented by two predicates that show which of n objects belong to these sets. We present a quantum algorithm that finds an element from the two sets intersection. It is a modification of the well-known Grover’s search algorithm that uses two Oracles with access to the predicates. The algorithm is faster than the naive application of Grover’s search.
Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.
Grover's algorithm achieves a quadratic speedup for unstructured search when a global oracle for the target set is available. However, its success probability is generally below 100%100\%100%. To overcome this issue, Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition, which can search for the target set with zero theoretical failure rate. Nevertheless, in many applications, the target set is determined by the intersection of multiple constrained sets. Most existing Grover-based methods are limited to the intersection of only two sets and are not always successful in searching for the target set. In this work, based on Long's method, we propose an algorithm for exactly searching the intersection of multiple sets. We derive and prove a phase-matching condition for searching the intersection exactly. Furthermore, we present a quantum circuit that implements exact intersection search. Finally, we support our theoretical results with numerical simulations.
We describe a quantum algorithm for computing the intersection of two sets and its application to associative memory. The algorithm is based on a modification of Grover's quantum search algorithm (Grover, 1996). We present algorithms for pattern retrieval, pattern completion, and pattern correction. We show that the quantum associative memory can store an exponential number of memories and retrieve them in sub-exponential time. We prove that this model has advantages over known classical associative memories as well as previously proposed quantum models.
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size NNN by using only O(N)O(\sqrt{N})O(N​) queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either MMM or KKK, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let mmm be the required number of iterations; we prove that under certain restrictions on the sizes of MMM and KKK the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.