Communications of the ACM
Quantum Algorithms Struggle Against Old Foe: Clever Computers
Intel, IBM, and others are predicting we are nearing quantum supremacy a nebulous frontier where quantum computers begin to do things beyond the ability of classical machines.
Credit: Josef Bsharah/Quanta Magazine
For Cristian Calude, doubt began with a puzzle so simple, he said, that "even a child can understand it." Here it is: Suppose you have a mysterious box that takes one of two possible inputs — you can press a red button or a blue button, say — and gives back one of two possible outputs — a red ball or a blue ball. If the box always returns the same color ball no matter what, it's said to be constant; if the color of the ball changes with the color of the button, it's balanced. Your assignment is to determine which type of box you've got by asking it to perform its secret act only once.
At first glance, the task might seem hopeless. Indeed, when the physicist David Deutsch described this thought experiment in 1985, computer scientists believed that no machine operating by the rules of classical physics could learn the box's identity with fewer than two queries: one for each input.
Deutsch, however, found that by translating the problem into the strange language of quantum mechanics, he could in fact achieve a one-query solution. He proposed a simple five-step algorithm that could run on a quantum computer of just two qubits — the basic units of quantum information. (Experimentalists wouldn't build an actual quantum machine capable of running the algorithm until 1998.)
Although it has no practical use, Deutsch's algorithm — the first quantum algorithm — became a ubiquitous illustration of the inimitable power of quantum computation, which might one day transform such fields as cryptography, drug discovery and materials engineering. "If you open a textbook in quantum computing written before the last 10 years or so, it will start with this example," said Calude, a mathematician and computer scientist at the University of Auckland in New Zealand. "It appeared everywhere."
But something bothered him. If Deutsch's algorithm were truly superior, as the early textbooks claimed, no classical algorithm of comparable ability could exist. Was that really true? "I'm a mathematician — I am by training an unbeliever," Calude said. "When I see a claim like this, I start thinking: How do I prove it?"
From Quantum Magazine
View Full Article
No entries found