3 ms·

"103459" in 100ms is a horrible, horrible result. There are like 64 primes to try. That's 64 32bit divisions - around 30cycles per division, make it 50 with all

by xxs 7y ago

"103459" in 100ms is a horrible, horrible result. There are like 64 primes to try. That's 64 32bit divisions - around 30cycles per division, make it 50 with all the checks. Run it at 5GHz, that's 10ns or so for divisions. Less than 1us for 64. We are talking 5 orders of magnitude.

y04nn 7y ago
No it's not, from what I understand of quantum computing, with more qbits you would be able to factor larger numbers in the same amount of time (100ms), when with your 5GHz it would take longer than the age of the universe.
- adrianN 7y ago
  Factoring is not a constant time problem for quantum computers.
  - y04nn 7y ago
    Ok, my bad, the time complexity of the Shor algorithme use in quantum computers is O((log n)^3) while your algorithm has a complexity O(n log log n). So quantum computers should be able to outperform classical computers in this task in the future.
alkonaut 7y ago
I don't think that's a very important distinction, the goal is of course factoring the 2048bit number without using exponentially more hardware. 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.
- nightcracker 7y ago
  > 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.
  - alkonaut 7y ago
    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.
- dvdkhlng 7y ago
  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 :)

by xxs 7y ago

y04nn 7y ago

No it's not, from what I understand of quantum computing, with more qbits you would be able to factor larger numbers in the same amount of time (100ms), when with your 5GHz it would take longer than the age of the universe.

adrianN 7y ago
Factoring is not a constant time problem for quantum computers.
- y04nn 7y ago
  Ok, my bad, the time complexity of the Shor algorithme use in quantum computers is O((log n)^3) while your algorithm has a complexity O(n log log n). So quantum computers should be able to outperform classical computers in this task in the future.

alkonaut 7y ago

I don't think that's a very important distinction, the goal is of course factoring the 2048bit number without using exponentially more hardware. 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.

nightcracker 7y ago
> 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.
- alkonaut 7y ago
  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.
dvdkhlng 7y ago
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 :)