|
|
|
Distributed Kuperberg's algorithm |
| Peng-Yu Yang(杨鹏宇)1, Xin Zhang(张新)2, and Song Lin(林崧)1,† |
1 College of Computer and Cyber Security, Fujian Normal University, Fuzhou 350117, China;
2 School of Mathematics and Statistics, Fujian Normal University, Fuzhou 350117, China |
|
|
|
|
Abstract As an important quantum cryptanalysis algorithm, Kuperberg's algorithm efficiently addresses the dihedral hidden subgroup problem with sub-exponential acceleration. However, when dealing with large numbers, the algorithm demands a deeper quantum circuit depth, rendering its implementation on current quantum devices prone to noise interference and thereby significantly reducing its efficiency. To mitigate this challenge, this paper proposes a distributed Kuperberg's algorithm. It decomposes the original function into sub-functions which can be executed on different nodes in parallel. The implementation of these sub-functions necessitates a shallower quantum circuit depth and a reduced number of qubits when contrasted with the execution of the original function. Furthermore, the proposed algorithm can be directly generalized to an arbitrary number of nodes by adjusting the quantity of input qubits. The utilization of multi-node parallel processing makes the proposed algorithm a linear enhancement in query complexity relative to the original algorithm. To validate the feasibility and demonstrate the superiority of our algorithm, experiments are conducted on the Qiskit platform.
|
Received: 12 June 2025
Revised: 31 July 2025
Accepted manuscript online: 14 August 2025
|
|
PACS:
|
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
03.67.Lx
|
(Quantum computation architectures and implementations)
|
| |
03.67.-a
|
(Quantum information)
|
|
| Fund: Project supported by the National Natural Science Foundation of China (Grant No. 62171131), the Natural Science Foundation of Fujian Province, China (Grant Nos. 2022J01186 and 2023J01533), and the Innovation Program for Quantum Science and Technology (Grant No. 2021ZD0302901). |
Corresponding Authors:
Song Lin
E-mail: lins95@fjnu.edu.cn
|
Cite this article:
Peng-Yu Yang(杨鹏宇), Xin Zhang(张新), and Song Lin(林崧) Distributed Kuperberg's algorithm 2026 Chin. Phys. B 35 030303
|
[1] Shor P W 1994 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, November 20–22 1994 Santa Fe USA p. 124
[2] Grover L K 1997 Phys. Rev. Lett. 79 325
[3] Harrow A W, Hassidim A and Lloyd S 2009 Phys. Rev. Lett. 103 150502
[4] Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N and Lloyd S 2017 Nature 549 195
[5] Preskill J 2018 Quantum 2 79
[6] Greinert F, Müller R, Goorney S R, Laurenza R, Sherson J and Ubben M S 2024 European competence framework for quantum technologies Geneva (Zenodo) pp. 1–30
[7] Caleffi M, Cacciapuoti A S and Bianchi G 2018 Proceedings of the 5th ACM International Conference on Nanoscale Computing and Communication, September 5–7 2018 Reykjavik Iceland p. 3
[8] Chen Z L, Guan Z J, Zhao S X and Cheng X Y 2025 Chin. Phys. B 34 050305
[9] Luo T Y, Zheng Y Z, Fu X and Deng Y X 2024 Chin. Phys. B 33 120302
[10] Tian L, Sun L L, Zhu X Y, Song X K, Yan L L, Liang E J, Su S L and Feng M 2020 Chin. Phys. B 29 050306
[11] Avron J, Casper O and Rozen I 2021 Phys. Rev. A 104 052404
[12] Tan J, Xiao L, Qiu D, Luo L and Mateus P 2022 Phys. Rev. A 106 032417
[13] Qiu D, Luo L and Xiao L 2024 Theor. Comput. Sci. 993 114461
[14] Kuperberg G 2005 SIAM J. Comput. 35 170
[15] Ettinger M, Hoyer P and Knill E 1999 arXiv:quant-ph/9901034 [quantph]
[16] Regev O 2004 SIAM J. Comput. 33 738
[17] Paterson M S 1990 Algorithmica 5 75
[18] Berry DW, Kieferová M, Scherer A, Sanders Y R, Low G H,Wiebe N, Gidney C and Babbush R 2018 npj Quantum Inf. 4 22
[19] Chun M, Baksi A and Chattopadhyay A 2023 Cryptol. ePrint Arch. 286
[20] Bravyi S and Kitaev A 2005 Phys. Rev. A 71 022316
[21] Fowler A G 2012 arXiv:1210.4626 [quant-ph] |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|
