The Ongoing Battle Between Quantum and Classical Computers

A popular misconception is that the potential—and the limits—of quantum computing must come from hardware. In the digital age, we’ve gotten used to marking advances in clock speed and memory. Likewise, the 50-qubit quantum machines now coming online from the likes of Intel and IBM have inspired predictions that we are nearing “quantum supremacy”—a nebulous frontier where quantum computers begin to do things beyond the ability of classical machines.

Quanta Magazine


Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

But quantum supremacy is not a single, sweeping victory to be sought—a broad Rubicon to be crossed—but rather a drawn-out series of small duels. It will be established problem by problem, quantum algorithm versus classical algorithm. “With quantum computers, progress is not just about speed,” said Michael Bremner, a quantum theorist at the University of Technology Sydney. “It’s much more about the intricacy of the algorithms at play.”

Paradoxically, reports of powerful quantum computations are motivating improvements to classical ones, making it harder for quantum machines to gain an advantage. “Most of the time when people talk about quantum computing, classical computing is dismissed, like something that is past its prime,” said Cristian Calude, a mathematician and computer scientist at the University of Auckland in New Zealand. “But that is not the case. This is an ongoing competition.”

And the goalposts are shifting. “When it comes to saying where the supremacy threshold is, it depends on how good the best classical algorithms are,” said John Preskill, a theoretical physicist at the California Institute of Technology. “As they get better, we have to move that boundary.”

‘It Doesn’t Look So Easy’

Before the dream of a quantum computer took shape in the 1980s, most computer scientists took for granted that classical computing was all there was. The field’s pioneers had convincingly argued that classical computers—epitomized by the mathematical abstraction known as a Turing machine—should be able to compute everything that is computable in the physical universe, from basic arithmetic to stock trades to black hole collisions.

Classical machines couldn’t necessarily do all these computations efficiently, though. Let’s say you wanted to understand something like the chemical behavior of a molecule. This behavior depends on the behavior of the electrons in the molecule, which exist in a superposition of many classical states. Making things messier, the quantum state of each electron depends on the states of all the others—due to the quantum-mechanical phenomenon known as entanglement. Classically calculating these entangled states in even very simple molecules can become a nightmare of exponentially increasing complexity.

A quantum computer, by contrast, can deal with the intertwined fates of the electrons under study by superposing and entangling its own quantum bits. This enables the computer to process extraordinary amounts of information. Each single qubit you add doubles the states the system can simultaneously store: Two qubits can store four states, three qubits can store eight states, and so on. Thus, you might need just 50 entangled qubits to model quantum states that would require exponentially many classical bits—1.125 quadrillion to be exact—to encode.

A quantum machine could therefore make the classically intractable problem of simulating large quantum-mechanical systems tractable, or so it appeared. “Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical,” the physicist Richard Feynman famously quipped in 1981. “And by golly it’s a wonderful problem, because it doesn’t look so easy.”

It wasn’t, of course.

Even before anyone began tinkering with quantum hardware, theorists struggled to come up with suitable software. Early on, Feynman and David Deutsch, a physicist at the University of Oxford, learned that they could control quantum information with mathematical operations borrowed from linear algebra, which they called gates. As analogues to classical logic gates, quantum gates manipulate qubits in all sorts of ways—guiding them into a succession of superpositions and entanglements and then measuring their output. By mixing and matching gates to form circuits, the theorists could easily assemble quantum algorithms.

Richard Feynman, the physicist who came up with the idea for a quantum computer in the 1980s, quipped that “by golly, it’s a wonderful problem, because it doesn’t look so easy.”

Cynthia Johnson/Getty Images

Conceiving algorithms that promised clear computational benefits proved more difficult. By the early 2000s, mathematicians had come up with only a few good candidates. Most famously, in 1994, a young staffer at Bell Laboratories named Peter Shor proposed a quantum algorithm that factors integers exponentially faster than any known classical algorithm—an efficiency that could allow it to crack many popular encryption schemes. Two years later, Shor’s Bell Labs colleague Lov Grover devised an algorithm that speeds up the classically tedious process of searching through unsorted databases. “There were a variety of examples that indicated quantum computing power should be greater than classical,” said Richard Jozsa, a quantum information scientist at the University of Cambridge.

But Jozsa, along with other researchers, would also discover a variety of examples that indicated just the opposite. “It turns out that many beautiful quantum processes look like they should be complicated” and therefore hard to simulate on a classical computer, Jozsa said. “But with clever, subtle mathematical techniques, you can figure out what they will do.” He and his colleagues found that they could use these techniques to efficiently simulate—or “de-quantize,” as Calude would say—a surprising number of quantum circuits. For instance, circuits that omit entanglement fall into this trap, as do those that entangle only a limited number of qubits or use only certain kinds of entangling gates.

