Shor's algorithm
Peter Shor's 1994 quantum algorithm that factors large numbers in roughly polynomial time, threatening modern encryption.
As defined in 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
Where it comes up · 5
- The Map of Quantum Computing - Quantum Computing Explained1 claim
- Dwarkesh Patel Podcast - Michael Nielsen – How science actually progresses1 claim
- AI and Quantum Computing: Glimpsing the Near Future | World Science Festival1 claim
- 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity1 claim
- David Deutsch: Knowledge Creation and The Human Race, Part 11 claim
Most important claims · 5 of 5Search all claims for “Shor's algorithm” →
- Quantum computing has proven highly useful for specialized mathematics via Shor's algorithm and other specific applications like quantum annealing, simulation of quantum systems, and drug discovery—these specialized use cases are arriving even before general quantum computers are available.AI and Quantum Computing: Glimpsing the Near Future | World Science Festival
- Today's quantum computers are not able to run Shor's algorithm on large numbers yet; the speaker has estimated they would need about a million qubits to do so, but so far the most advanced universal quantum computers have around 100 qubits.The Map of Quantum Computing - Quantum Computing Explained
- Many-Worlds (Everett) interpretation is the most straightforward interpretation of quantum physics; if you don't believe in Many-Worlds, you must explain how Shor's algorithm factors large numbers by pulling in the multiverse for computation.David Deutsch: Knowledge Creation and The Human Race, Part 1
- Peter Shor's 1994 algorithm showed that factoring an n-digit number, the basis of most modern encryption, lies in BQP — solvable on a quantum computer in roughly N-squared operations — versus the best known classical algorithm (the number field sieve) which takes time growing exponentially in roughly the cube root of N; this exploits special structure from group theory, number theory and the Fourier transform, not mere parallel-universe trial of every divisor.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- There may be an interesting transition with quantum computers because they are probably capable of a strictly larger class of potentially interesting computations than classical computers, so artificial general intelligence built on quantum machines (AQGI) might be qualitatively different — though after only ~40 years of thinking about it without the devices, it's unknown whether quantum advantage is narrow (like Shor's algorithm breaking encryption) or very broad.Dwarkesh Patel Podcast - Michael Nielsen – How science actually progresses