NEC Project
Title
Combinatorial optimization using quantum annealing ~Search for proper choices of solvers andevaluation of solutions on combinatorial optimization problems~
Sponsor NEC Corporation
NEC was founded in 1899 and is now focusing on developing solutions for the society that will
help resolve many of the issues the world is facing and lead to the creation of a brighter and more
prosperous society. Through co-creation initiatives with many different stakeholders, including
customers and business partners, citizens and government agencies, and international institutions,
we are actively devising new business models to create social value by harnessing our extensive
ICT (Information and Communication Technology) assets.
Industry Mentors
TBA
Background
Artificial intelligence (AI) is increasingly being used to solve various real-world problems. One
method for solving problems is selecting the best combination from an infinite number of choices
generated through machine learning.
These kinds of complex combinational optimization problems take even supercomputers anenormous amount of time to solve, making it impossible to obtain accurate answers within therequired time. Business, however, requires making the best decisions within at most a few tens ofminutes.
As societies mature, their problems also increase in complexity, leading to an ever-increasing
number of factors to consider in solving problems. In the future, the evolution of computer
technologies capable of solving complex problems will lead to significant social changes across
many fronts: time savings, energy and cost reduction, proper manpower allocation, labor shortage
resolution, industrial optimization, and value creation.
Among quantum computers, quantum annealing machines, which use weights among qubits(Quantum bits) in performing computations, has received wide attention as a tool for solving
complex combinational optimization problems within a short period of time. In 1999, NEC
succeeded in demonstrating solid-state qubit operation in the quantum superposition state for the
first time through a superconducting device. As it continued its research on ways to control thesuperposition state, NEC at some point shifted to quantum annealing as the main focus forgenerating a suite of outcomes from its research efforts.
Project and Expectations
Recent advent of quantum annealers and digital annealers has brought a breakthrough in solving
combinatorial optimization problems fast and accurately. However, size of target problems, forexample, obstructs us in directly applying these solvers to the problems, and conventional
approaches often outperform the new solvers.
Students are subjected to propose proper choices (or combinations) of the annealers and/orsolvers, for Employee Shift Scheduling as an example, which give the most accurate solution in
the shortest time. Students are also subjected to develop formulation of corresponding Isingmodels(*1) and estimate the applicability of each solver. NEC will provide datasets for theseevaluations.
1) The quantum and classical annealers provided by D-wave systems Inc.(*2),2) Solvers based on Xeon servers,
3) Solvers based on GPGPU servers,
4) Solvers based on NEC’s Vector machine “SX-Aurora TSUBASA” servers(*3),
and their combinations are also available.
(*1)

The Ising model, named after the physicist Ernst Ising, is a mathematical model offerromagnetism in statistical mechanics. The model consists of discrete variables that represent
magnetic dipole moments of atomic spins that can be in one of two states (+1 or −1). The spinsare arranged in a graph, usually a lattice, allowing each spin to interact with its neighbors.
Quantum annealers and digital annealers try to find the minimum energy state of this model, whichcorresponds to the optimal combination of the target problem.
(*2)

Students can use the classical annealer provided by D-wave systems Inc. to solve theproblems Then their Ising models will be executed by industrial mentors on the D-wave quantum
annealer.
(*3)

https://www.nec.com/en/global/solutions/hpc/

Requirements
Programming skills (Python, C, or MATLAB)

Recommended Readings and References[1] Professor Hidethosh Nishimori's website on quantum annealing.
http://www.stat.phys.titech.ac.jp/~nishimori/QA/q-annealing_e.html[2] D-Wave's website. https://www.dwavesys.com/(*4)[3] M. W. Johnson, et al., “Quantum annealing with manufactured spins," Nature 473, 194(2011).
[4] M. Aramon, et al., “Physics-Inspired Optimization for Quadratic Unconstrained Problems
Using a Digital Annealer," arXiv:1806.08815.
(*4)

You'll find materials on some applications of quantum annealing later on this website.