What, then, guarantees that an algorithm like Shor’s is uniquely powerful? “That’s very much an open question,” Jozsa said. “We never really succeeded in understanding why some [algorithms] are easy to simulate classically and others are not. Clearly entanglement is important, but it’s not the end of the story.” Experts began to wonder whether many of the quantum algorithms that they believed were superior might turn out to be only ordinary.

Sampling Struggle

Until recently, the pursuit of quantum power was largely an abstract one. “We weren’t really concerned with implementing our algorithms because nobody believed that in the reasonable future we’d have a quantum computer to do it,” Jozsa said. Running Shor’s algorithm for integers large enough to unlock a standard 128-bit encryption key, for instance, would require thousands of qubits—plus probably many thousands more to correct for errors. Experimentalists, meanwhile, were fumbling while trying to control more than a handful.

But by 2011, things were starting to look up. That fall, at a conference in Brussels, Preskill speculated that “the day when well-controlled quantum systems can perform tasks surpassing what can be done in the classical world” might not be far off. Recent laboratory results, he said, could soon lead to quantum machines on the order of 100 qubits. Getting them to pull off some “super-classical” feat maybe wasn’t out of the question. (Although D-Wave Systems’ commercial quantum processors could by then wrangle 128 qubits and now boast more than 2,000, they tackle only specific optimization problems; many experts doubt they can outperform classical computers.)

“I was just trying to emphasize we were getting close—that we might finally reach a real milestone in human civilization where quantum technology becomes the most powerful information technology that we have,” Preskill said. He called this milestone “quantum supremacy.” The name—and the optimism—stuck. “It took off to an extent I didn’t suspect.”

The buzz about quantum supremacy reflected a growing excitement in the field—over experimental progress, yes, but perhaps more so over a series of theoretical breakthroughs that began with a 2004 paper by the IBM physicists Barbara Terhal and David DiVincenzo. In their effort to understand quantum assets, the pair had turned their attention to rudimentary quantum puzzles known as sampling problems. In time, this class of problems would become experimentalists’ greatest hope for demonstrating an unambiguous speedup on early quantum machines.

David Deutsch, a physicist at the University of Oxford, came up with the first problem that could be solved exclusively by a quantum computer.

Sampling problems exploit the elusive nature of quantum information. Say you apply a sequence of gates to 100 qubits. This circuit may whip the qubits into a mathematical monstrosity equivalent to something on the order of 2100 classical bits. But once you measure the system, its complexity collapses to a string of only 100 bits. The system will spit out a particular string—or sample—with some probability determined by your circuit.

In a sampling problem, the goal is to produce a series of samples that look as though they came from this circuit. It’s like repeatedly tossing a coin to show that it will (on average) come up 50 percent heads and 50 percent tails. Except here, the outcome of each “toss” isn’t a single value—heads or tails—it’s a string of many values, each of which may be influenced by some (or even all) of the other values.

For a well-oiled quantum computer, this exercise is a no-brainer. It’s what it does naturally. Classical computers, on the other hand, seem to have a tougher time. In the worst circumstances, they must do the unwieldy work of computing probabilities for all possible output strings—all 2100 of them—and then randomly select samples from that distribution. “People always conjectured this was the case,” particularly for very complex quantum circuits, said Ashley Montanaro, an expert in quantum algorithms at the University of Bristol.

Terhal and DiVincenzo showed that even some simple quantum circuits should still be hard to sample by classical means. Hence, a bar was set. If experimentalists could get a quantum system to spit out these samples, they would have good reason to believe that they’d done something classically unmatchable.

Theorists soon expanded this line of thought to include other sorts of sampling problems. One of the most promising proposals came from Scott Aaronson, a computer scientist then at the Massachusetts Institute of Technology, and his doctoral student Alex Arkhipov. In work posted on the scientific preprint site in 2010, they described a quantum machine that sends photons through an optical circuit, which shifts and splits the light in quantum-mechanical ways, thereby generating output patterns with specific probabilities. Reproducing these patterns became known as boson sampling. Aaronson and Arkhipov reasoned that boson sampling would start to strain classical resources at around 30 photons—a plausible experimental target.

Similarly enticing were computations called instantaneous quantum polynomial, or IQP, circuits. An IQP circuit has gates that all commute, meaning they can act in any order without changing the outcome—in the same way 2 + 5 = 5 + 2. This quality makes IQP circuits mathematically pleasing. “We started studying them because they were easier to analyze,” Bremner said. But he discovered that they have other merits. In work that began in 2010 and culiminated in a 2016 paper with Montanaro and Dan Shepherd, now at the National Cyber Security Center in the U.K., Bremner explained why IQP circuits can be extremely powerful: Even for physically realistic systems of hundreds—or perhaps even dozens—of qubits, sampling would quickly become a classically thorny problem.

