Communications of the ACM
Quantum Speedup for the Fast Fourier Transform?
Credit: Maxim Studio
Researchers have been exploring the theoretical potential of quantum computers for decades. Only in recent years, however, have real systems begun to achieve an accuracy and scale that makes their eventual impact seem plausible.
A major impetus for the attention and investment is the revolutionary introduction of methods by Peter Shor, now at the Massachusetts Institute of Technology, that could allow quantum computers to break current public-key encryption schemes. The resources, such as time, required by classical techniques for factoring numbers, grow exponentially with the number of digits in the input. The demands of Shor's quantum algorithms grow only as a polynomial function, potentially rendering encrypted data vulnerable to future quantum computers.
No entries found