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

Advanced Quantum Technologies

Distributed Quantum Algorithm for the NISQ Era: A Novel Approach to Solving Simon's Problem with Reduced Resources

Xu Zhou, Yuchen Wang, Wenxuan Tao, Zhuojun Zhou, Le Luo

Published Apr 13, 2025• 1 citation
Publisher

Abstract

Abstract Distributed quantum computation has gained significant interest in the noisy intermediate‐scale quantum (NISQ) era. This paradigm requires each computing node to possess a reduced number of qubits and quantum gates. In this study, a Distributed Simon's Algorithm (DSA) is designed to tackle Simon's problem, which entails the discovery of a hidden string of a promised Boolean function , where if and only if or . Specifically, 1) our algorithm is capable of being partitioned into any nodes, where ; 2) the number of queries required by the DSA is , while that of the original Simon's algorithm (SA) is ; 3) the maximum number of qubits required by our approach at a single node is , which is fewer than the qubits required by both the SA and existing distributed Simon's algorithm. Here, denotes the number of computing qubits needed for the ‐th node and satisfies ; 4) the optimal circuit depth of the DSA is , which is reduced compared to the circuit depth of the SA, ; 5) in contrast to currently distributed schemes, the DSA eliminates the need for classical queries; 6) how the DSA solves a specific Simon's problem (e.g., ) is also simulated using MindSpore Quantum, a quantum simulation software. The simulation results show that the DSA features a shallower quantum circuit, thereby demonstrating enhanced resistance to circuit noise. This characteristic makes it more feasible for implementation in the NISQ era.

DOI
10.1002/qute.202500067

Related papers

Distributed quantum algorithm for Simon's problem

Jiawei Tan, Ligang Xiao, Daowen Qiu +2 more

Limited by today's physical devices, quantum circuits with a long depth are usually noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we study Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The algorithm proposed by us has the advantage of exponential acceleration compared with classical distributed computing and has the advantage of square acceleration compared with the best distributed quantum algorithm proposed before in query complexity. In particular, the previous distributed quantum algorithm for Simon's problem cannot be extended to the case of more than two computing nodes (i.e., two subproblems), but our distributed quantum algorithm can be extended to the case of multiple computing nodes (i.e., multiple subproblems).

arXiv:2204.11388•Physical Review A•Sep 13, 2022•31 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

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

A parallel and distributed fixed-point quantum search algorithm for solving SAT problems

He Wang, Jinyang Yao

Boolean satisfiability (SAT) problem is of fundamental importance in computer science and many application domains. For Grover's algorithm, solving the SAT problem requires $\mathcal{O}(\sqrt{2^n})$ queries--where n denotes the number of logic variables in the problem. However, Grover's algorithm suffers from the Souffle problem: specifically, when the number of solutions is unknown, terminating the algorithm too early or too late leads to a significant reduction in the probability of obtaining a solution. In this paper, we propose a parallel fixed-point (PFP) search algorithm to solve the SAT problem. By exploiting entanglement, each clause in the conjunctive normal form (CNF) formula can be processed independently, leading to a significant reduction in circuit depth. We also discuss how to perform the algorithm in distributed manner. These make the PFPS algorithm particularly suitable for the noisy intermediate-scale quantum (NISQ) era.

quant-pharXiv:2604.09980•Apr 14, 2026•0 citations

Improved distributed quantum algorithm for Simon's problem

Hao Li, Daowen Qiu

Simon's problem is one of the most important problems demonstrating the power of quantum computing. Recently, an interesting distributed quantum algorithm for Simon's problem was proposed, where a key sorting operator requiring a large number of qubits was employed. In this paper, we design an improved distributed quantum algorithm for Simon's problem without using sorting operators, and our algorithm has the advantage of reducing half number of qubits required for a single computing node. Moreover, our algorithm does not involve the classical search process.

arXiv:2504.09605•Apr 13, 2025•0 citations

Distributed Exact Quantum Amplitude Amplification Algorithm for Arbitrary Quantum States

Xu Zhou, Wenxuan Tao, Keren Li +1 more

In the noisy intermediate-scale quantum (NISQ) era, distributed quantum computation has garnered considerable interest, as it overcomes the physical limitations of single-device architectures and enables scalable quantum information processing. In this study, we focus on the challenge of achieving exact amplitude amplification for quantum states with arbitrary amplitude distributions and subsequently propose a Distributed Exact Quantum Amplitude Amplification Algorithm (DEQAAA). Specifically, (1) it supports partitioning across any number of nodes $t$ within the range $2 \leq t \leq n$; (2) the maximum qubit count required for any single node is expressed as $\max \left(n_0,n_1,\dots,n_{t-1} \right) $, where $n_j$ represents the number of qubits at the $j$-th node, with $\sum_{j=0}^{t-1} n_j =n$; (3) it can realize exact amplitude amplification for multiple targets of a quantum state with arbitrary amplitude distributions; (4) we verify the effectiveness of DEQAAA by resolving a specific exact amplitude amplification task involving two targets (8 and 14 in decimal) via MindSpore Quantum, a quantum simulation software, with tests conducted on 4-qubit, 6-qubit, 8-qubit and 10-qubit systems. Notably, through the decomposition of $C^{n-1}PS$ gates, DEQAAA demonstrates remarkable advantages in both quantum gate count and circuit depth as the qubit number scales, thereby boosting its noise resilience. In the 10-qubit scenario, for instance, it achieves a reduction of over $97\%$ in both indicators compared to QAAA and EQAAA, underscoring its outstanding resource-saving performance.