By 2016, boson samplers had yet to extend beyond 6 photons. Teams at Google and IBM, however, were verging on chips nearing 50 qubits; that August, Google quietly posted a draft paper laying out a road map for demonstrating quantum supremacy on these “near-term” devices.

Google’s team had considered sampling from an IQP circuit. But a closer look by Bremner and his collaborators suggested that the circuit would likely need some error correction—which would require extra gates and at least a couple hundred extra qubits—in order to unequivocally hamstring the best classical algorithms. So instead, the team used arguments akin to Aaronson’s and Bremner’s to show that circuits made of non-commuting gates, although likely harder to build and analyze than IQP circuits, would also be harder for a classical device to simulate. To make the classical computation even more challenging, the team proposed sampling from a circuit chosen at random. That way, classical competitors would be unable to exploit any familiar features of the circuit’s structure to better guess its behavior.

But there was nothing to stop the classical algorithms from getting more resourceful. In fact, in October 2017, a team at IBM showed how, with a bit of classical ingenuity, a supercomputer can simulate sampling from random circuits on as many as 56 qubits—provided the circuits don’t involve too much depth (layers of gates). Similarly, a more able algorithm has recently nudged the classical limits of boson sampling, to around 50 photons.

These upgrades, however, are still dreadfully inefficient. IBM’s simulation, for instance, took two days to do what a quantum computer is expected to do in less than one-tenth of a millisecond. Add a couple more qubits—or a little more depth—and quantum contenders could slip freely into supremacy territory. “Generally speaking, when it comes to emulating highly entangled systems, there has not been a [classical] breakthrough that has really changed the game,” Preskill said. “We’re just nibbling at the boundary rather than exploding it.”

That’s not to say there will be a clear victory. “Where the frontier is is a thing people will continue to debate,” Bremner said. Imagine this scenario: Researchers sample from a 50-qubit circuit of some depth—or maybe a slightly larger one of less depth—and claim supremacy. But the circuit is pretty noisy—the qubits are misbehaving, or the gates don’t work that well. So then some crackerjack classical theorists swoop in and simulate the quantum circuit, no sweat, because “with noise, things you think are hard become not so hard from a classical point of view,” Bremner explained. “Probably that will happen.”

What’s more certain is that the first “supreme” quantum machines, if and when they arrive, aren’t going to be cracking encryption codes or simulating novel pharmaceutical molecules. “That’s the funny thing about supremacy,” Montanaro said. “The first wave of problems we solve are ones for which we don’t really care about the answers.”

Yet these early wins, however small, will assure scientists that they are on the right track—that a new regime of computation really is possible. Then it’s anyone’s guess what the next wave of problems will be.

Correction on February 7, 2018: The original version of this article included an example of a classical version of a quantum algorithm developed by Christian Calude. Additional reporting has revealed that there is a strong debate in the quantum computing community as to whether the quasi-quantum algorithm solves the same problem that the original algorithm does. As a consequence, we have removed the mention of the classical algorithm.

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

Read more:

The Era of Quantum Computing Is Here. Outlook: Cloudy

After decades of heavy slog with no promise of success, quantum computing is suddenly buzzing with almost feverish excitement and activity. Nearly two years ago, IBM made a quantum computer available to the world: the 5-quantum-bit (qubit) resource they now call (a little awkwardly) the IBM Q experience. That seemed more like a toy for researchers than a way of getting any serious number crunching done. But 70,000 users worldwide have registered for it, and the qubit count in this resource has now quadrupled. In the past few months, IBM and Intel have announced that they have made quantum computers with 50 and 49 qubits, respectively, and Google is thought to have one waiting in the wings. “There is a lot of energy in the community, and the recent progress is immense,” said physicist Jens Eisert of the Free University of Berlin.

Quanta Magazine


Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

There is now talk of impending “quantum supremacy”: the moment when a quantum computer can carry out a task beyond the means of today’s best classical supercomputers. That might sound absurd when you compare the bare numbers: 50 qubits versus the billions of classical bits in your laptop. But the whole point of quantum computing is that a quantum bit counts for much, much more than a classical bit. Fifty qubits has long been considered the approximate number at which quantum computing becomes capable of calculations that would take an unfeasibly long time classically. Midway through 2017, researchers at Google announced that they hoped to have demonstrated quantum supremacy by the end of the year. (When pressed for an update, a spokesperson recently said that “we hope to announce results as soon as we can, but we’re going through all the detailed work to ensure we have a solid result before we announce.”)

It would be tempting to conclude from all this that the basic problems are solved in principle and the path to a future of ubiquitous quantum computing is now just a matter of engineering. But that would be a mistake. The fundamental physics of quantum computing is far from solved and can’t be readily disentangled from its implementation.

Even if we soon pass the quantum supremacy milestone, the next year or two might be the real crunch time for whether quantum computers will revolutionize computing. There’s still everything to play for and no guarantee of reaching the big goal.

IBM’s quantum computing center at the Thomas J. Watson Research Center in Yorktown Heights, New York, holds quantum computers in large cryogenic tanks (far right) that are cooled to a fraction of a degree above absolute zero.
Connie Zhou for IBM

Shut Up and Compute

Both the benefits and the challenges of quantum computing are inherent in the physics that permits it. The basic story has been told many times, though not always with the nuance that quantum mechanics demands. Classical computers encode and manipulate information as strings of binary digits—1 or 0. Quantum bits do the same, except that they may be placed in a so-called superposition of the states 1 and 0, which means that a measurement of the qubit’s state could elicit the answer 1 or 0 with some well-defined probability.

To perform a computation with many such qubits, they must all be sustained in interdependent superpositions of states—a “quantum-coherent” state, in which the qubits are said to be entangled. That way, a tweak to one qubit may influence all the others. This means that somehow computational operations on qubits count for more than they do for classical bits. The computational resources increase in simple proportion to the number of bits for a classical device, but adding an extra qubit potentially doubles the resources of a quantum computer. This is why the difference between a 5-qubit and a 50-qubit machine is so significant.

Note that I’ve not said—as it often is said—that a quantum computer has an advantage because the availability of superpositions hugely increases the number of states it can encode, relative to classical bits. Nor have I said that entanglement permits many calculations to be carried out in parallel. (Indeed, a strong degree of qubit entanglement isn’t essential.) There’s an element of truth in those descriptions—some of the time—but none captures the essence of quantum computing.

Inside one of IBM’s cryostats wired for a 50-qubit quantum system.
Connie Zhou for IBM

It’s hard to say qualitatively why quantum computing is so powerful precisely because it is hard to specify what quantum mechanics means at all. The equations of quantum theory certainly show that it will work: that, at least for some classes of computation such as factorization or database searches, there is tremendous speedup of the calculation. But how exactly?

Perhaps the safest way to describe quantum computing is to say that quantum mechanics somehow creates a “resource” for computation that is unavailable to classical devices. As quantum theorist Daniel Gottesman of the Perimeter Institute in Waterloo, Canada, put it, “If you have enough quantum mechanics available, in some sense, then you have speedup, and if not, you don’t.”

Some things are clear, though. To carry out a quantum computation, you need to keep all your qubits coherent. And this is very hard. Interactions of a system of quantum-coherent entities with their surrounding environment create channels through which the coherence rapidly “leaks out” in a process called decoherence. Researchers seeking to build quantum computers must stave off decoherence, which they can currently do only for a fraction of a second. That challenge gets ever greater as the number of qubits—and hence the potential to interact with the environment—increases. This is largely why, even though quantum computing was first proposed by Richard Feynman in 1982 and the theory was worked out in the early 1990s, it has taken until now to make devices that can actually perform a meaningful computation.

Quantum Errors

There’s a second fundamental reason why quantum computing is so difficult. Like just about every other process in nature, it is noisy. Random fluctuations, from heat in the qubits, say, or from fundamentally quantum-mechanical processes, will occasionally flip or randomize the state of a qubit, potentially derailing a calculation. This is a hazard in classical computing too, but it’s not hard to deal with—you just keep two or more backup copies of each bit so that a randomly flipped bit stands out as the odd one out.

Researchers working on quantum computers have created strategies for how to deal with the noise. But these strategies impose a huge debt of computational overhead—all your computing power goes to correcting errors and not to running your algorithms. “Current error rates significantly limit the lengths of computations that can be performed,” said Andrew Childs, the codirector of the Joint Center for Quantum Information and Computer Science at the University of Maryland. “We’ll have to do a lot better if we want to do something interesting.”

Andrew Childs, a quantum theorist at the University of Maryland, cautions that error rates are a fundamental concern for quantum computers.
Photo by John T. Consoli/University of Maryland

A lot of research on the fundamentals of quantum computing has been devoted to error correction. Part of the difficulty stems from another of the key properties of quantum systems: Superpositions can only be sustained as long as you don’t measure the qubit’s value. If you make a measurement, the superposition collapses to a definite value: 1 or 0. So how can you find out if a qubit has an error if you don’t know what state it is in?

One ingenious scheme involves looking indirectly, by coupling the qubit to another “ancilla” qubit that doesn’t take part in the calculation but that can be probed without collapsing the state of the main qubit itself. It’s complicated to implement, though. Such solutions mean that, to construct a genuine “logical qubit” on which computation with error correction can be performed, you need many physical qubits.

How many? Quantum theorist Alán Aspuru-Guzik of Harvard University estimates that around 10,000 of today’s physical qubits would be needed to make a single logical qubit—a totally impractical number. If the qubits get much better, he said, this number could come down to a few thousand or even hundreds. Eisert is less pessimistic, saying that on the order of 800 physical qubits might already be enough, but even so he agrees that “the overhead is heavy,” and for the moment we need to find ways of coping with error-prone qubits.

An alternative to correcting errors is avoiding them or canceling out their influence: so-called error mitigation. Researchers at IBM, for example, are developing schemes for figuring out mathematically how much error is likely to have been incurred in a computation and then extrapolating the output of a computation to the “zero noise” limit.

Some researchers think that the problem of error correction will prove intractable and will prevent quantum computers from achieving the grand goals predicted for them. “The task of creating quantum error-correcting codes is harder than the task of demonstrating quantum supremacy,” said mathematician Gil Kalai of the Hebrew University of Jerusalem in Israel. And he adds that “devices without error correction are computationally very primitive, and primitive-based supremacy is not possible.” In other words, you’ll never do better than classical computers while you’ve still got errors.

Others believe the problem will be cracked eventually. According to Jay Gambetta, a quantum information scientist at IBM’s Thomas J. Watson Research Center, “Our recent experiments at IBM have demonstrated the basic elements of quantum error correction on small devices, paving the way towards larger-scale devices where qubits can reliably store quantum information for a long period of time in the presence of noise.” Even so, he admits that “a universal fault-tolerant quantum computer, which has to use logical qubits, is still a long way off.” Such developments make Childs cautiously optimistic. “I’m sure we’ll see improved experimental demonstrations of [error correction], but I think it will be quite a while before we see it used for a real computation,” he said.

Living With Errors

For the time being, quantum computers are going to be error-prone, and the question is how to live with that. At IBM, researchers are talking about “approximate quantum computing” as the way the field will look in the near term: finding ways of accommodating the noise.

This calls for algorithms that tolerate errors, getting the correct result despite them. It’s a bit like working out the outcome of an election regardless of a few wrongly counted ballot papers. “A sufficiently large and high-fidelity quantum computation should have some advantage [over a classical computation] even if it is not fully fault-tolerant,” said Gambetta.

Lucy Reading-Ikkanda/Quanta Magazine

One of the most immediate error-tolerant applications seems likely to be of more value to scientists than to the world at large: to simulate stuff at the atomic level. (This, in fact, was the motivation that led Feynman to propose quantum computing in the first place.) The equations of quantum mechanics prescribe a way to calculate the properties—such as stability and chemical reactivity—of a molecule such as a drug. But they can’t be solved classically without making lots of simplifications.

In contrast, the quantum behavior of electrons and atoms, said Childs, “is relatively close to the native behavior of a quantum computer.” So one could then construct an exact computer model of such a molecule. “Many in the community, including me, believe that quantum chemistry and materials science will be one of the first useful applications of such devices,” said Aspuru-Guzik, who has been at the forefront of efforts to push quantum computing in this direction.

Quantum simulations are proving their worth even on the very small quantum computers available so far. A team of researchers including Aspuru-Guzik has developed an algorithm that they call the variational quantum eigensolver (VQE), which can efficiently find the lowest-energy states of molecules even with noisy qubits. So far it can only handle very small molecules with few electrons, which classical computers can already simulate accurately. But the capabilities are getting better, as Gambetta and coworkers showed last September when they used a 6-qubit device at IBM to calculate the electronic structures of molecules, including lithium hydride and beryllium hydride. The work was “a significant leap forward for the quantum regime,” according to physical chemist Markus Reiher of the Swiss Federal Institute of Technology in Zurich, Switzerland. “The use of the VQE for the simulation of small molecules is a great example of the possibility of near-term heuristic algorithms,” said Gambetta.

But even for this application, Aspuru-Guzik confesses that logical qubits with error correction will probably be needed before quantum computers truly begin to surpass classical devices. “I would be really excited when error-corrected quantum computing begins to become a reality,” he said.

“If we had more than 200 logical qubits, we could do things in quantum chemistry beyond standard approaches,” Reiher adds. “And if we had about 5,000 such qubits, then the quantum computer would be transformative in this field.”

What’s Your Volume?

Despite the challenges of reaching those goals, the fast growth of quantum computers from 5 to 50 qubits in barely more than a year has raised hopes. But we shouldn’t get too fixated on these numbers, because they tell only part of the story. What matters is not just—or even mainly—how many qubits you have, but how good they are, and how efficient your algorithms are.

