Re:Breaking RSA Security with a Low Noise D-Wave 2000Q Quant...
by nightcracker on Thursday May 07, 2020 @10:31AM
(#23103357)
> To go from the 17bit to the 2018 bit they need to use a million qbits instead of 1600-something. That's a tiny scale up of under 1000x.
What makes you think that the time, energy and space costs of keeping n qubits coherent and executing a circuit on them is linear in n? No one has ever done it.
Re:Breaking RSA Security with a Low Noise D-Wave 2000Q Quant...
by alkonaut on Thursday May 07, 2020 @12:36PM
(#23104918)
I have no idea - but the whole point of the endeavor is (presumably) that it at least scales better than a classical CPU. The goal of the research was hardly to achieve what can be done on a smartphone in one second.
Re:Breaking RSA Security with a Low Noise D-Wave 2000Q Quant...
by dvdkhlng on Thursday May 07, 2020 @12:23PM
(#23104753)
Yes the number of Qubits used to represent the problem scales polynomially with the bit-length of the input integers.
However, annealing here is used as an approximation of a brute-force search. If you demand a sufficiently exact (i.e. non-approximate) result, run-time is still going to grow exponentially with problem-size, thus for 2048-bit numbers the D-Wave machine will maybe not finish by the time the universe ends :)
To go from the 17bit to the 2018 bit they need to use a million qbits instead of 1600-something. That's a tiny scale up of under 1000x.
To factor a 1024 bit number you need a huge set of resources, and instead of needing "a million CPUs" for the 2048 bit numbers, what you need is a million times more resources for the 2048bit number, than you needed for the 1024bit number.
It's not like academic results are unimportant until they are actually faster than classical results.