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

Exact discrete logarithms from a flagged polygonal transform

Myeongjin Kang

Published Oct 13, 2026• 0 citations
Publisher

Abstract

Assume the flagged polygonal-transform and exact-factoring interfaces specified in the paper. We construct a polynomial-time uniform quantum circuit family over one fixed finite gate set that computes discrete logarithms in prime fields with probability one and polynomial worst-case resources. For prime-order inputs, each verified Fourier-bin label has probability at least 1/(81q). Given its verified logarithm, that probability is computable exactly by a bounded number of lattice-point counts in dimension at most thirteen. Dyadic completion produces success probability exactly one quarter, followed by one exact amplification step. All sampled probabilities are dyadic; no input-dependent rotation or postselection is used.

DOI
10.5281/zenodo.23350040

Related papers

Exact quantum factoring over a fixed finite gate set

OpenAI

We give a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer N\ge2 with probability one. A fixed finite set of bounded-arity gates suffices, and both the gate count and the number of qubits have polynomial worst-case bounds in the input length.

•Oct 6, 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•75 citations

Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized $k$-Orthogonal Vectors

Dhruv Prasad Deshpande, Abhishek Mishra

We study exact evaluation of the arithmetized $k$-Orthogonal Vectors polynomial $FOV^k$ of Ball et al. (2017, 2018). For every fixed integer $k \geq 3$, set $d(n) = \left \lceil \log^2 n \right \rceil$. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant $\varepsilon > 0$, no uniform quantum algorithm runs in $O(n^{k/2 - \varepsilon})$ time on every input and evaluates this polynomial correctly with probability at least $3 / 4$ over a uniformly random input in $\mathbb F_{p(n)}^{knd(n)}$ and the algorithm's internal randomness, for all sufficiently large $n$. This holds when $p(n)$ is the smallest prime greater than $n^{k - 1}$ and when it is the smallest prime greater than $n^k$. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo $p(n)$; otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.

arXiv:2611.14411•Nov 10, 2026•0 citations

Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo $p$ and Order $q$

Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu +1 more

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$p$and order$q$. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs of$p$and$q$up 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$p$and$q$, extrapolated the circuit sizes obtained, and compared them for$p = 2048$bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if$p$is equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of$p$in 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 = 2048$bits under Shor's algorithm is almost equivalent to that of a safe-prime group with$p = 1024$bits.

arXiv:2503.23939•IEEE Transactions on Quantum Engineering•Jan 1, 2025•3 citations

Logarithmic-depth quantum state preparation of polynomials

Baptiste Claudon, Alexis Lucas, Jean-Philip Piquemal +2 more

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 $\mathcal 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\rangle$. 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.

quant-pharXiv:2603.16527•Mar 18, 2026•4 citations

Quantum Algorithm for Discrete Logarithm Over Z_N

Xiang Fu

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.

Chinese Journal of Computers•Jan 1, 2014•0 citations
Assume the flagged polygonal-transform and exact-factoring interfaces specified in the paper. We construct a polynomial-time uniform quantum circuit family over one fixed finite gate set that computes discrete logarithms in prime fields with probability one and polynomial worst-case resources. For prime-order inputs, each verified Fourier-bin label has probability at least 1/(81q). Given its verified logarithm, that probability is computable exactly by a bounded number of lattice-point counts in dimension at most thirteen. Dyadic completion produces success probability exactly one quarter, followed by one exact amplification step. All sampled probabilities are dyadic; no input-dependent rotation or postselection is used.
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.
Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized kkk-Orthogonal Vectors
We study exact evaluation of the arithmetized kkk-Orthogonal Vectors polynomial FOVkFOV^kFOVk of Ball et al. (2017, 2018). For every fixed integer k≥3k \geq 3k≥3, set d(n)=⌈log⁡2n⌉d(n) = \left \lceil \log^2 n \right \rceild(n)=⌈log2n⌉. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant ε>0\varepsilon > 0ε>0, no uniform quantum algorithm runs in O(nk/2−ε)O(n^{k/2 - \varepsilon})O(nk/2−ε) time on every input and evaluates this polynomial correctly with probability at least 3/43 / 43/4 over a uniformly random input in Fp(n)knd(n)\mathbb F_{p(n)}^{knd(n)}Fp(n)knd(n)​ and the algorithm's internal randomness, for all sufficiently large nnn. This holds when p(n)p(n)p(n) is the smallest prime greater than nk−1n^{k - 1}nk−1 and when it is the smallest prime greater than nkn^knk. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo p(n)p(n)p(n); otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.
Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo ppp and Order qqq
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 modulopppand orderqqq. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs ofpppandqqqup 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 orderqqq, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs ofpppandqqq, extrapolated the circuit sizes obtained, and compared them forp=2048p = 2048p=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same ifpppis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length ofpppin 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 withp=2048p = 2048p=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group withp=1024p = 1024p=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-d−d polynomial, using circuits with logarithmic depth in the number nnn of qubits and only O(n)\mathcal O(n)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 nnn 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⟩|1\rangle∣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 141414 qubits and more than 500500500 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.
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.