Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

If the paper is correct then yes, it would be a huge improvement in the required space even accounting for the overhead of error correction.

Shor's algorithm requires performing a modular exponentiation under superposition. For an n bit modulus this requires 2n or 3n qubits of storage, plus let's say 50% overhead for routing and gates. You end up needing 5n to 10n logical qubits for an n bit number. So to factor a 2048 bit number you'd need on the order of ten thousand logical qubits. Improving that to a few hundred logical qubits would be a big improvement. Also, there's fewer operations so the code distance can be lower.

...but don't forget that "if the paper is correct" bit.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: