Quantum ComputingAlgorithms

Shor's Algorithm

Overview

Direct Answer

Shor's Algorithm is a polynomial-time quantum algorithm for factorising large composite integers, published by Peter Shor in 1994. It achieves exponential speedup over classical algorithms such as the general number field sieve, reducing the computational complexity from sub-exponential to polynomial time.

How It Works

The algorithm leverages quantum superposition and entanglement to identify the period of a modular exponential function. It uses the quantum Fourier transform to extract periodicity information from a superposed state, then applies classical post-processing to derive factors from the discovered period. The period-finding subroutine—the quantum core—runs in polynomial time, whereas classical period-finding requires exponential evaluation.

Why It Matters

The algorithm poses a theoretical threat to RSA and elliptic-curve cryptography, which underpin financial transactions, secure communications, and digital signatures across enterprises. This cryptographic vulnerability has driven urgent investment in post-quantum cryptography standards and quantum-resistant key exchange protocols by organisations including NIST and industry security leaders.

Common Applications

Potential applications include breaking RSA encryption used in legacy banking infrastructure and compromising TLS certificates in transit. Academic research focuses on factorising benchmarks; no practical large-scale cryptanalytic deployment exists due to quantum hardware immaturity.

Key Considerations

Implementation requires fault-tolerant quantum computers with thousands of logical qubits; current quantum processors lack the stability and scale necessary for cryptographically relevant integer sizes. The algorithm's theoretical power remains unrealised in practice, making near-term impact unlikely despite long-term strategic risk.

Cross-References(1)

Quantum Computing
Quantum Algorithm

More in Quantum Computing

Quantum Computing

Fundamentals

A computing paradigm that uses quantum mechanical phenomena like superposition and entanglement to process information exponentially faster for certain problems.

Quantum Cloud Computing

Fundamentals

Accessing quantum computing resources remotely through cloud-based platforms and APIs.

Quantum Machine Learning

Applications

The intersection of quantum computing and machine learning, using quantum systems to enhance learning algorithms.

Quantum Tunnelling

Fundamentals

A quantum phenomenon where particles pass through energy barriers that would be impossible to overcome classically.

Quantum Teleportation

Fundamentals

The transfer of quantum states between qubits using entanglement and classical communication.

Bloch Sphere

Fundamentals

A geometrical representation of the state space of a single qubit as a point on the surface of a sphere.

Quantum Error Correction

Fundamentals

Techniques for protecting quantum information from errors due to decoherence and other quantum noise sources.

Quantum Random Number Generator

Fundamentals

A device that generates truly random numbers using quantum mechanical processes.