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.
We study exact evaluation of the arithmetized
k-Orthogonal Vectors polynomial
FOVk of Ball et al. (2017, 2018). For every fixed integer
k≥3, set
d(n)=⌈log2n⌉. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant
ε>0, no uniform quantum algorithm runs in
O(nk/2−ε) time on every input and evaluates this polynomial correctly with probability at least
3/4 over a uniformly random input in
Fp(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
nk−1 and when it is the smallest prime greater than
nk. 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.
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.
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.