English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

These are pedagogical notes on Shor's factoring algorithm, which is a quantumalgorithm for factoring very large numbers (of order of hundreds to thousandsof bits) in polynomial time. In contrast, all known classical algorithms forthe factoring problem take an exponential time to factor large numbers. Inthese notes, we assume no prior knowledge of Shor's algorithm beyond a basicfamiliarity with the circuit model of quantum computing. The literature isthick with derivations and expositions of Shor's algorithm, but most of themseem to be lacking in essential details, and none of them provide a pedagogicalpresentation. We develop the theory of modular exponentiation (ME) operators insome detail, one of the fundamental components of Shor's algorithm, and theplace where most of the quantum resources are deployed. We also discuss thepost-quantum processing and the method of continued fractions, which is used toextract the exact period of the modular exponential function from theapproximately measured phase angles of the ME operator. The manuscript thenmoves on to a series of examples. We first verify the formalism by factoringN=15, the smallest number accessible to Shor's algorithm. We then proceed tofactor larger numbers, developing a systematic procedure that will find the MEoperators for any semi-prime $N = p \times q$ (where $q$ and~$p$ are prime).Finally, we factor the numbers N=21, 33, 35, 143, 247 using the Qiskitsimulator. It is observed that the ME operators are somewhat forgiving, andtruncated approximate forms are able to extract factors just as well as theexact operators. This is because the method of continued fractions onlyrequires an approximate phase value for its input, which suggests thatimplementing Shor's algorithm might not be as difficult as first suspected.

Shor's Factoring Algorithm and Modular Exponentiation Operators