中国物理B ›› 2026, Vol. 35 ›› Issue (3): 30303-030303.doi: 10.1088/1674-1056/adfb58

• • 上一篇    下一篇

Distributed Kuperberg’s algorithm

Peng-Yu Yang(杨鹏宇)1, Xin Zhang(张新)2, and Song Lin(林崧)1,†   

  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
  • 收稿日期:2025-06-12 修回日期:2025-07-31 接受日期:2025-08-14 出版日期:2026-02-11 发布日期:2026-03-10
  • 通讯作者: Song Lin E-mail:lins95@fjnu.edu.cn
  • 基金资助:
    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).

Distributed Kuperberg’s algorithm

Peng-Yu Yang(杨鹏宇)1, Xin Zhang(张新)2, and Song Lin(林崧)1,†   

  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
  • Received:2025-06-12 Revised:2025-07-31 Accepted:2025-08-14 Online:2026-02-11 Published:2026-03-10
  • Contact: Song Lin E-mail:lins95@fjnu.edu.cn
  • Supported by:
    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).

RichHTML

0

PDF (PC)

18

赞

摘要： 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.

关键词: Kuperberg's algorithm, distributed quantum computing, function decomposition, quantum circuit depth

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.

Key words: Kuperberg's algorithm, distributed quantum computing, function decomposition, quantum circuit depth

中图分类号:  (Quantum algorithms, protocols, and simulations)

  • 03.67.Ac
03.67.Lx (Quantum computation architectures and implementations) 03.67.-a (Quantum information)