Shor's algorithm

As explained in Quantum Programming in Depth

Shor's algorithm is a quantum algorithm for integer factorization with asymptotically better performance than the best known classical factorization algorithms.

Shor's algorithm is a quantum algorithm for integer factorization. Given a single number, it exploits the periodicity of a related function to find divisors, promising asymptotically better performance than the best known classical factorization algorithms. section 1.2 section 1.3.1

Its potential advantage depends on several conditions:

• Targets a small-data, big-compute problem: the input may be one number, while discovering its divisors is computationally hard. section 1.2
• Exploits structure rather than treating the problem as unstructured search; specifically, it relies on periodicity in a function defined from the number being factored. section 1.2
• Requires practical implementation analysis in addition to abstract computational complexity, because implementation details can reduce the value of a theoretical speedup. section 1.3.1

Figure 1.1 Quantum advantage might be achievable if the time a quantum computer takes to solve a certain problem grows at a slower rate as the problem size increases than the time a classical computer takes to do the same. In this case, problem instances that are much larger than the crossover size might be good candidates for quantum solutions. If the crossover time is months or more, quantum computing offers no practical advantage, since larger problem instances take much longer to solve, and running a quantum computer for months or years to solve a single problem is not practical.

Compare quantum and classical growth rates using the crossover point: a slower quantum growth rate may matter only when instances exceed a practical crossover size. section 1.2

How Quantum Programming in Depth covers it

How deep it goes

Explains the factorization goal, periodicity, asymptotic promise, and practical caveat without deriving the algorithm or implementation.

Examples

Uses factoring a single number and finding its divisors as the concrete problem example.

What you can do after

Evaluate whether factorization has the structure and scaling needed to justify a quantum approach.

How it connects

Connects integer factorization to periodicity, quantum computing, quantum advantage, and classical algorithm comparisons.

liveBookmanning.com

Read Quantum Programming in Depth on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Real-World CryptographyShor's algorithm is a quantum algorithm that efficiently solves integer factorization and discrete logarithm problems.

Compare how 2 books explain Shor's algorithm →

Related concepts

• factorizationaddresses · Factorization is the decomposition of a mathematical object, such as an integer or joint distribution, into simpler multiplicative factors.
• discrete logarithmaddresses · A discrete logarithm is an exponent or scalar that relates a specified group element to a base or generator under the group operation.
• periodaddresses · A period is the interval or number of steps between successive repetitions of a function, process, sequence, pattern, or state.
• quantum algorithmkind of · A quantum algorithm is a computational procedure designed to run on a quantum computer and exploit quantum-mechanical states or operations.
• post-quantum cryptographycontrasts with · Post-quantum cryptography is cryptography designed to resist attacks by quantum computers while generally running on conventional computers.
• RSAcontrasts with · RSA is a public-key cryptosystem based on the computational difficulty of factoring large composite integers and supporting encryption and digital signatures.

This explainer was generated by Manning's knowledge graph from the text of Quantum Programming in Depth. The section links point to the parts of the book it draws on.