It is known that there is a famous quantum factorization algorithm by Peter Shor. The algorithm is thought to be suitable only for quantum gate computer.

But can a an adiabatic quantum computer especially that which is capable of quantum annealing be used for factorization?

I am asking this because it seems that Geordie Rose claims in his blog that they have a quantum factorization algorithm that is somehow "better than Shor". But the details are unavailable as of now.

up vote 2 down vote accepted

Yes, though I don't think that we'll see D-Wave factoring even 20-bit numbers anytime soon. One of their tutorials shows how to model a NAND gate using 4 qubits. With a handful of those, I can make a carry-save multiplier cell, though surely it can be built more optimally. If I want to factor an N-bit number, I could use an N/2 by N/2 array of the carry save adder cells, and constrain the N-bit output to equal the number I want to factor, and have no weights on the inputs. Run Quantum Annealing, and in theory with probability approaching 100% as noise goes to zero and run time get's longer, and the inputs will settle to the input factors, in one of the two acceptable states, for example 3x5 = 15 vs 5x3 = 15.

The title "Better than Shor" may simply mean that with their new 512 qubit QAO, they believe they can factor 35 = 5x7, or maybe 51 = 3x17. I really don't see factoring a 512 bit number with a 512 qubit quantum annealer. Since building the multiplier takes O(N^2) qubits, we'll probably need over a million to factor 2048 bit RSA. A modified Booth Encoded multiplier saves you a factor of over 2. If D-Wave continues doubling qubits every year or so, and if they continue showing true quantum annealing performance, we may need to switch to a post-quantum-computer encryption algorithm.

Note that this technique also works for finding SHA-1 collisions. It's super cool stuff. I just found a paper describing the algorithm from 2002:

  • 1
    Can you provide some references for this? Sounds very intriguing. – SMeznaric Oct 5 '12 at 0:09

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.