Supremecy—Quantum Algorithms Struggle Against Old Foe: Clever Computers

From Quanta:

The quest for "quantum supremacy" – unambiguous proof that a quantum computer does something faster than an ordinary computer – has paradoxically led to a boom in quasi-quantum classical algorithms.

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?”

He couldn’t. Instead, he showed it was false. In a 2007 paper, he broke down Deutsch’s algorithm into its constituent quantum parts (for instance, the ability to represent two classical bits as a “superposition” of both at once) and sidestepped these instructions with classical operations — a process Calude calls “de-quantization.” In this way, he constructed an elegant classical solution to Deutsch’s black-box riddle. The quantum solution, it turned out, wasn’t always better after all....MORE