Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (1): 353-362.doi: 10.11896/jsjkx.241100181

• Information Security • Previous Articles     Next Articles

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 Published: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)

5

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

CLC Number: 

  • 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.
[1] ZHANG Yaolin, LIU Xiaonan, DU Shuaiqi, LIAN Demeng. Hybrid Quantum-classical Compressed Generative Adversarial Networks Based on Matrix Product Operators [J]. Computer Science, 2025, 52(6): 74-81.
[2] XIONG Qibing, MIAO Qiguang, YANG Tian, YUAN Benzheng, FEI Yangyang. Malicious Code Detection Method Based on Hybrid Quantum Convolutional Neural Network [J]. Computer Science, 2025, 52(3): 385-390.
[3] RUAN Ning, LI Chun, MA Haoyue, JIA Yi, LI Tao. Review of Quantum-inspired Metaheuristic Algorithms and Its Applications [J]. Computer Science, 2025, 52(10): 190-200.
[4] KANG Zhong, WANG Maoning, MA Xiaowen, DUAN Meijiao. New Design of Redactable Consortium Blockchain Scheme Based on Multi-user Chameleon Hash [J]. Computer Science, 2024, 51(6A): 230600004-6.
[5] CHEN Chao, YAN Wenjie, XUE Guixiang. Parameterized Quantum Circuits Based Quantum Neural Networks for Data Classification [J]. Computer Science, 2024, 51(11A): 231200112-7.
[6] Renata WONG. Application of Early Quantum Algorithms in Quantum Communication,Error Correction and Other Fields [J]. Computer Science, 2022, 49(6A): 645-648.
[7] LIU Xiao-nan, SONG Hui-chao, WANG Hong, JIANG Duo, AN Jia-le. Survey on Improvement and Application of Grover Algorithm [J]. Computer Science, 2021, 48(10): 315-323.
[8] LIU Shuai, CHEN Jian-hua. Certificateless Signature Scheme Without Bilinear Pairings and Its Application in Distribution Network [J]. Computer Science, 2020, 47(9): 304-310.
[9] Renata WONG. Uncertainty Principle as Related to Quantum Computation [J]. Computer Science, 2020, 47(1): 40-50.
[10] LIU Qing-hua,SONG Yu-qing and LIU Yi. Efficient Content Extraction Signature Scheme without Certification [J]. Computer Science, 2013, 40(8): 136-139.
[11] . Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Z DNA-based Computing [J]. Computer Science, 2012, 39(4): 232-235.
[12] CUI Guo-Hua ZHENG Ming-Hui SU Li （School of Computer Science, Huazhong University of Science ＆ Technology, Wuhan 430074）. [J]. Computer Science, 2008, 35(1): 77-79.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.