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:1208.1987

Shor's algorithm without partial fractions

Nolan R. Wallach

Published Aug 9, 2012• 0 citations
arXivHTMLPDF

Abstract

The purpose of this note was to give a proof that Shor's algorithm for period search is polynomial using only the standard $2^{n}$ quantum Fourier thansform and some simple trigonometry. There is an error that was pointed out to the author by Pavel Wocjan.

DOI
10.48550/arxiv.1208.1987

Related papers

An integral version of Shor's factoring algorithm

Felix M. Lev

We consider a version of Shor's quantum factoring algorithm such that the quantum Fourier transform is replaced by an extremely simple one where decomposition coefficients take only the values of $1,i,-1,-i$. In numerous calculations which have been carried out so far, our algorithm has been surprisingly stable and never failed. There are numerical indications that the probability of period finding given by the algorithm is a slowly decreasing function of the number to be factorized and is typically less than in Shor's algorithm. On the other hand, quantum computer (QC), capable of implementing our algorithm, will require a much less amount of resources and will be much less error-sensitive than standard QC. We also propose a modification of Coppersmith' Approximate Fast Fourier Transform. The numerical results show that the probability is signifacantly amplified even in the first post integral approximation. Our algorithm can be very useful at early stages of development of quantum computer.

arXiv:quant-ph/0109103•Sep 20, 2001•2 citations

A short note on Shor's factoring algorithm

Harry Buhrman

This note shows that Shor's algorithm for factoring in polynomial time on a quantum computer can be made to work with zero error probability.

ACM SIGACT News•Mar 1, 1996•8 citations

A Key Component of the Shor's Algorithm and Its Possible Quantum Implementations

Jiří Tomčala

A fundamental problem in factorization by Shor's algorithm [1] is the implementation of the modular exponentiation function. The period of this function is important for determining the individual factors, so its accurate implementation is for successful factorization critical.The imprecision of current quantum computers requires that any quantum circuits should be as simple as possible. Both in terms of the number of qubits used, the number of quantum gates and the depth of the quantum circuit. Therefore, it is necessary to search for an optimal variant for the implementation of the above-mentioned modular exponentiation function.The standard method is to implement individual arithmetic functions [2] which can be combined to achieve the desired modular exponentiation function. This process, however, creates a very complex quantum circuit, so that its measured result (probability distribution) will be so skewed that it will not be possible to reliably obtain the period of sought.Another way is to create a special quantum circuit for one particular modular exponentiation function [3]. Such a circuit is of course simpler than the circuit created by the above universal implementation, but in practice it only makes sense for testing the functionality of the surrounding quantum circuit for period detection.A very interesting possibility for the implementation of arithmetic functions is to use the direct and inverse quantum Fourier transform [4]. For a quantum computer, these transformations are very easy operations, and this interesting feature can then be used to advantage in these various implementations.This contribution will explore these possible approaches and show their advantages and disadvantages through concrete examples.

•Dec 17, 2025•0 citations

Continued Fractions and Probability Estimations in the Shor Algorithm -- A Detailed and Self-Contained Treatise

Johanna Barzen, Frank Leymann

The algorithm of Shor for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books) filling the gap to allow a complete comprehension of the algorithm of Shor. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.

arXiv:2205.01925•May 4, 2022•0 citations

Shor Factoring Algorithm and the Quantum Fourier Transform

Alice Flarend, Robert Hilborn

Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.

•Jul 9, 2026•0 citations

Continued Fractions and Probability Estimations in Shor’s Algorithm: A Detailed and Self-Contained Treatise

Johanna Barzen, Frank Leymann

Shor’s algorithm for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books), filling the gap to allow a complete comprehension of Shor’s algorithm. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.

AppliedMath•Jul 18, 2022•4 citations
The purpose of this note was to give a proof that Shor's algorithm for period search is polynomial using only the standard 2n2^{n}2n quantum Fourier thansform and some simple trigonometry. There is an error that was pointed out to the author by Pavel Wocjan.
We consider a version of Shor's quantum factoring algorithm such that the quantum Fourier transform is replaced by an extremely simple one where decomposition coefficients take only the values of 1,i,−1,−i1,i,-1,-i1,i,−1,−i. In numerous calculations which have been carried out so far, our algorithm has been surprisingly stable and never failed. There are numerical indications that the probability of period finding given by the algorithm is a slowly decreasing function of the number to be factorized and is typically less than in Shor's algorithm. On the other hand, quantum computer (QC), capable of implementing our algorithm, will require a much less amount of resources and will be much less error-sensitive than standard QC. We also propose a modification of Coppersmith' Approximate Fast Fourier Transform. The numerical results show that the probability is signifacantly amplified even in the first post integral approximation. Our algorithm can be very useful at early stages of development of quantum computer.
A fundamental problem in factorization by Shor's algorithm [1] is the implementation of the modular exponentiation function. The period of this function is important for determining the individual factors, so its accurate implementation is for successful factorization critical.The imprecision of current quantum computers requires that any quantum circuits should be as simple as possible. Both in terms of the number of qubits used, the number of quantum gates and the depth of the quantum circuit. Therefore, it is necessary to search for an optimal variant for the implementation of the above-mentioned modular exponentiation function.The standard method is to implement individual arithmetic functions [2] which can be combined to achieve the desired modular exponentiation function. This process, however, creates a very complex quantum circuit, so that its measured result (probability distribution) will be so skewed that it will not be possible to reliably obtain the period of sought.Another way is to create a special quantum circuit for one particular modular exponentiation function [3]. Such a circuit is of course simpler than the circuit created by the above universal implementation, but in practice it only makes sense for testing the functionality of the surrounding quantum circuit for period detection.A very interesting possibility for the implementation of arithmetic functions is to use the direct and inverse quantum Fourier transform [4]. For a quantum computer, these transformations are very easy operations, and this interesting feature can then be used to advantage in these various implementations.This contribution will explore these possible approaches and show their advantages and disadvantages through concrete examples.
The algorithm of Shor for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books) filling the gap to allow a complete comprehension of the algorithm of Shor. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.
Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.
Shor’s algorithm for prime factorization is a hybrid algorithm consisting of a quantum part and a classical part. The main focus of the classical part is a continued fraction analysis. The presentation of this is often short, pointing to text books on number theory. In this contribution, we present the relevant results and proofs from the theory of continued fractions in detail (even in more detail than in text books), filling the gap to allow a complete comprehension of Shor’s algorithm. Similarly, we provide a detailed computation of the estimation of the probability that convergents will provide the period required for determining a prime factor.