Factoring the largest number ever with a quantum computer

Ever since Shor's great discovery, quantum computers have been factoring larger and larger numbers. In 2001, the number 15 was factored using 8 qubits. This record was tied, but not beaten, until 2012 when the number 21 was factored using 10 qubits. And frankly this is where the story would end... if humans weren't quite so clever. Instead of waiting for the hardware to improve by yet further orders of magnitude, researchers began inventing better and better tricks for factoring numbers by exploiting their hidden structure.

In 2012, the very same year 21 was factored for the first time, 143 was factored. Even more amazingly, it was done with four qubits. That's fewer qubits! This was done by exploiting special structure in the number 143 to precompile the quantum part of the factoring problem down into something smaller and easier to manage. Then, in 2014, another huge breakthrough was made. There were numbers larger than 143 whose factoring problem precompiled down into the same quantum part as 143's factoring problem . It turned out that 2012 factoring of 143 was actually the 2012 factoring of 56153! Truly amazing.

I have to apologize for so quickly glossing over the rich history here. Suffice it to say that quantum factoring records have improved by what can only be described as an unbelievable amount. For example, at the 2020 Q2B conference, it was announced that the number 1099551473989 had been factored by precompiling down into a mere three qubits.

But. If you have your ear close to the quantum literature. If you seek out the whispers and the rumors. You may have heard legends of a technique for performing even better precompilation of factoring problems. I am here to tell you that the legends are true. Lost to time in the arXives, never published in a "real" journal, the Smolin-Smith-Vargo algorithm allows the truly audacious to harness unbounded factoring power... given the right insight into the true meaning of a number. Undeterred, I read forward...

And I am very happy to report here, on this very special day, that I was able to use a quantum computer and the Smolin-Smith-Vargo algorithm to factor a six thousand and twenty one digit number. Specifically, the number 291671182797429668031238852475522871688313947376048780905692029718761486852448217934002726713911166371797065789926861358001038309926791823037153309607038344386466504630862009885095835374063388681538740854573756984763365675961063107294541261056948126756713500082876897290806829519212252073625252903729164826939229937268358140359202760839878449283619825089409830663201790231806113418933698237614035166685973079119897925442388701635424676834454449169557409382254448047969411210843240836003242949956725155766531591501052942229421052655724666691397325634102511082189598034323906385311764688954392262917740666322904413249593651934711799245497736039481691942701018295648453789321098750101433275466592091275240471562574012639325274407937359939565997644744888626879352338627750927370817686889119416920350171901664469059271715608250848461172910192500124917913043084723760200336962254544736449976934826280451094033729173560884921189268528720501371851378561058188062023747243058214445802044477784468173990115494661065349334804292667033611703095306299887840788681802817090510453782255122176191217417814282138915069422701432482750933666279646514052254545839838715655752643620706192459952534043354084759044210585983336014538522931062740942515415079304899622236020309293036917120046158647471446922111430611051173311410550623233573244601694248544942615709333777616055028688928446398537179695288793510324635760076663279396564078367435242103498981445692558198809741901893058020211871952800513502065964655101452418248881764403773514215233151043167333359083190619294450557291339258651465910715914216791319911970044522155669518504517232288041363059136259094983407458375502383286163265233896123108795520636876488919869043697803547259539747873851072598407937923063218591110872328232238321140171385132205311770789280329860608594577714257317868270399096227182855167303553935052868995459591650385336377803042422853065481639618250097532955889761521091916881160108973576741687506504928708481015771024513106052679760752953335994452685752571524010889188855292134072196648709023888502399907186263270398930579644463527329155302416455167735601326232034586362597963268928664081788801456524003821683565503330431101730267869585370352143455420773361502648167179815130162479547215804270738259975418409318241262631572810255439301376988598081646350115947243309399130076505682455023838703680414534592637547594063538536874774558232334209018900585114224246666010598633697975151008780563978594746107730415174106118082092193466548051994311811556316244195693739250245197404025486611279670387828237102520106899304223957323511178848684801733032329576450052397141086062710820646635559717986354779769104254700368849278323331582232851830419987599043253727899529247902827559707615608104096353724721669864028916109266665493363128468922733083829871892871854559610881319195149728774427239301516121565406571703650646031077937841521038796655197020571602953550481648581133254568066497818991525368074064879636295858981536809944594432934861658997706168350104556565691587005874469526027836016177522657920774760854286309928960827240756330896317054700702812314008864980935450364313372550998442732470502088425915565739939988807264902322927119425761458365054624614149990555398366173104475363361177216916351633961409600561303872559487012972039610994034160578234626153165954484224573863382032435827372746454973165233785427764297454730442581096508416755679786238338349177340910373760981581439915740362476111629626645054391847771221190549981322755227596321478850960168351280923954278183933805451718535234286514607234242206985603686535990690711111326358313839255864586696411315965926251133481265048139263470154954590417017548195376147733836712111933279383984906913410781574912799816316130066217895794498685460845656365282707743778116281683433209653393713164497140184704421865461123131795498894932527378272085659816826730421859492184433810357750641659713593952066199723692348545832274859119719607524079963803946133926935865794790429998904795233770431685080837524713780739038193839037817735715802096377306096368331493071056852970795509954484975796736896127678218364251679942608763314341880798065413155435858596124222601709635954816295128935007000448659775298153401889818280673621531148964935427419791745240603650618265144062683973413259347974271011183578455665802243544663273030968313488838265538524014601364407432491549422851822890554691728589519611423291328675711436801782798188659680531717969167712532057716866912972439859343726476905957191089887550814050526594597238222532067396316519118004910367414171196504475590696957601071409239036415487756455722086296295452795200944511078455058164070249705470841174982185504817854768393128001792337176616940732234972115922761281961827747082779402656062088814404563373681300095430588519227467254856103004904687441102892193962990207098307465164137141389389455021645529320937924700920195037223430364892341951727519090504624510444513714150938785026801540983611808903307460374605841869013093951816660023798320509896992628509955304962788192272270400765390000311954687113536632813973210725523437609331272372080450728535880254716752760175325036540486657470931239524502552408754362403407840175498042316165890383821262310217327701306858572367635169163865036905514471505650508306686517841864656113148430696237358892826843616999850962910134523521264648521811833148370071032163829452492381580878568474126654585852046677346186982326514425124083042090383628289462952938972148369247174677918264255393324631735298241544392158510610718110362220314042118437263197620900434085217812272649321477286967632889342010979473623473720223936593925656760528117938117706475629621132905472289377844416667368678265970107446608874984968709986002499628402611999424406174134863733450443690231181428470625414819483082945694031940943959589970977465275380957993298342169846723361618695621858621172068934441178730030646811549032511117468478033713275791957484223997023131679545889826802822797888897004161307611947979344843012773462279886460781399143777110719326552407483120144464910648669699.

