We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can ...effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph <inline-formula><tex-math notation="LaTeX">k</tex-math> <mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="shirai-ieq1-3239539.gif"/> </inline-formula>-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.
Annealing machines have been developed as non-von Neumann computers aimed at solving combinatorial optimization problems efficiently. To use annealing machines for solving combinatorial optimization ...problems, we have to represent the objective function and constraints by an Ising model, which is a theoretical model in statistical physics. Further, it is necessary to transform the Ising model according to the hardware limitations. In the transformation, the process of effectively reducing the bit-widths of coefficients in the Ising model has hardly been studied so far. Thus, when we consider the Ising model with a large bit-width, a naive method, which means right bit-shift, has to be applied. Since it is expected that obtaining highly accurate solutions is difficult by the naive method, it is necessary to construct a method for efficiently reducing the bit-width. This article proposes methods for reducing the bit-widths of interaction and external magnetic field coefficients in the Ising model and proves that the reduction gives theoretically the same ground state of the original Ising model. The experimental evaluations also demonstrate the effectiveness of our proposed methods.
The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In ...this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.
Recently, with the spread of Internet of Things (IoT) devices, embedded hardware devices have been used in a variety of everyday electrical items. Due to the increased demand for embedded hardware ...devices, some of the IC design and manufacturing steps have been outsourced to third-party vendors. Since malicious third-party vendors may insert malicious circuits, called hardware Trojans, into their products, developing an effective hardware-Trojan detection method is strongly required. In this paper, we propose 25 hardware-Trojan features focusing on the structure of trigger circuits for machine-learning-based hardware-Trojan detection. Combining the proposed features into 11 existing hardware-Trojan features, we totally utilize 36 hardware-Trojan features for classification. Then we classify the nets in an unknown netlist into a set of normal nets and Trojan nets based on a random-forest classifier. The experimental results demonstrate that the average true positive rate (TPR) becomes 64.2% and the average true negative rate (TNR) becomes 100.0%. They improve the average TPR by 14.8 points while keeping the average TNR compared to existing state-of-the-art methods. In particular, the proposed method successfully finds out Trojan nets in several benchmark circuits, which are not found by the existing method.
Message from the Editor-in-Chief Togawa, Nozomu
IPSJ Transactions on System LSI Design Methodology,
2019, 2019-00-00, 20190101, Letnik:
12
Journal Article
Photonic-crystal surface-emitting lasers (PCSELs), which utilize a two-dimensional (2D) optical resonance inside a photonic crystal for lasing, feature various outstanding functionalities such as ...single-mode high-power operation and arbitrary control of beam polarizations. Although most of the previous designs of PCSELs employ spatially uniform photonic crystals, it is expected that lasing performance can be further improved if it becomes possible to optimize the spatial distribution of photonic crystals. In this paper, we investigate the structural optimization of PCSELs via quantum annealing towards high-power, narrow-beam-divergence operation with linear polarization. The optimization of PCSELs is performed by the iteration of the following three steps: (1) time-dependent 3D coupled-wave analysis of lasing performance, (2) formulation of the lasing performance via a factorization machine, and (3) selection of optimal solution(s) via quantum annealing. By using this approach, we discover an advanced PCSEL with a non-uniform spatial distribution of the band-edge frequency and injection current, which simultaneously enables higher output power, a narrower divergence angle, and a higher linear polarization ratio than conventional uniform PCSELs. Our results potentially indicate the universal applicability of quantum annealing, which has been mainly applied to specific types of discrete optimization problems so far, for various physics and engineering problems in the field of smart manufacturing.
The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can ...be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.
Technological devices have become deeply embedded in people's lives, and their demand is growing every year. It has been indicated that outsourcing the design and manufacturing of integrated ...circuits, which are essential for technological devices, may lead to the insertion of malicious circuitry, called hardware Trojans (HTs). This paper proposes an HT detection method at gate-level netlists based on XGBoost, one of the best gradient boosting decision tree models. We first propose the optimal set of HT features among many feature candidates at a netlist level through thorough evaluations. Then, we construct an XGBoost-based HT detection method with its optimized hyperparameters. Evaluation experiments were conducted on the netlists from Trust-HUB benchmarks and showed the average F-measure of 0.842 using the proposed method. Also, we newly propose a Trojan probability propagation method that effectively corrects the HT detection results and apply it to the results obtained by XGBoost-based HT detection. Evaluation experiments showed that the average F-measure is improved to 0.861. This value is 0.194 points higher than that of the existing best method proposed so far.
In recent years, with the wide spread of the Internet of Things (IoT) devices, security issues for hardware devices have been increasing, where detecting their anomalous behaviors becomes quite ...important. One of the effective methods for detecting anomalous behaviors of IoT devices is to utilize consumed energy and operation duration time extracted from their power waveforms. However, the existing methods do not consider the shape of time-series data and cannot distinguish between power waveforms with similar consumed energy and duration time but different shapes. In this paper, we propose a method for detecting anomalous behaviors based on the shape of time-series data by incorporating a shape-based distance (SBD) measure. The proposed method first obtains the entire power waveform of the target IoT device and extracts several application power waveforms. After that, we give the invariances to them, and we can effectively obtain the SBD between every two application power waveforms. Based on the SBD values, the local outlier factor (LOF) method can finally distinguish between normal application behaviors and anomalous application behaviors. Experimental results demonstrate that the proposed method successfully detects anomalous application behaviors, while the existing state-of-the-art method fails to detect them.
PDF
