Computing’s Search for Quantum Questions
Source: Stephen Ornes

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.

As a demonstration problem, factoring numbers is clean and straightforward. “Once your machine produces an answer, you can recheck that it’s right,” said Scott Aaronson, a theoretical computer scientist who is moving from the Massachusetts Institute of Technology to the University of Texas, Austin. “And it’s inherently quantum. If you run it and it works, you won’t need a debate” about whether it can do something other computers can’t.

Unlike a universal quantum computer, which is designed to tackle a range of problems, a quantum annealer is designed to tackle a specific type of problem called an NP-hard optimization problem. These can arise in many situations, but here’s an example: Say you went to a city and wanted to find the largest cluster of people who all know each other. (This is called the “maximum clique problem” in computer science.) You could try to tackle the problem with a brute-force approach, identifying every group of friends and comparing sizes until you settled on the largest. Such a strategy would work for a small village, but it becomes untenable if you want to identify and compare every group of friends in, say, Tokyo.

The D-Wave 2X processor must be cooled to fifteen-thousandths of a degree above absolute zero.

D-Wave Systems Inc.

The D-Wave 2X processor must be cooled to fifteen-thousandths of a degree above absolute zero.
NP-hard problems and the usefulness of annealing extend far beyond social networks. Say you had a fridge full of ingredients and wanted to identify recipes that would leave the least amount of waste, or you were building a house on a budget and wanted to know which materials and configuration would maximize your square footage. The traveling salesman problem, which involves identifying the most efficient route by which to visit every city on a list and return home, can also be expressed as an NP-hard optimization problem. So can many of the algorithms used in machine learning.

To solve this kind of problem, the D-Wave 2X uses a process called annealing, which gets its name from a 7,000-year-old metallurgical practice. Early metalworkers figured out that if they made a material hot enough and then let it cool down slowly, it would make the final product stronger. The process works because the heat randomly jiggles around all the atoms in the metal, and then as it cools, the atoms slowly arrange themselves into their lowest-energy (and therefore most stable) configuration. Bartenders may also recognize the process: The secret to creating a flawless and clear ice cube is to let the water freeze very, very slowly.

Quantum annealers reproduce this process using qubits. The D-Wave 2X contains approximately 1,000 qubits made out of tiny superconducting loops of metal. Each loop can produce a magnetic field that points either up or down, or, since this is a quantum system, both up and down at the same time. A sideways magnetic field jumbles up the state of each loop; as the field’s strength gets lower and eventually vanishes, the qubits tend to collapse into their lowest-energy states, which correspond to the problem’s solution. Because all quantum computations are probabilistic, the process must be repeated at least a few times to ensure that the final configuration of the system has truly minimized the overall energy.

There are also classical annealers that mimic this process — indeed, the algorithm that the D-Wave 2X competed against late last year was a simulated annealer.

Annealers can’t necessarily identify the best solution; they are designed to find good-enough solutions. The system could always land in a low-energy state that isn’t the lowest possible one. It’s like trying to find the deepest cave in a giant system of underground caverns — from where you’re standing, all paths may lead upward, but that doesn’t mean there isn’t a deeper point somewhere nearby.

The great advantage of a quantum annealer is that it can exploit a uniquely quantum property by which a system can “tunnel” through what appears to be an insurmountable barrier. Thus, the D-Wave can tunnel from one solution to another in search of the lowest energy state. This property has been contested over the years, but Google’s study delivered the most convincing evidence to date that the machine really does use quantum effects to solve problems, Troyer said.

Researchers were less impressed by the Google team’s announcement that the D-Wave 2X solved a certain problem 100 million times faster than a classical algorithm, since a simulated annealer wasn’t necessarily the best kind of algorithm to use on that particular problem. “They looked for problem instances where quantum annealing should work faster than classical annealing, and on those problems where the classical annealer is very slow, the D-Wave worked well,” Troyer said.

The researchers have reason to be skeptical. In 2013, following claims that the D-Wave 2 executed a problem 3,600 times faster than a classical computer, the company’s co-founder, Geordie Rose, declared that the machine performed “better at something than any other option available.” The claim didn’t hold: Sergei Isakov, at the time a postdoctoral researcher at ETH Zurich, used some clever code on a laptop to solve the same problem just as quickly. (Isakov has since been hired by Google and was listed as a co-author of the December paper.)

“One of the reasons why quantum computing is so hard, which hardly anyone is talking about, is that classical computing already exists and is so good,” Aaronson said. “It’s the elephant in the room.” After all, computer scientists have been building algorithms to make general-purpose computers work better for the past 60 years.

Toward Better Tests

The December test showed that the D-Wave can outperform a classical computer in one particular class of carefully crafted problem, according to Katzgraber — which suggests that “there are problems where quantum annealing shows a strong advantage,” he said. Now, he said, it’s up to researchers to identify real-world applications bearing the features of these problems. “By looking at the structure of the problem that Google chose, we now have a hint at a direction to search for instances where classical algorithms might have trouble and quantum algorithms might excel.” But the search for those specific applications is still in its early days.

The advances that emerge from the D-Wave 2X machine won’t be measurable in real-world speedups — at least not yet. A 1,000-qubit machine is still too small to lead to significant time savings. Yet Google’s work on the D-Wave 2X machine has pushed computer scientists to devise even better classical algorithms. “By having the competition, one gets lots of good ideas,” Troyer said. There’s been “huge progress in the field. For Google and NASA and Lockheed and those who invested, it paid off already [with] having better classical methods now.”

He added that the importance of the D-Wave 2X was never tied to practical concerns. Its true value has been in demonstrating the possibility of something that has never been seen before — an annealer that conclusively uses quantum properties to answer difficult questions. From this vantage point, computer scientists see a world of new potential.