Computing’s Search for Quantum Questions
Recent tests show that quantum computers made by D-Wave systems should solve some problems faster than ordinary computers. Researchers have begun to map out exactly which queries might benefit from these quantum machines.
Quantum bits, or “qubits,” can be in a superposition of the values zero and one.
It was billed as the vindication of the quantum computer. Late last year, researchers at Google announced that a quantum machine called the D-Wave 2X had executed a task 100 million times faster than a classical computer. The claim implies that the machine can complete in one second a task that might take a classical computer three years.
It also erased one facet of the skepticism that has long faced this particular version of a quantum computer. In the past, critics of so-called “quantum annealers” made by the Canadian company D-Wave Systems have wondered if the machines make use of intrinsically quantum processes at all.
Part of the problem lies in the catch-22 of quantum computing: The quantum features only work when they’re not being observed, so observing a quantum computer to check if it’s exploiting quantum behavior will destroy the quantum behavior being checked. “It’s hard to devise a physics experiment to study something you aren’t allowed to observe,” said Catherine McGeoch, a computer scientist at D-Wave. December’s news convincingly satisfied critics that the quantum annealer really does exploit uniquely quantum effects.
But it didn’t settle a more important question: What can these computers do that classical computers can’t? The claim of a 100-million-factor speedup did not conclusively prove that the D-Wave 2X — and quantum annealers in general — will profoundly surpass the abilities of classical machines. A case in point: The paper announcing the results was careful to mention that the 100-million-factor speedup came when the D-Wave computer was pitted against one particular type of algorithm running on a classical computer. Change the algorithm to a more efficient one, and the speedup disappears. “It’s a little like saying, ‘OK, we’re going to have a motorcycle race. Everybody bring out your motorbike.’ But only one person knows it’s going to be on dirt,” said Helmut Katzgraber, a computational physicist at Texas A&M University. “Then they bring the dirt bike, but nobody else knows. That’s basically what’s been done there.”
So how would the D-Wave machine compare in a fair race against the fastest classical computers? It depends on the racetrack.
Computer scientists are now actively mapping out so-called “benchmark problems” — the classes of problems that are particularly suited to the type of hybrid quantum machines epitomized by the D-Wave 2X. A study co-authored by Katzgraber and posted to the scientific preprint site arxiv.org in April concludes that scaled-up quantum annealers should be able to outperform classical computers in certain narrow computing domains. Fortunately, these domains are likely to include important problems in machine learning, protein folding and route planning, to name a few. But exactly which of these problems will show a marked improvement when processed by a quantum annealer, and how fast the speedup will be — these are questions that computer scientists are only beginning to understand.
Quantum Persuasion
Convincing people of a machine’s supremacy won’t be a thorny issue for a universal quantum computer, which a quantum annealer like the D-Wave machine is not. Though both types of machines solve problems using an array of qubits — the quantum analogue to classical bits of information — they’re inherently different. With a universal quantum computer, a user can measure and control the quantum states of individual qubits, which in theory allows the machine to solve problems that would effectively be impossible to solve using a classical device. For example, a universal quantum computer would be able to find the prime factors of a very large number, and thus crack many encryption schemes used today. “What you want to show, basically, is that you have solved a problem with a quantum device that you can’t solve classically,” said Matthias Troyer, a computational physicist at the Institute for Theoretical Physics at the Swiss Federal Institute of Technology Zurich (ETH Zurich). “The ultimate problem is to do an impossible calculation. That would convince most people.”
Universal quantum machines exist, though the engineering challenges of making them are so great that the most sophisticated of them can solve only simple problems like finding the prime factors of a relatively small number such as 56,153. In May, IBM announced that it had set up a cloud-based interface so that outside researchers could use the company’s quantum processor. It has five qubits....MORE
