计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (1): 353-362.doi: 10.11896/jsjkx.241100181

• 信息安全 • 上一篇    下一篇

基于变分量子的离散对数求解算法

张兴兰, 容潇军   

  1. 北京工业大学计算机学院 北京 100124;
    可信计算北京重点实验室 北京 100124
  • 收稿日期:2024-11-28 修回日期:2025-02-24 发布日期:2026-01-08
  • 通讯作者: 容潇军(rongxiaojun@emails.bjut.edu.cn)
  • 作者简介:(zhangxinglan@bjut.edu.cn)
  • 基金资助:
    国家自然科学基金(62202017)

Variational Quantum Algorithm for Solving Discrete Logarithms

ZHANG Xinglan, RONG Xiaojun   

  1. School of Computer Science, Beijing University of Technology, Beijing 100124, China;
    Beijing Key Laboratory of Trusted Computing, Beijing 100124, China
  • Received:2024-11-28 Revised:2025-02-24 Online:2026-01-08
  • About author:ZHANG Xinglan,born in 1970,Ph.D,professor,master’s supervisor.Her main research interests include foundational theories and technologies of cryptography,artificial intelligence security and quantum computing.
    RONG Xiaojun,born in 2001,postgra-duate.His main research interest is quantum computing.
  • Supported by:
    National Natural Science Foundation of China(62202017).

PDF (PC)

7

摘要： 离散对数问题是数论中的一个重要问题,因其求解困难,经典计算机没有高效的算法可以解决这一难题,故离散对数问题被广泛用于公钥密码体系中,而一旦离散对数问题被破解,将直接威胁密码系统的安全。但随着量子计算理论的引入,人们开始考虑采用量子计算机解决离散对数问题。目前求解离散对数问题的量子算法基本都基于Shor算法,但Shor算法由于自身的局限性,大多存在量子线路深度过大、使用量子比特数过多、后处理步骤复杂等问题,Shor算法难以在有噪声的中等规模量子(Noisy Intermediate-scale Quantum,NISQ)计算机上实现。为了解决这些问题,提出了基于变分量子的离散对数求解算法。首先,利用量子计算的并行性来计算参数化量子态的模幂,并设计标记解线路,将符合离散对数问题的解映射到辅助位上。然后,通过经典优化器不断对含参量子线路中的参数进行调整,使设计好的损失函数不断降低。最后,将经典优化器调整后的参数提出,并放入测量线路中进行测量,即可以较高的概率得到离散对数问题的解。与Shor算法相比,基于变分量子的离散对数求解算法减少了所需量子比特,同时将量子线路的深度减小了近一半。此外,还给出了详细的量子线路设计并用Python中的Qiskit包验证了所提算法的正确性。

关键词: 量子计算, 变分量子算法, 离散对数问题, Shor算法, Qiskit

Abstract: The discrete logarithm problem is a significant challenge in number theory,and due to the difficulty of solving it,classical computers lack efficient algorithms for this task.As a result,the discrete logarithm problem is widely used in public key cryptosystems,and if it were cracked,it would pose a direct threat to the security of these systems.However,with the advent of quantum computing,researchers have begun exploring quantum computers as a potential solution for the discrete logarithm problem.Currently,most quantum algorithms for solving the discrete logarithm problem are based on Shor’s algorithm.However,due to Shor’s inherent limitations,these algorithms often face issues such as large quantum circuit depth,high qubit usage and complex post-processing steps.This makes it difficult for Shor’s algorithm to be implemented on NISQ computers.To address these issues,this paper proposes a novel approach by introducing a variational quantum algorithm for solving the discrete logarithm pro-blem.This algorithm leverages the parallelism of quantum computing to compute the modular exponentiation of parameterized quantum states.It also designs a marked solution circuit that maps valid solutions of the discrete logarithm problem onto auxiliary qubits.Then,a classical optimizer is used to iteratively adjust the parameters within the parameterized quantum circuit,continuously reducing the value of a designed loss function.Finally,the optimized parameters from the classical optimizer are fed into the measurement circuit,where the solution to the discrete logarithm problem can be obtained with high probability.Compared to Shor’s algorithm,the proposed method significantly reduces the required number of qubits and nearly halves the quantum circuit depth.Furthermore,this paper provides a detailed design of the quantum circuit and verifies the correctness of the proposed algorithm using the Qiskit package in Python.

Key words: Quantum computing, Variational quantum algorithm, Discrete logarithm problem, Shor’s algorithm, Qiskit

中图分类号: 

  • TP309
