**Is your Supercomputer Stumped? There May Be a Quantum Solution**

Berkeley Lab-led team solves a tough math problem with quantum computing

Some math problems are so complicated that they can bog down even the world’s most powerful supercomputers. But a wild new frontier in computing that applies the rules of the quantum realm offers a different approach.

A new study led by a physicist at Lawrence Berkeley National Laboratory (Berkeley Lab), published in the journal Scientific Reports, details how a quantum computing technique called “quantum annealing” can be used to solve problems relevant to fundamental questions in nuclear physics about the subatomic building blocks of all matter. It could also help answer other vexing questions in science and industry, too.

**Seeking a quantum solution to really big problems**

“No quantum annealing algorithm exists for the problems that we are trying to solve,” said Chia Cheng “Jason” Chang, a RIKEN iTHEMS fellow in Berkeley Lab’s Nuclear Science Division and a research scientist at RIKEN, a scientific institute in Japan.

“The problems we are looking at are really, really big,” said Chang, who led the international team behind the study, published in the Scientific Reports journal. “The idea here is that the quantum annealer can evaluate a large number of variables at the same time and return the right solution in the end.”

The same problem-solving algorithm that Chang devised for the latest study, and that is available to the public via open-source code, could potentially be adapted and scaled for use in systems engineering and operations research, for example, or in other industry applications.

**Classical algebra with a quantum computer**

“We are cooking up small ‘toy’ examples just to develop how an algorithm works. The simplicity of current quantum annealers is that the solution is classical – akin to doing algebra with a quantum computer. You can check and understand what you are doing with a quantum annealer in a straightforward manner, without the massive overhead of verifying the solution classically.”

Chang’s team used a commercial quantum annealer located in Burnaby, Canada, called the D-Wave 2000Q that features superconducting electronic elements chilled to extreme temperatures to carry out its calculations.

Access to the D-Wave annealer was provided via the Oak Ridge Leadership Computing Facility at Oak Ridge National Laboratory (ORNL). “These methods will help us test the promise of quantum computers to solve problems in applied mathematics that are important to the U.S. Department of Energy’s scientific computing mission,” said Travis Humble, director of ORNL’s Quantum Computing Institute.

**Quantum data: A one, a zero, or both at the same time**

There are currently two of these machines in operation that are available to the public. They work by applying a common rule in physics: Systems in physics tend to seek out their lowest-energy state. For example, in a series of steep hills and deep valleys, a person traversing this terrain would tend to end up in the deepest valley, as it takes a lot of energy to climb out of it and the least amount of energy to settle in this valley.

The annealer applies this rule to calculations. In a typical computer, memory is stored in a series of bits that are occupied by either one or a zero. But quantum computing introduces a new paradigm in calculations: quantum bits, or qubits. With qubits, information can exist as either a one, a zero, or both at the same time. This trait makes quantum computers better suited to solving some problems with a very large number of possible variables that must be considered for a solution.

Each of the qubits used in the latest study ultimately produces a result of either a one or a zero by applying the lowest-energy-state rule, and researchers tested the algorithm using up to 30 logical qubits.

The algorithm that Chang developed to run on the quantum annealer can solve polynomial equations, which are equations that can have both numbers and variables and are set to add up to zero. A variable can represent any number in a large range of numbers.

**When there are ‘fewer but very dense calculations’**

Berkeley Lab and neighboring UC Berkeley have become a hotbed for R&D in the emerging field of quantum information science, and last year announced the formation of a partnership called Berkeley Quantum to advance this field.

Chang said that the quantum annealing approach used in the study, also known as adiabatic quantum computing, “works well for fewer but very dense calculations,” and that the technique appealed to him because the rules of quantum mechanics are familiar to him as a physicist.

The data output from the annealer was a series of solutions for the equations sorted into columns and rows. This data was then mapped into a representation of the annealer’s qubits, Chang explained, and the bulk of the algorithm was designed to properly account for the strength of the interaction between the annealer’s qubits. “We repeated the process thousands of times” to help validate the results, he said.

“Solving the system classically using this approach would take an exponentially long time to complete, but verifying the solution was very quick” with the annealer, he said, because it was solving a classical problem with a single solution. If the problem was quantum in nature, the solution would be expected to be different every time you measure it.

**Real-world applications for a quantum algorithm**

As quantum computers are equipped with more qubits that allow them to solve more complex problems more quickly, they can also potentially lead to energy savings by reducing the use of far larger supercomputers that could take far longer to solve the same problems.

The quantum approach brings within reach direct and verifiable solutions to problems involving “nonlinear” systems – in which the outcome of an equation does not match up proportionately to the input values. Nonlinear equations are problematic because they may appear more unpredictable or chaotic than other “linear” problems that are far more straightforward and solvable.

Chang sought the help of quantum-computing experts in quantum computing both in the U.S. and in Japan to develop the successfully tested algorithm. He said he is hopeful the algorithm will ultimately prove useful to calculations that can test how subatomic quarks behave and interact with other subatomic particles in the nuclei of atoms.

While it will be an exciting next step to work to apply the algorithm to solve nuclear physics problems, “This algorithm is much more general than just for nuclear science,” Chang noted. “It would be exciting to find new ways to use these new computers.”

The Oak Ridge Leadership Computing Facility is a DOE Office of Science User Facility.

Researchers from Lawrence Livermore 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 U.S. 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 Berkeley National Laboratory, Berkeley Lab