Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-14144
Authors: Barzen, Johanna
Leymann, Frank
Title: Continued fractions and probability estimations in Shor’s algorithm : a detailed and self-contained treatise
Issue Date: 2022
metadata.ubs.publikation.typ: Zeitschriftenartikel
metadata.ubs.publikation.seiten: 393-432
metadata.ubs.publikation.source: AppliedMath 2 (2022), S. 393-432
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-141634
http://elib.uni-stuttgart.de/handle/11682/14163
http://dx.doi.org/10.18419/opus-14144
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