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 :)
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 :)