Paper 2026/1001

Distributed Simon's Algorithm with Less Per-Node Qubit Overhead and Its Application to Cryptanalysis

Xiaofan Zhen, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Shuqin Fan, State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China

Yonglin Hao, State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China

Fei Gao, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Abstract

Distributed quantum computing (DQC) enables multi-device collaboration to reduce per-node circuit depth and solve larger-scale problems beyond the processing capability of a single quantum device. In 2022, Tan et al. proposed a distributed Simon's algorithm via a concatenation-type periodic function. In comparison with the standard version, the distributed Simon's algorithm has a lower per-node quantum query complexity resulting in not only a reduced per-node circuit depth but a higher per-node qubit requirement as well. This paper proposes a new distributed Simon's algorithm by constructing an XOR-type periodic function, which can reduce both the per-node quantum query complexity and the per-node qubit requirement. Specifically, the per-node quantum query complexity is reduced to $2c(n-t)$ ($c>3$), matching that of Tan et al.'s scheme; furthermore, the per-node qubit requirement is diminished significantly from Tan et al.'s $2^{t+1}m$ to $m+n-t$, which is an exponential reduction with respect to $t$. Here, $n$ and $m$ respectively denote the input and output lengths of the periodic function while $t$ is an integer satisfying $n/2<t<n$. Given the scale limitations of current quantum hardware, our distributed algorithm makes it feasible to tackle larger-scale problems that cannot be solved on a single quantum device. Based on this new algorithm, we propose distributed quantum key-recovery attacks on the SoEM22 construction. Compared with state-of-the-art non-distributed quantum attacks based on the standard Simon's algorithm, our attack requires notably lower per-node qubit overhead, while retaining comparable time complexity in both the classical and quantum query models.

@misc{cryptoeprint:2026/1001,
      author = {Zhenqiang Li and Xiaofan Zhen and Shuqin Fan and Yonglin Hao and Fei Gao},
      title = {Distributed Simon's Algorithm with Less Per-Node Qubit Overhead and Its Application to Cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1001},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1001}
}