Quantum Computing

Advanced

Shor's Factoring Complexity

Time complexity for Shor's algorithm to factor an integer N on a quantum computer.

Formula

O((\log N)^3)

Variables

NInteger to factorise

Example

RSA-2048: classical ≈ 10³⁰ ops; Shor's ≈ 10⁹ ops

Did You Know?

Shor's algorithm is the reason the world is racing to develop post-quantum cryptography before large-scale quantum computers arrive.

quantum shor factoring algorithm cryptography

Share this formula

More in Quantum Computing

Qubit Superposition State

General state of a single qubit as a superposition of the computational basis states.

Normalisation Constraint

The squared amplitudes of a qubit must sum to 1, ensuring total probability is 100 %.

Hadamard Gate

Puts a qubit into an equal superposition — the most common single-qubit gate.

Pauli-X Gate (Quantum NOT)

Flips |0⟩ to |1⟩ and vice versa — the quantum equivalent of a classical NOT gate.

CNOT Gate

Two-qubit gate that flips the target qubit only when the control qubit is |1⟩.

Bell State (EPR Pair)

Maximally entangled two-qubit state — measuring one qubit instantly determines the other.