© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2412.18306

The optimization of exact multi-target quantum search algorithm based on MindSpore

Zhong, Shijin, Wei Li, Guangzhen Dai, Daohua Wu

Published Dec 24, 2024• 0 citations

Abstract

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 version of Grover's search algorithm by introducing a phase-matching condition that can search for the target state with a 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 2-qubit with 2 targets, 5-qubit with 2 targets, 5-qubit with 4 targets, and 6-qubit with 3 targets, are implemented on MindSpore framework. 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.4% and maintain a 100% success probability. Our code are available at https://github.com/mindsporelab/models/tree/master/research/arxiv_papers/GROVER-OP. Thanks for the support provided by MindSpore Community.

DOI: 10.48550/arxiv.2412.18306

Related papers

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

Improved quantum multi-object search algorithm

Wei-Yun Ma

Grover’s quantum mechanical search algorithm solves the unsorted database search with quadratic speed-up over the classical algorithms.But Grover’s algorithm will be inefficient when the number of matching is close to 2n/2.This paper presents a quantum algorithm which can get a target item with certainty by a single query when the number of the target items is more than a quarter.

Computer Engineering and Applications Journal•Jan 1, 2009•0 citations

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•6 citations

Exact and Fixed-Point Grover Search with Qudits

Tanay Roy

Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.

quant-pharXiv:2607.24658•Jul 28, 2026•0 citations

Distributed exact Grover’s algorithm

Xu Zhou, Daowen Qiu, Le Luo

Distributed quantum computation has gained extensive attention. In this paper, we consider a search problem that includes only one target item in the unordered database. After that, we propose a distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into ⌊n/2⌋ parts. Specifically, (i) our algorithm is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is 8(n mod 2) + 9, which is less than the circuit depths of the original and modified Grover’s algorithms, $$1 + 8\left\lfloor {{\pi \over 4}\sqrt {{2^n}} } \right\rfloor $$ and $$9 + 8\left\lfloor {{\pi \over 4}\sqrt {{2^n}} - {1 \over 2}} \right\rfloor $$ , respectively. It only depends on the parity of n, and it is not deepened as n increases; (iii) we provide particular situations of the DEGA on MindQuantum (a quantum software) to demonstrate the practicality and validity of our method. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.

Frontiers of Physics•Aug 14, 2023•23 citations

Grover's search algorithm for $n$ qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•1 citation

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 version of Grover's search algorithm by introducing a phase-matching condition that can search for the target state with a 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 2-qubit with 2 targets, 5-qubit with 2 targets, 5-qubit with 4 targets, and 6-qubit with 3 targets, are implemented on MindSpore framework. 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.4% and maintain a 100% success probability. Our code are available at https://github.com/mindsporelab/models/tree/master/research/arxiv_papers/GROVER-OP. Thanks for the support provided by MindSpore Community.

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.

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.

Distributed quantum computation has gained extensive attention. In this paper, we consider a search problem that includes only one target item in the unordered database. After that, we propose a distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into ⌊n/2⌋ parts. Specifically, (i) our algorithm is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is 8(n mod 2) + 9, which is less than the circuit depths of the original and modified Grover’s algorithms,

1 + 8\left\lfloor {{\pi \over 4}\sqrt {{2^n}} } \right\rfloor

and

9 + 8\left\lfloor {{\pi \over 4}\sqrt {{2^n}} - {1 \over 2}} \right\rfloor

, respectively. It only depends on the parity of n, and it is not deepened as n increases; (iii) we provide particular situations of the DEGA on MindQuantum (a quantum software) to demonstrate the practicality and validity of our method. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.

The success probability of a search of

M

targets from a database of size

N

, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as

\mathcal{O}(\sqrt{N})

for large

N

, the asymptote is not a good indicator of the optimal number of iterations when

\sqrt{M/N}

is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of

n

-qubit Grover's search algorithm with

1 \leq M \leq N

target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given

N

and

M

, there is an upper-bound on the success probability of the algorithm.