A Quantum inspired Approach to Solving Real World Problems

Aug 6, 2024

TECH & DESIGN

How will the world change when quantum computers become practical?

The world of practical quantum computing holds the promise of tackling increasingly complex societal challenges and optimizing solutions. However, the reality is that there's still a long road ahead to reach such a world.

Currently, alongside the approach of achieving the best of both worlds with traditional (classical) computers and quantum computers through quantum-classical hybrid methods, the development of quantum-inspired technology is becoming increasingly crucial.

Leveraging the characteristic of quantum-inspired technology, which is suited for solving optimization problems with numerous variables and constraints, DENSO has begun to explore the application and evolution of quantum-inspired technology for addressing various real-world challenges, such as delivery and logistics.

Contents of this article

Quantum computers, expected to revolutionize complex societal issues with computational power far surpassing classical computers, face a challenging road to practicality despite mounting expectations.

Hirotaka Irie, a member of DENSO's Mathematical Solution R&I Dept., AI R&I Div., notes, "The gap between the theoretical potential and practical implementation of quantum computers is wider than initially anticipated by researchers.

While there's often talk of instantly solving prime factorization problems, achieving this requires more than just hardware innovation. For quantum computers to play a ubiquitous (*1) role, numerous algorithmic innovations connecting quantum computers to classical computing technologies are essential.

In these circumstances, Irie is focusing on 'quantum-classical hybrids' to promote the practical use of quantum computers. He is advancing research and development to build a foundation for quantum computing applications that harness the unique capabilities of quantum computers through integration with traditional computing systems.

The term quantum-classical hybrid refers to computational methods that maximize the strengths of both classical and quantum computers.

While quantum computers can rapidly solve specific problems using the principles of quantum mechanics, they are not suitable for all computations. On the other hand, classical computers play a foundational role in various practical applications despite facing challenges like combinatorial explosions (*2).

Quantum-classical hybrid computing begins with preparing the best algorithms for both quantum and classical computers. This approach leverages the strengths of both systems to discuss more efficient ways of solving complex problems with realistic computational resources. It is particularly promising for applications in optimization problems (*3) and materials science.

※1
Ubiquitous refers to a concept where something exists so naturally that it can be used without conscious awareness of its presence. For example, while classical computers are currently ubiquitous in society, the same is anticipated for quantum computers.

※2
Combinatorial explosion occurs when the number of combinations of conditions or elements required to solve a problem increases, leading to an explosion in the number of required computations.

※3
Optimization problems involve determining the best choice among various options under different constraints.

DENSO is focusing on quantum-inspired technology to build the foundation for quantum computing applications. Quantum-inspired technology involves emulating problem-solving methods unique to quantum computing using advanced parallel processing capabilities of classical computer hardware, particularly General-Purpose computing on Graphics Processing Units (GPGPU).

Quantum computers utilize quantum bits (qubits) and exploit unique phenomena such as superposition and entanglement to perform computations. This enables them to potentially find solutions to certain types of problems (like prime factorization, specific optimization problems, and chemical simulations) much faster than classical computers. However, implementing and operating large-scale, high-performance quantum bits in hardware to enable such computations poses numerous technical challenges that still need to be overcome.

On the other hand, problems that quantum computers are expected to solve can be partially emulated by classical algorithms. Quantum-inspired technology, leveraging the parallel processing capabilities of GPGPUs, aims to efficiently mimic quantum computing. While it cannot replicate the true capabilities of quantum computers, quantum-inspired technology seeks to emulate quantum-like approaches on classical computers. By doing so, it can surpass existing computational techniques and provide the best methods for practical problem-solving on classical computers.

"Various quantum-inspired technologies have been proposed in the past, but by understanding the characteristics of optimization problems, we have been able to develop quantum-inspired technologies that surpass the performance of existing mathematical optimization," says Akira Miki, a member of the Mathematical Solution R&I Dept., AI R&I Div.

DENSO Mk-D, the quantum-inspired technology developed by DENSO, is based on the quantum annealing method-a key technique in quantum computing. Quantum annealing computers utilize the Ising model, a framework from statistical mechanics that describes the properties of magnetic materials, to solve complex optimization problems. This model is particularly effective for formulating and addressing various optimization challenges.

DENSO Mk-D achieves high-speed computations even for practical and large-scale problems by minimizing the information needed to be referenced by compressing the information converted into the Ising model.

While Ising machines have been proposed as quantum-inspired technologies in the past, the evaluation has primarily focused on the abstract Ising model in statistical mechanics. In this context, it is recognized that there is a significant gap when compared to solving real-world optimization problems in logistics and transportation. In contrast, DENSO Mk-D was developed to exhibit suitable performance for applying to real optimization problems, aiming to bridge this gap. As a result, it has been able to significantly outperform existing technologies like mathematical optimization (Miki).

DENSO Mk-D can solve large-scale optimization problems with up to 5 million variables using real data and up to 12 million variables using virtual data. Variables in computing power are like containers that store the values of data handled during the computation process and the number of variables a computer can manage is an important indicator of the scale of computation.

Generally, there is a significant gap between the solvability of abstract Ising models and real-world problems. For instance, while a large-scale Ising model with more than a million variables might perform well, in real-world applications like logistics and distribution, beneficial computations are only feasible with fewer than 100,000 variables. This is a well-known fact in the realm of quantum-inspired technology.

