9 ms·

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.

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. 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...). 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] 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! [1]https://quantumcomputing.stackexchange.com/questions/9204/the-algorithm-of-the-new-quantum-factoring-record-1-099-551-473-989 https://quantumcomputing.stackexchange.com/questions/9204/th...

scottlocklin 6y ago
q: 103459 evaluates in 4 microseconds in a 12 year old intel chip running a single thread in J
deleted 6y ago
[deleted]
dvdkhlng 6y ago
Glancing at the paper, I do not find anything that is impressive. AFAICS the algorithm they implement is of asymptotic exponential complexity, even when run on a quantum computer. I cannot imagine how this work would have any effect on the field of asymmetric encryption algorithm research. To me it looks like they took the factorization problem, which has a lot of well-known (relatively) low-complexity algorithms and imlemented it by mapping it onto circuit-SAT [1] (the multiplication table corresponds to a multiplier circuit which they try to solve in reverse). Circuit-SAT is a proven NP-complete problem. There is currently no known quantum-algorithm that solves NP-complete problems in sub-exponential time. Note that in the complexity hierarchy NP-complete problems are "harder" than the factoring problem. These are generally bad problems, were not even a quantum-computer helps (and I know of no asymmetric encryption algorithm that is NP-complete when trying to break it, but maybe the quantum-resistant encryption algorithms are better in that regard). And that's even before we start talking about the limitations of quantum-annealers and the kind of speedups they can gain over classical computers. For a discussion of that, maybe one should start reading Scott Aaronson's blog [2]. [1] https://en.wikipedia.org/wiki/Circuit_satisfiability_problem https://en.wikipedia.org/wiki/Circuit_satisfiability_problem [2] https://www.scottaaronson.com/blog/?p=2555 https://www.scottaaronson.com/blog/?p=2555
- ohvirginia 6y ago
  But circuit sat is not equivalent to solving a multiplication table like this. If you're doing it that way, you're making it way too hard.
- conformist 6y ago
  This. Essentially, all the quantum annealing stuff that D-Wave does follows the patter of mapping a problem onto a spin glass and then finding the ground state with annealing. The only really interesting theoretical aspect is finding good maps form hard problems to spin glasses. This is a nice reference: https://arxiv.org/abs/1302.5843 https://arxiv.org/abs/1302.5843
- betterunix2 6y ago
  "asymmetric encryption algorithm that is NP-complete" No such cryptosystems are known, and in fact such a system would also have implications in complexity theory.
baby 6y ago
The number could have been factored by hand.
xxs 6y 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 6y 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 6y ago
    Factoring is not a constant time problem for quantum computers.
    - y04nn 6y 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 6y 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 6y ago
ohvirginia 6y ago
I think the really cool thing is to consider whether there exists a clever classical algorithm that uses some sort of anealing approach and some clever hacks based on the structure of integer multiplication to solve the multiplication table in sub exponential time. I like the approach in the paper of moving from binary to blocks, to try to create subproblems. Since 2012, I've wondered whether creating equivalences between tables in different radices, or using some of the statistics such that any choice of a factor radix unit, limits the possible values of the intermediate products adjacent to it, or that a delta of change in any of the intermediate products would produce a cascade of changes along its intersecting row column, and other things like that, to break the symmetry and kind of hack out a little bit more information.
phkahler 6y ago
>> 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 What? I was implementing CFRAC on my Atari 800 trying to factor a 100 bit number on its 6502. I had found enough congruences saved to disk but never wrote the matrix reduction code to spit out the answer. 17 bits. Pffft P.s. not kidding about cfrac on atari.

scottlocklin 6y ago

q: 103459 evaluates in 4 microseconds in a 12 year old intel chip running a single thread in J

deleted 6y ago

[deleted]

dvdkhlng 6y ago

Glancing at the paper, I do not find anything that is impressive. AFAICS the algorithm they implement is of asymptotic exponential complexity, even when run on a quantum computer. I cannot imagine how this work would have any effect on the field of asymmetric encryption algorithm research. To me it looks like they took the factorization problem, which has a lot of well-known (relatively) low-complexity algorithms and imlemented it by mapping it onto circuit-SAT [1] (the multiplication table corresponds to a multiplier circuit which they try to solve in reverse). Circuit-SAT is a proven NP-complete problem. There is currently no known quantum-algorithm that solves NP-complete problems in sub-exponential time. Note that in the complexity hierarchy NP-complete problems are "harder" than the factoring problem. These are generally bad problems, were not even a quantum-computer helps (and I know of no asymmetric encryption algorithm that is NP-complete when trying to break it, but maybe the quantum-resistant encryption algorithms are better in that regard). And that's even before we start talking about the limitations of quantum-annealers and the kind of speedups they can gain over classical computers. For a discussion of that, maybe one should start reading Scott Aaronson's blog [2]. [1] https://en.wikipedia.org/wiki/Circuit_satisfiability_problem https://en.wikipedia.org/wiki/Circuit_satisfiability_problem [2] https://www.scottaaronson.com/blog/?p=2555 https://www.scottaaronson.com/blog/?p=2555

ohvirginia 6y ago
But circuit sat is not equivalent to solving a multiplication table like this. If you're doing it that way, you're making it way too hard.
conformist 6y ago
This. Essentially, all the quantum annealing stuff that D-Wave does follows the patter of mapping a problem onto a spin glass and then finding the ground state with annealing. The only really interesting theoretical aspect is finding good maps form hard problems to spin glasses. This is a nice reference: https://arxiv.org/abs/1302.5843 https://arxiv.org/abs/1302.5843
betterunix2 6y ago
"asymmetric encryption algorithm that is NP-complete" No such cryptosystems are known, and in fact such a system would also have implications in complexity theory.

baby 6y ago

The number could have been factored by hand.

xxs 6y 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 6y 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 6y ago
  Factoring is not a constant time problem for quantum computers.
  - y04nn 6y 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 6y 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 6y ago

ohvirginia 6y ago

I think the really cool thing is to consider whether there exists a clever classical algorithm that uses some sort of anealing approach and some clever hacks based on the structure of integer multiplication to solve the multiplication table in sub exponential time. I like the approach in the paper of moving from binary to blocks, to try to create subproblems. Since 2012, I've wondered whether creating equivalences between tables in different radices, or using some of the statistics such that any choice of a factor radix unit, limits the possible values of the intermediate products adjacent to it, or that a delta of change in any of the intermediate products would produce a cascade of changes along its intersecting row column, and other things like that, to break the symmetry and kind of hack out a little bit more information.

phkahler 6y ago

>> 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 What? I was implementing CFRAC on my Atari 800 trying to factor a 100 bit number on its 6502. I had found enough congruences saved to disk but never wrote the matrix reduction code to spit out the answer. 17 bits. Pffft P.s. not kidding about cfrac on atari.