quant-pharXiv:2601.09128•Science China Information Sciences•Jan 15, 2026•0 citations
Abstract Distributed quantum computation has gained significant interest in the noisy intermediate‐scale quantum (NISQ) era. This paradigm requires each computing node to possess a reduced number of qubits and quantum gates. In this study, a Distributed Simon's Algorithm (DSA) is designed to tackle Simon's problem, which entails the discovery of a hidden string of a promised Boolean function , where if and only if or . Specifically, 1) our algorithm is capable of being partitioned into any nodes, where ; 2) the number of queries required by the DSA is , while that of the original Simon's algorithm (SA) is ; 3) the maximum number of qubits required by our approach at a single node is , which is fewer than the qubits required by both the SA and existing distributed Simon's algorithm. Here, denotes the number of computing qubits needed for the ‐th node and satisfies ; 4) the optimal circuit depth of the DSA is , which is reduced compared to the circuit depth of the SA, ; 5) in contrast to currently distributed schemes, the DSA eliminates the need for classical queries; 6) how the DSA solves a specific Simon's problem (e.g., ) is also simulated using MindSpore Quantum, a quantum simulation software. The simulation results show that the DSA features a shallower quantum circuit, thereby demonstrating enhanced resistance to circuit noise. This characteristic makes it more feasible for implementation in the NISQ era.
Limited by today's physical devices, quantum circuits with a long depth are usually noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we study Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The algorithm proposed by us has the advantage of exponential acceleration compared with classical distributed computing and has the advantage of square acceleration compared with the best distributed quantum algorithm proposed before in query complexity. In particular, the previous distributed quantum algorithm for Simon's problem cannot be extended to the case of more than two computing nodes (i.e., two subproblems), but our distributed quantum algorithm can be extended to the case of multiple computing nodes (i.e., multiple subproblems).
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.
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.
Boolean satisfiability (SAT) problem is of fundamental importance in computer science and many application domains. For Grover's algorithm, solving the SAT problem requires O(2n)\mathcal{O}(\sqrt{2^n})O(2n​) queries--where n denotes the number of logic variables in the problem. However, Grover's algorithm suffers from the Souffle problem: specifically, when the number of solutions is unknown, terminating the algorithm too early or too late leads to a significant reduction in the probability of obtaining a solution. In this paper, we propose a parallel fixed-point (PFP) search algorithm to solve the SAT problem. By exploiting entanglement, each clause in the conjunctive normal form (CNF) formula can be processed independently, leading to a significant reduction in circuit depth. We also discuss how to perform the algorithm in distributed manner. These make the PFPS algorithm particularly suitable for the noisy intermediate-scale quantum (NISQ) era.
Simon's problem is one of the most important problems demonstrating the power of quantum computing. Recently, an interesting distributed quantum algorithm for Simon's problem was proposed, where a key sorting operator requiring a large number of qubits was employed. In this paper, we design an improved distributed quantum algorithm for Simon's problem without using sorting operators, and our algorithm has the advantage of reducing half number of qubits required for a single computing node. Moreover, our algorithm does not involve the classical search process.
In the noisy intermediate-scale quantum (NISQ) era, distributed quantum computation has garnered considerable interest, as it overcomes the physical limitations of single-device architectures and enables scalable quantum information processing. In this study, we focus on the challenge of achieving exact amplitude amplification for quantum states with arbitrary amplitude distributions and subsequently propose a Distributed Exact Quantum Amplitude Amplification Algorithm (DEQAAA). Specifically, (1) it supports partitioning across any number of nodes ttt within the range 2≤t≤n2 \leq t \leq n2≤t≤n; (2) the maximum qubit count required for any single node is expressed as $\max \left(n_0,n_1,\dots,n_{t-1} \right) $, where njn_jnj​ represents the number of qubits at the jjj-th node, with ∑j=0t−1nj=n\sum_{j=0}^{t-1} n_j =n∑j=0t−1​nj​=n; (3) it can realize exact amplitude amplification for multiple targets of a quantum state with arbitrary amplitude distributions; (4) we verify the effectiveness of DEQAAA by resolving a specific exact amplitude amplification task involving two targets (8 and 14 in decimal) via MindSpore Quantum, a quantum simulation software, with tests conducted on 4-qubit, 6-qubit, 8-qubit and 10-qubit systems. Notably, through the decomposition of Cn−1PSC^{n-1}PSCn−1PS gates, DEQAAA demonstrates remarkable advantages in both quantum gate count and circuit depth as the qubit number scales, thereby boosting its noise resilience. In the 10-qubit scenario, for instance, it achieves a reduction of over 97%97\%97% in both indicators compared to QAAA and EQAAA, underscoring its outstanding resource-saving performance.