Please use this identifier to cite or link to this item:
Authors: Barzen, Johanna
Leymann, Frank
Title: Continued fractions and probability estimations in Shor’s algorithm : a detailed and self-contained treatise
Issue Date: 2022 Zeitschriftenartikel 393-432 AppliedMath 2 (2022), S. 393-432
ISSN: 2673-9909
Abstract: 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.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
appliedmath-02-00023-v2.pdf7,66 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons