Koji Nakano
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Koji Nakano has a total of 89 co-authors. Here are the top co-authors by number of shared publications:
- Yasuaki Ito
School of Advanced Science and Engineering, Hiroshima University, Higashi-Hiroshima 739-8527, Japan
32 shared publications Yasuaki Ito
Hiroshima University Kagamiyama 1-4-1,Graduate School of Advanced Science and Engineering,Higashihiroshima,Japan,739-8527
8 shared publications- Akihiko Kasagi
Fujitsu Limited, Kawasaki 211-8588, Japan
5 shared publications - Daisuke Takafuji
Hiroshima University Kagamiyama 1-4-1,Graduate School of Advanced Science and Engineering,Higashihiroshima,Japan,739-8527
5 shared publications Hiroki Tokura
Hiroshima University
5 shared publications- Ryota Yasudo
Kyoto University, Kyoto, Japan
5 shared publications
Latest Publications
- Open Access
GANSU: A GPU-Native Quantum Chemistry Framework for Efficient Hartree–Fock and Post-HF Calculations
GPU-accelerated quantum chemistry programs can dramatically reduce the time required for electronic structure calculations, yet most existing implementations either retrofit GPU kernels onto legacy CPU codebases or optimize individual kernels without addressing workflow-level integration overhead. We present GANSU (GPU Accelerated Numerical Simulation Utility), an open-source quantum chemistry framework written entirely in CUDA/C++ that integrates GPU-accelerated kernels for electron repulsion integrals, Fock matrix construction, and post-Hartree–Fock (post-HF) methods into a unified, GPU-resident execution pipeline. The key design principle is to eliminate host–device data transfers between computational stages by keeping all intermediate data, including density matrices, integral buffers, and Fock matrix replicas, on the GPU throughout the self-consistent field (SCF) iteration, combined with runtime-selectable integral strategies (stored ERI, resolution-of-the-identity, and Direct-SCF) that adapt to system size and available memory. On an NVIDIA H200 GPU, GANSU achieves end-to-end speedups of up to over PySCF for SCF, for MP2 on molecules with up to 470 basis functions, and for FCI, while outperforming GPU4PySCF by up to for FCI, across a range of molecular systems with up to 650 basis functions. The framework further provides analytical energy gradients and geometry optimization with nine algorithms, all operating within the same GPU-resident data flow. These results demonstrate that workflow-aware kernel integration, not just kernel-level optimization, is essential for realizing the full potential of GPU acceleration in scientific computing. GANSU is publicly available under the BSD-3-Clause license.Open AccessGANSU: A GPU-Native Quantum Chemistry Framework for Efficient Hartree–Fock and Post-HF Calculations
GPU-accelerated quantum chemistry programs can dramatically reduce the time required for electronic structure calculations, yet most existing implementations either retrofit GPU kernels onto legacy CPU codebases or optimize individual kernels without addressing workflow-level integration overhead. We present GANSU (GPU Accelerated Numerical Simulation Utility), an open-source quantum chemistry framework written entirely in CUDA/C++ that integrates GPU-accelerated kernels for electron repulsion integrals, Fock matrix construction, and post-Hartree–Fock (post-HF) methods into a unified, GPU-resident execution pipeline. The key design principle is to eliminate host–device data transfers between computational stages by keeping all intermediate data, including density matrices, integral buffers, and Fock matrix replicas, on the GPU throughout the self-consistent field (SCF) iteration, combined with runtime-selectable integral strategies (stored ERI, resolution-of-the-identity, and Direct-SCF) that adapt to system size and available memory. On an NVIDIA H200 GPU, GANSU achieves end-to-end speedups of up to over PySCF for SCF, for MP2 on molecules with up to 470 basis functions, and for FCI, while outperforming GPU4PySCF by up to for FCI, across a range of molecular systems with up to 650 basis functions. The framework further provides analytical energy gradients and geometry optimization with nine algorithms, all operating within the same GPU-resident data flow. These results demonstrate that workflow-aware kernel integration, not just kernel-level optimization, is essential for realizing the full potential of GPU acceleration in scientific computing. GANSU is publicly available under the BSD-3-Clause license. - Open Access
- 2 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 37 (4) , 836-848
A 590-Nanosecond 757-Gbps FPGA Lossy Compressed Network
Inter-FPGA communication bandwidth has become a limiting factor in scaling memory-intensive workloads on FPGA-based systems. While modern FPGAs integrate high-bandwidth memory (HBM) to increase local memory throughput, network interfaces often lag behind, creating an imbalance between computation and communication resources. Data compression is a technique to increase effective communication bandwidth by reducing the amount of data transferred, but existing solutions struggle to meet the performance and operation latency requirements of FPGA-based platforms. This paper presents a high-throughput lossy compression framework that enables sub-microsecond latency communication in FPGA clusters. The proposed design addresses the challenge of aligning variable-length compressed data with fixed-width network channels by using transpose circuits, memory-bank reordering, and word-wise operations. A run-length encoding scheme with bounded error is employed to compress floating-point and fixed-point data without relying on complex fine-grained bit-level manipulations, enabling low-latency and scalable implementation. The proposed architecture is implemented on a custom Stratix 10 MX2100 FPGA card equipped with eight 50 Gbps network ports and silicon photonics transceivers. The system achieves up to 757 Gbps of aggregate bandwidth per FPGA in collective communication operations. Compression and decompression are performed within 590 ns total latency, while maintaining the quality of results in a GradAllReduce workload for deep learning.
- 2 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 37 (4) , 836-848
Open AccessA 590-Nanosecond 757-Gbps FPGA Lossy Compressed Network
Inter-FPGA communication bandwidth has become a limiting factor in scaling memory-intensive workloads on FPGA-based systems. While modern FPGAs integrate high-bandwidth memory (HBM) to increase local memory throughput, network interfaces often lag behind, creating an imbalance between computation and communication resources. Data compression is a technique to increase effective communication bandwidth by reducing the amount of data transferred, but existing solutions struggle to meet the performance and operation latency requirements of FPGA-based platforms. This paper presents a high-throughput lossy compression framework that enables sub-microsecond latency communication in FPGA clusters. The proposed design addresses the challenge of aligning variable-length compressed data with fixed-width network channels by using transpose circuits, memory-bank reordering, and word-wise operations. A run-length encoding scheme with bounded error is employed to compress floating-point and fixed-point data without relying on complex fine-grained bit-level manipulations, enabling low-latency and scalable implementation. The proposed architecture is implemented on a custom Stratix 10 MX2100 FPGA card equipped with eight 50 Gbps network ports and silicon photonics transceivers. The system achieves up to 757 Gbps of aggregate bandwidth per FPGA in collective communication operations. Compression and decompression are performed within 590 ns total latency, while maintaining the quality of results in a GradAllReduce workload for deep learning.
- Open Access
- 31 October 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (21) , 11676
Predicting the Cooling Rate in Steel-Part Heat Treatment via Random Forests
Heat treatment is a thermal-processing method involving controlled heating and cooling cycles designed to achieve the desired properties of materials. Among these steps, the cooling rate in heat treatment plays a crucial role, as it significantly influences the resulting material properties. In this paper, we investigated the feasibility of random forests in estimating the cooling-rate parameters for the steel-part heat treatment process. Random forests are particularly appealing in modeling an ensemble of expressive decision trees from which cooling can be modeled and estimated from the interaction of metal features. Our computational experiments using real-world data from industrial-scale operations demonstrated the advantageous properties of random forest regression models, particularly when combined with a random oversampling scheme. We also found that the chemical composition—specifically carbon and chromium content—as well as the weight of the steel parts, are key features that predict the cooling rate of steel parts. Furthermore, our validation using real-world cooling scenarios aligned closely with the practical insights of seasoned operators who routinely recommend cooling parameters for the metal-normalizing process. Our results highlight the effectiveness of the ensemble approach of random forest for practical applicability in industrial-scale heat treatment.
- 31 October 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (21) , 11676
Open AccessPredicting the Cooling Rate in Steel-Part Heat Treatment via Random Forests
Heat treatment is a thermal-processing method involving controlled heating and cooling cycles designed to achieve the desired properties of materials. Among these steps, the cooling rate in heat treatment plays a crucial role, as it significantly influences the resulting material properties. In this paper, we investigated the feasibility of random forests in estimating the cooling-rate parameters for the steel-part heat treatment process. Random forests are particularly appealing in modeling an ensemble of expressive decision trees from which cooling can be modeled and estimated from the interaction of metal features. Our computational experiments using real-world data from industrial-scale operations demonstrated the advantageous properties of random forest regression models, particularly when combined with a random oversampling scheme. We also found that the chemical composition—specifically carbon and chromium content—as well as the weight of the steel parts, are key features that predict the cooling rate of steel parts. Furthermore, our validation using real-world cooling scenarios aligned closely with the practical insights of seasoned operators who routinely recommend cooling parameters for the metal-normalizing process. Our results highlight the effectiveness of the ensemble approach of random forest for practical applicability in industrial-scale heat treatment.
- Open Access
- 11 August 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (16) , 8847
Optimizing Heat Treatment Schedules via QUBO Formulation
Quadratic Unconstrained Binary Optimization (QUBO) is the problem of finding binary variable assignments that minimize a given quadratic objective function. Many combinatorial optimization problems can be transformed into equivalent QUBO formulations, and significant research efforts have been devoted to developing efficient QUBO solvers. This paper presents a method for converting a real-world, industrial-scale scheduling problem arising in the heat treatment process of metal parts into an equivalent QUBO formulation. In current operations, two experienced operators manually spend about two hours each day to create a 24 h schedule for two furnaces, considering various constraints and processing priorities. We have developed a C++-based scheduling system that automatically converts this problem into a QUBO instance and solves it using QUBO++, a high-performance toolkit we have recently developed and released. The experimental results on actual scheduling instances show that QUBO++ consistently produces high-quality solutions in a short time, leveraging the computational merits of the QUBO formulation. The system reduces the labor equivalent to two hours of expert work per day, indicating that automated scheduling via QUBO++ is a promising approach for improving efficiency and accuracy in factory operations.
- 11 August 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (16) , 8847
Open AccessOptimizing Heat Treatment Schedules via QUBO Formulation
Quadratic Unconstrained Binary Optimization (QUBO) is the problem of finding binary variable assignments that minimize a given quadratic objective function. Many combinatorial optimization problems can be transformed into equivalent QUBO formulations, and significant research efforts have been devoted to developing efficient QUBO solvers. This paper presents a method for converting a real-world, industrial-scale scheduling problem arising in the heat treatment process of metal parts into an equivalent QUBO formulation. In current operations, two experienced operators manually spend about two hours each day to create a 24 h schedule for two furnaces, considering various constraints and processing priorities. We have developed a C++-based scheduling system that automatically converts this problem into a QUBO instance and solves it using QUBO++, a high-performance toolkit we have recently developed and released. The experimental results on actual scheduling instances show that QUBO++ consistently produces high-quality solutions in a short time, leveraging the computational merits of the QUBO formulation. The system reduces the labor equivalent to two hours of expert work per day, indicating that automated scheduling via QUBO++ is a promising approach for improving efficiency and accuracy in factory operations.
- Open Access
- 25 April 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (9) , 4779
GPU-Accelerated Fock Matrix Computation with Efficient Reduction
In quantum chemistry, constructing the Fock matrix is essential to compute Coulomb interactions among atoms and electrons and, thus, to determine electron orbitals and densities. In the fundamental framework of quantum chemistry such as the Hartree–Fock method, the iterative computation of the Fock matrix is a dominant process, constituting a critical computational bottleneck. Although the Fock matrix computation has been accelerated by parallel processing using GPUs, the issue of performance degradation due to memory contention remains unresolved. This is due to frequent conflicts of atomic operations accessing the same memory addresses when multiple threads update the Fock matrix elements concurrently. To address this issue, we propose a parallel algorithm that efficiently and suitably distributes the atomic operations; and significantly reduces the memory contention by decomposing the Fock matrix into multiple replicas, allowing each GPU thread to contribute to different replicas. Experimental results using a relevant set/configuration of molecules on an NVIDIA A100 GPU show that our approach achieves up to a speedup in Fock matrix computation compared to conventional high-contention approaches. Furthermore, our proposed method can also be readily combined with existing implementations that reduce the number of atomic operations, leading to a improvement.- 25 April 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (9) , 4779
Open AccessGPU-Accelerated Fock Matrix Computation with Efficient Reduction
In quantum chemistry, constructing the Fock matrix is essential to compute Coulomb interactions among atoms and electrons and, thus, to determine electron orbitals and densities. In the fundamental framework of quantum chemistry such as the Hartree–Fock method, the iterative computation of the Fock matrix is a dominant process, constituting a critical computational bottleneck. Although the Fock matrix computation has been accelerated by parallel processing using GPUs, the issue of performance degradation due to memory contention remains unresolved. This is due to frequent conflicts of atomic operations accessing the same memory addresses when multiple threads update the Fock matrix elements concurrently. To address this issue, we propose a parallel algorithm that efficiently and suitably distributes the atomic operations; and significantly reduces the memory contention by decomposing the Fock matrix into multiple replicas, allowing each GPU thread to contribute to different replicas. Experimental results using a relevant set/configuration of molecules on an NVIDIA A100 GPU show that our approach achieves up to a speedup in Fock matrix computation compared to conventional high-contention approaches. Furthermore, our proposed method can also be readily combined with existing implementations that reduce the number of atomic operations, leading to a improvement. - Open Access
- 27 February 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (5) , 2572
Efficient GPU Implementation of the McMurchie–Davidson Method for Shell-Based ERI Computations
Quantum chemistry offers the formal machinery to derive molecular and physical properties arising from (sub)atomic interactions. However, as molecules of practical interest are largely polyatomic, contemporary approximation schemes such as the Hartree–Fock scheme are computationally expensive due to the large number of electron repulsion integrals (ERIs). Central to the Hartree–Fock method is the efficient computation of ERIs over Gaussian functions (GTO-ERIs). Here, the well-known McMurchie–Davidson method (MD) offers an elegant formalism by incrementally extending Hermite Gaussian functions and auxiliary tabulated functions. Although the MD method offers a high degree of versatility to acceleration schemes through Graphics Processing Units (GPUs), the current GPU implementations limit the practical use of supported values of the azimuthal quantum number. In this paper, we propose a generalized framework capable of computing GTO-ERIs for arbitrary azimuthal quantum numbers, provided that the intermediate terms of the MD method can be stored. Our approach benefits from extending the MD recurrence relations through shells, batches, and triple-buffering of the shared memory, and ordering similar ERIs, thus enabling the effective parallelization and use of GPU resources. Furthermore, our approach proposes four GPU implementation schemes considering the suitable mappings between Gaussian basis and CUDA blocks and threads. Our computational experiments involving the GTO-ERI computations of molecules of interest on an NVIDIA A100 Tensor Core GPU (NVIDIA, Santa Clara, CA, USA) have revealed the merits of the proposed acceleration schemes in terms of computation time, including up to a 72× improvement over our previous GPU implementation and up to a 4500× speedup compared to a naive CPU implementation, highlighting the effectiveness of our method in accelerating ERI computations for both monatomic and polyatomic molecules. Our work has the potential to explore new parallelization schemes of distinct and complex computation paths involved in ERI computation.
- 27 February 2025
- Published by MDPI AG in Applied Sciences
- Vol. 15 (5) , 2572
Open AccessEfficient GPU Implementation of the McMurchie–Davidson Method for Shell-Based ERI Computations
Quantum chemistry offers the formal machinery to derive molecular and physical properties arising from (sub)atomic interactions. However, as molecules of practical interest are largely polyatomic, contemporary approximation schemes such as the Hartree–Fock scheme are computationally expensive due to the large number of electron repulsion integrals (ERIs). Central to the Hartree–Fock method is the efficient computation of ERIs over Gaussian functions (GTO-ERIs). Here, the well-known McMurchie–Davidson method (MD) offers an elegant formalism by incrementally extending Hermite Gaussian functions and auxiliary tabulated functions. Although the MD method offers a high degree of versatility to acceleration schemes through Graphics Processing Units (GPUs), the current GPU implementations limit the practical use of supported values of the azimuthal quantum number. In this paper, we propose a generalized framework capable of computing GTO-ERIs for arbitrary azimuthal quantum numbers, provided that the intermediate terms of the MD method can be stored. Our approach benefits from extending the MD recurrence relations through shells, batches, and triple-buffering of the shared memory, and ordering similar ERIs, thus enabling the effective parallelization and use of GPU resources. Furthermore, our approach proposes four GPU implementation schemes considering the suitable mappings between Gaussian basis and CUDA blocks and threads. Our computational experiments involving the GTO-ERI computations of molecules of interest on an NVIDIA A100 Tensor Core GPU (NVIDIA, Santa Clara, CA, USA) have revealed the merits of the proposed acceleration schemes in terms of computation time, including up to a 72× improvement over our previous GPU implementation and up to a 4500× speedup compared to a naive CPU implementation, highlighting the effectiveness of our method in accelerating ERI computations for both monatomic and polyatomic molecules. Our work has the potential to explore new parallelization schemes of distinct and complex computation paths involved in ERI computation.
- 16 January 2025
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 37 (3)
Ising Models for Solving the N‐Queens Puzzle Based on the Domain‐Wall Vectors
An Ising model is a mathematical model defined by an objective function comprising a quadratic formula of multiple spin variables, each taking values of either or . The task of determining a spin value assignment to these variables that minimizes the resulting value of an Ising model is a challenging optimization problem. Recently, quantum annealers, consisting of qubit cells interconnected according to principles of quantum mechanics, have emerged as a solution for tackling such problems. Ising models characterized by fewer quadratic terms are preferable as they reduce the resource requirements of quantum annealers. Additionally, it is advantageous for the absolute values of coefficients associated with linear and quadratic terms to be small to facilitate the discovery of good solutions, given the inherent limitations in the resolution of quantum annealers. The primary contribution of this article lies in presenting Ising models tailored for solving the ‐Queens puzzle. The conventional Ising model for this puzzle involves quadratic terms, with the maximum absolute value of coefficients being . Our novel Ising model significantly reduces the number of quadratic terms to only , with a maximum absolute coefficient of 6. Furthermore, we provide embedding results for a quantum annealer D‐Wave Advantage utilizing a Pegasus graph . We succeeded in embedding our novel Ising model for up to the 21‐Queens puzzle, while the conventional Ising model can be embedded only for up to the 14‐Queens puzzle.
- 16 January 2025
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 37 (3)
Ising Models for Solving the N‐Queens Puzzle Based on the Domain‐Wall Vectors
An Ising model is a mathematical model defined by an objective function comprising a quadratic formula of multiple spin variables, each taking values of either or . The task of determining a spin value assignment to these variables that minimizes the resulting value of an Ising model is a challenging optimization problem. Recently, quantum annealers, consisting of qubit cells interconnected according to principles of quantum mechanics, have emerged as a solution for tackling such problems. Ising models characterized by fewer quadratic terms are preferable as they reduce the resource requirements of quantum annealers. Additionally, it is advantageous for the absolute values of coefficients associated with linear and quadratic terms to be small to facilitate the discovery of good solutions, given the inherent limitations in the resolution of quantum annealers. The primary contribution of this article lies in presenting Ising models tailored for solving the ‐Queens puzzle. The conventional Ising model for this puzzle involves quadratic terms, with the maximum absolute value of coefficients being . Our novel Ising model significantly reduces the number of quadratic terms to only , with a maximum absolute coefficient of 6. Furthermore, we provide embedding results for a quantum annealer D‐Wave Advantage utilizing a Pegasus graph . We succeeded in embedding our novel Ising model for up to the 21‐Queens puzzle, while the conventional Ising model can be embedded only for up to the 14‐Queens puzzle.
- Open Access
- 19 November 2024
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 37 (2)
GPU Acceleration of the Boys Function Evaluation in Computational Quantum Chemistry
The Boys function, a mathematical integral function, plays a pivotal role and is frequently evaluated in ab initio molecular orbital computations. The main contribution of this paper is to accelerate the bulk evaluation of the Boys function through the effective utilization of GPUs. The proposed GPU implementation addresses GPU‐specific programming issues such as warp divergence and coalesced/stride access to global memory, and we employ the optimal numerical evaluation method from four methods based on input values to ensure efficient computation with sufficient accuracy. Moreover, to consider actual computation of molecular integrals, we have implemented and evaluated the proposed method in two scenarios: single evaluation, which computes a single value of the Boys function for a single input, and incremental evaluation, which computes multiple values of the Boys function incrementally. The execution time of the proposed GPU implementation was evaluated for both scenarios using an NVIDIA A100 Tensor Core GPU. As a result, the GPU‐accelerated bulk evaluation has achieved a throughput of computing the values of the Boys function times per second for the single evaluation and times per second for the incremental evaluation, respectively. Our parallelized CPU and GPU implementation is available at https://github.com/sstsuji/Boys‐function‐GPU‐library.
- 19 November 2024
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 37 (2)
Open AccessGPU Acceleration of the Boys Function Evaluation in Computational Quantum Chemistry
The Boys function, a mathematical integral function, plays a pivotal role and is frequently evaluated in ab initio molecular orbital computations. The main contribution of this paper is to accelerate the bulk evaluation of the Boys function through the effective utilization of GPUs. The proposed GPU implementation addresses GPU‐specific programming issues such as warp divergence and coalesced/stride access to global memory, and we employ the optimal numerical evaluation method from four methods based on input values to ensure efficient computation with sufficient accuracy. Moreover, to consider actual computation of molecular integrals, we have implemented and evaluated the proposed method in two scenarios: single evaluation, which computes a single value of the Boys function for a single input, and incremental evaluation, which computes multiple values of the Boys function incrementally. The execution time of the proposed GPU implementation was evaluated for both scenarios using an NVIDIA A100 Tensor Core GPU. As a result, the GPU‐accelerated bulk evaluation has achieved a throughput of computing the values of the Boys function times per second for the single evaluation and times per second for the incremental evaluation, respectively. Our parallelized CPU and GPU implementation is available at https://github.com/sstsuji/Boys‐function‐GPU‐library.
- 20 November 2023
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 36 (10)
Bit duplication technique to generate hard quadratic unconstrained binary optimization problems with adjustable sizes
Summary: Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem with adjustable sizes. The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with bits is converted to a hard QUBO problem with bits . We use random QUBO problems, N‐Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D‐Wave samplers with SA, D‐Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.
- 20 November 2023
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 36 (10)
Bit duplication technique to generate hard quadratic unconstrained binary optimization problems with adjustable sizes
Summary: Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem with adjustable sizes. The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with bits is converted to a hard QUBO problem with bits . We use random QUBO problems, N‐Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D‐Wave samplers with SA, D‐Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.
- Open Access
- 17 October 2023
- Published by MDPI AG in Technologies
- Vol. 11 (5) , 143
Dual-Matrix Domain Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes
The Ising model is defined by an objective function using a quadratic formula of qubit variables. The problem of an Ising model aims to determine the qubit values of the variables that minimize the objective function, and many optimization problems can be reduced to this problem. In this paper, we focus on optimization problems related to permutations, where the goal is to find the optimal permutation out of the possible permutations of n elements. To represent these problems as Ising models, a commonly employed approach is to use a kernel that applies one-hot encoding to find any one of the permutations as the optimal solution. However, this kernel contains a large number of quadratic terms and high absolute coefficient values. The main contribution of this paper is the introduction of a novel permutation encoding technique called the dual-matrix domain wall, which significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. Surprisingly, our dual-matrix domain-wall encoding reduces the quadratic term count and maximum absolute coefficient values from and to and 2, respectively. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models. Furthermore, we discuss a family of permutation problems that can be efficiently implemented using Ising/QUBO models with our dual-matrix domain-wall encoding.- 17 October 2023
- Published by MDPI AG in Technologies
- Vol. 11 (5) , 143
Open AccessDual-Matrix Domain Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes
The Ising model is defined by an objective function using a quadratic formula of qubit variables. The problem of an Ising model aims to determine the qubit values of the variables that minimize the objective function, and many optimization problems can be reduced to this problem. In this paper, we focus on optimization problems related to permutations, where the goal is to find the optimal permutation out of the possible permutations of n elements. To represent these problems as Ising models, a commonly employed approach is to use a kernel that applies one-hot encoding to find any one of the permutations as the optimal solution. However, this kernel contains a large number of quadratic terms and high absolute coefficient values. The main contribution of this paper is the introduction of a novel permutation encoding technique called the dual-matrix domain wall, which significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. Surprisingly, our dual-matrix domain-wall encoding reduces the quadratic term count and maximum absolute coefficient values from and to and 2, respectively. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models. Furthermore, we discuss a family of permutation problems that can be efficiently implemented using Ising/QUBO models with our dual-matrix domain-wall encoding.