Preparing for a literal quantum leap in computing
August 1, 2018
Craig TylerA true, universal, and fault-tolerant quantum computer exists only in concept. If built, it could create, maintain, and manipulate information in quantum bits, or qubits, to perform calculations that normal computers have so far been unable to do efficiently. Because in this context “do efficiently” could mean “do within our lifetime,” a true quantum computer would represent, quite literally, a quantum leap in computing.
The concept goes roughly like this: You prepare subatomic particles representing qubits in a particular state (say, all in the ground state, representing all zeros). You perform some operation on them (say, fire a series of laser pulses), causing them to interact in a prescribed way, and then measure some property that corresponds, with a high probability, to the correct answer to a computational problem. It’s a tall order because of the difficulty in isolating the submicroscopic particles from all external influences, while at the same time being able to manipulate them and extract information from them.
Partial quantum computers already exist—machines that offer a particular mechanism for working with qubits, allowing them to do a subset of the tasks a true quantum computer could do—and Los Alamos is one of the few institutions that has one [see “Not Magic, Quantum,” in the July 2016 issue of 1663]. For both the partial quantum computer already on site and the true quantum computer of the future, Los Alamos’s Rolando Somma is working to develop the algorithms needed to unleash the full potential.
“We can’t categorically state that classical computers are incapable of doing what quantum computers can do,” says Somma. “Someone could always discover a new way to do things classically. But these efforts have all failed so far, and in many cases, we have found a more natural quantum algorithm that does the trick.”
A classical computer bit is a two-level structure, 0 or 1. It can be manipulated via a logical operation called a gate, such as the NOT gate (which converts 0s into 1s and 1s into 0s) or the AND gate (which combines two bits such that two 1s combine to return 1 and other combinations return 0). Deep down, computer routines, such as if-then instructions or arithmetic computations, are built from logical gates like these.

A qubit is also built from a two-level structure, but in addition to 0 and 1, it can exist in a superposition, or mixture, of both 0 and 1. So in addition to classical logical gates, a qubit can also support additional, purely quantum gates, such as the Hadamard gate (which converts a 0 or 1 into an equal superposition of 0 and 1) or the phase gate (which attaches a phase to a 0 or 1, affecting probabilistic quantum behavior). In principle, any advanced computational algorithm can be approximated by a combination of these two quantum gates, plus some classical ones. In practice, however, one first needs a physical machine capable of reliably working with qubits.
A qubit can be made from any quantum two-level system: atoms or ions with two accessible energy levels, particles spinning one direction or the other, photons polarized horizontally or vertically, and so on. To compute with such a qubit, the two levels must be interchangeable via technological manipulation, such as a laser pulse. In the case of Los Alamos’s partial quantum computer, called a quantum annealer, the qubits are built from superconducting loops whose two states are electrical currents circulating one direction or the other, manipulated magnetically with a device called a Josephson junction.
Quantum annealing has been shown to perform well for optimization problems, as in graph theory and related search problems, including searching a database, and in other calculations that can be readily mapped into optimization problems. It does not appear to be as promising for better-known, true quantum-computing problems, such as codebreaking and, perhaps unsurprisingly, modeling physical systems that are dominated by quantum effects.
Somma is designing quantum-computing algorithms for complex material simulations, including the well-known Hubbard model. The model describes at a quantum level—as contrasted with the usual approximations, which gloss over quantum interactions—the properties of a lattice of atoms in which some electrons are able to move from one atom to the next. It is an excellent model for electrical conductivity and, importantly, superconductivity. In particular, it may help explain a phenomenon called high-temperature superconductivity, which could allow for the construction of loss-free circuits and transmission lines, presently possible only at low temperatures obtained with cryogenic laboratory equipment. (The quantum annealer itself relies on a sophisticated series of cryogenic “fridges” to isolate its superconducting qubits at one hundredth of a degree above absolute zero.) And Hubbard-model computations of high-temperature superconductivity may be forever beyond the domain of classical computers.
“The best classical supercomputers today can only handle maybe 40 electrons in a Hubbard model lattice—40 qubits on a quantum computer,” says Somma. “And even if we allow the computing time of that classical computer to double, we would probably only gain the equivalent of one additional qubit.” By contrast, the quantum annealer at Los Alamos processes about 1000 qubits (although it is limited in which gates it can apply to them), and a future quantum computer, it is hoped, would process several million.
Somma is busily preparing for that day, developing quantum-computing algorithms that can be made either with a complete set of quantum gates or with a partial set of quantum operations, as in quantum-annealing applications. He is identifying which problems can be solved efficiently by quantum annealing—including, he found, certain linear algebra computations and simulations of low-temperature but nonquantum physical systems. Meanwhile, the “quantum algorithm zoo,” an online compilation of known quantum-computing algorithms put forward by a colleague of Somma’s, stands at about 60-strong and growing.
“It’s an exciting time,” says Somma. “Some of these are likely to be real game changers.”