Quantum Algorithm for Searching of Two Sets Intersection

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.

References in corpus (6)

• Quantum Amplitude Amplification and Estimation
• Grover Algorithm with zero theoretical failure rate
• Quantum Search on Bounded-Error Inputs
• Quantum query complexity of some graph problems
• Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
• Lecture Notes on Quantum Algorithms