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 algori...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.展开更多
基金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)the Innovation Program for Quantum Science and Technology(Grant No.2021ZD0302901)。
文摘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.
