Exact quantum algorithm for searching of multiple sets intersection
Abstract
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.
Related
- Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
- Fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm
- COFI-DQI: Curve-based Optimal Function Intersection via Decoded Quantum Interferometry
- Hybrid Kernel/Bath Quantum Dynamics Reveal Conical Intersection Signatures in X-ray Raman Spectroscopy
- An exact algorithm for U(N) matrix models in the gauge-invariant singlet sector
BibTeX
@misc{mao2026exact,
title = {{Exact quantum algorithm for searching of multiple sets intersection}},
author = {Sheng-Ao Mao and Lin Zhang and Bo Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36908},
eprint = {2609.36908},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36908},
}
RIS
TY - UNPB
TI - Exact quantum algorithm for searching of multiple sets intersection
AU - Sheng-Ao Mao
AU - Lin Zhang
AU - Bo Li
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36908
UR - https://arxiv.org/abs/2609.36908
AB - 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.
ER -