Traditional quantum-inspired technologies, despite being capable of handling real-world problems on the scale of one million variables, have faced limitations in performance.

It was the development of the DENSO Mk-D that first demonstrated globally that a real-world problem with as many as five million variables could be efficiently solved, surpassing the previously recognized one million-variable limits of quantum-inspired technology.

DENSO is working on optimizing delivery schedules in the delivery transportation network of logistics centers to evaluate the performance of quantum-inspired technology DENSO Mk-D.

D-Stream, one of DENSO's largest logistics centers located in Nishio City, Aichi Prefecture, plays a crucial role in DENSO's logistics network. Now we are using actual data to perform optimization calculations.

The logistics center plays a crucial role in sorting and distributing products collected from DENSO's factories according to customer demands. The logistics process involves numerous interconnected elements such as the number of trucks used per day, delivery routes, driver rest times, loading times, and delivery time restrictions, making it an extremely complex problem involving up to 5 million variables. To streamline this complex logistics process, we utilized the quantum-inspired technology DENSO Mk-D to optimize truck delivery schedules. Miki reflects on the optimization results as follows.

"As a result, using DENSO Mk-D, we were able to reduce the delivery schedule from the usual 77 trucks per day to 58 trucks. This represents approximately a 25% reduction in the number of trucks and an equivalent 15% reduction in working hours. Additionally, we achieved a reduction of 322 kg of CO₂ emissions per day. The optimization problem at 'D-Stream' was solved using DENSO Mk-D in just 6 minutes of computation time. This is about 500 times faster than conventional mathematical optimization techniques, demonstrating for the first time in the world the ability to solve large-scale real-world problems using quantum-inspired technology." (Miki)

"However," Miki continues, "DENSO Mk-D is not effective for everything. While quantum-inspired technology shows promising applications like in this case, it's still a challenging task to identify its specific strengths and areas of expertise."

"The optimization problem of the delivery transportation network at this logistics center was a good example of where DENSO Mk-D performed well. In society, there are numerous large-scale and complex challenges beyond logistics. As the scale increases, the number of combinations becomes enormous, making it difficult for conventional mathematical optimization techniques to cope. That's why it's essential to advance the utilization of quantum-inspired technology, which is considered effective for solving optimization problems," concludes Miki.

In the future, DENSO will consider implementing DENSO Mk-D first in small-scale logistics with an eye toward internal logistics optimization and expanding into the logistics business. The goal is to aim for practical operation.

DENSO has been advancing quantum computing technology development through collaboration between academia and industry," says Irie, outlining prospects. "Moving forward, we are particularly keen on actively promoting the industrial application of our research findings.

DENSO has been collaborating on research in quantum computing with Professor Masayuki Ohzeki (Graduate School of Information Sciences, Tohoku University) and Associate Professor Shu Tanaka (Department of Applied Physics and Physico-Informatics, Faculty of Science and Technology, Keio University) since 2015.

In 2019, DENSO embarked on research and development of quantum-classical hybrid technology and quantum-inspired technology in collaboration with Dr. Tetsuo Hatsuda, the Program Director of the RIKEN Interdisciplinary Theoretical and Mathematical Sciences Program (iTHEMS) at RIKEN. Irie explains the recent endeavors as follows.

"We have previously applied quantum annealing technology to optimize factory operations and Mobility as a Service (MaaS) fields, as well as developed the foundational technology for quantum-inspired technology. The lessons learned from these research and development efforts have contributed to the achievements in the logistics field this time. Moving forward, we not only aim to enhance these technologies but also explore the application of quantum computing in AI utilizing quantum gates and material development," says Irie.

As part of these efforts, since the fiscal year 2017, we have been conducting research on taxi dispatching and multimodal transportation systems in Thailand. Since the fiscal year 2018, we have been conducting Proof of Concept (PoC) experiments for route optimization of Automated Guided Vehicles (AGVs) within factories. Additionally, since fiscal year 2020, we have been working on applying quantum computing to black-box optimization (*4) for product design optimization.

"While the utilization of quantum computers is still in the research stage, we believe that the foundational technologies for quantum computing applications, including quantum-inspired technology, are impacting current businesses. Moreover, for black-box optimization in product design, not only optimization but also quantum machine learning and quantum simulation are necessary. This area is believed to be where the true potential of quantum computers can be demonstrated. By integrating the development of these technologies with the quantum-inspired technology we have cultivated, we believe it will lead to further technological advancement and solving societal challenges," states Irie.

As societal challenges become increasingly complex, DENSO will continue its research and development efforts in quantum-inspired technology. By doing so, we aim to address challenges such as optimization in logistics and factory operations, and we remain committed to tackling these challenges and continuing to push boundaries in the future.

※4
Black-box optimization refers to efficiently optimizing objective functions that cannot be evaluated analytically, such as in design optimization or materials discovery problems. The goal is to find the optimal parameters or composition that minimize or maximize the desired metric through simulations, treating the objective as a black box.

TECH & DESIGN

SHARE

• CAREER & LIFENov 29, 2022

  Eliminating traffic accident deaths through brain science research

  Motivated by the vision of a fantastical future in which even kids can drive

• TECH & DESIGNDec 10, 2021

  To Achieve AI-based Fully Automated Driving

  Elemental technology research and past development projects at DENSO