Emerging Insights on Limitations of Quantum Computing: Shape Quest for Fast Algorithms
January 24, 2003
By Sara Robinson
Read a typical article about quantum computing (including this one) and
almost surely, somewhere in the first three paragraphs, you'll find a
reference to Peter Shor's polynomial-time quantum algorithm for
factoring.
Shor's 1994 result propelled quantum computing into the limelight,
attracting hordes of eager young researchers and abundant government
funding. If a quantum computer could factor in polynomial time,
computer scientists theorized, perhaps it could solve
many other important, seemingly intractable problems.