Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0311134

Quantum Computing Discrete Logarithms with the Help of a Preprocessed State

Wim van Dam

Published Nov 20, 2003• 3 citations
arXivHTMLPDF

Abstract

An alternative quantum algorithm for the discrete logarithm problem is presented. The algorithm uses two quantum registers and two Fourier transforms whereas Shor's algorithm requires three registers and four Fourier transforms. A crucial ingredient of the algorithm is a quantum state that needs to be constructed before we can perform the computation. After one copy of this state is created, the algorithm can be executed arbitrarily many times.

DOI
10.48550/arxiv.quant-ph/0311134

Related papers

Quantum Fourier transform

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum Fourier transform, which is an essential quantum algorithmic primitive that efficiently applies a discrete Fourier transform to the amplitudes of a quantum state. It features prominently in quantum phase estimation and Shor’s algorithm for factoring and computing discrete logarithms.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Distributed Quantum Discrete Logarithm Algorithm

Renjie Xu, Daowen Qiu, Ligang Xiao +2 more

Solving the discrete logarithm problem (DLP) with quantum computers is a fundamental task with important implications. Beyond Shor's algorithm, many researchers have proposed alternative solutions in recent years. However, due to current hardware limitations, the scale of DLP instances that can be addressed by quantum computers remains insufficient. To overcome this limitation, we propose a distributed quantum discrete logarithm algorithm that reduces the required quantum register size for solving DLPs. Specifically, we design a distributed quantum algorithm to determine whether the solution is contained in a given set. Based on this procedure, our method solves DLPs by identifying the intersection of sets containing the solution. Compared with Shor's original algorithm, our approach reduces the register size and can improve the success probability, while requiring no quantum communication.

quant-pharXiv:2603.26160•Mar 30, 2026•0 citations

Variational Quantum Algorithm for Solving Discrete Logarithms

RONG Xiaojun ZHANG Xinglan

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.

•Jan 1, 2026•0 citations

EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS

Michele Mosca, Christof Zalka

We show how the Quantum Fast Fourier Transform (QFFT) can be made exact for arbitrary orders (first showing it for large primes). Most quantum algorithms only need a good approximation of the quantum Fourier transform of order 2n to succeed with high probability, and this QFFT can in fact be done exactly. Kitaev1 showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as "amplitude amplification". Although unlikely to be of any practical use, this construction allows one to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that "quantum" need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely, the parameters of the gates can be approximated efficiently.

arXiv:quant-ph/0301093•International Journal of Quantum Information•Mar 1, 2004•65 citations

Quantum factoring, discrete logarithms, and the hidden subgroup problem

Richard Jozsa

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. This article reviews the essential ingredients of these algorithms and draws out the unifying generalization of the so-called hidden subgroup problem.

arXiv:quant-ph/0012084•Computing in Science & Engineering•Jan 1, 2001•121 citations

Quantum computation of discrete logarithms in semigroups

Andrew M. Childs, Gábor Ivanyos

Abstract We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and the discrete logarithm problem as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete logarithm problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete logarithm problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to k ≥ 2 generators in a black-box abelian semigroup of order N requires Θ ˜ ( N 1 2 - 1 2 k ) $\tilde{\Theta }(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries.

arXiv:1310.6238•Journal of Mathematical Cryptology•Jul 8, 2014•32 citations
An alternative quantum algorithm for the discrete logarithm problem is presented. The algorithm uses two quantum registers and two Fourier transforms whereas Shor's algorithm requires three registers and four Fourier transforms. A crucial ingredient of the algorithm is a quantum state that needs to be constructed before we can perform the computation. After one copy of this state is created, the algorithm can be executed arbitrarily many times.
Solving the discrete logarithm problem (DLP) with quantum computers is a fundamental task with important implications. Beyond Shor's algorithm, many researchers have proposed alternative solutions in recent years. However, due to current hardware limitations, the scale of DLP instances that can be addressed by quantum computers remains insufficient. To overcome this limitation, we propose a distributed quantum discrete logarithm algorithm that reduces the required quantum register size for solving DLPs. Specifically, we design a distributed quantum algorithm to determine whether the solution is contained in a given set. Based on this procedure, our method solves DLPs by identifying the intersection of sets containing the solution. Compared with Shor's original algorithm, our approach reduces the register size and can improve the success probability, while requiring no quantum communication.
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.
We show how the Quantum Fast Fourier Transform (QFFT) can be made exact for arbitrary orders (first showing it for large primes). Most quantum algorithms only need a good approximation of the quantum Fourier transform of order 2n to succeed with high probability, and this QFFT can in fact be done exactly. Kitaev1 showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as "amplitude amplification". Although unlikely to be of any practical use, this construction allows one to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that "quantum" need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely, the parameters of the gates can be approximated efficiently.
Abstract We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and the discrete logarithm problem as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete logarithm problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete logarithm problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to k ≥ 2 generators in a black-box abelian semigroup of order N requires Θ ˜ ( N 1 2 - 1 2 k ) Θ~(N12−12k)\tilde{\Theta }(N^{\frac{1}{2}-\frac{1}{2k}})Θ~(N21​−2k1​) quantum queries.