You're wondering how I managed to factor that monster. Well, this is the true beauty of the Smolin-Smith-Vargo algorithm. All I needed to do was run this humble little circuit:

0: ---H---@---H---M('out')---
          |
1: -------X------------------

That circuit may not look like much, but everything will be crystal clear after I tell you the magic number. The magic number is 55455317658905280202245347842333931908101347106319953838804752997378449819769787789885750684217286993567340880135365152567303938644008376461398562802127203732752209024208157012547203576945103585033012158444377380060992577848495892991730816767980424753799543702642468967411200474060887824099031758482538508237457932940109186085613800814951499776567033272957784867098613956635691034046917291781383764920178438493685748813250997776695324702300348810324053353647546079052013616566665757705765052811811737612340887625533911238739810749378481950128647456763507313513486661024175447171124559833317123689912461529583079557321919275784252328577016735691962874798565976747494236220253095432854250963853205651037140928694431688960830271846637710848267152904768074593052185931142262653891821522488834942740155086058949533384327567500377346128794964818573709027710243829880515192617721226769556092432561872163149477322287780465324841220919868219803381549016106318504743925806568171053725779298281508831410460192683030153307408903257062615141173780473598192137847001123813841602091518510191266626201986571740768391178119478817794238978997895667158427332169983382021790196924455205852697841169686535078421654888849239635660845022678476066766765529768351566272977217527875852815477564412766861141490165685114538389593898373641354036775512814604297705367292660115917204491431566056610330247457290190342300898982670091194010097950780215504453160090943019833947261942159205966892017873851651559516309649202661178033486217229888000791062474169860623174945145446704273143786092812788458380206799186805471901252476415747783414763173585853048567675542592918618850006238471343437364586325884812184096057253801128892010991827624852432218979643648445695100315447088300697200181368085238655202048220290604052578314948014552812174347299006162000537979414525703917692616599517926143308485460428883615749629219831768952677983787736855881360288716680132555491710788920596571589285418401709435132838427674027544913984693910547266201569171910662956569670923485199833609180723047539970698642759063250206034403963496068447034142192454930648856892423331604017601135910559809267209076295081983520758058399204087568338676313698661880333359689914218229708529930726866118284174651477198245676823481641308760135796623791758423981403798243014835793906874147998693215514135321905034983671431124763212319403340820520631488670620671663830136862506857524171840841336593379126511612493278089051361765254391050428382112833226113799527146221651088324761362298417004118821140886164422432836351225956218167881045515451286394217432523551447532836275031864136249742359200560764748832907322001811434497496297069932618562880964320020028807001280049939539905629297613363318354640806667402545764282443077110868429300906963317757056462159667100807148052694578292360415902868278237120936678550630228123771355563839479070565155150685854153070295660590151760163495032674143948731354037829479819621234947022575123514179905704132022607872796813150623096011059449614213951558548899321315141977323427799104927129521263487048486400296055479915828283044881365384669243398896162313628642735406062948333588082038600375306709992382463660904731088664479182986743720451604098350063705221848850853616026559954561184733253605336378880222036203480925394051636378618710768013922784093892701813980002144077957373746123728767997644621204707719637328028392090047003314680185286069992322668044257340144797130927822511864894023070800284202640462291025554336249837754774212962736346117255279943589999907735023741193825256882184542044813487007989712169006019212324686248982275821186031862482835693074494469282325646779343055207096805900459857386369127546455409596135898206052911717361041830187523325861253815620665703223390752281663845753346284615451124553123795782288680083053941674064112266059329836662748189027119642855386240869166378528013314955881041757899853415188454731736746408311529747843217324794782678711884323107413213851262790543633593791311952088552267485497221385267327454156761551226530594884192032547659978925779956728862369719268731989323276667561394845647946854411399010844134831166986728469063951004852737774217905157443852022880961465716591008340008373378614589077715906627964666721866275844454515901002832350220699166505405063979029192962749874937509642869317204794265187713808271743688236007562447992428452241332768188653435626092835782740960989956891156006230356514647192576057511585700926260700870024944944168152576931076315318746962195981024176476850839036664569102718532291032877509016781695607438289618593490895809499998627100789738433156720593844504970829725750608252071525455137806026111100899304149544330023737170038984234479269815559263519142550596447658124644849793698109120032427174550286067278569425457849482469819977591154461029148015532031315447002157605749578597979534402453862349916651627873018642601908058980272070951526810492761957013331268354049456934644004080967085316658111425678735249016012852541164547164589363061276294664261578822574174093232962849922804671641589931344046603614077529532733507351992904009849485268463142328068359620608745063072122385488037512729380635162622521475630873506077816634389559458062828882142475250509554691858088457816767478302588091437359788231145573110442490668646478553920807255390169645511701295896111455069105440711235233110237993645387421826127997861030029699505155671346851482266197794240337648148780339290908667615541167281090576134920097808508163937015875486263656484992603573667153783686501913900353138130482804712725075696317183137672327797576237994606117971245626916381858869311131877831252710519552641017920011587282342509502471056868044020384899682667695053173584830669049685446709620156280850901561991773490600953725032989674911728614173164715904108373691868635548173146335980358273932146852652781594790513189635991443741608677393783684078628308685042145643948450008665706096380612185209734486724736792331979702184243075703474696483044052775330047628190816484245192549879572167914248417992027480594604244323390983.

