A bit too much: reducing the bit width of Ising models for quantum annealing

January 06, 2021

Given a list of cities and the distances between each pair of cities, how do you determine the shortest route that visits each city exactly once and returns to the starting location? This famous problem is called the "traveling salesman problem" and is an example of a combinatorial optimization problem. Solving these problems using conventional computers can be very time-consuming, and special devices called "quantum annealers" have been created for this purpose.

Quantum annealers are designed to find the lowest energy state (or "ground state") of what's known as an "Ising model." Such models are abstract representations of a quantum mechanical system involving interacting spins that are also influenced by external magnetic fields. In the late 90s, scientists found that combinatorial optimization problems could be formulated as Ising models, which in turn could be physically implemented in quantum annealers. To obtain the solution to a combinatorial optimization problem, one simply has to observe the ground state reached in its associated quantum annealer after a short time.

One of the biggest challenges in this process is the transformation of the "logical" Ising model into a physically implementable Ising model suitable for quantum annealing. Sometimes, the numerical values of the spin interactions or the external magnetic fields require a number of bits to represent them (bit width) too large for a physical system. This severely limits the versatility and applicability of quantum annealers to real world problems. Fortunately, in a recent study published in IEEE Transactions on Computers, scientists from Japan have tackled this issue. Based purely on mathematical theory, they developed a method by which a given logical Ising model can be transformed into an equivalent model with a desired bit width so as to make it "fit" a desired physical implementation.

Their approach consists in adding auxiliary spins to the Ising model for problematic interactions or magnetic fields in such a way that the ground state (solution) of the transformed model is the same as that of the original model while also requiring a lower bit width. The technique is relatively simple and completely guaranteed to produce an equivalent Ising model with the same solution as the original. "Our strategy is the world's first to efficiently and theoretically address the bit-width reduction problem in the spin interactions and magnetic field coefficients in Ising models," remarks Professor Nozomu Togawa from Waseda University, Japan, who led the study.

The scientists also put their method to the test in several experiments, which further confirmed its validity. Prof. Togawa has high hopes, and he concludes by saying, "The approach developed in this study will widen the applicability of quantum annealers and make them much more attractive for people dealing with not only physical Ising models but all kinds of combinatorial optimization problems. Such problems are common in cryptography, logistics, and artificial intelligence, among many other fields."

Authors: Daisuke Oku (1), Masashi Tawada (1), Shu Tanaka (2,3), and Nozomu Togawa (1)

Title of original paper: How to Reduce the Bit-width of an Ising Model by Adding Auxiliary Spins

Journal: IEEE Trans. Computers

DOI: 10.1109/TC.2020.3045112


(1) Department of Computer Science and Communications Engineering, Waseda University
(2) Green Computing Systems Research Organization, Waseda University
(3) Precursory Research for Embryonic Science and Technology

About Waseda University

Located in the heart of Tokyo, Waseda University is a leading private research university that has long been dedicated to academic excellence, innovative research, and civic engagement at both the local and global levels since 1882. The University number one in Japan in international activities, including the number of international students, with the broadest range of degree programs fully taught in English. To learn more about Waseda University, visit https://www.waseda.jp/top/en

Waseda University

Related Magnetic Fields Articles from Brightsurf:

Physicists circumvent centuries-old theory to cancel magnetic fields
A team of scientists including two physicists at the University of Sussex has found a way to circumvent a 178-year old theory which means they can effectively cancel magnetic fields at a distance.

Magnetic fields on the moon are the remnant of an ancient core dynamo
An international simulation study by scientists from the US, Australia, and Germany, shows that alternative explanatory models such as asteroid impacts do not generate sufficiently large magnetic fields.

Modelling extreme magnetic fields and temperature variation on distant stars
New research is helping to explain one of the big questions that has perplexed astrophysicists for the past 30 years - what causes the changing brightness of distant stars called magnetars.

Could megatesla magnetic fields be realized on Earth?
A team of researchers led by Osaka University discovered a novel mechanism called a ''microtube implosion,'' demonstrating the generation of megatesla-order magnetic fields, which is three orders of magnitude higher than those ever experimentally achieved.

Superconductors are super resilient to magnetic fields
A Professor at the University of Tsukuba provides a new theoretical mechanism that explains the ability of superconductive materials to bounce back from being exposed to a magnetic field.

A tiny instrument to measure the faintest magnetic fields
Physicists at the University of Basel have developed a minuscule instrument able to detect extremely faint magnetic fields.

Graphene sensors find subtleties in magnetic fields
Cornell researchers used an ultrathin graphene ''sandwich'' to create a tiny magnetic field sensor that can operate over a greater temperature range than previous sensors, while also detecting miniscule changes in magnetic fields that might otherwise get lost within a larger magnetic background.

Twisting magnetic fields for extreme plasma compression
A new spin on the magnetic compression of plasmas could improve materials science, nuclear fusion research, X-ray generation and laboratory astrophysics, research led by the University of Michigan suggests.

How magnetic fields and 3D printers will create the pills of tomorrow
Doctors could soon be administering an entire course of treatment for life-threatening conditions with a 3D printed capsule controlled by magnetic fields thanks to advances made by University of Sussex researchers.

Researchers develop ultra-sensitive device for detecting magnetic fields
The new magnetic sensor is inexpensive to make, works on minimal power and is 20 times more sensitive than many traditional sensors.

Read More: Magnetic Fields News and Magnetic Fields Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.