Any quantum computation has to be completed before decoherence kicks in and scrambles the qubits. Typically, the groups of qubits assembled so far have decoherence times of a few microseconds. The number of logic operations you can carry out during that fleeting moment depends on how quickly the quantum gates can be switched—if this time is too slow, it really doesn’t matter how many qubits you have at your disposal. The number of gate operations needed for a calculation is called its depth: Low-depth (shallow) algorithms are more feasible than high-depth ones, but the question is whether they can be used to perform useful calculations.

What’s more, not all qubits are equally noisy. In theory it should be possible to make very low-noise qubits from so-called topological electronic states of certain materials, in which the “shape” of the electron states used for encoding binary information confers a kind of protection against random noise. Researchers at Microsoft, most prominently, are seeking such topological states in exotic quantum materials, but there’s no guarantee that they’ll be found or will be controllable.

Researchers at IBM have suggested that the power of a quantum computation on a given device be expressed as a number called the “quantum volume,” which bundles up all the relevant factors: number and connectivity of qubits, depth of algorithm, and other measures of the gate quality, such as noisiness. It’s really this quantum volume that characterizes the power of a quantum computation, and Gambetta said that the best way forward right now is to develop quantum-computational hardware that increases the available quantum volume.

This is one reason why the much vaunted notion of quantum supremacy is more slippery than it seems. The image of a 50-qubit (or so) quantum computer outperforming a state-of-the-art supercomputer sounds alluring, but it leaves a lot of questions hanging. Outperforming for which problem? How do you know the quantum computer has got the right answer if you can’t check it with a tried-and-tested classical device? And how can you be sure that the classical machine wouldn’t do better if you could find the right algorithm?

So quantum supremacy is a concept to handle with care. Some researchers prefer now to talk about “quantum advantage,” which refers to the speedup that quantum devices offer without making definitive claims about what is best. An aversion to the word “supremacy” has also arisen because of the racial and political implications.

Whatever you choose to call it, a demonstration that quantum computers can do things beyond current classical means would be psychologically significant for the field. “Demonstrating an unambiguous quantum advantage will be an important milestone,” said Eisert—it would prove that quantum computers really can extend what is technologically possible.

That might still be more of a symbolic gesture than a transformation in useful computing resources. But such things may matter, because if quantum computing is going to succeed, it won’t be simply by the likes of IBM and Google suddenly offering their classy new machines for sale. Rather, it’ll happen through an interactive and perhaps messy collaboration between developers and users, and the skill set will evolve in the latter only if they have sufficient faith that the effort is worth it. This is why both IBM and Google are keen to make their devices available as soon as they’re ready. As well as a 16-qubit IBM Q experience offered to anyone who registers online, IBM now has a 20-qubit version for corporate clients, including JP Morgan Chase, Daimler, Honda, Samsung and the University of Oxford. Not only will that help clients discover what’s in it for them; it should create a quantum-literate community of programmers who will devise resources and solve problems beyond what any individual company could muster.

“For quantum computing to take traction and blossom, we must enable the world to use and to learn it,” said Gambetta. “This period is for the world of scientists and industry to focus on getting quantum-ready.”

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

Read more:

Quantum Computing Is the Next Big Security Risk

The 20th century gave birth to the Nuclear Age as the power of the atom was harnessed and unleashed. Today, we are on the cusp of an equally momentous and irrevocable breakthrough: the advent of computers that draw their computational capability from quantum mechanics.



US representative Will Hurd (R-Texas) (@HurdOnTheHill) chairs the Information Technology Subcommittee of the Committee on Oversight and Government Reform and serves on the Committee on Homeland Security and the Permanent Select Committee on Intelligence.

The potential benefits of mastering quantum computing, from advances in cancer research to unlocking the mysteries of the universe, are limitless.

But that same computing power can be used to unlock different kinds of secrets—from your personal financial or health records, to corporate research projects and classified government intelligence.

It’s more than just theoretical: An algorithm formulated by mathematician Peter Shor demonstrates that quantum computers are able to factor large numbers more efficiently than classical computers. Large-number factoring is the foundation of today’s encryption standards.

The impact of quantum on our national defense will be tremendous. The question is whether the United States and its allies will be ready.

The consequences of mastering quantum computing, while not as visual or visceral as a mushroom cloud, are no less significant than those faced by the scientists who lit up the New Mexico sky with the detonation at the Trinity test site 72 years ago. In the same way that atomic weaponry symbolized power throughout the Cold War, quantum capability is likely to define hegemony in today’s increasingly digital, interconnected global economy.

Unlike traditional computers, which process information in binary bits, quantum computers exploit the ability of quantum bits (qubits) to exist in multiple states simultaneously. This allows them to perform incredibly complex calculations at speeds unimaginable today and solve certain classes of problems that are beyond the grasp of today’s most advanced super computers.

Today, quantum computers are beginning to move out of research labs in search of broader investment and applications. In October, Google announced that by the end of this year it expects to achieve quantum supremacy—the point at which a quantum computer can outperform a classical computer.

