Kosuke Tatsumura

Hayato Goto, Ryo Hidaka, Kosuke Tatsumura

Nonlinear dynamical systems with continuous variables can be used for solving combinatorial optimization problems with discrete variables. Numerical simulations of them are also useful as heuristic algorithms with a desirable property, namely, parallelizability, which allows us to execute them in a massively parallel manner, leading to ultrafast performance. However, the dynamical-system approaches with continuous variables are usually less accurate than conventional approaches with discrete variables such as simulated annealing. To improve the solution accuracy of a quantum-inspired algorithm called simulated bifurcation (SB), which was found from classical simulation of a quantum nonlinear oscillator network exhibiting quantum bifurcation, here we generalize it by introducing nonlinear control of individual bifurcation parameters and show that the generalized SB (GSB) can achieve surprisingly high performance, namely, almost 100% success probabilities for some large-scale problems. As a result, the time to solution for a 2,000-variable problem is shortened to 10 ms by a GSB-based machine, which is two orders of magnitude shorter than the best known value, 1.3 s, previously obtained by an SB-based machine. To examine the reason for the ultrahigh performance, we investigated chaos in the GSB changing the nonlinear-control strength and found that the dramatic increase of success probabilities happens near the edge of chaos. That is, the GSB can find a solution with high probability by harnessing the edge of chaos. This finding suggests that dynamical-system approaches to combinatorial optimization will be enhanced by harnessing the edge of chaos, opening a broad possibility for physics-inspired approaches to combinatorial optimization.

Ryota Tamura, Tomoya Kashimata, Yohei Hamakawa et al.

A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.

Kosuke Tatsumura, Yohei Hamakawa, Masaya Yamasaki et al.

A cognitive function of tracking multiple objects, needed in autonomous mobile vehicles, comprises object detection and their temporal association. While great progress owing to machine learning has been recently seen for elaborating the similarity matrix between the objects that have been recognized and the objects detected in a current video frame, less for the assignment problem that finally determines the temporal association, which is a combinatorial optimization problem. Here we show an in-vehicle multiple object tracking system with a flexible assignment function for tracking through multiple long-term occlusion events. To solve the flexible assignment problem formulated as a nondeterministic polynomial time-hard problem, the system relies on an embeddable Ising machine based on a quantum-inspired algorithm called simulated bifurcation. Using a vehicle-mountable computing platform, we demonstrate a realtime system-wide throughput (23 frames per second on average) with the enhanced functionality.

Yukino Terui, Yuka Inoue, Yohei Hamakawa et al.

Collaborative filtering generates recommendations by exploiting user-item similarities based on rating data, which often contains numerous unrated items. To predict scores for unrated items, matrix factorization techniques such as nonnegative matrix factorization (NMF) are often employed. Nonnegative/binary matrix factorization (NBMF), which is an extension of NMF, approximates a nonnegative matrix as the product of nonnegative and binary matrices. While previous studies have applied NBMF primarily to dense data such as images, this paper proposes a modified NBMF algorithm tailored for collaborative filtering with sparse data. In the modified method, unrated entries in the rating matrix are masked, enhancing prediction accuracy. Furthermore, utilizing a low-latency Ising machine in NBMF is advantageous in terms of the computation time, making the proposed method beneficial.

Tomoya Kashimata, Yohei Hamakawa, Masaya Yamasaki et al.

Many real-time systems require the optimization of discrete variables. Black-box optimization (BBO) algorithms and multi-armed bandit (MAB) algorithms perform optimization by repeatedly taking actions and observing the corresponding instant rewards without any prior knowledge. Recently, a BBO method using an Ising machine has been proposed to find the best action that is represented by a combination of discrete values and maximizes the instant reward in static environments. In contrast, dynamic environments, where real-time systems operate, necessitate MAB algorithms that maximize the average reward over multiple trials. However, due to the enormous number of actions resulting from the combinatorial nature of discrete optimization, conventional MAB algorithms cannot effectively optimize dynamic, discrete environments. Here, we show a heuristic MAB method for dynamic, discrete environments by extending the BBO method, in which an Ising machine effectively explores the actions while considering interactions between variables and changes in dynamic environments. We demonstrate the dynamic adaptability of the proposed method in a wireless communication system with moving users.

Yohei Hamakawa, Tomoya Kashimata, Masaya Yamasaki et al.

Quantum or quantum-inspired Ising machines have recently shown promise in solving combinatorial optimization problems in a short time. Real-world applications, such as time division multiple access (TDMA) scheduling for wireless multi-hop networks and financial trading, require solving those problems sequentially where the size and characteristics change dynamically. However, using Ising machines involves challenges to shorten system-wide latency due to the transfer of large Ising model or the cloud access and to determine the parameters for each problem. Here we show a combinatorial optimization method using embedded Ising machines, which enables solving diverse problems at high speed without runtime parameter tuning. We customize the algorithm and circuit architecture of the simulated bifurcation-based Ising machine to compress the Ising model and accelerate computation and then built a machine learning model to estimate appropriate parameters using extensive training data. In TDMA scheduling for wireless multi-hop networks, our demonstration has shown that the sophisticated system can adapt to changes in the problem and showed that it has a speed advantage over conventional methods.