arXiv:2609.36908
Exact quantum algorithm for searching of multiple sets intersection
Sheng-Ao Mao, Lin Zhang, Bo Li
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.
AI Summary
The paper considers finding an element in the intersection of $k$ subsets of an unstructured search space of size $N=2^n$, using the individual subsets’ membership oracles. Its objective is unit-probability search rather than the generally nonunit success probability of ordinary Grover search. For diagonal subset phase oracles $O_i$, it constructs the intersection projector $\Pi=\prod_{i=0}^{k-1}(I-O_i)/2$ and the marking operator $O_{\cap}(\phi)=I+(e^{i\phi}-1)\Pi$. Combining this with a matching phase rotation about the uniform initial state gives Long-style exact amplitude amplification. Writing $r$ for the intersection size and $\beta=\arcsin\sqrt{r/N}$, the prescribed phase is $\phi=2\arcsin[\sin(\pi/(4L+2))/\sin\beta]$, with $L\geq\lfloor(\pi/2+\beta)/(2\beta)\rfloor$. A two-dimensional invariant-subspace calculation, using the Cayley–Hamilton theorem, establishes vanishing non-target amplitude after $L$ iterations. The circuit computes subset memberships into ancillas, forms their conjunction with Toffoli gates, applies a conditional phase, and uncomputes the workspace. It assumes access to controlled subset phase oracles and uses $2k-2$ auxiliary qubits. The phase prescription requires the intersection size $r$. Numerical circuit simulations use $N=32$, $k=2,3,4$, and $r=1,2,3,4$; the corresponding iteration counts are $4,3,3,2$. Each configuration produces only target outcomes in 1,000 shots. The stated scope assumes a nonempty, proper intersection. The conclusion highlights applications with modest search-space dimension and a need for certainty, or where initial-state preparation and changes to experimental settings are difficult.
Generative-AI tools were used for language refinement. They were also used to assist in writing the experimental code.
Central claim may not hold: The exact-search guarantee assumes knowledge of the intersection cardinality r, which determines the phase and iteration count, but the abstract does not state this requirement and the paper provides no procedure to obtain it. The circuit requires controlled versions of the individual phase oracles, a stronger access assumption than the stated problem supplies; ordinary black-box phase-oracle access alone cannot generally identify the intersection.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 13 pages, 16 figures