[1]FEYNMAN R P.Simulating physics with computers[J].International Journal of Theoretical Physics,1982,21(6):467-488.
[2]DEUTSCH D,JOZSA R.Rapid solution of problems by quantum computation[C]//Proceedings of the Royal Society of London.1992:553-558.
[3]SHOR P W.Algorithms for quantum computation:discrete logarithms and factoring[C]//Proceedings 35th Annual Sympo-sium on Foundations of Computer Science.2002:124-134.
[4]GROVER L K.A Fast Quantum Mechanical Algorithm for Database Search[C]//Proceedings of the 28th Annual ACM Symposium on Theory of Computing.1996:212-219.
[5]HARROW A W,HASSIDIM A,LLOYD S.Quantum Algo-rithm for Linear Systems of Equations[J].Physical Review Letters,2009,103(15):150502.
[6]OHZEKI M.Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian[J].arXiv:1901.06901,2019.
[7]LLOYD S,MOHSENI M,REBENTROST P.Quantum principal component analysis[J].Nature Physics,2014,10(9):631-633.
[8]GUOFENG Z,HAMDULLA A.Adaptive Morphological Contrast Enhancement Based on Quantum Genetic Algorithm for Point Target Detection[J].Mobile Networks and Applications,2021,26(2):638-648.
[9]DIFFIE W,HELLMAN M.New directions in cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.
[10]ELGAMAL T.A Public Key Cryptosystem and a SignatureScheme Based on Discrete Logarithms[J].IEEE Transactions on Information Theory,1985,31(4):469-472.
[11]POHLIG S,HELLMAN M.An improved algorithm for computing logarithms over GF(p) and its cryptographic significance[J].IEEE Transactions on Information Theory,1978,24(1):106-110.
[12]NIELSEN M A,CHUANG I L.Quantum Computation andQuantum Information[M]//Cambridge:Cambridge University Press,2010.
[13]FU X Q,BAO W S,WANG S.Discrete Logarithm Quantum Computing Algorithm on Z_N[J].Chinese Journal of Compu-ters,2014,37(5):1058-1062.
[14]EKERÅ M,HÅSTAD J.Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers[J].ar-Xiv:1702.00249,2017.
[15]AONO Y,LIU S,TANAKA T,et al.The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers[J].arXiv:2111.06102,2021.
[16]WROŃSKI M.Practical Solving of Discrete Logarithm Problem over Prime Fields Using Quantum Annealing[C]//Computational Science-ICCS 2022.2022:93-106.
[17]PRESKILL J.Quantum Computing in the NISQ era and beyond[J].arXiv:1801.00862,2018.
[18]ORTS F,FILATOVAS E,ORTEGA G,et al.Improving thenumber of t gates and their spread in integer multipliers on quantum computing[J].Physical Review A,2023,107(4):042621.
[19]CEREZO M,ARRASMITH A,BABBUSH R,et al.Variational Quantum Algorithms[J].Nature Reviews Physics,2021,3(9):625-644.
[20]ZHANG X L,ZHANG F.Variational Quantum ComputationInteger Factorization Algorithm[J].International Journal of Theoretical Physics,2023,62(11):245-264.
[21]CROSS A.The IBM Q Experience and Qiskit Open-SourceQuantum Computing Software[C]//APS March Meeting Abstracts.2018.
[22]SCHULD M.Supervised quantum machine learning models are kernel methods[J].arXiv:2101.11020,2021.
[23]ARAUJO I F,PARK D K,LUDERMIR T B,et al.Configurable sublinear circuits for quantum state preparation[J].Quantum Information Processing,2023,22(2):123-149.
[24]HAVLÍČEK V,CÓRCOLES A,TEMME K,et al.Supervisedlearning with quantum-enhanced feature spaces[J].Nature,2019,567(7747):209-212.
[25]LAROSE R,COYLE B.Robust data encodings for quantumclassifiers[J].Physical Review A,2020,102(3):032420.
[26]SIM S,JOHNSON P D,ASPURU-GUZIK A.Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms[J].arXiv:1905.10876,2019.
[27]KANDALA A,MEZZACAPO A,TEMME K,et al.Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets[J].Nature,2017,549(7671):242-264.
[28]SCHULD M,BERGHOLM V,GOGOLIN C,et al.Evaluating analytic gradients on quantum hardware[J].Physical Review A,2019,99(3):032331.
[29]STOKES J,IZAAC J,KILLORAN N,et al.Quantum Natural Gradient[J].arXiv:1909.02108,2019.
[30]GACON J,ZOUFAL C,CARLEO G,et al.Simultaneous Per-turbation Stochastic Approximation of the Quantum Fisher Information[J].arXiv:2103.09232,2021.
[31]POWELL M J D.A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation[M]//Dordrecht:Springer Netherlands,1994.
[32]BEAUREGARD S.Circuit for Shor’s algorithm using 2n+3 qubits[J].Quantum Information & Computation,2003,3(2):175-185.
[33]DRAPER T G.Addition on a Quantum Computer[J].arXiv:quant-ph/0008033,2000.
[34]LARASATI H T,KIM H.Simulation of Modular Exponentiation Circuit for Shor's Algorithm in Qiskit[C]//2020 14th International Conference on Telecommunication Systems,Services,and Applications(TSSA).2020:1-7.
[35]BARENCO A,BENNETT C H,CLEVE R,et al.Elementary gates for quantum computation[J].Physical Review A,1995,52(5):3457-3467.
[36]SILVA A J D,PARK D K.Linear-depth quantum circuits formultiqubit controlled gates[J].Physical Review A,2022,106(4):042602.
[37]XIULI S,LIANGSEN W.An improved circuit for Shor’s factoring algorithm using 2n+2 qubits[J].Quantum Information Processing,2023,22(11):402-418.
[38]ORTIZ M C,KIEFEROVÁ M,WIEBE N.Entanglement-in-duced barren plateaus[J].PRX Quantum,2021,2(4):040316.
[39]SKOLIK A,MCCLEAN J R,MOHSENI M,et al.Layerwise learning for quantum neural networks[J].Quantum Machine Intelligence,2021,3:1-11.
[40]CAMPOS E,NASRALLAH A,BIAMONTE J.Abrupt transitions in variational quantum circuit training[J].Physical Review A,2021,103(3):032607.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发