Shor's algorithm factors integers in polynomial time on a quantum computer
Image: Public domain, via Wikimedia Commons
Shor's algorithm
Shor's algorithm factors integers in polynomial time on a quantum computer
Shor's algorithm, developed by Peter Shor in 1994, is a quantum algorithm that can factor integers efficiently. It runs in polynomial time relative to the logarithm of the integer, which means the time taken is polynomial in log(N).
Shor's algorithm has the potential to outperform classical algorithms for factoring, which is a significant computational problem with applications in cryptography. This superpolynomial speedup could revolutionize fields that rely on integer factorization.
The algorithm addresses problems like factoring, discrete logarithms, and period-finding, all instances of the hidden subgroup problem. These related problems highlight the versatility and power of Shor's algorithm in quantum computing.
Example
To factor the integer N = 15 using Shor's algorithm, the quantum computer would run in polynomial time related to log(15).
Shor's algorithm's ability to factor integers in polynomial time on a quantum computer has profound implications for cryptography and computational efficiency.
Related concepts
Randomized algorithm
Randomized algorithms use random bits for expected polynomial time
Computational complexity of matrix multiplication
O(n³) naive matrix multiplication
QR decomposition
QR decomposition factors A = QR, where Q is orthogonal, R is upper triangular
Quantum computing
Quantum computers can solve certain problems exponentially faster than classical computers
quantization to INT8 doubles throughput
Quantization to INT8 doubles throughput because tensor cores process INT8 2x faster
Quantum logic gate
Hadamard gate puts a qubit into equal superposition of |0⟩ and |1⟩
One email a day: 5 concepts + the 5 stories that matter →
Swipe through 100 ML concepts daily
Open TickerNews