Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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.

share|improve this question
1  
possible duplicate of What can the D-Wave quantum computer do? –  Luboš Motl Jun 13 '11 at 17:24

1 Answer 1

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: http://arxiv.org/abs/quant-ph/0209084

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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