Because nations around the world, including China, are investing heavily in research and development, the world is likely less than a decade away from the day when a nation-state could use quantum computers to render many of today’s most sophisticated encryption systems useless.

From academics to the National Security Agency, there is widespread agreement that quantum computers will rock current security protocols that protect global financial markets and the inner workings of government.

Already, intelligence agencies around the world are archiving intercepted communications transmitted with encryption that's currently all but unbreakable, in the hopes that in the future computing advances will turn what’s gibberish now into potentially valuable intelligence. Rogue states may also be able to leverage the power of quantum to attack the banking and financial systems at the heart of western capitalism.

Everyone has seen the damage individual hackers can do when they infiltrate a system. Imagine a nation-state intercepting the encrypted financial data that flows across the globe and being able to read it as easily as you are reading this. Quantum computers are so big and expensive that—outside of global technology companies and well-funded research universities—most will be owned and maintained by nation-states. That means the first quantum attacks are likely to be organized by countries hostile to the US and our allies. Rogue states could read military communiques the way the United States and its allies did after cracking the Nazi Enigma codes.

In short, quantum computing presents both an unprecedented opportunity and a serious threat. The United States must lead this transition, in collaboration with its allies around the world. Whether lawmakers want to think of it as a new Manhattan Project or a race to the moon, the US cannot abdicate leadership in scientific discovery or international security.

The window is closing, fast. It took more than five years and nearly half a trillion dollars for companies and governments to prepare for Y2K, which resulted in a non-event for most people. But, the US is not ready for what experts call Y2Q (Years to Quantum), and the time to prepare is now. Even in a pre-quantum era, the need for quantum-safe encryption is real. Banks, government agencies, insurers, hospitals, utilities, and airlines all need to be thinking now about how to implement security and encryption that will withstand a quantum attack.

On complex, large-scale networks, it can take years to roll out even a relatively straightforward update. Quantum-safe encryption relies on mathematical approaches that even quantum computers have difficulty solving. The challenge is ensuring that every point through which data flows, and even the data itself, is wrapped in quantum-safe security.

Private sector research and development are happening in pockets across North America and among the US's allies. Google and IBM both have well-publicized programs to build viable quantum computers. At the same time, though, the US and its allies must take practical steps to prepare for the quantum threat. The National Institute of Standards and Technology is working to evaluate quantum-safe cryptographic candidate algorithms. Other organizations like the European Telecommunications Standards Institute and the United Nations’ International Telecommunications Union are working to ensure our standards for connecting systems continue to evolve to be quantum safe. Companies like ISARA are among a small cadre of cryptographers and programmers building quantum-safe security solutions to help high-risk industries and organizations begin protecting themselves.

It’s these kinds of efforts that the US and its allies must collaborate on to align the goals of scientific discovery, technological advancement, and national security. As companies build powerful quantum machines, leaders must simultaneously understand the risks those machines pose and the counter-measures required. Executives in every industry need to understand the implications that quantum computing will have on their legacy systems, and take steps to be ready. At a minimum, that means retrofitting their networks, computers, and applications with encryption that can withstand a quantum attack.

Nowhere is it more vital to begin preparations than with the vast network of governmental systems that do everything from processing Social Security checks to analyzing vast amounts of electronic intelligence.

Whether it was the discovery of fission or the launch of Sputnik, the United States has responded to scientific challenges of the past century with resolve and determination. The US must do the same with quantum computing.

WIRED Opinion publishes pieces written by outside contributors and represents a wide range of viewpoints. Read more opinions here.

Read more:

Researchers create a light-based key distribution system for quantum encryption

Researchers at Duke University, OSU and Oak Ridge National Laboratory have solved one of the biggest problems with new forms of quantum encryption: quantum key distribution. QKD is the process of distributing keys during a transmission and in a way that will tell both sides of the conversation that someone is eavesdropping. The new system, which uses lasers to transmit multiple bits at once, can be used to connect and secure quantum computers in the future.

“We are now likely to have a functioning quantum computer that might be able to start breaking the existing cryptographic codes in the near future,” said Daniel Gauthier, a professor of physics at The Ohio State University. “We really need to be thinking hard now of different techniques that we could use for trying to secure the internet.”

Their paper is available here.

Most current QKD systems transmit data “between tens to hundreds of kilobytes per second,” a rate not sufficient for most uses, including chat and telephony. The researchers can inject more information into each photon transmitted by adjusting the release time and the phase, thereby encoding two bits instead of just one. This means they can transmit keys quickly and securely and, more importantly, over fast fiber optic cables.

The system uses off-the-shelf parts and, barring the detectors, nothing unavailable to normal telecommunications providers.

