Computer science’s ‘Nobel Prize’ goes quantum

The biggest prize in computer science, the A.M. Turing Award, has for the first time honored work in the quantum realm. This year, Charles Bennett, a physicist at IBM, and Gilles Brassard, a computer scientist at the University of Montreal, share the $1 million award for “their essential role in establishing the foundations of quantum information science,” according to the Association for Computing Machinery, which awarded the prize today. It’s another signal that systems designed to exploit the strange and counterintuitive rules of quantum mechanics will shape the future of computing. Sometimes called the Nobel Prize of computer science, the 60-year-old Turing Award has honored multiple technological advances that are now ubiquitous, such as the internet and the World Wide Web. In contrast, a full-fledged quantum computer does not yet exist. Nevertheless, Bennett and Brassard have prepared the ground for the much-anticipated quantum revolution, says Ueli Maurer, a computer scientist at ETH Zürich. “It’s the intellectual foundation: How can we exploit quantum effects?” he says. Harry Buhrman, a computer scientist at the University of Amsterdam who works on quantum computing, says the award winners “had the spark of this idea that turned into this quantum fire we’re in now.” Ordinary computers work by flipping microscopic electrical switches called bits to signify a 0 or a 1. In contrast, a quantum computer or system manipulates qubits that have well-defined quantum states, such as a photon that can be polarized horizontally, vertically, or both ways at once. Unlike a bit, a qubit can be set to 0 and 1 at the same time—at least until it’s measured, when a qubit collapses randomly to either 0 or 1. In addition, two qubits can share a mysterious link called entanglement. When qubits are entangled, the state of each one is uncertain—both 0 and 1—but the particles’ states are correlated. For example, two quantum particles can be entangled so that if one is measured and collapses, say to 1, the other is sure to collapse the same way, too. Bennett and Brassard were among the first to explore the ways in which such quantum phenomena could be used to encode and transmit information. The two began working together in 1979, when both attended a computing conference in San Juan, Puerto Rico. When Bennett learned Brassard shared his then-peculiar interest in combining quantum mechanics and information theory, he looked for a chance to approach him privately—which turned out to be while they were at the beach. “A complete stranger swims up to me and tells me a friend of his has found a way [in principle] to use quantum mechanics to make bank notes that would be impossible to counterfeit,” Brassard recalls. Since then, Bennett and Brassard have collaborated on more than two dozen papers. “You put us in a room and the ideas just spark,” Brassard says. “It’s magic.” In 1984, Bennett and Brassard invented a protocol that allows two parties who want to share a secret message to establish a secure key for scrambling and unscrambling the message by exchanging single photons. The scheme exploits the fact that, according to quantum mechanics, an eavesdropper can’t measure the quantum states of the photons without changing them and revealing the snooping. The paper kicked off the subfield of quantum cryptography, and quantum key distribution systems are now sold commercially. In 1993, Bennett, Brassard, and colleagues predicted that entanglement can be used to transfer or “teleport” the unknown state of one quantum particle to a distant one. In 1996, they and colleagues showed how to use multiple imperfectly entangled pairs of particles to generate a smaller number of more completely entangled pairs in so-called entanglement distillation. Both quantum teleportation and entanglement distillation will likely be essential to the functioning of a full-fledged quantum computer. Other researchers also helped launch the endeavor of quantum computing. “Gilles and I have gotten a lot of prizes together, and often we get them together with Peter Shor and David Deutsch,” Bennett says, referring, respectively, to the mathematician at the Massachusetts Institute of Technology and the physicist at the University of Oxford who are often credited with initiating the quest to build a quantum computer. Other researchers say a future Turing prize may honor Deutsch and Shor. Jack Dongarra, a computer scientist at the University of Tennessee, Knoxville and a Turing Award winner himself, says that compared with previous awards, this year’s prize emphasizes potential more than technological accomplishment. They’re sending a message,” says Dongarra, an expert in classical algorithms. “That message is that this is an important area, we need to focus attention on it, and it’s going to have a big impact in the future.”