Revision #656 → #1563 · back to history
addedShor's algorithm9cdbcd18bb4b
addedPolynomial-time factoring on a quantum computerab327a8c2bc5
addedInteger factorization is in BQPbd0fe6294bb2
addedAsymptotically faster than the number field sievea4f1544ce9c4
addedBreaking RSA via factoring3be39dc8f78b
addedNo classical polynomial factoring algorithm known2bcf38c87157
addedPolynomial-complexity factoring circuit02898515e4de
addedIBM 2001 NMR factorization of 15f3da5d58be03
added2012 solid-state qubit factorization21b54045b8bd
addedLater 2012 factorization7a342d334b5f
added2016 trapped-ion factorization0bb48cc47f8a
addedFactoring problema43244e0ae39
addedReduction to factoring into two integers00108078b4d0
addedEfficient GCD via Euclid's algorithm63278dd4bc9e
addedMultiplicative order33780fd58e50
addedDifference-of-squares factoringf8b1e43a71a6
addedShor's algorithm (restated steps)1e62b90d1ab4
addedSuccess after a few runs271cddeb0949
addedOrder-finding problem1a9486b59b78
addedSufficient register size for accuracy72ccddd47135
addedQuantum phase estimation behavior9d33c91859fc
addedEigenvalues are roots of unity2815969a0b46
addedEigenvectors of the multiplication gate0c49e18e660d
addedPhase estimation returns the integer with high probability15cc16445500
addedContinued-fraction extraction of the period85f25ac13343
addedLCM recovers the order5565b3596ffd
addedRegister size sufficient to recover the period4c38e3a35a8b
addedContinued-fraction recovery theorem2dfd33403d6e
addedModular exponentiation is the bottleneck0e5b67f42482
addedGate count of reversible circuits5622c82d9d9d
addedInstances of the period-finding problem249e4f4c17d5
addedAll three are hidden subgroup problems8ef55f04f5fb
addedDiscrete logarithm probleme303034723a0
addedDiscrete log as abelian hidden subgroup problem9de6bbe6db1f
addedOrder-finding as hidden subgroup probleme0a6bd750f27
addedQuantum HSP algorithm for finite abelian groups869a57192fe7