What Sorts Of Problems Are Quantum Computers Good For?

A couple of weeks ago, the APS’s Physics ran a piece titled Traveling with a Quantum Salesman, about a quantum computing approach to the famous “Traveling Salesman” problem. I saw the headline, and immediately thought “Oh, yeah, of course that would be a good problem for a quantum computer…” The paper in question is far enough from my core expertise that I can’t really do better than the original Physics piece in terms of explaining what the researchers did and why it matters. My reaction to it, though, seems like a useful jumping-off point for a post correcting some misconceptions about how quantum computers really work, and what they’re good for. Justin Trudeau, Canada’s prime minister, gestures as he speaks during a panel session at the World Economic Forum. Photographer: Matthew Lloyd/Bloomberg. The most common non-technical way to explain quantum computers is to talk in terms of added power from having the ability to put bits in superposition states. Or, as the Prime Minister of Canada famously put it:

Normal computers work, either there’s power going through a wire or not. It’s 1 or a 0. They’re binary systems. What quantum states allow for is much more complex information to be encoded into a single bit. A regular computer bit is either a 1 or 0—on or off. A quantum state can be much more complex than that because as we know, things can be both particle and wave at the same time and the uncertainty around quantum states allows us to encode more information into a much smaller computer. That’s what exciting about quantum computing.

That’s not a terrible explanation, and even experts in the field, asked to match Trudeau’s explanation mostly resort to variations of this: a classical bit is either “0” or “1,” but a qubit can be an arbitrary superposition of “0” and “1,” which dramatically increases your options when calculating stuff. It’s not the whole story, though, and leaves many people with the impression that quantum computers are a logical means of extending “Moore’s Law” to continue making more powerful computers once we hit physical limits on classical chips. In fact, even when quantum computers are finally built, they’re likely to remain highly specialized instruments, for the simple reason that they really only offer an advantage for certain special kinds of problems. Why is that? Well, you can get some sense of the reason from one of the answers in that Maclean’s piece, from quantum computing theorist (and physics blogger) Scott Aaronson:

A quantum computer is a proposed device that exploits quantum mechanics to solve certain specific problems like factoring huge numbers much faster than we know how to solve them with any existing computer. Quantum mechanics has been the basic framework of physics since the 1920s. It’s a generalization of the rules of probability themselves. From day to day life, you’d never talk about a minus-20 per cent chance of something happening, but quantum mechanics is based on numbers called amplitudes, which can be positive or negative or even complex numbers. The goal in quantum computing is to choreograph things so that some paths leading to a wrong answer have positive amplitudes and others have negative amplitudes, so on the whole they cancel out and the wrong answer is not observed.

That’s maybe not as smooth as Trudeau’s explanation– it introduces some jargon terms, and seems to take a weird turn halfway through (though it makes sense by the end)– but it’s a more correct and complete explanation. And, more importantly, it points to why quantum computers are definitively better than classical computers for only a limited set of problems. Waves coming together in complicated ways. The key fact that Aaronson brings out, that’s often hidden by talk about qubits in superposition states, is that quantum computers are all about waves and probability. That’s fundamentally what lets your qubits be in a superposition in the first place– what you can predict is a probability of finding a particular outcome, and that probability comes from amplitudes that have wave-like properties and aren’t confined to a single state. So, in a sense, quantum computing is properly understood as a process of engineering the pattern of a complex set of waves, in hopes of channeling the flow toward the correct answer. Of course, this is vastly complicated by the fact that we generally don’t know what the answer is in advance, so it’s not just a simple matter of laying out a single channel, but trying to stir up a set of waves in the open ocean that somehow all come together to make one big splash. See the original article here

Advertisements

South Carolina high schools could require computer coding course for graduation

Want a high school diploma? You might need to learn a little bit of JavaScript. All South Carolina public schools could require computer-science training for graduation starting as soon as 2019. A bill advancing out of the state House of Representatives would create new standards for computer science education in grades 9-12, set up summer training for new teachers in the field and require that every high school in the state offer at least one computer science course. The state currently requires one credit of “computer science” for a high school diploma, but that credit can be for a keyboarding class — a far cry from the rigorous and standards-based courses that some state lawmakers say would give students a leg up as they enter an increasingly knowledge-based workforce. “At this rate, we’ll be ahead of the curve,” said Valerie Sessions, chair of the Computer Science Department at Charleston Southern University. She recently signed an open letter in support of the bill along with leaders from Boeing, Google and Bibliolabs. House Bill 3427, the SC Computer Science Education Initiative, passed in the House with a 106-1 vote Tuesday and advanced to the Senate. It includes $1.36 million in new expenditures over the next two years to develop grade-appropriate standards, hire a state computer science education coordinator, fund summer teacher training camps and provide other support. But the bill does not set aside recurring funds to support computer science education or provide school districts with more money to hire additional teachers. The hiring of computer science teachers could cost local school districts a combined $19.2 million in the 2019-20 school year alone, according to an estimate included with the bill. Quinn Burke, an assistant professor of education at the College of Charleston, helped write computer science standards for kindergarten through eighth grade. When it comes to the high school proposal, he’s concerned about the lack of recurring funds for teachers. “To be offering computer science education in South Carolina schools for 2019 but putting absolutely no money behind it — that’s a tremendous problem,” Burke said. “I have concerns that if it’s not properly funded and supported, by 2020 we’ll be scratching our heads saying, ‘This was a waste, it was ill-conceived.'” But if it works, Burke said, students will be prepared for all sorts of tech-centric careers. Some districts already teach block-based introductory coding languages in elementary school. By the time students leave high school, they could have the tools to learn new languages and thrive in whatever environment awaits them. The earlier the head start, the better. “Kids are a lot more willing to tinker at things for longer periods of time, whereas adults, their concentration level peters out,” Burke said. Read the original article here