August 22, 2019 — An international team of researchers, including Lawrence Livermore National Laboratory (LLNL) physicist Arjun Gambhir, has developed a new algorithm for solving polynomial systems of equations using a type of quantum computer called a “quantum annealer.” The team systematically examined how this method scales when facing increasingly difficult mathematical equations, with promising results.

It has been theorized that quantum computers would enable researchers to solve problems much faster than they could with classical computing, or even tackle problems too complex for today’s supercomputers, but that “quantum speedup” has not yet been realized. This study provides evidence that quantum annealing could one day deliver these gains. The research was published July 16 in Nature Scientific Reports.

“We found that problems that are really hard to solve with classical computing scale differently with quantum annealing,” said LLNL physicist Gambhir. “It was really interesting. When we made problems harder, the annealer didn’t have any more trouble, and in some cases the harder problems were actually easier to solve.”

To test how their algorithm would scale to problems of varying complexity, the team deployed the method on the commercially available D-Wave 2000Q quantum annealer. They started by running fairly simple problems and validated the output to make sure they were getting correct answers. The team then made the problems incrementally larger and more complex to systematically evaluate how the quantum annealer might compare to classical computing.

The team found that problems scale different with quantum annealing. While the approach scaled proportionally when it came to problem size, they got a surprising result when they increased the complexity of problems, expressed by the equation’s “condition number.” The quantum annealer was able to solve more complex problems just as easily as simple problems, and in some cases, the quantum annealer had an easier time with the complex problems.

“When I try to describe how a quantum annealer works, people often look at me like it runs on magic,” Gambhir said. “In a way it does; it runs on the magic of quantum physics. In some ways, it’s easier to understand by comparing it to metalworking than classical computer science.”

Quantum annealing works by leveraging a fundamental rule of physics: Physical systems tend to seek out their lowest-energy state. Metalworkers have been leveraging the process of annealing for hundreds of years to help make hardened tools and knives more ductile. They do so by carefully heating already-hardened metal, which excites the atomic structure in a controlled way, and then allowing it to cool so that the metal can recrystallize in a lower, less-brittle energy state. Quantum annealing is analogous to that process.

In classical computers, electricity is applied to transistors to switch their state to either a 1 or a 0. This single binary value — a 1 or a 0 — is called a bit. Instead of using transistors to process information, quantum annealers use tiny, niobium tubes supercooled to 0.7 degrees Kelvin (to put that into perspective, a warm room is around 300 degrees Kelvin and deep space is 3 degrees Kelvin). This environment changes the properties of the niobium tubes into superconductors, which allows them to relax to lower energy states with virtually zero resistance. These superconductors act as “qubits” and are the heart of how the quantum annealer solves problems.

To program the mathematical problem into the quantum annealer, researchers apply magnetic fields to the qubits to configure their initial state as a 1, a 0 or some superposition state of the qubit being both at once. They also “entangle” the qubits by specifying how each qubit should react to its neighbors. Energizing and entangling the qubits is similar to a metalworker heating up a knife for annealing. At this point, the researchers simply let the qubits naturally relax into their lowest energy state, just like the metalworker allows the knife to cool and recrystallize. It takes less than 200 microseconds for the qubits to find their end state, at which time the researchers can measure whether each qubit ended up as a 1 or a 0. If programmed properly, this end state is the answer to the problem.

“It’s crazy that I’m writing code for a quantum computer,” Gambhir said. “It’s so different than code development for other high-performance machines. That’s what’s so fascinating about this. If these quantum computers scale the way we think they might, it could help us leapfrog Moore’s Law for certain problems.”

Researchers from Lawrence Berkeley National Laboratory, Oak Ridge National Laboratory and the RIKEN Computational Materials Science Research Team also participated in the study. The study was supported by the  Department of Energy Office of Science and by Oak Ridge National Laboratory and its Laboratory Directed Research and Development funds. The Oak Ridge Leadership Computing Facility is supported by the DOE Office of Science’s Advanced Scientific Computing Research program.

---

Source Lawrence Livermore National Laboratory (LLNL)