“All of this equipment, apart from the single-photon detectors, exist in the telecommunications industry, and with some engineering we could probably fit the entire transmitter and receiver in a box as big as a computer CPU,” said Duke graduate student Nurul Taimur Islam.

Read more:

Quantum Computing Is Real, and D-Wave Just Open-Sourced It

Quantum computing is real. But it’s also hard. So hard that only a few developers, usually trained in quantum physics, advanced mathematics, or most likely both, can actually work with the few quantum computers that exist. Now D-Wave, the Canadian company behind the quantum computer that Google and NASA have been testing since 2013, wants to make quantum computing a bit easier through the power of open source software.

Traditional computers store information in “bits,” which can represent either a “1” or a “0.” Quantum computing takes advantage of quantum particles in a strange state called “superposition,” meaning that the particle is spinning in two directions at once. Researchers have learned to take advantage of these particles to create what they call “qubits,” which can represent both a 1 and a 0 at the same time. By stringing qubits together, companies like D-Wave hope to create computers that are exponentially faster than today’s machines.

IBM demonstrated a working quantum computer in 2000 and continues to improve on its technology. Google is working on its own quantum computer and also teamed up with NASA to test D-Wave’s system in 2013. Lockheed Martin and the Los Alamos National Laboratory are also working with D-Wave machines. But today’s quantum computers still aren’t practical for most real-world applications. qubits are fragile and can be easily knocked out of the superposition state. Meanwhile, quantum computers are extremely difficult to program today because they require highly specialized knowledge.

“D-Wave is driving the hardware forward,” says D-Wave International president Bo Ewald. “But we need more smart people thinking about applications, and another set thinking about software tools.”

That’s where the company’s new software tool Qbsolv comes in. Qbsolv is designed to help developers program D-Wave machines without needing a background in quantum physics. A few of D-Wave’s partners are already using the tool, but today the company released Qbsolv as open source, meaning anyone will be able to freely share and modify the software.

“Not everyone in the computer science community realizes the potential impact of quantum computing,” says Fred Glover, a mathematician at the University of Colorado, Boulder who has been working with Qbsolv. “Qbsolv offers a tool that can make this impact graphically visible, by getting researchers and practitioners involved in charting the future directions of quantum computing developments.”

qubits for All

Qbsolv joins a small but growing pool of tools for would-be quantum computer programmers. Last year Scott Pakin of Los Alamos National Laboratory–and one of Qbsolv’s first users–released another free tool called Qmasm, which also eases the burden of writing code for D-Wave machines by freeing developers from having to worry about addressing the underlying hardware. The goal, Ewald says, is to kickstart a quantum computing software tools ecosystem and foster a community of developers working on quantum computing problems. In recent years, open source software has been the best way to build communities of both independent developers and big corporate contributors.

Of course to actually run the software you create with these tools, you’ll need access to one of the very few existing D-Wave machines. In the meantime, you can download a D-Wave simulator that will let you test the software on your own computer. Obviously this won’t be the same as running it on a piece of hardware that uses real quantum particles, but it’s a start.

Last year, IBM launched a cloud-based service that enables people to run their own programs on the company’s quantum computer. But at least for the moment, Qbsolv and Qmasm will only be useful for creating applications for D-Wave’s hardware. D-Wave’s machines take a radically different approach to computing than traditional computers, or even other quantum computing prototypes. While most computersranging from your smartphone to IBM’s quantum computerare general purpose, meaning they can be programmed to solve all sort of problems, D-Wave’s machines are designed for a single purpose: solving optimization problems. The classic example is known as the traveling salesman problem: calculating the shortest route that passes through a list of specific locations.

In the early days, critics wondered whether D-Wave’s expensive machines were even quantum computers at all, but most researchers now seem to agree that the machines do exhibit quantum behavior. “There are very few doubts left that there are indeed quantum effects at work and that they play a meaningful computational role,” University of Southern California researcher Daniel Lidar told us in 2015 after Google and NASA released a research paper detailing some of their work with the D-Wave. The big question now is whether D-Waves are actually any faster than traditional computers, and if its unique approach is better than that taken by IBM and other researchers.

Pakin says his team are believers in D-Waves potential, even though they admit its systems might not yet offer performance improvements except in very narrow cases. He also explains that D-Wave’s computers don’t necessarily provide the most efficient answers to an optimization problemor even a correct one. Instead, the idea is to provide solutions that are probably good, if not perfect solutions, and to do it very quickly. That narrows the D-Wave machines’ usefulness to optimization problems that need to be solved fast but don’t need to be perfect. That could include many artificial intelligence applications.

Ideally, however, the hardware and software will improve to the point that other types of computing problems can be translated into optimization problems, and Qbsolv and Qmasm are steps towards building exactly that. But to get there, they’ll need more than just open source software. They’ll need an open source community.

Read more: