The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulo
pand order
q. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs of
pand
qup to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by [Ekerå, arXiv:1905.09084 (2019)]. As a result, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of order
q, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs of
pand
q, extrapolated the circuit sizes obtained, and compared them for
p=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if
pis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of
pin the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group with
p=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group with
p=1024bits.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree
−d polynomial, using circuits with logarithmic depth in the number
n of qubits and only
O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only
n terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state
∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using
14 qubits and more than
500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.
The Discrete Fourier Transform (DFT) is central to the analysis of uniformly sampled signals, yet many practical applications involve non-uniform sampling, requiring the Non-Uniform Discrete Fourier Transform (NUDFT). While quantum algorithms for the standard DFT are well established, a corresponding framework for the non-uniform case remains underdeveloped. This work introduces a quantum algorithm for the Non-Uniform Quantum Fourier Transform (NUQFT) based on a low-rank factorization of the NUDFT matrix. The factorization is translated into an explicit quantum construction using block encodings, Quantum Signal Processing, and the Linear Combination of Unitaries framework, yielding an
ε-accurate block encoding of the NUDFT matrix with controlled approximation error from both classical truncation and quantum implementation. Under standard oracle access assumptions for non-uniform sampling points, we derive explicit, non-asymptotic gate-level resource estimates. The resulting complexity scales polylogarithmically with target precision, quadratically with the number of qubits through the quantum Fourier transform, and logarithmically with a geometry-dependent conditioning parameter induced by the non-uniform grid. This establishes a concrete and resource-efficient quantum analogue of the NUDFT and provides a foundation for quantum algorithms on irregularly sampled data.
By applying multiple Fourier transform and variable transform,aquantum algorithm for discrete logarithm problem over ZNis presented.The relationship between order r and success probability is quantitatively characterized,where r is the order of the selective element.Particularly, when r is a prime number,the success probability is close to 1and the scale of elementary quantum gates is O(L3),where L=[log N]+1.The new algorithm doesn't need to perform inverse quantum Fourier transform on|f(x1,x2)〉,which is superior to the existing algorithm.
Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of
O(nlog2(n)) O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of
O(nlog(n)) O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.