Short··0:40·Mathematical physics
Quantum Factoring: How Often Does Shor's Algorithm Win?
Watch on YouTubeAbout the problem →
About this video
Multiplying two primes is easy. Undoing it is hard. Can a quantum computer factor any number, every single time?
Hop by powers of 7 around a 15-hour clock and the pattern loops every 4 steps. That loop length cracks 15 into 3 × 5. For 2021 = 43 × 47 the loop in the animation is 322 steps, and for real encryption keys it is far too long to walk. Shor's algorithm (1994) finds the loop with interfering quantum waves, but every run is a gamble: sometimes it fails and you run it again.
OpenAI says its AI has found a way to make the odds exactly 1 in 4, and then two reflections turn that into a sure thing: a circuit that factors every number with probability one, using a fixed set of gates. This is OpenAI's claim and has not yet been peer reviewed. The animation illustrates the idea; it is not the proof.
Paper (OpenAI's manuscript): github.com/openai/math/blob/main/preprints/Exact-quantum-fact…
Gradient Damage: mathematics you can see, equations you can hear.
Visual maths, 3D animation and sound experiments.
youtube.com/@gradientdamage
About the problem
Mathematical physics·OpenAI Math·Result 279
Exact quantum factoring over a fixed finite gate set
Gives a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer with probability one. Both gate count and qubit count are polynomial in the input length, and one fixed finite gate set suffices. (Lean)
Topics
quantum factoringShor's algorithmquantum computinginteger factorizationRSA encryptionperiod findingamplitude amplificationexact quantum algorithmquantum algorithmOpenAI mathAI proofAI solves math problemmaths shortsGradient Damage
