Quantum Leap

Hopes for quantum computing have long been buoyed by the existence of algorithms that would solve some particularly challenging problems with exponentially fewer operations than any known algorithm for conventional computers. Many experts believe, but have been unable to prove, that these problems will resist even the cleverest non-quantum algorithms. Recently, researchers have shown the strongest evidence yet that even if conventional computers were made much more powerful, they probably still could not efficiently solve some problems that a quantum computer could. That such problems exist is a long-standing conjecture about the greater capability of quantum computers. "It was really the first big conjecture in quantum complexity theory," said computer scientist Umesh Vazirani of the University of California, Berkeley, who proposed the conjecture with then-student Ethan Bernstein in the 1993 paper (updated in 1997) that established the field.