Communications of the ACM

ACM News

The Soft Side of Quantum Computing

By Arnout Jaspers
June 1, 2017
Comments

Quantum computing is no longer a futuristic endeavor; it's already on-line. IBM has a website, Quantum Experience, where one can operate five real-world qubits, the building blocks of a quantum computer. Visitors can subject these qubits to various elementary programming operations (the equivalent of logic gates like AND and XOR in classical computing) and read out the resulting bit values (0 or 1).

No intuition

Hoever, five qubits are not nearly enough to calculate something interesting. In principle, one could use them to determine that 15 = 3 x 5. Even if 50 qubits were available—a target Google has set itself for the end of this year—we would have only very limited options to do interesting calculations with them.

A big part of the problem is that a quantum computer, like a classical computer, needs to execute an algorithm, but quantum algorithms are fundamentally different from classical ones. Ronald Hanson, scientific director at QuTech, a quantum physics research center in Delft, the Netherlands, explains, "Classical computing runs closely parallel to how we experience the world; it's basically like operating a big abacus. Qubits exhibit these strange quantum properties, superposition and entanglement, and we have to exploit those, but we have no intuition about that, so only a few examples of quantum algorithms are known. These were found by brilliant people in a stroke of genius. At this time, there is no general method to construct other quantum algorithms."

A case in point is Shor's algorithm, with which a quantum computer can factorize a large integer N exponentially faster than a classical computer can. Classically, finding the prime factors of N boils down to trying out lots of candidates, and if N has 200 digits, the number of candidates is just too large. The security of RSA, used to encrypt crucial parts of Tnternet data traffic, depends on that.

Shor's algorithm uses the quantum magic of superposition to let all the qubits zoom in simultaneously on a factor of N, resulting in much greater speed. To crack RSA, a quantum computer with perhaps 2,000 qubits would be needed. However, Shor's algorithm cannot be adapted to do other calculations, like finding the shortest route around a large number of cities (another infamous problem that can't be solved efficiently via classical means).

Is it just a stroke of luck that a quantum algorithm is known for a problem that is highly relevant, or is this circumstantial evidence that other useful quantum algorithms are out there? Nobody really knows.          

QuTech puts most of its effort in developing hardware, but also has theoretical physicists working on algorithms for quantum computers and the small quantum Internet that is now under construction. 

Fundamental research on quantum algorithms got a boost from the founding of QuSoft, a collaboration of several institutes for mathematics, computer science and physics, last December. Director Harry Buhrman summarizes QuSoft's mission as: "Not every computation can be speeded up exponentially with a quantum computer. We need to investigate now what quantum software will be able to do and what not. When the quantum computer arrives on the scene, it's too late."

Because of Shor's algorithm, we know that a quantum computer will break RSA. What other cryptographic systems are no longer safe? Progress has been made already on constructing cryptographic schemes that are secure in a quantum world, but there is still much to explore.   

Also, QuSoft wants to get familiar with the experiments at this early stage, when only five or ten qubits in superposition are available. In terms of standard operations—those visitors can apply to the qubits on the IBM website—not much can be done. Yet talking to experimental physicists at QuTech and elsewhere has given Buhrman and his colleagues some ideas on how to make better use of a small number of qubits. Instead of regarding the qubits as abstract programming entities, it pays to look into their physical nuts and bolts. "We want to get even closer to the qubits," says Buhrman. "If we can exploit that, it would give us an even lower-level but richer programming language."

Quantum supremacy

While a system of multiple classical bits can be analyzed step-by-step, 50 qubits in superposition are an indivisible entity that can be in 2⁵⁰ possible states, far too many to be simulated on a classical computer.

Although Buhrman is skeptical Google can achieve 50 qubits by the end of the year, such an achievement would cross a threshold: "With 50 to 100 qubits, one can achieve 'quantum supremacy', which means doing something which can not be done classically." While this still falls short of doing a useful quantum computation, such a quantum machine will deliver a distribution (a very large set) of 50 bit values each, which cannot be produced by a classical computer.

This leaves the experts with a curious problem, says Buhrman; "How do we verify that this distribution is what we expect it to be?" A classical computation can be interrupted at any point to check what all the bit values are at that stage; if one interrupts a quantum computation in progress, the superposed qubits degenerate to just a bunch of random zeros and ones. In general, verifying that a quantum algorithm really does what its designers intend is highly non-trivial, and another focal point of QuSoft's research.

In the long run, Buhrman says, the resources invested in quantum software may outgrow those devoted to quantum hardware, the way it is in classical computing now. Quantum physicists are also becoming aware the interesting science is not only in the hardware.

Says QuTech's Hanson, "We really want to prepare the Netherlands for the future in this field."

The Dutch science organization NWO apparently has gotten the message; on May 8, it announced 18.8 million euros (US$20.4 million) in funding for research that includes a "Quantum Software Consortium" that will bring together researchers from computer science, mathematics, and physics "to invent and demonstrate the first applications for [quantum] computers and the Internet of the future."

Also, in April QuSoft signed a collaboration agreement with quantum computing groups in France and Latvia.

Then there's the European Union; once it decides to spend, it spends big. Quantum technology is now one of three EU flagship research programs that will each get a billion euros (US$1.09 billion) .

Says QuSoft's Buhrman, "Quantum software is becoming an integral part of that program as well."

Arnout Jaspers is a freelance science writer based in Leiden, the Netherlands

---

No entries found