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).
Remember this
Shor's algorithm's ability to factor integers in polynomial time on a quantum computer has profound implications for cryptography and computational efficiency.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
Randomized algorithm
Randomized algorithms use random bits for expected polynomial time
Computational complexity of matrix multiplication
O(n³) naive matrix multiplication
Matrix multiplication algorithm
Ever wondered how computers speed up multiplying huge numbers?
QR decomposition
QR decomposition factors A = QR
tensor cores are
Why can computers crunch numbers faster than humans?
Quantum computing
Quantum computers can solve certain problems exponentially faster than classical computers
Swipe through 100 ML concepts daily
Open Pocket Polymath