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

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.