Oh... it's still not clear? Well, okay.

Shor's algorithm works by performing period finding. It just so happens that the magic number I listed, when raised to a power modulo the number I said I wanted to factor, oscillates between two different values. The modular exponentiation has period 2. This means that we can precompile the whole controlled modular exponentiation process in Shor's algorithm down into any single gate with a period of 2, such as a NOT gate, controlled by the least significant qubit of the exponent. All the other qubits in the exponent make period 2 contributions to the result, which are irrelevant and can be omitted. What you're left with after that precompilation is the tiny little circuit I listed.

Oh? How did I find the magic number? Uh...

Anyways, if you run that quantum circuit on a quantum computer, you will get one of two possible results: 0 or 1. Getting 0 is bad; it causes the denominator extraction part of Shor's algorithm to return a useless result. When dealing with larger periods, the chance of this happening is totally negligible. In our case... there's a 50/50 chance.

Undeterred, I went to a quantum computer that will remain unnamed. I loaded up my circuit. I ran the circuit one single time and it returned... 1! Complete success! I quickly fed this result into my Shor's algorithm post-processing code, which computed the correct period (namely 2), allowing it to compute a quadratic residue of the number to be factored, and after that the factors were no match.

Here are the factors that my code returned:

15344210911551879034154475615756648278710459723460883322390091291476358391050278291171331209082786845152973069513609280964675427823555770385688380667986386420207234220929797190144190306444163072205716416855773737259045123763054417994565954237771285914931584182054585084310527905433743307376754550379347631047384892235207511938592564571143815233517021788653294529493843381735886680867572066905745967472486422980865488312552358292973570937340344213297379708786586584566516153160056099076401092599629838895979158510116755371244889727799017541298227827911578685205564459899425940157424673302895849272154959505258352824096054187896504066642990647029949704492953468901489482069248864535126493105096157250571718912858630335350253125066302315596064294566641832738234399669601421944832232700273783368625178024777349712658431864229683085291099532113899564036385785958096843780202134387853953460688344264132220901183199796523244028209350642992730744932397145166677499698093002659814356951484582940404780420662556622346854864366985270990346308998389089741803082213709710653860719860675825712251452180634514171224829999607236951975464582484429179291064420810423921033981202161641204043506503604899667776094117035538346877455767455028912628518259203892985077185322836653239043071678187345523293594095714227275799459763995264855171969145502730887503822935984762466100663329502161975606668557141116137852004453534622943473068458546914423356563756384096456896596611218818671200401017620373225866487184738175324205378994648425493053785379984466070624462558779581656333349004741569347707874895977839572314982676512472215809477149705523382918759511288442162518278341253875014998047839554217280237152864715817486287969171664568867140712747183430008604624868739887669376265997357520983345554251770601048968085413068875133733319692911785892782431569580536379627191092033677236262365360733637042571724543361024791471493219329286946812790261472390723189407900022090292330394028618091700828496784010769625985163251126023210297504388315198588502673890888920564844512096368136784854917503873925660271126368315132532237619279321842934507837610175705433111164755139952777810513077632969561726071530974080839458403225674542315990108825282084004242279956424491522191764489773752960875740881334656453078058053509519091284413138385921206674154724298649922186464861595886616887910357676573958215861584760287255047334444654030792137613849542144613141628228535158375086464377825525352568936836525222099671633766950744890890939616477828300759874183701047766349180097314707660420446188110787549126254892374148598271527797957604060653908403369938836710131129258646160181621981564491029727538455635295646836982287625424301987199757072019771445825051760259939666710550993109649321084159574093695390805869514378398586979969653085272890158243913036819928416609225496480434465820327980554885822153826662852533819065002850588417017070794272207204753581958033406062612778556399422527035257640828755689084602832438731803165022066175219836798131943707977817177

