Quantum computing timelines

[Cross­post­ing from https://​​blog.jess­riedel.com/​​2020/​​09/​​15/​​quan­tum-com­put­ing-timelines/​​ ]

IN SHORT: We at­tempt to fore­cast when quan­tum com­put­ers will be able to crack the com­mon cryp­to­graphic scheme RSA2048, and de­velop a model that pre­dicts less than 5% con­fi­dence that this ca­pa­bil­ity will be reached be­fore 2039. You can read the full ar­ti­cle at https://​​arxiv.org/​​abs/​​2009.05045

Ad­vanced quan­tum com­put­ing comes with some new ap­pli­ca­tions as well as a few risks, most no­tably threat­en­ing the foun­da­tions of mod­ern on­line se­cu­rity.

In light of the re­cent ex­per­i­men­tal cross­ing of the “quan­tum supremacy” mile­stone, it is of great in­ter­est to es­ti­mate when de­vices ca­pa­ble of at­tack­ing typ­i­cal en­crypted com­mu­ni­ca­tion will be con­structed, and whether the de­vel­op­ment of com­mu­ni­ca­tion pro­to­cols that are se­cure against quan­tum com­put­ers is pro­gress­ing at an ad­e­quate pace.

Beyond its in­trin­sic in­ter­est, quan­tum com­put­ing is also fer­tile ground for quan­tified fore­cast­ing. Ex­er­cises on fore­cast­ing tech­nolog­i­cal progress have gen­er­ally been sparse — with some no­table ex­cep­tions — but it is of great im­por­tance: tech­nolog­i­cal progress dic­tates a large part of hu­man progress.

To date, most sys­tem­atic pre­dic­tions about de­vel­op­ment timelines for quan­tum com­put­ing have been based on ex­pert sur­veys, in part be­cause quan­ti­ta­tive data about re­al­is­tic ar­chi­tec­tures has been limited to a small num­ber of idiosyn­cratic pro­to­types. How­ever, in the last few years the num­ber of de­vice has been rapidly in­creas­ing and it is now pos­si­ble to squint through the fog of re­search and make some ten­ta­tive ex­trap­o­la­tions. We em­pha­size that our quan­ti­ta­tive model should be con­sid­ered to at most aug­ment, not re­place, ex­pert pre­dic­tions. In­deed, as we dis­cuss in our preprint, this early data is noisy, and we nec­es­sar­ily must make strong as­sump­tions to say any­thing con­crete.

Our first step was to com­pile an im­perfect dataset of quan­tum com­put­ing de­vices de­vel­oped so far, span­ning 2003-2020. This dataset is freely available, and we en­courage oth­ers to build on it in the fu­ture as the data con­tinues to roll in.

To quan­tify progress, we de­vel­oped our own in­dex—the gen­er­al­ized log­i­cal qubit—that com­bines two im­por­tant met­rics of perfor­mance for quan­tum com­put­ers: the num­ber of phys­i­cal qubits and the er­ror rate for two-qubit gates. Roughly speak­ing, the gen­er­al­ized log­i­cal qubit is the num­ber of noise­less qubits that could be simu­lated with quan­tum er­ror cor­rec­tion us­ing a given num­ber of phys­i­cal qubits with a given gate er­ror. Im­por­tantly, the met­ric can be ex­tended to frac­tional val­ues, al­low­ing us to con­sider con­tem­po­rary sys­tems that are un­able to simu­late even a sin­gle qubit noise­lessly.

To fore­cast his­tor­i­cal progress into the fu­ture, we fo­cus on su­per­con­duct­ing-qubit de­vices. We make our key as­sump­tion of ex­po­nen­tial progress on the two main met­rics and use statis­ti­cal boot­strap­ping to build con­fi­dence in­ter­vals around when our in­dex met­ric will cross the fron­tier where it will be able to threaten the pop­u­lar cryp­to­graphic pro­to­col RSA 2048.

Note that since we are mod­el­ling progress on each met­ric sep­a­rately we are ig­nor­ing the in­ter­play be­tween the two met­rics. But a sim­ple statis­ti­cal check shows that the met­rics are likely nega­tively cor­re­lated within each sys­tem—that is, quan­tum com­puter de­sign­ers face a trade off be­tween in­creas­ing the num­ber of qubits and the gate qual­ity. Ig­nor­ing this cou­pling be­tween the met­rics re­sults in an op­ti­mistic model.

Our main re­sult: the 5%, me­dian and 95% con­fi­dence ex­trap­o­la­tion for the gen­er­al­ized log­i­cal qubit met­ric us­ing a boot­strap­ping pro­ce­dure. The 4100 thresh­old is where we es­ti­mate quan­tum com­put­ing will be able to solve the pop­u­lar cryp­to­graphic scheme RSA-2048. Past recorded val­ues of the met­ric are shown as pur­ple icons on the graph.

As a point of com­par­i­son, last year Pi­ani and Mosca sur­veyed quan­tum com­put­ing ex­perts and found that 22.7% think it is likely or highly likely that quan­tum com­put­ers will be able to crack RSA-2048 keys by 2030, and 50% think that is likely or highly likely that we will be able to crack RSA-2048 keys by 2035.

Will this be enough time to de­ploy ad­e­quate coun­ter­mea­sures? I dis­cuss this in depth in this other ar­ti­cle about quan­tum crypt­anal­y­sis. Given the cur­rent rate of progress on the stan­dard­iza­tion of quan­tum-re­sis­tant cryp­tog­ra­phy there seems to be lit­tle rea­son for con­cern (though it should be con­sid­ered that the yearly base rate for dis­con­tin­u­ous break­throughs for any given tech­nol­ogy is about 0.1%).

A plau­si­ble timeline of de­vel­op­ment and de­ploy­ment of a quan­tum-re­sis­tant cryp­tog­ra­phy stan­dard, for illus­tra­tive pur­poses. Also shown a sum­mary of ex­pert pre­dic­tion on at­tack ca­pa­bil­ities. As com­par­i­son, our statis­ti­cal pre­dic­tion as­signs <5% con­fi­dence to hav­ing quan­tum com­put­ing hard­ware ca­pa­ble of break­ing RSA 2048 be­fore 2039. This figure origi­nally ap­peared on Assess­ing the im­pact of quan­tum crypt­anal­y­sis. The figure is based on an in­ter­view with the leader of NIST’s Cryp­to­graphic Tech­nol­ogy Group Lily Chen and ed­u­cated guess­work.

If you are in­ter­ested in bet­ter un­der­stand­ing our model and as­sump­tions, I en­courage you to check out our preprint on the arXiv.