When Quantum Computing Comes at a Cost: The Trade-Off of Forgetting the Path

Sunday - July 23 2023, 20:47 UTC - 1 year ago

Quantum computers offer the potential for faster computing than classical computers. In 2020, a group of researchers took a big step towards resolving a long-standing problem in quantum computing and showed that any path-finding algorithm running on a quantum computer has to forget some steps in order to find the exit faster than any classical algorithm.

Imagine you visit a maze with some friends. You emerge from the exit shortly after going in, and wait around for hours before your friends emerge. Naturally, they ask about the path you took — surely you can retrace your steps and show them the way, right? .

Not so in a world governed by the strange laws of quantum physics. Twenty years ago, quantum computing researchers developed an algorithm that harnessed those laws to traverse a specific kind of mathematical maze much faster than any algorithm running on an ordinary classical computer. But that speedup comes at a cost: The fast quantum algorithm finds the exit but has no idea how it got there.

Researchers have long wondered whether this trade-off is inevitable. Is it really impossible to find the exit quickly without forgetting the way? .

"It’s kind of mind-blowing that you would even need to ask this question," said Matthew Coudron, a computer scientist at the National Institute of Standards and Technology in Gaithersburg, Maryland.

Last November, Coudron and two colleagues took a big step toward resolving that long-standing problem: They proved that no algorithm in a broad and natural class of fast quantum algorithms can find a path through that special maze, called a welded tree graph. The results show that any hypothetical path-finding algorithm that doesn’t blindly guess would have to temporarily lose track of the entrance to have any chance of succeeding. It seems that forgetting is inevitable.

"There is no way I would have guessed that they could actually prove that," said Simon Apers, a quantum computing researcher with the National Center for Scientific Research at the Institute for Research in Foundations of Computer Science in Paris, adding that the result "is very useful in illustrating what quantum algorithms can and cannot do." .

The Quantum Boost .

Quantum computers owe their power in part to a phenomenon known as superposition, which effectively allows them to simultaneously explore many options that a classical computer would need to consider individually. But it’s not as simple as performing multiple calculations at once to save time. Checking the result of a superposition of choices never reveals a superposition of outcomes — rather, you only ever obtain one of the possible outcomes, each of which has a different probability. Quantum algorithms rely on the fact that contributions to these probabilities can interfere with each other like waves on the surface of a pond, boosting the probability of getting the right answer while reducing the probability of every other outcome.

Because the interference has to work out just right, not every computational task is amenable to a quantum speedup, and indeed researchers are still working out where quantum algorithms can help, decades after quantum computing was first proposed. But they’ve had some notable successes. In 1994, Peter Shor developed a quantum algorithm for factoring large numbers — a task whose apparent difficulty for classical computers underlies much of modern cryptography. Shor’s algorithm could rapidly factor numbers so large that all known classical algorithms would be practically useless.