and

19008548857852651843472107131567050202912913490211449314695610130141021811765358799994791107204877298960911220299073392580485173028261591572444805472010614413033556039906837636414550701249922902279567850906588882673004630831874387444576698843544094535826838336636254068816991385250337194041074148244453215165669012350349594863945869366600406153881365068498447053516913214402261561816497713849103876998648995370204212977861464949036150940310404392499240744605727311193602451844856278322396875974281339968407151353212714575367554734962654614521906720211996001897945406155111067502347891467743021361684009214893577371183286246881318795278044926654904150526799235406083559437892449692602882885584068820801164287284333497404976174954080335722748688959692573957705958144749229707608758811833583103775572145897172995721923284862708175679959675668972653992515865668222212710319805883622405746209394633695755483401057173038615777344654374117134878316772915313052311824425783290468247154401255007654138887086472066477007628361230938112256969291993865541299078549488369237617195075032722412762583993863556475715493928020768206985546411492056828655925858915906732486227993790263351851913345099136234550083953107672426303577738945589287228463879318800326433782081227297886439747883355457810524332248132716310119890491519968692296471322754791881171684768263143638078028474458219382740325013811402899323335471844197712387165576533698674603697168989709740388744477520010135307790504652108536265222706430560737693614054519029966760913572750244866716144199679889818901469998845281463805852624442831496513200220257253913341627317098288565643121668260782061965948407581714142603866616706050184293639018458434818763842852854823990471761838786110225675543810566369954528989907052372921494816971293349424175021291777561394181223151542420476962324954125226183822505556502000546491277560403914100788947694535262223998410165610191001251258864614102572411635737111916389972275768710293863523878184542216469086908434511764848966760959155994092961444324306312534551839408738370375184415123370114112476485775688955107328442739319947485187421006829752966103465995728174833443556999573882177096694974808602721610251496561463139708808980732482975317530757185657909450052452640752314077996944919211370999930023881598514366321712002220770900829092121788784703091515899519339042306197066702961960332971677992498355861675597593592116718966293134353888955843424723515037289007905951925391243104914166882335337377586958062328857058774805666831454724887742839317266967165931494136341229174415778403396187386562685323043190627795084683020003678359652302529477350562973476934783394667635715407319888008815599286200283928365530624605414315274342731760543211570528837494284426099138814160882728443021588708022473750910633812941196019105482904076825042221476174770887262439636737569650004608491955624146295669617494595749646325514451456933767542866592627891318559085120832199895219256179671869900371682585076429554333661959737177386387167297697644544108987

which you can check are correct.

Smolin, Smith, and Vargo were not able to get their hands on a quantum computer while writing their paper. They had to resort to flipping coins as a substitute. I can only hope that this blog post completes their work, cementing their rightful place in history.

View r/algassert comment thread