Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Frontiers of Physics

Distributed exact Grover’s algorithm

Xu Zhou, Daowen Qiu, Le Luo

Published Aug 14, 2023• 23 citations
Publisher

Abstract

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.

DOI
10.1007/s11467-023-1327-x

Related papers

Distributed exact quantum algorithms for Bernstein-Vazirani and search problems

Xu Zhou, Daowen Qiu, Lou, Le

Distributed quantum computation has gained extensive attention since small-qubit quantum computers seem to be built more practically in the noisy intermediate-scale quantum (NISQ) era. In this paper, we give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. Though the designing techniques are simple in the light of BV algorithm, Grover's algorithm, the improved Grover's algorithm by Long, and the distributed Grover's algorithm by Qiu et al, in comparison to BV algorithm, the circuit depth of DBVA is not greater than $2^{\text{max}(n_0, n_1, \cdots, n_{t-1})}+3$ instead of $2^{n}+3$, and the circuit depth of DEGA is $8(n~\text{mod}~2)+9$, which is less than the circuit depth of Grover's algorithm, $1 + 8\left\lfloor \fracπ{4}\sqrt{2^n} \right\rfloor$. In particular, we provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods. By simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithm has superiority of resisting noise.

arXiv:2303.10670•Mar 19, 2023•2 citations

Low Depth Distributed Quantum Algorithms for Unordered Database Search

Huaijing Huang, Daowen Qiu, Ximing Hua +1 more

Grover's algorithm accelerates unstructured database search quadratically compared to classical algorithms. In the NISQ era, distributed quantum computing can decrease circuit depth and reduce noise. In this paper, an algorithm for constructing query operators for subfunctions is proposed. By dividing the target string of the search problem into several substrings and integrating the query operator of each subfunction, a low-depth distributed exact quantum search algorithm is designed. The contributions of this paper are as follows: (1) The proposed distributed algorithm has a lower circuit depth and can mitigate error accumulation compared to distributed quantum search algorithms; (2) The target can be accurately located by the proposed distributed algorithm; (3) Experiments conducted with the quantum software MindQuantum confirm the effectiveness and feasibility of the proposed distributed algorithm. Moreover, the introduction of noise to the circuit during these experiments indicates that the algorithm possesses an inherent capacity for noise resistance.

quant-pharXiv:2604.14081•Chinese Journal of Physics•Apr 16, 2026•1 citation

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

Zhong, Shijin, Wei Li, Guangzhen Dai +1 more

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.

arXiv:2412.18306•Dec 24, 2024•0 citations

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

Distributed exact multi-objective quantum search algorithm

Hao Li, Daowen Qiu, Le Luo

Multi-objective search means searching for any one of several objectives in an unstructured database. Grover's algorithm has quadratic acceleration in multi-objection search than classical ones. Iterated operator in Grover's algorithm is a key element and plays an important role in amplitude amplification. In this paper, we design two distributed iterated operators and therefore two new distributed Grover's algorithms are obtained with the following advantages: (1) Compared to Grover's algorithm and the modified Grover's algorithm by Long, our distributed algorithms require fewer qubits; (2) Compared to the distributed Grover's algorithm proposed by Qiu et al., one of our distributed algorithms is exact. Of course, both our distributed algorithms require quite quantum communication and involve a number of more complicated unitary operators as cost, but there still may have certain advantage of physical realizability in the Noisy Intermediate-Scale Quantum (NISQ) era.

arXiv:2409.04039•Sep 6, 2024•0 citations

Two improvements in Grover's algorithm

Kai Kang

Grover search algorithm is applied to the current number of objectives in quantum unsorted database, the meaning of each goal difference is not taken into account. When the target is more than a quarter of the total items, the probability of the target falls quickly identify and target increases, and when the target is more than half of the total items, the algorithm will fail. To solve these problems, first of all, based on a weighted index improvement is proposed in which each target in accordance with the right given to the importance of the weight coefficient. These different weight coefficients, we give all the target state, which may make the probability of each target equal weights of the quantum superposition. Secondly, an improved phase matching is proposed the phase rotation in both directions is the same, and the inner product of two states by the target amplitude superposition and initial state of the system is determined. When this inner product is 1/2 or more, when using the improved phase matching, the target may be 100% probability and by only one Grover iteration. Finally, the effectiveness of these measures by a simple search instance validation.

