This is pretty impressive, they were able to factor a 17 bit number (103459 = 337 * 307) using 1635 physical qubits (arranged as 73 logical qubits) using QUBO. In this configuration they were able to achieve an average time to solution of just under 100ms.<p>That said, they did pick an 'easy' number to factor, just like most other quantum factorization results. This number could easily be factored using Fermat's factorization method (only the first step is required). It would have been very interesting to see a list of all primes and the time required to factor them (since they claim it only takes 100ms to factor the 17 bit one, such an experiment should be able to run in a day...).<p>For an extreeme case of this class of 'cheating' compare to the largest number factored on a quantum computer (1,099,551,473,989 =1,048,589 * 1,048,601) which only actually takes 3 qubits to calculate [1]<p>They also estimate that in order to factor a 2048bit number it would require just under a million logical qubits using QUBO, but didn't present a physical implementation. Worse yet, this is still not a general algorithm and is generally predicated on picking an easy number to factor in the first place!<p>[1]<a href="https://quantumcomputing.stackexchange.com/questions/9204/the-algorithm-of-the-new-quantum-factoring-record-1-099-551-473-989" rel="nofollow">https://quantumcomputing.stackexchange.com/questions/9204/th...</a>
Well, for those looking at the comments first:<p>No; they do not actually factor any 1024 or 2048 bit numbers. The largest is 17 bits. Although they point out that representing the problem can be done in a quadratic size of the input, the datapoints in the paper don't give any reason to believe that the <i>time</i> to finding the factors won't just be exponential in the input.<p>Also, no, this is not a record for Quantum Computing; as this is a DWave Quantum Annealing machine which needs to be evaluated by a different standard.<p>This seems to be more interesting if you look at it from the perspective "How can I treat prime factorization as a optimization problem" rather than "Does it look like Quantum Annealing Machines can factor RSA in the near term".
This study considers seven semi-primes (without justification why these seven) and reports an average(?) runtime of factoring each with D-Wave. No conclusions should be drawn on so few data-points.
The proposed "Block Multiplication Table Method" will only affect the constants and thus has no effect on the asymptotics.
The embedding from logical to physical qubits appears to have an exponential gap (but again, we shouldn't draw conclusions from so few data-points). However, if this is indeed true then even a polynomial runtime for annealing would still result in an exponential runtime for factoring.
All in all, it eludes me why authors conclude that the obtained results are promising.
IBM and Google both claim to have 53 qubit computers, which I thought was the edge of the technology at the moment. This machine has 1635 "physical qubits". I'm guessing these are not the same thing. Can anyone comment on what the difference is?
The authors give the following factorization with their algorithm: 231037 = 499 * 363. Not only is the product not equal to 231037, but 363 is also clearly not a prime as it is divisible by 3.<p>There is no discussion whatsoever about this failure, except for "The low noise D-Wave 2000Q factored correctly all integers N up to L_N= 17"
Layman question:<p>assuming one day RSA gets actually broken and a quantum computer or a new algorithm can factorize prime numbers fast: would there be any alternatives avaiable for public/private key encryption?<p>Or would the solution be, to use just a lot bigger prime numbers calculated also with a quantum computer? That sounds not too promising.
At what bit lenght is this approach faster than <a href="https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...</a> ?
It's 2020, and I'm still waiting to see an impressive proof of work out out of a quantum computer that I can easily verify on my traditional computer (two different files with identical SHA-512, for example?).<p>Maybe a few years from now?
I see a slight irony in how I perceive crypto conversations as very cryptic. It's pleasant to wander into a thread like this where you can't really tell up from down (as a relative layperson).