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.
Answer
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: http://arxiv.org/abs/quant-ph/0209084
No comments:
Post a Comment