3 ms·
Shor’s algorithm can factorize integers on a quantum computer asymptoticly faster than on a classical computer but the algorithm requires at least a 128 qubit q
by jcoffland 9y ago
Shor’s algorithm can factorize integers on a quantum computer asymptoticly faster than on a classical computer but the algorithm requires at least a 128 qubit quantum computer to factor a 128 bit number and thereby break something like 128 bit RSA encryption. No one yet has, or is publicly admitting to having, a reliable 128 qubit device.
In some cases, error correction can be achieved simply by running the algorithm a few times.
- Beltiras 9y agoError correction is immaterial for the factoring case. You multiply the factors and if you do not get the original number you know you have to run it again.
- jcoffland 9y agoIn Schor's algorithm, the quantum computer finds the period p of B mod N were N is the number you are trying to factor and B is a random number less than N. The quantum computer may find p with imperfect accuracy. Running the algorithm repeatedly can improve the accuracy of p. You can also try other numbers close to p. Both are examples of error correcting a quantum algorithm.