<p>Grover’s search algorithm has attracted great attention due to its quadratic speedup over classical algorithms in unsorted database search problems. However, Grover’s algorithm is inefficient in multi-target search problems, except in the case of 1/4 of the data in the database satisfying the search conditions. Long presented a modified Grover’s algorithm by introducing a phase-matching condition, which can search for the target state with zero theoretical failure rate. In this work, we present an optimized exact multi-target search algorithm based on the modified Grover’s algorithm, by transforming the canonical diffusion operator to a more efficient diffusion operator, which can solve the multi-target search problem with a 100<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4932_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\%$</EquationSource> <EquationSource Format="MATHML"><math> <mo>%</mo> </math></EquationSource> </InlineEquation> success rate while requiring fewer gate counts and shallower circuit depth. After that, the optimized multi-target algorithm for four different items, including two-qubit with two targets, five-qubit with two targets, six-qubit with three targets, and eight-qubit with four targets, are implemented on two quantum computing frameworks MindQuantum and IBM Quantum, respectively. The experimental results show that, compared with Grover’s algorithm and the modified Grover’s algorithm, the proposed algorithm can reduce the quantum gate count by at least 21.1<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4932_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\%$</EquationSource> <EquationSource Format="MATHML"><math> <mo>%</mo> </math></EquationSource> </InlineEquation> and the depth of the quantum circuit by at least 11.7<InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4932_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\%$</EquationSource> <EquationSource Format="MATHML"><math> <mo>%</mo> </math></EquationSource> </InlineEquation> and maintain a 100<InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4932_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\%$</EquationSource> <EquationSource Format="MATHML"><math> <mo>%</mo> </math></EquationSource> </InlineEquation> success probability.</p>

An optimized exact multi-target search algorithm

期刊论文
发表日期：

2025年9月23日

查看全文

Shijin Zhong,
Yingnan Zhao,
Guangzhen Dai,
Daohua Wu

摘要

Grover’s search algorithm has attracted great attention due to its quadratic speedup over classical algorithms in unsorted database search problems. However, Grover’s algorithm is inefficient in multi-target search problems, except in the case of 1/4 of the data in the database satisfying the search conditions. Long presented a modified Grover’s algorithm by introducing a phase-matching condition, which can search for the target state with zero theoretical failure rate. In this work, we present an optimized exact multi-target search algorithm based on the modified Grover’s algorithm, by transforming the canonical diffusion operator to a more efficient diffusion operator, which can solve the multi-target search problem with a 100 $\%$ $%$ success rate while requiring fewer gate counts and shallower circuit depth. After that, the optimized multi-target algorithm for four different items, including two-qubit with two targets, five-qubit with two targets, six-qubit with three targets, and eight-qubit with four targets, are implemented on two quantum computing frameworks MindQuantum and IBM Quantum, respectively. The experimental results show that, compared with Grover’s algorithm and the modified Grover’s algorithm, the proposed algorithm can reduce the quantum gate count by at least 21.1 $\%$ $%$ and the depth of the quantum circuit by at least 11.7 $\%$ $%$ and maintain a 100 $\%$ $%$ success probability.