Chinese Control and Decision Conference (CCDC)•May 1, 2015•5 citations
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⌊π42n⌋1 + 8\left\lfloor {{\pi \over 4}\sqrt {{2^n}} } \right\rfloor 1+8⌊4π​2n​⌋ and 9+8⌊π42n−12⌋9 + 8\left\lfloor {{\pi \over 4}\sqrt {{2^n}} - {1 \over 2}} \right\rfloor 9+8⌊4π​2n​−21​⌋ , 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.
Distributed quantum computation has gained extensive attention since small-qubit quantum computers seem to be built more practically in the noisy intermediate-scale quantum (NISQ) era. In this paper, we give a distributed Bernstein-Vazirani algorithm (DBVA) with ttt computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. Though the designing techniques are simple in the light of BV algorithm, Grover's algorithm, the improved Grover's algorithm by Long, and the distributed Grover's algorithm by Qiu et al, in comparison to BV algorithm, the circuit depth of DBVA is not greater than 2max(n0,n1,⋯ ,nt−1)+32^{\text{max}(n_0, n_1, \cdots, n_{t-1})}+32max(n0​,n1​,⋯,nt−1​)+3 instead of 2n+32^{n}+32n+3, and the circuit depth of DEGA is 8(n mod 2)+98(n~\text{mod}~2)+98(n mod 2)+9, which is less than the circuit depth of Grover's algorithm, 1+8⌊π42n⌋1 + 8\left\lfloor \fracπ{4}\sqrt{2^n} \right\rfloor1+8⌊4π​2n​⌋. In particular, we provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods. By simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithm has superiority of resisting noise.
Grover's algorithm accelerates unstructured database search quadratically compared to classical algorithms. In the NISQ era, distributed quantum computing can decrease circuit depth and reduce noise. In this paper, an algorithm for constructing query operators for subfunctions is proposed. By dividing the target string of the search problem into several substrings and integrating the query operator of each subfunction, a low-depth distributed exact quantum search algorithm is designed. The contributions of this paper are as follows: (1) The proposed distributed algorithm has a lower circuit depth and can mitigate error accumulation compared to distributed quantum search algorithms; (2) The target can be accurately located by the proposed distributed algorithm; (3) Experiments conducted with the quantum software MindQuantum confirm the effectiveness and feasibility of the proposed distributed algorithm. Moreover, the introduction of noise to the circuit during these experiments indicates that the algorithm possesses an inherent capacity for noise resistance.
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%100\%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.
Multi-objective search means searching for any one of several objectives in an unstructured database. Grover's algorithm has quadratic acceleration in multi-objection search than classical ones. Iterated operator in Grover's algorithm is a key element and plays an important role in amplitude amplification. In this paper, we design two distributed iterated operators and therefore two new distributed Grover's algorithms are obtained with the following advantages: (1) Compared to Grover's algorithm and the modified Grover's algorithm by Long, our distributed algorithms require fewer qubits; (2) Compared to the distributed Grover's algorithm proposed by Qiu et al., one of our distributed algorithms is exact. Of course, both our distributed algorithms require quite quantum communication and involve a number of more complicated unitary operators as cost, but there still may have certain advantage of physical realizability in the Noisy Intermediate-Scale Quantum (NISQ) era.
Grover search algorithm is applied to the current number of objectives in quantum unsorted database, the meaning of each goal difference is not taken into account. When the target is more than a quarter of the total items, the probability of the target falls quickly identify and target increases, and when the target is more than half of the total items, the algorithm will fail. To solve these problems, first of all, based on a weighted index improvement is proposed in which each target in accordance with the right given to the importance of the weight coefficient. These different weight coefficients, we give all the target state, which may make the probability of each target equal weights of the quantum superposition. Secondly, an improved phase matching is proposed the phase rotation in both directions is the same, and the inner product of two states by the target amplitude superposition and initial state of the system is determined. When this inner product is 1/2 or more, when using the improved phase matching, the target may be 100% probability and by only one Grover iteration. Finally, the effectiveness of these measures by a simple search instance validation.