Because of this, researchers have studied how quantum computers fare on problems involving oracles. These efforts can provide indirect evidence that quantum computers really are more powerful than classical ones, and they can help researchers explore qualitatively new tasks where quantum computers might excel. Sometimes, they can even have practical applications. In 1994, the applied mathematician Peter Shor was inspired by a recent oracle result(opens a new tab) to develop a fast quantum algorithm for factoring large numbers — a task whose apparent difficulty underlies the cryptographic systems that keep our online data secure. Shor’s discovery kicked off a race to build powerful quantum computers that continues to this day.
It’s hard to predict the future of complexity theory, but not every question about the trajectory of the field is equally hard to answer. Will researchers continue to consult oracles? Signs point to yes.